Special Issue Paper
On the use of mutations and testing for debugging
Mihai Nica,
Simona Nica,
Franz Wotawa,
Mihai Nica
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Search for more papers by this authorSimona Nica
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Search for more papers by this authorCorresponding Author
Franz Wotawa
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Correspondence to: Franz Wotawa, Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria.
E-mail: [email protected]
Search for more papers by this authorMihai Nica,
Simona Nica,
Franz Wotawa,
Mihai Nica
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Search for more papers by this authorSimona Nica
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Search for more papers by this authorCorresponding Author
Franz Wotawa
Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria
Correspondence to: Franz Wotawa, Institute for Software Technology, Graz University of Technology, Inffeldgasse 16b/II, 8010 Graz, Austria.
E-mail: [email protected]
Search for more papers by this authorSUMMARY
Tools for automated fault localization usually generate too many bug candidates depending on the underlying technique. Hence, more information is required in order to further restrict the number of bug candidates. Approaches that rely on specific knowledge of the program to be debugged, such as variable values at specific positions in the source code, are not easily accessible for users especially in the case of software maintenance. In order to avoid this problem, we suggest integrating testing to restrict the number of bug candidates. In particular, we propose computing possible corrections of the program and from this distinguishing test cases. A distinguishing test case is a test that reveals different output values for two program variants given the same input values. Besides the formal definitions and algorithms, we extend the first empirical results of our approach in this paper. The obtained empirical results show that the use of mutations and distinguishing test cases reduces the number of bug candidates by more than 90% on average. Copyright © 2012 John Wiley & Sons, Ltd.
REFERENCES
- 1 Wotawa F, Nica M, Aichernig BK. Generating distinguishing tests using the minion constraint solver. Proceedings of the 2nd Workshop on Constraints for Testing, Verification and Analysis (CSTVA), Paris, France, IEEE, 2010; 325–330.
- 2 Weimer W, Nguyen TV, Le Goues C, Forrest S. Automatically finding patches using genetic programming. ACM/IEEE International Conference on Software Engineering (ICSE), Vancouver, Canada, 2009; 364–374.
- 3 Debroy V, Wong WE. Using mutation to automatically suggest fixes for faulty programs. Third International Conference on Software Testing, Verification and Validation (ICST), Paris, France, IEEE, 2010; 65–74.
- 4 Tretmans J.Test generation with inputs, outputs and repetitive quiescence.Software - Concepts and Tools1996; 17(3): 103–120.
- 5 Peischl B, Wotawa F.Automated source-level error localization in hardware designs.IEEE Design and Test of Computers2006; 23(1): 8–19.
- 6 Mayer W, Abreu R, Stumptner M, van Gemund AJ. Prioritizing model-based debugging diagnostic reports. Proceedings of the International Workshop on Principles of Diagnosis (DX), Blue Mountains, New South Wales, Australia, 2008; 127–134.
- 7 Abreu R, Zoeteweij P, van Gemund AJ. On the accuracy of spectrum-based fault localization. Testing: Academic and Industrial Conference Practice and Research Techniques (TAIC PART), Windsor, UK, IEEE, 2007; 89–98.
- 8 Mayer W. Static and hybrid analysis in model-based debugging. PhD Thesis, School of Computer and Information Science, University of South Australia, Adelaide, Australia, 2007.
- 9 Ceballos R, Gasca RM, Del Valle C, Borrego D.Diagnosing errors in DBC programs using constraint programming.Lecture Notes in Computer Science2006; 4177: 200–210.
- 10 Nica M, Weber J, Wotawa F. How to debug sequential code by means of constraint representation. 19th International Workshop on Principles of Diagnosis (DX), Blue Mountains, New South Wales, Australia, 2008; 135–142.
- 11 Wotawa F, Nica M.On the compilation of programs into their equivalent constraint representation.Informatika2008; 32: 359–371.
- 12 Cytron R, Ferrante J, Rosen BK, Wegman MN, Zadeck FK.Efficiently computing static single assignment form and the control dependence graph.ACM Transactions on Programming Languages and Systems1991; 13(4): 451–490.
- 13 Gent IP, Jefferson C, Miguel I. Minion: a fast, scalable, constraint solver. 17th European Conference on Artificial Intelligence (ECAI), Trentino, Italy, 2006; 98–102.
- 14 Reiter R.A theory of diagnosis from first principles.Artificial Intelligence1987; 32(1): 57–95.
- 15 de Kleer J, Williams BC.Diagnosing multiple faults.Artificial Intelligence1987; 32(1): 97–130.
- 16 Ma Y-S, Offutt J, Kwon YR.Mujava: an automated class mutation system.Software Testing, Verification and Reliability2005; 15: 97–133.
- 17
Offutt AJ,
Pan J.Automatically detecting equivalent mutants and infeasible paths.Software Testing, Verification and Reliability1997; 7(3): 165–192.
10.1002/(SICI)1099-1689(199709)7:3<165::AID-STVR143>3.0.CO;2-U Google Scholar
- 18
Hierons RM,
Harman M,
Danicic S.Using program slicing to assist in the detection of equivalent mutants.Software Testing, Verification and Reliability1999; 9(4): 233–262.
10.1002/(SICI)1099-1689(199912)9:4<233::AID-STVR191>3.0.CO;2-3 Google Scholar
- 19 Schuler D, Zeller A. (Un-)covering equivalent mutants. Proceedings of the 3rd International Conference on Software Testing Verification and Validation (ICST), Paris, France, 2010; 45–54.
- 20 Offutt AJ, Lee A, Rothermel G, Untch R, Zapf C.An experimental determination of sufficient mutant operators.ACM Transactions on Software Engineering Methodology1996; 5: 99–118.
- 21 Console L, Friedrich G, Dupré DT. Model-based diagnosis meets error diagnosis in logic programs. Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI), Chambery, 1993; 1494–1499.
- 22 Shapiro E. Algorithmic Program Debugging. MIT Press: Cambridge, Massachusetts, 1983.
- 23 Bond GW, Pagurek B. A critical analysis of “Model-Based Diagnosis Meets Error Dagnosis in Logic Programs”. Technical Report SCE-94-15, Carleton University, Dept. of Systems and Computer Engineering, Ottawa, Canada, 1994.
- 24 Bond GW. Logic programs for consistency-based diagnosis. PhD Thesis, Carleton University, Faculty of Engineering, Ottawa, Canada, 1994.
- 25 Felfernig A, Friedrich G, Jannach D, Stumptner M. An integrated development environment for the design and maintenance of large configuration knowledge bases. Proceedings Artificial Intelligence in Design, Kluwer Academic Publishers: Worcester MA, 2000; 169–189.
- 26 Felfernig A, Friedrich G, Jannach D, Stumptner M. Consistency-based diagnosis of configuration knowledge bases. Proceedings of the European Conference on Artificial Intelligence (ECAI), Berlin, 2000; 146–150.
- 27 Liver B. Modeling software systems for diagnosis. Proceedings of the Fifth International Workshop on Principles of Diagnosis (DX), New Paltz, NY, 1994; 179–184.
- 28 Friedrich G, Stumptner M, Wotawa F.Model-based diagnosis of hardware designs.Artificial Intelligence1999; 111(1–2): 3–39.
- 29 Wotawa F.Debugging hardware designs using a value-based model.Applied Intelligence2002; 16(1): 71–92.
- 30 Mayer W, Stumptner M. Model-based debugging using multiple abstract models. Proceedings of the 5th International Workshop on Automated and Algorithmic Debugging (AADEBUG-03), Ghent, Belgium, 2003; 55–70.
- 31 Mayer W, Stumptner M, Wieland D, Wotawa F. Can AI help to improve debugging substantially? Debugging experiences with value-based models. Proceedings of the European Conference on Artificial Intelligence (ECAI), IOS Press: Lyon, France, 2002; 417–421.
- 32 Mayer W, Stumptner M, Wieland D, Wotawa F. Towards an integrated debugging environment. Proceedings of the European Conference on Artificial Intelligence (ECAI), IOS Press: Lyon, France, 2002; 422–426.
- 33 Wotawa F, Weber J, Nica M, Ceballos R. On the complexity of program debugging using constraints for modeling the program's syntax and semantics. Proceedings Conference of the Spanish Association for Artificial Intelligence (CAEPIA), Seville, Spain, 2009; 22–31.
- 34 Budd T, DeMillo R, Lipton R, Sayward F. Theoretical and empirical studies on using program mutation to test the functional correctness of programs. Proceedings of the Seventh ACM Symposium on Principles of Programming Languages (POPL), Las Vegas, Nevada, ACM, 1980; 220–233.
- 35 Offutt AJ, Lee SD.An empirical evaluation of weak mutation.IEEE Transactions on Software Engineering1994; 20(5): 337–344.
- 36 Jones JA, Harrold MJ. Empirical evaluation of the tarantula automatic fault-localization technique. Proceedings of the International Conference on Automated Software Engineering (ASE), Long Beach, California, ACM Press, 2005; 273–282.
- 37 Gotlieb A, Botella B, Rueher M. Automatic test data generation using constraint solving techniques. Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), Clearwater Beach, Florida, 1998; 53–62.
- 38 Collavizza H, Rueher M. Exploring different constraint-based modelings for program verification. In Principles and Practice of Constraint Programming (CP). Providence, RI, USA, 2007; 49–63.
- 39 Shirley MH, Davis R. Generating distinguishing tests based on hierarchical models and symptom information. IEEE International Conference on Computer Design: VLSI in Computers, Silver Springs, Maryland, 1983; 341–347.
- 40 McIlraith S. Generating tests using abduction. Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR), Bonn, Germany, 1994; 449–460.
- 41 Esser M, Struss P. Fault-model-based test generation for embedded software.Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, 2007; 342–347.
- 42 Zeller A, Hildebrandt R.Simplifying and isolating failure-inducing input.IEEE Transactions on Software Engineering2002; 28(2): 183–200.
- 43 Gupta N, He H, Zhang X, Gupta R. Locating faulty code using failure-inducing chops. Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE), Long Beach, California, 2005; 263–272.
- 44 Abreu R, Zoeteweij P, van Gemund AJ. Spectrum-based multiple fault localization. Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE), Auckland, New Zealand, 2009; 88–99.
- 45
Kusumoto S,
Nishimatsu A,
Nishie K,
Inoue K.Experimental evaluation of program slicing for fault localization.Empirical Software Engineering2002; 7: 49–76.
10.1023/A:1014823126938 Google Scholar
- 46 Binkley D, Harman M. A Survey of Empirical Results on Program Slicing. In Advances in Computers, Vol. 62, M Zelkowitz (ed.). Academic Press Inc.: Maryland Heights, Missouri, USA, 2004; 105–178.
- 47 Zhang X, He H, Gupta N, Gupta R. Experimental evaluation of using dynamic slices for fault localization. Sixth International Symposium on Automated & Analysis-Driven Debugging (AADEBUG), Monterey, California, 2005; 33–42.
- 48 Wotawa F. Bridging the gap between slicing and model-based diagnosis. Proceedings of the 20th International Conference on Software Engineering and Knowledge Engineering (SEKE), Redwood City, California, 2008; 836–841.
- 49 Nica M, Nica S, Wotawa F. Does testing help to reduce the number of potentially faulty statement in debugging? Testing: Academic and Industrial Conference Practice and Research Techniques (TAIC PART), Windsor, UK, 2010; 88–103.
- 50 Weiser M.Programmers use slices when debugging.Communications of the ACM1982; 25(7): 446–452.
- 51 Weiser M.Program slicing.IEEE Transactions on Software Engineering1984; 10(4): 352–357.
- 52 Korel B, Laski J.Dynamic program slicing.Information Processing Letters1988; 29: 155–163.
- 53 Korel B, Rilling J. Application of dynamic slicing in program debugging. Proceedings of the Third International Workshop on Automatic Debugging (AADEBUG), Linköping, Sweden, 1997; 43–58.
- 54 DeMillo RA, Pan H, Spafford EH. Critical slicing for software fault localization. International Symposium on Software Testing and Analysis (ISSTA), San Diego, California, 1996; 121–134.
- 55 Wotawa F.On the relationship between model-based debugging and program slicing.Artificial Intelligence2002; 135(1–2): 124–143.
