Predicting defects using network analysis on dependency graphs

ABSTRACT

In software development, resources for quality assurance are limited by time and by cost. In order to allocate resources effectively, managers need to rely on their experience backed by code complexity metrics. But often dependencies exist between various pieces of code over which managers may have little knowledge. These dependencies can be construed as a low level graph of the entire system. In this paper, we propose to use network analysis on these dependency graphs. This allows managers to identify central program units that are more likely to face defects. In our evaluation on Windows Server 2003, we found that the recall for models built from network measures is by 10% points higher than for models built from complexity metrics. In addition, network measures could identify 60% of the binaries that the Windows developers considered as critical-twice as many as identified by complexity metrics.

References

1. F. B. e. Abreu and W. Melo, "Evaluating the Impact of OO Design on Software Quality," in International Software Metrics Symposium, Berlin, 1996.
2. V. R. Basili, L. C. Briand, and W. L. Melo, "A Validation of Object Orient Design Metrics as Quality Indicators," IEEE Transactions on Software Engineering, vol. 22, pp. 751--761, 1996.
3. V. R. Basili, F. Shull, and F. Lanubile, "Building Knowledge Through Families of Experiments," IEEE Transactions on Software Engineering, vol. 25, pp. 456 -- 473, 1999.
4. J. Bevan, "Software Instability Analysis: Co-Change Analysis Across Configuration-Based Dependence Relationships." PhD Thesis: University of California, Santa Cruz, 2006.
5. J. Bevan and J. E. James Whitehead, "Identification of Software Instabilities," in Working Conference on Reverse Engineering, 2003, pp. 134--145.
6. A. B. Binkley and S. Schach, "Validation of the coupling dependency metric as a predictor of run-time failures and maintenance measures," in International Conference on Software Engineering, 1998, pp. 452 -- 455
7. D. Binkley and M. Harman, "An empirical study of predicate dependence levels and trends," in International Conference on Software Engineering 2003, pp. 330--339.
8. S. P. Borgatti, M. G. Everett, and L. C. Freeman, "Ucinet for Windows: Software for Social Network Analysis," Analytic Technologies, Harvard, MA, 2002.
9. L. Briand, P. Devanbu, and W. Melo, "An investigation into coupling measures for C++," in International Conference on Software Engineering Boston, Massachusetts, United States: ACM Press, 1997.
10. L. C. Briand, J. W. Daly, and J. Wüst, "A Unified Framework for Coupling Measurement in Object-Oriented Systems," IEEE Transactions on Software Engineering, vol. 25, pp. 91--121, 1999.
11. L. C. Briand, W. L. Melo, and J. Wüst, "Assessing the Applicability of Fault-Proneness Models Across Object-Oriented Software Projects," IEEE Transactions on Software Engineering, vol. 28, pp. 706--720, 2002.
12. C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph " Communications of the ACM, vol. 16, pp. 575--577, 1973.
13. R. Burt, Structural Holes: The Social Structure of Competition. Cambridge, MA: Harvard University Press, 1995.
14. J. Cho, H. Garcia-Molina, and L. Page, "Efficient crawling through URL ordering," in International Conference on World Wide Web Brisbane, Australia: Elsevier Science Publishers B. V., 1998.
15. N. Fenton and N. Ohlsson, "Quantitative analysis of faults and failures in a complex software system," IEEE Transactions on Software Engineering, vol. 26, pp. 797 -- 814 2000.
16. N. E. Fenton and S. L. Pfleeger, Software Metrics: A Rigorous and Practical Approach: Brooks/Cole, 1998.
17. J. Ferrante, K. J. Ottenstein, and J. D. Warren, "The program dependence graph and its use in optimization," ACM Transactions on Programming Languages and Systems, vol. 9, pp. 319 -- 349 1987.
18. R. A. Ghosh, "Clustering and dependencies in free/open source software development: Methodology and tools," First Monday, vol. 8, 2003.
19. R. A. Hanneman and M. Riddle, Introduction to social network methods. Riverside, CA: University of California, Riverside 2005.
20. A. E. Hassan and R. C. Holt, "The Small World of Software Reverse Engineering," in Working Conference on Reverse Engineering: IEEE Computer Society, 2004.
21. S. M. Henry and D. Kafura, "Software Structure Metrics based on Information Flow," IEEE Transactions on Software Engineering, vol. 7, pp. 510--518, 1981.
22. S.-K. Huang and K.-m. Liu, "Mining version histories to verify the learning process of Legitimate Peripheral Participants," in International Workshop on Mining Software Repositories, 2005.
23. E. J. Jackson, A Users Guide to Principal Components. Hoboken, NJ: John Wiley & Sons Inc., 2003.
24. A. J. Ko and B. A. Myers, "A framework and methodology for studying the causes of software errors in programming systems," Journal of Visual Languages & Computing, vol. 16, pp. 41--84, 2005.
25. B. Korel, "The program dependence graph in static program testing," Information Processing Letters, vol. 24, pp. 103--108, 1987.
26. Z. Li, L. Tan, X. Wang, S. Lu, Y. Zhou, and C. Zhai, "Have things changed now? An empirical study of bug characteristics in modern open source software," in Workshop on Architectural and System Support for Improving Software Dependability San Jose, California: ACM Press, 2006.
27. L. Lopez-Fernandez, G. Robles, and J. M. Gonzalez-Barahona, "Applying Social Network Analysis to the Information in CVS Repositories," in International Workshop on Mining Software Repositories, Edinburgh, Scotland, UK, 2004, pp. 101--105.
28. G. Madey, V. Freeh, and R. Tynan, "The open source software development phenomenon: An analysis based on social network theory," Americas Conference on Information Systems, 2002.
29. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network Motifs: Simple Building Blocks of Complex Networks," Science, vol. 298, pp. 824--827, October 25, 2002 2002.
30. K.-H. Möller and D. J. Paulish, "An empirical investigation of software fault distribution," in International Software Metrics Symposium, 1993, pp. 82--90.
31. J. Munson and T. Khoshgoftaar, "The Detection of Fault-Prone Programs," IEEE Transactions on Software Engineering, vol. 18, pp. 423--433, 1992.
32. N. Nagappan and T. Ball, "Use of Relative Code Churn Measures to Predict System Defect Density," in International Conference on Software Engineering, St. Louis, MO, 2005, pp. 284--292.
33. N. Nagappan and T. Ball, "Using Software Dependencies and Churn Metrics to Predict Field Failures: An Empirical Case Study," in International Symposium on Empirical Software Engineering and Measurement, 2007, pp. 364--373.
34. N. Nagappan, T. Ball, and B. Murphy, "Using Historical In-Process and Product Metrics for Early Estimation of Software Failures.," in International Symposium on Software Reliability Engineering, 2006, pp. 62--74.
35. N. Nagappan, T. Ball, and A. Zeller, "Mining metrics to predict component failures," in International Conference on Software Engineering, 2006, pp. 452--461.
36. N. J. D. Nagelkerke, "A note on a general definition of the coefficient of determination," Biometrika, vol. 78, pp. 691--692, 1991.
37. M. E. J. Newman, "The structure and function of complex networks," SIAM Review, vol. 45, pp. 167--456, 2003.
38. M. Ohira, N. Ohsugi, T. Ohoka, and K.-i. Matsumoto, "Accelerating cross-project knowledge collaboration using collaborative filtering and social networks," in International Workshop on Mining Software Repositories St. Louis, Missouri: ACM Press, 2005.
39. N. Ohlsson and H. Alberg, "Predicting fault-prone software modules in telephone switches," IEEE Transactions on Software Engineering, vol. 22, pp. 886 -- 894 1996.
40. A. Orso, S. Sinha, and M. J. Harrold, "Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging," ACM Transactions on Software Engineering and Methodology, vol. 13, pp. 199 -- 239 2004.
41. T. Ostrand, E. Weyuker, and R. M. Bell, "Predicting the location and number of faults in large software systems," IEEE Transactions on Software Engineering, vol. 31, pp. 340 -- 355 2005.
42. A. Pogdurski and L. A. Clarke, "A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance," IEEE Transactions on Software Engineering, vol. 16, pp. 965--979, 1990.
43. G. Sabidussi, "The centrality index of a graph," Psychometrika, vol. 31, pp. 581--603, 1966.
44. A. Schröter, T. Zimmermann, and A. Zeller, "Predicting Component Failures at Design Time," in International Symposium on Empirical Software Engineering Rio de Janeiro, Brazil, 2006.
45. S. Sinha, M. J. Harrold, and G. Rothermel, "Interprocedural control dependence," ACM Transactions on Software Engineering and Methodology, vol. 10, pp. 209 -- 254 2001.
46. A. Srivastava, T. J., and C. Schertz, "Efficient Integration Testing using Dependency Analysis," Microsoft Research-Technical Report, MSR-TR-2005-94, 2005.
47. R. Subramanyam and M. S. Krishnan, "Empirical Analysis of CK Metrics for Object-Oriented Design Complexity: Implications for Software Defects.," IEEE Transactions on Software Engineering, vol. 29, pp. 297--310, 2003.
48. G. Tassey, "The Economic Impacts of Inadequate Infrastructure for Software Testing," National Institute of Standards and Technology 2002.
49. S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1984.
50. T. Zimmermann and N. Nagappan, "Predicting Subsystem Defects using Dependency Graph Complexities," in International Symposium on Software Reliability Engineering Trollhättan, Sweden, 2007.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

      • System management

        • Quality assurance

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Reusability

        • Software product lines

    • Software verification and validation

      • Process validation

  • Software organization and properties

    • Extra-functional properties

      • Software performance