@phdthesis{819,
abstract = {Contagious diseases must transmit from infectious to susceptible hosts in order to reproduce. Whilst vectored pathogens can rely on intermediaries to find new hosts for them, many infectious pathogens require close contact or direct interaction between hosts for transmission. Hence, this means that conspecifics are often the main source of infection for most animals and so, in theory, animals should avoid conspecifics to reduce their risk of infection. Of course, in reality animals must interact with one another, as a bare minimum, to mate. However, being social provides many additional benefits and group living has become a taxonomically diverse and widespread trait. How then do social animals overcome the issue of increased disease? Over the last few decades, the social insects (ants, termites and some bees and wasps) have become a model system for studying disease in social animals. On paper, a social insect colony should be particularly susceptible to disease, given that they often contain thousands of potential hosts that are closely related and frequently interact, as well as exhibiting stable environmental conditions that encourage microbial growth. Yet, disease outbreaks appear to be rare and attempts to eradicate pest species using pathogens have failed time and again. Evolutionary biologists investigating this observation have discovered that the reduced disease susceptibility in social insects is, in part, due to collectively performed disease defences of the workers. These defences act like a “social immune system” for the colony, resulting in a per capita decrease in disease, termed social immunity. Our understanding of social immunity, and its importance in relation to the immunological defences of each insect, continues to grow, but there remain many open questions. In this thesis I have studied disease defence in garden ants. In the first data chapter, I use the invasive garden ant, Lasius neglectus, to investigate how colonies mitigate lethal infections and prevent them from spreading systemically. I find that ants have evolved ‘destructive disinfection’ – a behaviour that uses endogenously produced acidic poison to kill diseased brood and to prevent the pathogen from replicating. In the second experimental chapter, I continue to study the use of poison in invasive garden ant colonies, finding that it is sprayed prophylactically within the nest. However, this spraying has negative effects on developing pupae when they have had their cocoons artificially removed. Hence, I suggest that acidic nest sanitation may be maintaining larval cocoon spinning in this species. In the next experimental chapter, I investigated how colony founding black garden ant queens (Lasius niger) prevent disease when a co-foundress dies. I show that ant queens prophylactically perform undertaking behaviours, similar to those performed by the workers in mature nests. When a co-foundress was infected, these undertaking behaviours improved the survival of the healthy queen. In the final data chapter, I explored how immunocompetence (measured as antifungal activity) changes as incipient black garden ant colonies grow and mature, from the solitary queen phase to colonies with several hundred workers. Queen and worker antifungal activity varied throughout this time period, but despite social immunity, did not decrease as colonies matured. In addition to the above data chapters, this thesis includes two co-authored reviews. In the first, we examine the state of the art in the field of social immunity and how it might develop in the future. In the second, we identify several challenges and open questions in the study of disease defence in animals. We highlight how social insects offer a unique model to tackle some of these problems, as disease defence can be studied from the cell to the society. },
author = {Pull, Christopher},
pages = {122},
publisher = {IST Austria},
title = {{Disease defence in garden ants}},
doi = {10.15479/AT:ISTA:th_861},
year = {2017},
}
@phdthesis{820,
abstract = {The lac operon is a classic model system for bacterial gene regulation, and has been studied extensively in E. coli, a classic model organism. However, not much is known about E. coli’s ecology and life outside the laboratory, in particular in soil and water environments. The natural diversity of the lac operon outside the laboratory, its role in the ecology of E. coli and the selection pressures it is exposed to, are similarly unknown.
In Chapter Two of this thesis, I explore the genetic diversity, phylogenetic history and signatures of selection of the lac operon across 20 natural isolates of E. coli and divergent clades of Escherichia. I found that complete lac operons were present in all isolates examined, which in all but one case were functional. The lac operon phylogeny conformed to the whole-genome phylogeny of the divergent Escherichia clades, which excludes horizontal gene transfer as an explanation for the presence of functional lac operons in these clades. All lac operon genes showed a signature of purifying selection; this signature was strongest for the lacY gene. Lac operon genes of human and environmental isolates showed similar signatures of selection, except the lacZ gene, which showed a stronger signature of selection in environmental isolates.
In Chapter Three, I try to identify the natural genetic variation relevant for phenotype and fitness in the lac operon, comparing growth rate on lactose and LacZ activity of the lac operons of these wild isolates in a common genetic background. Sequence variation in the lac promoter region, upstream of the -10 and -35 RNA polymerase binding motif, predicted variation in LacZ activity at full induction, using a thermodynamic model of polymerase binding (Tugrul, 2016). However, neither variation in LacZ activity, nor RNA polymerase binding predicted by the model correlated with variation in growth rate. Lac operons of human and environmental isolates did not differ systematically in either growth rate on lactose or LacZ protein activity, suggesting that these lac operons have been exposed to similar selection pressures. We thus have no evidence that the phenotypic variation we measured is relevant for fitness.
To start assessing the effect of genomic background on the growth phenotype conferred by the lac operon, I compared growth on minimal medium with lactose between lac operon constructs and the corresponding original isolates, I found that maximal growth rate was determined by genomic background, with almost all backgrounds conferring higher growth rates than lab strain K12 MG1655. However, I found no evidence that the lactose concentration at which growth was half maximal depended on genomic background.},
author = {Jesse, Fabienne},
pages = {87},
publisher = {IST Austria},
title = {{The lac operon in the wild}},
doi = {10.15479/AT:ISTA:th_857},
year = {2017},
}
@phdthesis{821,
abstract = {This dissertation focuses on algorithmic aspects of program verification, and presents modeling and complexity advances on several problems related to the
static analysis of programs, the stateless model checking of concurrent programs, and the competitive analysis of real-time scheduling algorithms.
Our contributions can be broadly grouped into five categories.
Our first contribution is a set of new algorithms and data structures for the quantitative and data-flow analysis of programs, based on the graph-theoretic notion of treewidth.
It has been observed that the control-flow graphs of typical programs have special structure, and are characterized as graphs of small treewidth.
We utilize this structural property to provide faster algorithms for the quantitative and data-flow analysis of recursive and concurrent programs.
In most cases we make an algebraic treatment of the considered problem,
where several interesting analyses, such as the reachability, shortest path, and certain kind of data-flow analysis problems follow as special cases.
We exploit the constant-treewidth property to obtain algorithmic improvements for on-demand versions of the problems,
and provide data structures with various tradeoffs between the resources spent in the preprocessing and querying phase.
We also improve on the algorithmic complexity of quantitative problems outside the algebraic path framework,
namely of the minimum mean-payoff, minimum ratio, and minimum initial credit for energy problems.
Our second contribution is a set of algorithms for Dyck reachability with applications to data-dependence analysis and alias analysis.
In particular, we develop an optimal algorithm for Dyck reachability on bidirected graphs, which are ubiquitous in context-insensitive, field-sensitive points-to analysis.
Additionally, we develop an efficient algorithm for context-sensitive data-dependence analysis via Dyck reachability,
where the task is to obtain analysis summaries of library code in the presence of callbacks.
Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is (i)~linear in the number of call sites and (ii)~only logarithmic in the size of the whole library, as opposed to linear in the size of the whole library.
Finally, we prove that Dyck reachability is Boolean Matrix Multiplication-hard in general, and the hardness also holds for graphs of constant treewidth.
This hardness result strongly indicates that there exist no combinatorial algorithms for Dyck reachability with truly subcubic complexity.
Our third contribution is the formalization and algorithmic treatment of the Quantitative Interprocedural Analysis framework.
In this framework, the transitions of a recursive program are annotated as good, bad or neutral, and receive a weight which measures
the magnitude of their respective effect.
The Quantitative Interprocedural Analysis problem asks to determine whether there exists an infinite run of the program where the long-run ratio of the bad weights over the good weights is above a given threshold.
We illustrate how several quantitative problems related to static analysis of recursive programs can be instantiated in this framework,
and present some case studies to this direction.
Our fourth contribution is a new dynamic partial-order reduction for the stateless model checking of concurrent programs. Traditional approaches rely on the standard Mazurkiewicz equivalence between traces, by means of partitioning the trace space into equivalence classes, and attempting to explore a few representatives from each class.
We present a new dynamic partial-order reduction method called the Data-centric Partial Order Reduction (DC-DPOR).
Our algorithm is based on a new equivalence between traces, called the observation equivalence.
DC-DPOR explores a coarser partitioning of the trace space than any exploration method based on the standard Mazurkiewicz equivalence.
Depending on the program, the new partitioning can be even exponentially coarser.
Additionally, DC-DPOR spends only polynomial time in each explored class.
Our fifth contribution is the use of automata and game-theoretic verification techniques in the competitive analysis and synthesis of real-time scheduling algorithms for firm-deadline tasks.
On the analysis side, we leverage automata on infinite words to compute the competitive ratio of real-time schedulers subject to various environmental constraints.
On the synthesis side, we introduce a new instance of two-player mean-payoff partial-information games, and show
how the synthesis of an optimal real-time scheduler can be reduced to computing winning strategies in this new type of games.},
author = {Pavlogiannis, Andreas},
pages = {418},
publisher = {IST Austria},
title = {{Algorithmic advances in program analysis and their applications}},
doi = {10.15479/AT:ISTA:th_854},
year = {2017},
}
@phdthesis{838,
abstract = {In this thesis we discuss the exact security of message authentications codes HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). PMAC is a block-cipher based mode of operation, which also happens to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, under two assumptions. Unfortunately, for many instantiations of HMAC one of them has been found to be wrong. To restore the provable guarantees for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure variable input-length PRF. For adversaries making q queries, each of length at most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one initially XORs a mask to every message block, where the mask for the i th block is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is the i -th codeword of the Gray code. Our attack applies more generally to any sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As for NMAC , our first contribution is a simpler and uniform proof: If f is an ε -secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length at most ` blocks each. We also show that this ε + `qδ bound is basically tight by constructing an f for which an attack with advantage `qδ exists. Moreover, we analyze the PRF-security of a modification of NMAC called NI by An and Bellare that avoids the constant rekeying on multi-block messages in NMAC and allows for an information-theoretic analysis. We carry out such an analysis, obtaining a tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2 q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved by using τ i ’s that are k -wise independent, for k > 1 (the original has k = 1). We observe that the security of PMAC will not increase in general if k = 2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether k = 3 is already sufficient to get this level of security is left as an open problem. Keywords: Message authentication codes, Pseudorandom functions, HMAC, PMAC. },
author = {Rybar, Michal},
pages = {86},
publisher = {IST Austria},
title = {{(The exact security of) Message authentication codes}},
doi = {10.15479/AT:ISTA:th_828},
year = {2017},
}
@phdthesis{839,
abstract = {This thesis describes a brittle fracture simulation method for visual effects applications. Building upon a symmetric Galerkin boundary element method, we first compute stress intensity factors following the theory of linear elastic fracture mechanics. We then use these stress intensities to simulate the motion of a propagating crack front at a significantly higher resolution than the overall deformation of the breaking object. Allowing for spatial variations of the material's toughness during crack propagation produces visually realistic, highly-detailed fracture surfaces. Furthermore, we introduce approximations for stress intensities and crack opening displacements, resulting in both practical speed-up and theoretically superior runtime complexity compared to previous methods. While we choose a quasi-static approach to fracture mechanics, ignoring dynamic deformations, we also couple our fracture simulation framework to a standard rigid-body dynamics solver, enabling visual effects artists to simulate both large scale motion, as well as fracturing due to collision forces in a combined system. As fractures inside of an object grow, their geometry must be represented both in the coarse boundary element mesh, as well as at the desired fine output resolution. Using a boundary element method, we avoid complicated volumetric meshing operations. Instead we describe a simple set of surface meshing operations that allow us to progressively add cracks to the mesh of an object and still re-use all previously computed entries of the linear boundary element system matrix. On the high resolution level, we opt for an implicit surface representation. We then describe how to capture fracture surfaces during crack propagation, as well as separate the individual fragments resulting from the fracture process, based on this implicit representation. We show results obtained with our method, either solving the full boundary element system in every time step, or alternatively using our fast approximations. These results demonstrate that both of these methods perform well in basic test cases and produce realistic fracture surfaces. Furthermore we show that our fast approximations substantially out-perform the standard approach in more demanding scenarios. Finally, these two methods naturally combine, using the full solution while the problem size is manageably small and switching to the fast approximations later on. The resulting hybrid method gives the user a direct way to choose between speed and accuracy of the simulation. },
author = {Hahn, David},
pages = {124},
publisher = {IST Austria},
title = {{Brittle fracture simulation with boundary elements for computer graphics}},
doi = {10.15479/AT:ISTA:th_855},
year = {2017},
}