AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

SymPas: Symbolic Program Slicing

College of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
Show Author Information

Abstract

Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior. Current mainstream static slicing methods operate on dependence graph PDG (program dependence graph) or SDG (system dependence graph), but these friendly graph representations may be a bit expensive for some users. In this paper we attempt to study a light-weight approach of static program slicing, called Symbolic Program Slicing (SymPas), which works as a dataflow analysis on LLVM (low-level virtual machine). In our SymPas approach, slices are stored in symbolic forms, not in procedures being re-analyzed (cf. procedure summaries). Instead of re-analyzing a procedure multiple times to find its slices for each callling context, we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis; SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation (IR). For comparison, we systematically adapt IFDS (interprocedural finite distributive subset) analysis and the SDG-based slicing method (SDG-IFDS) to statically slice IR programs. Evaluated on open-source and benchmark programs, our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost, compared with backward SDG-IFDS, thus being more efficient. In addition, the result shows that after studying slices from 66 programs, ranging up to 336 800 IR instructions in size, SymPas is highly size-scalable.

Keywords

data flow analysisinstruction dependency tablelow-level virtual machine (LLVM)procedure symbolic sliceprogram slicing

Electronic Supplementary Material

Download File(s)
jcst-36-2-397-Highlights.pdf (412 KB)

References

[1]

Weiser M. Program slicing. IEEE Transaction on Software Engineering, 1984, 16(5): 498-509. https://doi.org/10.1109/TSE.1984.5010248.
Crossref Google Scholar
[2]

Tip F. A survey of program slicing techniques. Journal of Programming Languages, 1995, 3(3): 121-189.
Google Scholar
[3]

Gallagher K B, Lyle J R. Using program slicing in software maintenance. IEEE Transactions on Software Engineering, 1991, 17(8): 751-761. https://doi.org/10.1109/32.83912.
Crossref Google Scholar
[4]

Harman M, Hierons R M. An overview of program slicing. Software Focus, 2001, 2(3): 85-92. https://doi.org/10.1002/swf.41.
Crossref Google Scholar
[5]

Binkley D, Gallagher K B. Program slicing. Advances in Computers, 1996, 43: 1-50. https://doi.org/10.1016/S0065-2458(08)60641-5.
Crossref Google Scholar
[6]

Josep S. A vocabulary of program slicing-based techniques. ACM Computing Surveys, 2012, 44(3): Article No. 12. https://doi.org/10.1145/2187671.2187674.
Crossref Google Scholar
[7]

Binkley D, Harman M. A survey of empirical results on program slicing. Advances in Computers, 2004, 62: 105-178. https://doi.org/10.1016/S0065-2458(03)62003-6.
Crossref Google Scholar
[8]
Binkley D, Danicic S, Gyimothy T, Harman M, Kiss A, Ouarbya L. Formalizing executable dynamic and forward slicing. In Proc. the 4th IEEE International Workshop on Source Code Analysis and Manipulation, September 2004, pp.43-52. https://doi.org/10.1109/SCAM.2004.13.
Crossref
[9]

Horwiz S, Reps T, Binkley D. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 1990, 12(1): 26-60. https://doi.org/10.1145/77606.77608.
Crossref Google Scholar
[10]
Reps T, Horwitz S, Sagiv M. Precise interprocedural dataflow analysis via graph reachability. In Proc. the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 1995, pp.49-61. https://doi.org/10.1145/199448.199462.
Crossref
[11]

Ottenstein K J, Ottenstein L M. The program dependence graph in a software development environment. ACM SIGPLAN Notices, 1984, 19(5): 177-184. https://doi.org/10.1145/390011.808263.
Crossref Google Scholar
[12]
Reps T, Sagiv M, Horwitz S. Interprocedural dataflow analysis via graph reachability. Technical Report, University of Copenhagen, 1994. https://research.cs.wisc.edu/wpis/papers/diku-tr94-14.pdf, Nov. 2020.
[13]
Naeem A, Lhotak O, Rodriguez J. Practical extensions to the IFDS algorithm. In Proc. the 19th International Conference on Compiler Construction, March 2010, pp.124-144. https://doi.org/10.1007/978-3-642-11970-5_8.
Crossref
[14]

Cytron R, Ferrante J, Rosen B K, Wegman M N, Zadeck F K. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Prog. Langs. and Systs., 1991, 13(4): 451-490. https://doi.org/10.1145/115372.115320.
Crossref Google Scholar
[15]
Zhao J, Zdancewic S, Nagarakatte S, Martin M. Formalizing the LLVM intermediate representation for verified program transformation. In Proc. the 39th Annual ACM SIGPLAN-SIGACT Symp. Principles of Programming Languages, January 2012, pp.427-440. https://doi.org/10.1145/2103656.2103709.
Crossref
[16]

Canfora G, Cimitile A, De Lucia A. Conditioned program slicing. Information and Software Technology, 1998, 40(11/12): 595-607. https://doi.org/10.1016/S0950-5849(98)00086-X.
Crossref Google Scholar
[17]

Harman M, Binkley D, Danicic S. Amorphous program slicing. Journal of Systems and Software, 2003, 68(1): 45-64. https://doi.org/10.1016/S0164-1212(02)00135-8.
Crossref Google Scholar
[18]

Morrison D R. PATRICIA-Practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM, 1968, 15(4): 514-534. https://doi.org/10.1145/321479.321481.
Crossref Google Scholar
[19]
Okasaki C, Gill A. Fast mergeable integer maps. In Proc. the 1998 ACM SIGPLAN Workshop on Machine Learning, September 1998, pp.77-86.
[20]

Adams S. Efficient sets: A balancing act. Journal of Functional Programming, 1993, 3(4): 553-562. https://doi.org/10.1017/S0956796800000885.
Crossref Google Scholar
[21]
Sharir M, Pnueli A. Two approaches to interprocedural dataflow analysis. In Program Flow Analysis: Theory and Applications, Muchnick S S, Jones N D (eds.), Prentice-Hall Inc., 1981, pp.189-233.
[22]
Gustafsson J, Betts A, Ermedahl A, Lisper B. The mälardalen WCET benchmarks Past, present and future. In Proc. the 10th Workshop Worst-Case Execution Time Analysis, July 2010, pp.137-147. https://doi.org/10.4230/OASIcs.WCET.2010.136.
[23]

Binkley D, Gold N, Harman M. An empirical study of static program slice size. ACM Transactions on Software Engineering and Methodology, 2007, 16(2): Article No. 8. https://doi.org/10.1145/1217295.1217297.
Crossref Google Scholar
[24]
Hwang J C, Du M W, Chou C R. Finding program slices for recursive procedures. In Proc. the 12th Annual International Computer Software & Applications Conference, Oct. 1988, pp.220-227. https://doi.org/10.1109/CMPSAC.1988.17176.
Crossref
[25]

Reps T. On the sequential nature of interprocedural program-analysis problems. Acta Informatica, 1996, 33(8): 739-757. https://doi.org/10.1007/s002360050068.
Crossref Google Scholar
[26]
Lakhotia A. Improved interprocedural slicing algorithm. Technical Report, University of Southwestern Louisian, 1992. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.3466&rep=rep1&type=pdf, Nov. 2020.
[27]

Livadas P, Johnson T. An optimal algorithm for the construction of the system dependence graph. Information Sciences, 2000, 125(1/2/3/4): 99-131. https://doi.org/10.1016/S0020-0255(99)00030-4.
Crossref Google Scholar
[28]

Alomari H, Collard M, Maletic J, Alhindawi N, Meqdadi O. srcSlice: Very efficient and scalable forward static slicing. Journal of Software: Evolution and Process, 2014, 26(11): 931-961. https://doi.org/10.1002/smr.1651.
Crossref Google Scholar
[29]

Mastroeni I, Zanardini D. Abstract program slicing: An abstract interpretation-based approach to program slicing. ACM Trans. Comput. Logic, 2017, 18(1): Article No. 7. https://doi.org/10.1145/3029052.
Crossref Google Scholar
[30]
Cousot P, Cousot R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proc. the 4th ACM Symp. Principles of Programming Languages, January 1977, pp.238-252. https://doi.org/10.1145/512950.512973.
Crossref
[31]

Zhang Y. A novel formal approach to program slicing. Science in China, Ser. F: Info. Sci., 2007, 50(5): 657-670. https://doi.org/10.1007/s11432-007-0061-2.
Crossref Google Scholar
[32]

Zhang Y. A precise monadic dynamic slicing method. Knowledge-Based Systems, 2017, 115: 40-54. https://doi.org/10.1016/j.knosys.2016.10.013.
Crossref Google Scholar
[33]
Liang S. Modular monadic semantics and compilation [Ph.D. Thesis]. University of Yale, 1998.
[34]
Wadler P. Comprehending monads. In Proc. the 1990 ACM Conf. LISP and Functional Programming, May 1990, pp.61-78. https://doi.org/10.1145/91556.91592.
Crossref
[35]
Liang S, Hudak P, Jones M. Monad transformers and modular interpreters. In Proc. the 22nd ACM SIG-PLAN-SIGACT Sym. Principles of Programming Languages, January 1995, pp.333-343. https://doi.org/10.1145/199448.199528.
Crossref
[36]
Binkley D, Gold N, Harman M, Islam S, Krinke J, Yoo S. ORBS: Language-independent program slicing. In Proc. the 22nd Int. Symp. Foundations of Software Engineering, November 2014, pp.109-120. https://doi.org/10.1145/2635868.2635893.
Crossref
[37]

Binkley D, Gold N, Islam S, Krinke J, Yoo S. A comparison of tree- and line-oriented observational slicing. Empir. Software Eng., 2019, 24(1): 3077-3113. https://doi.org/10.1007/s10664-018-9675-9.
Crossref Google Scholar
[38]
Beszédes A, Faragó C, Szabó Z, Csirik J, Gyimóthy T. Union slices for program maintenance. In Proc. the 2002 IEEE Int. Conference on Software Maintenance, Oct. 2002, pp.12-21. https://doi.org/10.1109/ICSM.2002.1167743.
Crossref
[39]
Lisper B, Masud A, Khanfar H. Static backward demand-driven slicing. In Proc. the 2015 Workshop on Partial Evaluation and Program Manipulation, January 2015, pp.115-126. https://doi.org/10.1145/2678015.2682538.
Crossref
[40]
Srinivasan V, Reps T. An improved algorithm for slicing machine code. In Proc. the 2016 ACM SIGPLAN Int. Conf. Object-Oriented Programming, Systems, Languages, and Applications, October 2016, pp.378-393. https://doi.org/10.1145/2983990.2984003.
Crossref
[41]

Meyers T, Binkley D. An empirical study of slice-based cohesion and coupling metrics. ACM Transactions on Software Methodology, 2007, 17(1): Article No. 2. https://doi.org/10.1145/1314493.1314495.
Crossref Google Scholar
[42]
Zhang X, Gupta R, Zhang Y. Precise dynamic slicing algorithms. In Proc. the 25th Int. Conf. Software Engineering, May 2003, pp.319-329.
Journal of Computer Science and Technology
Volume 36 Issue 2,
March 2021
Pages 397-418
DOI: 10.1007/s11390-020-9754-4
Cite this article:
Zhang Y-Z. SymPas: Symbolic Program Slicing. Journal of Computer Science and Technology, 2021, 36(2): 397-418. https://doi.org/10.1007/s11390-020-9754-4

338

Views

5

Crossref

5

Web of Science

6

Scopus

1

CSCD

Altmetrics
Received: 05 June 2019
Accepted: 22 January 2020
Published: 05 March 2021
©Institute of Computing Technology, Chinese Academy of Sciences 2021
Return