This dissertation discusses novel techniques for interpolation-based software model checking, an approximate method which uses Craig interpolation to compute invariants of programs. Our work addresses two aspects of program analyses based on model checking: verification (the construction of correctness proofs for programs) and falsification (the detection of counterexamples that violate the specification). In Hoare's calculus, a proof of correctness comprises assertions which establish that a program adheres to its specification. The principal challenge is to derive appropriate assertions and loop invariants. Contemporary software verification tools use Craig interpolation (as opposed to traditional predicate transformers such as the weakest precondition) to derive approximate assertions. The performance of the model checker is contingent on the Craig interpolants computed. We present novel interpolation techniques which provide the following advantages over existing methods. Firstly, the resulting interpolants are sound with respect to the bit-level semantics of programs, which is an improvement over interpolation systems that use linear arithmetic over the reals to approximate bit-vector arithmetic and/or do not support bit-level operations. Secondly, our interpolation systems afford us a choice of interpolants and enable us to fine-tune their logical strength and structure. In contrast, existing procedures are limited to a single ad-hoc choice of an interpolant. Interpolation-based verification tools are typically forced to refine an initial approximation repeatedly in order to achieve the accuracy required to establish or refute the correctness of a program. The detection of a counterexample containing a repetitive construct may necessitate one refinement step (involving the computation of additional interpolants) for each iteration of the loop. We present a heuristic that aims to avoid the repeated and computationally expensive construction of interpolants, thus enabling the detection of deeply buried defects such as buffer overflows. Finally, we present an implementation of our techniques and evaluate them on a set of standardised device driver and buffer overflow benchmarks.

De nombreux travaux ont montré l'importance de l'interpolation de Craig pour la structuration et la modularité des spécifications de type axiomatique. En vue d'en donner des conditions suffisantes dans un cadre théorique adapté à l'informatique, nous nous sommes intéressé à une propriété équivalente à l'interpolation de Craig dans le cadre de la théorie standard des modèles : la consistance de Robinson. L'étude de cette dernière propriété nous a amené à généraliser dans une spécialisation des institutions les notions classiques de diagrammes complets et de morphismes élémentaires. Ceci nous a alors permis de généraliser quelques résultats classiques de théorie des modèles tels que les théorèmes de Löwenheim-Skolem ou l'union de chaînes de Tarski. En fin, les constructeurs de formules étant explicites dans notre cadre théorique, nous nous sommes naturellemant intéressés à la combinaison de logiques et à la préservation de l'interpolation de Craig et de la consistance de Robinson.

The purpose of this study is to create a performer's guide for three separate pieces written by David Sampson. The first piece, Breakaway, is written for two trumpets and electronic accompaniment. The second piece is entitled Passage, and is written for muted flugelhorn and viola. The final piece for examination is the Sonata for trumpet entitled Triptych, a commission from the International Trumpet Guild in 1991. Although the number of compositions for trumpet has increased in the twentieth and twenty-first centuries, guides for the performer regarding pieces with unique instrumentation and internationally commissioned works extremely limited. Included in this study is an examination of the specific challenges found in Breakaway, Passage, and Triptych, with detailed consideration regarding the methods with which to execute the unique performance elements of each composition. In addition, the information found in this study will expand the number of twentieth and twenty-first century trumpet works that have been investigated in a formal research capacity.

Thesis (M.A.E.T.)--Covenant Theological Seminary, 2002. / Abstract. Includes bibliographical references (leaves 88-90).

Thesis (MA(N.T.))--University of Pretoria, 2006. / Includes bibliographical references (leaves 206-217) Available on the Internet via the World Wide Web.

Thesis (M.A.E.T.)--Covenant Theological Seminary, 2002. / Abstract. Includes bibliographical references (leaves 88-90).

Thesis (Ph.D.)--Memorial University of Newfoundland, 2003. / Bibliography: leaves 226-236.

Při verifikaci programů se snažíme rozhodnout, zda program obsahuje či neobsahuje chyby. Základním předpokladem všech verifikačních postupů je efektivní reprezentace a manipulace se stavy programů. V této práci představujeme techniky pro nalezení nepodstatných informací ve stavech programů a pro jejich odstranění. Tato práce obsahuje redukce vhodné pro explicitní i symbolickou reprezentaci stavů. Naše postupy vhodné pro explicitní reprezentaci byly speciálně navrženy pro vícevláknové programy. Naše analýzy dokáží nalézt takové hodnoty v dynamicky alokovaných objektech, tedy na haldě, které program již nebude v následujících krocích číst. Logické formule v predikátové nebo výrokové logice jsou převažující symbolickou reprezentací množin stavů programu. Craigovy interpolanty jsou jedním z obvyklých postupů pro získání formulí s požadovanými vlastnostmi. V této práci představujeme nový způsob jejich výpočtu, který používá přiřazení proměnných pro zmenšení jejich velikosti. Pomocí přiřazení proměnných můžeme zablokovat ty cesty v programu, které nechceme, aby interpolant bral v potaz a tím zmenšit jejich velikost.

Abstract. Since the introduction of interpolants to the field of symbolic model checking, interpolation-based methods have been successfully used in both hardware and software model checking. Recently, variable assignments have been introduced to the computation of interpolants. In the context of abstract reachability graphs, variable assignment can be used not only to prevent out-of-scope variables from appearing in interpolants, but also to reduce the size of the interpolant significantly. We further extend the framework for computing interpolants under variable assignment, prove the correctness of the system and show that it has potential to further decrease the size of the computed interpolants. At the end we analyze under which conditions the computed interpolants will still have the path interpolation property, a desired property in many interpolation-based techniques. 1

Le mémoire original s'accompagnait en annexe du livre-objet Le poids de l'oiseau sur la vitre. / Ce mémoire de maîtrise en recherche-création explore les modalités d’intégration d’éléments défiant, dans les romans dits hybrides, les conventions visuelles de la majeure partie du texte et participant à la construction du sens. Le poids de l’oiseau sur la vitre est un récit hybride qui suit le parcours d’une vieille femme revisitant un fragment du journal intime de sa jeunesse, écrit – ou imaginé – après la perte de son bébé. Un parcours qui est une seconde fuite car au fil des corrections et de la reconstruction du texte, elle tombe à nouveau dans le piège du mensonge. Confrontée à une surenchère du faux, elle réalisera que cette habitude de considérer la fiction comme un refuge équivaut à rester infidèle au passé, et ultimement à soi. L’essai associe Blankets de Craig Thompson, roman graphique au style composite, au roman hybride, et se consacre à l’étude de ses pages visuellement atypiques, cherchant à déterminer comment elles parviennent, malgré leur aspect divergent, à renforcer la cohésion et le caractère immersif de l’œuvre. / This practice-led M.A. thesis explores how in hybrid novels, the integration of elements defying the visual conventions of the majority of the text participate to their construction of meaning. In the hybrid narrative Le poids de l’oiseau sur la vitre, an elderly woman revisits her diary, written – or imagined – decades ago to shield her from the reality of her infant son’s death. At first intent on restoring the truth, she soon falls, through the many corrections she brings to the original text and her reconstruction of the book, into her habit of tweaking facts, realizing at last that giving in to this spiral of lies means cheating herself from the past and, ultimately, her future. The following essay likens Craig Thompson’s Blankets, a graphic novel whose structure dynamics are based upon the use of different styles and page layouts, to hybrid novels, and studies its most visually striking pages to determine how, despite their distinctive appearance, they enhance the novel’s cohesion and make it more immersive.