skip to main content
research-article
Open access

Specialization Slicing

Published: 01 June 2014 Publication History

Abstract

This paper defines a new variant of program slicing, called specialization slicing, and presents an algorithm for the specialization-slicing problem that creates an optimal output slice. An algorithm for specialization slicing is polyvariant: for a given procedure р, the algorithm may create multiple specialized copies of р. In creating specialized procedures, the algorithm must decide for which patterns of formal parameters a given procedure should be specialized and which program elements should be included in each specialized procedure.
We formalize the specialization-slicing problem as a partitioning problem on the elements of the possibly infinite unrolled program. To manipulate possibly infinite sets of program elements, the algorithm makes use of automata-theoretic techniques originally developed in the model-checking community. The algorithm returns a finite answer that is optimal (with respect to a criterion defined in the article). In particular, (i) each element replicated by the specialization-slicing algorithm provides information about specialized patterns of program behavior that are intrinsic to the program, and (ii) the answer is of minimal size (i.e., among all possible answers with property (i), there is no smaller one).
The specialization-slicing algorithm provides a new way to create executable slices. Moreover, by combining specialization slicing with forward slicing, we obtain a method for removing unwanted features from a program. While it was previously known how to solve the feature-removal problem for single-procedure programs, it was not known how to solve it for programs with procedure calls.

References

[1]
L. O. Andersen. 1993. Binding-time analysis and the taming of C pointers. In Part. Eval. and Semantics-Based Prog. Manip. 47--58.
[2]
P. Anderson, T. Reps, and T. Teitelbaum. 2003. Design and implementation of a fine-grained software inspection tool. TSE 29, 8 (2003).
[3]
ANSI C. 2005. ISO/IEC 9899:TC2. (2005). “www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf”.
[4]
S. Bates and S. Horwitz. 1993. Incremental program testing using program dependence graphs. In Conference Record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1993), ACM Press, Charleston, SC, January 1993, 384--396.
[5]
D. Binkley. 1992. Using semantic differencing to reduce the cost of regression testing. In Proceedings of the IEEE International Conference on Software Maintenance (ICSM 1992), IEEE Computer Society, Orlando, FL, November 1992, 41--50.
[6]
D. Binkley. 1993. Precise executable interprocedural slices. LOPLAS 2 (1993), 31--45.
[7]
D. Binkley. 1997. Semantics guided regression test cost reduction. TSE 23, 8 (1997), 498--516.
[8]
D. Binkley. 2012. Personal Communication. (July 2012).
[9]
D. Binkley, S. Danicic, T. Gyimóthy, M. Harman, Á. Kiss, and L. Ouarbya. 2004. Formalizing executable dynamic and forward slicing. In Proceedings of the 4th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2004), IEEE Computer Society, Chicago, IL, September 2004, 43--52.
[10]
D. Binkley, S. Danicic, M. Harman, J. Howroyd, and L. Ouarbya. 2006. A formal relationship between program slicing and partial evaluation. Formal Aspects of Computing 18, 2 (2006), 103--119.
[11]
D. Binkley and K. Gallagher. 1996. Program slicing. In Advances in Computers, Vol. 43. Marvin V. Zelkowitz (Ed.), 1--50. Academic Press.
[12]
R. F. Book and F. Otto. 1993. String-Rewriting Systems. Springer-Verlag.
[13]
A. Bouajjani, J. Esparza, A. Finkel, O. Maler, P. Rossmanith, B. Willems, and P. Wolper. 2000. An efficient automata approach to some problems on context-free grammars. IPL 74, 5--6 (2000), 221--227.
[14]
A. Bouajjani, J. Esparza, and O. Maler. 1997. Reachability analysis of pushdown automata: Application to model checking. In Proceedings of the 8th International Conference on Concurrency Theory (CONCUR 1997), Springer, Warsaw, Poland, July, 1997, 135--150.
[15]
J. R. Büchi. 1964. Regular canonical systems and finite automata. Arch. Math. Logik Grundlagenforschung 6 (1964), 91--111.
[16]
J. R. Büchi. 1988. Finite Automata, their Algebras and Grammars. Springer-Verlag. D. Siefkes (ed.).
[17]
M. A. Bulyonkov. 1993. Extracting polyvariant binding time analysis from polyvariant specializer. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM 1993), ACM Press, Copenhagen, Denmark, June 1993, 59--65.
[18]
G. Canfora, A. Cimitile, A. De Lucia, and G. A. Di Lucca. 1994. Software salvaging based on conditions. In Proceedings of the International Conference on Software Maintenance (ICSM 1994), IEEE Computer Society, Victoria, BC, Canada, September 1994, 424--433.
[19]
D. Caucal. 1992. On the regular structure of prefix rewriting. Theor. Comp. Sci. 106, 1 (1992), 61--86.
[20]
S. Chaudhuri. 2008. Subcubic algorithms for recursive state machines. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2008), ACM Press, San Francisco, CA, January 2008, 159--169.
[21]
CodeSurfer. CodeSurfer System. (2014). Retrieved May 10, 2014 from www.grammatech.com/products/codesurfer.
[22]
K. D. Cooper and K. Kennedy. 1988. Interprocedural side-effect analysis in linear time. PLDI. 57--66.
[23]
S. Danicic, M. Daoudi, C. Fox, M. Harman, R. M. Hierons, J. Howroyd, L. Ouarbya, and M. P. Ward. 2005. ConSUS: A light-weight program conditioner. J. Syst. and Software 77, 3 (2005).
[24]
A. De Lucia, A. R. Fasolino, and M. Munro. 1996. Understanding function behaviors through program slicing. In Proceedings of the 4th International Workshop on Program Comprehension (WPC 1996), IEEE Computer Society, Berlin, Germany, March 1996, 9--10.
[25]
H. Do, S. G. Elbaum, and G. Rothermel. 2005. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering 10, 4 (2005), 405--435.
[26]
J. Esparza, D. Hansel, P. Rossmanith, and S. Schwoon. 2000. Efficient algorithms for model checking pushdown systems. In Proceedings of the 12th International Conference on Computer Aided Verification (CAV 2000), Springer, Chicago, IL, July 2000, 232--247.
[27]
J. Field, G. Ramalingam, and F. Tip. 1995. Parametric program slicing. In POPL.
[28]
A. Finkel, B. Willems, and P. Wolper. 1997. A direct symbolic approach to model checking pushdown systems. ENTCS 9 (1997).
[29]
I. Forgács and T. Gyimóthy. 1997. An efficient interprocedural slicing method for large programs. In Proceedings of the 9th International Conference on Software Engineering & Knowledge Engineering (SEKE 1997), Madrid, Spain, June 1997.
[30]
C. Fox, S. Danicic, M. Harman, and R. M. Hierons. 2004. ConSIT: A fully automated conditioned program slicer. SPE 34, 1 (2004).
[31]
K. B. Gallagher and J. R. Lyle. 1991. Using program slicing in software maintenance. TSE 17, 8 (Aug. 1991), 751--761.
[32]
R. Giacobazzi and I. Mastroeni. 2003. Non-standard semantics for program slicing. HOSC 16, 4 (2003), 297--339.
[33]
P. Godefroid, N. Klarlund, and K. Sen. 2005. DART: Directed automated random testing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2005), ACM Press, Chicago, IL, June 2005, 213--223.
[34]
S. Graf and H. Saïdi. 1997. Construction of abstract state graphs with PVS. In Proceedings of the 9th International Conference on Computer Aided Verification (CAV 1997), Springer, Haifa, Israel, June 1997, 72--83.
[35]
A. Gupta. 1994. Inductive Boolean Function Manipulation: A Hardware Verification Methodology for Automatic Induction. Ph.D. Dissertation. Carnegie Mellon Univ. Tech. Rep. CMU-CS-94-208.
[36]
M. Harman, D. Binkley, and S. Danicic. 2003. Amorphous program slicing. J. Systems and Software 68, 1 (2003), 45--64.
[37]
M. Harman and S. Danicic. 1997. Amorphous program slicing. In Proceedings of the 5th International Workshop on Program Comprehension (WPC 1997), IEEE Computer Society, Dearborn, MI, May 1997, 70--79.
[38]
H. S. Hong, I. Lee, and O. Sokolsky. 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 (SCAM 2005), IEEE Computer Society, Budapest, Hungary, September--October 2005, 25--34.
[39]
J. E. Hopcroft. 1971. An n log n algorithm for minimizing the states in a finite automaton. In Proceedings of the International Symposium on the Theory of Machines and Computations, Haifa, Israel, Academic Press, New York, August 1971, 189--196.
[40]
S. Horwitz. 1990. Identifying the semantic and textual differences between two versions of a program. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 1990), ACM Press, White Plains, New York, NY, June 1990, 234--245.
[41]
S. Horwitz, B. Liblit, and M. Polishchuck. 2010. Better debugging via output tracing and callstack-sensitive slicing. TSE 36, 1 (Jan. 2010).
[42]
S. Horwitz, J. Prins, and T. Reps. 1989. Integrating non-interfering versions of programs. TOPLAS 11, 3 (July 1989), 345--387.
[43]
S. Horwitz and T. W. Reps. 1991. Efficient comparison of program slices. Acta Inf. 28, 8 (1991), 713--732.
[44]
S. Horwitz and T. Reps. 1992. The use of program dependence graphs in software engineering. In Proceedings of the 14th International Conference on Software Engineering (ICSE 1992), ACM Press, Melbourne, Australia, May 1992, 392--411.
[45]
S. Horwitz, T. Reps, and D. Binkley. 1990. Interprocedural slicing using dependence graphs. TOPLAS 12, 1 (Jan. 1990), 26--60.
[46]
M. Hutchins, H. Foster, T. Goradia, and T. Ostrand. 1994. Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria. Int. Conf. on Software Eng. 191--200.
[47]
D. Jackson and E. J. Rollins. 1994. A new model of program dependences for reverse engineering. In Proceedings of the 2nd ACM SIGSOFT Symposium on Foundations of Software Engineering (SIGSOFT 1994), ACM Press, New Orleans, LA, December 1994, 2--10.
[48]
J. Jaffar, V. Murali, J. A. Navas, and A. E. Santosa. 2012. Path-sensitive backward slicing. In Proceedings of the 19th International Symposium on Static Analysis (SAS 2012), Springer, Deauville, France, September 2012, 231--247.
[49]
N. D. Jones, C. K. Gomard, and P. Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall International.
[50]
N. Kidd, A. Lal, and T. Reps. 2007. WALi: The Weighted Automaton Library. (2007). www.cs.wisc.edu/wpis/wpds/download.php.
[51]
J. Krinke. 2004. Context-sensitivity matters, but context does not. In Proceedings of the 4th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2004), IEEE Computer Society, Chicago, IL, September 2004, 29--35.
[52]
D. J. Kuck, R. H. Kuhn, B. Leasure, D. A. Padua, and M. Wolfe. 1981. Dependence graphs and compiler optimizations. In Conference Record of the 8th Annual ACM Symposium on Principles of Programming Languages (POPL 1981), ACM Press, Williamsburg, Virginia, January 1981, 207--218.
[53]
A. Lakhotia and J. Deprez. 1998. Restructuring programs by tucking statements into functions. Inf. and Softw. Tech. 40, 11--12 (1998), 677--690.
[54]
J. Lyle and M. Weiser. 1986. Experiments on slicing-based debugging tools. In Proceedings of the 1st Workshop on Empirical Studies of Programmers, Ablex Pub. Corp., Washington, DC, June 1986, 187--197.
[55]
J. R. Lyle and M. Weiser. 1987. Automatic program bug location by program slicing. In Proceedings of the 2nd International Conference on Computers and Applications, Peking, China, June 1987, 877--882.
[56]
G. B. Mund and R. Mall. 2007. Program slicing. In The Compiler Design Handbook (2nd. ed.). Y. N. Srikant, Priti Shankar (Eds.), CRC Press, Chapter 14.
[57]
OpenFST. 2012. OpenFst Library. (2012). www.openfst.org.
[58]
K. J. Ottenstein and L. M. Ottenstein. 1984. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (SDE 1984), ACM Press, Pittsburgh, PA, April 1984, 177--184.
[59]
L. Ouarbya, S. Danicic, M. Daoudi, M. Harman, and C. Fox. 2002. A denotational interprocedural program slicer. In Proceedings of the 9th Working Conference on Reverse Engineering (WCRE 2002), IEEE Computer Society, Richmond, VA, October--November 2002, 181--189.
[60]
T. Reps. 1998. Program analysis via graph reachability. Inf. and Softw. Tech. 40, 11--12 (1998), 701--726.
[61]
T. Reps, S. Horwitz, M. Sagiv, and G. Rosay. 1994. Speeding up slicing. In Proceedings of the 2nd ACM SIGSOFT Symposium on Foundations of Software Engineering (FSE 1994), ACM Press, New Orleans, LA, December 1994, 11--20.
[62]
T. Reps and G. Rosay. 1995. Precise interprocedural chopping. In Proceedings of the 3rd ACM SIGSOFT Symposium on Foundations of Software Engineering (FSE 1995), ACM Press, Washington, DC, October 1995, 41--52.
[63]
T. Reps and T. Turnidge. 1996. Program specialization via program slicing. In Selected Papers from the International Seminar on Partial Evaluation, Olivier Danvy, Robert Glück, Peter Thiemann (Eds.), Springer, Dagstuhl Castle, Germany, February 1996, 409--429.
[64]
S. Schwoon. 2002. Model-Checking Pushdown Systems. Ph.D. Dissertation. Technical Univ. of Munich, Munich, Germany.
[65]
J. Sebej. 2010. Reversal of regular languages and state complexity. In Proceedings of the Conference on Theory and Practice of Information Technologies (ITAT 2010), CEUR-WS.org, Vel'ka' Fatra, Slovak Republic, September 2010, 47--54.
[66]
SIR. Software-artifact Infrastructure Repository. (2014). Retrieved May 10, 2014 from sir.unl.edu/portal/index.php.
[67]
G. Snelting, T. Robschink, and J. Krinke. 2006. Efficient path conditions in dependence graphs for software safety analysis. TOSEM 15, 4 (2006), 410--457.
[68]
C. Sun, L. Tang, and Z. Chen. 2010. Enforcing reactive noninterference with reachability analysis. In Proceedings of the 10th International Conference on Quality Software (QSIC), IEEE Computer Society, Zhangjiajie, China, July 2010, 142--150.
[69]
C. Sun, L. Tang, and Z. Chen. 2011. Enforcing reactive noninterference with reachability analysis. In Proceedings of the 8th International Conference on Information Technology: New Generations (ITNG), IEEE Computer Society, Las Vegas, NV, April 2011, 321--326.
[70]
F. Tip. 1995. A survey of program slicing techniques. JPL 3, 3 (1995).
[71]
M. Weiser. 1984. Program slicing. TSE 10, 4 (July 1984), 352--357.
[72]
Wikipedia: Output-Sensitive Algorithm 2014. Output-sensitive algorithm. (2014). en.wikipedia.org/wiki/Output-sensitive_algorithm, Jan. 5, 2014.
[73]
M. Yannakakis. 1990. Graph-theoretic methods in database theory. In Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), ACM Press, Nashville, TN, 230--242.

Cited By

View all
  • (2024)STASE: Static Analysis Guided Symbolic Execution for UEFI Vulnerability Signature GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695543(1783-1794)Online publication date: 27-Oct-2024
  • (2020)Slicing Unconditional Jumps with Unnecessary Control DependenciesLogic-Based Program Synthesis and Transformation10.1007/978-3-030-68446-4_15(293-308)Online publication date: 7-Sep-2020
  • (2019)An automated change impact analysis approach for User Requirements Notation modelsJournal of Systems and Software10.1016/j.jss.2019.110397157(110397)Online publication date: Nov-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems
ACM Transactions on Programming Languages and Systems  Volume 36, Issue 2
July 2014
171 pages
ISSN:0164-0925
EISSN:1558-4593
DOI:10.1145/2633904
Issue’s Table of Contents
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: 01 June 2014
Accepted: 01 January 2014
Revised: 01 August 2013
Received: 01 October 2012
Published in TOPLAS Volume 36, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Program slicing
  2. executable slice
  3. feature removal
  4. program dependence graph
  5. program specialization
  6. pushdown system
  7. reverse-deterministic automaton

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)102
  • Downloads (Last 6 weeks)19
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)STASE: Static Analysis Guided Symbolic Execution for UEFI Vulnerability Signature GenerationProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695543(1783-1794)Online publication date: 27-Oct-2024
  • (2020)Slicing Unconditional Jumps with Unnecessary Control DependenciesLogic-Based Program Synthesis and Transformation10.1007/978-3-030-68446-4_15(293-308)Online publication date: 7-Sep-2020
  • (2019)An automated change impact analysis approach for User Requirements Notation modelsJournal of Systems and Software10.1016/j.jss.2019.110397157(110397)Online publication date: Nov-2019
  • (2018)Towards a framework for generating program dependence graphs from source codeProceedings of the 4th ACM SIGSOFT International Workshop on Software Analytics10.1145/3278142.3278144(30-36)Online publication date: 5-Nov-2018
  • (2017)Hierarchical regression test case selection using slicingInternational Journal of Computational Science and Engineering10.1504/IJCSE.2017.08288214:2(179-197)Online publication date: 1-Jan-2017
  • (2016)An improved algorithm for slicing machine codeACM SIGPLAN Notices10.1145/3022671.298400351:10(378-393)Online publication date: 19-Oct-2016
  • (2016)An improved algorithm for slicing machine codeProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984003(378-393)Online publication date: 19-Oct-2016
  • (2015)Partial evaluation of machine codeACM SIGPLAN Notices10.1145/2858965.281432150:10(860-879)Online publication date: 23-Oct-2015
  • (2015)Partial evaluation of machine codeProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814321(860-879)Online publication date: 23-Oct-2015

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media