Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: Rui Abreu , Peter Zoeteweij , Arjan J. C. van Gemund, On the Accuracy of Spectrum-based Fault Localization, Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION, p.89-98, September 10-14, 2007
• 2: Piramanayagam Arumuga Nainar , Ting Chen , Jake Rosin , Ben Liblit, Statistical debugging using compound boolean predicates, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273467]
• 3: George K. Baah , Andy Podgurski , Mary Jean Harrold, The probabilistic program dependence graph and its application to fault diagnosis, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390654]
• 4: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 5: Thomas Ball , Peter Mataga , Mooly Sagiv, Edge profiling versus path profiling: the showdown, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.134-148, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268958]
• 6: Benoit Baudry , Franck Fleurey , Yves Le Traon, Improving test suites for efficient fault localization, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134299]
• 7: Michael D. Bond , Kathryn S. McKinley, Continuous Path and Edge Profiling, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.130-140, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.16]
• 8: Trishul M. Chilimbi , Ben Liblit , Krishna Mehra , Aditya V. Nori , Kapil Vaswani, HOLMES: Effective statistical debugging via efficient path profiling, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.34-44, May 16-24, 2009 [doi>10.1109/ICSE.2009.5070506]
• 9: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 10: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 11: Joao A. Duraes , Henrique S. Madeira, Emulation of Software Faults: A Field Data Study and a Practical Approach, IEEE Transactions on Software Engineering, v.32 n.11, p.849-867, November 2006 [doi>10.1109/TSE.2006.113]
• 12: Sebastian Elbaum , Gregg Rothermel , Satya Kanduri , Alexey G. Malishevsky, Selecting a Cost-Effective Test Case Prioritization Technique, Software Quality Control, v.12 n.3, p.185-210, September 2004 [doi>10.1023/B:SQJO.0000034708.84524.22]
• 13: Neelam Gupta , Haifeng He , Xiangyu Zhang , Rajiv Gupta, Locating faulty code using failure-inducing chops, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101948]
• 14: Dennis Jeffrey , Neelam Gupta , Rajiv Gupta, Fault localization using value replacement, Proceedings of the 2008 international symposium on Software testing and analysis, July 20-24, 2008, Seattle, WA, USA [doi>10.1145/1390630.1390652]
• 15: James A. Jones , Mary Jean Harrold, Empirical evaluation of the tarantula automatic fault-localization technique, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101949]
• 16: James A. Jones , James F. Bowring , Mary Jean Harrold, Debugging in Parallel, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273468]
• 17: Andrew J. Ko , Brad A. Myers, Debugging reinvented: asking and answering why and why not questions about program behavior, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368130]
• 18: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA [doi>10.1145/1065010.1065014]
• 19: Chao Liu , Long Fei , Xifeng Yan , Jiawei Han , Samuel P. Midkiff, Statistical Debugging: A Hypothesis Testing-Based Approach, IEEE Transactions on Software Engineering, v.32 n.10, p.831-848, October 2006 [doi>10.1109/TSE.2006.105]
• 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: Raul Santelices , James A. Jones , Yanbing Yu , Mary Jean Harrold, Lightweight fault-localization using multiple coverage types, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.56-66, May 16-24, 2009 [doi>10.1109/ICSE.2009.5070508]
• 22: Jeffrey M. Voas, PIE: A Dynamic Failure-Based Technique, IEEE Transactions on Software Engineering, v.18 n.8, p.717-727, August 1992 [doi>10.1109/32.153381]
• 23: Xinming Wang , S. C. Cheung , W. K. Chan , Zhenyu Zhang, Taming coincidental correctness: Coverage refinement with context patterns to improve fault localization, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.45-55, May 16-24, 2009 [doi>10.1109/ICSE.2009.5070507]
• 24: Yanbing Yu , James A. Jones , Mary Jean Harrold, An empirical study of the effects of test-suite reduction on fault localization, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368116]
• 25: Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587053]
• 26: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Locating faults through automated predicate switching, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134324]
• 27: Zhenyu Zhang , W. K. Chan , T. H. Tse , Peifeng Hu , Xinming Wang, Is non-parametric hypothesis testing model robust for statistical fault localization?, Information and Software Technology, v.51 n.11, p.1573-1585, November, 2009 [doi>10.1016/j.infsof.2009.06.013]
• 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: Zhenyu Zhang , Bo Jiang , W. K. Chan , T. H. Tse, Debugging through Evaluation Sequences: A Controlled Experimental Study, Proceedings of the 2008 32nd Annual IEEE International Computer Software and Applications Conference, p.128-135, July 28-August 01, 2008 [doi>10.1109/COMPSAC.2008.207]
• 30: Dennis G. Zill , Michael R. Cullen, Advanced Engineering Mathematics, Jones and Bartlett Publishers, Inc., 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