Although slices provide a good basis for analyzing programs during debugging, they lack in their capabilities providing precise information regarding the most likely root causes of faults. Hence, a lot of work is left to the programmer during fault localization. In this paper, we present an approach that combines an advanced dynamic slicing method with constraint solving in order to reduce the number of delivered fault candidates. The approach is called Constraints Based Slicing (CONBAS). The idea behind CONBAS is to convert an execution trace of a failing test case into its constraint representation and to check if it is possible to find values for all variables in the execution trace so that there is no contradiction with the test case. For doing so, we make use of the correctness and incorrectness assumptions behind a diagnosis, the given failing test case. Beside the theoretical foundations and the algorithm, we present empirical results and discuss future research. The obtained empirical results indicate an improvement of about 28% for the single fault and 50% for the double-fault case compared to dynamic slicing approaches. 1. Introduction Debugging, that is, locating a fault in a program and correcting it, is a tedious and very time-consuming task that is mainly performed manually. There have been several approaches published that aid the debugging process. However, these approaches are hardly used by programmers except for tools allowing to set breakpoints and to observe the computation of variable values during execution. There are many reasons that justify this observation. In particular, most of the debugging tools do not smoothly integrate with the software development tools. In addition, debuggers fail to identify unique root causes and still leave a lot of work for the programmer. Moreover, the approaches can also be computationally demanding, which prevents them from being used in an interactive manner. In this paper, we do not claim to solve all of the mentioned problems. We discuss a method that improves debugging results when using dependence-based approaches like dynamic slicing. Our method makes use of execution traces and the dependencies between the executed statements. In contrast to slicing, we also use symbolic execution to further reduce the number of potential root causes. In order to introduce our method, we make use of the program numfun that implements a numeric function. The program and a test case are given in Figure 1. When executing the program using the test case, numfun returns a value of 10 for variable f, which
References
[1]
B. Hofer and F. Wotawa, “Reducing the size of dynamic slicing with constraint solving,” in Proceedings of the 12th International Conference on Quality Software, 2012.
[2]
M. J. Harrold, G. Rothermel, R. Wu, and L. Yi, “An empirical investigation of program spectra,” in Proceedings of the Workshop on Program Analysis for Software Tools and Engineering, pp. 83–90, ACM, New York, NY, USA, 1998.
[3]
R. Abreu, P. Zoeteweij, R. Golsteijn, and A. J. C. van Gemund, “A practical evaluation of spectrum-based fault localization,” Journal of Systems and Software, vol. 82, no. 11, pp. 1780–1792, 2009.
[4]
P. Zoeteweij, R. Abreu, R. Golsteijn, and A. J. C. Van Gemund, “Diagnosis of embedded software using program spectra,” in Proceedings of the 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS '07), pp. 213–220, March 2007.
[5]
J. A. 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 (ASE '05), pp. 273–282, ACM Press, November 2005.
[6]
R. Abreu, P. Zoeteweij, and A. J. C. Van Gemund, “An evaluation of similarity coefficients for software fault localization,” in Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing (PRDC '06), pp. 39–46, Washington, DC, USA, December 2006.
[7]
R. Abreu and A. J. C. Van Gemund, “Diagnosing multiple intermittent failures using maximum likelihood estimation,” Artificial Intelligence, vol. 174, no. 18, pp. 1481–1497, 2010.
[8]
R. Abreu, W. Mayer, M. Stumptner, and A. J. C. Van Gemund, “Refining spectrum-based fault localization rankings,” in Proceedings of the 24th Annual ACM Symposium on Applied Computing (SAC '09), pp. 409–414, Honolulu, Hawaii, USA, March 2009.
[9]
A. Zeller and R. Hildebrandt, “Simplifying and isolating failure-inducing input,” IEEE Transactions on Software Engineering, vol. 28, no. 2, pp. 183–200, 2002.
[10]
H. Cleve and A. Zeller, “Locating causes of program failures,” in Proceedings of the 27th International Conference on Software Engineering (ICSE '05), pp. 342–351, ACM Press, New York, NY, USA, May 2005.
[11]
A. Zeller, “Isolating cause-effect chains from computer programs,” in Proceedings of the 10th ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 1–10, November 2002.
[12]
M. Weiser, “Programmers use slices when debugging,” Communications of the ACM, vol. 25, no. 7, pp. 446–452, 1982.
[13]
W. Mayer and M. Stumptner, “Model-based debugging—state of the art and future challenges,” Electronic Notes in Theoretical Computer Science, vol. 174, no. 4, pp. 61–82, 2007.
[14]
A. Arcuri, “On the automation of fixing software bugs,” in Proceedings of the 30th International Conference on Software Engineering (ICSE '08), pp. 1003–1006, New York, NY, USA, May 2008.
[15]
W. Weimer, S. Forrest, C. Le Goues, and T. Nguyen, “Automatic program repair with evolutionary computation,” Communications of the ACM, vol. 53, no. 5, pp. 109–116, 2010.
[16]
W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest, “Automatically finding patches using genetic programming,” in Proceedings of the 31st International Conference on Software Engineering (ICSE '09), pp. 364–374, May 2009.
[17]
B. Korel and J. Laski, “Dynamic program slicing,” Information Processing Letters, vol. 29, no. 3, pp. 155–163, 1988.
[18]
X. Zhang, H. He, N. Gupta, and R. Gupta, “Experimental evaluation of using dynamic slices for fault location,” in Proceedings of the 6th International Symposium on Automated and Analysis-Driven Debugging (AADEBUG '05), pp. 33–42, September 2005.
[19]
X. Zhang, S. Tallam, N. Gupta, and R. Gupta, “Towards locating execution omission errors,” ACM SIGPLAN Notices, vol. 42, no. 6, pp. 415–424, 2007.
[20]
M. Sridharan, S. J. Fink, and R. Bodik, “Thin slicing,” in Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '07 ), pp. 112–122, ACM, San Diego, Calif, USA, June 2007.
[21]
N. Gupta, H. He, X. Zhang, and R. Gupta, “Locating faulty code using failure-inducing chops,” in Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering (ASE '05), pp. 263–272, New York, NY, USA, November 2005.
[22]
X. Zhang, N. Gupta, and R. Gupta, “Pruning dynamic slices with confidence,” ACM SIGPLAN Notices, vol. 41, no. 6, pp. 169–180, 2006.
[23]
X. Zhang, N. Gupta, and R. Gupta, “A study of effectiveness of dynamic slicing in locating real faults,” Empirical Software Engineering, vol. 12, no. 2, pp. 143–160, 2007.
[24]
X. Zhang, R. Gupta, and Y. Zhang, “Efficient forward computation of dynamic slices using reduced ordered binary decision diagrams,” in Proceedings of the 26th International Conference on Software Engineering (ICSE '04), pp. 502–511, Los Alamitos, Calif, USA, May 2004.
[25]
X. Zhang, S. Tallam, and R. Gupta, “Dynamic slicing long running programs through execution fast forwarding,” in Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering (SIGSOFT '06), pp. 81–91, New York, NY, USA, November 2006.
[26]
D. Jeffrey, N. Gupta, and R. Gupta, “Fault localization using value replacement,” in Proceedings of the International Symposium on Software Testing and Analysis (ISSTA '08), pp. 167–177, ACM, New York, NY, USA, July 2008.
[27]
F. Tip, “A survey of program slicing techniques,” Journal of Programming Languages, vol. 3, no. 3, pp. 121–189, 1995.
[28]
B. Korel and J. Rilling, “Dynamic program slicing methods,” Information and Software Technology, vol. 40, no. 11-12, pp. 647–659, 1998.
[29]
R. Reiter, “A theory of diagnosis from first principles,” Artificial Intelligence, vol. 32, no. 1, pp. 57–95, 1987.
[30]
F. Wotawa, “On the relationship between model-based debugging and program slicing,” Artificial Intelligence, vol. 135, no. 1-2, pp. 125–143, 2002.
[31]
M. Nica, S. Nica, and F. Wotawa, “On the use of mutations and testing for debugging,” Software—Practice and Experience. In press.
[32]
F. Wotawa, M. Nica, and I. Moraru, “Automated debugging based on a constraint model of the program and a test case,” Journal of Logic and Algebraic Programming, vol. 81, no. 4, pp. 390–407, 2012.
[33]
W. Mayer, Static and hybrid analysis in model-based debugging [Ph.D. thesis], School of Computer and Information Science, University of South Australia, 2007.
[34]
W. Mayer, R. Abreu, M. Stumptner, and J. C. A. van Gemund, “Prioritising model-based debugging diagnostic reports (DX),” in Proceedings of the International Workshop on Principles of Diagnosis, pp. 127–134, 2008.
[35]
F. Wotawa and M. Nica, “On the compilation of programs into their equivalent constraint representation,” Informatica, vol. 32, no. 4, pp. 359–371, 2008.
[36]
B. Beizer, Software Testing Techniques, Van Nostrand Reinhold, New York, NY, USA, 2nd edition, 1990.
[37]
L. Console, D. T. Dupre, and P. Torasso, “On the relationship between abduction and deduction,” Journal of Logic and Computation, vol. 1, no. 5, pp. 661–690, 1991.
[38]
J. de Kleer, A. K. Mackworth, and R. Reiter, “Characterizing diagnoses and systems,” Artificial Intelligence, vol. 56, no. 2-3, pp. 197–222, 1992.
[39]
M. M. Brandis and H. Mossenbock, “Single-pass generation of static single-assignment form for structured languages,” ACM Transactions on Programming Languages and Systems, vol. 16, no. 6, pp. 1684–1698, 1994.
[40]
R. Dechter, Constraint Processing, Elsevier Morgan Kaufmann, 2003.
[41]
R. Greiner, B. A. Smith, and R. W. Wilkerson, “A correction to the algorithm in reiter's theory of diagnosis,” Artificial Intelligence, vol. 41, no. 1, pp. 79–88, 1989.
[42]
I. P. Gent, C. Jefferson, and I. Miguel, “Minion: a fast, scalable, constraint solver,” in Proceedings of the 17th European Conference on Artificial Intelligence (ECAI '06), pp. 98–102, Riva del Garda, Italy, August 2006.
[43]
F. Brglez and H. Fujiwara, “A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran,” in Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 663–698, June 1985.
[44]
C. Parnin and A. Orso, “Are automated debugging techniques actually helping programmers?” in Proceedings of the 20th International Symposium on Software Testing and Analysis (ISSTA '11), pp. 199–209, ACM, New York, NY, USA, 2011.
[45]
a. González-Sanchez, R. Abreu, H.-G. Hans-Gerhard Gross, and A. van Gemund, “Prioritizing tests for fault localization through ambiguity group reduction,” in Proceedings of the 26th IEEE/ACM International Conference on Automated Software Engineering (ASE '11), pp. 83–92, IEEE Computer Society, Washington, DC, USA.
