irregexp: wrong null match for lazy match-anything loop in an alternation (Fail() emitted by BoyerMooreLookahead::EmitSkipInstructions)
Categories
(Core :: JavaScript Engine, defect, P3)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox160 | --- | fixed |
People
(Reporter: bugmon, Assigned: iain)
References
(Blocks 1 open bug)
Details
(Keywords: testcase)
Attachments
(4 files, 1 external file)
LoopChoiceNode::IsImplicitSearchLoop identifies the compiler-prepended unanchored-search loop by shape only, so a user-written lazy match-anything loop ([^]*?, or .*? with the s flag) is accepted as well. ChoiceNode::EmitOptimizedUnanchoredSearch then runs BoyerMooreLookahead::EmitSkipInstructions on that loop, which emits an unconditional Fail() when a lookahead position has no possible character. For a user-written loop inside an alternation this ends the whole match instead of backtracking to the sibling alternative, so /[^]*?a^|b/.exec("cb") returns null instead of ["b"] at index 1. Whether the Fail() is emitted depends on character frequencies sampled from the subject string at compile time, so the bytecode and native tiers of one RegExp can return different results.
A web page author can make a RegExp return null for input that the specification says matches by writing a pattern with a lazy match-anything loop followed by a branch that cannot match after the start (such as a^) alongside another alternative. The demonstrated effect is an incorrect, false-negative match result that occurs with default flags. No assertion failure, sanitizer report or memory corruption was observed in the debug shell.
Build Info
- Branch: main
- Revision: b4b9efb6ee130740a94caf46ffff0625af1d51db
- Timestamp: 2026-10-04T19:31:16+00:00
Affected Code
File: js/src/irregexp/imported/regexp-compiler.cc, line 4432-4443
// The machine-generated `.*?` loop that PreprocessRegExp prepends to every
// unanchored, non-sticky pattern to retry the match at each start position.
// Recognized structurally: a two-alternative loop whose second alternative is
// an omnivorous (matches-anything) text looping back to the loop. A
// user-written loop of that exact shape (e.g. /[\s\S]*?foo/) matches too, which
// is harmless -- its loop-exit backtrack has the same rescan-forward behavior.
bool LoopChoiceNode::IsImplicitSearchLoop(Compiler* compiler) {
if (alternatives_->length() != 2) return false;
GuardedAlternative alt1 = alternatives_->at(1);
if (alt1.guards() != nullptr && alt1.guards()->length() != 0) return false;
return alt1.node()->GetSuccessorOfOmnivorousTextNode(compiler) == this;
}
File: js/src/irregexp/imported/regexp-compiler.cc, line 4575-4578, 4602-4628
LoopChoiceNode* loop_choice = AsLoopChoiceNode();
if (loop_choice == nullptr || !loop_choice->IsImplicitSearchLoop(compiler)) {
return eats_at_least;
}
...
if (bm == nullptr && v8_flags.regexp_quick_check) {
eats_at_least = std::min(kMaxLookaheadForBoyerMoore, EatsAtLeast(false));
if (eats_at_least >= 1) {
bm = zone()->New<BoyerMooreLookahead>(eats_at_least, compiler, zone());
GuardedAlternative alt0 = alternatives_->at(0);
alt0.node()->FillInBMInfo(isolate, 0, kRecursionBudget, bm, false);
}
}
if (bm != nullptr) {
...
if (EmitOneOfMasked3Search(compiler, bm) ||
bm->EmitSkipInstructions(macro_assembler)) {
// BM owns the search; do not attempt the inline SkipUntil* scan paths.
*bm_scan_emitted = true;
}
}
File: js/src/irregexp/imported/regexp-compiler.cc, line 3955-3973
if (!FindWorthwhileInterval(&min_lookahead, &max_lookahead)) {
TRACE_COMPILER(compiler_, " No worthwhile interval found");
return false;
}
...
for (int i = min_lookahead; i <= max_lookahead; i++) {
BoyerMoorePositionInfo* map = bitmaps_->at(i);
if (map->map_count() == 0) {
// If we have a position where no characters can match then we just can't
// match.
masm->Fail();
return true;
}
File: js/src/irregexp/imported/regexp-compiler.cc, line 1808-1814
void AssertionNode::FillInBMInfo(Isolate* isolate, int offset, int budget,
BoyerMooreLookahead* bm, bool not_at_start) {
// Match the behaviour of EatsAtLeast on this node.
if (assertion_type() == AT_START && not_at_start) return;
on_success()->FillInBMInfo(isolate, offset, budget - 1, bm, not_at_start);
SaveBMInfo(bm, not_at_start, offset);
}
File: js/src/irregexp/imported/regexp-compiler.cc, line 6192-6203
static void VisitAssertion(AssertionNode* that) {
EatsAtLeastInfo eats_at_least = *that->on_success()->eats_at_least_info();
if (that->assertion_type() == AssertionNode::AT_START) {
...
eats_at_least.from_not_start = UINT8_MAX;
}
that->set_eats_at_least_info(eats_at_least);
}
File: js/src/irregexp/RegExpAPI.cpp, line 394-407, 837
static void SampleCharacters(Handle<JSLinearString*> sample_subject,
RegExpCompiler& compiler) {
static const int kSampleSize = 128;
int chars_sampled = 0;
int length = sample_subject->length();
int half_way = (length - kSampleSize) / 2;
for (int i = std::max(0, half_way); i < length && chars_sampled < kSampleSize;
i++, chars_sampled++) {
compiler.frequency_collator()->CountCharacter(
sample_subject->latin1OrTwoByteChar(i));
}
}
...
SampleCharacters(input, compiler);
The user-written loop [^]*? passes the structural test in IsImplicitSearchLoop. Its body a^ reports an eats-at-least of UINT8_MAX when not at the start (VisitAssertion), so the Boyer-Moore lookahead is built with 8 positions; AssertionNode::FillInBMInfo returns without filling positions after a, leaving them with map_count() == 0. If FindWorthwhileInterval accepts the interval (it uses character frequencies from the subject sampled by SampleCharacters), EmitSkipInstructions emits Fail(). With sample "cb" the emitted program for the loop head is Fail();; with sample "ab" it is SkipUntilChar(... character='a' ...) and the result is correct (both observed with --trace-regexp-assembler).
Exploit Chain
- Script creates a RegExp whose alternation contains a user-written lazy match-anything loop followed by a branch that cannot match once a character has been consumed, e.g. /[^]*?a^|b/.
- The first exec is called on a subject that does not contain the loop's following literal ("cb"); the pattern is compiled with that subject as the frequency sample, FindWorthwhileInterval accepts the Boyer-Moore interval, and EmitSkipInstructions emits Fail() at the head of the user-written loop.
- Any exec on that compiled code reaches Fail() before the second alternative is tried and returns null, including for "ab" and "cb", where the specification requires ["b"] at index 1.
- If the RegExp is recompiled for the native tier with a subject containing 'a' ("ab" with --regexp-warmup-threshold=0), no interval is chosen, correct code is generated, and the same exec returns ["b"] at index 1, so the two configurations disagree.
Steps to Reproduce
- Build the SpiderMonkey debug shell from an unmodified tree with /app/mozconfigs/mozconfig.js.linux.debug (binary: /firefox/obj-js-debug/dist/bin/js). No patches, prefs or environment variables are needed.
- Run testcase.js with js_shell_differential_evaluator using shell_a = shell_b = /firefox/obj-js-debug/dist/bin/js, flags_a = ["--no-native-regexp"], flags_b = ["--regexp-warmup-threshold=0"]. Result: differs=true; shell_a exits 3 with "Error: expected match 'b' at index 1, got null", shell_b exits 0.
- Re-run with "--differential-testing" added to both flag lists. Result: differs=true with the same exit codes.
- Optional: flags_a = [] (default flags) against flags_b = ["--regexp-warmup-threshold=0"] also gives differs=true.
- Optional single-configuration check: /[^]*?a^|b/.exec("cb") returns null under default flags and under --regexp-warmup-threshold=0; the expected result is ["b"] at index 1.
Security Impact
- Severity: Low
- Attacker capability: Cause RegExp exec to return null (no match) for input that the specification says matches, for patterns containing a lazy match-anything loop followed by a branch that cannot match after the start, inside an alternation. Only incorrect match results were observed; no assertion failure, sanitizer report or memory corruption was produced.
- Preconditions: The pattern must have the specific shape described (e.g. /[^]?a^|b/ or /.?a^|b/s), and the subject used when the pattern is compiled must make the Boyer-Moore interval look worthwhile (for the testcase, a subject without 'a'). Reachable with default shell flags.
ASAN Report
No sanitizer report: this is a js_differential finding and the proof is the evaluator divergence below (verifier's own runs, unmodified tree, debug shell).
Run 1: differs=true
shell_a argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--no-native-regexp","/tmp/fx_audit_jsdiff_jlj48apk/testcase.js"]
shell_a exit_code: 3, timed_out: false, succeeded: false
shell_a stderr:
/tmp/fx_audit_jsdiff_jlj48apk/testcase.js:5:9 Error: expected match 'b' at index 1, got null
Stack:
@/tmp/fx_audit_jsdiff_jlj48apk/testcase.js:5:9
shell_b argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--regexp-warmup-threshold=0","/tmp/fx_audit_jsdiff_jlj48apk/testcase.js"]
shell_b exit_code: 0, timed_out: false, succeeded: true
Run 2 (--differential-testing on both sides): differs=true
shell_a argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--differential-testing","--no-native-regexp","/tmp/fx_audit_jsdiff_gb5dk8el/testcase.js"]
shell_a exit_code: 3, timed_out: false, succeeded: false
shell_a stderr:
/tmp/fx_audit_jsdiff_gb5dk8el/testcase.js:5:9 Error: expected match 'b' at index 1, got null
Stack:
@/tmp/fx_audit_jsdiff_gb5dk8el/testcase.js:5:1
shell_b argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--differential-testing","--regexp-warmup-threshold=0","/tmp/fx_audit_jsdiff_gb5dk8el/testcase.js"]
shell_b exit_code: 0, timed_out: false, succeeded: true
Run 3 (default flags vs eager regexp tier-up, --differential-testing on both sides): differs=true
shell_a argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--differential-testing","/tmp/fx_audit_jsdiff_faja_ghp/testcase.js"]
shell_a exit_code: 3, timed_out: false, succeeded: false
shell_b argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--differential-testing","--regexp-warmup-threshold=0","/tmp/fx_audit_jsdiff_faja_ghp/testcase.js"]
shell_b exit_code: 0, timed_out: false, succeeded: true
Wrong side: shell_a. /[^]*?a^|b/.exec("ab") must be ["b"] at index 1: the first alternative cannot match because non-multiline ^ follows a consumed 'a'; the second alternative matches 'b' at index 1.
--trace-regexp-assembler, --no-native-regexp, first exec on "cb" (result null):
PushBacktrack(label[1ec14348]);
label[0565dc58]: (Bind)
PushCurrentPosition();
WriteCurrentPositionToRegister(register=0,cp_offset=0);
PushBacktrack(label[1ec13a48]);
label[0565d7b8]: (Bind)
Fail();label[0565d888]: (Bind)
CheckPosition(cp_offset=0, label[00000000]);
AdvanceCurrentPosition(by=1);
GoTo(label[0565d7b8]);
Same flags, first exec on "ab" (result ["b"]@1):
label[c15147b8]: (Bind)
SkipUntilChar(cp_offset=0, advance_by=1, character=0x0061(a), bounds_check_offset=0, on_match=label[e140b760], on_no_match=label[e140b760]
| Reporter | ||
Comment 1•1 month ago
|
||
| Reporter | ||
Comment 2•1 month ago
|
||
| Reporter | ||
Comment 3•1 month ago
|
||
| Reporter | ||
Comment 4•1 month ago
|
||
| Reporter | ||
Comment 5•1 month ago
|
||
This bug was filed automatically by an AI-powered security testing tool. The analysis, testcase, and any suggested patches were generated by an AI model and have NOT been verified by a human.
Please review all details carefully before triaging. The issue was confirmed by an independent verifier, but for non-ASAN issues, the verifier has been made less strict. Additionally, the root cause analysis and suggested fix may contain errors.
Updated•1 month ago
|
Updated•1 month ago
|
| Assignee | ||
Comment 6•1 month ago
|
||
This is fixed upstream by this patch. We should be able to pull in the fix in the next irregexp update.
| Assignee | ||
Comment 7•27 days ago
|
||
This is just a correctness issue.
| Assignee | ||
Comment 8•27 days ago
|
||
This is fixed by the irregexp update in bug 2083707.
Updated•27 days ago
|
Comment 10•26 days ago
|
||
| bugherder | ||
Updated•18 days ago
|
Description
•