Closed Bug 2078864 Opened 1 month ago Closed 26 days ago

irregexp: wrong null match for lazy match-anything loop in an alternation (Fail() emitted by BoyerMooreLookahead::EmitSkipInstructions)

Categories

(Core :: JavaScript Engine, defect, P3)

defect

Tracking

()

RESOLVED FIXED
160 Branch
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

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

  1. 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/.
  2. 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.
  3. 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.
  4. 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

  1. 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.
  2. 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.
  3. Re-run with "--differential-testing" added to both flag lists. Result: differs=true with the same exit codes.
  4. Optional: flags_a = [] (default flags) against flags_b = ["--regexp-warmup-threshold=0"] also gives differs=true.
  5. 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]
Attached patch fix.patch — — Splinter Review
Attached file crash_stack.txt —
Attached file testcase.js —
Attached file README.txt —

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.

Group: core-security → javascript-core-security
Blocks: sm-security
Severity: -- → S3
Priority: -- → P3

This is fixed upstream by this patch. We should be able to pull in the fix in the next irregexp update.

This is just a correctness issue.

Group: javascript-core-security
Keywords: sec-other

This is fixed by the irregexp update in bug 2083707.

Assignee: nobody → iireland
Status: UNCONFIRMED → ASSIGNED
Ever confirmed: true
Status: ASSIGNED → RESOLVED
Closed: 26 days ago
Resolution: --- → FIXED
Target Milestone: --- → 160 Branch
QA Whiteboard: [qa-triage-done-c161/b160]
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: