Automated fault localization via hierarchical multiple predicate switching

• A hierarchical multiple predicate switching (HMPS) technique is proposed to locate bugs efficiently.
• HMPS combines spectrum-based fault localization techniques with predicate switching techniques.
• Two switch instrumentation strategies and three switch combination strategies are presented to facilitate the search for critical predicates.
• The results show that HMPS finds critical predicates for 199 out of 300 common bugs, in which 111 out of 199 are identified only through switching multiple predicate instances.

Single predicate switching forcibly changes the state of a predicate instance at runtime and then identifies the root cause by examining the switched predicate, called critical predicate. However, switching one predicate instance has its limitations: in our experiments, we found that single predicate switching can only find critical predicates for 88 out of 300 common bugs in five real-life utility programs. For other 212 bugs, overcoming them may require switching multiple predicate instances. Nonetheless, taking all possible combinations of predicate instances into consideration will result in exponential explosion. Therefore, we propose a hierarchical multiple predicate switching technique, called HMPS, to locate faults effectively. Specifically, HMPS restricts the search for critical predicates to the scope of highly suspect functions identified by employing spectrum-based fault localization techniques. Besides, instrumentation methods and strategies for switch combination are presented to facilitate the search for critical predicates. The empirical studies show that HMPS is able to find critical predicates for 111 out of 212 bugs mentioned above through switching multiple predicate instances. In addition, HMPS captures 62% of these 300 bugs when examining up to 1% of the executed code, while the Barinel and Ochiai approaches locate 18% and 16% respectively.