ABSTRACT Automatic Isolation of Cause-Effect Chains with Machine Learning

Accurate bug localization is important for automated debugging. One attractive approach is to apply statistical-based techniques on large number of evaluation profiles of program predicates to locate bug causes. Previous research has proposed a number of specialized techniques to isolate certain predicates as bug predictors. However, these techniques still require a programmer to manually examine significant fractions of code to locate bugs, and no existing statistical-based technique can discover cause-effect chains. In this paper, we adapt advanced machine learning techniques (such as support vector machines and random forests) and propose an effective algorithm for both isolating bug-related predicates and discovering cause-effect chains. Our technique combines feature selection (to select bug-related predicates) and clustering (to group similar predicates) in a novel way to precisely pinpoint bug causes. We have implemented our technique and validated it on various instrumented code including the Siemens test suite and rhythmbox (a music management application for GNOME). Compared to previous techniques, our algorithm not only discovers more bugs but also requires significantly less manual code inspection. For example, on the Siemens test suite, it discovers 38 bugs when programmers are expected to examine no more than 1 % of the code, significantly better than 11, the best previously reported number (see Table 1, Section 5). Our algorithm also discovers previously unknown errors in ryhthmbox that were missed by previous techniques. 1