916635 - Recursive graph traversal in RangeAnalysis

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Dan Gohman [:sunfish]]

Attachment: avoid-recursion.patch

RangeAnalysis::markBlocksInLoopBody uses recursion to visit all the basic blocks in a loop. Since there's no explicit limit on how many blocks a loop might contain, this could theoretically overflow the stack (though in practice, usually something else fails first).

Comment 1

[Brian Hackett [Laid off!]]

Comment on attachment 805109 [details] [diff] [review]
avoid-recursion.patch

Review of attachment 805109 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit/RangeAnalysis.cpp
@@ +1300,1 @@
>  RangeAnalysis::markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current)

Maybe rename |current| to |backedge|?

@@ +1400,5 @@
>  
>          for (MDefinitionIterator iter(block); iter; iter++) {
>              MDefinition *def = *iter;
>              if (def->isBoundsCheck() && def->isMovable()) {
>                  if (tryHoistBoundsCheck(header, def->toBoundsCheck()))

This |if| should have {} now.

@@ +1769,5 @@
>              IonSpew(IonSpew_Range, "computing range on %d", def->id());
>              SpewRange(def);
>          }
>  
>          if (block->isLoopHeader())

Ditto.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: avoid-recursion.patch

(In reply to Brian Hackett (:bhackett) from comment #1)
> Comment on attachment 805109 [details] [diff] [review]
> avoid-recursion.patch
> 
> Review of attachment 805109 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jit/RangeAnalysis.cpp
> @@ +1300,1 @@
> >  RangeAnalysis::markBlocksInLoopBody(MBasicBlock *header, MBasicBlock *current)
> 
> Maybe rename |current| to |backedge|?

Done.

> @@ +1400,5 @@
> >  
> >          for (MDefinitionIterator iter(block); iter; iter++) {
> >              MDefinition *def = *iter;
> >              if (def->isBoundsCheck() && def->isMovable()) {
> >                  if (tryHoistBoundsCheck(header, def->toBoundsCheck()))
> 
> This |if| should have {} now.

Done.

> @@ +1769,5 @@
> >              IonSpew(IonSpew_Range, "computing range on %d", def->id());
> >              SpewRange(def);
> >          }
> >  
> >          if (block->isLoopHeader())
> 
> Ditto.

Done.

Attached is an updated patch.

Comment 3

[Dan Gohman [:sunfish]]

Comment on attachment 805415 [details] [diff] [review]
avoid-recursion.patch

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not easily. I tried, but everything I tried hit some other limit before becoming big enough to actually overflow the stack.

Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

The make it clear what the bug is. They don't make it clear how to construct a testcase which actually exploits it.

Which older supported branches are affected by this flaw?

All branches at least back to mozilla-release.

If not all supported branches, which bug introduced the flaw?

The bug was introduced in 89e5db8cf62f (bug 766592).

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

I don't have them yet, but they would be easy to create, with relatively low risk.

How likely is this patch to cause regressions; how much testing does it need?

I'd guess it doesn't need any testing beyond what would be done for any other patch.

Comment 4

[Al Billings [:abillings - ex-MoCo]]

Can someone suggest a security rating for this?


This looks to be necessary on all branches?

Comment 5

[David Bolter [:davidb] (NeedInfo me for attention)]

(In reply to Al Billings [:abillings] from comment #4)
> Can someone suggest a security rating for this?

Am I right that it is a hypothetical stack overflow? If so this is probably not too bad. We need a js team opinion.

Comment 6

[Andrew McCreight [:mccr8]]

It sounds like this is just a DOS.

Comment 7

[Daniel Veditz [:dveditz]]

Comment on attachment 805415 [details] [diff] [review]
avoid-recursion.patch

sec-approval+
(You don't need sec-approval to land a sec-low bug, btw)

Comment 8

[Dan Gohman [:sunfish]]

Attachment: the patch, ported to the aurora branch

Comment 9

[Dan Gohman [:sunfish]]

Attachment: the patch, ported to the beta branch

Comment 10

[Dan Gohman [:sunfish]]

Checked into mozilla-inbound here:
https://hg.mozilla.org/integration/mozilla-inbound/rev/e56f23a35f8b

Comment 11

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/e56f23a35f8b