Learning the Language of Software Errors

Hana Chockler, Pascal Kesseli, Daniel Kroening, Ofer StrichmanJAIR 2020 · DOI · OpenReview

Introduction

When automated verification tools like model checkers identify a bug, they typically produce a single "counterexample"—a specific execution trace leading to the error. In complex, real-world software, these traces can be millions of steps long and filled with low-level noise, leaving developers to wonder if the trace represents a unique edge case or a systemic root cause. This research introduces a method to summarize complex software bugs by learning a "language of errors" represented as a Deterministic Finite Automaton (DFA), providing a concise, visual map of the various ways a program assertion can fail.

The Learning Framework

The authors treat the set of all error-triggering execution paths as a formal language. To map this language, they utilize the $L^*$ learning algorithm, a classic method for learning unknown regular languages through iterative queries.

The interaction between the L* learning algorithm and the verification Oracle (CBMC).

In this framework, the system acts as both a Teacher and an Oracle:

  1. Membership Queries: The learner asks if a specific sequence of events leads to an error. The system instruments the code and uses Bounded Model Checking (CBMC) to verify the path.
  2. Conjecture Queries: Once the learner builds a candidate DFA, the Oracle checks if it perfectly represents the error space. If not, a counterexample is provided to refine the model.
  3. User-Defined Abstraction: To ensure the resulting DFA is human-readable, users define an "alphabet" of interesting events (e.g., specific function calls). This filters out low-level noise and focuses the analysis on architectural logic.

Optimizing with Lazy Learning

A significant challenge in this approach is the computational cost of running a model checker for every query. The authors introduce Lazy Learning, which optimizes the process by aggressively guessing that most execution paths do not lead to errors (answering "no" by default). These guesses are only verified in batches during the conjecture phase. This heuristic proved highly effective, with the "no" guesses being correct 97.9% of the time, ultimately saving an average of 75% of CBMC queries and reducing total runtime by 30%.

Key Insights and Real-World Impact

By viewing software misbehavior as a formal language, the tool—named PV—allows for advanced debugging techniques such as "visual diffing," where two versions of a program are compared to show only the behaviors present in one but not the other.

A Deterministic Finite Automaton (DFA) generated by PV, mapping error-triggering paths in a sorting implementation.

The tool was evaluated on several benchmarks, including an industrial case study of JQ, a popular command-line JSON processor. For the 75k-line JQ project, lazy learning reduced the analysis time from 59 minutes to 28 minutes and helped identify a previously unknown bug related to library search paths.

Limitations and Future Work

While powerful, the method is currently limited by the bounds of the model checker; bugs that occur beyond the specified loop or word-length bounds will not be captured. Additionally, because software logic is often context-free due to recursion, the authors suggest that future iterations could move toward learning Context-Free Grammars or Büchi automata to handle more complex liveness properties.

Summary updated

Abstract

We propose to use algorithms for learning deterministic finite automata (DFA), such as Angluin’s L* algorithm, for learning a DFA that describes the possible scenarios under which a given program error occurs. The alphabet of this automaton is given by the user (for instance, a subset of the function call sites or branches), and hence the automaton describes a user-defined abstraction of those scenarios. More generally, the same technique can be used for visualising the behavior of a program or parts thereof. It can also be used for visually comparing different versions of a program (by presenting an automaton for the behavior in the symmetric difference between them), and for assisting in merging several development branches. We present experiments that demonstrate the power of an abstract visual representation of errors and of program segments, accessible via the project’s web page. In addition, our experiments in this paper demonstrate that such automata can be learned efficiently over real-world programs. We also present lazy learning, which is a method for reducing the number of membership queries while using L*, and demonstrate its effectiveness on standard benchmarks.
BibTeX
@article{chockler2020learning,
  author = {Hana Chockler and Pascal Kesseli and Daniel Kroening and Ofer Strichman},
  title = {{Learning the Language of Software Errors}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  doi = {10.1613/jair.1.11798},
}
Figure