IsQuine fails to detect period-2 "loopy" zip quines — only adjacent parent/child pairs are compared

[Mabbs]

Summary

Extractor.IsQuine never detects period-2 (loopy) zip quines — an archive A containing archive B, where B again contains a byte-identical copy of A (an alternating cycle). The implementation only compares adjacent pairs along the parent chain, but in a loopy pair both the names and the contents alternate, so no adjacent pair is ever identical — even though entry L3 is byte-identical to its grandparent L1.

This contradicts the method's own documented contract:

/// <returns>True if the FileEntry is a identical to any of its predecessors</returns>

("any of its predecessors", not "its immediate parent"). Extraction of such an archive is stopped only by the MaxExtractedBytesRatio backstop (200× amplification by design), not by the quine protection the README advertises.

Affected version

• Microsoft.CST.RecursiveExtractor.Cli 0.2.61 (latest on NuGet at the time of writing)
• Source verified at master b8e85c698cd80735207bb38847531e8c977c7e6b (2026-09-10)

Reproduction

Option A — ready-made public sample (no build needed). examples/Ouroboros.zip from ruvmello/zip-quine-generator (MIT, companion artifact of the MDPI Appl. Sci. 2024, 14(21), 9797 paper) is a true period-2 loopy pair. Verified byte-level: L1 (sha256 84a1395d…) → loopy_zipquine.zip (34f984a9…) → Ouroboros.zip (84a1395d… again) → …

dotnet tool install -g Microsoft.CST.RecursiveExtractor.Cli
RecursiveExtractor --input Ouroboros.zip --output out -s

Observed: no Detected Quine message. Extraction recurses ~85 levels (170 filesystem entries materialized for a 50 KB input) until the ratio governor fires OverflowException: Too many bytes extracted, exceeding limit.

Option B — generate your own.

git clone https://github.com/ruvmello/zip-quine-generator
mvn package -DskipTests
java -jar target/zip_quine_generator.jar one.txt two.txt --loop   # produces one.zip; keep the name!
RecursiveExtractor --input one.zip --output out

The --loop mode outputs one.zip ⊃ two.zip ⊃ one.zip ⊃ … with alternating names — same bypass.

Note on the shipped example's naming: Ouroboros.zip bypasses because its inner member keeps a different name (loopy_zipquine.zip); the name cycle alternates together with the content cycle. A same-content copy that is renamed to match its parent is still caught (at depth 3) by the current code — the bypass requires the content period to be ≥ 2, which is exactly what loopy pairs are.

Observed impact

• With a small pair (≈50 KB), the only thing that stops extraction is ResourceGovernor — i.e. the designed 200× byte amplification is fully consumed before stopping. Quine detection, which should stop this at depth 3, never fires.
• With a larger archive containing such a pair (example: MayxBlog.7z), the ratio budget (≈3.7 GB) exceeds what the filesystem tolerates: on Windows the recursion reached ~1,700 levels before dying with an unhandled IOException (path > 32,767 chars → AggregateException, exit Failure) after ~15 min CPU, ~950 MB RAM and ~7,400 filesystem entries written — instead of a clean OverflowException from quine detection.

I encountered a pair produced by this generator inside a real-world publicly distributed archive, so this is not merely a theoretical construction.

Root cause

Extractor.cs (master b8e85c6):

// https://github.com/microsoft/RecursiveExtractor/blob/master/RecursiveExtractor/Extractor.cs
public static bool IsQuine(FileEntry fileEntry)   // line 183
{
    var next = fileEntry.Parent;
    var current = fileEntry;

    while (next != null)
    {
        if (AreIdentical(current, next))   // only (entry,parent), (parent,grandparent), ...
        {
            return true;
        }
        current = next;        // ← the window slides: grandparent-identical entries are never compared
        next = next.Parent;
    }

    return false;
}

current = next restricts the comparison to adjacent chain pairs. For a period-2 cycle the identical entries are always two levels apart and are never compared. (All current quine fixtures in TestData/Bombs are period-1, which is why this went unnoticed.)

Suggested fix

Pin current to the entry and slide only next, so the entry is compared against every ancestor:

public static bool IsQuine(FileEntry fileEntry)
{
    var next = fileEntry.Parent;
    while (next != null)
    {
        if (AreIdentical(fileEntry, next))
        {
            return true;
        }
        next = next.Parent;
    }

    return false;
}

Cost is unchanged (same number of AreIdentical calls per entry), and AreIdentical's Name/Length pre-checks keep full byte comparisons rare. Comparing against ancestors only (as opposed to a global seen-set) is the right semantics — identical files in sibling branches are legitimately extracted; identical files along the ancestor chain mean re-producing an ancestor.

Suggested regression test

Add a period-2 fixture to TestData/Bombs (e.g. the Ouroboros.zip example or output of the generator's --loop mode) and assert that Extract throws OverflowException via the quine path (Detected Quine), not via ResourceGovernor.