This research was conducted by Peter Ohmann, Alexander Brooks, Loris D’Antoni, and Ben Liblit. The paper will appear in the ACM SIGPLAN 2017 Conference on Programming Language Design and Implementation (PLDI 2017).
Debugging is difficult. When software fails in production, debugging is even harder, as failure reports usually provide only an incomplete picture of the failing execution. We present a system that answers control-flow queries posed by developers as formal languages, indicating whether the query expresses control flow that is possible or impossible for a given failure report. We consider three separate approaches that trade off precision, expressiveness for failure constraints, and scalability. We also introduce a new subclass of regular languages, the unreliable trace languages, which are uniquely suited to answering control-flow queries in polynomial time. Our system answers queries remarkably efficiently when we encode failure constraints and user queries entirely as unreliable trace languages.
The full paper is being prepared for publication. A preprint should be available here on or shortly after April 15, 2017. A suggested BibTeX citation record is also available.