Security record: nish/regex — parsing, compiling and matching regular expressions
The record of nish/regex (#858): the parser of JavaScript's u-flag syntax,
the compiler to a Pike VM program and its reverse, the lazy DFA, the
prefilters, and the byte-window scan nish_regex_scan that starts a search.
It says what the module refuses and with what, what it caps and where the cap
is set, what it allocates, and the test that pins each property. It is written
with the code, against main at 804120e, and cites functions rather than
lines.
Result. One search (test, exec, find) is linear in the subject
whatever the pattern, the DFA's memory is bounded, and the C kernel reads
nothing outside its buffers. No pattern or subject panicked under fuzzing.
Iterating every match (findAll, count, replaceAll, split) is
quadratic in the subject when a preferred alternative reads far ahead before
a short one wins (REGEX-4, accepted, and now documented where linear time was
promised).
For a pattern the attacker writes, the audit found compile time
unbounded for nested exact repeats of an empty body (REGEX-1), parse time
quadratic in a class's ranges (REGEX-2) and in named groups (REGEX-3), and
compile memory of about 424 MiB for a 10 KB pattern (REGEX-5); each is fixed
with a cap or a cut, and a row of tests/link/std_regex pins it. Six
findings are fixed (one Medium, five Low, REGEX-7 below) and one is accepted
(Medium).
Property escapes (\p{…}, \P{…}) and Unicode case folding under i came
later (#1048). They grow a pattern's classes from tables rather than from its
bytes, so they get their own cap: at most REGEX_MAX_PROPERTY_RANGES
(100,000) ranges per pattern, counted across every escape and every folded
class (REGEX-7). Sorting those ranges is O(r log r) above 64 of them, so the
cap bounds the work as well as the memory.
Scope
| File | Functions |
|---|---|
std/regex.ts |
RegexParser (parseAlt, parseGroup, parseBraces, parseClass, parseClassAtom, addRange, finishClass, fail; the property escapes addProperty, countPropertyRanges, tableNumber, regexPropertyEntry; the case folding charNode, foldSeek, foldStepOf, foldRanges, rangesHave, regexFoldTarget, regexFixedAt, regexSpanAt, regexFoldsIn; the word helpers under i regexFoldWordBefore, regexFoldWordAt, regexContextMask, assertHolds, dAssert; storeRanges, mergeSort); the compiler (emit, compileNode, compileIteration, compileEmptyCheckedRepeat, compileMarked); regexSortPoints, regexScanFrom; Regex (build, findPrefilters, findInner, findScan, scanTo, dSkipTo, ctxBefore, ctxAt, dfaForward, dfaReverse, dfaInner, run, vm, test, exec, find, findAll, count, replace, replaceAll, replaceMatches, slotText, expand, split); regexCompile, regexEscape |
runtime/runtime-simd.c |
nish_regex_scan, nish_scan_pick (scalar, AVX2, NEON and WASM SIMD paths) |
runtime/nish.h |
the nish_regex_scan contract |
src/kernels.ts |
the lowering of regexScanFrom to nish_regex_scan |
scripts/gen-regex-unicode.mjs |
the generator of the property and folding tables in std/regex.ts from the pinned (sha256) Unicode 16.0.0 data files, and of the Node oracle tests/link/std_regex_unicode/oracle.ts |
Out of scope: lookaround and backreferences, which are refused at compile
time; the Unicode data itself, which the generator takes as published once its
hash matches; and the callers' use of matches. Folding never crosses into
ASCII (K does not match U+212A KELVIN SIGN, s does not match U+017F) — a
documented difference from JavaScript, not a gap; under i the two are word
characters to \w, \W, \b and \B, as JavaScript's iu has them, and
tests/link/std_regex_unicode pins that view of \w, \W, \b and \B against Node; nish's own answers elsewhere are pinned in tests/link/std_regex.
Threat model
The attacker writes the subject: every byte, in any length, including invalid UTF-8. In a separate case the attacker also writes the pattern, for a program that compiles user-supplied patterns, and the flags.
A win is any of:
- time superlinear in the subject;
- a compile whose time or memory the pattern's length does not bound;
- memory without a bound the program set;
- a panic;
- a read outside the subject or the mask array in
nish_regex_scan.
The program calling the module is trusted. Its choice of pattern, in the first case, is its own.
Findings
| Id | Severity | Where | Finding | Disposition |
|---|---|---|---|---|
| REGEX-1 | Medium | compileNode (repeat case), compileEmptyCheckedRepeat, emit |
An exact repeat of a body that emits no instruction ((?:), a{0}) still compiles the body min times. The instruction cap is only checked in emit, so nesting them is 1000^L work for a 10·L-byte pattern: 7.4 s at L = 3, beyond 30 s at L = 4. |
Fixed: both min loops stop once an iteration emitted nothing, since every later copy emits nothing too. Tests: the rows "an empty body repeated 1000^4 times compiles" and "a{0} repeated 1000^3 times compiles" (the first did not finish in 30 s before) |
| REGEX-2 | Low | parseClass, finishClass |
A class's non-ASCII ranges are insertion-sorted, Θ(r²) for a descending list, and nothing caps r: 2.5 s for an 80,000-range, 720 KB class. | Fixed: a class of more than REGEX_MAX_CLASS_RANGES (10,000) ranges is refused, "a class has more than 10000 ranges". Tests: the rows "a class of 10001 ranges" and "a class of 10000 ranges compiles" |
| REGEX-3 | Low | parseGroup, build |
The duplicate-name check scans every earlier name, and the group count is only refused in build, after parsing: 1.25 s for 40,000 named groups. |
Fixed: parseGroup refuses a capturing group past REGEX_MAX_GROUPS (1,024), "too many groups", so the name scan is at most 1,024² comparisons. Tests: the rows "1025 groups" and "500 groups compile" |
| REGEX-4 | Medium | findAll, count, replaceMatches, split |
Leftmost-first iteration runs one search per match. When a preferred branch reads to the end before a short branch wins (.*X|a, <[^>]*>|<), the iteration is O(n²) in the subject: 1.5 s at 40,000 bytes, 9.2 s at 100,000. One search stays linear. The module header, the guide and std/README.md promised linear time "whatever the pattern". |
Accepted: inherent to leftmost-first iteration, the same bound RE2 and Rust's regex document. The module header, std/README.md and the guide's regular-expressions section now say one search is linear and iterating can be quadratic, and how to bound the long branch. |
| REGEX-5 | Low | build, compileIteration |
Groups under {0} emit nothing, yet every enclosing iteration's CLEAR clears their slots. build sizes the VM stack at one frame per cleared slot times 2^levels: 424 MiB for a 10 KB pattern, held for the Regex's life. It is bounded (about 8 × 4194304 frames) but far above the documented 1 MiB. |
Fixed: build refuses a pattern whose stack frames would pass REGEX_MAX_SLOT_TABLE, "too many groups for the pattern's size", before it allocates them. Never-set groups still go into CLEAR; the cap is what bounds the memory. Test: the row "a backtrack stack past the slot table" |
| REGEX-6 | Low | src/kernels.ts (the regexScanFrom comment) |
The comment states a mask array of 32 bytes per position. The contract in runtime/nish.h, and the kernel, need 288 bytes per position. No caller is affected. |
Fixed: the comment states 288 bytes a position |
| REGEX-7 | Low | addProperty, foldRanges, finishClass |
Found while adding them: a property escape adds up to about 700 ranges from 9 pattern bytes (\p{L}), and a class under i adds its folded orbits, so the class cap of 10,000 bounds neither a pattern of many escapes outside classes nor the ranges folding adds after it. |
Fixed: countPropertyRanges refuses a pattern whose escapes and folding add more than REGEX_MAX_PROPERTY_RANGES (100,000) ranges, "property escapes and case folding add more than 100000 ranges"; a class's own ranges stay under REGEX_MAX_CLASS_RANGES before folding; storeRanges merge-sorts more than REGEX_INSERTION_SORT (64) ranges, so the sort is O(r log r). Nothing is decoded ahead of time: a compile reads the folding table in place, REGEX_FOLD_INDEX (every sixteenth folding code point) bounding each lookup to one block of at most sixteen entries, with the table's size fixed by the generator, and only for a pattern that folds a code point in REGEX_FOLD_SPANS. Tests: the rows "property escapes past 100000 ranges", "case folding past 100000 ranges" and "property escapes just under 100000 ranges compile" (147 \p{L}, one escape short of the cap) |
Properties verified
One search is linear in the subject, whatever the pattern.
- The DFA and the Pike VM follow every alternative at once.
(a+)+$,(a|a)*cand(\b\w+\b\s*)+$on 4 MB run in about 15 ms.- When the DFA gives up (
[ab]*a[ab]{20}on random text), the VM fallback is linear: 634 ms at 1.6 MB, with memory flat. dfaInnerabandons an inner literal whose waste passes twice its gain plusDFA_INNER_SLACK, so the inner-literal search stays linear.- Pinned by: the suite's linear-time rows in
tests/link/std_regex. They are bounded only by the test's timeout, and none covers the VM fallback.
The DFA's memory is bounded. It holds at most 2,048 states and 262,144 transitions, and its pool is at most max(2 × total, 16,384). On a flush or a give-up it falls back to the VM. Pinned by: none. What would: a row counting matches of a state-explosive pattern over 1 MB.
Pattern errors are refused, not panicked on.
- A repeat count over 1000 is refused, as are nesting deeper than 250 and more than 100,000 instructions.
- Malformed syntax gets a refusal naming its byte: an unclosed class or group, a lone quantifier, a bad escape, a bad range, a bad or duplicate name, an unknown property name or value (
\p,\p{Foo},\p{gc=Foo}), and a property escape as a range end ([\p{L}-z]). - More than 1,024 groups, a class of more than 10,000 ranges, and property escapes and folding adding more than 100,000 ranges are refused, and so is a backtrack stack past the slot table ("too many groups for the pattern's size", in
build). - A repeat whose body compiles to nothing ends its loop rather than repeating it (REGEX-2).
- Fuzzing found no panic and no disagreement between
test,exec,countandfindAll:- 2,000 + 8 × 40,000 token patterns with every flag combination;
- 4 × 100,000 raw-byte patterns including 0x80, 0xE2 and 0xFF;
- subjects with invalid UTF-8, U+2028 and truncated sequences;
execfrom every offset;- malformed replacement templates.
- Pinned by: the error rows in
tests/link/std_regex(for exampleregex: a repeat count is over 1000 at byte 1), and the compile-bound rows: "a class of 10001 ranges", "1025 groups", "a backtrack stack past the slot table" and "an empty body repeated 1000^4 times compiles". The 250-depth and instruction caps have no row. No fuzz target is in tree.
Iteration terminates. After an empty match, findAll, count, replaceAll and split step one character (regexWidthAt), which is at least one byte. Pinned by: the suite's empty-match rows.
Templates are bounded. expand reads $< without > and $NN past the group count literally, and slotText bounds its index. Pinned by: the suite's replacement rows.
nish_regex_scan reads only inside the subject and the masks.
- Each path loads only behind a guard:
- the scalar loop, behind
i + d ≤ n; - the AVX2 loop, behind
i + 31 + o + w ≤ n, with width 4 run by the width-3 copy; - the NEON and WASM loops, behind
i + 15 + o + w ≤ n.
- the scalar loop, behind
nish_scan_pickrefusesc + d > n.- Table reads stay under 288 × depth bytes.
- An empty subject loads nothing.
findScanandscanTokeep the contract: depth 1..8, width at most 3, offset + width ≤ depth,from≤ length.- Pinned by: the
simdregex-scan checks, which compare each vector path with the scalar one. None places a match against an unmapped page.
Tests
-
link/${name}: exits with ${wantCode} and stdout matches expected.out—tests/link/std_regex(JavaScript-generated rows, error rows, the compile-bound rows, prefilter rows, the linear-time rows, the property-escape and folding rows) andtests/link/std_regex_f64(the same suite under--number-mode f64);tests/link/std_regex_unicode(every property escape, every folded code point and a set of classes underi, against Node'sRegExpwithuandiuover a sample of every code point) -
simd: ${label}: ${said}, wheresaidis the agreement driver's report line (itsregex-scan:prefix removed), withlabelone of:regex-scan native ${process.arch}regex-scan wasm32-wasi, the scalar base pathregex-scan wasm32-wasi -msimd128regex-scan aarch64 through binfmt, the NEON path
The driver is
tests/simd/regex-scan.c. -
simd: ${label} names ${paths} as the paths it ran— the cross-compiled labels

