This is the record of an abcd-managed repository

abcdBetav0.16.2 · 2026-11-06

Development record

scanner-adjacency-galloping-probe-structural-fix

specclosedspc-48

Summary

Replaces the fixed 512-byte adjacency window in the secret/PII scanner with a galloping (exponential-doubling) trueMatchEnd probe, so a match end is never a truncation artefact of the window edge. The window grows only while a match keeps running into its edge and stops the moment the match ends short of the edge or reaches the real end of line. This is the structural fix designed in the 2026-08-08 decision dcn-2608080000000001, and it dissolves the two superseded issues — iss-189 (a trailing boundary satisfied by the artificial window edge → spurious over-redaction) and iss-190 (a window-capped recovery truncating a token and breaking the recovery chain) — without a boundary classifier or a clipped-so-skip special case, and without the round-6 cost regression.

Scope

In:

  • internal/adapter/scanner/scanner.go — the probeAt closure inside scanAllPatterns (scanner.go:484–497), where a match end is computed against a truncated slice, and stolenJunctions (scanner.go:539) where the same fixed cap bounds the forward junction search.
  • internal/adapter/scanner/adjacency_test.go — the iss-189 and iss-190 repro shapes as regression tests, plus a cost-class assertion.

Out:

  • No change to the pattern set, the probe construction (adjacencyProbe, junctionProbe), or the redaction step.
  • maxAdjacencyBacktrack (the backward bound in stolenJunctions, scanner.go:449) is retained; the galloping change is on the forward extent only.
  • No boundary classifier and no clipped-so-skip branch — the intent forbids both, and the design achieves the fixes without them.

Approach

Today's truncation source. In probeAt (scanner.go:484–497) the window is a single fixed slice:

limit := at + maxAdjacencyProbeWindow   // maxAdjacencyProbeWindow = 512, scanner.go:434
if limit > len(line) { limit = len(line) }
window := line[at:limit]
m := probes[j].FindStringIndex(window)
... add(patMatch{j, at, at + m[1]})     // end computed against the truncated slice

Because RE2 treats the slice's end as end-of-string, a trailing \b in a probe is satisfied by the artificial edge (iss-189), and an open-ended token longer than 512 has its end pinned at at + 512 — an artificial end that makes the next probeAt(m.end) and stolenJunctions start mid-token, breaking recovery (iss-190).

The galloping probe. Replace the single-shot slice with an exponential-doubling probe that computes trueMatchEnd:

  1. Start with a small window w (e.g. 64 bytes) at at.
  2. Run probes[j].FindStringIndex(line[at:min(at+w, len(line))]).
  3. If the match reaches the window edge — m[1] == w and at+w < len(line) — the match may still be growing: double w and re-run.
  4. Stop when the match ends short of the edge (m[1] < w) or the window has reached the real end of line (at+w >= len(line)). In both stop cases the slice end is not an artefact: either the match genuinely ended before it, or it is the true end of line. Set end := at + m[1].

Because the probe grows only while the match keeps running into its edge, a short match (ending well before 64 bytes) is found on the first attempt with the same cost and result as today. A long match doubles a logarithmic number of times, and each doubled scan is over a prefix the top-level cp.Re.FindAllStringIndex(line, -1) (scanner.go:499) already pays for — so the amortised cost stays in the class the unbounded top-level match already pays, the round-6 regression the decision dcn-2608080000000001 warns against.

stolenJunctions. Its forward bound hi := m.end + maxAdjacencyProbeWindow (scanner.go:547) is replaced with the same galloping extent, so the recovery chain is never capped by the fixed 512 and the iss-190 chain stays intact. The backward bound (lo, using maxAdjacencyBacktrack) and the resume-at-cut+1 step (scanner.go:576, the iss-188 fix) are unchanged.

How it satisfies each acceptance criterion

  • A match running past the old 512 window is captured whole; its end is never a truncation artefact — the galloping loop doubles until the match ends short of the edge or hits end-of-line, so trueMatchEnd is the real end. Test: a redactable token > 512 bytes; assert the whole match is captured and end equals the true token end.
  • A short match's result and cost are unchanged — a match ending before the initial w is found on the first, smallest scan. Test: TestConcatenatedSecretsBothDetected and the short-match cases in adjacency_test.go stay green; a cost assertion mirrors TestAdjacencyProbeStaysLinearOnLongLines.
  • iss-189 shape produces no spurious over-redaction, without a boundary classifier — the trailing \b is now evaluated against the true end of line, not the artificial edge, so it is not satisfied by the edge. Test: add the iss-189 repro (a trailing boundary met only by the window edge) and assert no finding, with no boundary-classifier code introduced.
  • iss-190 shape keeps the recovery chain intact, without a clipped-so-skip special case — the token's true end feeds the next probeAt(m.end) and the galloping stolenJunctions, so the third abutting token recovers. Test: add the iss-190 repro (window-capped recovery) and assert every token is detected, with no clipped-so-skip branch.
  • A match genuinely still growing doubles only while it runs into the edge, within the amortised cost class — the loop's stop condition (m[1] < w or end-of-line) bounds growth to genuinely-growing matches. Test: assert the number of probe doublings is logarithmic in the match length, mirroring TestAdjacencyProbeWindowIsBounded / TestJunctionBacktrackIsBounded as cost guards.

Decisions

The three prior bug-hunt rounds each BLOCKed on a local patch (a boundary classifier for iss-189, a clipped-so-skip for iss-190) that reached further than the ambiguity and either over-redacted or regressed cost. The decision dcn-2608080000000001 resolved on the structural fix: remove the artificial edge entirely, so neither local patch is needed. This spec encodes that resolution — the galloping probe is the single mechanism, and the two superseded repro shapes are its acceptance corpus.

Frontmatter

idspc-48
typespec
lifecycleclosed

.abcd/development/specs/closed/spc-48-scanner-adjacency-galloping-probe.md
open on GitHub ↗ · commit history ↗

References1

  • itd-155implement the galloping/exponential-doubling probe (trueMatchEnd) that replaces the fixed 512-byte adjacency window in scanAllPatterns/probeAt: the window grows only while a match keeps running into its edge and stops the moment the match ends short of the edge or reaches the real end of line, so a match end is never a truncation artifact. This is the structural fix designed in the 2026-08-08 decision [dcn-2608080000000001](../../../work/decisions/dcn-2608080000000001-iss-189-iss-190-shared-root-cause.md) after bug-hunt rounds 6-8 each BLOCKed on local patches for the same root cause (a truncated window-edge view driving a discard/skip decision reaching further than the ambiguity). It dissolves iss-189 (trailing boundary satisfied by the artificial window edge, spurious over-redaction) and iss-190 (window-capped recovery truncating a token and breaking the recovery chain) outright, without reintroducing the round-6 cost regression: the window grows only for matches genuinely still growing, at the amortized cost class the top-level unbounded match already pays. iss-189 and iss-190 (both superseded by this capture) are its acceptance corpus: their repro shapes must pass without a boundary classifier or a clipped-so-skip special case.implements

mentions7

  • dcn-26080800000000012026-08-08 — iss-189/iss-190 shared root cause identified, fix designed but not
  • iss-188scanner adjacency recovery misses greedy over-consumption in open-ended-quantifier secret patterns. iss-185's fix (scanAllPatterns, scanner.go) recovers a second token that immediately abuts a first with no separator ONLY when the first pattern is fixed-length (its match always ends exactly where the second token begins, so probing every pattern's boundary-free variant at that one byte offset is sufficient). A pattern whose quantifier is open-ended (e.g. `\bghp_[A-Za-z0-9]{36,}`, `\bsk-ant-[A-Za-z0-9_-]{40,}`, `\bsk_live_[A-Za-z0-9]{20,}`) instead greedily consumes as many class-matching bytes as are available, including a following token's own leading bytes when those happen to fall inside the same character class — shifting the true junction earlier than the reported match end, before scanAllPatterns' adjacency probe ever runs. Concrete repro: `"ghp_" + strings.Repeat("a",36) + "ghp_" + strings.Repeat("b",36)` — the first `ghp_` pattern's `{36,}` class run consumes the 36 a's AND the second token's leading "ghp" (all alnum), stopping only at the second token's `_` (not in `[A-Za-z0-9]`); ScanText reports exactly ONE finding covering `ghp_aaaa...aaaghp`, and the second token's `_bbbb...bbb` tail survives Redact completely raw with the fail-closed residual re-scan reporting clean — the same "can never contain a live secret" violation iss-185 was filed for, just for the open-ended-quantifier pattern family instead of the fixed-length one. Distinct from iss-185 (closed): that fix's mechanism (probe every pattern at a match's reported end) is necessary but not sufficient — this needs a bounded backward search (shrink the greedy match's end toward its start, checking at each candidate cut whether the shortened match is still valid for its own pattern AND some pattern's boundary-free variant matches there) without becoming O(line length) per match, since these patterns' matches can legitimately be very long (base64 blobs, minified files) and an unbounded backward scan across every byte would be a new resource-exhaustion risk on exactly the kind of large single-line input a secret scanner must handle. Surfaced by an adversarial pre-PR security review of iss-185's fix (bug-hunt loop round 3), not by the round's own hunt; not fixed in that PR to keep its diff scoped to the exact bug iss-185 named and to avoid shipping an unbounded-cost search under review pressure. Affected pattern families: github_pat (ghp_/ghs_/gho_/ghu_/ghr_), anthropic, openai_project, openai_svcacct, stripe_live, stripe_test, slack, jwt_shaped — every bundled pattern with an open (`{n,}`) rather than fixed (`{n}`) quantifier.
  • iss-189adjacency probe's trailing \b can be satisfied by the window edge instead of real content, causing a spurious over-redaction. scanAllPatterns (scanner.go) slices the line to a bounded window (line[end:min(end+512,len(line))]) before running each pattern's adjacencyProbe, to keep one probe attempt's cost constant regardless of what follows (iss-185's fix). Some probes retain an internal trailing \b of their own (e.g. net_lan_hostname's `\b` at the very end of its alternation) which normally requires a real non-word character (or true end of string) after the match. But when the probe is truncated to the window, "end of window" is treated by the regex engine exactly like "end of string" — so if the window happens to end immediately after what LOOKS like a complete hostname/token, the trailing \b is satisfied by the artificial window boundary rather than by real surrounding content, even though the FULL, untruncated line would not have matched there (the real next byte continues the token). Concrete repro: a line built as `"AKIA"+16*"Q"` (a confirmed match, establishing the probe's junction) + 506 filler bytes + ".local" + "zzz" — the window (512 bytes from the junction) ends exactly after "local", so net_lan_hostname's probe matches "b...local" (satisfied by end-of-window) even though the real line continues with "zzz" right after ".local", meaning the FULL line's own un-windowed net_lan_hostname pattern would NOT match there at all (no real word boundary follows in the actual text). Impact: a spurious net:lan_hostname finding (warn severity only, not hard_fail) causes Redact to needlessly rewrite up to 512 bytes of legitimate content as fingerprinted/starred output — not a security leak (over-redaction, not under-redaction) but a correctness/usability defect: legitimate file content gets mangled on a contrived but reachable input shape. Suggested fix (from the reviewer that found this): when a probe match's end lands exactly at the window's limit AND limit < len(line) (i.e. the window was actually truncated, not naturally at the line's end), re-run that one probe against the full, untruncated line[end:] before accepting the match — paying the larger cost only in this rare edge case rather than on every probe. Found during a merge-gate correctness review of iss-185's PR (bugfix/iss-185-scanner-adjacent-secret-boundary-bypass); non-blocking (contrived input, warn-severity-only impact), so not fixed inline — captured for its own verify-and-fix cycle.
  • iss-190scanner adjacency recovery is capped by maxAdjacencyProbeWindow, so a recovered token longer than the window is truncated — and the truncation can break the recovery CHAIN, hiding a third abutting token entirely. probeAt (scanAllPatterns, internal/adapter/scanner/scanner.go) runs its anchored probe against line[at:at+maxAdjacencyProbeWindow] (512 bytes), so a recovered open-ended match longer than that is recorded with an artificial end at the window edge. Two manifestations. (a) Known and accepted since iss-185: the recovered token's far tail past the window stays raw in Redact's output; the token's prefix is still masked, so this is a partial-redaction trade, not a total miss. (b) NEW, found by two independent adversarial reviews of iss-188's fix: because the artificial end does not align with the token's real end, the next iteration's probeAt(m.end) and stolenJunctions both start from a byte offset that is inside the token rather than at its junction, so the chain that would otherwise unwind a run of three or more abutting tokens breaks — the third token becomes entirely invisible, not merely truncated. Repro: line := "ghp_" + strings.Repeat("a",36) + "ghp_" + strings.Repeat("m",600) + "ghp_" + strings.Repeat("z",36) yields exactly 2 token:github_pat findings where an unbounded search would find 3; the third token's 36 raw bytes survive Redact and the fail-closed residual re-scan reports the output clean. A sharper variant of (a) affects jwt_shaped specifically: its regex requires two literal '.' separators, so a JWT-shaped token whose header and payload together exceed the window has NEITHER separator inside the probe's slice and the anchored probe finds no match at all — the token is missed entirely rather than truncated, e.g. a fixed-length match immediately followed by a JWT whose first two segments total more than ~502 bytes. This is NOT a defect introduced by iss-188's backward search; it is the same pre-existing maxAdjacencyProbeWindow trade-off from iss-185, now reachable through a second code path because the backward search feeds more candidates into probeAt. Fixing it properly needs a different mechanism (a growing or adaptive window, or re-probing chained from a recovered match's real end) that must not reintroduce the unbounded per-match cost the window exists to prevent — the exact risk iss-188's own ledger entry warned against. Deliberately not folded into iss-188's fix pass to keep that diff scoped to the confirmed junction-search defect.
  • iss-239Dangling pre-rebuild spec ids in the draft corpus: itd-44 (spc-56), itd-51 (spc-33/37), itd-57 (spc-48/60/62), itd-61 (spc-75) cite specs from the numbering adr-21/adr-26 reset (live store is spc-1..spc-22). Worse, intents/README.md and itd-34 assert the itd-44 lineage 'landed as itd-44 (spc-56 thin adoption)' — no such spec or decision-verdict code exists, so the record claims a delivery the tree cannot back.
  • itd-44A Capture-Time `decision` Verdict That Routes Infrastructure Choices Into The Existing ADR Store
  • itd-57Every abcd Voyage Ships With A Manual-Hold Sentinel That Blocks A Spec From Autonomous Pickup Until A Human Lifts It