article

Open access

Cost and precision tradeoffs of dynamic data slicing algorithms

Authors:

Youtao ZhangAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 27, Issue 4

Pages 631 - 661

https://doi.org/10.1145/1075382.1075384

Published: 01 July 2005 Publication History

Abstract

Dynamic slicing algorithms are used to narrow the attention of the user or an algorithm to a relevant subset of executed program statements. Although dynamic slicing was first introduced to aid in user level debugging, increasingly applications aimed at improving software quality, reliability, security, and performance are finding opportunities to make automated use of dynamic slicing. In this paper we present the design and evaluation of three precise dynamic data slicing algorithms called the full preprocessing (FP), no preprocessing (NP) and limited preprocessing (LP) algorithms. The algorithms differ in the relative timing of constructing the dynamic data dependence graph and its traversal for computing requested dynamic data slices. Our experiments show that the LP algorithm is a fast and practical precise data slicing algorithm. In fact we show that while precise data slices can be orders of magnitude smaller than imprecise dynamic data slices, for small number of data slicing requests, the LP algorithm is faster than an imprecise dynamic data slicing algorithm proposed by Agrawal and Horgan.

References

[1]

Agrawal, H. and Horgan, J. 1990. Dynamic program slicing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 246--256.

[2]

Agrawal, H., DeMillo, R., and Spafford, E. 1993. Debugging with dynamic slicing and backtracking. Softw. Prac. Exper. 23, 6, 589--616.

[3]

Beszedes, A., Farago, C., Szabo, Z. M., Csirik, J., and Gyimothy, T. 2002. Union slices for program maintenance. In Proceedings of the International Conference on Software Maintenance. IEEE Computer Society Press, Los Alamitos, Calif., 12--21.

[4]

Beszedes, A., Gergely, T., Szabo, Z. M., Csirik, J., and Gyimothy, T. 2001. Dynamic slicing method for maintenance of large C programs. In Proceedings of the 5th European Conference on Software Maintenance and Reengineering. 105--113.

[5]

Duesterwald, E., Gupta, R., and Soffa, M. L. 1992a. Distributed slicing and partial re-execution for distributed programs. In Proceedings of the 5th Workshop on Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science, vol. 757. Springer-Verlag, New York, 497--511.

[6]

Duesterwald, E., Gupta, R., and Soffa, M. L. 1992b. Rigorous data flow testing through output influences. In Proceedings of the 2nd Irvine Software Symposium. 131--145.

[7]

Field, J., Ramalingam, G., and Tip, F. 1995. Parametric program slicing. In Proceedings of the SIGACT-SIGPLAN Symposium on Principles of Programming Languages. ACM, New York, 379--392.

[8]

Gupta, N. and Rao, P. 2001. Program execution based module cohesion measurement. In Proceedings of the 16th IEEE International Conference on Automated Software Engineering. IEEE Computer Society Press, Los Alamitos, Calif., 144--153.

[9]

Gupta, R. and Soffa, M. L. 1995. Hybrid slicing: an approach for refining static slices using dynamic information. In Proceedings of the SIGSOFT 3rd Symposium on the Foundations of Software Engineering. ACM, New York, 29--40.

[10]

Harman, M., Hierons, R. M., Danicic, S., Howroyd, J., and Fox, C. 2001. Pre/post conditioned slicing. In Proceedings of the International Conference on Software Maintenance. IEEE Computer Society Press, Los Alamitos, Calif., 138--147.

[11]

Hoffner, T. 1995. Evaluation and comparison of program slicing tools. Tech. Rep., Dept. of Computer and Information Science, Linkoping University, Sweden.

[12]

Kamkar, M. 1993. Interprocedural dynamic slicing with applications to debugging and testing. Ph.D. dissertation, Linkoping University, Sweden.

[13]

Korel, B. and Laski, J. 1988. Dynamic program slicing. Inf. Proc. Lett. 29, 3, 155--163.

[14]

Korel, B. and Rilling, J. 1997. Application of dynamic slicing in program debugging. In Proceedings of the Automated and Algorithmic Debugging. 43--59.

[15]

Korel, B. and Yalamanchili. S. 1994. Forward computation of dynamic program slices. In Proceedings of the International Symposium on Software Testing and Analysis. ACM, New York, 66--79.

[16]

Mock, M., Atkinson, D. C., Chambers, C., and Eggers, S. J. 2002. Improving program slicing with dynamic points-to data. In Proceedings of the SIGSOFT 10th Symposium on the Foundations of Software Engineering. ACM, New York, 71--80.

[17]

Nishimatsu, A., Jihira, M., Kusumoto, S., Inoue, K. 1999. Call-mark slicing: an efficient and economical way of reducing slice. In Proceedings of the 21st International Conference on Software Engineering. ACM/IEEE, New York, 422--431.

[18]

Sazeides, Y. 2003. Instruction-isomorphism in program execution. In Proceedings of the 1st Value Prediction Workshop.

[19]

Tip, F. 1995. A survey of program slicing techniques. J. Prog. Lang. 3, 3 (Sept.), 121--189.

[20]

Venkatesh, G. A. 1991. The semantic approach to program slicing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 26--28.

[21]

Venkatesh, G. A. 1995. Experimental results from dynamic slicing of C programs. ACM Trans. Prog. Lang. Syst. 17, 2, 197--216.

[22]

Weiser, M. 1979. Program slices: formal, psychological, and practical investigations of an automatic program abstraction method. Ph.D. dissertation. University of Michigan, Ann Arbor, Michigan.

[23]

Weiser, M. 1982. Program slicing. IEEE Trans. Softw. Eng. SE-10, 4, 352--357.

[24]

Zhang, X. and Gupta, R. 2004. Cost effective dynamic program slicing. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 94--106.

[25]

Zhang, X., Gupta, R., and Zhang, Y. 2004. Effective forward computation of dynamic slices using reduced ordered binary decision diagrams. In Proceedings of the International Conference on Software Engineering. ACM, New York, 502--511.

[26]

Zilles, C. B. and Sohi, G. 2000. Understanding the backward slices of performance degrading instructions. In Proceedings of the 27th International Symposium on Computer Architecture. ACM/IEEE, New York, 172--181.

[27]

The Trimaran Compiler Research Infrastructure. 1997. Tutorial Notes. http://www.trimaran.org.

Cited By

Stoica BSahoo SLarus JAdve VMussbacher GAtlee JBultan T(2019)WokProceedings of the 41st International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion.2019.00136(324-325)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE-Companion.2019.00136
Hwang SLee SKim YRyu SBao FMiller SZhou JAhn G(2015)Bittersweet ADBProceedings of the 10th ACM Symposium on Information, Computer and Communications Security10.1145/2714576.2714638(579-584)Online publication date: 14-Apr-2015
https://dl.acm.org/doi/10.1145/2714576.2714638
Zhu ELiu FFang XLi XYang YLiang A(2014)DYBS: A Lightweight Dynamic Slicing Framework for Diagnosing Attacks on x86 Binary ProgramsJournal of Software10.4304/jsw.9.3.560-5689:3Online publication date: 1-Mar-2014
https://doi.org/10.4304/jsw.9.3.560-568
Show More Cited By

Index Terms

Cost and precision tradeoffs of dynamic data slicing algorithms
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
      2. Software defect analysis
        Software testing and debugging

Recommendations

Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging

Understanding data dependences in programs is important for many software-engineering activities, such as program understanding, impact analysis, reverse engineering, and debugging. The presence of pointers can cause subtle and complex data dependences ...
A brief survey of program slicing

Program slicing is a technique to extract program parts with respect to some special computation. Since Weiser first proposed the notion of slicing in 1979, hundreds of papers have been presented in this area. Tens of variants of slicing have been ...
An efficient interprocedural dynamic slicing method

We present an efficient interprocedural dynamic slicing algorithm for structured programs. We first propose an intraprocedural dynamic slicing algorithm, and subsequently extend it to handle interprocedural calls. Our intraprocedural dynamic slicing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 27, Issue 4

July 2005

236 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1075382

Issue’s Table of Contents

Copyright © 2005 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2005

Published in TOPLAS Volume 27, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
713
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)13

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stoica BSahoo SLarus JAdve VMussbacher GAtlee JBultan T(2019)WokProceedings of the 41st International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion.2019.00136(324-325)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE-Companion.2019.00136
Hwang SLee SKim YRyu SBao FMiller SZhou JAhn G(2015)Bittersweet ADBProceedings of the 10th ACM Symposium on Information, Computer and Communications Security10.1145/2714576.2714638(579-584)Online publication date: 14-Apr-2015
https://dl.acm.org/doi/10.1145/2714576.2714638
Zhu ELiu FFang XLi XYang YLiang A(2014)DYBS: A Lightweight Dynamic Slicing Framework for Diagnosing Attacks on x86 Binary ProgramsJournal of Software10.4304/jsw.9.3.560-5689:3Online publication date: 1-Mar-2014
https://doi.org/10.4304/jsw.9.3.560-568
Jiang SSantelices RGrechanik MCai H(2014)On the Accuracy of Forward Dynamic Slicing and Its Effects on Software MaintenanceProceedings of the 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation10.1109/SCAM.2014.23(145-154)Online publication date: 28-Sep-2014
https://dl.acm.org/doi/10.1109/SCAM.2014.23
Liu CYang JTan LHafiz M(2013)R2FixProceedings of the 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation10.1109/ICST.2013.24(282-291)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1109/ICST.2013.24
Holewinski JRamamurthi RRavishankar MFauzia NPouchet LRountev ASadayappan P(2012)Dynamic trace-based analysis of vectorization potential of applicationsACM SIGPLAN Notices10.1145/2345156.225410847:6(371-382)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254108
Holewinski JRamamurthi RRavishankar MFauzia NPouchet LRountev ASadayappan PVitek JLin HTip F(2012)Dynamic trace-based analysis of vectorization potential of applicationsProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254108(371-382)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254108
Yu KLin MChen JZhang X(2012)Towards automated debugging in software evolutionJournal of Systems and Software10.1016/j.jss.2011.10.01685:10(2305-2317)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.jss.2011.10.016
El-Zawawy M(2012)Heap slicing using type systemsProceedings of the 12th international conference on Computational Science and Its Applications - Volume Part III10.1007/978-3-642-31137-6_45(592-606)Online publication date: 18-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-31137-6_45
Yu RZhao LWang LYin X(2011)Statistical Fault Localization via Semi-dynamic Program SlicingProceedings of the 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications10.1109/TrustCom.2011.89(695-700)Online publication date: 16-Nov-2011
https://dl.acm.org/doi/10.1109/TrustCom.2011.89
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents