2078766 - Array.prototype.sort skips calling a pattern-matched `a - b` comparator and converts each element once via ToNumber (observable spec divergence)

Status: UNCONFIRMED

(Core :: JavaScript: Standard Library, defect, P3)

Description

[Bugmon [:jkratzer for issues]]

ArraySortPrologue in js/src/builtin/Array.cpp calls MatchNumericComparator, which inspects the comparator's bytecode and, when it is exactly GetArg; GetArg; Sub; Return over arguments 0 and 1, routes the sort to ArraySortWithoutComparator instead of the comparator path. For element lists that are not all int32, that function calls SortNumerically, which runs ToNumber once on each element and sorts the cached doubles; the user comparator is never invoked. When elements are objects with a user-defined valueOf, the number and order of valueOf calls differs from what any sequence of comparator calls can produce: three elements yield three valueOf calls, where each comparator call would perform two.

A web page script can observe Array.prototype.sort behaviour that ECMA-262 does not permit by sorting objects with a side-effecting valueOf using a comparator of the form (a, b) => a - b or (a, b) => b - a. The demonstrated effect is limited to a wrong count and order of user-visible conversion calls; the sorted result is correct, and no crash, assertion failure or memory-safety effect was observed. The behaviour is identical with the JIT disabled, with Baseline eager and with Ion eager, so it is not a JIT miscompilation.

Build Info

• Branch: main
• Revision: bf9757d91e2e53b8ab836f2a08bf4c0275fdcd23
• Timestamp: 2026-10-02T21:18:24+00:00

Affected Code

File: js/src/builtin/Array.cpp, line 1946-1978

  jsbytecode* pc = script->code();

  uint16_t arg0, arg1;
  if (JSOp(*pc) != JSOp::GetArg) {
    return Match_None;
  }
  arg0 = GET_ARGNO(pc);
  pc += JSOpLength_GetArg;

  if (JSOp(*pc) != JSOp::GetArg) {
    return Match_None;
  }
  arg1 = GET_ARGNO(pc);
  pc += JSOpLength_GetArg;

  if (JSOp(*pc) != JSOp::Sub) {
    return Match_None;
  }
  pc += JSOpLength_Sub;

  if (JSOp(*pc) != JSOp::Return) {
    return Match_None;
  }

  if (arg0 == 0 && arg1 == 1) {
    return Match_LeftMinusRight;
  }

  if (arg0 == 1 && arg1 == 0) {
    return Match_RightMinusLeft;
  }

  return Match_None;

File: js/src/builtin/Array.cpp, line 2349-2367

  do {
    ComparatorMatchResult comp = Match_None;
    if (comparefn.isObject()) {
      comp = MatchNumericComparator(cx, &comparefn.toObject());
      if (comp == Match_Failure) {
        return false;
      }
      if (comp == Match_None) {
        // Pattern matching failed.
        break;
      }
    }
    if (!ArraySortWithoutComparator(cx, obj, length, comp)) {
      return false;
    }
    d->setReturnValue(obj);
    *done = true;
    return true;
  } while (false);

File: js/src/builtin/Array.cpp, line 2269-2281

    } else {
      if (allInts) {
        MOZ_ALWAYS_TRUE(vec.resize(n * 2));
        if (!MergeSort(vec.begin(), n, vec.begin() + n,
                       SortComparatorInt32s[comp])) {
          return false;
        }
      } else {
        if (!SortNumerically(cx, &vec, n, comp)) {
          return false;
        }
      }
    }

File: js/src/builtin/Array.cpp, line 2083-2099

  /* Convert Values to numerics. */
  for (size_t i = 0; i < len; i++) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    double dv;
    if (!ToNumber(cx, vec[i], &dv)) {
      return false;
    }

    numElements[i] = {dv, i};
  }

  /* Sort Values in vec numerically. */
  return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
                        SortComparatorNumerics[comp], vec);

The fast path is selected purely from the comparator's bytecode shape, without regard to whether the elements' numeric conversion is observable. SortNumerically then performs one ToNumber per element in index order and never calls the comparator. Both entry points (js::array_sort and js::ArraySortFromJit) go through ArraySortPrologue, which matches the observation that all tiers behave the same. A comparator that does not match the pattern (for example (a, b) => +(a - b)) takes the generic path and produces six valueOf calls for the same input, as V8 does.

Exploit Chain

1. Script creates an array of objects whose valueOf has an observable side effect (here, incrementing a counter).
2. Script calls arr.sort((a, b) => a - b). ArraySortPrologue calls MatchNumericComparator, which matches the comparator bytecode and returns Match_LeftMinusRight.
3. ArraySortWithoutComparator sees non-int32 elements and calls SortNumerically, which calls ToNumber once per element (one valueOf call each, in index order 3,1,2 in my instrumented run) and sorts the cached doubles without calling the comparator.
4. The script observes 3 valueOf calls. Under ECMA-262, sorting proceeds by calls to SortCompare, each of which performs Call(comparefn, undefined, << x, y >>); with a - b that is two valueOf calls per comparison, so the total must be even. V8 performs 6 calls. The demonstrated impact ends at this observable divergence.

Steps to Reproduce

1. Build the SpiderMonkey debug shell from the unmodified tree with /app/mozconfigs/mozconfig.js.linux.debug (no patches, no prefs).
2. Run testcase.js through js_shell_differential_evaluator with shell_a=/firefox/obj-js-debug/dist/bin/js (flags --no-threads) and shell_b=/app/tools/d8/d8 (engine v8). Result: differs: true; SpiderMonkey exits 3 with Error: valueOf ran an odd number of times: 3, d8 exits 0.
3. Re-run with flags_a=["--no-threads", "--differential-testing"]. Result: differs: true with the same error and exit codes.
4. Optional confirmation of root cause: replace the comparator with (a, b) => +(a - b); SpiderMonkey then makes 6 valueOf calls and the testcase passes. The 3-call result is the same under --no-jit-backend, --baseline-eager and --ion-eager --no-threads.

Security Impact

• Severity: Low
• Attacker capability: Web content can observe that Array.prototype.sort with a comparator shaped exactly like a - b or b - a does not call the comparator and instead converts each element once, producing a count and order of valueOf/Symbol.toPrimitive side effects that the specification does not allow. No memory corruption, assertion failure, information disclosure or wrong sort result was demonstrated; this is a conformance defect, and Low is the lowest rating the schema offers.
• Preconditions: None beyond running script. The array must contain at least one non-int32, non-undefined element so that SortNumerically rather than the int32 path is taken, and the comparator's bytecode must be exactly two GetArg ops, Sub, Return.

ASAN Report

No sanitizer report: this is a js_differential finding, and the proof is the exit-status divergence below (my own runs).

=== Run 1 (without --differential-testing) === differs: true
shell_a argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--no-threads","/tmp/fx_audit_jsdiff_swmlufus/testcase.js"]
shell_a engine: spidermonkey, exit_code: 3, timed_out: false, succeeded: false
shell_a stderr:
/tmp/fx_audit_jsdiff_swmlufus/testcase.js:11:9 Error: valueOf ran an odd number of times: 3
Stack:
  @/tmp/fx_audit_jsdiff_swmlufus/testcase.js:11:9
shell_b argv: ["/app/tools/d8/d8","/tmp/fx_audit_jsdiff_swmlufus/testcase.js"]
shell_b engine: v8, exit_code: 0, timed_out: false, succeeded: true, stderr empty

=== Run 2 (with --differential-testing on the SpiderMonkey side) === differs: true
shell_a argv: ["/firefox/obj-js-debug/dist/bin/js","--fuzzing-safe","--no-threads","--differential-testing","/tmp/fx_audit_jsdiff_88yek8fr/testcase.js"]
shell_a engine: spidermonkey, exit_code: 3, timed_out: false, succeeded: false
shell_a stderr:
/tmp/fx_audit_jsdiff_88yek8fr/testcase.js:11:9 Error: valueOf ran an odd number of times: 3
Stack:
  @/tmp/fx_audit_jsdiff_88yek8fr/testcase.js:11:1
shell_b argv: ["/app/tools/d8/d8","/tmp/fx_audit_jsdiff_88yek8fr/testcase.js"]
shell_b engine: v8, exit_code: 0, timed_out: false, succeeded: true, stderr empty

=== Instrumented comparison (valueOf call count / order for [box(3), box(1), box(2)]) ===
SpiderMonkey (default, --no-jit-backend, --baseline-eager, --ion-eager --no-threads all identical):
  (a, b) => a - b        : calls=3 order=3,1,2
  (a, b) => b - a        : calls=3 order=3,1,2
  (a, b) => +(a - b)     : calls=6 order=3,1,3,2,1,2
d8:
  (a, b) => a - b        : calls=6 order=1,3,2,3,2,1
  (a, b) => b - a        : calls=6 order=3,1,1,2,3,2
  (a, b) => +(a - b)     : calls=6 order=1,3,2,3,2,1

Comment 1

[Bugmon [:jkratzer for issues]]

Attachment: fix.patch

Comment 2

[Bugmon [:jkratzer for issues]]

Attachment: crash_stack.txt

Comment 3

[Bugmon [:jkratzer for issues]]

Attachment: testcase.js

Comment 4

[Bugmon [:jkratzer for issues]]

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.