Hierarchical Delta Debugging Abstract

Computer Science Inputs causing a program to fail are usually large and often contain information irrelevant to the failure. It thus helps debugging to simplify program inputs. The Delta Debugging algorithm is a general technique applicable to minimizing all failure-inducing inputs for more effective debugging. In this thesis, we present HDD, a simple but effective algorithm that significantly speeds up Delta Debugging and increases its output quality on tree structured inputs such as XML. Instead of treating the inputs as one flat atomic list, we apply Delta Debugging to the very structure of the data. In particular, we apply the original Delta Debugging algorithm to each level of a program’s input, working from the coarsest to the finest levels. We are thus able to prune the large irrelevant portions of the input early. With the careful application of our algorithm to any particular input language, HDD creates only syntactically valid variations of the input, thus reducing the number of inconclusive configurations tested and accordingly the amount of time spent simplifying. We also demonstrate a general framework requiring only the input language’s context-free grammar to automatically simplify input while ensuring that all test cases are syntactically valid. This frame-work proceeds by calculating correction strings of minimal length that can replace removed nodes from the input parse tree. We have implemented HDD and evaluated it on a number of real failure-inducing inputs from the GCC and Mozilla bugzilla databases. To demonstrate generality and the application of our framework, we have also evaluated it on a Java program injected with an error. Our Hierarchical Delta Debugging algorithm produces simpler outputs and takes orders of magnitude fewer test cases than the original Delta Debugging algorithm. It is able to scale to inputs of considerable size that the original Delta Debugging algorithm cannot process in practice. We argue that HDD is an effective tool for automatic debugging of programs expecting structured inputs