Automated Program Analysis: Revisiting Precondition Inference through Constraint Acquisition

Grégoire Menguy, Sébastien Bardin, Nadjib Lazaar, Arnaud GotliebIJCAI 2022 · DOI

TL;DR

This paper introduces PRECA, a novel framework that uses Constraint Acquisition (CA) to automatically infer function preconditions from input-output examples. PRECA offers stronger theoretical guarantees than prior black-box methods and demonstrates superior performance in experiments, particularly for memory-related preconditions.

What Problem Does This Paper Address?

Software development and verification heavily rely on function preconditions, which specify the conditions under which a function is expected to execute correctly. However, these preconditions are rarely available and must be manually written, which is time-consuming and error-prone. While automated methods exist, they often struggle with complex code, black-box components, or lack theoretical guarantees. White-box approaches can be precise but fail on obfuscated code or when source code is unavailable. Black-box methods, which learn from execution traces, are more flexible but often depend heavily on the quality of test cases and lack formal assurances of correctness. This paper aims to bridge this gap by developing a black-box precondition inference technique with robust theoretical foundations.

Methods

The core of PRECA is its application of Constraint Acquisition (CA), a machine learning paradigm that learns constraints describing a target concept. In PRECA, the target concept is the weakest precondition of a function. The system operates in an active learning setting, meaning it actively generates test cases to query an oracle (the program itself) about its behavior.

Key methodological aspects include:

  • Constraint Acquisition Framework: PRECA adapts the CONACQ framework, which learns a set of constraints that correctly classify examples. It uses an "active" approach where the learner generates informative examples to reduce the search space efficiently.
  • Oracle: The oracle is the program under analysis. It takes an input, executes the function, and returns "yes" if the postcondition is met, "no" if it's violated or an error occurs, and "unknown" if a timeout occurs. This "unknown" capability is crucial for handling real-world program execution.
  • Bias: A critical component is the "bias," which is a predefined set of possible constraints from which the system learns. The paper proposes a specific bias for memory-related preconditions, including constraints on pointers (validity, aliasing) and integers.
  • Background Knowledge and Preprocessing: To speed up convergence, PRECA incorporates background knowledge (e.g., transitivity of equality) and a preprocessing step that prioritizes "likely-positive" queries (those that are unlikely to cause immediate errors).

Datasets

The paper evaluates PRECA on a benchmark of 50 real-world C functions. This benchmark includes functions from standard libraries (string.h), academic benchmarks (DSA, Frama-C WP test suite, Siemens suite), and programming textbooks. The functions vary in size and complexity, with many containing loops and some with recursive calls. For evaluation, the authors consider two postcondition scenarios: an implicit "true" postcondition and manually chosen explicit postconditions.

Key Insights and Ideas

  • Constraint Acquisition for Program Analysis: The paper demonstrates that CA, a technique traditionally used in other domains, is a powerful and theoretically sound approach for automated precondition inference in program analysis.
  • Active Learning with Guarantees: PRECA's active learning strategy, combined with its CA foundation, allows it to achieve stronger theoretical guarantees (consistency and soundness) compared to prior black-box methods.
  • Memory-Related Preconditions: The paper successfully tailors PRECA to infer memory-related preconditions, which are critical for safety and security in systems programming. The proposed constraint language and bias are effective for this domain.
  • Surprising Performance: PRECA significantly outperforms existing black-box and even white-box methods in terms of both correctness (inferring weakest preconditions) and speed, often achieving better results with much less time.

Key Results

  • High Accuracy: With a 5-minute time budget per function and no explicit postcondition, PRECA infers the weakest precondition for 46 out of 50 functions. With explicit postconditions, it infers them for 18 out of 44 functions within 5 minutes.
  • Speed Advantage: PRECA with a 5-second budget infers more weakest preconditions than prior approaches with a 1-hour budget. For example, PRECA infers 38/50 weakest preconditions in 5s, while Daikon, PIE, and Gehr et al. achieve 26/50, 17/50, and 1/50 respectively in 1 hour.
  • Robustness: PRECA performs exceptionally well on "hard" scenarios where white-box methods fail, such as when source code is unavailable, obfuscated, or contains inline assembly. In these cases, P-Gen (a white-box method) infers no preconditions, while PRECA maintains its performance.
  • Active Learning Benefits: PRECA's active learning approach significantly outperforms its passive counterpart (using random queries), highlighting the effectiveness of its query generation strategy.

Limitations and Future Work

  • Handling Constant Values: The paper notes that handling constant values in preconditions is challenging, as it's difficult to select relevant constants for the bias without making it explode.
  • Horn Clause Size: While a heuristic is used for selecting the size of Horn clauses in the bias, a more principled approach is desirable.
  • Determinism Assumption: PRECA currently assumes that the function under analysis is deterministic.
  • Future Work: The authors suggest exploring more sophisticated bias selection, handling non-deterministic functions, and extending the approach to infer other types of program properties.

Summary updated

BibTeX
@inproceedings{menguy2022automated,
  author = {Grégoire Menguy and Sébastien Bardin and Nadjib Lazaar and Arnaud Gotlieb},
  title = {{Automated Program Analysis: Revisiting Precondition Inference through Constraint Acquisition}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/260},
}
Figure