1766283 - InlineTable does not provide any deterministic order (HashTable previous resize change the ordering of entries)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Nicolas B. Pierron [:nbp]]

This problem first appeared while using concurrent delazification, which caused differences while mixing its content with functions delazified on-demand.

The problem likely comes from the fact that we have a pool of InlineTable, which are using HashMap from which we clear the content but keep the same capacity.

The problem occurs as follows:

• The pools of InlineTable is dependent on the JSContext. Thus we have a different pool between the main thread and the helper thread.
• While parsing other functions, the InlineTable's HashMap from the NameCollectionPool might grow in capacity before being added back to the pool.
• When an InlineTable is taken out of the pool, the content is cleared but the capacity is not reset. Thus we might have different mHashShift, which both describe the capacity and how many bits are considered before considering that we have a collision.

As the number of bits considered register entries in the HashMap is different, we can have more collisions in non-resized HashMap and less in resized HashMap. When we have collisions, the order of entries depends on the order in which entries are added.

Thus, if we have 2 ParserAtomIndex p1 and p2 which respectly have hashes h1 and h2, where h2 is smaller than h1, and that there is a mask for which the upper bits are identical. Then it exists a HashTable size for which p1 appears before p2 (after collision), and a size for which p1 appears after p2 (without collision).

The problem is that the order is relied on the compute the slot index at which the names are saved. Thus when a function is generated with a given starting HashMap capacity, and referenced from inner functions with a different starting HashMap capacity, we would generate code which is using the wrong slot index.

The other issue is that the HashTable are purged on GC. Thus the parsing of a script, from another origin, could pre-populate the pool of HashTable with larger sizes, which could potentially remove existing HashTable collisions, and change the on-demand parsing, causing the original website to misbehave by changing slot indexes between the enclosing function and its inner functions.

Comment 1

[BugBot [:suhaib / :marco/ :calixte]]

The severity field for this bug is set to S3. However, the bug is flagged with the sec-high keyword.
:nbp, could you consider increasing the severity of this security bug?

For more information, please visit auto_nag documentation.

Comment 2

[Nicolas B. Pierron [:nbp]]

So far, the only way I managed to exhibit this issue, is either by using concurrent delazification which mix-up stencils produced through concurrent delazification and stencils produced through on-demand delazification.

I am still trying to figure out a minimal test case, relying only on on-demand delazification, which is expected, but hard.
I might have to add extra JS shell testing primitive to exhibit this behavior in cases where this does not represent a security issue.

I have a patch which works locally, to fix this issue in the JS shell. I am currently double checking if this fix works for all concurrent delazification issues seen while running Firefox.

Comment 3

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1766283 - Make hash table usage deterministic.

Comment 4

[Nicolas B. Pierron [:nbp]]

Comment on attachment 9274453 [details]
Bug 1766283 - Make hash table usage deterministic.

Security Approval Request

• How easily could an exploit be constructed based on the patch?: This is extremely hard.

Meeting all criterion of having a high number of variables / aliased variables, with nearby hashes, which becomes exploitable when swapped in an inner functions, is really hard.

• Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?: No
• Which older supported branches are affected by this flaw?: all
• If not all supported branches, which bug introduced the flaw?: None
• Do you have backports for the affected branches?: No
• If not, how different, hard to create, and risky will they be?: The patch should be the same.
• How likely is this patch to cause regressions; how much testing does it need?: This patch causes the hash table allocations to be discarded, such that we always go through the same process of resizing and filling the hash table in the same order.

The worse cases would be a slow down during parsing which should only be noticeable in generated JavaScript code which generates multiple functions with thousands of variables.

• Is Android affected?: Yes

Comment 5

[Nicolas B. Pierron [:nbp]]

I am able to minimize this issue into a test case relying on concurrent delazification using the instrumentation from Bug 1756003.

Comment 6

[Tom Ritter [:tjr]]

Comment on attachment 9274453 [details]
Bug 1766283 - Make hash table usage deterministic.

Approved to land and request uplift

Comment 7

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

Make hash table usage deterministic. r=arai
https://hg.mozilla.org/integration/autoland/rev/e61ebd2a248d773198cdc5104c9a59b7fc432981
https://hg.mozilla.org/mozilla-central/rev/e61ebd2a248d

Comment 8

[Ryan VanderMeulen [:RyanVM]]

Please nominate this for Beta & ESR approval when you get a chance.

Comment 9

[Nicolas B. Pierron [:nbp]]

Attachment: Bug 1766283 - Check bytecode differences between delazification modes.

This test case checks that the order of local variable is deterministic across
delazification modes, such that we can mix concurrent delazification with
on-demand delazification.

Comment 10

[Nicolas B. Pierron [:nbp]]

Comment on attachment 9274453 [details]
Bug 1766283 - Make hash table usage deterministic.

ESR Uplift Approval Request

• If this is not a sec:{high,crit} bug, please state case for ESR consideration:
• User impact if declined: A clever attacker can cause miss-interpretation of JS code of any other realms within a single process.
• Fix Landed on Version: 102
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): This is a one line change which force us to reclaim memory in addition to cleaning the state of a HashMap.
  By reclaiming memory, we make the usage of the HashMap deterministic.

Beta/Release Uplift Approval Request

• User impact if declined: A clever attacker can cause miss-interpretation of JS code of any other realms within a single process.
• Is this code covered by automated tests?: Yes
• Has the fix been verified in Nightly?: Yes
• Needs manual test from QE?: No
• If yes, steps to reproduce:
• List of other uplifts needed: None
• Risk to taking this patch: Low
• Why is the change risky/not risky? (and alternatives if risky): This is a one line change which force us to reclaim memory in addition to cleaning the state of a HashMap.
  By reclaiming memory, we make the usage of the HashMap deterministic.
• String changes made/needed: N/A
• Is Android affected?: Yes

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Comment on attachment 9274453 [details]
Bug 1766283 - Make hash table usage deterministic.

Approved for 101.0b6 and 91.10esr.

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/82f9add2b682

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-esr91/rev/a231c9c155cf

Comment 14

[BugBot [:suhaib / :marco/ :calixte]]

7 months ago, Tom Ritter [:tjr] placed a reminder on the bug using the whiteboard tag [reminder-test 2022-07-15] .

nbp, please refer to the original comment to better understand the reason for the reminder.