Making Software

Detecting Clones in Software

The problem of detecting code clones is an interesting one technically; if an existing code fragment is duplicated and then changed to fit a new purpose, how can you recognize this with an automated tool? If all code clones were verbatim copies that were never subsequently altered—and some clones do fit this description—then code clone detection would be pretty easy. However, usually clones are adapted for new uses: existing lines are changed or removed, and new code may be added. Thus, it’s probably a good idea to pause at this point and ask the question: just what is a software clone?

Well, first we should note that almost all clone detection techniques actually measure similarity of code chunks. That is, we typically don’t have access to logs that record actual copy-paste edit events; we just infer they happened if the similarity measures are within a given threshold.

Second, there is no consensus on what similarity means concretely or what thresholds are reasonable. (Ira Baxter, a researcher in the community, likes to say, “Software clones are segments of code that are similar…according to some definition of similarity.”) Detection tools use a wide variety of techniques. Some tools treat programs as a sequence of character strings, and perform textual comparisons. Other tools compare token streams, abstract syntax trees (ASTs), and program dependence graphs (PDGs). Some compute metrics or compare lightweight semantic models of program components. And ...