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.
In this framework, the system acts as both a Teacher and an Oracle:
- 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.
- 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.
- 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.
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