Ligia Nicoleta Nistor

Thesis Title: Object Propositions
Degree Type: Ph.D. in Computer Science
Advisor(s): Jonathan Aldrich
Graduated: December 2017

Abstract:

The presence of aliasing makes modular verification of object-oriented code difficult. If multiple clients depend on the properties of an object, one client may break a property that others depend on.

In this thesis we present a modular verification approach based on the novel abstraction of object propositions, which combine predicates and information about object aliasing. In our methodology, even if shared data is modified, we know that an object invariant specified by a client holds. Our permission system allows verification using a mixture of linear and nonlinear reasoning. This allows it to provide more modularity in some cases than competing separation logic approaches, because it can more effectively hide the exact aliasing relationships within a module. We have implemented the methodology into our tool Oprop. We have used Oprop to automatically verify a number of examples, thus showing the applicability of this research.

Thesis Committee:
Jonathan Aldrich (Chair)
Frank Pfenning
David Garlan
Matthew Parkinson (Microsoft Research)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Verification, Java, Oprop, logic, Boogie

CMU-CS-17-132.pdf (1.13 MB) ( 197 pages)
Copyright Notice