The research presented in this thesis concerns one of the most important questions in software engineering of our time: how can we make sure that software is free from memory safety bugs? Memory... Show moreThe research presented in this thesis concerns one of the most important questions in software engineering of our time: how can we make sure that software is free from memory safety bugs? Memory safety bugs are the major cause of common vulnerabilities and exposures, and their presence threatens the stability and security of our digital world. This question is so important that it has escalated to the highest level. In a recent White House press release (February 26, 2024), the National Cyber Director of the United States of America calls on the academic community to help solve this hard problem: “addressing [this challenge] is imperative to ensuring we can secure our digital ecosystem long-term and protect the security of our Nation.” The accompanying technical report advises on the use of memory safe programming languages, and prominently mentions formal methods as one way to achieve the highly desired freedom from bugs, including memory safety bugs.In this thesis, formal methods are studied that are used to analyze software for its correctness, where correctness means that software satisfies its specification and incorrectness means the presence of a bug. The focus is on separation logic, a formal method designed as a scalable technique in ensuring freedom from memory safety bugs. Nowadays, separation logic is a well-established field of research: it has been widely studied academically in the past twenty years, and is successfully applied on an industry-wide scale to ensure memory safety. For example, separation logic is the technique used to prove, with mathematical certainty, that memory safe programming languages (such as Rust and Go) indeed live up to the promise that “they offer a way to eliminate, not just mitigate, entire bug classes.”In two parts, this thesis presents important scientific contributions that fill a gap in the academic literature. The first part contains the missing completeness theorem for separation logic, that is on par with the fundamental result by Goedel for first-order logic. Completeness is important for any formal method as it shows that the formal method can be adequately used for demonstrating every validity. The second part finally introduces dynamic separation logic that gives an alternative way to analyze memory safety problems, such that now it is possible to prove elementary specifications without needing extra logical techniques. This is important because it ensures ‘backwards compatibility’ with automated reasoning techniques that are optimized for first-order logic. Show less
In this thesis we investigate different techniques and formalisms to address complexity introduced by unbounded structures in object-oriented programs. We give a representation of a weakest... Show moreIn this thesis we investigate different techniques and formalisms to address complexity introduced by unbounded structures in object-oriented programs. We give a representation of a weakest precondition calculus for abstract object creation in dynamic logic. Based on this calculus we define symbolic execution including abstract object creation. We investigate the complex behaviour introduced by multi-threading and give a formalism based on the transformation of multi-threaded reentrant call-graphs to thread automata and the application of context free language reachability to decide deadlock freedom of such programs. We give a formalisation of the observable interface behaviour of a concurrent, object-oriented language with futures and promises. The calculus captures the core of the Creol language and allows for a comparison with the concurrency model of thread-based, object-oriented languages like Java or C#. We give a technique to detect deadlock freedom for an Actor-like subset of the Creol language. Show less
