How Code Similarity Detection Moved From Text to Trees

In the spring of 1976, two researchers at Bell Labs published a technical report describing how to compute the longest common subsequence of two files and print the differences. diff was written for patch sets, not for grading. Within a few years instructors were piping student submissions through it anyway, which is more or less where the history of code similarity detection begins.

Fifty years on, code similarity detection is a stack of five distinct generations: character-level diffing, token streams, sampled fingerprints, syntax trees and program graphs, and learned vector representations. Each generation exists because the previous one could be defeated by a student with a text editor and twenty minutes. The interesting part of the story is not who shipped what first. It's what each layer can and cannot see.

Every detector is a specific answer to one question: what do you throw away before you compare?

The four clone types that define the whole field

Roy and Cordy's 2007 survey gave the field its working vocabulary, and it is still the fastest way to understand why one tool reports 94% on a pair that another tool scores at 11%. They sorted duplicated code into four buckets, and almost every design decision in every detector since maps onto which bucket it targets.

Type	What changed	Typical example	First generation that handles it
1	Nothing except whitespace and comments	Copy, paste, reindent	Character diff (1976)
2	Identifier and literal names	Rename total to acc, change loop variable	Token streams (1992)
3	Structure, with edits	Reorder statements, add a null check, merge two loops	AST and graph matching (1998)
4	Algorithm, not text	Recursive rewrite of an iterative method	Partially, with embeddings (2016 onward)

Type 3 and Type 4 are where tools diverge, and where the pedagogical argument actually lives. A detector that only sees Types 1 and 2 will hand you a clean-looking report on a straight copy and a boring 12% on a lightly rewritten one. That's the exact failure mode that makes a TA stop trusting the tool and go back to reading submissions by hand at midnight.

Generation one, characters (1976-1991)

Hunt and McIlroy's diff reduced comparison to a well-understood problem: find the longest common subsequence of two byte strings, then invert it to get the edit script. Myers formalized the O(ND) variant in 1986, and that algorithm is still what git diff runs today, layered with heuristics. For source code, the appeal was obvious. No parser, no language support matrix, no configuration. Just two text files and a number.

The number was the problem. Take this method:

public static int sumEven(int[] values) {
    int total = 0;
    for (int v : values) {
        if (v % 2 == 0) {
            total += v;
        }
    }
    return total;
}

And this one, which a student produced by renaming every identifier and running an auto-formatter set to Allman braces:

public static int addEvens( int[] nums )
{
  int acc = 0 ;
  for( int item : nums ) { if( item % 2 == 0 ) { acc += item ; } }
  return acc ;
}

Feed both to Python's difflib.SequenceMatcher with autojunk=False and you get a ratio around 0.61. The two methods are semantically identical. The tool reports them as 61% similar, which in a report full of legitimate 40% pairs reads as "probably fine, ignore it." Meanwhile a completely honest submission that happens to share a boilerplate main with eight classmates lands in the same band. Character comparison doesn't measure semantics. It measures how many bytes the two strings happen to share, which is a proxy that breaks the moment whitespace is in play.

There's a second, subtler failure. diff is a whole-file algorithm. It wants to produce one edit script covering the entire input. Plagiarism is not one edit script. A pair of submissions can contain a shared 80-line helper that was pasted wholesale and 400 lines of genuinely independent work, and a single global LCS ratio will average that away into a meaningless 34%.

Generation two, tokens and tiling (1992-1999)

Brenda Baker's 1992 parameterized matching work, and her 1995 dup system, made the first real conceptual jump: stop comparing characters, compare a normalized token stream. Rename a variable and the token stream is unchanged if you collapse identifiers to a placeholder. Reformat and the stream is unchanged if you drop whitespace tokens. That's Type 2 cloning, solved by construction, eight years before the commercial tools caught up.

The normalization step is where all the subtlety lives. Here's the idea in Python, since tokenize ships in the standard library and makes the mechanism visible:

import io, tokenize

KEYWORDS = {"if", "else", "for", "while", "return", "def", "class", "in", "not"}

def token_stream(src):
    out = []
    for tok in tokenize.generate_tokens(io.StringIO(src).readline):
        if tok.type in (tokenize.COMMENT, tokenize.NL, tokenize.NEWLINE,
                        tokenize.INDENT, tokenize.DEDENT):
            continue
        if tok.type == tokenize.NAME and tok.string not in KEYWORDS:
            out.append("ID")
        elif tok.type == tokenize.NUMBER:
            out.append("NUM")
        elif tok.type == tokenize.STRING:
            out.append("STR")
        else:
            out.append(tok.string)
    return out

Run that over both Java methods above (transliterated, since the same collapse applies) and the two streams become identical. The similarity jumps from 0.61 to 1.00 and stays there. That's the whole trick, and it has been the whole trick for thirty-three years.

Matching also changed. Michael Wise's 1993 greedy string tiling, later packaged as YAP3 in 1996, replaced global LCS with a local search: find the longest common token run, mark those tokens as used, repeat on what's left. That handles the pasted-helper-inside-original-work case that diff couldn't. It produces a list of matched regions rather than a single number, which is also the first time a tool could show evidence a human would accept.

The metrics branch ran in parallel. Mayrand, Leblanc and Merlo's 1996 paper measured function clones by extracting Halstead-style vectors and control-flow features per function, then comparing vectors. It worked on large industrial code and it was fast, but it produced a scalar, and a scalar is not evidence. You cannot sit a student down and say "this number is 0.87, please explain yourself."

One warning from that era, learned painfully by anyone who has written a normalizer. Collapsing every numeric literal to a single token is tempting and wrong. Every submission containing a 0 and a 1 then shares those tokens, and a cohort of entirely independent intro assignments picks up a baseline similarity floor of a few percent that you then have to explain to a department committee. Normalize identifiers, yes. Be much more careful with literals.

Generation three, fingerprints at scale (2003)

The problem with pairwise comparison is combinatorics. Six hundred submissions in a course is 179,700 pairs. Token-level greedy tiling on 179,700 pairs is not something you finish between the due date and the grading deadline.

Schleimer, Wilkerson and Aiken's 2003 SIGMOD paper on winnowing is the hinge point of the whole field, and it's worth understanding mechanically because most modern detectors including MOSS still run a variant of it. The idea: hash every k-gram of the token stream, then select only some of those hashes as document fingerprints, using a rule that guarantees you keep at least one hash from every window of w consecutive k-grams. Their rule is simple. In each window, take the minimum hash.

def winnow(hashes, w):
    picked = set()
    for i in range(len(hashes) - w + 1):
        window = hashes[i:i + w]
        m = min(window)
        picked.add((m, i + window.index(m)))
    return picked

The guarantee that makes this usable for grading is precise: any shared run of tokens of length at least k + w - 1 will contribute at least one shared fingerprint. Not "usually." Will. You can tune sensitivity by adjusting k and w, and you know exactly what you're trading away. With k=20 and w=8, nothing shorter than a 27-token shared run will surface, which filters out idiom noise like for (int i = 0; i < n; i++) while still catching a copied method.

MOSS (Measure Of Software Similarity) put that algorithm behind an email-based submission script that academia then used, largely unchanged, for two decades. Its limitations are historical rather than algorithmic. The corpus is whatever you submit, so it has no idea that the same code exists in a GitHub repository. There is no report UI, only an HTML page of matched regions. There's no concept of AI-generated code, because in 2003 that problem didn't exist. And the service is a black box you submit to and wait for, which is fine until you need to explain a result in a formal academic integrity hearing and want the raw token alignment.

Generation four, trees and graphs (1998-2008)

Token streams have a blind spot, and it's the one that matters most now. They ignore structure. Two token sequences can be identical as bags and radically different as programs, and more importantly, two programs with the same structure can produce quite different token sequences if the author reorders independent statements or inlines a variable.

Ira Baxter and colleagues attacked this at ICSM in 1998 with CloneDR, hashing subtrees of a parsed abstract syntax tree and comparing subtree hashes rather than token runs. It's a clean generalization: a subtree hash is invariant to everything inside the subtree that your normalizer already collapses, plus it gives you a notion of matching at a syntactic boundary. In 2007, Jiang and colleagues' DECKARD pushed the same instinct into the vector domain, converting tree neighborhoods into characteristic vectors and clustering them, which got them Type 3 clones at reasonable scale. Gabel, Jiang and Su followed in 2008 with a scalable semantic clone detector built on program dependence graphs, which encode control and data flow rather than syntax.

PDG-based detection, from Komondoor and Horwitz in 2001 and Krinke's WCRE paper the same year, is the most aggressive version of the idea. Two fragments are "similar" if their dependence graphs are isomorphic. That catches Type 4 rewrites that no token tool will ever see. It also costs you a real compiler frontend per language, and the matching problem is graph isomorphism, which is expensive and, for near-misses, needs approximation. That's why PDG detection has stayed mostly in research and in very specific industrial clone tooling rather than in grading systems.

JPlag, from Prechelt, Malpohl and Philippsen at Karlsruhe (the 2002 journal paper; the workshop version is 2000), is the tool academia actually adopted from this period. It stayed token-based with greedy string tiling rather than going full graph, and the reason is instructive. It was built for the same audience as a source code plagiarism checker is today: instructors who need a defensible result fast, not a research contribution. JPlag has since been rewritten, the 4.x line arrived in 2023 and a 5.x line after it, it covers around twenty languages, and it remains free for academic use. Those are real advantages and I'd never tell a department to stop using it.

The empirical check on all of this came from Bellon and colleagues in 2007, who ran six different clone detectors against the same large corpus. Their headline finding was not that one tool won. It was that agreement between tools was poor, and that essentially no tool reliably caught semantic clones. Twenty years later, the same sentence applies to the code plagiarism market, which is why stacking detectors rather than trusting one is the standard advice.

Generation five, vectors (2016-2022)

Machine learning entered from the clone-detection side first. SourcererCC (Sajnani et al., ICSE 2016) used token-level inverted indexes and a filtering heuristic to get clone detection to internet scale on GitHub. DeepSim (Zhao and Huang, FSE 2018) learned a representation of control-flow graphs and compared in an embedding space. CodeBERT (Feng et al., 2020) gave everyone a pretrained encoder and produced a small wave of papers reporting decent numbers on type-4 clone benchmarks.

For education specifically, Dolos (2022) is the most interesting artifact of this period: language-agnostic, open source, produces a real report, and it merged fingerprinting with tree-based comparison in a way that reads like the field consolidating everything above into one pipeline.

The cost of embeddings is the same thing that made metrics fail in 1996. A cosine distance is not evidence. If a student appeals and you have to justify the finding, "the CodeBERT embedding of your function is 0.94 close to your classmate's" is not a sentence that survives contact with a faculty committee. The tools that held up in practice kept the token alignment and the AST structure visible and used embeddings as one more signal in a ranked queue.

2022, when paraphrasing became cheap

Everything above assumed a fixed evasion cost. To defeat a token-based detector in 2015, a student had to rename identifiers, restructure control flow, and reorder statements by hand. That's forty minutes of tedious work, and most students would rather just write the assignment. GitHub Copilot went generally available in June 2022. ChatGPT launched in November 2022. By 2023 the forty-minute laundering step cost one prompt.

That changed the economics on both sides of the ledger. On the generation side, a model can produce a correct, idiomatic solution to a well-specified assignment in seconds, and it will happily produce a different correct solution if you ask it to try again. On the detection side, the artifact you're analyzing now has two properties simultaneously: it may have no human author, and it may have no near neighbor in the cohort because no two students prompted identically.

Peer similarity cannot see that. This is the structural reason AI detection had to become a separate signal rather than an extension of similarity scoring. Detectors now look at statistical properties of the token sequence itself: which tokens the file chooses, how predictable each choice is under a code language model, how uniform the comment style is, whether the imports are exactly what a model would emit for the stated problem. It works, and it fails in specific places. A 300-line submission where a student wrote 280 lines and let a model complete one function will produce a mixed score, and any tool that reports a single confident number for the whole file is overselling.

Provenance checking got more important at the same time, for a related reason. Models were trained on code that's still sitting on GitHub and Stack Overflow, so pasted-from-the-internet and generated-by-a-model now overlap. A match against a public repository is a hard fact you can put in front of a student's advisor. A 0.83 AI probability is a signal that needs a human conversation behind it. You want both, in that order of evidentiary weight.

What the arc suggests about picking a detector now

Read the fifty-year history as a checklist and the current market gets easier to sort. Four properties matter, and they correspond almost exactly to the five generations above.

Normalization depth determines what you can catch. Character comparison catches copy-paste. Token normalization with careful literal handling catches renaming. AST comparison catches reordering and inlining. If a tool's documentation only talks about "text similarity" and "exact matching," it is a 1985 detector with a 2025 interface.

Corpus breadth determines what you can find that isn't in the room. Peer comparison alone is blind to code lifted from a tutorial, a previous semester, a GitHub repository, or a model's training data. Some of those sources are checkable and some are not, but a detector that only compares submitted work against other submitted work is answering a strictly smaller question than the one instructors actually have.

Evidence quality determines whether the finding survives an appeal. This is the axis people underestimate. A percentage is a lead. A synchronized diff with the matched token runs highlighted, plus a line count and a source URL, is a finding. The difference between those two things is the difference between a conversation and a grievance procedure.

Workflow fit determines whether anyone uses it. MOSS and JPlag were built for a world where one instructor ran a batch job twice a semester. Engineering teams now want the same analysis in CI, and course staff want a dashboard that ranks 400 submissions instead of a tarball of HTML.

This is where I'll make the case for Codequiry, because it's the tool that happens to sit at the intersection of all four axes. The detection core is a token plus AST plus fingerprint pipeline, so renaming, reformatting and structural edits all stay visible, which is the direct inheritance of generations two through four. The corpus is peer submissions plus the open web plus GitHub, which is generation five's provenance lesson taken seriously. AI generation is scored as a separate per-file signal, so you can tell the difference between "copied from a classmate" and "produced by a model" instead of getting one blended number. Reports carry the side-by-side diff, so the evidence problem is handled at the point of generation rather than in a follow-up email. And it runs either through a web dashboard for instructors or through a REST API and CLI for teams that want it in a pipeline.

The honest comparison to the incumbents is this. MOSS is free, battle-tested, and has no UI, no web corpus, and no AI signal; if that's sufficient for you, use it. JPlag is free for academia with better language coverage than it had a decade ago and a modern report viewer, but it's still primarily peer comparison. Dolos is the best of the open-source newcomers and I'd recommend it to anyone building their own pipeline. Codequiry's advantage is that the three signals that matter now, structural similarity, web provenance, and AI generation, arrive in one report with one set of scores rather than three tools you have to reconcile yourself. If you want the detailed feature-by-feature version, there's a longer write-up in Codequiry vs MOSS.

Frequently asked questions

Does token-based similarity detection survive renaming and refactoring?

Renaming and reformatting, reliably, because the normalizer collapses identifiers and drops whitespace before any comparison happens. Structural refactoring is a harder case and depends on depth: statement reordering and loop restructuring usually survive AST-level comparison but can drop a token-only detector's score substantially. This is the main practical argument for tools that combine both.

Can AI-generated code be detected with the same technique?

No, and it's worth being precise about why. Peer similarity asks "does this resemble something else in the corpus?" AI detection asks "does this token sequence look like it was sampled from a language model?" Those are different questions with different failure modes. A fully generated submission with a unique prompt has no near neighbor, so similarity finds nothing; a heavily edited human submission can look statistically model-like. Running both and reporting them separately is the only honest arrangement.

Is MOSS still adequate for a university course in 2025?

For straight peer copying, largely yes, and it's free. The gaps are the ones history created: no web or GitHub corpus, no AI-generation signal, and no evidence interface beyond a list of matched regions. Many departments run MOSS alongside a second tool specifically to cover those gaps. You can see how that comparison plays out in practice through the AI code detector side of the problem, which MOSS was never designed to address.

What's the minimum shared run a winnowing detector will catch?

With k-gram length k and window size w, the guarantee is any shared run of at least k + w - 1 tokens. In practice tools set k in the high teens or twenties so that common idioms and standard boilerplate don't generate false matches. Lower k finds more, including more noise.

The through-line of the last fifty years is that detectors keep moving up the abstraction ladder, and the evasions keep moving up with them. If you want to see what the current top of that ladder produces on real submissions, you can run a check on your own course archive and read the report yourself.