This paper presents an approach to automatically analyzing program spectra, an execution profile of program testing results for fault localization. Using a mathematical theory of evidence for uncertainty reasoning, the proposed approach estimates the likelihood of faulty locations based on evidence from program spectra. Our approach is theoretically grounded and can be computed online. Therefore, we can predict fault locations immediately after each test execution is completed. We evaluate the approach by comparing its performance with the top three performing fault localizers using a benchmark set of real-world programs. The results show that our approach is at least as effective as others with an average effectiveness (the reduction of the amount of code examined to locate a fault) of 85.6% over 119 versions of the programs. We also study the quantity and quality impacts of program spectra on our approach where the quality refers to the spectra support in identifying that a certain unit is faulty. The results show that the effectiveness of our approach slightly improves with a larger number of failed runs but not with a larger number of passed runs. Program spectra with support quality increases from 1% to 100% improves the approach's effectiveness by 3.29%. 1. Introduction Identifying location of faulty software is notoriously known to be among the most costly and time-consuming process in software development [1, 2]. As software gets larger and more complex, the task can be daunting even with the help of debugging tools. Over the decades, many approaches to software fault localization have been studied including diagnostic reasoning [3], program slicing [4], nearest neighbor [5], and statistical analysis [6, 7]. Recent fault localization techniques have focused on automatically analyzing program behaviors observed from the execution of a suite of test cases on the tested program called program spectra [8]. For each run of the test case, certain program units (e.g., statements or blocks of code) are executed and result in either a passed test (run, or execution) when the output of the program’s execution is the same as the expected output, or a failed test, otherwise. A collection of program spectra contains execution profiles that indicate which part of the program is involved in each test run and whether it is passed or failed. Spectrum-based fault localization basically tries to identify the part of the program whose activity correlates most with the resulting passed or failed test runs. Most existing spectrum-based approaches rely on similarity
References
[1]
B. Hailpern and P. Santhanam, “Software debugging, testing, and verification,” IBM Systems Journal, vol. 41, no. 1, pp. 4–12, 2002.
[2]
I. Vessey, “Expertise in debugging computer programs: an analysis of the content of verbal protocols,” IEEE Transactions on Systems, Man and Cybernetics, vol. 16, no. 5, pp. 621–637, 1986.
[3]
R. Sedlmeyer, W. B. Thompson, and P. E. Johnson, “Diagnostic reasoning in software fault localization,” in Proceedings of the 8th International Joint Conference on Artificial Intelligence, vol. 1, pp. 29–31, Morgan Kaufmann, San Francisco, Calif, USA, 1983.
[4]
M. Weiser, “Programmers use slices when debugging,” Communications of the ACM, vol. 25, no. 7, pp. 446–452, 1982.
[5]
M. Renieres and S. P. Reiss, “Fault localization with nearest neighbor queries,” in Proceedings of the 18th IEEE International Conference on Automated Software Engineering, pp. 30–39, Providence, RI, USA, 2003.
[6]
B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan, “Scalable statistical bug isolation,” in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 15–26, Association for Computing Machinery, New York, NY, USA, 2005.
[7]
C. Liu, L. Fei, X. Yan, J. Han, and S. P. Midkiff, “Statistical debugging: a hypothesis testing-based approach,” IEEE Transactions on Software Engineering, vol. 32, no. 10, pp. 831–848, 2006.
[8]
T. Reps, T. Ball, M. Das, and J. Larus, “The use of program profiling for software maintenance with applications to the year 2000 problem,” in Proceedings of the 6th European Software Engineering Conference, pp. 432–449, Springer, New York, NY, USA, 1997.
[9]
R. Abreu, P. Zoeteweij, and A. van Gemund, “An evaluation of similarity coefficients for software fault localization,” in Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing, pp. 39–46, IEEE Computer Society Press, Riverside, Calif, USA, 2006.
[10]
R. Abreu, P. Zoeteweij, and A. van Gemund, “On the Accuracy of Spectrum-based Fault Localization,” in Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques (MUTATION '07), pp. 89–98, IEEE Computer Society Press, Washington, DC, USA, 2007.
[11]
S. Ali, J. H. Andrews, T. Dhandapani, and W. Wang, “Evaluating the accuracy of fault localization techniques,” in Proceedings of the IEEE/ACM International Conference on Automated Software Engineering, pp. 76–87, IEEE Computer Society Press, Washington, DC, USA, 2009.
[12]
M. Y. Chen, E. Kiciman, E. Fratkin, A. Fox, and E. Brewer, “Pinpoint: problem determination in large, dynamic internet services,” in Proceedings of the International Conference on Dependable Systems and Networks (DSN '02), pp. 595–604, Berkeley, Calif, USA, 2002.
[13]
J. Jones, M. J. Harrold, and J. Stasko, “Visualization of test information to assist fault localization,” in Proceedings of the 24th International Conference on Software Engineering, pp. 467–477, Association for Computing Machinery, New York, NY, USA, 2002.
[14]
A. Meyer, A. Garcia, A. Souza, and C. Souza Jr., “Comparison of similarity coefficients used for cluster analysis with dominant markers in maize (Zea mays L),” Genetics and Molecular Biology, vol. 27, no. 1, pp. 83–91, 2004.
[15]
S. Nessa, M. Abedin, E. W. Wong, L. Khan, and Y. Qi, “Software fault localization using N-gram analysis,” in Proceedings of the 3rd International Conference on Wireless Algorithms, Systems, and Applications, pp. 548–559, Springer, Berlin, Germany, 2008.
[16]
V. Dallmeier, C. Lindig, and A. Zeller, “Lightweight defect localization for Java,” in Proceedings of the 19th European Conference on Object-Oriented Programming, vol. 3568 of Lecture Notes in Computer Science, pp. 528–550, Springer, Glasgow, UK, 2005.
[17]
G. Shafer, A Mathematical Theory of Evidence, Princeton University Press, Princeton, NJ, USA, 1976.
[18]
J. Jones and M. J. Harrold, “Empirical evaluation of the tarantula automatic fault-localization technique,” in Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, pp. 273–282, Association for Computing Machinery, New York, NY, USA, 2005.
[19]
P. Jaccard, “étude comparative de la distribution florale dans une portion des Alpes et des Jura,” Bulletin de la Société Vaudoise des Sciences Naturelles, vol. 37, pp. 547–579, 1901.
[20]
A. Ochiai, “Zoogeographic studies on the soleoid fishes found in Japan and its neighbouring regions,” Bulletin of the Japanese Society for the Science of Fish, vol. 22, pp. 526–530, 1957.
[21]
J. Pearl, Causality: Models, Reasoning, and Inference, Cambridge University Press, 2000.
[22]
M. Hutchins, H. Foster, T. Goradia, and T. Ostrand, “Experiments of the effectiveness of dataflow- and control flow-based test adequacy criteria,” in Proceedings of the 6th International Conference on Software Engineering, pp. 191–200, IEEE Computer Society Press, Sorrento , Italy, 1994.
[23]
H. Agrawal, J. R. Horgan, S. London, and W. E. Wong, “Fault localization using execution slices and dataflow tests,” in Proceedings of the 6th International Symposium on Software Reliability Engineering, pp. 143–151, Toulouse , France, 1995.
[24]
W. Wong and Y. Qi, “BP neural network-based effective fault localization,” International Journal of Software Engineering and Knowledge Engineering, vol. 19, no. 4, pp. 573–597, 2009.
