Pruning dynamic slices with confidence

Abstract

Given an incorrect value produced during a failed program run (e.g., a wrong output value or a value that causes the program to crash), the backward dynamic slice of the value very frequently captures the faulty code responsible for producing the incorrect value. Although the dynamic slice often contains only a small percentage of the statements executed during the failed program run, the dynamic slice can still be large and thus considerable effort may be required by the programmer to locate the faulty code.In this paper we develop a strategy for pruning the dynamic slice to identify a subset of statements in the dynamic slice that are likely responsible for producing the incorrect value. We observe that some of the statements used in computing the incorrect value may also have been involved in computing correct values (e.g., a value produced by a statement in the dynamic slice of the incorrect value may also have been used in computing a correct output value prior to the incorrect value). For each such executed statement in the dynamic slice, using the value profiles of the executed statements, we compute a confidence value ranging from 0 to 1 - a higher confidence value corresponds to greater likelihood that the execution of the statement produced a correct value. Given a failed run involving execution of a single error, we demonstrate that the pruning of a dynamic slice by excluding only the statements with the confidence value of 1 is highly effective in reducing the size of the dynamic slice while retaining the faulty code in the slice. Our experiments show that the number of distinct statements in a pruned dynamic slice are 1.79 to 190.57 times less than the full dynamic slice. Confidence values also prioritize the statements in the dynamic slice according to the likelihood of them being faulty. We show that examining the statements in the order of increasing confidence values is an effective strategy for reducing the effort of fault location.

References

1. Agrawal, H. and Horgan, J., "Dynamic Program Slicing," SIGPLAN Conference on Programming Language Design and Implementation, pages 246--256, 1990.
2. Blume, W. and Eigenmann, R., "Symbolic Range Propagation," International Symposium on Parallel Processing, 1995.
3. Chen, T.Y. and Cheung, Y.Y., "Dynamic Program Dicing," International Conference on Software Maintenance, pages 378--385, 1993.
4. Cleve, H. and Zeller, A., "Locating Causes of Program Failures," International Conf. on Software Engineering, pages 342--351, 2005.
5. Gupta, N., He, H., Zhang, X., and Gupta, R., "Locating Faulty Code Using Failure-Inducing Chops," IEEE/ACM International Conference on Automated Software Engineering, pages 263--272, Nov. 2005.
6. Gyimothy, T., Beszedes, A., and Forgacs, I., "An Efficient Relevant Slicing Method for Debugging," European Software Engineering Conference/ ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 303--321, 1999.
7. Hangal, S. and Lam, M.S., "Tracking Down Software Bugs Using Automatic Anomaly Detection," International Conference on Software Engineering, pages 291--301, May 2002.
8. Harrold, M.J., Rothermel, G., Sayre, K., Wu, R., and Yi, L., "An Empirical Investigation of the Relationship Between Spectra Differences and Regression Faults," Journal of Software Testing Verification and Reliability, 10(3):171--194, 2000.
9. He, H. and Gupta, N., "Automated Debugging using Path-Based Weakest Preconditions," Fundamental Approaches to Software Engineering, Springer, LNCS 2984, pages 267--280, 2004.
10. Hildebrandt, R. and Zeller, A., "Simplifying Failure-inducing Input," International Symposium on Software Testing and Analysis, 2000.
11. Hutchins, M., Foster, H., Goradia, T., and Ostrand, T., "Experiments on the Effectiveness of Dataflow- and Controlflow-based Test Adequacy Criteria," International Conference on Software Engineering, pages 191--200, 1994.
12. Jones, J.A., "Fault Localization Using Visualization of Test Information," International Conf. on Software Engineering, 2004.
13. Korel, B. and Laski, J., "Dynamic Program Slicing," Information Processing Letters, 29(3):155--163, 1988.
14. Liblit, B., Aiken, A., Zheng, A.X., and Jordan, M.I., "Bug Isolation via Remote Program Sampling," SIGPLAN Conference on Programming Language Design and Implementation, pages 141--154, 2003.
15. Narayanasamy, S., Pokam, G., Calder, B., "BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging," International Symp. on Computer Architecture, pages 284--295, 2005.
16. Pytlik, B., Renieris, M., Krishnamurthi, S., and Reiss, S., "Automated Fault Localization Using Potential Invariants," Fifth International Workshop on Automated and Algorithmic Debugging, Sept. 2003.
17. Renieris, M. and Reiss, S., "Fault Localization with Nearest Neighbor Queries," IEEE International Conference on Automated Software Engineering, pages 30--39, 2003.
18. Weiser, M., "Program Slicing," IEEE Transactions on Software Engineering, Vol. SE-10, No. 4, pages 352--357, 1982.
19. Xie, Y. and Engler, D., "Using Redundancies to Find Errors," ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 51--60, 2002.
20. Zeller, A., "Isolating Cause-effect Chains from Computer Programs," SIGSOFT Symposium on Foundations of Software Engineering, 2002.
21. Zeller, A., "Yesterday, my program worked. Today, it does not. Why?," European Software Engineering Conference/ ACM SIGSOFT Symp. on Foundations of Software Engineering, pages 253--267, 1999.
22. Zeller, A. and Hildebrandt, R., "Simplifying and Isolating Failure inducing Input," IEEE Transactions on Software Engineering, Vol. 28, No. 2, pages 183--200, Feb. 2002.
23. Zhang, X., Gupta, R., and Zhang, Y., "Precise Dynamic Slicing Algorithms," International Conference on Software Engineering, pages 319--329, May 2003.
24. Zhang, X., Gupta, R., and Zhang, Y., "Effective Forward Computation of Dynamic Slices Using Reduced Ordered Binary Decision Diagrams," International Conf. on Software Engineering, pages 502--511, May 2004.
25. Zhang, X. and Gupta, R., "Cost Effective Dynamic Program Slicing," SIGPLAN Conference on Programming Language Design and Implementation, pages 94--106, June 2004.
26. Zhang, X. and Gupta, R., "Whole Execution Traces," IEEE/ACM 37th International Symposium on Microarchitecture, 2004.
27. Zhang, X., He, H., Gupta, N., and Gupta, R., "Experimental Evaluation of Using Dynamic Slices for Fault Location," International Symposium on Automated and Analysis-Driven Debugging, 2005.
28. Zhang, X., Gupta, N., and Gupta, R., "Locating Faults Through Automated Predicate Switching," International Conference on Software Engineering, 2006.
29. Zhou, P., Liu, W., Long, F., Lu, S., Qin, F., Zhou, Y., Midkiff, S., and Torrelas, J., "Accmon: Automatically Detecting Memoryrelated Bugs via Program Counter-based Invariants," International Symposium on Microarchitecture, pages 269--280, 2004.
30. Zhou, P., Qin, F., Liu, W., Zhou, Y., and Torrelas, J., "Iwatcher: Efficient Architecture Support for Software Debugging," International Symp. on Computer Architecture, pages 224--237, 2004.
31. http://www.cse.unl.edu/~galileo/sir
32. http://www.elis.ugent.be/diablo/
33. http://valgrind.org/

Index Terms

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Process validation

        • Traceability

      • Software defect analysis

        • Software testing and debugging