## 6 Related Work  
There are, at present, six types of clone detection techniques: text-based, token-based, tree-based, PDG-based, matrix-based, and machine learning-based. A text-based clone detection technique treats the code as text and detects clones through direct comparison of code fragments. For example, _Dup_, a text-based and line-based clone detection tool, uses a parameterized matching algorithm [3], and [PERSON] [25] uses a Karp-Rabin string matching approach. These text-based techniques can find clones simply and quickly but are not capable of detecting clones that are not completely or near identical to the source code. Token-based clone detection transforms the entire code into a sequence of tokens and then compares the sequences. CCFinder [26], for example, lexes, parses, and transforms identifiers related to variables, constants, and user-defined types into a sequence of tokens. CCFinder detects clones, even if only identifiers have been changed. CCFinder cannot detect clones, however, where the order of sentences has been modified or new code has  
Figure 7: Example of ST3 clone classified as MT3 clone. been inserted. To overcome this limitation, a different token-based clone detection tool, CP-Miner [7], uses frequent pattern mining. CP-Miner can detect one or two code lines that have been inserted, deleted, or modified, but it is still unable to detect cloned codes where more extensive code modifications have been made. Tree-based clone detection techniques seek to overcome the limitations of text-based techniques by converting code to AST and then using tree matching algorithms to detect clones. CloneDR [27] transforms AST to hash values via hash functions and then detects clones by comparing subtrees with the same hash value. [PERSON] et al. [28] have proposed a technique for clone detection using frequent pattern mining techniques based on AST expressed in XML. [PERSON] and [PERSON] [29] have suggested a technique to detect clones using AST's subtree where a particular pattern appears. While researchers have worked hard to refine these tree-based clone detection techniques, clone detection remains complicated in situations where two code fragments have different orders. An alternative technique for detecting clones, including differently ordered statements, newly inserted statements, or removed statements, are PDG-based techniques. PDG-based techniques detect clones by matching PDGs that contain data flow and control flow information of a code fragment. The most well-known PDG-based clone detection technique is PDG-DUP, proposed by [PERSON] and [PERSON] [30]. PDG-DUP finds identical PDG subgraphs using program slicing. [PERSON] [31] uses k-length patch matching to identify maximally similar subgraphs in PDGs. While PDG-based clone detection techniques overcome the limitations of the text-based, token-based, and tree-based techniques, this technique does not scale well to large-scale systems, as matching PDG subgraphs takes a while. Metric-based clone detection techniques refer to various metric values derived from code for clone detection. Metrics are typically calculated from classes, techniques, and statements using fingerprinting algorithms. [PERSON] et al. [32] transformed each function of source code to Intermediate Presentation Language (IRL) to calculate metrics values from the names, layout, expression, and control flow of functions. A pair of functions that has similar metric values is detected as a clone. Another metric-based clone detection technique proposed by [PERSON] et al. [4] computes metric values that capture the data and control flow properties of source code. The technique annotates metric values to corresponding nodes of AST constructed from source code and detects clones by comparing the distances between annotated metric values of code fragment pairs using dynamic programming approach. Since metric-based techniques do not utilize the code itself, this method may be less precise than others, as two different codes with similar metric values may be identified as clones.