The DOI matches its Crossref record; 95 of the 95 references it cites were found in a registry or an index.
A brief survey of program slicing
Abstract
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 studied, as well as algorithms to compute them. Different notions of slicing have different properties and different applications. These notions vary from Weiser's syntax-preserving static slicing to amorphous slicing which is not syntax-preserving, and the algorithms can be based on dataflow equations, information-flow relations or dependence graphs.Slicing was first-developed to facilitate debugging, but it is then found helpful in many aspects of the software development life cycle, including program debugging, software testing, software measurement, program comprehension, software maintenance, program parallelization and so on.Over the last two decades, several surveys on program slicing have been presented. However, most of them only reviewed parts of researches on program slicing or have now been out of date. People who are interested in program slicing need more information about the up to date researches. Our survey fills this gap. In this paper, we briefly review most of existing slicing techniques including static slicing, dynamic slicing and the latest slicing techniques. We also discuss the contribution of each work and compare the major difference between them. Researches on slicing are classified by the research hot spots such that people can be kept informed of the overall program slicing researches.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Weiser, M. (1984) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1984.5010248 · Cited by 3,204
The program dependence graph and its use in optimization
Ferrante, J., Ottenstein, K. J., & Warren, J. D. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/24039.24041 · Cited by 2,755
Efficiently computing static single assignment form and the control dependence graph
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., & Zadeck, F. K. (1991) · ACM Transactions on Programming Languages and Systems · doi:10.1145/115372.115320 · Cited by 2,267
Fedeli, L., & Huebl, A. (2022) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.6464240 · Cited by 1,319
Precise interprocedural dataflow analysis via graph reachability
Reps, T., Horwitz, S., & Sagiv, M. (1995) · Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '95 · doi:10.1145/199448.199462 · Cited by 1,170
Points-to analysis in almost linear time
Steensgaard, B. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237727 · Cited by 1,088
Shapiro, E. Y. (1983) · doi:10.7551/mitpress/1192.001.0001 · Cited by 1,085
Certification of programs for secure information flow
Denning, D. E., & Denning, P. J. (1977) · Communications of the ACM · doi:10.1145/359636.359712 · Cited by 1,029
Agrawal, H., & Horgan, J. R. (1990) · Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation - PLDI '90 · doi:10.1145/93542.93576 · Cited by 867
Programmers use slices when debugging
Weiser, M. (1982) · Communications of the ACM · doi:10.1145/358557.358577 · Cited by 761
Korel, B., & Laski, J. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90054-3 · Cited by 759
Software testing techniques (2nd ed.)
Beizer, B. (1990) · Cited by 744
Flow Analysis of Computer Programs
Hecht, M. S. (1977) · Cited by 724
Analyzing regression test selection techniques
Rothermel, G., & Harrold, M. J. (1996) · IEEE Transactions on Software Engineering · doi:10.1109/32.536955 · Cited by 708
Structured Programming with go to Statements
Knuth, D. E. (1974) · ACM Computing Surveys · doi:10.1145/356635.356640 · Cited by 678
Dependence graphs and compiler optimizations
Kuck, D. J., Kuhn, R. H., Padua, D. A., Leasure, B., & Wolfe, M. (1981) · Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '81 · doi:10.1145/567532.567555 · Cited by 651
A fast algorithm for finding dominators in a flowgraph
Lengauer, T., & Tarjan, R. E. (1979) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357062.357071 · Cited by 645
The program dependence graph in a software development environment
Ottenstein, K. J., & Ottenstein, L. M. (1984) · ACM SIGPLAN Notices · doi:10.1145/390011.808263 · Cited by 641
Conversion of control dependence to data dependence
Allen, J. R., Kennedy, K., Porterfield, C., & Warren, J. (1983) · Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '83 · doi:10.1145/567067.567085 · Cited by 609
Context-sensitive interprocedural points-to analysis in the presence of function pointers
Emami, M., Ghiya, R., & Hendren, L. J. (1994) · Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation · doi:10.1145/178243.178264 · Cited by 570
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · ACM SIGPLAN Notices · doi:10.1145/223428.207111 · Cited by 539
Using Slicing to Identify Duplication in Source Code
Komondoor, R., & Horwitz, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-47764-0_3 · Cited by 527
Efficient context-sensitive pointer analysis for C programs
Wilson, R. P., & Lam, M. S. (1995) · Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation · doi:10.1145/207110.207111 · Cited by 458
Efficient and precise datarace detection for multithreaded object-oriented programs
Choi, J.-D., Lee, K., Loginov, A., O'Callahan, R., Sarkar, V., & Sridharan, M. (2002) · Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation · doi:10.1145/512529.512560 · Cited by 441
Integrating noninterfering versions of programs
Horwitz, S., Prins, J., & Reps, T. (1989) · ACM Transactions on Programming Languages and Systems · doi:10.1145/65979.65980 · Cited by 417
Abadi, M., Banerjee, A., Heintze, N., & Riecke, J. G. (1999) · Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/292540.292555 · Cited by 413
Undecidability of static analysis
Landi, W. A. (1992) · ACM Letters on Programming Languages and Systems · doi:10.1145/161494.161501 · Cited by 407
Fourier-Motzkin elimination and its dual
Dantzig, G. B., & Eaves, B. C. (1973) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(73)90004-6 · Cited by 386
Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
Choi, J.-D., Burke, M., & Carini, P. R. (1993) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/158511.158639 · Cited by 362
Optimally profiling and tracing programs
Ball, T., & Larus, J. R. (1994) · ACM Transactions on Programming Languages and Systems · doi:10.1145/183432.183527 · Cited by 362
Program analysis via graph reachability
Reps, T. (1998) · Information and Software Technology · doi:10.1016/s0950-5849(98)00093-7 · Cited by 357
Weiser, M. (1979) · Deep Blue (University of Michigan) · doi:10.7302/11363 · Cited by 341
Interprocedural may-alias analysis for pointers: beyond k -limiting
Deutsch, A. (1994) · Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation · doi:10.1145/178243.178263 · Cited by 328
Debugging with dynamic slicing and backtracking
Agrawal, H., Demillo, R. A., & Spafford, E. H. (1993) · Software: Practice and Experience · doi:10.1002/spe.4380230603 · Cited by 311
Analysis of pointers and structures
Chase, D. R., Wegman, M., & Zadeck, F. K. (1990) · Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation - PLDI '90 · doi:10.1145/93542.93585 · Cited by 303
Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C
Ghiya, R., & Hendren, L. J. (1996) · Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '96 · doi:10.1145/237721.237724 · Cited by 287
Context-sensitive synchronization-sensitive analysis is undecidable
Ramalingam, G. (2000) · ACM Transactions on Programming Languages and Systems · doi:10.1145/349214.349241 · Cited by 275
A framework for call graph construction algorithms
Grove, D., & Chambers, C. (2001) · ACM Transactions on Programming Languages and Systems · doi:10.1145/506315.506316 · Cited by 267
Harman, M., Hu, L., Hierons, R., Wegener, J., Sthamer, H., Baresel, A., & Roper, M. (2004) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2004.1265732 · Cited by 265
Bieman, J. M., & Ott, L. M. (1994) · IEEE Transactions on Software Engineering · doi:10.1109/32.310673 · Cited by 251
Dependence analysis for pointer variables
Horwitz, S., Pfeiffer, P., & Reps, T. (1989) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/73141.74821 · Cited by 233
Incremental program testing using program dependence graphs
Bates, S., & Horwitz, S. (1993) · Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '93 · doi:10.1145/158511.158694 · Cited by 222
Using program slicing to assist in the detection of equivalent mutants
Hierons, R. M., Harman, M., & Danicic, S. (1999) · Software Testing Verification and Reliability · Cited by 218
Information-flow and data-flow analysis of while-programs
Bergeretti, J.-F., & Carré, B. A. (1985) · ACM Transactions on Programming Languages and Systems · doi:10.1145/2363.2366 · Cited by 211
Precise dynamic slicing algorithms
Zhang, X., Gupta, R., & Zhang, Y. (2003) · doi:10.5555/776816.776855 · Cited by 186
Self-citationDeciding Linear Inequalities by Computing Loop Residues
Shostak, R. E. (1981) · Journal of the ACM · doi:10.1145/322276.322288 · Cited by 181
An overview of program slicing
Harman, M., & Hierons, R. (2001) · Software Focus · doi:10.1002/swf.41 · Cited by 178
Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation
Cheng, B.-C., & Hwu, W.-M. W. (2000) · Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation · doi:10.1145/349299.349311 · Cited by 165
Techniques for debugging parallel programs with flowback analysis
Choi, J.-D., Miller, B. P., & Netzer, R. H. B. (1991) · ACM Transactions on Programming Languages and Systems · doi:10.1145/115372.115324 · Cited by 164
Slicing Software for Model Construction
Hatcliff, J., Dwyer, M. B., & Zheng, H. (2000) · LISP and Symbolic Computation · doi:10.1023/a:1026599015809 · Cited by 160
A Survey of Empirical Results on Program Slicing
Binkley, D., & Harman, M. (2004) · Advances in computers · doi:10.1016/s0065-2458(03)62003-6 · Cited by 142
Efficient path conditions in dependence graphs for software safety analysis
Snelting, G., Robschink, T., & Krinke, J. (2006) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/1178625.1178628 · Cited by 141
A mechanism for efficient debugging of parallel programs
Miller, B. P., & Choi, J.-D. (1988) · ACM SIGPLAN Notices · doi:10.1145/960116.54004 · Cited by 138
Pointer analysis for multithreaded programs
Rugina, R., & Rinard, M. (1999) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/301618.301645 · Cited by 133
Program integration for languages with procedure calls
Binkley, D., Horwitz, S., & Reps, T. (1995) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/201055.201056 · Cited by 132
An efficient relevant slicing method for debugging
Gyimóthy, T., Beszédes, Á., & Forgács, I. (1999) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/318774.319248 · Cited by 131
Measuring design-level cohesion
Bieman, J. M., & Kang, B.-K. (1998) · IEEE Transactions on Software Engineering · doi:10.1109/32.666825 · Cited by 113
An Algorithm for Structuring Flowgraphs
Baker, B. S. (1977) · Journal of the ACM · doi:10.1145/321992.321999 · Cited by 108
Critical slicing for software fault localization
DeMillo, R. A., Pan, H., & Spafford, E. H. (1996) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/226295.226310 · Cited by 103
On the relationship between model-based debugging and program slicing
Wotawa, F. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00161-8 · Cited by 102
Taming control flow: a structured approach to eliminating goto statements
Erosa, A. M., & Hendren, L. J. (2002) · International Conference on Computer Languages (ICCL) · doi:10.1109/iccl.1994.288377 · Cited by 96
Rule-based approach to computing module cohesion
Lakhotia, A. (1993) · doi:10.5555/257572.257586 · Cited by 96
Forward computation of dynamic program slices
Korel, B., & Yalamanchili, S. (1994) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1145/186258.186514 · Cited by 93
On the importance of points-to analysis and other memory disambiguation methods for C programs
Ghiya, R., Lavery, D., & Sehr, D. C. (2001) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/378795.378806 · Cited by 92
Two Easy Theories Whose Combination is Hard
Pratt, V. (2002) · Cited by 88
Using semantic differencing to reduce the cost of regression testing
Binkley, D. (2003) · Proceedings/Proceedings - Conference on Software Maintenance · doi:10.1109/icsm.1992.242560 · Cited by 83
Dynamic slicing method for maintenance of large C programs
Beszédes, Á., Gergely, T., Szabo, Z. M., Csirik, J., & Gyimóthy, T. (2002) · Euromicro Conference on Software Maintenance and Reengineering (CSMR) · doi:10.1109/.2001.914974 · Cited by 80
Harman, M., Hierons, R. M., Fox, C., Danicic, S., & Howroyd, J. (2002) · IEEE International Conference on Software Maintenance (ICSM) · doi:10.1109/icsm.2001.972724 · Cited by 80
Improving program slicing with dynamic points-to data
Mock, M. U., Atkinson, D. C., Chambers, C., & Eggers, S. J. (2002) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/587051.587062 · Cited by 74
Experimental Evaluation of Program Slicing for Fault Localization
Kusumoto, S., Nishimatsu, A., Nishie, K., & Inoue, K. (2002) · Empirical Software Engineering · doi:10.1023/a:1014823126938 · Cited by 73
Identifying comprehension bottlenecks using program slicing and cognitive complexity metrics
Rilling, J., & Klemola, T. (2004) · International Symposium on Micro-NanoMechatronics and Human Science · doi:10.1109/wpc.2003.1199195 · Cited by 71
Decomposing legacy programs: a first step towards migrating to client–server platforms
Canfora, G., Cimitile, A., Lucia, A. D., & Lucca, G. A. D. (2000) · Journal of Systems and Software · doi:10.1016/s0164-1212(00)00030-3 · Cited by 69
Optimal tracing and incremental reexecution for debugging long-running programs
Netzer, R. H. B., & Weaver, M. H. (1994) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/178243.178477 · Cited by 68
Application of Dynamic Slicing in Program Debugging
Korel, B., & Rilling, J. (1997) · Cited by 67
Distributed slicing and partial re-execution for distributed programs
Duesterwald, E., Gupta, R., & Soffa, M. L. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57502-2_67 · Cited by 66
Efficient forward computation of dynamic slices using reduced ordered binary decision diagrams
Zhang, X., Gupta, R., & Zhang, Y. (2004) · doi:10.5555/998675.999454 · Cited by 66
Self-citationOn slicing a distributed computation
Garg, V. K., & Mittal, N. (2002) · Proceedings of the ... International Conference on Distributed Computing Systems/Proceedings of the International Conference on Distributed Computing Systems · doi:10.1109/icdsc.2001.918962 · Cited by 65
Towards automatic debugging of computer programs
Agrawal, H. (1992) · Cited by 61
Code extraction algorithms which unify slicing and concept assignment
Harman, M., Gold, N., Hierons, R. M., & Binkley, D. (2003) · Working Conference on Reverse Engineering (WCRE) · doi:10.1109/wcre.2002.1173060 · Cited by 55
Program slicing in understanding of large programs
Korel, B., & Rilling, J. (2002) · doi:10.1109/wpc.1998.693339 · Cited by 51
Interprocedural dynamic slicing applied to interprocedural data flow testing
Kramkar, M., Fritzson, P., & Shahmehri, N. (2002) · IEEE International Conference on Software Maintenance (ICSM) · doi:10.1109/icsm.1993.366924 · Cited by 44
STAD-a system for testing and debugging: user perspective
Korel, B., & Laski, J. W. (2003) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1109/wst.1988.5350 · Cited by 41
The value of slicing while debugging
Francel, M. A., & Rugaber, S. (2001) · Science of Computer Programming · doi:10.1016/s0167-6423(01)00013-2 · Cited by 39
Efficient path conditions in dependence graphs
Robschink, T., & Snelting, G. (2002) · ACM/IEEE International Conference on Software Engineering: Companion Proceedings (ICSE-Companion) · doi:10.1145/581339.581398 · Cited by 39
Incremental slicing based on data-dependences types
Orso, A., Sinha, S. K., & Harrold, M. J. (2002) · doi:10.1109/icsm.2001.972726 · Cited by 34
Slicing, Chopping, and Path Conditions with Barriers
Krinke, J. (2004) · Software Quality Journal · doi:10.1023/b:sqjo.0000039792.93414.a5 · Cited by 31
Feasible test path selection by principal slicing
Forgács, I., & Bertolino, A. (1997) · SZTAKI Publication Repository (Hungarian Academy of Sciences) · Cited by 24
Building executable union slices using conditioned slicing
Danicic, S., Lucia, A. D., & Harman, M. (2004) · IEEE International Conference on Program Comprehension (ICPC) · doi:10.1109/wpc.2004.1311051 · Cited by 19
Equivalence analysis and its application in improving the efficiency of program slicing
Liang, D., & Harrold, M. J. (2002) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/567793.567796 · Cited by 15
Precise interprocedural dependence analysis of parallel programs
Müller-Olm, M. (2003) · Theoretical Computer Science · doi:10.1016/j.tcs.2003.09.002 · Cited by 9
Pointer analysis for multithreaded programs
Rugina, R., & Rinard, M. (1999) · ACM SIGPLAN Notices · doi:10.1145/301631.301645 · Cited by 8
Forward Slicing of Multi-paradigm Declarative Programs Based on Partial Evaluation
Vidal, G. (2003) · Lecture notes in computer science · doi:10.1007/3-540-45013-0_17 · Cited by 6
Program slicing: Its improved algorithm and application in verification
Lü, Q., Zhang, F., & Qian, J. (1988) · Journal of Computer Science and Technology · doi:10.1007/bf02943330 · Cited by 6
Self-citationAn Adaptation of Dynamic Slicing Techniques for Logic Programming
Vasconcelos, W. W., & Aragão, M. A. T. (1998) · Lecture notes in computer science · doi:10.1007/10692710_16 · Cited by 3
Cited by
A Survey on Software Fault Localization
Wong, W. E., Gao, R., Li, Y., Abreu, R., & Wotawa, F. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2521368 · Cited by 1,110
“Hundreds of papers on this topic have been published [52], [344], [394] since Weiser first proposed static slicing in 1979 [361].”
BackgroundMetamorphic Testing: A Review of Challenges and Opportunities
Chen, T. Y., Kuo, F.-C., Liu, H., Poon, P.-L., Towey, D., Tse, T. H., & Zhou, Z. Q. (2019) · ACM Computing Surveys · doi:10.1145/3143561 · Cited by 665
Evaluating and Improving Fault Localization
Pearson, S., Campos, J., Just, R., Fraser, G., Abreu, R., Ernst, M. D., Pang, D., & Keller, B. (2017) · 2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE) · doi:10.1109/icse.2017.62 · Cited by 426
An empirical study on TensorFlow program bugs
Zhang, Y., Chen, Y., Cheung, S.-C., Xiong, Y., & Zhang, L. (2018) · Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis · doi:10.1145/3213846.3213866 · Cited by 304
Debugging reinvented: asking and answering why and why not questions about program behavior
Ko, A. J., & Myers, B. A. (2008) · Proceedings of the 30th international conference on Software engineering · doi:10.1145/1368088.1368130 · Cited by 296
Metadata
- Authors
- Xu, B., Qian, J., Zhang, X., Wu, Z., & Chen, L.
- Venue
- ACM SIGSOFT Software Engineering Notes
- Published
- 2005-03
- Volume
- 30
- Issue
- 2
- Pages
- 1-36
- ISSN
- 0163-5948 (ISSN-L)
- OpenAlex
- W2007121005
- Cited by
- 313
- References
- 95
- FWCI
- 44.06
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.