Building a Refactoring-Resistant Similarity Pipeline

Refactoring-resistant plagiarism detection works by comparing normalized token streams and abstract syntax trees rather than the text a student actually typed. Renaming a variable, extracting a helper method, or converting a loop to recursion changes the text and leaves the token sequence and the tree shape largely intact. The engineering problem is deciding how far to normalize, because every step away from the literal source buys resistance to camouflage and costs precision.

Two submissions to a data structures midterm, 210 in the cohort, both implementing red-black tree insertion in C++. One student wrote the fixup inline with a while loop and named things parent, uncle, node. The second extracted the fixup into rebalance_upward, renamed every identifier to p, u, n, and converted the recursion to iteration. MOSS returned 14% for the pair. The pair was one submission with a two-hour refactoring pass in between.

Fourteen percent is not a bug in MOSS. It's a precise statement about what the tool was asked to compare. MOSS compares fingerprints of token k-grams, and the student changed enough tokens to break the fingerprints. If your detection pipeline can be defeated by a rename refactor, the pipeline is measuring the wrong thing.

Why text-matching tools miss refactored code

Most general-purpose plagiarism checkers were built for prose, and prose similarity is a solved-enough problem that the tooling got lazy. They strip whitespace, chunk the document into phrases of n words, hash the phrases, and compare hash sets. Run that on two C++ files where one has been reformatted by clang-format and had its identifiers renamed, and you get a similarity score near zero. Run it on two files where one student copied the other and changed nothing but a comment header, and you get 97%. The tool is measuring textual overlap, which is a proxy for copying that a determined student can invalidate in twenty minutes with a text editor.

Hage, Rademaker, and van Vugt published a comparison of JPlag, MOSS, and Sherlock in 2010 and the finding that has held up since is that token-based comparison dominates text-based comparison on exactly this axis. Fifteen years later the conclusion has not moved. The interesting work is all in choosing the token model.

Refactoring-resistant plagiarism detection starts at the tokenizer

The first level of normalization is lexical. Take the source, run it through a real tokenizer for the language, throw away the tokens that carry no semantic weight, and replace the ones that carry too much identifying information with a class marker. Here's the whole idea in about fifteen lines of Python:

import io, tokenize

KEYWORDS = {"if", "elif", "else", "for", "while", "return", "def",
            "class", "in", "not", "and", "or", "None", "True", "False"}

def normalized_stream(src):
    stream = []
    for tok in tokenize.generate_tokens(io.StringIO(src).readline):
        kind, text = tok.type, tok.string
        if kind in (tokenize.COMMENT, tokenize.NL, tokenize.NEWLINE,
                    tokenize.INDENT, tokenize.DEDENT):
            continue                      # layout carries no signal
        if kind == tokenize.NAME and text not in KEYWORDS:
            stream.append("ID")           # rename-resistant
        elif kind == tokenize.NUMBER:
            stream.append("NUM")          # constant-swap resistant
        elif kind == tokenize.STRING:
            stream.append("STR")
        else:
            stream.append(text)           # punctuation, keywords, operators
    return stream

Three things just happened. Comments and layout vanished, so reformatting and comment-swapping are neutralized. Every user identifier collapsed to ID, so parent and p became indistinguishable. Every numeric literal collapsed to NUM, so i < n - 1 and i < 99 stopped differing. What survives is the sequence of keywords, operators, and structural punctuation, which is a much better proxy for "did this person write this algorithm" than the raw text.

Go further and your students are all writing the same program, which is philosophically interesting and operationally useless. I'll come back to that.

k-gram fingerprinting and the winnowing guarantee

A normalized token stream is still a sequence, and comparing sequences pairwise across 210 submissions is 21,945 comparisons. The standard trick, and the one MOSS is built on, comes from Schleimer, Wilkerson, and Aiken's 2003 SIGMOD paper on winnowing. Cut the stream into overlapping k-grams, hash each one, then select a sparse subset of those hashes by taking the minimum hash value in each window of width w.

from hashlib import blake2b

def h(tokens):
    return blake2b(" ".join(tokens).encode(), digest_size=8).digest()

def fingerprints(stream, k=15, w=4):
    grams = [h(stream[i:i+k]) for i in range(len(stream) - k + 1)]
    picked = set()
    for i in range(len(grams) - w + 1):
        picked.add(min(grams[i:i+w]))
    return picked

Use a stable digest, not Python's builtin hash(), which is salted per process and will give you different fingerprints on every run.

The reason winnowing beats naive sampling is a guarantee worth stating precisely: if two documents share a token substring of length at least k + w − 1, winnowing will select at least one common fingerprint from that substring. With k = 15 and w = 4, any shared run of 18 consecutive normalized tokens is guaranteed to surface. That's the number to tune. Lower k catches shorter copied fragments and floods you with false positives on idiomatic code. Raise k past about 25 and students who copy a helper function but rewrite the surrounding twenty lines start slipping through.

Score the resulting sets with containment rather than Jaccard. If one submission is 400 tokens and the other is 1,200 because the second student wrote more of the assignment, Jaccard punishes the honest difference in size. Containment, |A ∩ B| / min(|A|, |B|), answers the question you actually care about: how much of the smaller submission is inside the larger one.

AST comparison and what tree edit distance costs

Token normalization handles renaming. It does not handle restructuring, and restructuring is what a student does when they have absorbed the copied logic well enough to change its shape. Loop to recursion, if chains to switch, inline code to an extracted method. Falleri and colleagues published GumTree in 2014 for fine-grained source differencing, and the same tree-matching machinery is what modern clone detectors use: parse both files, map nodes by label and structure, and measure how much of one tree maps onto the other.

The cost is tree edit distance. Zhang and Shasha's 1989 algorithm runs in O(n·m·min(depth, leaves)²), which is fine for a 200-line method and unpleasant for a 2,000-line file. Every tool that does this seriously ends up with heuristics: hash subtrees above a size threshold, prune identical subtrees, only run the expensive matching on candidate pairs that already scored above 40% on the cheap token pass. That two-stage design is why real pipelines are fast enough to be useful.

Dolos, described by Maertens and colleagues in 2022, takes a hybrid approach that is worth studying: parse with tree-sitter to get a language-agnostic AST, run a winnowing pass over the tree's serialized structure, and fall back to token-level comparison where parsing fails. The hybrid is not indecision. The two representations catch different edits, and an edited submission usually trips one of them.

The precision cost of aggressive normalization

Here's the tension nobody puts in the tool's README. Every normalization step raises recall on refactored copies and lowers precision everywhere else.

Normalization level	Defeats	Typical false positive rate on a 150-student cohort
Whitespace-insensitive text	Reformatting, comment changes	Low, and it also misses most real copies
Tokenized, literals preserved	Renaming	Moderate
Tokenized, identifiers and literals collapsed	Renaming, constant swapping, dead-code insertion	High on constrained assignments
AST-level with subtree hashing	Restructuring, helper extraction	High, and harder to explain to a student

The failure mode is predictable. Assign an exercise with a fixed public interface, say "implement insert, delete, and lookup on a chained hash map," and the correct solution space is small. Every student writes the same forty lines. Collapse identifiers and literals and the top pairwise similarity in the cohort will sit somewhere around 70 to 85 percent, and the highest-scoring pair may have never spoken to each other. That's not plagiarism, that's a specification.

I have made this mistake in production. The first semester I ran a normalized pipeline, I left identifier collapsing on for an assignment that handed students a header file with the method signatures spelled out. The scan produced forty flagged pairs on the first night. Thirty-eight of them were two students independently writing the obvious loop. We spent a weekend reading diffs we should never have had to read, and I have set normalization per assignment ever since.

Choosing a normalization level per assignment

The rule I use now: normalize proportionally to how much freedom the assignment gives. A from-scratch implementation of Dijkstra's algorithm with no starter code has an enormous solution space, so aggressive normalization costs you almost nothing and catches the student who copied and then renamed. An assignment that ships a 300-line scaffold and asks students to fill in four functions has a tiny solution space, so you want strict comparison, literal preservation, and a much higher threshold before anyone gets flagged.

Two settings carry most of the weight: whether identifiers collapse to ID, and what k is. Write them down per assignment. When a student appeals, the first question you'll be asked is what the checker was configured to do, and "I don't remember" is not an answer that survives a department committee.

Where MOSS, JPlag, Dolos, and Codequiry actually differ

MOSS is free, and it is genuinely good at what it does. It's also a script that emails you a directory of HTML files with no database, no web UI, no per-assignment history, and a results format that has not changed meaningfully since the Bush administration. Adding a new language often means waiting for someone at Stanford to care. JPlag's open-source token-based approach with real language grammars is a strong choice if you want to read the source and the 5.x releases in 2024 finally replaced the old report viewer. Dolos has the best structural modeling of the open-source options. None of them answer the question "which of these 210 submissions should I look at first" without you building that layer yourself.

That triage layer is most of the actual work in a grading pipeline, and it's the part a source code plagiarism checker built for a cohort rather than a file pair has to earn. Codequiry runs token, AST, and fingerprint passes in one scan, stores the per-submission history, and surfaces peer, web, and AI signals on the same report, which means you're not reconciling three tools' output formats at 11 p.m. before grades are due. If you're currently on MOSS, the honest comparison is at Codequiry vs MOSS; the short version is that you're trading a free script for a maintained pipeline with an API.

Running the pipeline without generating false accusations

The workflow that has held up for us is three passes, and the first two are cheap.

Export submissions from the LMS, run the scan, and sort by score. That's pass one and it takes ten minutes. Pass two is the one people skip: read the actual aligned token streams for anything above your threshold before you decide anything. A 78% score with a contiguous 400-token alignment is a copy. A 78% score distributed across fourteen short matches is two students writing idiomatic code against a tight spec. The score tells you where to look. The alignment tells you what happened.

Pass three is a conversation, and its content depends entirely on whether pass two produced evidence you'd be willing to show the student. If the answer is no, the pipeline failed, not the student.

What similarity can't tell you

Normalization and similarity answer one question: does this submission resemble another submission or a known source. They do not answer the question that has consumed most academic integrity conversations since 2023, which is whether a student wrote the code at all. A submission generated by ChatGPT and lightly edited has no peer to match against and no GitHub repository to trace to. Peer similarity will rate it unremarkable. Web similarity will rate it unremarkable. It will be, in the precise sense, original.

Catching it needs a different signal entirely, one that looks at the statistical texture of the code rather than its similarity to anything. That's a separate pipeline with its own error characteristics, and it's worth running alongside the similarity scan rather than instead of it. Codequiry bundles an AI code detector into the same scan for that reason: the two signals answer different questions, and the case where both fire is the case you can defend.

If you're setting this up for a course or a cohort this term, the code plagiarism checker is where the configuration starts.