Abstracting Failure-Inducing Inputs

Summary

A program fails. Under which circumstances does the failure occur? Starting with a single failure-inducing input "The input '((4))' fails") and an input grammar, the DDSET algorithm uses systematic tests to automatically generalize the input to an _abstract failure-inducing input_ that contains both (concrete) terminal symbols and (abstract) nonterminal symbols from the grammar - for instance, "(())", which represents any expression in double parentheses. Such an abstract failure-inducing input can be used 1. as a *debugging diagnostic*, characterizing the circumstances under which a failure occurs ("The error occurs whenever an expression is enclosed in double parentheses"); 2. as a *producer* of additional failure-inducing tests to help design and validate fixes and repair candidates ("The inputs '((1))', '((3 * 4))', and many more also fail"). In its evaluation on real-world bugs in JavaScript, Clojure, Lua, and Coreutils, DDSET's abstract failure-inducing inputs provided to-the-point diagnostics, and precise producers for further failure inducing inputs.