Efficient and precise dynamic impact analysis using execute-after sequences

ABSTRACT

As software evolves, impact analysis estimates the potential effects of changes, before or after they are made, by identifying which parts of the software may be affected by such changes. Traditional impact-analysis techniques are based on static analysis and, due to their conservative assumptions, tend to identify most of the software as affected by the changes. More recently, researchers have begun to investigate dynamic impact-analysis techniques, which rely on dynamic, rather than static, information about software behavior. Existing dynamic impact-analysis techniques are either very expensive---in terms of execution overhead or amount of dynamic information collected---or imprecise. In this paper, we present a new technique for dynamic impact analysis that is almost as efficient as the most efficient existing technique and is as precise as the most precise existing technique. The technique is based on a novel algorithm that collects (and analyzes) only the essential dynamic information required for the analysis. We discuss our technique, prove its correctness, and present a set of empirical studies in which we compare our new technique with two existing techniques, in terms of performance and precision.

REFERENCES

• 1: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, A Differencing Algorithm for Object-Oriented Programs, Proceedings of the 19th IEEE international conference on Automated software engineering, p.2-13, September 20-24, 2004 [doi>10.1109/ASE.2004.5]
• 2: Robert S. Arnold, Software Change Impact Analysis, IEEE Computer Society Press, Los Alamitos, CA, 1996
• 3: B. Breech , A. Danalis , Stacey Shindo , Lori Pollock, Online Impact Analysis via Dynamic Compilation Technology, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.453-457, September 11-14, 2004
• 4: Design and evaluation of a wide-area event notification service, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.332-383, Aug. 2001 [doi>10.1145/380749.380767]
• 5: A. Chawla and A. Orso. A generic instrumentation framework for collecting dynamic information. In Online Proceeding of the ISSTA Workshop on Empirical Research in Software Testing (WERST 2004), july 2004.
• 6: James Law , Gregg Rothermel, Incremental Dynamic Impact Analysis for Evolving Software Systems, Proceedings of the 14th International Symposium on Software Reliability Engineering, p.430, November 17-21, 2003
• 7: James Law , Gregg Rothermel, Whole program Path-Based dynamic impact analysis, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 8: J. L. Lions. ARIANE 5, Flight 501 Failure, Report by the Inquiry Board. European Space Agency, July 1996.
• 9: J. P. Loyall, S. A. Mathisen, and C. P. Satterthwaite. Impact analysis and change management for avionics software. In Proceedings of the IEEE National Aeronautics and Electronics Conference, Part 2, pages 740--747, July 1997.
• 10: Alessandro Orso , Taweesup Apiwattanapong , Mary Jean Harrold, Leveraging field data for impact analysis and regression testing, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 11: Alessandro Orso , Taweesup Apiwattanapong , James Law , Gregg Rothermel , Mary Jean Harrold, An Empirical Comparison of Dynamic Impact Analysis Algorithms, Proceedings of the 26th International Conference on Software Engineering, p.491-500, May 23-28, 2004
• 12: Using Component Metacontent to Support the Regression Testing of Component-Based Software, Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01), p.716, November 07-09, 2001
• 13: Alessandro Orso , Donglin Liang , Mary Jean Harrold , Richard Lipton, Gamma system: continuous evolution of software after deployment, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 14: Shari Lawrence Pfleeger, Software engineering: theory and practice, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 15: Xiaoxia Ren , Fenil Shah , Frank Tip , Barbara G. Ryder , Ophelia Chesley, Chianti: a tool for change impact analysis of java programs, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 16: R. J. Turver and M. Munro. Early impact analysis technique for software maintenance. Journal of Software Maintenance, 6(1):35--52, Jan. 1994.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

General Terms:
Algorithms, Experimentation

Keywords:
dynamic analysis, impact analysis, software maintenance