Skip to content

Security review

James Conway edited this page Nov 19, 2026 · 1 revision

Security review of the parser

Recorded 2026-11-18. Covers the tokenizer, the tree builder, the selector engine, the editing API and the one unsafe block, against the assurance case in Limits and hostile input and Thread safety and memory safety.

All four findings are fixed, in netweir/netweir#333, synced here in #96, each with a test that fails without its fix. Report any new way to break a promise privately, per SECURITY.md.

Scope

In scope: crates/parsec/src/{tokenizer, tree, dom, edit, serialize, css, pattern, entities, lib}.rs. The threat is a library parsing HTML nobody vouches for, plus selectors and DOM edits that may carry a user's input. I looked for: panics reachable from input (indexing, unwrap/expect on input-derived data, arithmetic overflow near MAX_INPUT, non-char-boundary slicing); unbounded recursion / stack overflow (tree depth, selector nesting and length, the pattern.rs regex, serialization); super-linear time (quadratic walks in the tree builder, in :has(), in :nth-child(of S), regex backtracking against the step limit); memory blow-up; the single unsafe block's soundness; Send/Sync; and whether an edit sequence can build a cycle, a dangling id or a broken invariant that later panics or hangs.

Out of scope: output differences from a browser with nothing worse (those are ordinary bugs), the generated entities.rs table beyond its use, and the build/supply-chain controls, which the assurance case covers separately.

Method

I read each file closely, then confirmed or refuted each suspicion with a small throwaway Rust program in a scratch crate outside the repository that depends on parsec by path. Timing runs were release builds (-j 2). Where a run could hang or overflow, I ran it on a worker thread with a chosen stack size and a watchdog, so an overflow or non-termination shows up as a result rather than taking the harness down. Every finding below is one I reproduced; I have not listed suspicions I could not trigger.

What I exercised directly: the editing API's cycle guard against the template-contents edge; selector matching against a very long descendant chain and against nesting; :has() and :nth-child(An+B of S) timing as input grows; the pattern attribute's regex against catastrophic backtracking; and a read of the unsafe block, the Send/Sync assertion, the span/offset arithmetic and the tokenizer's slicing.

Findings (all fixed)

F1: A template can be edited inside its own contents, and serialization then never ends (high)

insert_before's cycle check (edit.rs:112-119) walks parent links up from the proposed parent. A template's contents node hangs off Element.contents, not off any parent link, and its own parent is NONE. So append(contents, template) — both ordinary current ids, from template_contents and the public append — slips past the guard and makes a cycle: template → (contents) → template. outer_html and text push a template's children and its contents' children both, so they re-push the template without end: an unbounded hang. Confirmed: on a 64 MiB stack outer_html did not return in 3 s. This breaks the assurance case's promise that EditError::Cycle keeps a node from ending up inside itself. Fix: make the cycle check cross the contents edge (refuse inserting into a template's contents a node that is or contains that template).

Fixed: the cycle check climbs out of template contents through a map from each contents fragment to its template, built the first time an edit needs it and kept up to date. Both shapes, append(contents, template) and append(contents, ancestor), now return EditError::Cycle.

F2: A long descendant-chain selector overflows the stack while matching (high)

Cx::complex (css.rs:1618) recurses once per compound in a complex selector. MAX_DEPTH = 32 bounds functional-pseudo nesting only, not the number of compounds joined by combinators, and there is no limit on selector length. Confirmed: matching div×25000 b aborts with "fatal runtime error: stack overflow" on an 8 MiB stack (it returns fine at 20000). On a 2 MiB worker-thread stack the threshold is near 6000 compounds (~30 KB of selector text). A selector passed through from a user is untrusted, and an abort takes the process down. Fix: cap the compound count at parse time, or make complex iterative.

Fixed: matching a complex selector is a loop with its own small stack, so no selector is refused and none can overflow. 25,000 compounds on a 2 MiB thread now take 4.7 ms, and 100,000 work. Testing the fix turned up a second problem, which is fixed too: backtracking was exponential. x div div … (12 compounds) over 30 nested divs took 4.9 s; it now fails fast the way browsers do and takes 6 µs.

F3: :has() matching is quadratic in subtree size, with no time budget (medium)

select runs Cx::has (css.rs:2424) for each subject, and has walks the subject's whole subtree. On a deep chain of divs, div:has(b) is O(n²). Confirmed: 19 ms at n=2000 rising to 1.24 s at n=16000 (~190 KB), clean quadratic. The HTML is untrusted; the selector is fixed and ordinary. Unlike the tree builder, the selector API has no time budget — MatchOptions carries only a URL, and pattern_budget guards only the pattern attribute's regex. Fix: give matching an optional step/time budget, as parse_with has.

Fixed: :has() with one compound remembers, per query, which subtrees and runs of later siblings hold a match. div:has(b) over 16,000 nested elements went from 1.39 s to 1.2 ms. MatchOptions also has an optional budget, with try_select_with and try_matches_with returning MatchTimeout, for what's still super-linear: a :has() with more than one compound, or a descendant combinator over a very deep tree.

F4: :nth-child(An+B of S) is quadratic in sibling count, with no budget (medium)

In the Pseudo::Nth arm (css.rs:2254) an of S list skips the per-parent position cache, so each matching element re-tests S against every sibling. Confirmed: li:nth-child(2n of .x) over a flat list of li.x costs 36 ms at n=2000 and 505 ms at n=8000 — quadratic in sibling count, which a flat list makes easy to reach. Same missing-budget cause as F3, and the same fix.

Fixed: :nth-child(of S) and :nth-last-child(of S) keep a per-parent table of the siblings matching S. 8,000 siblings went from 516 ms to 0.5 ms. The of-type forms switch to the same table past 32 siblings.

What held up

  • The one unsafe block (tree.rs:source). The reference is to the heap bytes of a Box<str> set once and never rewritten during the parse; the box can move, the bytes can't; the reference is used only by the tokenizer inside run and doesn't outlive it. The only assignment to doc.src is in this function. The SAFETY comment is accurate.
  • Send/Sync. A compile-time assertion (lib.rs) pins Document and SelectorList as Send + Sync; both are plain owned data. The Cell and RefCell are confined to short-lived local matchers, never the shared types.
  • The pattern.rs regex engine. Its step limit, select-wide step budget, measured stack limit and depth cap together bound catastrophic backtracking; (a+)+$ against a non-matching value finished in ~16 ms.
  • Arithmetic and slicing. Offsets stay inside 30 bits under MAX_INPUT; character-reference and CSS-escape code points saturate or clamp and fall back to U+FFFD; tokenizer slices land on ASCII delimiters, always UTF-8 boundaries.
  • Depth. Serialization, text, select's walk and deep_clone use explicit stacks, so tree depth alone doesn't overflow — the selector-length case (F2) is the one stack-overflow I found.

Earlier fixes, recorded

Parsec #49 / Netweir #238 — crafted pages could crash the parser or make it crawl (merged). A review for Parsec found four hostile inputs. About 100 KB of nested markup inside a <select> copied into <selectedcontent> overflowed the thread's stack and aborted the process; the fix rewrote deep_clone in tree.rs to keep its own stack, producing the same nodes with the same ids in the same order. Three other patterns took seconds on a few hundred kilobytes because a step walked the stack of open elements once per tag — end tags matching nothing open, the same inside SVG, and options with no select open. The fix counts open elements by name (any_other_end, the foreign-content end-tag step and nearest_select return at once when nothing open could match), at a measured 1.4% cost on a 50-page corpus. Tests in tree.rs's hostile module parse 20,000 levels on a 256 KB stack and fail if four times the input takes over eight times as long. These are the first entries in this record.

What this review did not cover

  • Fuzzing beyond the current target. The existing target (fuzz/ fuzz_targets/parse.rs) parses arbitrary bytes as a document and a fragment and checks the tree's links; it runs five minutes nightly on inputs up to 4,096 bytes. It does not fuzz the selector parser/matcher or the editing API — the two places this review found trouble. A selector fuzzer and an edit-sequence fuzzer would be the natural next step.
  • Larger inputs. The quadratic selectors (F3, F4) were measured to ~190 KB and extrapolate by the square toward MAX_INPUT; I did not run them to the cap.
  • The url and memchr dependencies' internals, and the generated entities table's correctness.
  • Concurrency in practice. I confirmed the types are Send/Sync by construction but did not run a concurrent stress test.

Clone this wiki locally