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

doi:10.1007/s11704-016-5226-y

Front. Comput. Sci.

2016, Vol. 10

Issue (5) : 812-831 https://doi.org/10.1007/s11704-016-5226-y

RESEARCH ARTICLE

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

Xiaobing SUN^1,^2,³(

),Xin PENG^1,²,Bin LI³,Bixin LI⁴,Wanzhi WEN⁵

¹. School of Computer Science, Fudan University, Shanghai 200433, China
². Shanghai Key Laboratory of Data Science, Fudan University, Shanghai 200433, China
³. School of Information Engineering, Yangzhou University, Yangzhou 225127, China
⁴. School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
⁵. School of Computer Science and Technology, Nantong University, Nantong 226019, China

Download: PDF(1157 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Xiaobing SUN

Just Accepted Date: 08 January 2016 Online First Date: 18 July 2016 Issue Date: 07 September 2016

Cite this article:

Xiaobing SUN,Xin PENG,Bin LI, et al. IPSETFUL: an iterative process of selecting test cases for effective fault localization by exploring concept lattice of program spectra[J]. Front. Comput. Sci., 2016, 10(5): 812-831.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5226-y
https://academic.hep.com.cn/fcs/EN/Y2016/V10/I5/812

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 https://doi.org/10.1145/1101908.1101949
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 https://doi.org/10.1109/ICSM.2013.42
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 https://doi.org/10.1109/icsm.2009.5306303
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 https://doi.org/10.1145/2635868.2635906
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 https://doi.org/10.1016/j.jss.2013.08.031
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 https://doi.org/10.1016/j.jss.2013.11.1109
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 https://doi.org/10.1145/2593882.2593885
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 https://doi.org/10.1145/2001420.2001445
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 https://doi.org/10.1145/1143844.1143983
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 https://doi.org/10.1109/ase.2009.25
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 https://doi.org/10.1016/j.jss.2013.12.036
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 https://doi.org/10.1109/ICST.2014.28
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 https://doi.org/10.1145/1831708.1831715
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 https://doi.org/10.1109/qsic.2013.66
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 https://doi.org/10.1145/1081706.1081753
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 https://doi.org/10.1145/581396.581397
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 https://doi.org/10.1007/11528784_13
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 https://doi.org/10.1109/DAPSE.2013.6603802
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 https://doi.org/10.1145/2377656.2377660
28	Birkhoff G. Lattice Theory. Providence: American Mathematical Society Colloquium Publications, 1940 https://doi.org/10.1090/coll/025
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 https://doi.org/10.1007/978-3-540-24651-0_8
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 https://doi.org/10.1007/978-3-540-24651-0_31
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 https://doi.org/10.1109/DSN.2002.1029005
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 https://doi.org/10.1109/issre.2012.28
34	Weiser M. Program slicing. IEEE Transactions on Software Engineering, 1984, 10(4): 352–357 https://doi.org/10.1109/TSE.1984.5010248
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 https://doi.org/10.1145/2001420.2001446
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 https://doi.org/10.1016/j.infsof.2012.08.008
37	Debroy V, Wong W E. Combining mutation and fault localization for automated program debugging. Journal of Systems and Software, 2014, 90: 45–60 https://doi.org/10.1016/j.jss.2013.10.042
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 https://doi.org/10.1109/icsme.2014.41
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 https://doi.org/10.1109/icstw.2015.7107448
40	Zhang X Y, Gupta R. Cost effective dynamic program slicing. ACM SIGPLAN Notice, 2004, 39(6): 94–106 https://doi.org/10.1145/996893.996855
41	Chen T Y, Cheung Y Y. Dynamic program dicing. In: Proceedings of the Conference on Software Maintenance. 1993, 378–385 https://doi.org/10.1109/icsm.1993.366925
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 https://doi.org/10.1016/j.jss.2005.06.045
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 https://doi.org/10.1007/3-540-48166-4_19
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 https://doi.org/10.1145/1831708.1831717
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 https://doi.org/10.1145/1065010.1065014
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 https://doi.org/10.1145/1273463.1273468
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 https://doi.org/10.1109/ISSRE.2014.29
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 https://doi.org/10.1016/j.infsof.2014.05.022
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 https://doi.org/10.1016/j.infsof.2012.10.001
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 https://doi.org/10.1016/j.cl.2013.04.001

[1]

Supplementary Material

Download

[1]	Deheng YANG, Yuhua QI, Xiaoguang MAO, Yan LEI. Evaluating the usage of fault localization in automated program repair: an empirical study[J]. Front. Comput. Sci., 2021, 15(1): 151202-.
[2]	Farid FEYZI, Saeed PARSA. Inforence: effective fault localization based on information-theoretic analysis and statistical causal inference[J]. Front. Comput. Sci., 2019, 13(4): 735-759.
[3]	Jozef PÓCS,Jana PÓCSOVÁ. Basic theorem as representation of heterogeneous concept lattices[J]. Front. Comput. Sci., 2015, 9(4): 636-642.

Viewed

Full text

Abstract

Cited

Shared

Discussed