Program Tailoring: Slicing by Sequential Criteria

Authors Yue Li, Tian Tan, Yifei Zhang, Jingling Xue



PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2016.15.pdf
  • Filesize: 1.41 MB
  • 27 pages

Document Identifiers

Author Details

Yue Li
Tian Tan
Yifei Zhang
Jingling Xue

Cite AsGet BibTex

Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue. Program Tailoring: Slicing by Sequential Criteria. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 15:1-15:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ECOOP.2016.15

Abstract

Protocol and typestate analyses often report some sequences of statements ending at a program point P that needs to be scrutinized, since P may be erroneous or imprecisely analyzed. Program slicing focuses only on the behavior at P by computing a slice of the program affecting the values at P. In this paper, we propose to restrict our attention to the subset of that behavior at P affected by one or several statement sequences, called a sequential criterion (SC). By leveraging the ordering information in a SC, e.g., the temporal order in a few valid/invalid API method invocation sequences, we introduce a new technique, program tailoring, to compute a tailored program that comprises the statements in all possible execution paths passing through at least one sequence in SC in the given order. With a prototyping implementation, Tailor, we show why tailoring is practically useful by conducting two case studies on seven large real-world Java applications. For program debugging and understanding, Tailor can complement program slicing by removing SC-irrelevant statements. For program analysis, Tailor can enable a pointer analysis, which is unscalable to a program, to perform a more focused and therefore potentially scalable analysis to its specific parts containing hard language features such as reflection.
Keywords
  • Program Slicing
  • Program Analysis
  • API Protocol Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mithun Acharya, Tao Xie, Jian Pei, and Jun Xu. Mining API patterns as partial orders from source code: From usage scenarios to specifications. FSE '07. Google Scholar
  2. Stephen Adams, Thomas Ball, Manuvir Das, Sorin Lerner, Sriram K. Rajamani, Mark Seigle, and Westley Weimer. Speeding up dataflow analysis using flow-insensitive pointer analysis. SAS '02. Google Scholar
  3. Glenn Ammons, Rastislav Bodík, and James R. Larus. Mining specifications. POPL'02. Google Scholar
  4. Min Aung, Susan Horwitz, Rich Joiner, and Thomas Reps. Specialization slicing. ACM Trans. Program. Lang. Syst., 2014. Google Scholar
  5. Paulo Barros, René Just, Suzanne Millstein, Paul Vines, Werner Dietl, Marcelo d'Amorim, and Michael D. Ernst. Static analysis of implicit control flow: Resolving Java reflection and android intents. ASE '15. Google Scholar
  6. Jon Beck and David Eichmann. Program and interface slicing for reverse engineering. ICSE '93. Google Scholar
  7. Kevin Bierhoff, Nels E. Beckman, and Jonathan Aldrich. Practical API protocol checking with access permissions. ECOOP '09. Google Scholar
  8. David Binkley and Mark Harman. A survey of empirical results on program slicing. Advances in Computers., 2004. Google Scholar
  9. Eric Bodden. Efficient hybrid typestate analysis by determining continuation-equivalent states. ICSE '10. Google Scholar
  10. Eric Bodden. Inter-procedural data-flow analysis with IFDS/IDE and Soot. SOAP '12. Google Scholar
  11. Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. ICSE '11. Google Scholar
  12. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. OOPSLA '09. Google Scholar
  13. Manuvir Das, Sorin Lerner, and Mark Seigle. ESP: Path-sensitive program verification in polynomial time. PLDI '02. Google Scholar
  14. DOOP. URL: http://doop.program-analysis.org.
  15. John Field, G. Ramalingam, and Frank Tip. Parametric program slicing. POPL '95. Google Scholar
  16. Stephen J. Fink, Eran Yahav, Nurit Dor, G. Ramalingam, and Emmanuel Geay. Effective typestate verification in the presence of aliasing. ACM Trans. Softw. Eng. Methodol., 2008. Google Scholar
  17. Mark Gabel and Zhendong Su. Javert: Fully automatic mining of general temporal properties from dynamic traces. FSE '08. Google Scholar
  18. GrammaTech. GrammaTech static analysis. URL: http://www.grammatech.com.
  19. Mark Harman and Sebastian Danicic. Amorphous program slicing. IWPC '97. Google Scholar
  20. Mark Harman and Rob Hierons. An overview of program slicing. Software Focus., 2001. Google Scholar
  21. Susan Horwitz, Thomas Reps, and David Binkley. Interprocedural slicing using dependence graphs. ACM Trans. Program. Lang. Syst., 1990. Google Scholar
  22. Daniel Jackson and Eugene J. Rollins. A new model of program dependences for reverse engineering. SIGSOFT '94. Google Scholar
  23. Ranjit Jhala and Rupak Majumdar. Path slicing. PLDI '05. Google Scholar
  24. George Kastrinis and Yannis Smaragdakis. Hybrid context-sensitivity for points-to analysis. PLDI '13. Google Scholar
  25. Andrew J. Ko and Brad A. Myers. Extracting and answering why and why not questions about Java program output. ACM Trans. Softw. Eng. Methodol., 2010. Google Scholar
  26. Shrawan Kumar, Amitabha Sanyal, and Uday P. Khedker. Value slice: A new slicing concept for scalable property checking. TACAS '15. Google Scholar
  27. Ondřej Lhoták and Laurie Hendren. Scaling Java points-to analysis using Spark. CC '03. Google Scholar
  28. Yue Li, Tian Tan, Yulei Sui, and Jingling Xue. Self-inferencing reflection resolution for Java. ECOOP' 14. Google Scholar
  29. Yue Li, Tian Tan, and Jingling Xue. Effective soundness-guided reflection analysis. SAS'15. Google Scholar
  30. Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, J. Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z. Guyer, Uday P. Khedker, Anders Møller, and Dimitrios Vardoulakis. In defense of soundiness: A manifesto. CACM, 2015. Google Scholar
  31. Benjamin Livshits, John Whaley, and Monica Lam. Reflection analysis for Java. APLAS'05. Google Scholar
  32. Yi Lu, Lei Shang, Xinwei Xie, and Jingling Xue. An incremental points-to analysis with CFL-reachability. CC '13. Google Scholar
  33. Ana Milanova, Atanas Rountev, and Barbara G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Trans. Softw. Eng. Methodol., 2005. Google Scholar
  34. Nomair A. Naeem and Ondřej Lhoták. Typestate-like analysis of multiple interacting objects. OOPSLA '08. Google Scholar
  35. Phung Hua Nguyen and Jingling Xue. Interprocedural side-effect analysis and optimisation in the presence of dynamic class loading. ACSC '05. Google Scholar
  36. Tung Thanh Nguyen, Hoan Anh Nguyen, Nam H. Pham, Jafar M. Al-Kofahi, and Tien N. Nguyen. Graph-based mining of multiple object usage patterns. FSE '09. Google Scholar
  37. Michael Pradel, Ciera Jaspan, Jonathan Aldrich, and Thomas R. Gross. Statically checking API protocol conformance with mined multi-object specifications. ICSE '12. Google Scholar
  38. Thomas Reps, Susan Horwitz, and Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. POPL '95. Google Scholar
  39. Thomas Reps and Genevieve Rosay. Precise interprocedural chopping. SIGSOFT '95. Google Scholar
  40. Lei Shang, Yi Lu, and Jingling Xue. Fast and precise points-to analysis with incremental CFL-reachability summarisation. ASE '12. Google Scholar
  41. Lei Shang, Xinwei Xie, and Jingling Xue. On-demand dynamic summary-based points-to analysis. CGO '12. Google Scholar
  42. Sharon Shoham, Eran Yahav, Stephen Fink, and Marco Pistoia. Static specification mining using automata-based abstractions. ISSTA '07. Google Scholar
  43. Josep Silva. A vocabulary of program slicing-based techniques. ACM Comput. Surv., 2012. Google Scholar
  44. Yannis Smaragdakis, Martin Bravenboer, and Ondrej Lhoták. Pick your contexts well: understanding object-sensitivity. POPL '11. Google Scholar
  45. Yannis Smaragdakis, George Kastrinis, George Balatsouras, and Martin Bravenboer. More sound static handling of Java reflection. APLAS '15. Google Scholar
  46. Manu Sridharan and Rastislav Bodík. Refinement-based context-sensitive points-to analysis for Java. PLDI '06. Google Scholar
  47. Manu Sridharan, Stephen J. Fink, and Rastislav Bodik. Thin slicing. PLDI '07. Google Scholar
  48. Robert Tarjan. Depth first search and linear graph algorithms. SICOMP, 1972. Google Scholar
  49. Frank Tip. A survey of program slicing techniques. J Program Lang, 1995. Google Scholar
  50. Omer Tripp, Marco Pistoia, Stephen J. Fink, Manu Sridharan, and Omri Weisman. TAJ: Effective taint analysis of web applications. PLDI '09. Google Scholar
  51. Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. Soot - a Java bytecode optimization framework. CASCON '99. Google Scholar
  52. WALA. T.J. Watson libraries for analysis. URL: http://wala.sf.net.
  53. Mark Weiser. Program slicing. ICSE '81. Google Scholar
  54. John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. PLDI '04. Google Scholar
  55. Xiao Xiao and Charles Zhang. Geometric encoding: Forging the high performance context sensitive points-to analysis for Java. ISSTA '11. Google Scholar
  56. Jingling Xue and Phung Hua Nguyen. Completeness analysis for incomplete object-oriented programs. CC '05. Google Scholar
  57. Jingling Xue, Phung Hua Nguyen, and John Potter. Interprocedural side-effect analysis for incomplete object-oriented software modules. Journal of Systems and Software, 2007. Google Scholar
  58. Dacong Yan, Guoqing Xu, and Atanas Rountev. Demand-driven context-sensitive alias analysis for java. ISSTA '11. Google Scholar
  59. Sai Zhang and Michael D. Ernst. Which configuration option should I change? ICSE '14. Google Scholar
  60. Hao Zhong, Tao Xie, Lu Zhang, Jian Pei, and Hong Mei. MAPO: Mining and recommending API usage patterns. ECOOP '09. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail