Path-based dynamic impact analysis

Graduation date: 2006Successful software systems evolve over their lifetimes through the cumulative\ud changes made by software maintainers. As software evolves, the problems resulting\ud from software change worsen, exacerbated by increased system size and complexity,\ud lack of program understanding, amount of effort required to make changes, and\ud number of personnel involved. Experience shows that software changes made without\ud visibility into their effects can lead to poor effort estimates, delays in release\ud schedules, degraded software design, unreliable software products, increased costs,\ud and premature retirement of the software system.\ud Software change impact analysis, impact analysis, is a software maintenance\ud technique meant to address these problems, by assessing the effects of changes\ud made to a software system. While impact analysis is frequently cited as a motivation\ud or a potential application for program analysis and software maintenance research,\ud research specific to the task of impact analysis has languished for more than 10\ud years. In addition, few researchers have examined the empirical factors underlying common impact analysis techniques or the tradeoffs inherent in known techniques,\ud and none have performed empirical studies comparing impact analysis techniques.\ud In this dissertation we introduce a new impact analysis approach, named\ud PathImpact, that addresses a set of tradeoffs not addressed by any current impact\ud analysis approach. Ours is the first fully-dynamic impact analysis approach.\ud PathImpact uses light-weight instrumentation to record program execution at\ud the level of procedure calls and returns, then efficiently builds a compressed representation\ud that can be directly used to estimate change impact.\ud We next extend PathImpact to accomodate system evolution yielding a technique\ud we call EvolveImpact. EvolveImpact updates the impact representation\ud after a system change, whereas PathImpact requires a complete recompution.\ud In addition, we show how our approaches can be extended to a large class\ud of emerging software architectures, including Java component-based systems and\ud large-scale systems.\ud Finally, we discuss the implementation of our approaches, present the first cost\ud models for impact analysis techniques, and report the results of the first empirical\ud studies that compare impact analysis techniques. We also empirically examine the\ud performance of our approaches and the factors affecting the use of our techniques in\ud practice. We found that our approach has linear time and space complexity (in the\ud size of the dynamic information collected) and achieved a mean compression value\ud of 0.955 on the subjects we used in our experiments. Our investigation of program\ud evolution across multiple versions of three of our subject programs showed that,\ud depending on the level of change activity, EvolveImpact can update the impact\ud representation more efficiently than recomputing it in a majority of cases