Closed Bug 916635 Opened 6 years ago Closed 6 years ago

Recursive graph traversal in RangeAnalysis

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla27
Tracking Status
firefox24 --- wontfix
firefox25 --- affected
firefox26 --- affected
firefox27 + fixed
firefox-esr17 --- unaffected
firefox-esr24 --- wontfix
b2g18 --- unaffected

People

(Reporter: sunfish, Assigned: sunfish)

References

Details

(4 keywords, Whiteboard: [qa-][adv-main27+])

Attachments

(3 files, 1 obsolete file)

Attached patch avoid-recursion.patch (obsolete) — Splinter Review
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).
Attachment #805109 - Flags: review?(bhackett1024)
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.
Attachment #805109 - Flags: review?(bhackett1024) → review+
(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.
Attachment #805109 - Attachment is obsolete: true
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.
Attachment #805415 - Flags: sec-approval?
Can someone suggest a security rating for this?


This looks to be necessary on all branches?
(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.
It sounds like this is just a DOS.
Keywords: csec-dos, sec-low
Keywords: crash
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)
Attachment #805415 - Flags: sec-approval? → sec-approval+
Whiteboard: [qa-]
Whiteboard: [qa-] → [qa-][adv-main27+]
Group: core-security
You need to log in before you can comment on or make changes to this bug.