research-article

Open access

Dynamic slicing on Java bytecode traces

Authors:

Abhik RoychoudhuryAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 30, Issue 2

Article No.: 10, Pages 1 - 49

https://doi.org/10.1145/1330017.1330021

Published: 14 March 2008 Publication History

Abstract

Dynamic slicing is a well-known technique for program analysis, debugging and understanding. Given a program P and input I, it finds all program statements which directly/indirectly affect the values of some variables' occurrences when P is executed with I. In this article, we develop a dynamic slicing method for Java programs. Our technique proceeds by backwards traversal of the bytecode trace produced by an input I in a given program P. Since such traces can be huge, we use results from data compression to compactly represent bytecode traces. The major space savings in our method come from the optimized representation of (a) data addresses used as operands by memory reference bytecodes, and (b) instruction addresses used as operands by control transfer bytecodes. We show how dynamic slicing algorithms can directly traverse our compact bytecode traces without resorting to costly decompression. We also extend our dynamic slicing algorithm to perform “relevant slicing”. The resultant slices can be used to explain omission errors that is, why some events did not happen during program execution. Detailed experimental results on space/time overheads of tracing and slicing are reported in the article. The slices computed at the bytecode level are translated back by our tool to the source code level with the help of information available in Java class files. Our JSlice dynamic slicing tool has been integrated with the Eclipse platform and is available for usage in research and development.

References

[1]

Agrawal, H. 1991. Towards automatic debugging of computer programs. Ph.D. dissertation, Purdue University.

Digital Library

[2]

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

Digital Library

[3]

Agrawal, H., Horgan, J., Krauser, E., and London, S. 1993. Incremental regression testing. In Proceedings of the International Conference on Software Maintenance (ICSM) (Washington, DC). IEEE Computer Society Press, Los Alamitos, CA, 348--357.

Digital Library

[4]

Akgul, T., Mooney, V., and Pande, S. 2004. A fast assembly level reverse execution method via dynamic slicing. In Proceedings of the International Conference on Software Engineering (ICSE) (Edinburgh, Scotland). IEEE Computer Society Press, Los Alamitos, CA, 522--531.

Digital Library

[5]

Andersen, L. O. 1994. Program analysis and specialization for the C progranzming language. Ph.D. dissertation, University of Copenhagen.

[6]

Berk, E. J. and Ananian, C. S. 2003. A lexical analyzer generator for Java. website: http://www.cs.princeton.edu/~appel/modern/java/JLex/.

[7]

Dhamdhere, D., Gururaja, K., and Ganu, P. 2003. A compact execution history for dynamic slicing. Inf. Proc. Lett. 85, 145--152.

Digital Library

[8]

Ferrante, J., Ottenstein, K., and Warren, J. 1987. The program dependence graph and its use in optimization. ACM Trans. Prog. Lang. Syst. 9, 3, 319--349.

Digital Library

[9]

Goel, A., Roychoudhury, A., and Mitra, T. 2003. Compactly representing parallel program executions. In Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming (PPoPP). San Diego, CA, USA, 191--202.

Digital Library

[10]

Gyimóthy, T., Beszédes, A., and Forgács, I. 1999. An efficient relevant slicing method for debugging. In Proceedings of the 7th ACM SIGSOFT International Symposium on Foundations of Software Engineering (Toulouse, France). ACM, New York, 303--321.

Digital Library

[11]

Horwitz, S., Reps, T., and Binkley, D. 1990. Interprocedural slicing using dependence graphs. ACM Trans. Prog. Lang. Syst. (TOPLAS) 12, 1, 26--60.

Digital Library

[12]

JGF. The Java Grande Forum Benchmark Suite. website: http://www.epcc.ed.ac.uk/javagrande/seq/contents.html.

[13]

Joy, B., Steele, G., Gosling, J., and Bracha, G. 2000. Java(TM) Language Specification (2nd Edition). Prentice Hall, Englewood Cliffs, NJ.

[14]

Kaffe. The Kaffe virtual machine. website: http://www.kaffe.org.

[15]

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

Digital Library

[16]

Korel, B. and Rilling, J. 1997. Application of dynamic slicing in program debugging. In Proceedings of the International Workshop on Automatic Debugging (Linkoping, Sweden). Springer-Verlag, New York.

[17]

Lamport, L. 1997. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 558--565.

Digital Library

[18]

Larsen, L. and Harrold, M. 1996. Slicing object-oriented software. In Proceedings of the ACM/IEEE International Conference on Software Engineering (ICSE) (Berlin, Germany). IEEE Computer Society Press, Los Alamitos, CA, 495--505.

Digital Library

[19]

Larus, J. 1990. Abstract execution: A technique for efficiently tracing programs. Software - Practice and Experience (SPE) 20, 1241--1258.

Digital Library

[20]

Larus, J. R. 1999. Whole program paths. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, Atlanta, Georgia, USA, 259--269.

Digital Library

[21]

Levrouw, L. J., Audenaert, K. M. R., and Campenhout, J. M. 1994. A new trace and replay system for shared memory programs based on lamport clocks. In Proceedings of the 2nd Euromicro Workshop on Parallel and Distributed Processing. IEEE Computer Society, ELIS, Universiteit Gent, Belgium, 471--478.

[22]

Lhoták, O. 2002. Spark: A flexible points-to analysis framework for Java. M.S. dissertation, McGill University.

[23]

Lindholm, T. and Yellin, F. 1999. The Java(TM) Virtual Machine Specification (2nd Edition). Prentice Hall, Englewood Cliffs, NJ.

Digital Library

[24]

Lucia, A. D. 2001. Program slicing: Methods and applications. In Proceedings of the IEEE International Workshop on Source Code Analysis and Manipulation (Florence, Italy). IEEE Computer Society Press, Los Alamitos, CA, 142--149.

[25]

Majumdar, R. and Jhala, R. 2005. Path slicing. In Proceedings of the International Conference on Programming Language Design and Implementation (PLDI) (Chicago, IL). ACM, New York.

Digital Library

[26]

Nevill-Manning, C. G. and Witten, I. H. 1997. Linear-time, incremental hierarchy inference for compression. In Proceedings of the Data Commpression Conference (DCC) (Snowbird, Utah). IEEE Computer Society Press, Los Alamitos, CA, 3--11.

Digital Library

[27]

Ohata, F., Hirose, K., Fujii, M., and Inoue, K. 2001. A slicing method for object-oriented programs using lightweight dynamic information. In Proceedings of the Asia-Pacific Software Engineering Conference (Macau, China). IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[28]

Pleszkun, A. R. 1994. Techniques for compressing programm address traces. In Proceedings of the IEEE/ACM International Symposium on Microarchitecture (MICRO) (San Jose, CA). ACM, New York, 32--39.

Digital Library

[29]

Reiss, S. P. and Renieris, M. 2001. Encoding program executions. In Proceedings of the ACM/IEEE International Conference on Software Engineering (ICSE) (Toronto, Ont., Canada). IEEE Computer Society Press, Los Alamitos, CA, 221--230.

Digital Library

[30]

Ronsse, M. and Bosschere, K. D. 1999. Recplay: A fully integrated practical record/replay system. ACM Trans. Comput. Syst. (TOCS) 17, 133--152.

Digital Library

[31]

Sazeides, Y. 2003. Instruction isomorphism in program execution. J. Instruction-Level Paral. 5.

[32]

Sinha, S. and Harrold, M. J. 2000. Analysis and testing of programs with exceptionhandling constructs. IEEE Trans. Softw. Eng. 26, 9, 849--871.

Digital Library

[33]

SPECjvm98. 1998. Spec JVM98 benchmarks. website: http://www.specbench.org/osg/jvm98/.

[34]

Steensgaard, B. 1996. Points-to analysis in almost linear time. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (St. Petersburg Beach, FL). ACM, New York, 32--41.

Digital Library

[35]

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

[36]

Vallée-Rai, R., Co, P., Gagnon, E., Hendren, L., Lam, P., and Sundaresan, V. 1999. Soot - A Java bytecode optimization framework. In Proceedings of the Conference of the Centre for Advanced Studies on Collaborative Research (CASCON) (Mississauga, Ontario, Canada). IBM Press. 13.

Digital Library

[37]

Wang, T. and Roychoudhury, A. 2007. Dynamic slicing on Java bytecode traces. Tech. Rep. TRB3/07, National University of Singapore. March. http://www.comp.nus.edu.sg/~abhik/pdf/JSlice-TR.pdf.

[38]

Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Engineering 10, 4, 352--357.

Digital Library

[39]

Xu, B., Chen, Z., and Yang, H. 2002. Dynamic slicing object-oriented programs for debugging. In Proceedings of the IEEE International Workshop on Source Code Analysis and Manipulation (Montreal, Canada). IEEE Computer Society Press, Los Alamitos, CA.

Digital Library

[40]

Zhang, Y. and Gupta, R. 2001. Timestamped whole program path representation and its applications. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (Snowbird, UT). ACM, New York, 180--190.

Digital Library

[41]

Zhang, X. and Gupta, R. 2004. Whole execution traces. In Proceedings of the IEEE/ACM International Symposium on Microarchitecture (MICRO) (Portland, OR). IEEE Computer Society Press, Los Alamitos, CA, 105--116.

Digital Library

[42]

Zhang, X., Gupta, R., and Zhang, Y. 2005. Cost and precision tradeoffs of dynamic data slicing algorithms. ACM Trans. Prog. Lang. Syst. (TOPLAS) 27, 631--661.

Digital Library

[43]

Zhao, J. 2000. Dependence analysis of Java bytecode. In IEEE Annual International Computer Software and Applications Conference (Taipei, Taiwan). IEEE Computer Society Press, Los Alamitos, CA, 486--491.

Digital Library

[44]

Zilles, C. B. and Sohi, G. 2000. Understanding the backward slices of performance degrading instructions. In Proceedings of the International Symposium on Computer Architecture (ISCA) (Vancouver, BC, Canada). IEEE Computer Society Press, Los Alamitos, CA, 172--181.

Digital Library

Cited By

Win HTan SSui Y(2023)Event-aware precise dynamic slicing for automatic debugging of Android applicationsJournal of Systems and Software10.1016/j.jss.2023.111606198(111606)Online publication date: Apr-2023
https://doi.org/10.1016/j.jss.2023.111606
Shankar SMacke SChasins SHead AParameswaran A(2022)Bolt-on, Compact, and Rapid Program Slicing for NotebooksProceedings of the VLDB Endowment10.14778/3565838.356585515:13(4038-4047)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3565838.3565855
Zhang MMathur UViswanathan MSpinellis DGousios GChechik MDi Penta M(2021)Checking LTL[F,G,X] on compressed traces in polynomial timeProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468557(131-143)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468557
Show More Cited By

Index Terms

Dynamic slicing on Java bytecode traces
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

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 ...
Slicing concurrent Java programs using Indus and Kaveri

Program slicing is a program analysis and transformation technique that has been successfully used in a wide range of applications including program comprehension, debugging, maintenance, testing, and verification. However, there are only few fully ...
A tracing technique using dynamic bytecode instrumentation of Java applications and libraries at basic block level
ICOOOLPS '11: Proceedings of the 6th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems

Implementing a profiler to trace a program execution is non-trivial. One way to do this on running Java programs is through bytecode instrumentation. Nowadays, tools exist that ease the instrumentation process itself, but as far as we know, none offers ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 30, Issue 2

March 2008

217 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1330017

Issue’s Table of Contents

Copyright © 2008 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 March 2008

Accepted: 01 February 2007

Revised: 01 October 2005

Received: 01 March 2005

Published in TOPLAS Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
1,139
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)16

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Win HTan SSui Y(2023)Event-aware precise dynamic slicing for automatic debugging of Android applicationsJournal of Systems and Software10.1016/j.jss.2023.111606198(111606)Online publication date: Apr-2023
https://doi.org/10.1016/j.jss.2023.111606
Shankar SMacke SChasins SHead AParameswaran A(2022)Bolt-on, Compact, and Rapid Program Slicing for NotebooksProceedings of the VLDB Endowment10.14778/3565838.356585515:13(4038-4047)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3565838.3565855
Zhang MMathur UViswanathan MSpinellis DGousios GChechik MDi Penta M(2021)Checking LTL[F,G,X] on compressed traces in polynomial timeProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468557(131-143)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468557
Pauck FWehrheim H(2021)Jicer: Simplifying Cooperative Android App Analysis Tasks2021 IEEE 21st International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM52516.2021.00031(187-197)Online publication date: Sep-2021
https://doi.org/10.1109/SCAM52516.2021.00031
Li XOrso A(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
https://doi.org/10.1109/ICST46399.2020.00014
Xu XZou CXue J(2020)Every Mutation Should Be Rewarded: Boosting Fault Localization with Mutated Predicates2020 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME46990.2020.00028(196-207)Online publication date: Sep-2020
https://doi.org/10.1109/ICSME46990.2020.00028
Reis SAbreu RD'Amorim M(2019)Demystifying the combination of dynamic slicing and spectrum-based fault localizationProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367705(4760-4766)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367705
Ayhan SCostas PSamet H(2019)A Data-driven Framework for Long-Range Aircraft Conflict Detection and ResolutionACM Transactions on Spatial Algorithms and Systems10.1145/33288325:4(1-23)Online publication date: 12-Sep-2019
https://dl.acm.org/doi/10.1145/3328832
Kannangara STanin EHarwood AKarunasekera S(2019)Stepping Stone GraphACM Transactions on Spatial Algorithms and Systems10.1145/33248835:4(1-24)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3324883
Aly HKrumm JRanade GHorvitz E(2019)To Buy or Not to BuyACM Transactions on Spatial Algorithms and Systems10.1145/33204315:4(1-25)Online publication date: 12-Sep-2019
https://dl.acm.org/doi/10.1145/3320431
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

Figures

Tables

Media

View Issue’s Table of Contents