Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1133981.1134002acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
Article

Pruning dynamic slices with confidence

Published: 11 June 2006 Publication History

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/

Cited By

View all
  • (2023)Variable-based Fault Localization via Enhanced Decision TreeACM Transactions on Software Engineering and Methodology10.1145/362474133:2(1-32)Online publication date: 18-Sep-2023
  • (2023)Hypothesizer: A Hypothesis-Based Debugger to Find and Test Debugging HypothesesProceedings of the 36th Annual ACM Symposium on User Interface Software and Technology10.1145/3586183.3606781(1-14)Online publication date: 29-Oct-2023
  • (2022)Context-Aware Code Change Embedding for Better Patch Correctness AssessmentACM Transactions on Software Engineering and Methodology10.1145/350524731:3(1-29)Online publication date: 18-May-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation
June 2006
438 pages
ISBN:1595933204
DOI:10.1145/1133981
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 41, Issue 6
    Proceedings of the 2006 PLDI Conference
    June 2006
    426 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1133255
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. data and control dependences
  2. debugging
  3. dynamic slicing

Qualifiers

  • Article

Conference

PLDI06
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 16 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Variable-based Fault Localization via Enhanced Decision TreeACM Transactions on Software Engineering and Methodology10.1145/362474133:2(1-32)Online publication date: 18-Sep-2023
  • (2023)Hypothesizer: A Hypothesis-Based Debugger to Find and Test Debugging HypothesesProceedings of the 36th Annual ACM Symposium on User Interface Software and Technology10.1145/3586183.3606781(1-14)Online publication date: 29-Oct-2023
  • (2022)Context-Aware Code Change Embedding for Better Patch Correctness AssessmentACM Transactions on Software Engineering and Methodology10.1145/350524731:3(1-29)Online publication date: 18-May-2022
  • (2021)A Practical Approach for Dynamic Taint Tracking with Control-flow RelationshipsACM Transactions on Software Engineering and Methodology10.1145/348546431:2(1-43)Online publication date: 24-Dec-2021
  • (2021)Edit - Run Behavior in Programming and Debugging2021 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)10.1109/VL/HCC51201.2021.9576170(1-10)Online publication date: 10-Oct-2021
  • (2020)Using Hypotheses as a Debugging Aid2020 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)10.1109/VL/HCC50065.2020.9127273(1-9)Online publication date: Aug-2020
  • (2020)More Accurate Dynamic Slicing for Better Supporting Software Debugging2020 IEEE 13th International Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST46399.2020.00014(28-38)Online publication date: Oct-2020
  • (2019)Combining spectrum-based fault localization and statistical debuggingProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00054(502-514)Online publication date: 10-Nov-2019
  • (2018)Automated patch extraction via syntax- and semantics-aware Delta debugging on source code changesProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3236047(598-609)Online publication date: 26-Oct-2018
  • (2018)Debugging with intelligence via probabilistic inferenceProceedings of the 40th International Conference on Software Engineering10.1145/3180155.3180237(1171-1181)Online publication date: 27-May-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media