When does my Program do this? Learning Circumstances of Software Behavior

Summary

We introduce Alhazen—an approach that automatically determines the circumstances under which a particular program behavior, such as a failure, takes place. Alhazen starts with a run that exhibits this 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 determine _features_ from the elements such as existence, length, or numerical values. (3) We use a decision tree learner to _observe_ and _learn_ which input features are associated with the behavior in question. (4) We use the grammar to _generate additional inputs_ to further strengthen or refute hypotheses as learned associations. (5) By repeating steps 2 to 4, 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.”