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

research-article

A vocabulary of program slicing-based techniques

Author:

Josep SilvaAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 44, Issue 3

Article No.: 12, Pages 1 - 41

https://doi.org/10.1145/2187671.2187674

Published: 14 June 2012 Publication History

Abstract

This article surveys previous work on program slicing-based techniques. For each technique, we describe its features, its main applications, and a common example of slicing using such a technique. After discussing each technique separately, all of them are compared in order to clarify and establish the relations between them. This comparison gives rise to a classification of techniques which can help to guide future research directions in this field.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

Agrawal, H., Horgan, J. R., Krauser, E. W., and London, S. 1993. Incremental regression testing. In Proceedings of the Conference on Software Maintenance. IEEE Computer Society, 348--357.

Digital Library

[4]

Beck, J. 1993. Interface slicing: A static program analysis tool for software engineering. Ph.D. dissertation, Morgantown, WV.

Digital Library

[5]

Beck, J. and Eichmann, D. 1993. Program and interface slicing for reverse engineering. In Proceedings of the 15th International Conference on Software Engineering. IEEE Computer Society Press, 509--519.

Digital Library

[6]

Bergeretti, J. and Carré, B. 1985. Information-flow and data-flow analysis of While-programs. ACM Trans. Program. Lang. Syst. 7, 1, 37--61.

Digital Library

[7]

Beszédes, Á., Faragó, C., Szabó, Z. M., Csirik, J., and Gyimóthy, T. 2002. Union slices for program maintenance. In Proceedings of the International Conference on Software Maintenance. IEEE Computer Society, 12--21.

Digital Library

[8]

Binkley, D., Danicic, S., Gyimóthy, T., Harman, M., Kiss, Á., and Korel, B. 2006a. A formalization of the relationship between forms of program slicing. Sci. Comput. Program. 62, 3, 228--252.

Digital Library

[9]

Binkley, D., Danicic, S., Gyimóthy, T., Harman, M., Kiss, A., and Korel, B. 2006b. Theoretical foundations of dynamic program slicing. Theoretical Computer Science 360, 1, 23--41.

Digital Library

[10]

Binkley, D., Danicic, S., Gyimothy, T., Harman, M., Kiss, A., and Ouarbya, L. 2004. Formalizing executable dynamic and forward slicing. In Proceedings of the 4th IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society, 43--52.

Digital Library

[11]

Binkley, D. and Gallagher, K. B. 1996. Program slicing. Adv. Comput. 43, 1--50.

[12]

Binkley, D. and Harman, M. 2004. A survey of empirical results on program slicing. Adv. Comput. 62, 105--178.

[13]

Canfora, G., Cimitile, A., and De Lucia, A. 1998. Conditioned program slicing. Inform. Softw. Technol. 40, 11--12, 595--608.

[14]

Canfora, G., Cimitile, A., De Lucia, A., and Lucca, G. A. D. 1994. Software salvaging based on conditions. In Proceedings of the International Conference on Software Maintenance. 424--433.

Digital Library

[15]

Chen, T. Y. and Cheung, Y. Y. 1993. Dynamic program dicing. In Proceedings of the International Conference on Software Maintenance. 378--385.

Digital Library

[16]

Cheney, J. 2007. Program slicing and data provenance. IEEE Data Engineer. Bullet. 30, 4, 22--28.

[17]

Cheng, J. 1993. Slicing concurrent programs—A graph-theoretical approach. In Proceedings of the International Workshop on Automated and Algorithmic Debugging. 223--240.

Digital Library

[18]

Danicic, S., Fox, C., Harman, M., Hierons, R., Howroyd, J., and Laurence, M. 2005. Static program slicing algorithms are minimal for free liberal program schemas. Comput. J. 48, 6, 737--748.

Digital Library

[19]

Danicic, S. and Harman, M. 1996. Program slicing using functional networks. In Proceedings of the 2nd U.K. Workshop on Program Comprehension. 54--65.

[20]

De Lucia, A. 2001. Program slicing: Methods and applications. In Proceedings of the 1st IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society Press, Los Alamitos, California, 142--149.

[21]

De Lucia, A., Fasolino, A. R., and Munro, M. 1996. Understanding function behaviors through program slicing. In Proceedings of the 4th Workshop on Program Comprehension, A. Cimitile and H. A. Müller, Eds. IEEE Computer Society Press, 9--18.

Digital Library

[22]

De Lucia, A., Harman, M., Hierons, R. M., and Krinke, J. 2003. Unions of slices are not slices. In Proceedings of the 7th European Conference on Software Maintenance and Reengineering. IEEE Computer Society, 363--367.

Digital Library

[23]

Dwyer, M. and Hatcliff, J. 1999. Slicing software for model construction. In Proceedings of the Symposium on Partial Evaluation and Semantic-Based Program Manipulation. 105--118.

[24]

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

Digital Library

[25]

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

Digital Library

[26]

Fox, C., Harman, M., Hierons, R., and Danicic, S. 2001. Backward conditioning: A new program specialization technique and its application to program comprehension. In Proceedings of the 9th IEEE International Workshop on Program Comprehension. 89--97.

Digital Library

[27]

Gallagher, K., Binkley, D., and Harman, M. 2006. Stop-list slicing. In Proceedings of the 6th IEEE International Workshop on Source Code Analysis and Manipulation. 11--20.

Digital Library

[28]

Gallagher, K. and Lyle, J. 1991. Using program slicing in software maintenance. IEEE Trans. Softw. Engin. 17, 8, 751--761.

Digital Library

[29]

Gallagher, K. B. 2004. Some notes on interprocedural program slicing. In Proceedings of the IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society, 36--42.

Digital Library

[30]

Gaucher, F. 2003. Slicing Lustre programs. Tech. rep., VERIMAG, Grenoble.

[31]

Giacobazzi, R. and Mastroeni, I. 2003. Non-standard semantics for program slicing. Higher Order Symbol. Comput. 16, 4, 297--339.

Digital Library

[32]

Giffhorn, D. and Hammer, C. 2007. An evaluation of slicing algorithms for concurrent programs. In Proceedings of the 7th IEEE International Working Conference on Source Code Analysis and Manipulation. IEEE Computer Society, 17--26.

Digital Library

[33]

Greibach, S. 1985. Theory of Program Structures: Schemes, Semantics, Verification. Springer-Verlag New York, Inc., Secaucus, NJ.

Digital Library

[34]

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

Digital Library

[35]

Gyimóthy, T., Beszédes, Á., and Forgács, I. 1999. An efficient relevant slicing method for debugging. In Proceedings of the 7th European Software Engineering Conference. Springer-Verlag, 303--321.

Digital Library

[36]

Hall, R. 1995. Automatic extraction of executable program subsets by simultaneous dynamic program slicing. Auto. Softw. Engin. 2, 1, 33--53.

[37]

Harman, M. and Danicic, S. 1997. Amorphous program slicing. In Proceedings of the 5th International Workshop on Program Comprehension. IEEE Computer Society Press, 70--79.

Digital Library

[38]

Harman, M., Danicic, S., Sivagurunathan, Y., and Simpson, D. 1996. The next 700 slicing criteria. In Proceedings of the 2nd U.K. Workshop on Program Comprehension.

[39]

Harman, M. and Gallagher, K. 1998. Program slicing. Inform. Softw. Technol. 40, 11--12, 577--582.

[40]

Harman, M. and Hierons, R. 2001. An overview of program slicing. Softw. Focus 2, 3, 85--92.

[41]

Harman, M., Hierons, R. M., Fox, C., Danicic, S., and Howroyd, J. 2001. Pre/postconditioned slicing. In Proceedings of the International Conference on Software Maintenance. 138--147.

Digital Library

[42]

Hong, H., Lee, I., and Sokolsky, O. 2005. Abstract slicing: A new approach to program slicing based on abstract interpretation and model checking. In Proceedings of the 5th IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society, 25--34.

Digital Library

[43]

Horwitz, S., Reps, T., and Binkley, D. 1988. Interprocedural slicing using dependence graphs. In Proceedings of the Conference on Programming Language Design and Implementation, ACM SIGPLAN, 23, 7, 35--46.

Digital Library

[44]

Jackson, D. and Rollins, E. 1994. Chopping: A generalization of slicing. Tech. rep. CS-94-169, Carnegie Mellon University, School of Computer Science.

Digital Library

[45]

Jhala, R. and Majumdar, R. 2005. Path slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM Press, New York, NY, 38--47.

Digital Library

[46]

Jones, N. 1996. An introduction to partial evaluation. ACM Comput. Surv. 28, 3, 480--503.

Digital Library

[47]

Korel, B. and Laski, J. 1988. Dynamic program slicing. Inform. Process. Letters 29, 3, 155--163.

Digital Library

[48]

Krinke, J. 1998. Static slicing of threaded programs. SIGPLAN Notices 33, 7, 35--42.

Digital Library

[49]

Krinke, J. 2003a. Barrier slicing and chopping. In Proceedings of the 3rd IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society, 81--87.

[50]

Krinke, J. 2003b. Context-sensitive slicing of concurrent programs. In Proceedings of the 11th ACM SIGSOFT Symposium on Foundations of Software Engineering. 178--187.

Digital Library

[51]

Krinke, J. 2004. Slicing, chopping, and path conditions with barriers. Softw. Qual. J. 12, 4, 339--360.

Digital Library

[52]

Kuck, D., Kuhn, R., Padua, D., Leasure, B., and Wolfe, M. 1981. Dependence graphs and compiler optimization. In Proceedings of the 8th Symposium on the Principles of Programming Languages, SIGPLAN Notices. 207--218.

Digital Library

[53]

Lakhotia, A. 1993. Rule-based approach to computing module cohesion. In Proceedings of the 15th International Conference on Software Engineering. IEEE Computer Society Press, Los Alamitos, CA, 35--44.

Digital Library

[54]

Larsen, L. and Harrold, M. 1996. Slicing object-oriented software. In Proceedings of the 18th International Conference on Software Engineering. IEEE Computer Society, 495--505.

Digital Library

[55]

Müller-Olm, M. and Seidl, H. 2001. On optimal slicing of parallel programs. In Proc. of the 33rd ACM Symposium on Theory of Computing. ACM, New York, NY, 647--656.

Digital Library

[56]

Nanda, M. and Ramesh, S. 2000. Slicing concurrent programs. In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis. ACM, New York, NY, 180--190.

Digital Library

[57]

Lyle, J. and Weiser, M. 1987. Automatic program bug location by program slicing. In Proceedings of the 2nd International Conference on Computers and Applications. 877--882.

[58]

Ning, J., Engberts, A., and Kozaczynski, W. 1994. Automated support for legacy code understanding. Commun. ACM 37, 5, 50--57.

Digital Library

[59]

Nishimatsu, A., Jihira, M., Kusumoto, S., and Inoue, K. 1999. Call-mark slicing: An efficient and economical way of reducing slices. In Proceedings of the 21st International Conference on Software Engineering. ACM Press, 422--431.

Digital Library

[60]

Orso, A., Sinha, S., and Harrold, M. 2001a. Effects of pointers on data dependences. In Proceedings of the 9th International Workshop on Program Comprehension (IWPC'01). 39--49.

Digital Library

[61]

Orso, A., Sinha, S., and Harrold, M. 2001b. Incremental slicing based on data-dependence types. In Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01). 158--167.

Digital Library

[62]

Ottenstein, K. and Ottenstein, L. 1984. The program dependence graph in a software development environment. In Proceedings of the 1st ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments. ACM Press, New York, NY, 177--184.

Digital Library

[63]

Reps, T. and Bricker, T. 1989. Illustrating interference in interfering versions of programs. SIGSOFT Softw. Engineer. Notes 14, 7, 46--55.

Digital Library

[64]

Reps, T. and Rosay, G. 1995. Precise interprocedural chopping. SIGSOFT Softw. Engineer. Notes 20, 4, 41--52.

Digital Library

[65]

Sivagurunathan, Y., Harman, M., and Danicic, S. 1997. Slicing, I/O, and the implicit state. In Proceedings of the International Workshop on Automated and Algorithmic Debugging. 59--68.

[66]

Sparud, J. and Runciman, C. 1997. Tracing lazy functional computations using redex trails. In Proceedings of the 9th International Symposium on Programming Languages, Implementations, Logics and Programs. Springer, Berlin, Lecture Notes in Computer Science, vol. 1292, 291--308.

Digital Library

[67]

Sridharan, M., Fink, S., and Bodik, R. 2007. Thin slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, NY, 112--122.

Digital Library

[68]

Takada, T., Ohata, F., and Inoue, K. 2002. Dependence-cache slicing: A program slicing method using lightweight dynamic information. In Proceedings of the 10th International Workshop on Program Comprehension. IEEE Computer Society, 169--177.

Digital Library

[69]

Tan, H. and Ling, T. 1998. Correct program slicing of database operations. IEEE Softw. 15, 2, 105--112.

Digital Library

[70]

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

[71]

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

Digital Library

[72]

Ward, M. 2002. Program slicing via fermat transformations. In Proceedings of the 26th International Computer Software and Applications Conference, Prolonging Software Life: Development and Redevelopment. IEEE Computer Society, 357--362.

Digital Library

[73]

Ward, M. 2003. Slicing the scam mug: A case study in semantic slicing. In Proceedings of the 3rd IEEE International Workshop on Source Code Analysis and Manipulation. IEEE Computer Society, 88--97.

[74]

Ward, M. and Zedan, H. 2007. Slicing as a program transformation. ACM Trans. Program. Lang. Syst. 29, 2.

Digital Library

[75]

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

Digital Library

[76]

Weiser, M. 1981. Program slicing. In Proceedings of the 5th International Conference on Software Engineering. 439--449.

Digital Library

[77]

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

Digital Library

[78]

Willmor, D., Embury, S., and Shao, J. 2004. Program slicing in the presence of a database state. In Proceedings of the 20th IEEE International Conference on Software Maintenance. IEEE Computer Society, 448--452.

Digital Library

[79]

Xu, B., Qian, J., Zhang, X., Wu, Z., and Chen, L. 2005. A brief survey of program slicing. SIGSOFT Softw. Engineer. Notes 30, 2, 1--36.

Digital Library

[80]

Zhao, J. 2002. Slicing aspect-oriented software. In Proceedings of the 10th International Workshop on Program Comprehension. IEEE Computer Society, 251.

Digital Library

Cited By

Gerling L(2025)Syntax-preserving program slicing for C-based software product linesJournal of Systems and Software10.1016/j.jss.2024.112255219(112255)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112255
Bendjeddou ABrodo LFalaschi MTiezzi E(2024)A Computational Model of the Secondary Hemostasis Pathway in Reaction SystemsMathematics10.3390/math1215242212:15(2422)Online publication date: 4-Aug-2024
https://doi.org/10.3390/math12152422
Hirsch THofer B(2024)Reducing the Length of Dynamic and Relevant Slices by Pruning Boolean ExpressionsElectronics10.3390/electronics1306114613:6(1146)Online publication date: 20-Mar-2024
https://doi.org/10.3390/electronics13061146
Show More Cited By

Index Terms

A vocabulary of program slicing-based techniques
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation

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 ...
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 ...
Computing super reduced program slices by composing slicing techniques
SAC '17: Proceedings of the Symposium on Applied Computing

Program slicing is a technique to extract the part of a program (the slice) that influences or is influenced by a set of variables at a given point. Computing minimal slices is undecidable in the general case, and obtaining the minimal slice of a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 44, Issue 3

June 2012

344 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2187671

Issue’s Table of Contents

Copyright © 2012 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 June 2012

Accepted: 01 October 2010

Revised: 01 December 2007

Received: 01 October 2006

Published in CSUR Volume 44, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

107
Total Citations
View Citations
1,985
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gerling L(2025)Syntax-preserving program slicing for C-based software product linesJournal of Systems and Software10.1016/j.jss.2024.112255219(112255)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112255
Bendjeddou ABrodo LFalaschi MTiezzi E(2024)A Computational Model of the Secondary Hemostasis Pathway in Reaction SystemsMathematics10.3390/math1215242212:15(2422)Online publication date: 4-Aug-2024
https://doi.org/10.3390/math12152422
Hirsch THofer B(2024)Reducing the Length of Dynamic and Relevant Slices by Pruning Boolean ExpressionsElectronics10.3390/electronics1306114613:6(1146)Online publication date: 20-Mar-2024
https://doi.org/10.3390/electronics13061146
Ballis DBrodo LFalaschi M(2024)Modeling and Analyzing Reaction Systems in MaudeElectronics10.3390/electronics1306113913:6(1139)Online publication date: 20-Mar-2024
https://doi.org/10.3390/electronics13061139
Galindo CKrinke JPérez SSilva J(2024)Field-sensitive program slicingJournal of Systems and Software10.1016/j.jss.2023.111939210(111939)Online publication date: Apr-2024
https://doi.org/10.1016/j.jss.2023.111939
Brodo LBruni RFalaschi M(2024)A framework for monitored dynamic slicing of reaction systemsNatural Computing: an international journal10.1007/s11047-024-09976-323:2(217-234)Online publication date: 4-May-2024
https://dl.acm.org/doi/10.1007/s11047-024-09976-3
Brodo LBruni RFalaschi MGori RMilazzo PMontagna VPulieri P(2024)Causal analysis of positive Reaction SystemsInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-024-00757-y26:4(509-526)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10009-024-00757-y
Cao YDong YPeng J(2024)Vulnerability detection based on transformer and high‐quality number embeddingConcurrency and Computation: Practice and Experience10.1002/cpe.829236:28Online publication date: 23-Sep-2024
https://doi.org/10.1002/cpe.8292
El Yaacoub AMottola LVoigt TRümmer P(2023)Timing Analysis of Embedded Software Updates2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA58653.2023.00010(1-11)Online publication date: 30-Aug-2023
https://doi.org/10.1109/RTCSA58653.2023.00010
Soha PGergely THorváth FVancsics BBeszédes Á(2023)A Case Against Coverage-Based Program Spectra2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00011(13-24)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00011
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents