More Web Proxy on the site http://driver.im/

research-article

Data dependencies and program slicing: from syntax to abstract semantics

Authors:

Isabella Mastroeni,

Damiano ZanardiniAuthors Info & Claims

PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

Pages 125 - 134

https://doi.org/10.1145/1328408.1328428

Published: 07 January 2008 Publication History

Abstract

We discuss the relation between program slicing and data dependencies. We claim that slicing can be defined, and therefore calculated, parametrically on the chosen notion of dependency, which implies a different result when building the program dependency graph. In this framework, it is possible to choose dependency in the syntactic or semantic sense, thus leading to compute possibly different, smaller slices. Moreover, the notion of abstract dependency, based on properties instead of exact data values, is investigated in its theoretical meaning. Constructive ideas are given to compute abstract dependencies on expressions, and to transform properties in order to rule out some dependencies. The application of these ideas to information flow is also discussed.

References

[1]

M. Abadi, A. Banerjee, N. Heintze, and J. Riecke. A core calculus of dependency. In Proc. POPL. ACM, 1999.

Digital Library

[2]

T. Amtoft, S. Bandhakavi, and A. Banerjee. A logic for information flow in object-oriented programs. In Proc. POPL. ACM, 2006.

Digital Library

[3]

T. Amtoft and A. Banerjee. A logic for information flow analysis with an application to forward slicing of simple imperative programs. Science of Computer Programming, 64(1), 2007.

Digital Library

[4]

D. Binkley and K. Gallagher. Program slicing. Advances in Computers, 43, 1996.

[5]

I. Cartwright and M. Felleisen. The semantics of program dependence. In Proc. PLDI. ACM, 1989.

Digital Library

[6]

E. Cohen. Information transmission in computational systems. ACM SIGOPS Operating System Review, 11(5), 1977.

Digital Library

[7]

P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proc. POPL. ACM, 1977.

Digital Library

[8]

P. Cousot and R. Cousot. Systematic design of program analysis frameworks. In Proc. POPL. ACM, 1979.

Digital Library

[9]

R. Giacobazzi and I. Mastroeni. Abstract non-interference: Parameterizing non-interference by abstract interpretation. In Proc. POPL. ACM, 2004.

Digital Library

[10]

R. Giacobazzi and I. Mastroeni. Proving abstract non-interference. In Proc. EACSL, volume 3210 of LNCS. SV, 2004.

[11]

R. Giacobazzi, F. Ranzato, and F. Scozzari. Making abstract interpretations complete. Journal of the ACM, 47(2), 2000.

Digital Library

[12]

J. Goguen and J. Meseguer. Security policies and security models. In Proc. SSP. IEEE, 1982.

[13]

H. Hong, I. Lee, and O. Sokolsky. Abstract Slicing: A new approach to program slicing based on abstract interpretation and model checking. In Proc. SCAM. IEEE, 2005.

Digital Library

[14]

S. Horwitz, J. Prins, and T. Reps. Integrating non-interfering versions of programs. ACM TOPLAS, 11(3), 1989.

Digital Library

[15]

S. Hunt and I. Mastroeni. The PER model of abstract noninterference. In Proc. SAS, volume 3672 of LNCS. SV, 2005.

Digital Library

[16]

T. Reps. Algebraic properties of program integration. Science of Computer Programming, 17, 1991.

Digital Library

[17]

T. Reps and W. Yang. The semantics of program slicing and program integration. In Proc. Colloq. on Current Issues in Programming Languages, volume 352 of LNCS. SV, 1989.

Digital Library

[18]

X. Rival. Abstract dependences for alarm diagnosis. In Proc. APLAS, volume 3780 of LNCS. SV, 2005.

Digital Library

[19]

A. Sabelfeld and A. Myers. Language-based information-flow security. IEEE Journal on Selected Areas in Communications, 21(1), 2003.

Digital Library

[20]

F. Tip. A survey of program slicing techniques. Journal of Programming Languages, 3, 1995.

[21]

M. Ward and H. Zedan. Slicing as a program transformation. ACM TOPLAS, 29(2), 2007.

Digital Library

[22]

M. Weiser. Program slicing. In Proc. ICSE. IEEE, 1981.

Digital Library

[23]

G. Winskel. The Formal Semantics of Programming Languages: An Introduction. MIT Press, 1993.

Digital Library

Cited By

Vyshnavi CRaj CGopakumar GPrasanna GBelwal M(2024)Enhancing Code Insights through Semantic Change Impact Evaluation2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10725350(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10725350
Reinhard TFasse JJacobs BFerrara PHadarean L(2023)Completeness Thresholds for Memory Safety of Array Traversing ProgramsProceedings of the 12th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3589250.3596143(47-54)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3589250.3596143
Kashyap AJana A(2023)Policy-Based Code Slicing of Database Application Using Semantic Rule-Based ApproachInnovations in Bio-Inspired Computing and Applications10.1007/978-3-031-27499-2_37(392-403)Online publication date: 28-Mar-2023
https://doi.org/10.1007/978-3-031-27499-2_37
Show More Cited By

Index Terms

Data dependencies and program slicing: from syntax to abstract semantics
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
      1. Semantics
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics
      1. Denotational semantics

Recommendations

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 ...
Verified Validation of Program Slicing
CPP '15: Proceedings of the 2015 Conference on Certified Programs and Proofs

Program slicing is a well-known program transformation which simplifies a program wrt a given criterion while preserving its semantics. Since the seminal paper published by Weiser in 1981, program slicing is still widely used in various application ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

January 2008

214 pages

ISBN:9781595939777

DOI:10.1145/1328408

General Chair:
John Hatcliff
Kansas State University, USA
,
Program Chairs:
Robert Glück
University of Copenhagen, Denmark
,
Oege de Moor
Oxford University, UK

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PEPM08

Sponsor:

PEPM08: Partial Evaluation and Program Manipulation

January 7 - 8, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
423
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vyshnavi CRaj CGopakumar GPrasanna GBelwal M(2024)Enhancing Code Insights through Semantic Change Impact Evaluation2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT)10.1109/ICCCNT61001.2024.10725350(1-7)Online publication date: 24-Jun-2024
https://doi.org/10.1109/ICCCNT61001.2024.10725350
Reinhard TFasse JJacobs BFerrara PHadarean L(2023)Completeness Thresholds for Memory Safety of Array Traversing ProgramsProceedings of the 12th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3589250.3596143(47-54)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3589250.3596143
Kashyap AJana A(2023)Policy-Based Code Slicing of Database Application Using Semantic Rule-Based ApproachInnovations in Bio-Inspired Computing and Applications10.1007/978-3-031-27499-2_37(392-403)Online publication date: 28-Mar-2023
https://doi.org/10.1007/978-3-031-27499-2_37
Ambrozy M(2023)Searching for Criteria for a Thinking MachineBrain, Decision Making and Mental Health10.1007/978-3-031-15959-6_24(511-529)Online publication date: 2-Jan-2023
https://doi.org/10.1007/978-3-031-15959-6_24
Jana AHalder RAbhishekh KGanni SCortesi A(2020)Extending Abstract Interpretation to Dependency Analysis of Database ApplicationsIEEE Transactions on Software Engineering10.1109/TSE.2018.286170746:5(463-494)Online publication date: 1-May-2020
https://doi.org/10.1109/TSE.2018.2861707
Hanam QMesbah AHolmes R(2019)Aiding Code Change Understanding with Semantic Change Impact Analysis2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME.2019.00031(202-212)Online publication date: Sep-2019
https://doi.org/10.1109/ICSME.2019.00031
Giacobazzi RMastroeni I(2018)Abstract Non-InterferenceACM Transactions on Privacy and Security10.1145/317566021:2(1-31)Online publication date: 5-Feb-2018
https://dl.acm.org/doi/10.1145/3175660
Kulkarni RPatil P(2018)Abstraction of Information Flow Table from a Restructured Legacy ‘C’ Program to Be Amenable for Multicore ArchitectureInnovations in Computer Science and Engineering10.1007/978-981-10-8201-6_45(401-409)Online publication date: 26-May-2018
https://doi.org/10.1007/978-981-10-8201-6_45
Mastroeni IZanardini D(2017)Abstract Program SlicingACM Transactions on Computational Logic10.1145/302905218:1(1-58)Online publication date: 22-Feb-2017
https://dl.acm.org/doi/10.1145/3029052
Kulkarni RPatii P(2017)Abstraction of information flow and functional dependency from a restructured legacy ‘C’ program for parallelization2017 International Conference On Smart Technologies For Smart Nation (SmartTechCon)10.1109/SmartTechCon.2017.8358389(318-323)Online publication date: Aug-2017
https://doi.org/10.1109/SmartTechCon.2017.8358389
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents