ABSTRACT
Program slicing systematically identifies parts of a program relevant to a seed statement. Unfortunately, slices of modern programs often grow too large for human consumption. We argue that unwieldy slices arise primarily from an overly broad definition of relevance, rather than from analysis imprecision. While a traditional slice includes all statements that may affect a point of interest, not all such statements appear equally relevant to a human.
As an improved method of finding relevant statements, we propose thin slicing. A thin slice consists only of producer statements for the seed, i.e., those statements that help compute and copy avalue to the seed. Statements that explain why producers affect the seed are excluded. For example, for a seed that reads a value from a container object, a thin slice includes statements that store the value into the container, but excludes statements that manipulate pointers to the container itself. Thin slices can also be hierarchically expanded to include statements explaining how producers affect the seed, yielding a traditional slice in the limit.
We evaluated thin slicing for a set of debugging and program understanding tasks. The evaluation showed that thin slices usually included the desired statements for the tasks (e.g., the buggy statement for a debugging task). Furthermore, in simulated use of a slicing tool, thin slices revealed desired statements after inspecting 3.3 times fewer statements than traditional slicing for our debugging tasks and 9.4 times fewer statements for our program understanding tasks. Finally, our thin slicing algorithm scales well to relatively large Java benchmarks, suggesting that thin slicing represents an attractive option for practical tools.
- Codesurfer. http://www.grammatech.com/products/codesurfer/.Google Scholar
- T.J. Watson Libraries for Analysis. http://wala.sourceforge.net.Google Scholar
- M. Allen and S. Horwitz. Slicing Java programs that throw and catch exceptions. In PEPM '03: Proceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation, pages 44--54, New York, NY, USA, 2003. ACM Press. Google ScholarDigital Library
- L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, DIKU, 1994.Google Scholar
- D. C. Atkinson andW. G. Griswold. Effective whole-program analysis in the presence of pointers. In Foundations of Software Engineering, pages 46--55, 1998. Google ScholarDigital Library
- M. Das, S. Lerner, and M. Seigle. ESP: path-sensitive program verification in polynomial time. In Conference on Programming Language Design and Implementation (PLDI), 2002. Google ScholarDigital Library
- H. Do, S. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 10(4), October 2005. Google ScholarDigital Library
- S. Fink, E. Yahav, N. Dor, G. Ramalingam, and E. Geay. Effective typestate verification in the presence of aliasing. In International symposium on Software testing and analysis (ISSTA), 2006. Google ScholarDigital Library
- C. Hammer and G. Snelting. An improved slicer for Java. In Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, pages 17--22, 2004. Google ScholarDigital Library
- S. Horwitz, P. Pfeiffer, and T. Reps. Dependence analysis for pointer variables. In Conference on Programming Language Design and Implementation (PLDI), 1989. Google ScholarDigital Library
- S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. In Conference on Programming Language Design and Implementation (PLDI), 1988. Google ScholarDigital Library
- J. Krinke. Advanced Slicing of Sequential and Concurrent Programs. PhD thesis, University of Passau, 2003.Google Scholar
- L. Larsen and M. J. Harrold. Slicing object-oriented software. In International Conference on Software Engineering (ICSE), 1996. Google ScholarDigital Library
- D. Liang and M. J. Harrold. Slicing objects using system dependence graphs. In ICSM, pages 358--367, 1998. Google ScholarDigital Library
- R. Manevich, M. Sridharan, S. Adams, M. Das, and Z. Yang. PSE: explaining program failures via postmortem static analysis. In SIGSOFT '04/FSE-12: Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, pages 63-- 72, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for java. ACM Trans. Softw. Eng. Methodol., 14(1):1--41, 2005. Google ScholarDigital Library
- M. Mock, D. C. Atkinson, C. Chambers, and S. J. Eggers. Improving program slicing with dynamic points-to data. SIGSOFT Softw. Eng. Notes, 27(6):71--80, 2002. Google ScholarDigital Library
- A. Orso, S. Sinha, and M. J. Harrold. Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging. ACM Transactions on Software Engineering and Methodology (TOSEM), 13(2):199--239, 2004. Google ScholarDigital Library
- M. Renieris and S. P. Reiss. Fault localization with nearest neighbor queries. In IEEE International Conference on Automated Software Engineering (ASE), 2003.Google ScholarCross Ref
- T. Reps. Program analysis via graph reachability. Information and Software Technology, 40(11--12):701--726, November/December 1998.Google Scholar
- T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In ACM Symposium on Principles of Programming Languages (POPL), 1995. Google ScholarDigital Library
- T. Reps, S. Horwitz, M. Sagiv, and G. Rosay. Speeding up slicing. In ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE), New Orleans, LA, December 1994. Google ScholarDigital Library
- A. Rountev, A. Milanova, and B. G. Ryder. Points-to analysis for Java using annotated constraints. In Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), Tampa Bay, Florida, October 2001. Google ScholarDigital Library
- B. G. Ryder, W. A. Landi, P. A. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural modification side-effect analysis with pointer aliasing. ACM Trans. Program. Lang. Syst., 23(2):105--186, 2001. Google ScholarDigital Library
- M. Sridharan and R. Bodfk. Refinement-based context-sensitive points-to analysis for Java. In Conference on Programming Language Design and Implementation (PLDI), 2006. Google ScholarDigital Library
- T. Teitelbaum. Personal communication regarding CodeSurfer. 2007.Google Scholar
- F. Tip. A survey of program slicing techniques. Journal of programming languages, 3:121--189, 1995.Google Scholar
- M. D. Weiser. Program slices: formal, psychological, and practical investigations of an automatic program abstraction method. PhD thesis, University of Michigan, Ann Arbor, 1979. Google ScholarDigital Library
- A. Zeller. Isolating cause--effect chains from computer programs. SIGSOFT Softw. Eng. Notes, 27(6):1--10, 2002. Google ScholarDigital Library
- X. Zhang, N. Gupta, and R. Gupta. Pruning dynamic slices with confidence. In Conference on Programming Language Design and Implementation (PLDI), 2006. Google ScholarDigital Library
- X. Zhang, N. Gupta, and R. Gupta. A study of effectiveness of dynamic slicing in locating real faults. Empirical Software Engineering, 2006. To appear. Google ScholarDigital Library
- X. Zhang, R. Gupta, and Y. Zhang. Efficient forward computation of dynamic slices using reduced ordered binary decision diagrams. In International Conference on Software Engineering (ICSE), 2004. Google ScholarDigital Library
- X. Zhang, S. Tallam, and R. Gupta. Dynamic slicing long running programs through execution fast forwarding. In ACM SIGSOFT Symposium on Foundations of Software Engineering, 2006. Google ScholarDigital Library
- A. X. Zheng, M. I. Jordan, B. Liblit, M. Naik, and A. Aiken. Statistical debugging: Simultaneous identification of multiple bugs. In Proceedings of the 23rd International Conference on Machine Learning, 2006. Google ScholarDigital Library
Index Terms
- Thin slicing
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 ...
Thin slicing
Proceedings of the 2007 PLDI conferenceProgram slicing systematically identifies parts of a program relevant to a seed statement. Unfortunately, slices of modern programs often grow too large for human consumption. We argue that unwieldy slices arise primarily from an overly broad definition ...
Static slicing in the presence of goto statements
A static program slice is an extract of a program which can help our understanding of the behavior of the program; it has been proposed for use in debugging, optimization, parallelization, and integration of programs. This article considers two types of ...
Comments