Improving slice accuracy by compression of data and control flow paths

ABSTRACT

Program slicing is a useful technique in tools for program understanding and transformation. Computing correct and accurate slices for unstructured programs is particularly difficult. We present a new family of slicing algorithms that are proved correct and are more accurate than the best previous algorithms. An empirical study shows significant improvements of our algorithms on real code.

REFERENCES

• 1: H. Agrawal. On slicing programs with jump statements. In Proc. ACM Conf. Programming Lang. Design and Implementation (PLDI), 1994.
• 2: T. Ball and S. Horwitz. Slicing programs with arbitrary control-flow. In Automated and Algorithmic Debugging, pages 206--222, 1993.
• 3: J.-D. Choi and J. Ferrante. Static slicing in the presence of goto statements. ACM Trans. Programming Languages and Systems, 16(4):1097--1113, July 1994.
• 4: Y. Cohen and Y. A. Feldman. Automatic high-quality reengineering of database programs by abstraction, transformation, and reimplementation. ACM Trans. Software Engineering and Methodology, 12(3):285--316, July 2003.
• 5: R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Programming Languages and Systems, 13(4):451--490, Oct 1991.
• 6: M. D. Ernst. Practical fine-grained static slicing of optimized code. Technical Report MSR-TR-94-14, Microsoft Research, Redmond, WA, July 1994.
• 7: Y. A. Feldman and D. A. Friedman. Portability by automatic translation: A large-scale case study. Artificial Intelligence, 107(1):1--28, 1999.
• 8: Y. A. Feldman and L. Gendler. DISCERN: Towards the automatic discovery of software contracts. In Proc. Fourth IEEE Int'l Conf. Software Engineering and Formal Methods, pages 90--99, Sept. 2006.
• 9: M. Harman and S. Danicic. A new algorithm for slicing unstructured programs. J. Software Maintenance, 10(6), 1998.
• 10: M. Harman, A. Lakhotia, and D. Binkley. Theory and algorithms for slicing unstructured programs. Information and Software Technology, 48(7):549--565, 2006.
• 11: S. Kumar and S. Horwitz. Better slicing of programs with jumps and switches. In Fundamental Approaches to Software Engineering, pages 96--112, 2002.
• 12: K. J. Ottenstein and L. M. Ottenstein. The program dependence graph in a software development environment. SIGPLAN Not., 19(5):177--184, 1984.
• 13: C. Rich. A formal representation for plans in the Programmer's Apprentice. In Proc. 7th Int. Joint Conf. Artificial Intelligence, pages 1044--1052, Vancouver, British Columbia, Canada, Aug. 1981.
• 14: C. Rich and R. C. Waters. The Programmer's Apprentice. ACM Press and Addison Wesley, 1990.
• 15: M. Weiser. Program slicing. IEEE Trans. Software Engineering, SE-10(4), 1984.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

General Terms:
Algorithms

Keywords:
program slicing