Learning the Language of Software Errors

Hana Chockler, Pascal Kesseli, Daniel Kroening, Ofer Strichman

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
125 Downloads (Pure)

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 webpage. 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 usingL∗, and demonstrate its effectiveness on standard benchmarks.
Original languageEnglish
Pages (from-to)881-903
Number of pages23
JournalJournal of Artificial Intelligence Research
Volume67
Early online date23 Apr 2020
DOIs
Publication statusPublished - Apr 2020

Fingerprint

Dive into the research topics of 'Learning the Language of Software Errors'. Together they form a unique fingerprint.

Cite this