Clone detection using rolling hashing, suffix trees and dagification: a case study

TY - GEN

T1 - Clone detection using rolling hashing, suffix trees and dagification

T2 - 6th International Workshop on Software Clones

AU - Thomsen, Mikkel Jønsson

AU - Henglein, Fritz

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - Microsoft Dynamics NAV is a widely used enterprise resource planning system for small and medium-sized enterprises that, by design, encourages rapid customization by copy-paste programming. We report the results of analyzing clone detection for NAV using two previously published methods and one new algorithmic method: character-based sliding window sampling using Rabin-Karp hashing (MOSS), line-based sequence matching using suffix trees (CodeDup), and abstract-syntax-tree based graph sharing analysis (XMLClone). The latter is piggybacked on XMLStore, which stores XML trees as directed acyclic graphs (dags) where all isomorphic subtrees are identified and coalesced into single nodes, which can be done in linear time using multiset discrimination. This dagification discovers all well-formed Type-1 and, with suitable input normalization, Type-2 clones. We find that the subsequent dag analysis to discover Type-3 clones performs well on NAV source code, both in terms of computational complexity and precision. This suggests that efficient dagification and independently configurable dag interpretation may be valuable ingredients for modular clone detection.

AB - Microsoft Dynamics NAV is a widely used enterprise resource planning system for small and medium-sized enterprises that, by design, encourages rapid customization by copy-paste programming. We report the results of analyzing clone detection for NAV using two previously published methods and one new algorithmic method: character-based sliding window sampling using Rabin-Karp hashing (MOSS), line-based sequence matching using suffix trees (CodeDup), and abstract-syntax-tree based graph sharing analysis (XMLClone). The latter is piggybacked on XMLStore, which stores XML trees as directed acyclic graphs (dags) where all isomorphic subtrees are identified and coalesced into single nodes, which can be done in linear time using multiset discrimination. This dagification discovers all well-formed Type-1 and, with suitable input normalization, Type-2 clones. We find that the subsequent dag analysis to discover Type-3 clones performs well on NAV source code, both in terms of computational complexity and precision. This suggests that efficient dagification and independently configurable dag interpretation may be valuable ingredients for modular clone detection.

KW - XML

KW - cryptography

KW - directed graphs

KW - enterprise resource planning

KW - small-to-medium enterprises

KW - trees (mathematics)

KW - CodeDup

KW - MOSS

KW - Microsoft dynamics NAV

KW - Rabin-Karp hashing

KW - XML trees

KW - XMLClone

KW - abstract-syntax-tree

KW - character-based sliding window sampling

KW - copy-paste programming

KW - dagification

KW - directed acyclic graph

KW - enterprise resource planning system

KW - graph sharing analysis

KW - isomorphic subtrees

KW - line-based sequence matching

KW - linear time

KW - modular clone detection

KW - multiset discrimination

KW - rolling hashing

KW - small-and-medium-sized enterprises

KW - suffix trees

KW - Abstracts

KW - Calibration

KW - Cloning

KW - Plagiarism

KW - Syntactics

KW - Cod-eDup

KW - ERP

KW - MS Dynamics NAV

KW - XMLStore

KW - clone

KW - code

KW - detection

KW - discrimination

KW - hashing

KW - multiset

KW - similarity

KW - suffix

KW - tree

KW - winnowing

U2 - 10.1109/IWSC.2012.6227862

DO - 10.1109/IWSC.2012.6227862

M3 - Article in proceedings

SN - 978-1-4673-1794-8

SP - 22

EP - 28

BT - 2012 6th International Workshop on Software Clones (IWSC)

PB - IEEE

Y2 - 4 June 2012 through 4 June 2012

ER -