Deriving an approximation algorithm for automatic computation of ripple effect measures

摘要

The ripple effect measures impact, or how likely it is that a change to a particular module may cause problems in the rest of a program. It can also be used as an indicator of the complexity of a particular module or program. Central to this paper is a reformulation in terms of matrix arithmetic of the original ripple effect algorithm produced by Yau and Collofello in 1978. The main aim of the reformulation is to clarify the component parts of the algorithm making the calculation more explicit. The reformulated algorithm has been used to implement REST (Ripple Effect and Stability Tool) which produces ripple effect measures for C programs. This paper describes the reformulation of Yau and Collofello's ripple effect algorithm focusing on the computation of matrix Z_m which holds intramodule change propagation information. The reformulation of the ripple effect algorithm is validated using fifteen programs which have been grouped by type. Due to the approximation spurious Is are contained within matrix Z_m. It is discussed whether this has an impact on the accuracy of the reformulated algorithm. The conclusion of this research is that the approximated algorithm is valid and as such can replace Yau and Collofello's original algorithm.