Journal of Systems and Software 83 (2): 174-187 (2010)

Fault Localization through Evaluation Sequences 1

Zhenyu Zhang 2 , Bo Jiang 2 , W.K. Chan 3 , T.H. Tse 4 , and Xinming Wang 5

[paper from ScienceDirect | technical report TR-2009-20]


Predicate-based statistical fault-localization techniques find fault-relevant predicates in a program by contrasting the statistics of the evaluation results of individual predicates between failed runs and successful runs. While short-circuit evaluations may occur in program executions, treating predicates as atomic units ignores this fact, masking out various types of useful statistics on dynamic program behavior. In this paper, we differentiate the short-circuit evaluations of individual predicates on individual program statements, producing one set of evaluation sequences per predicate. We then investigate experimentally the effectiveness of using these sequences to locate faults by comparing existing predicate-based techniques with and without such differentiation. We use both the Siemens program suite and four real-life UNIX utility programs as our subjects. The experimental results show that the proposed use of short-circuit evaluations can, on average, improve predicate-based statistical fault-localization techniques while incurring relatively small performance overhead.

Keywords: fault localization, Boolean expression, predicate, evaluation sequence

1. This project is supported in part by the General Research Fund of the Research Grants Council of Hong Kong (project nos. 111107 and 716507).
2. Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong.
3. Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Hong Kong.
4. (Corresponding author.)
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong.
5. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong.


  Cumulative visitor count