917841 - (CVE-2013-5619) binary searches use overflow-prone arithmetic

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Dan Gohman [:sunfish]]

Attachment: binary-search-overflow.patch

An informal search of SpiderMonkey for binary search algorithms turned up several places using (lo+hi)/2, which is prone to overflow in general [0]. Attached is a patch which changes them to use lo+(hi-lo)/2.

While most of them look like they'd be safe in practice -- if numICEntries() or script->nTypeSets approach anything close to SIZE_MAX/2, I assume the program would have far worse problems -- one of them, in js/src/frontend/TokenStream.cpp, is not obviously safe, since it uses uint32_t indices, and there's nothing obvious which would protect them.

This patch changes all of them, to be on the safe side.

[0] http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Comment 1

[Luke Wagner [:luke]]

Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

My goodness, how many duplicates of binary search do we have?!  I must confess I'm guilty of adding one of my own (LookupHeapAccess, not on this list, it does low+(high-low)/2).

After you land the fix, perhaps you'd like to file a bug to write a template algorithm to factor these out?

Comment 2

[Dan Gohman [:sunfish]]

Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

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

I haven't tried, but it may just involve presenting a 2 GiB or so script to the JavaScript parser and then carefully leading it down a particular path, to get an out-of-bounds array access, from which an exploit could theoretically be crafted.

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

Binary-search overflow is a widely understood phenomenon, and it will be evident from the patch. But, there are no testcases showing specifically how to trigger it, much less exploit it.

Which older supported branches are affected by this flaw?

It's present in all branches at least back to mozilla-release.

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

The interesting case was introduced in 1f3587e02361 (bug 747831).

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

I don't at the moment, but it would be trivial to create them for any branch.

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

The patch is very unlikely to cause regressions.

Comment 3

[Dan Gohman [:sunfish]]

(In reply to Luke Wagner [:luke] from comment #1)
> Comment on attachment 806669 [details] [diff] [review]
> binary-search-overflow.patch
> 
> My goodness, how many duplicates of binary search do we have?!  I must
> confess I'm guilty of adding one of my own (LookupHeapAccess, not on this
> list, it does low+(high-low)/2).
> 
> After you land the fix, perhaps you'd like to file a bug to write a template
> algorithm to factor these out?

Sure. I filed bug 917918 to record several other binary-search-like things found in various places.

I thought I had clicked the box to make bug 917918 a protected bug, but apparently I didn't, and I don't seem to have the ability to change it now. Can someone correct this?

Comment 4

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

We need to get a security rating on this issue before sec-approval.

Comment 5

[Daniel Veditz [:dveditz]]

Comment on attachment 806669 [details] [diff] [review]
binary-search-overflow.patch

sec-approval+

Comment 6

[Nicholas Nethercote [inactive]]

Thanks, Dan!

Comment 7

[Dan Gohman [:sunfish]]

Attachment: the patch, ported to the aurora branch

Comment 8

[Dan Gohman [:sunfish]]

Attachment: the patch, ported to the beta branch

Comment 9

[Dan Gohman [:sunfish]]

Landed on on mozilla-inbound here:
https://hg.mozilla.org/integration/mozilla-inbound/rev/c231777cadca

Should I pursue landing this patch on other affected branches?

Comment 10

[Lukas Blakk [:lsblakk] use ?needinfo]

Ryan - if this landed on inbound a month ago shouldn't it be on central now? Can you help clarify where this might still need to land?

Comment 11

[Ryan VanderMeulen [:RyanVM]]

Indeed, looks like the bug was never resolved when it landed on m-c.

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

Comment 12

[Lukas Blakk [:lsblakk] use ?needinfo]

Can you please nominate this for uplift to the beta branch if it's a low risk landing?  If not, we can wait until the release of FF27.

Comment 13

[Dan Gohman [:sunfish]]

Comment on attachment 808893 [details] [diff] [review]
the patch, ported to the beta branch

Assuming "nominate this for uplift to the beta branch" means "requeset approval-mozilla-beta". Please correct me if I'm wrong. The fix is very low-risk.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 

The interesting case was introduced in 1f3587e02361 (bug 747831).

User impact if declined: 

There is no known user impact. At this point, all we can say is that we don't know that user impact is impossible.

Testing completed (on m-c, etc.): 

It's been on mozilla-central for almost 2 months now.

Risk to taking this patch (and alternatives if risky): 

Very low. The patch is simple, and it's well tested.

String or IDL/UUID changes made by this patch:

None.

Comment 14

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/0095ca6ac388

Note that it was actually the Aurora patch that was landed given the cycle we were in when these patches were created.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-b2g26_v1_2/rev/0095ca6ac388

Comment 16

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

This was never marked for ESR24. From what I can tell, it affects ESR24 as well.