Report
Teaser, summary, work performed and final results
Periodic Reporting for period 2 - SYMCAR (Symbolic Computation and Automated Reasoning for Program Analysis)
Teaser
Daily activities of our society, such as online banking or (semi-)autonomous driving, are routinely run by software. This software is growing in size and functionalities, but its reliability is hardly improving. We are getting used to the fact that software is error-prone and...
Summary
Daily activities of our society, such as online banking or (semi-)autonomous driving, are routinely run by software.
This software is growing in size and functionalities, but its reliability is hardly improving.
We are getting used to the fact that software is error-prone and insecure.
One cannot hope to fully eliminate the presence of software errors in computer systems – there are theoretical
results showing the hardness and limitations of such a task. However, one can try to minimize the presence
of such errors. Moreover, depending on the application and software domain, software errors can be identified
and corrected during software development, before public releases of software products.
The objective of our SYMCAR project is to advance the state-of-the-art in identifying
and correcting software errors by designing and using new methods based on automated reasoning and symbolic computation.
Our project automates program analysis by automating the generation and proving of program properties
that prevent programmers introducing errors during software development.
The work in our project is structure within the following two project parts (PP):
- (PP1) Automatic generation of program properties;
- (PP2) Reasoning with both theories and quantifiers.
Our project designs new ways to generate and prove program properties by relying on our symbol elimination method.
Our work proposes symbol elimination as the new kind of fully automatic approach to generating and
proving first-order properties. Various methods in program analysis, such as quantifier elimination, Groebner basis computation and Craig interpolation,
can be viewed as special instances of symbol elimination.
Results of our project are implemented in the Aligator software package for invariant generation and the Vampire theorem prover for generating and proving first-order software properties.
Our experimental results show that our techniques outperform state-of-the-art methods in program analysis and automated reasoning
– for example, 24 recent problems from the academic software verification community could be proved only by our work.
Work performed
The distinctive feature of our project is that it uses symbol elimination not only for generating, but also for proving program properties.
Unlike existing methods, symbol elimination is not restricted to quantifier-free formulas of first-order logic
but supports arbitrarily quantified first-order properties; such properties are crucial to express, for example,
operations over the computer memory.
Our project uses symbol elimination for generating polynomial and quantified loop invariants (PP1.1),
precise bounds on the worst-case execution of programs (PP1.3) and first-order interpolants of program properties (PP1.2).
Rather than analyzing programs only with affine arithmetic and restricted use of data structures,
we support a rich class of polynomial operations and various unbounded data structures, such as arrays and lists.
We designed new theorem proving techniques for proving quantified properties over such data structures and
introduced SAT-based techniques for integrating first-order theorem proving with theory reasoning (PP2.2).
We also developed new preprocessing techniques for quantified formulas with theories (PP2.1).
Our results come with a fully automated tool support, by relying on our Aligator and Vampire software.
With these tools at hand, software developers can integrate our methods within software development without the need of becoming experts in automated reasoning.
Final results
Unlike other approaches, our project makes no restriction on first-order theories of data structures
used in the software but supports full first-order reasoning, in particular generating and proving quantified
properties of software systems.
Our experiments demonstrate that no other method can reason about such properties with the same accuracy and
expressiveness as our work.
Our project also enables the generation of polynomial invariants that other techniques cannot infer.
For example, polynomial relations of numeric programs, such as Fibonacci numbers, can be derived only by our work.
In addition to generating and proving program properties, our project introduced new extensions to theorem provers for making them better suited for applications of program analysis.
Our results led to a new input standard in the first-order theorem proving community, allowing first-order reasoners and theory-specific solvers to support the same type of input problems.
We expect our project will further advance the state-of-the-art in reasoning-based program analysis.
We plan extending our work to generate polynomial inequality invariants, support probabilistic programs,
and further develop theory-specific inference rules and techniques to be used in first-order theorem provers.
We are also interested in making our work better suited for applications of program security, for example, by analyzing and proving reliability of smart contracts.