IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra

Abstract

Fault localization is an important and challenging task during software testing. Among techniques studied in this field, program spectrum based fault localization is a promising approach. To perform spectrum based fault localization, a set of test oracles should be provided, and the effectiveness of fault localization depends highly on the quality of test oracles. Moreover, their effectiveness is usually affected when multiple simultaneous faults are present. Faced with multiple faults it is difficult for developers to determine when to stop the fault localization process. To address these issues, we propose an iterative fault localization process, i.e., an iterative process of selecting test cases for effective fault localization (IPSETFUL), to identify as many faults as possible in the program until the stopping criterion is satisfied. It is performed based on a concept lattice of program spectrum (CLPS) proposed in our previous work. Based on the labeling approach of CLPS, program statements are categorized as dangerous statements, safe statements, and sensitive statements. To identify the faults, developers need to check the dangerous statements. Meantime, developers need to select a set of test cases covering the dangerous or sensitive statements from the original test suite, and a new CLPS is generated for the next iteration. The same process is proceeded in the same way. This iterative process ends until there are no failing tests in the test suite and all statements on the CLPS become safe statements. We conduct an empirical study on several subject programs, and the results show that IPSETFUL can help identifymost of the faults in the program with the given test suite. Moreover, it can save much effort in inspecting unfaulty program statements compared with the existing spectrum based fault localization techniques and the relevant state of the art technique.

Keywords

fault localization / program spectrum / concept lattice / test case selection / iterative process

References

[1] Jones J A, Harrold M J. Empirical evaluation of the tarantula automatic fault-localization technique. In: Proceedings of the IEEE/ACM International Conference on Automated Software Engineering. 2005, 273–282

[2] Le T D B, Lo D. Will fault localization work for these failures? An automated approach to predict effectiveness of fault localization tools. In: Proceedings of the 2013 IEEE International Conference on Software Maintenance. 2013, 310–319

[3] Jeffrey D, Gupta N, Gupta R. Effective and efficient localization of multiple faults using value replacement. In: Proceedings of IEEE International Conference on Software Maintenance. 2009, 221–230

[4] Nainar P A, Liblit B. Adaptive bug isolation. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. 2010, 255–264

[5] Xuan J F, Monperrus M. Test case purification for improving fault localization. In: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2014, 52–63

[6] Papadakis M, Le Traon Y. Effective fault localization viamutation analysis: a selective mutation approach. In: Proceedings of the 29th Annual ACM Symposium on Applied Computing. 2014, 1293–1300

[7] Mao X G, Lei Y, Dai Z Y, Qi Y H, Wang C S. Slice-based statistical fault localization. Journal of Systems and Software, 2014, 89: 51–62

[8] Lucia, Lo D, Xia X. Fusion fault localizers. In: Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering. 2014, 127–138

[9] Ju X, Jiang S, Chen X, Wang X Y, Zhang Y M, Cao H L. HSFal: effective fault localization using hybrid spectrum of full slices and execution slices. Journal of Systems and Software, 2014, 90: 3–17

[10] Xie X Y, Chen T Y, Kuo F C, Xu B W. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Transations on Software Engineering and Methodology, 2013, 22(4)

[11] Yoo S, Harman M, Clark D. Fault localization prioritization: comparing information-theoretic and coverage-based approaches. ACM Transations on Software Engineering and Methodology, 2013, 22(3)

[12] Orso A, Rothermel G. Software testing: a research travelogue (2000– 2014). In: Proceedings of the on Future of Software Engineering. 2014, 117–132

[13] Parnin C, Orso A. Are automated debugging techniques actually helping programmers? In: Proceedings of the 20th International Symposium on Software Testing and Analysis. 2011, 199–209

[14] Zheng A X, Jordan M I, Liblit B, Naik M, Aiken A. Statistical debugging: simultaneous identification of multiple bugs. In: Proceedings of the 23rd International Conference on Machine Learning. 2006, 1105–1112

[15] Abreu R, Zoeteweij P, van Gemund A J C. Spectrum-based multiple fault localization. In: Proceedings of the IEEE/ACM International Conference on Automated Software Engineering. 2009, 88–99

[16] Cellier P, Ducassé M, Ferré S, Ridoux O. Multiple fault localization with data mining. In: Proceedings of the 23rd International Conference on Software Engineering and Knowledge Engineering (SEKE’2011). 2011, 238–243

[17] Perez A, Abreu R, Riboira A. A dynamic code coverage approach to maximize fault localization efficiency. Journal of Systems and Software, 2014, 90: 18–28

[18] Moon S, Kim Y, Kim M, Yoo S. Ask the mutants: mutating faulty programs for fault localization. In: Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation. 2014, 153–162

[19] Artzi S, Dolby J, Tip F, Pistoia M. Directed test generation for effective fault localization. In: Proceedings of the 19th International Symposium on Software Testing and Analysis. 2010, 49–60

[20] Sun X B, Li B X, Wen W Z. CLPS-MFL: using concept lattice of program spectrum for effective multi-fault localization. In: Proceedings of the 13th International Conference on Quality Software. 2013, 204–207

[21] Liu C, Yan X F, Fei L, Han J W, Midkiff S P. SOBER: statistical modelbased bug localization. In: Proceedings of the 10th European Software Engineering Conference Held Jointly with the 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2005, 286–295

[22] Jones J A, Harrold M J, Stasko J. Visualization of test information to assist fault localization. In: Proceedings of the 24th International Conference on Software Engineering. 2002, 467–477

[23] Abreu R, Zoeteweij P, van Gemund A J. On the accuracy of spectrumbased fault localization. In: Proceedings of Testing: Academic and Industrial Conference Practice and Research Techniques-MUTATION, 2007. 2007, 89–98

[24] Ganter B, Wille R. Formal Concept Analysis: Mathematical Foundations. Berlin: Springer-Verlag, 1986

[25] Tilley T, Cole R, Becker P, Eklund P. A survey of formal concept analysis support for software engineering activities. Formal Concept Analysis, 2005, 250–271

[26] Sun X B, Chen Y, Li B, Li B X. Exploring software engineering data with formal concept analysis. In: Proceedings of 2013 International workshop on Data Analysis Patterns in Software Engineering. 2013, 14–16

[27] Poshyvanyk D, Gethers M, Marcus A. Concept location using formal concept analysis and information retrieval. ACM Transations on Software Engineering and Methodology, 2012, 21(4): 23

[28] Birkhoff G. Lattice Theory. Providence: American Mathematical Society Colloquium Publications, 1940

[29] Cigarrĺćn J M, Gonzalo J, Peñas A, Verdejo F. Browsing search results via formal concept analysis: automatic selection of attributes. In: Proceedings of International Conference on Formal Concept Analysis. 2004, 74–87

[30] van der Merwe D, Obiedkov S, Kourie D. AddIntent: a new incremental algorithm for constructing concept lattices. In: Proceedings of International Conference on Formal Concept Analysis. 2004, 372–385

[31] Santelices R, Jones J A, Yu Y B, Harrold M J. Lightweight faultlocalization using multiple coverage types. In: Proceedings of the 31st International Conference on Software Engineering. 2009, 56–66

[32] Chen M Y, Kiciman E, Fratkin E, Fox A, Brewer E. Pinpoint: problem determination in large, dynamic internet services. In: Proceedings of the 32nd IEEE/IFIP International Conference on Dependable Systems and Networks. 2002, 595–604

[33] Steimann F, Frenkel M. Improving coverage-based localization of multiple faults using algorithms from integer linear programming. In: Proceedings of the 23rd IEEE International Symposium on Software Reliability Engineering. 2012, 121–130

[34] Weiser M. Program slicing. IEEE Transactions on Software Engineering, 1984, 10(4): 352–357

[35] DiGiuseppe N, Jones J A. On the influence of multiple faults on coverage-based fault localization. In: Proceedings of the 2011 International Symposium on Software Testing and Analysis. 2011, 210–220

[36] Xie X Y, Wong W E, Chen T Y, Xu B W. Metamorphic slice: an application in spectrum-based fault localization. Information of Software Technology, 2013, 55(5): 866–879

[37] Debroy V, Wong W E. Combining mutation and fault localization for automated program debugging. Journal of Systems and Software, 2014, 90: 45–60

[38] Xuan J F, Monperrus M. Learning to combine multiple ranking metrics for fault localization. In: Proceedings of the 30th IEEE International Conference on Software Maintenance and Evolution. 2014, 191–200

[39] Gong P, Zhao R L, Li Z. Faster mutation-based fault localization with a novel mutation execution strategy. In: Proceedings of the 8th IEEE International Conference on Software Testing, Verification and Validation. 2015, 1–10

[40] Zhang X Y, Gupta R. Cost effective dynamic program slicing. ACM SIGPLAN Notice, 2004, 39(6): 94–106

[41] Chen T Y, Cheung Y Y. Dynamic program dicing. In: Proceedings of the Conference on Software Maintenance. 1993, 378–385

[42] Wong W E, Qi Y. Effective program debugging based on execution slices and inter-block data dependency. Journal of Systems and Software, 2006, 79(7): 891–903

[43] Gyimothy T, Beszedes Á, Forgacs I. An efficient relevant slicing method for debugging. In: Proceedings of the Conference on Foundations of Software Engineering. 1999, 303–321

[44] Baah G K, Podgurski A, Harrold M J. Causal inference for statistical fault localization. In: Proceedings of the 19th International Symposium on Software Testing and Analysis. 2010, 73–84

[45] Liblit B, Naik M, Zheng A X, Aiken A, Jordan M I. Scalable statistical bug isolation. In: Proceedings of the 2005 ACMSIGPLAN Conference on Programming Language Design and Implementation. 2005, 15–26

[46] Jones J A, Bowring J F, Harrold M J. Debugging in parallel. In: Proceedings of the 2007 International Symposium on Software Testing and Analysis. 2007, 16–26

[47] Hogerle W, Steimann F, Frenkel M. More debugging in parallel. In: Proceedings of the 25th IEEE International Symposium on Software Reliability Engineering, ISSRE 2014. 2014, 133–143

[48] Gong D D, Su X H, Wang T T, Ma P J, Yua W. State dependency probabilistic model for fault localization. Information of Software Technology, 2015, 57(1): 430–445

[49] Jiang B, Zhai K, Chan W K, Tse T H, Zhang Z Y. On the adoption of MC/DC and control-flow adequacy for a tight integration of program testing and statistical fault localization. Information of Software Technology, 2013, 55(5): 897–917

[50] Gong D D, Wang T T, Sa X H, Ma P S. A test-suite reduction approach to improving fault-localization effectiveness. Computer Language, Systems & Structure, 2013, 39(3): 95–108

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg