When does my program do this? learning circumstances of software behavior

A program fails. Under which circumstances does the failure occur? Our Alhazen approach starts with a run that exhibits a particular behavior and automatically determines input features associated with the behavior in question: (1) We use a grammar to parse the input into individual elements. (2) We use a decision tree learner to observe and learn which input elements are associated with the behavior in question. (3) We use the grammar to generate additional inputs to further strengthen or refute hypotheses as learned associations. (4) By repeating steps 2 and 3, we obtain a theory that explains and predicts the given behavior. In our evaluation using inputs for find, grep, NetHack, and a JavaScript transpiler, the theories produced by Alhazen predict and produce failures with high accuracy and allow developers to focus on a small set of input features: łgrep fails whenever the --fixed-strings option is used in conjunction with an empty search string. ž

• Software and its engineering → Software testing and debugging; • Theory of computation → Grammars and context-free languages; Oracles and decision trees; Active learning.