Capturing propagation of infected program states

ABSTRACT

Coverage-based fault-localization techniques find the fault-related positions in programs by comparing the execution statistics of passed executions and failed executions. They assess the fault suspiciousness of individual program entities and rank the statements in descending order of their suspiciousness scores to help identify faults in programs. However, many such techniques focus on assessing the suspiciousness of individual program entities but ignore the propagation of infected program states among them. In this paper, we use edge profiles to represent passed executions and failed executions, contrast them to model how each basic block contributes to failures by abstractly propagating infected program states to its adjacent basic blocks through control flow edges. We assess the suspiciousness of the infected program states propagated through each edge, associate basic blocks with edges via such propagation of infected program states, calculate suspiciousness scores for each basic block, and finally synthesize a ranked list of statements to facilitate the identification of program faults. We conduct a controlled experiment to compare the effectiveness of existing representative techniques with ours using standard bench-marks. The results are promising.

REFERENCES

• 1: R. Abreu, P. Zoeteweij, and A. J. C. van Gemund. On the accuracy of spectrum-based fault localization. In Proceedings of TAICPART-MUTATION 2007, pages 89--98. IEEE Computer Society Press, Los Alamitos, CA, 2007.
• 2: P. Arumuga Nainar, T. Chen, J. Rosin, and B. Liblit. Statistical debugging using compound Boolean predicates. In Proceedings of ISSTA 2007, pages 5--15. ACM Press, New York, NY, 2007.
• 3: G. K. Baah, A. Podgurski, and M. J. Harrold. The probabilistic program dependence graph and its application to fault diagnosis. In Proceedings ISSTA 2008, pages 189--200. ACM Press, New York, NY, 2008.
• 4: T. Ball and S. Horwitz. Slicing programs with arbitrary control-flow. In Proceedings of AADEBUG '93 volume 749 of Lecture Notes in Computer Science, pages 206--222. Springer, London, UK, 1993.
• 5: T. Ball, P. Mataga, and M. Sagiv. Edge profiling versus path profiling: the showdown. In Proceedings of POPL '98, pages 134--148. ACM Press, New York, NY, 1998.
• 6: B. Baudry, F. Fleurey, and Y. Le Traon. Improving test suites for efficient fault localization. In Proceedings of ICSE 2006, pages 82--91. ACM Press, New York, NY, 2006.
• 7: M. D. Bond and K. S. McKinley. Continuous path and edge profiling. In Proceedings of MICRO 2005, pages 130--140. IEEE Computer Society Press, Los Alamitos, CA, 2005.
• 8: T. Chilimbi, B. Liblit, K. Mehra, A. Nori, and K. Vaswani. Holmes: effective Statistical Debugging via Efficient Path Profiling. In Proceedings of ICSE 2009. IEEE Computer Society Press, Los Alamitos, CA, 2009.
• 9: H. Cleve and A. Zeller. Locating causes of program failures. In Proceedings of ICSE 2005, pages 342--351. ACM Press, New York, NY, 2005.
• 10: H. Do, S. G. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empirical Software Engineering, 10 (4): 405--435, 2005.
• 11: J. A. Durães and H. S. Madeira. Emulation of software faults: a field data study and a practical approach. IEEE Transactions on Software Engineering, 32 (11): 849--867, 2006.
• 12: S. G. Elbaum, G. Rothermel, S. Kanduri, and A. G. Malishevsky. Selecting a cost-effective test case prioritization technique. Software Quality Control, 12 (3): 185--210, 2004.
• 13: N. Gupta, H. He, X. Zhang, and R. Gupta. Locating faulty code using failure-inducing chops. In Proceedings ASE 2005, pages 263--272. ACM Press, New York, NY, 2005.
• 14: D. Jeffrey, N. Gupta, and R. Gupta. Fault localization using value replacement. In Proceedings of ISSTA 2008, pages 167--178. ACM Press, New York, NY, 2008.
• 15: J. A. Jones and M. J. Harrold. Empirical evaluation of the Tarantula automatic fault-localization technique. In Proceedings of ASE 2005, pages 273--282. ACM Press, New York, NY, 2005.
• 16: J. A. Jones, M. J. Harrold, and J. F. Bowring. Debugging in parallel. In Proceedings of ISSTA 2007. ACM Press, New York, NY, pages 16--26, 2007.
• 17: A. J. Ko and B. A. Myers. Debugging reinvented: asking and answering why and why not questions about program behavior. In Proceedings of ICSE 2008, pages 301--310. ACM Press, New York, NY, 2008.
• 18: B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In Proceedings of PLDI 2005, pages 15--26. ACM Press, New York, NY, 2005.
• 19: C. Liu, L. Fei, X. Yan, S. P. Midkiff, and J. Han. Statistical debugging: a hypothesis testing-based approach. IEEE Transactions on Software Engineering, 32 (10): 831--848, 2006.
• 20: M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In Proceedings of ASE 2003, pages 30--39. IEEE Computer Society Press, Los Alamitos, CA, 2003.
• 21: R. Santelices, J. A. Jones, Y. Yu, and M. J. Harrold. Lightweight fault-localization using multiple coverage types. In Proceedings of ICSE 2009. IEEE Computer Society Press, Los Alamitos, CA, 2009.
• 22: J. M. Voas. PIE: a dynamic failure-based technique. IEEE Transactions on Software Engineering, 18 (8): 717--727, 1992.
• 23: X. Wang, S. C. Cheung, W. K. Chan, and Z. Zhang. Taming coincidental correctness: refine code coverage with context pattern to improve fault localization. In Proceedings of ICSE 2009, pages 45--55. IEEE Computer Society Press, Los Alamitos, CA, 2009.
• 24: Y. Yu, J. A. Jones, and M. J. Harrold. An empirical study of the effects of test-suite reduction on fault localization. In Proceedings of ICSE 2008, pages 201--210. ACM Press, New York, NY, 2008.
• 25: A. Zeller. Isolating cause-effect chains from computer programs. In Proceedings of SIGSOFT 2002 / FSE-10, pages 1--10. ACM Press, New York, NY, 2002.
• 26: X. Zhang, N. Gupta, and R. Gupta. Locating faults through automated predicate switching. In Proceedings of ICSE 2006, pages 272--281. ACM Press, New York, NY, 2006.
• 27: Z. Zhang, W. K. Chan, T. H. Tse, P. Hu, and X. Wang. Is non-parametric hypothesis testing model robust for statistical fault localization? Information and Software Technology, to appear.
• 28: Z. Zhang, W. K. Chan, T. H. Tse, B. Jiang, and X. Wang. Capturing propagation of infected program states. Technical Report TR-2009-14. Department of Computer Science, The University of Hong Kong, Hong Kong, 2009.
• 29: Z. Zhang, B. Jiang, W. K. Chan, and T. H. Tse. Debugging through evaluation sequences: a controlled experimental study. In Proceedings of COMPSAC 2008, pages 128--135. IEEE Computer Society Press, Los Alamitos, CA, 2008.
• 30: D. G. Zill and M. R. Cullen. Advanced Engineering Mathematics. Jones and Bartlett Publishers, Sudbury, MA, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Experimentation, Verification

Keywords:
basic block, control-flow edge, edge profile, fault localization