Abstract
Software programs are proliferating throughout modern life, to a point where even the simplest appliances such as lightbulbs contain software, in addition to the software embedded in cars and airplanes. The correct functioning of these programs is therefore of the utmost importance, for the quality and sustenance of life. Due to the complexity inherent in the software it can be very difficult for the software developer to guarantee the absence of errors; automated support in the form of automated program analysis is therefore essential.
Two methods have traditionally been proposed: model checking and abstract interpretation. Model checking views the program as a finite automaton and tries to prove logical properties over the automaton model, or present a counter-example if not possible — with a focus on precision. Abstract interpretation translates the program semantics into abstract semantics efficiently represented as a lattice structure, and tries to use the
invariants given by the lattice element to prove the absence of errors — with a focus on efficiency.
Previous work has argued that on a theoretical level the two methods are converging, and one method can indeed be used to solve the same problems as the other by a reformulation. This thesis argues that there is even a convergence on the practical level, and that a generalisation of the formalism of timed automata into lattice automata captures key aspects of both methods; indeed model checking timed automata can be formulated in terms of an abstract interpretation.
For the generalisation to lattice automata to have benefit it is important that efficient tools exist. This thesis presents multi-core tools for efficient and scalable reachability and Büchi emptiness checking of timed/lattice automata.
Finally, a number of case studies are considered, among others numerical analysis of c programs, and worst-case execution time analysis of ARM programs. It is shown how lattice automata allow automatic and manual tuning of the precision and efficiency of the verification procedure. In the case of worst-case execution time analysis a sound overapproximation of the hardware is needed; the case of identifying timing anomalous hardware for which such abstractions are hard to find is considered.
Two methods have traditionally been proposed: model checking and abstract interpretation. Model checking views the program as a finite automaton and tries to prove logical properties over the automaton model, or present a counter-example if not possible — with a focus on precision. Abstract interpretation translates the program semantics into abstract semantics efficiently represented as a lattice structure, and tries to use the
invariants given by the lattice element to prove the absence of errors — with a focus on efficiency.
Previous work has argued that on a theoretical level the two methods are converging, and one method can indeed be used to solve the same problems as the other by a reformulation. This thesis argues that there is even a convergence on the practical level, and that a generalisation of the formalism of timed automata into lattice automata captures key aspects of both methods; indeed model checking timed automata can be formulated in terms of an abstract interpretation.
For the generalisation to lattice automata to have benefit it is important that efficient tools exist. This thesis presents multi-core tools for efficient and scalable reachability and Büchi emptiness checking of timed/lattice automata.
Finally, a number of case studies are considered, among others numerical analysis of c programs, and worst-case execution time analysis of ARM programs. It is shown how lattice automata allow automatic and manual tuning of the precision and efficiency of the verification procedure. In the case of worst-case execution time analysis a sound overapproximation of the hardware is needed; the case of identifying timing anomalous hardware for which such abstractions are hard to find is considered.
| Bidragets oversatte titel | Program Analyse som Model Checking |
|---|---|
| Originalsprog | Engelsk |
| Vejledere |
|
| Udgiver | |
| Status | Udgivet - 1 sep. 2014 |