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
Complex applications such as incident management, social simulations, manufacturing applications, electronic auctions, e-institutions, and business to business applications are pervasive and... Show moreComplex applications such as incident management, social simulations, manufacturing applications, electronic auctions, e-institutions, and business to business applications are pervasive and important nowadays. Agent-oriented methodology is an advance in abstractionwhich can be used by software developers to naturally model and develop systems for suchapplications. In general, with respect to design methodologies, what it may be important tostress is that control structures should be added at later stages of design, in a natural top-downmanner going from specifications to implementations, by refinement. Too much detail (be itfor the sake of efficiency) in specifications often turns out to be harmful. To paraphrase D.E.Knuth, “Premature optimization is the root of all evil” (quoted in ‘The Unix ProgrammingEnvironment’ by Kernighan and Pine, p. 91).The aim of this thesis is to adapt formal techniques to the agent-oriented methodologyinto an executable theory of refinement. The justification for doing so is to provide correctagent-based software by design. The underlying logical framework of the theory we proposeis based on rewriting logic, thus the theory is executable in the same sense as rewriting logicis. The storyline is as follows. We first motivate and explain constituting elements of agentlanguages chosen to represent both abstract and concrete levels of design. We then proposea definition of refinement between agents written in such languages. This notion of refinement ensures that concrete agents are correct with respect to the abstract ones. The advantageof the definition is that it easily leads to formulating a proof technique for refinement viathe classical notion of simulation. This makes it possible to effectively verify refinement bymodel-checking. Additionally, we propose a weakest precondition calculus as a deductivemethod based on assertions which allow to prove correctness of infinite state agents. Wegeneralise the refinement relation from single agents to multi-agent systems in order to ensure that concrete multi-agent systems refine their abstractions. We see multi-agent systemsas collections of coordinated agents, and we consider coordination artefacts as being basedeither on actions or on normative rules. We integrate these two orthogonal coordinationmechanisms within the same refinement theory extended to a timed framework. Finally, wediscuss implementation aspects. Show less
