Program Abstractions

Automated detection of relevant code features

Enterprise-scale software tends to be very complex, and abstracting away some of the complexity of the code is a necessary step to make its analysis manageable. The abstract version of the program is then analysed, and checks are executed to ensure that the result obtained also applies to the original code. Often, the abstraction is built on-the-fly and improved based on the feedback of the analysis.

Examples of the abstraction our researchers use include describing the program execution using a set of simple true-false predicates or more complex expressions, and over-approximating the behaviour of for and while loops in order to speed up their execution time.

Read our published work

SATABS: SAT-Based Predicate Abstraction for ANSI-C by Edmund M. Clarke, Daniel Kroening, Natasha Sharygina, Karen Yorav

This paper presents a model checking tool, SatAbs, that implements a predicate abstraction refinement loop. Existing software verification tools such as Slam, Blast, or Magic use decision procedures for abstraction and simulation that are limited to integers. SatAbs overcomes these limitations by using a SAT-solver. This allows the model checker to handle the semantics of the ANSI-C standard accurately. This includes a sound treatment of bit-vector overflow, and of the ANSI-C pointer arithmetic constructs.

Unbounded-Time Analysis of Guarded LTI Systems with Inputs by Abstract Acceleration by Dario Cattaruzza, Alessandro Abate, Peter Schrammel, Daniel Kroening

Linear Time Invariant (LTI) systems are ubiquitous in control applications. Unbounded-time reachability analysis that can cope with industrial-scale models with thousands of variables is needed. To tackle this problem, we use abstract acceleration, a method for unbounded-time polyhedral reachability analysis for linear systems. Existing variants of the method are restricted to closed systems, i.e., dynamical models without inputs or non-determinism. In this paper, we present an extension of abstract acceleration to linear loops with inputs, which correspond to discrete-time LTI control systems under guard conditions. The new method relies on a relaxation of the solution of the linear dynamical equation that leads to a precise over-approximation of the set of reachable states, which are evaluated using support functions. In order to increase scalability, we use floating-point computations and ensure soundness by interval arithmetic. Our experiments show that performance increases by several orders of magnitude over alternative approaches in the literature. In turn, this tremendous gain allows us to improve on precision by computing more expensive abstractions. We outperform state-of-the-art tools for unbounded-time analysis of LTI system with inputs in speed as well as in precision.

Lost in abstraction: Monotonicity in multi-threaded programs byt Alexander Kaiser, Daniel Kroening, and Thomas Wahl

Monotonicity in concurrent systems stipulates that, in any global state, system actions remain executable when new processes are added to the state. This concept is both natural and useful: if every thread’s memory is finite, monotonicity often guarantees the decidability of safety properties even when the number of running threads is unknown. In this paper, we show that finite-data thread abstractions for model checking can be at odds with monotonicity: predicate-abstracting monotone software can result in non-monotone Boolean programs — the monotonicity is lost in the abstraction . As a result, pertinent well-established safety checking algorithms for infinite-state systems become inapplicable. We demonstrate how monotonicity in the abstraction can be restored, without affecting safety properties. This improves earlier approaches of enforcing monotonicity via overapproximations. We implemented our solution in the unbounded-thread model checker monabs and applied it to numerous concurrent programs and algorithms, whose predicate abstractions are often fundamentally beyond existing tools.

Abstracting path conditions by Jan Strejcek, and Marek Trtik

We present a symbolic-execution-based algorithm that for a given program and a given program location in it produces a nontrivial necessary condition on input values to drive the program execution to the given location. The algorithm is based on computation of loop summaries for loops along acyclic paths leading to the target location. We also propose an application of necessary conditions in contemporary bug-finding and test-generation tools. Experimental results on several small benchmarks show that the presented technique can in some cases significantly improve performance of the tools.