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, “((<expr>))”, which represents any expression <expr> 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.

Note: As of now, we check each abstraction independently of others, and then merge them which necessitates isolation later. An alternative route is to simply accumulate abstractions as your find them, and when generating, regenerate each abstract node that you have accumulated. With this, we can be sure that each node that we mark as abstract is truly abstract. A problem here is that of semantic validity. That is, if say the first abstraction has only 0.5 chance of producing a valid input, and the next abstraction candidate has again only 0.5 chance of producing a valid input, combining them together will reduce the probability of valid input in any generation to 0.25, and as abstractions accumulate, the probability of generating semantically valid inputs drop. Hence, we instead identify them independently and later merge them, with the trade off being a later isolation step.

Another difference is that during isolation we leave every possibly causative part intact. That is, if A or B is necessary for fault reproduction, we leave both A and B as concrete. A user may instead change it to leave either A or B as concrete.

Artifacts available ACM artifact available functional ACM artifact functional reusable ACM artifact reusable

ACM Distinguished Paper distinguished paper