Fault Localization for Exploratory Simulations
Gore, Ross, Computer Science - School of Engineering and Applied Science, University of Virginia
Reynolds, Paul, Department of Computer Science, University of Virginia
Predicate-level statistical debuggers are applied to software to identify program statements which cause software failures. These debuggers use a set of conditional propositions, or predicates, which are inserted into a program and tested at particular points. The debugger estimates the likelihood that each predicate reflects the fault via suspiciousness. Then, developers examine the predicates in decreasing order of suspiciousness estimate until the location of the fault is discovered.
While predicate-level statistical debuggers are often effective, they are not well suited to an important class of software, including exploratory simulations, which employ floating-point computations and continuous stochastic distributions to represent, or support the evaluation of, an underlying model. This dissertation addresses this deficiency with three contributions to improve the effectiveness of predicate-level statistical debuggers for software employing floating point computations and continuous stochastic distributions.
First, the concept of elastic predicates is introduced and their viability and effectiveness are established. Elastic predicates are formed from summary statistics of variable values profiled at instrumented program points. The result is predicates that more closely match where a fault is expressed. Experimental results for established benchmarks and widely used simulations show improved effectiveness and reasonable efficiency with elastic predicates.
Next, confounding bias within the measures used to estimate predicate suspiciousness is addressed. Confounding bias is reduced via a model that controls for two different previously unaccounted for variables that influence the suspiciousness of a predicate. Statistical matching is employed to further reduce confounding effects. Empirical results show that matching, in conjunction with the new model, significantly improves the effectiveness of the suspiciousness estimate in predicate-level statistical debuggers, including those employing elastic predicates.
Finally, the first analytical result concerning many-valued, as opposed to binary, passing extents for statistical debuggers is presented. These continuous or fuzzy, passing extents enable debugging to be applied to a large class of software employing stochastic distributions, which previously had been inapplicable for statistical debugging.
Combined, elastic predicates, reduced bias suspiciousness estimates and fuzzy passing extents significantly improve the state of the art for localizing sources of failures in all software, but particularly software employing floating point computations and continuous stochastic distributions.
PHD (Doctor of Philosophy)
computer science, fault localization, statistical debugging, simulation
All rights reserved (no additional license for public reuse)