Context-based detection of clone-related bugs

ABSTRACT

Studies show that programs contain much similar code, commonly known as clones. One of the main reasons for introducing clones is programmers' tendency to copy and paste code to quickly duplicate functionality. We commonly believe that clones can make programs difficult to maintain and introduce subtle bugs. Although much research has proposed techniques for detecting and removing clones to improve software maintainability, little has considered how to detect latent bugs introduced by clones. In this paper, we introduce a general notion of context-based inconsistencies among clones and develop an efficient algorithm to detect such inconsistencies for locating bugs. We have implemented our algorithm and evaluated it on large open source projects including the latest versions of the Linux kernel and Eclipse. We have discovered many previously unknown bugs and programming style issues in both projects (with 57 for the Linux kernel and 38 for Eclipse). We have also categorized the bugs and style issues and noticed that they exhibit diverse characteristics and are difficult to detect with any single existing bug detection technique. We believe that our approach complements well these existing techniques.

REFERENCES

• 1: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 2: B. S. Baker, On finding duplication and near-duplication in large software systems, Proceedings of the Second Working Conference on Reverse Engineering, p.86, July 14-16, 1995
• 3: Brenda S. Baker, Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal on Computing, v.26 n.5, p.1343-1362, Oct. 1997 [doi>10.1137/S0097539793246707]
• 4: Thomas Ball , Sriram K. Rajamani, The SLAM project: debugging system software via static analysis, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-3, January 16-18, 2002, Portland, Oregon
• 5: Hamid Abdul Basit , Stan Jarzabek, Detecting higher-level similarity patterns in programs, 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
• 6: Ira D. Baxter , Christopher Pidgeon , Michael Mehlich, DMS®: Program Transformations for Practical Scalable Software Evolution, Proceedings of the 26th International Conference on Software Engineering, p.625-634, May 23-28, 2004
• 7: Ira D. Baxter , Andrew Yahin , Leonardo Moura , Marcelo Sant'Anna , Lorraine Bier, Clone Detection Using Abstract Syntax Trees, Proceedings of the International Conference on Software Maintenance, p.368, March 16-19, 1998
• 8: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 10: Isil Dillig , Thomas Dillig , Alex Aiken, Static error detection using semantic inconsistency inference, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 11: 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
• 12: 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]
• 13: Cormac Flanagan , K. Rustan M. Leino , Mark Lillibridge , Greg Nelson , James B. Saxe , Raymie Stata, Extended static checking for Java, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 14: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar , Grégoire Sutre, Lazy abstraction, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.58-70, January 16-18, 2002, Portland, Oregon
• 15: Stan Jarzabek , Paul Bassett , Hongyu Zhang , Weishan Zhang, XVCL: XML-based variant configuration language, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 16: Stan Jarzabek , Li Shubiao, Eliminating redundancies with a "composition with adaptation" meta-programming technique, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 17: Lingxiao Jiang , Ghassan Misherghi , Zhendong Su , Stephane Glondu, DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proceedings of the 29th international conference on Software Engineering, p.96-105, May 20-26, 2007 [doi>10.1109/ICSE.2007.30]
• 18: Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480]
• 19: Cory Kapser , Michael W. Godfrey, "Cloning Considered Harmful" Considered Harmful, Proceedings of the 13th Working Conference on Reverse Engineering, p.19-28, October 23-27, 2006 [doi>10.1109/WCRE.2006.1]
• 20: Miryung Kim , Vibha Sazawal , David Notkin , Gail Murphy, An empirical study of code clone genealogies, 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
• 21: Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
• 22: Ted Kremenek , Paul Twohey , Godmar Back , Andrew Ng , Dawson Engler, From uncertainty to belief: inferring the specification within, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 23: 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
• 24: Bruno Lague , Daniel Proulx , Jean Mayrand , Ettore M. Merlo , John Hudepohl, Assessing the Benefits of Incorporating Function Clone Detection in a Development Process, Proceedings of the International Conference on Software Maintenance, p.314, October 01-03, 1997
• 25: Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: a tool for finding copy-paste and related bugs in operating system code, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.20-20, December 06-08, 2004, San Francisco, CA
• 26: 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
• 27: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 28: Damith C. Rajapakse , Stan Jarzabek, Using Server Pages to Unify Clones in Web Applications: A Trade-Off Analysis, Proceedings of the 29th international conference on Software Engineering, p.116-126, May 20-26, 2007 [doi>10.1109/ICSE.2007.95]
• 29: Vera Wahler , Dietmar Seipel , Jurgen Wolff v. Gudenberg , Gregor Fischer, Clone Detection in Source Code by Frequent Itemset Techniques, Proceedings of the Source Code Analysis and Manipulation, Fourth IEEE International Workshop, p.128-135, September 15-16, 2004 [doi>10.1109/SCAM.2004.5]
• 30: Yichen Xie , Alex Aiken, Scalable error detection using boolean satisfiability, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.351-363, January 12-14, 2005, Long Beach, California, USA
• 31: Yichen Xie , Dawson Engler, Using redundancies to find errors, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587060]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Code inspections and walk-throughs

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

General Terms:
Experimentation, Reliability

Keywords:
code clone detection, code clone-related bugs, context-based bug detection, inconsistencies