article

Open access

A new foundation for control dependence and slicing for modern program structures

Authors:

Venkatesh Prasad Ranganath,

Anindya Banerjee,

Matthew B. DwyerAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 29, Issue 5

Pages 27 - es

https://doi.org/10.1145/1275497.1275502

Published: 02 August 2007 Publication History

Abstract

The notion of control dependence underlies many program analysis and transformation techniques. Despite being widely used, existing definitions and approaches to calculating control dependence are difficult to apply directly to modern program structures because these make substantial use of exception processing and increasingly support reactive systems designed to run indefinitely.

This article revisits foundational issues surrounding control dependence, and develops definitions and algorithms for computing several variations of control dependence that can be directly applied to modern program structures. To provide a foundation for slicing reactive systems, the article proposes a notion of slicing correctness based on weak bisimulation, and proves that some of these new definitions of control dependence generate slices that conform to this notion of correctness. This new framework of control dependence definitions, with corresponding correctness results, is even able to support programs with irreducible control flow graphs. Finally, a variety of properties show that the new definitions conservatively extend classic definitions. These new definitions and algorithms form the basis of the Indus Java slicer, a publicly available program slicer that has been implemented for full Java.

References

[1]

Allen, M. and Horwitz, S. 2003. Slicing Java programs that throw and catch exceptions. In Procedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM). ACM, 44--54.

Digital Library

[2]

Andersen, L. O. 1994. Program analysis and specialization for the C programming languages. Ph.D. thesis, DIKU, University of Copenhagen, DIKU, Universitetsparken 1, DK-2100, Copenhagen ∅, Denmark.

[3]

Ball, T. and Horwitz, S. 1993. Slicing programs with arbitrary control-flow. In Proceedings of the 1st International Workshop on Automated and Algorithmic Debugging (AADEBUG). Lecture Notes in Computer Science, vol. 749. Springer, 206--222.

Digital Library

[4]

Bilardi, G. and Pingali, K. 1996. A framework for generalized control dependences. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (Pennsylvania, PA). ACM Press, New York, 291--300.

Digital Library

[5]

Clarke, E. M., Grumberg, O., and Peled, D. A. 1999. Model Checking. MIT Press, Cambridge, MA.

Digital Library

[6]

Corbett, J. C., Dwyer, M. B., Hatcliff, J., Laubach, S., Păsăreanu, C. S., Robby, and Zheng, H. 2000. Bandera: Extracting finite-state models from Java source code. In Proceedings of the 22nd International Conference on Software Engineering (ICSE). 439--448.

Digital Library

[7]

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

Digital Library

[8]

Francel, M. A. and Rugaber, S. 1999. The relationship of slicing and debugging to program understanding. In Proceedings of the 7th IEEE International Workshop on Program Comprehension (IWPC). 106--113.

Digital Library

[9]

Hatcliff, J., Dwyer, M. B., and Zheng, H. 2000. Slicing software for model construction. J. Higher-Order Symb. Comput. 13, 4, 315--353. A special issue containing selected papers from the 1999 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation.

Digital Library

[10]

Hatcliff, J., Corbett, J. C., Dwyer, M. B., Sokolowski, S., and Zheng, H. 1999. A formal study of slicing for multi-threaded programs with JVM concurrency primitives. In Proceedings on the International Symposium on Static Analysis (SAS). Lecture Notes in Computer Science, vol. 1694. Springer, 1--18.

Digital Library

[11]

Hecht, M. S. and Ullman, J. D. 1974. Characterizations of reducible flow graphs. J. ACM 21, 3, 367--375.

Digital Library

[12]

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

Digital Library

[13]

Horwitz, S., Pfeiffer, P., and Reps, T. W. 1989. Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, 28--40.

Digital Library

[14]

I. Millett, L. and Teitelbaum, T. 1998. Slicing Promela and its applications to model checking, simulation, and protocol understanding. In Proceedings of the 4th International SPIN Workshop.

[15]

Jayaraman, G., Ranganath, V. P., and Hatcliff, J. 2004. Kaveri: Delivering Indus Java program slicer to Eclipse. http://projects.cis.ksu.edu/docman/?group_id=12.

[16]

Johnson, R. and Pingali, K. 1993. Dependence-Based program analysis. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 78--89.

Digital Library

[17]

Krinke, J. 1998. Static slicing of threaded programs. In Proceedings of the ACM SIGPLAN/SIGFSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE). 35--42.

Digital Library

[18]

Milner, R. 1989. Communication and Concurrency. Prentice-Hall. ISBN: 0-13-115007-3.

Digital Library

[19]

Muchnick, S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, San Francisco, CA.

Digital Library

[20]

Podgurski, A. and Clarke, L. 1990. A formal model of program dependences and its implications for software testing, debugging, and maintenance. IEEE Trans. Softw. Eng. 16, 9, 965--979.

Digital Library

[21]

Ranganath, V. P., Amtoft, T., Banerjee, A., B. Dwyer, M., and Hatcliff, J. 2005. A new foundation for control-dependence and slicing for modern program structures. In Proceedings of the European Symposium on Programming Languages and Systems (ESOP). Lecture Notes in Computer Science, vol. 3444. Springer, 77--93. Extended version available at http://projects.cis. ksu.edu/docman/?group_id=12.

Digital Library

[22]

SAnToS Laboratory. 2007 Indus, a toolkit to customize and adapt Java programs. http://indus. projects.cis.ksu.edu.

[23]

Stafford, J. 2000. A formal, language-independent, and compositional approach to interprocedural control dependence analysis. Ph.D. thesis, University of Colorado.

Digital Library

[24]

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

[25]

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

Digital Library

Cited By

Kim YChoi Y(2024)PBE-Based Selective Abstraction and Refinement for Efficient Property Falsification of Embedded SoftwareProceedings of the ACM on Software Engineering10.1145/36437401:FSE(293-315)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643740
Wang YZhang PSun MLu ZYang YTang YQian JLi ZZhou Y(2023)Uncovering Bugs in Code Coverage Profilers via Control Flow Constraint SolvingIEEE Transactions on Software Engineering10.1109/TSE.2023.332138149:11(4964-4987)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3321381
Masud A(2023)The Duality in Computing SSA Programs and Control DependencyIEEE Transactions on Software Engineering10.1109/TSE.2022.319224949:4(1766-1781)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TSE.2022.3192249
Show More Cited By

Index Terms

A new foundation for control dependence and slicing for modern program structures
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
      1. Semantics
    2. General programming languages
      1. Language features
        Control structures
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics

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 for modern program structures: a theory for eliminating irrelevant loops

Slicing is a program transformation technique with numerous applications, as it allows the user to focus on the parts of a program that are relevant for a given purpose. Ideally, the slice program should have the same termination properties as the ...
Abstract Program Slicing: An Abstract Interpretation-Based Approach to Program Slicing

In the present article, we formally define the notion of abstract program slicing, a general form of program slicing where properties of data are considered instead of their exact value. This approach is applied to a language with numeric and reference ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 29, Issue 5

Special Issue ESOP'05

August 2007

213 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1275497

Issue’s Table of Contents

Copyright © 2007 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: 02 August 2007

Published in TOPLAS Volume 29, Issue 5

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

81
Total Citations
View Citations
1,063
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)10

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim YChoi Y(2024)PBE-Based Selective Abstraction and Refinement for Efficient Property Falsification of Embedded SoftwareProceedings of the ACM on Software Engineering10.1145/36437401:FSE(293-315)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643740
Wang YZhang PSun MLu ZYang YTang YQian JLi ZZhou Y(2023)Uncovering Bugs in Code Coverage Profilers via Control Flow Constraint SolvingIEEE Transactions on Software Engineering10.1109/TSE.2023.332138149:11(4964-4987)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3321381
Masud A(2023)The Duality in Computing SSA Programs and Control DependencyIEEE Transactions on Software Engineering10.1109/TSE.2022.319224949:4(1766-1781)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TSE.2022.3192249
Cai HZhang ZJian YLi DHuang Z(2023)BDGSE: A Symbolic Execution Technique for High MC/DC2023 IEEE 23rd International Conference on Software Quality, Reliability, and Security (QRS)10.1109/QRS60937.2023.00039(313-324)Online publication date: 22-Oct-2023
https://doi.org/10.1109/QRS60937.2023.00039
Léchenet JKosmatov NLe Gall P(2023)Efficient computation of arbitrary control dependenciesTheoretical Computer Science10.1016/j.tcs.2023.114029969(114029)Online publication date: Aug-2023
https://doi.org/10.1016/j.tcs.2023.114029
Galindo CPérez SSilva J(2023)Exception-sensitive program slicingJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2022.100832130(100832)Online publication date: Jan-2023
https://doi.org/10.1016/j.jlamp.2022.100832
Masud ALisper BEgger BSmith A(2022)On the computation of interprocedural weak control closureProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction10.1145/3497776.3517782(65-76)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3497776.3517782
Masud A(2022)Fast and Incremental Computation of Weak Control ClosureStatic Analysis10.1007/978-3-031-22308-2_15(325-349)Online publication date: 2-Dec-2022
https://doi.org/10.1007/978-3-031-22308-2_15
Hecker MBischof SSnelting G(2021)On Time-sensitive Control DependenciesACM Transactions on Programming Languages and Systems10.1145/348600344:1(1-37)Online publication date: 9-Dec-2021
https://dl.acm.org/doi/10.1145/3486003
Masud ALisper B(2021)Semantic Correctness of Dependence-based Slicing for Interprocedural, Possibly Nonterminating ProgramsACM Transactions on Programming Languages and Systems10.1145/343448942:4(1-56)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434489
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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