Abstracting Program Dependencies Using the Method Dependence Graph

While empowering a wide range of software engineering tasks, the traditional fine-grained software dependence (TSD) model can face great scalability challenges that hinder its applications. Many dependence abstraction approaches have been proposed, yet most of them either target very specific clients or model partial dependencies only, while others have not been fully evaluated for their accuracy with respect to the TSD model, especially in approximating forward dependencies on object-oriented programs. To fill this gap, we present a new dependence abstraction called the method dependence graph (MDG) that approximates the TSD model at method level, and compare it against a recent TSD abstraction, called the Static-Exectue-After (SEA), concerning forward-dependence approximation. We also evaluate the cost-effectiveness of both approaches in the application context of impact analysis. Our results show that the MDG can approximate TSD safely, for method-level forward dependence at least, with little loss of precision yet huge gain in efficiency, and for the same purpose, while both are safe, the MDG can achieve significantly higher precision than SEA at practical costs.