Detecting higher-level similarity patterns in programs

ABSTRACT

Cloning in software systems is known to create problems during software maintenance. Several techniques have been proposed to detect the same or similar code fragments in software, so-called simple clones. While the knowledge of simple clones is useful, detecting design-level similarities in software could ease maintenance even further, and also help us identify reuse opportunities. We observed that recurring patterns of simple clones - so-called structural clones - often indicate the presence of interesting design-level similarities. An example would be patterns of collaborating classes or components. Finding structural clones that signify potentially useful design information requires efficient techniques to analyze the bulk of simple clone data and making non-trivial inferences based on the abstracted information. In this paper, we describe a practical solution to the problem of detecting some basic, but useful, types of design-level similarities such as groups of highly similar classes or files. First, we detect simple clones by applying conventional token-based techniques. Then we find the patterns of co-occurring clones in different files using the Frequent Itemset Mining (FIM) technique. Finally, we perform file clustering to detect those clusters of highly similar files that are likely to contribute to a design-level similarity pattern. The novelty of our approach is application of data mining techniques to detect design level similarities. Experiments confirmed that our method finds many useful structural clones and scales up to big programs. The paper describes our method for structural clone detection, a prototype tool called Clone Miner that implements the method and experimental results.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, The Enhanced Suffix Array and Its Applications to Genome Analysis, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.449-463, September 17-21, 2002
• 2: Mohamed Ibrahim Abouelhoda , Enno Ohlebusch , Stefan Kurtz, Optimal Exact Strring Matching Based on Suffix Arrays, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.31-43, September 11-13, 2002
• 3: ANTLR website at http://www.antlr.org
• 4: Hamid Abdul Basit , Damith C. Rajapakse , Stan Jarzabek, Beyond templates: a study of clones in the STL and some general implications, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062537]
• 5: 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
• 6: 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]
• 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: Ted J. Biggerstaff, Design Recovery for Maintenance and Reuse, Computer, v.22 n.7, p.36-49, July 1989 [doi>10.1109/2.30731 ]
• 9: E. Buss , R. De Mori , W. M. Gentleman , J. Henshaw , H. Johnson , K. Kontogiannis , E. Merlo , H. A. Müller , J. Mylopoulos , S. Paul , A. Prakash , M. Stanley , S. R. Tilley , J. Troster , K. Wong, Investigating reverse engineering technologies for the CAS program understanding project, IBM Systems Journal, v.33 n.3, p.477-500, July 1994
• 10: Case Study: eliminating redundant codes in the Buffer library. At XVCL Website, http://xvcl.comp.nus.edu.sg/xvcl/buffer/index.htm
• 11: Church, K. W. and Helfman, J. I. Dotplot: A program for exploring self-similarity in million of lines of text and code. Journal of Computational and Graphical Statistics, June 1993, 2(2):153--174.
• 12: Davey, N., Barson, P., Field, S., Frank, R., and Tansley, D. The development of a software clone detector. International Journal of Applied Software Technology, 1(3-4): 219--236, 1995.
• 13: Stéphane Ducasse , Matthias Rieger , Serge Demeyer, A Language Independent Approach for Detecting Duplicated Code, Proceedings of the IEEE International Conference on Software Maintenance, p.109, August 30-September 03, 1999
• 14: Martin Fowler, Analysis patterns: reusable objects models, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 15: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 16: Grahne, G., and Zhu, J., Efficiently Using Prefix-trees in Mining Frequent Itemsets. In Proceeding of the First IEEE ICDM Workshop on Frequent Itemset Mining Implementations (FIMI'03), Melbourne, FL, Nov 2003.
• 17: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 18: 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
• 19: Java Technology at http://java.sun.com/
• 20: J. Howard Johnson, Identifying redundancy in source code using fingerprints, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
• 21: J. Howard Johnson, Substring Matching for Clone Detection and Change Tracking, Proceedings of the International Conference on Software Maintenance, p.120-126, September 01, 1994
• 22: 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 ]
• 23: Karkkainen, J., and Sanders, P. Simple linear work suffix array construction. In Proc. 30th Internat. Colloq. Automata, Languages & Programming (2003) 943--955.
• 24: Toru Kasai , Gunho Lee , Hiroki Arimura , Setsuo Arikawa , Kunsoo Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.181-192, July 01-04, 2001
• 25: Andrew Kennedy , Don Syme, Design and implementation of generics for the .NET Common language runtime, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.1-12, June 2001, Snowbird, Utah, United States
• 26: Kim, D.K., Sim, J.S., Park, H., and Park, K. Linear-time construction of suffix arrays. In Proc. Fourteenth Annual Symp. Combinatorial Pattern Matching (2003) 186--199.
• 27: Ko, P., and Aluru, S. Space efficient linear time construction of suffix arrays. In Proc. Fourteenth Annual Symp. Combinatorial Pattern Matching (2003) 200--210.
• 28: Kontogiannis, K.A., De Mori, R., Merlo, E., Galler, M., and Bernstein, M. Pattern Matching for Clone and Concept Detection. J. Automated Software Eng., vol. 3, pp. 770--108, 1996.
• 29: 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
• 30: 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
• 31: Larsson, N.J., and Sadakane, K. Faster Suffix Sorting. Technical Report LU-CS-TR:99-214, Lund University (1999) 20 pp.
• 32: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 33: 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
• 34: Tadeusz Morzy , Marek Wojciechowski , Maciej Zakrzewicz, Pattern-Oriented Hierachical Clustering, Proceedings of the Third East European Conference on Advances in Databases and Information Systems, p.179-190, September 13-16, 1999
• 35: Morzy, T., Wojciechowski, M., and Zakrzewicz, M. Web Users Clustering. In Proc. of the 15th International Symposium on Computer and Information Sciences, Istanbul, Turkey, 2000, pages 374--382.
• 36: Tadeusz Morzy , Marek Wojciechowski , Maciej Zakrzewicz, Scalable Hierarchical Clustering Method for Sequences of Categorical Values, Proceedings of the 5th Pacific-Asia Conference on Knowledge Discovery and Data Mining, p.282-293, April 16-18, 2001
• 37: David Lorge Parnas, Software aging, Proceedings of the 16th international conference on Software engineering, p.279-287, May 16-21, 1994, Sorrento, Italy
• 38: Simon J. Puglisi , William F. Smyth , Andrew Turpin, The Performance of Linear Time Suffix Sorting Algorithms, Proceedings of the Data Compression Conference, p.358-367, March 29-31, 2005 [doi>10.1109/DCC.2005.87]
• 39: Ryan, A. P. J., Smyth, W. F., Turpin, A., and Xiaoyang Y. New suffix array algorithms -- linear but not fast? In Proc. 15th Australasian Workshop on Combinatorial Algorithms, Seok-Hee Hong (ed.) (2004) 148--156.
• 40: K. Sadakane, A Fast Algorithms for Making Suffix Arrays and for Burrows-Wheeler Transformation, Proceedings of the Conference on Data Compression, p.129, March 30-April 01, 1998
• 41: Ian Sommerville, Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 42: XVCL website at : http://xvcl.comp.nus.edu.sg/overview_brochure.php

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Design

Keywords:
clone detection, similarity patterns, software clones