The Influences of Edge Instability on Change Propagation and Connectivity in Call Graphs

摘要

During the lifetime of any software there are numerous changes, which lead to a large number of versions over time. The amount of effort in programming and debugging for these updates and therefore the reliability of the software depends substantially on how far the change propagates. We introduced the concept of Propagation Scope (PS) to quantify change propagation and investigated several open-source software systems. We found that the propagation property varies even with systems of similar scales. According to the asymmetry between the in-degree and out-degree distributions in call graphs of software, we defined Edge Instability (EI) to measure the change propagation of a call graph. Analyzing newly added nodes in six software, we found that the new nodes exhibited preferential attachment behaviors and were more likely to call new nodes. We proposed a model based on these observations to adjust EI and Clustering Coefficient (CC). CC has been believed to be the major factor determining the propagation scope in a network. Our experiments showed, however, that EI had a larger impact on the propagation of call graphs. In both real software and our model, we measured the connectivity of call graphs with EI and evaluated connectivity under three edge-removal strategies. Our experiments showed that removing edges with high EIs hurt network connectivity the most.