Differential assertion checking

Shuvendu K. Lahiri, Kenneth L. McMillan, Rahul Sharma, Chris Hawblitzel

TL;DR

This paper introduces Differential Assertion Checking (DAC), a novel approach to program verification that compares two versions of a program to find bugs. By focusing on relative correctness rather than absolute correctness, DAC significantly reduces the cost of verification and offers a practical way to identify regressions and suppress false alarms, especially for evolving software.

What Problem Does This Paper Address?

Static analysis tools, particularly for assertion checking, face adoption challenges due to the high cost of defining specifications, environment conditions, and auxiliary invariants. While previous versions of a program can aid analysis, existing methods like equivalence checking are too strict, and incremental verification struggles with existing false warnings. This paper addresses the need for a more cost-effective and practical approach to program verification, especially for software that evolves over time, by leveraging the relationship between different program versions.

Methods

The core of the paper is the formalization of Differential Assertion Checking (DAC). DAC defines a "differential error" as a scenario where one program version fails an assertion while another, starting from the same state, does not. This is achieved by transforming the problem of checking two programs into verifying assertions over a single, composed program. This modular approach allows existing program verifiers and invariant generation tools to be leveraged. The authors also propose a scheme for automatically inferring "conjunctive relative specifications" using the HOUDINI algorithm, which helps in synthesizing necessary invariants for the composed program.

Datasets

The paper evaluates their approach using several benchmarks:

  • VERISEC suite: Snippets of open-source programs with bug fixes, used for verifying bug fixes.
  • SIEMENS and SPACE suites: C benchmarks from the Software-artifact Infrastructure Repository, used for filtering warnings.
  • Windows Device Drivers: Drivers from Windows Vista and Windows 7, used for comparing absolute vs. differential reasoning.

No new benchmarks were introduced, but the paper utilizes existing suites to demonstrate the effectiveness of DAC.

Key Insights and Ideas

  • Relative correctness is cheaper: Proving that program B behaves "similarly" to program A (e.g., doesn't introduce new memory accesses) is often much easier and cheaper than proving B is absolutely correct on its own.
  • DAC as a "bug fix" verifier: DAC is particularly well-suited for verifying that a bug fix in one version of a program doesn't introduce new regressions in another.
  • Filtering false alarms: By comparing a new version to an older, presumably more stable one, DAC can help suppress warnings that were already present and are not related to the recent changes.
  • Natural relative specifications: DAC allows for writing specifications that directly capture the relationship between two versions without needing extensive modeling (e.g., ghost variables) to express properties.
  • Modular verification: The transformation into a single composed program enables modular analysis, allowing existing verifiers and invariant generators to be applied effectively.

Key Results

  • Bug Fix Verification: DAC successfully verified bug fixes for several C examples from the VERISEC suite, demonstrating that the corrected versions did not introduce new memory dereferences compared to the buggy versions. In most cases, relative contracts were automatically inferred by HOUDINI, proving sufficient.
  • Warning Filtering: Experiments on SIEMENS and SPACE benchmarks showed a significant reduction in warnings when using DAC compared to traditional single-program analysis. For example, on the SIEMENS suite, absolute checking yielded 110 versions with warnings, while sound differential checking reduced this to 50.
  • Runtime: Modular DAC approaches were observed to be significantly faster (10-100 times) than non-modular DAC, highlighting the scalability benefits of the proposed method.
  • Imprecision: The paper also illustrates how different levels of unsoundness in DAC can lead to varying numbers of warnings, with "bogus" (most unsound) yielding the fewest warnings, but potentially missing true bugs.

Limitations and Future Work

  • Loop Handling: The current approach relies on transforming loops into tail-recursive procedures. While this is standard, the paper notes that the control flow graph must be reducible for this to work efficiently.
  • Invariant Inference: While HOUDINI is used for inferring specifications, it's not guaranteed to find all necessary invariants, and the authors mention exploring interpolant-based methods for more complex cases.
  • Scalability of Non-Modular DAC: Non-modular DAC (inlining callees) was found to be computationally expensive and did not scale to larger programs.
  • Future Work: The authors plan to integrate other tools, such as those based on interpolants, to generate relative specifications when the current scheme is insufficient. They also aim to further explore the trade-offs between soundness and cost in DAC.

Summary updated

Abstract

Previous version of a program can be a powerful enabler for program analysis by defining new relative specifications and making the results of current program analysis more relevant. In this paper, we describe the approach of differential assertion checking (DAC) for comparing different versions of a program with respect to a set of assertions. DAC provides a natural way to write relative specifications over two programs. We introduce a novel modular approach to DAC by reducing it to safety checking of a composed program, which can be accomplished by standard program verifiers. In particular, we leverage automatic invariant generation to synthesize relative specifications for pairs of loops and procedures. We provide a preliminary evaluation of a prototype implementation within the SymDiff tool along two directions (a) soundly verifying bug fixes in the presence of loops and (b) providing a knob for suppressing alarms when checking a new version of a program.
BibTeX
@inproceedings{lahiri2013differential,
  author = {Shuvendu K. Lahiri and Kenneth L. McMillan and Rahul Sharma and Chris Hawblitzel},
  title = {{Differential assertion checking}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2013},
  doi = {10.1145/2491411.2491452},
}
Figure