Dissertation
Reasoning about object-oriented programs: from classes to interfaces
Throughout the history of computer science, a major challenge has been how to assert that software is free of bugs and works as intended. Software bugs can lead to serious negative impacts on any software system. Throughout the main body of the thesis, we implemented a series of studies on exploring ways to apply formal methods systematically for the verification of complex object-oriented libraries such as the Java Collection Framework.
- Author
- J. Bian
- Date
- 21 May 2024
- Links
- Thesis in Leiden Repository
We start with specifying and verifying methods in the java.util.LinkedList class, but we encounter challenges with methods that take an interface type as a parameter. To address this, we proposed to use histories as method calls and returns to completely determine the concrete state of any implementation and thus can be seen as a way to reason about the interface. The executable history-based (EHB) approach embeds histories and attributes directly as Java objects. This approach could be seamlessly integrated in the KeY theorem prover itself. However, the EHB approach still has its limitations, particularly when it comes to reasoning about the heap and properties of user-defined attributes.To mitigate this, we introduce the logical history-based (LHB) approach, which models histories as an external abstract data type with functions. Building on the LHB approach, we have developed a history-based refinement theory for reasoning about hierarchy in object-oriented programs.