Automatic mining of functionally equivalent code fragments via random testing

ABSTRACT

Similar code may exist in large software projects due to some common software engineering practices, such as copying and pasting code and n-version programming. Although previous work has studied syntactic equivalence and small-scale, coarse-grained program-level and function-level semantic equivalence, it is not known whether significant fine-grained, code-level semantic duplications exist. Detecting such semantic equivalence is also desirable because it can enable many applications such as code understanding, maintenance, and optimization.

In this paper, we introduce the first algorithm to automatically mine functionally equivalent code fragments of arbitrary size - down to an executable statement. Our notion of functional equivalence is based on input and output behavior. Inspired by Schwartz's randomized polynomial identity testing, we develop our core algorithm using automated random testing: (1) candidate code fragments are automatically extracted from the input program; and (2) random inputs are generated to partition the code fragments based on their output values on the generated inputs. We implemented the algorithm and conducted a large-scale empirical evaluation of it on the Linux kernel 2.6.24. Our results show that there exist many functionally equivalent code fragments that are syntactically different (i.e., they are unlikely due to copying and pasting code). The algorithm also scales to million-line programs; it was able to analyze the Linux kernel with several days of parallel processing.

REFERENCES

• 1: 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
• 2: 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]
• 3: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• 4: 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
• 5: 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
• 6: Boris Beizer, Software Testing Techniques, John Wiley & Sons, Inc., New York, NY, 1990
• 7: M. Bertran, F.-X. Babot, and A. Climent. An input/output semantics for distributed program equivalence reasoning. Electr. Notes Theor. Comput. Sci, 137(1):25--46, 2005.
• 8: David L Bird , Carlos Urias Munoz, Automatic generation of random self-checking test cases, IBM Systems Journal, v.22 n.3, p.229-245, 1983
• 9: Christian Collberg , Clark Thomborson, Software watermarking: models and dynamic embeddings, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-324, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292569]
• 10: G. Cousineau and P. Enjalbert. Program equivalence and provability. In MFCS: Symposium on Mathematical Foundations of Computer Science, 1979.
• 11: Roy L. Crole , Andrew D. Gordon, A Sound Metalogical Semantics for Input/Output Effects, Selected Papers from the 8th International Workshop on Computer Science Logic, p.339-353, September 25-30, 1994
• 12: 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
• 13: 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
• 14: Mark Gabel , Lingxiao Jiang , Zhendong Su, Scalable detection of semantic clones, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368132]
• 15: Patrice Godefroid , Nils Klarlund , Koushik Sen, DART: directed automated random testing, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 16: A. Groce and R. Joshi. Exploiting traces in program analysis. In TACAS, volume 3920 of LNCS, pages 379--393. Springer, 2006.
• 17: Hyun-il Lim , Heewan Park , Seokwoo Choi , Taisook Han, Detecting Theft of Java Applications via a Static Birthmark Based on Weighted Stack Patterns, IEICE - Transactions on Information and Systems, v.E91-D n.9, p.2323-2332, September 2008 [doi>10.1093/ietisy/e91-d.9.2323]
• 18: 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]
• 19: Lingxiao Jiang , Zhendong Su , Edwin Chiu, Context-based detection of clone-related bugs, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287634]
• 20: 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]
• 21: 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
• 22: 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
• 23: K. A. Kontogiannis , R. Demori , E. Merlo , M. Galler , M. Bernstein, Pattern matching for clone and concept detection, Reverse engineering, Kluwer Academic Publishers, Norwell, MA, 1996
• 24: 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
• 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: Jean Mayrand , Claude Leblanc , Ettore Merlo, Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics, Proceedings of the 1996 International Conference on Software Maintenance, p.244, November 04-08, 1996
• 27: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 28: Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 29: A. Jefferson Offutt , J. Huffman Hayes, A semantic model of program faults, Proceedings of the 1996 ACM SIGSOFT international symposium on Software testing and analysis, p.195-200, January 08-10, 1996, San Diego, California, United States
• 30: Andrew M. Pitts, Operational Semantics and Program Equivalence, Applied Semantics, International Summer School, APPSEM 2000, Caminha, Portugal, September 9-15, 2000, Advanced Lectures, p.378-412, September 09-15, 2000
• 31: Jean-Claude Raoult , Jean Vuillemin, Operational and Semantic Equivalence Between Recursive Programs, Journal of the ACM (JACM), v.27 n.4, p.772-796, Oct. 1980 [doi>10.1145/322217.322229]
• 32: David Schuler , Valentin Dallmeier , Christian Lindig, A dynamic birthmark for java, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321672]
• 33: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 34: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, 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
• 35: 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]
• 36: Bin Xin , Xiangyu Zhang, Efficient online detection of dynamic control dependence, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273489]
• 37: Vladimir A. Zakharov, To the Functional Equivalence of Turing Machines, Proceedings of the International Conference on Fundamentals of Computation Theory, p.488-491, June 22-26, 1987
• 38: Xiaoming Zhou , Xingming Sun , Guang Sun , Ying Yang, A Combined Static and Dynamic Software Birthmark Based on Component Dependence Graph, Proceedings of the 2008 International Conference on Intelligent Information Hiding and Multimedia Signal Processing, p.1416-1421, August 15-17, 2008 [doi>10.1109/IIH-MSP.2008.145]
• 39: R. Zippel, An explicit separation of relativised random polynomial time and relativised deterministic polynomial time, Information Processing Letters, v.33 n.4, p.207-212, December 1989 [doi>10.1016/0020-0190(89)90143-9]

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: Diagnostics
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering
      D.2.m Miscellaneous

General Terms:
Algorithms, Experimentation

Keywords:
code clones, functional equivalence, random testing