Finding what's not there: a new approach to revealing neglected conditions in software

ABSTRACT

Neglected conditions are an important but difficult-to-find class of software defects. This paper presents a novel approach to revealing neglected conditions that integrates static program analysis and advanced data mining techniques to discover implicit conditional rules in a code base and to discover rule violations that indicate neglected conditions. The approach requires the user to indicate minimal constraints on the context of the rules to be sought, rather than specific rule templates. To permit this generality, rules are modeled as graph minors of program dependence graphs, and both frequent itemset mining and frequent subgraph mining algorithms are employed to identify candidate rules. We report the results of an empirical evaluation of the approach in which it was used to discover conditional rules and neglected conditions in ~25,000 lines of source code.

REFERENCES

• 1: Apache.org. Apache HTTP Server Project. www.apache.org.
• 2: Timothy A. Budd , Richard A. DeMillo , Richard J. Lipton , Frederick G. Sayward, Theoretical and empirical studies on using program mutation to test the functional correctness of programs, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.220-233, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567468]
• 3: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 4: Benjamin Chelf , Dawson Engler , Seth Hallem, How to write system-specific, static checkers in metal, Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.51-60, November 18-19, 2002, Charleston, South Carolina, USA
• 5: Chockler, H., Kupferman, O., and Vardi, M. Coverage metrics for formal verification. Lecture Notes in Computer Science 2860, Springer, 2003, pp. 111--125.
• 6: Alastair Dunsmore , Marc Roper , Murray Wood, Practical Code Inspection Techniques for Object-Oriented Systems: An Experimental Comparison, IEEE Software, v.20 n.4, p.21-29, July 2003 [doi>10.1109/MS.2003.1207450]
• 7: Dawson Engler , David Yu Chen , Seth Hallem , Andy Chou , Benjamin Chelf, Bugs as deviant behavior: a general approach to inferring errors in systems code, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 8: Engler, D. Meta-level compilation. metacomp.stanford.edu.
• 9: M. E. Fagan, Design and code inspections to reduce errors in program development, IBM Systems Journal, v.38 n.2-3, p.258-287, 1999
• 10: Giuseppe Di Fatta , Stefan Leue , Evghenia Stegantova, Discriminative pattern mining in software fault detection, Proceedings of the 3rd international workshop on Software quality assurance, November 06-06, 2006, Portland, Oregon [doi>10.1145/1188895.1188910]
• 11: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 12: Festa, P. Study says buffer overflow is most common security bug. C|Net News.com. news.com.com/2100-1001-233483.html.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Grammatech. CodeSurfer. www.grammatech.com/products/codesurfer/overview.html.
• 15: Grammatech. Dependence graphs and program slicing. www.grammatech.com/research/slicing/slicingWhitepaper
• 16: Holder, L. B., Cook, D. J., and Djoko, S. Substructure discovery in the SUBDUE system. AAAI Workshop on Knowledge Discovery in Databases, 1994, 169--180.
• 17: Michael Howard , David E. Leblanc, Writing Secure Code, Microsoft Press, Redmond, WA, 2002
• 18: Howden, W. Reliability of the path analysis testing strategy. IEEE Trans. on Softw. Eng., SE-2, Sept. 1976, pp. 208--215.
• 19: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 20: Jun Huan , Wei Wang , Jan Prins , Jiong Yang, SPIN: mining maximal frequent subgraphs from graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014123]
• 21: IBM. Orthogonal defect classification. Center for Software Eng., www.research.ibm.com/softeng/ODC/ODC.HTM.
• 22: Jens Krinke, Identifying Similar Code with Program Dependence Graphs, Proceedings of the Eighth Working Conference on Reverse Engineering (WCRE'01), p.301, October 02-05, 2001
• 23: Kuramochi, M. and Karypis, G. Finding frequent patterns in a large sparse graph. Technical Report #03-038, Dept. of Computer Sci. and Eng., Univ. of Minnesota.
• 24: Kuramochi, M. and Karypis, G. GREW: A Scalable Frequent Subgraph Discovery Algorithm. Technical Report #TR 04-024, CSE Dept., Univ. of Minnesota.
• 25: Zhenmin Li , Yuanyuan Zhou, PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 26: Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: Finding Copy-Paste and Related Bugs in Large-Scale Software Code, IEEE Transactions on Software Engineering, v.32 n.3, p.176-192, March 2006 [doi>10.1109/TSE.2006.28]
• 27: Chao Liu , Chen Chen , Jiawei Han , Philip S. Yu, GPLAG: detection of software plagiarism by program dependence graph analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150522]
• 28: Benjamin Livshits , Thomas Zimmermann, DynaMine: finding common error patterns by mining software revision histories, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 29: Stuart McClure , Joel Scambray , George Kurtz, Hacking Exposed: Network Security Secrets and Solutions,Third Edition, McGraw-Hill Professional, 2001
• 30: Glenford J. Myers, A controlled experiment in program testing and code walkthroughs/inspections, Communications of the ACM, v.21 n.9, p.760-768, Sept. 1978 [doi>10.1145/359588.359602]
• 31: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 32: Mozilla.org. Bugzilla. https://bugzilla.mozilla.org/.
• 33: NIST. National Vulnerability Database. http://nvd.nist.gov/.
• 34: Shruti Raghavan , Rosanne Rohana , David Leon , Andy Podgurski , Vinay Augustine, Dex: A Semantic-Graph Differencing Tool for Studying Changes in Large Code Bases, Proceedings of the 20th IEEE International Conference on Software Maintenance, p.188-197, September 11-14, 2004
• 35: Renieres, M. and Reiss, S. P. Fault localization with nearest neighbor queries. 18th International Conference on Automated Software Engineering (Oct. 2003), pp. 30--39.
• 36: Richardson, D. J. and Clarke, L. A. Partition analysis: a method combining testing and verification. IEEE Trans. on Softw. Eng., SE-11, 12 (Dec. 1985), 1477--1490.
• 37: Robertson, N. and Seymour, P. D. Graph Minors. I. Excluding a forest. Journal of Combinatorial Theory, Series B 35 (1), 1983, 39--61.
• 38: Ian Sommerville , Peter Sawyer , Stephen Viller, Viewpoints for Requirements Elicitation: A Practical Approach, Proceedings of the 3rd International Conference on Requirements Engineering: Putting Requirements Engineering to Practice, p.74-81, April 06-10, 1998
• 39: Thayer, T. A., Lipow, M., and Nelson, E. C. Software reliability study. TRW-SS-76-03, Redondo Beach, California, TRW, March 1976.
• 40: Lini T. Thomas , Satyanarayana R. Valluri , Kamalakar Karlapalem, MARGIN: Maximal Frequent Subgraph Mining, Proceedings of the Sixth International Conference on Data Mining, p.1097-1101, December 18-22, 2006 [doi>10.1109/ICDM.2006.102]
• 41: Wilander, J. and Fak, P. Rule Matching Security Properties of Code using Dependence Graphs. 1st Intl. Workshop on Code Based Software Security Assessments (Pittsburgh, PA, November 2005).
• 42: Chadd C. Williams , Jeffrey K. Hollingsworth, Automatic Mining of Source Code Repositories to Improve Bug Finding Techniques, IEEE Transactions on Software Engineering, v.31 n.6, p.466-480, June 2005 [doi>10.1109/TSE.2005.63]
• 43: Jeannette M. Wing , Mandana Vaziri-Farahani, Model checking software systems: a case study, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.128-139, October 12-15, 1995, Washington, D.C., United States
• 44: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 45: Zhang, S., Yang, J., and Cheedella, V. Monkey: Approximate Graph Mining Based on Spanning Trees, to appear in ICDE, April 2007, Istanbul, Turkey.
• 46: Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997 [doi>10.1145/267580.267590]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Keywords:
automatic defect detection, frequent itemset mining, frequent subgraph mining, mining software repositories, program dependences