311497 - Unrooted pivot in js_HeapSort

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

js_HeapSort does not GC-root its pivot element. Thus if GC would be triggered
during swap of elements in HeapSortHelper from  jsarray.c while pivot holding
value temporarily taken out from the array as a part of element swap and that
value refers to GC-thing, then the sorted array would contain a pointer to a
memory area GC considers free.

I am not sure if this is exploitable, but it definitely allows to manipulate GC
free list if one can trigger that GC in the middle of swap. To play it safe I
mark the bug as a security problem.

Comment 1

[Igor Bukanov]

Attachment: Fix: pivot memory is passed to js_HeapSort

The patch changes js_HeapSort to use memory for pivot suplied by client which
can take all the necessary measures to root it.

Comment 2

[Igor Bukanov]

Attachment: Test case to crash js shell

It turned out that the bug does not require multiple threads to exploit and can
be used from single thread. The problem is that there is a code path which
calls compare when pivot holds a reference that is overwritten in the working
array. Thus the idea is to check in custom compare function for that condition
and when it is met, remove all the references to affected elements and call
operation that would trigger garbage collection. 

This attachment is demonstrates the problem for JS shell.

Comment 3

[Igor Bukanov]

This can be used to crash JS engine embedding.

Comment 4

[Brendan Eich [:brendan]]

Comment on attachment 198796 [details] [diff] [review]
Fix: pivot memory is passed to js_HeapSort

Thanks, Igor.  I'll check this (with cosmetic changes only, I promise) in on
the trunk right now.

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: patch extracted from trunk for branch checkin

Comment 6

[Brendan Eich [:brendan]]

Fixed on trunk.

/be

Comment 7

[Igor Bukanov]

(In reply to comment #6)
> Fixed on trunk.


I believe this should be applied to Firefox 1.0.* since a variation of the above
example allows to read 64 bits stored in GC things and to change 64 bits that GC
thing holds to almost arbitrary predefined value. 

This is quite reliable since I can make Firefox to visit other pages before
crashing after replacing context of a pointer to JSObject.

Now I would not claim that this can be used to arbitrary code execution but
knowledge of and ability to replace the value JSObject.map and JSObject.slots to
chosen value can facilitate potential exploits.

So I reopen this to make patch to apply to 1.0.* branch as well.

Comment 8

[Daniel Veditz [:dveditz]]

We're using "fixed" for the trunk state, and nomination flags for the branches.
Re-closing and plussing for aviary/17 branches

Comment 9

[Brendan Eich [:brendan]]

Patches for 1.0.x and 1.7.y will take work -- the patch for the 1.8 branch here
won't apply as is.

/be

Comment 10

[Igor Bukanov]

> [sg:low] memory read at least, maybe more

So far it looks like it can be used for arbitrary code execution. 

Step 1. One starts with subverting a reference to a double value to point to
JSString where JSString->chars holds the code to execute and extracts from
double bits the address of JSString->chars. 

Step 2. Subvert another double reference to point to string where chars bytes
when interpreted as JSObjectOps would give in JSObjectOps->defaultValue a
pointer to the code to execute obtained on the previous step. Then one use
double value to extract a pointer to JSObjectOps image.

Step 3. Subvert third double reference into string that is an image of
JSObjectMap with JSObjectMap->ops pointing to JSObjectOps from the previous step
and extract the address of JSObjectMap.

Step 4. Construct a double value which when interpreted as JSObject would point
to JSObjectMap from the previous step through JSObject->map.

Step 5. Subvert a reference to object to point to the double value from the
previous step.

Step 6. Call Math.sin() on the subverted object reference. Since runtime would
assume that this is an object, it would call JSObject->map->ops->defaultValue
and execute the code from step 1.

For details of pointer subversion see bug 311792. Note that it is important to
keep references to subverted doubles from step 1-3 to prevent strings they point
to from GC forced at the following steps.

Now what did I miss here?

Comment 11

[Brendan Eich [:brendan]]

Igor, you missed nothing -- you are ahead of the curve as usual ;-).

We had another bug this year where I worked with a friendly hacker to develop an
exploit based on forging an XPCOM object using a JSString.  We treat heap
overruns as exploitable by default.  Even easier if instead of overrunning a
malloc chunk, you can control GC-things.

/be

Comment 12

[Bob Clary [:bc] (inactive)]

Attachment: testcase js1_5/Regress/regress-311497.js

This testcase is not to be checked in until the bug is made public.

Comment 13

[Igor Bukanov]

Attachment: Bettr testcase testcase js1_5/Regress/regress-311497.js

There is no guaranty that the original test case would crash so it is better to
verify the array structure on exit explicitly. In addition the test case force
GC on each compare to avoid dependancy on details of array.sort implementation
so if somebody commits the currently proposed version of merge sort to replace
heap sort from bug 224128, the test case would spot unrooted access there.

Comment 14

[Brendan Eich [:brendan]]

Fixed on branch too.

/be

Comment 15

[Bob Clary [:bc] (inactive)]

(In reply to comment #13)

Neither 1.8 or trunk cvs builds from this morning crash.
1.8 branch (opt/dbg) passes, trunk build (opt/dbg) fails

Testcase js1_5/Regress/regress-311497.js failed Bug Number 311497
[ Top of Page ]
STATUS: Root pivots in js_HeapSort
Failure messages were:
FAILED!: Root pivots in js_HeapSort
FAILED!: Expected value '10', Actual value '5'
FAILED!:

Comment 16

[Bob Clary [:bc] (inactive)]

Igor, can you reproduce the difference for your "Better" testcase in the patched
(bug 312069) trunk vs. the unpatched 1.8? Is this meaningful

Comment 17

[Igor Bukanov]

(In reply to comment #16)
> Igor, can you reproduce the difference for your "Better" testcase in the patched
> (bug 312069) trunk vs. the unpatched 1.8? Is this meaningful

Yes, this is meaningful! The trunk already contain changes for Bug 312069 which
was a regression caused by my fix for this bug. Now that "fix for the fix"
caused regression in this bug! It seems that extra argv + argc and argv + argc +
1 GC-roots that the last patch uses are not treated as GC roots at all!

I do not know why it is so.



Since the 1.8 branch contains only "fix", not "fix" + "fix for the fix", the
example works there.

Comment 18

[Igor Bukanov]

Reopening per above comment :(

Comment 19

[Igor Bukanov]

With the following patch to jsgc.c the test case no longer crashes the jsshell.
But the patch can not be right since it assumes local roots where missed from
GC-marking and that can not be true! So what is wrong there?

--- jsgc.c      29 Jul 2005 15:15:48 -0000      3.104
+++ jsgc.c      13 Oct 2005 14:34:34 -0000
@@ -1747,8 +1747,8 @@
                 GC_MARK(cx, fp->thisp, "this", NULL);
                 if (fp->argv) {
                     nslots = fp->argc;
-                    if (fp->fun && fp->fun->nargs > nslots)
-                        nslots = fp->fun->nargs;
+                    if (fp->fun && fp->fun->nargs + fp->fun->extra > nslots)
+                        nslots = fp->fun->nargs + fp->fun->extra;
                     GC_MARK_JSVALS(cx, nslots, fp->argv, "arg");
                 }
                 if (JSVAL_IS_GCTHING(fp->rval))

Comment 20

[Brendan Eich [:brendan]]

(In reply to comment #19)
> With the following patch to jsgc.c the test case no longer crashes the jsshell.
> But the patch can not be right since it assumes local roots where missed from
> GC-marking and that can not be true! So what is wrong there?

This is a very old bug.  Normally, arguments that the callee accesses via
fp->argv come from the caller's operand stack, so they lie within
fp->down->spbase and fp->down->sp.  All native functions are invoked via
js_Invoke, and it adds fun->extra to fun->nargs (see the minargs local in
js_Invoke) to ensure that fun->nargs + fun->extra contiguous jsvals are
available at fp->argv for the callee to use, irrespective of argc -- and
especially including the local roots at the end.

This implies that typically, the GC redundantly marks, by scanning

  fp->argv[0..MAX(fp->argc,fp->nargs)]

the same operand stack space it will mark when it moves fp down one frame to the
caller and scans:

  fp->spbase[0..MIN(fp->sp - fp->spbase, fp->script->depth)]

There are cases where argv is not on the operand stack, or there could be, and I
didn't want to rule that out, so I left this redundant scanning in.

But there's a bug in it, and igor's patch fixes that bug.  Question is, why does
the bug only bite rarely, as in the present case?  It's because normally the
caller opernad stack space includes enough room for the local roots.  But not so
in the testcase.  When the caller's operand stack budget, fp->script->depth for
fp denoting the caller frame (fp->down where fp denotes the callee's frame), is
not big enough to hold the actual arguments, any missing formal parameters, and
the fp->fun->extra local roots, then whatever doesn't fit will not be scanned.

Igor's patch is a reasonable fix.  There might be a tighter fix that overscans
fp->spbase (fp the caller's frame) to include missing formals and extra local
roots that fit in the stack arena, but that exceeded the depth budget.

Igor, what do you think?  If your patch seems best, please attach it.  Thanks
for finding this very old bug!

/be

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #20)
> There might be a tighter fix that overscans
> fp->spbase (fp the caller's frame) to include missing formals and extra local
> roots that fit in the stack arena, but that exceeded the depth budget.

In other words, perhaps the operand stack scanning should cover fp->spbase to
fp->sp, never mind depth.  But that has a bug, because we could have a hole due
to hitting end of a stack arena, and fp->sp is in the next arena (along with any
fp->vars allocated for a scripted function -- not an issue for natives as in the
present case).

So it's tricky, and perhaps Igor's patch is best, but I'll let him noodle on
this and shut up now.

/be

Comment 22

[Igor Bukanov]

Attachment: New version of js1_5/Regress/regress-311497.js

This version of the test case contains a proof that the patch in comment 19 is
not enough.

The problem is that array_sort assumes that extra slots starts from argv + argc
while the patch fixes GC scanning code to scan from fun->nargs + fun->extra.
Now if in the test case from attachment 199062 [details] one replaces array.sort(cmp) by

array.sort(cmp,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18);

then one would get segmentation fault after the first GC.

The problem is in js_Invoke which assumes that a native function would use for
fun->extra slots after fun->nargs, not after MAX(fun->nargs, argc).

So here is a test case that covers both the original array.sort(cmp) and the
extra run with array.sort(cmp,0,1...);

Comment 23

[Igor Bukanov]

Attachment: Fix for fun->extra bug

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 199543 [details] [diff] [review]
Fix for fun->extra bug

Thanks, Igor -- you are the best!  This bug goes back 8 years, I recall fur
reviewing this code. My fault, should have re-read it more carefully at some
point.

I will attach a version of this patch that tries to minimize change in some
places (using nslots instead of extraslots), while getting rid of unnecessary
intN usage nearby.

/be

Comment 25

[Brendan Eich [:brendan]]

Attachment: minimize using nslots, eliminate intN locals and casts

Looking for review to make sure I didn't fat-finger (or fat-brain) anything.

I'll take the bug to make up for 8 years of its existence, and get this checked
into the trunk when reviewed, and then get branch approval.  Thanks again,

/be

Comment 26

[Igor Bukanov]

Comment on attachment 199564 [details] [diff] [review]
minimize using nslots, eliminate intN locals and casts

>     /* Now allocate stack space for local variables. */
>-    nslots = (intN)frame.nvars;
>+    nslots = frame.nvars;
>     if (nslots) {

BTW, frame.nvars is nvars here. Thus replacing nslots by nvars in the "if" body
one gets IMO more clear code especially with extra JS_ASSERT(nvars == 0) after
the "if". But then the patch would affect 3 additional lines.

Comment 27

[Igor Bukanov]

From the quick look at the bug 311161 it *CAN* be the case that extra underscan
is  at fault teher as well. Object.prototype.toSource requires 3 extra slots so
GC can wipe out them if an extra stack would be allocated for them. With 3
extras and the fact that script contains calls with no more then 2 arguments the
bug is exposed here as well. 

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 199564 [details] [diff] [review]
minimize using nslots, eliminate intN locals and casts

Fat-fingered it: nalloc must be tested in a signed sense > 0, it can underflow.
 I left its type unsigned to minimize casts.  New patch in a minute.

/be

Comment 29

[Brendan Eich [:brendan]]

Attachment: fix v2

Works, even.

/be

Comment 30

[Brendan Eich [:brendan]]

Comment on attachment 199612 [details] [diff] [review]
fix v2

Bugzilla's interdiff works, but warns that it may not.	Check it out.

This patch uses nvars instead of nslots = frame.nvars as Igor suggested, too.

/be

Comment 31

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 199612 [details] [diff] [review]
fix v2

sr=shaver

Comment 32

[Brendan Eich [:brendan]]

Comment on attachment 199612 [details] [diff] [review]
fix v2

This is in the trunk now. It fixes a critical security bug, which is in essence
8+ years old, and which has probably caused other mystery-crashes over the
years.	It looks like it should fix another bug on our current critical
blocking1.8rc1 list.  How about approving it on Monday if all is well on the
trunk?

/be

Comment 33

[Brendan Eich [:brendan]]

Fixed on the trunk.

/be

Comment 34

[Brendan Eich [:brendan]]

*** Bug 311161 has been marked as a duplicate of this bug. ***

Comment 35

[Bob Clary [:bc] (inactive)]

bug 312069 comment 19 claims this was checked in on the branch, and the patch
for bug 312069 was checked in. I am now getting

Testcase js1_5/Regress/regress-311497.js failed Bug Number 311497
[ Top of Page ]
STATUS: Root pivots in js_HeapSort
Failure messages were:
FAILED!: Root pivots in js_HeapSort
FAILED!: Expected value '10', Actual value '5'
FAILED!: 

on the branch as well. Was this really checked in to the branch?

Comment 36

[Brendan Eich [:brendan]]

Fix v2 checked in.

/be

Comment 37

[Bob Clary [:bc] (inactive)]

verified firefox 1.5 rc2 linux/win32 2005-11-07

Comment 38

[Bob Clary [:bc] (inactive)]

testcase+ to get this off my radar. when this is made public, i will check in the test.

Comment 39

[Daniel Veditz [:dveditz]]

Comment on attachment 199612 [details] [diff] [review]
fix v2

aviary101/moz17 landing approval: a=dveditz for drivers. Please add the fixed1.7.13 and fixed-aviary1.0.8 keywords when landed.

Comment 40

[Daniel Veditz [:dveditz]]

Comment on attachment 199612 [details] [diff] [review]
fix v2

per comment 3 it sounds like this patch won't work on the old branches. Can we get a new one?

Comment 41

[Mike Schroepfer]

In discussion with BKap tonight both patches (#3, and #6 above) are needed and need minor mechnical backporting for 1.7 tree.  Please approve the above patches if you want them to be backported to the 1.7 tree.

Comment 42

[Daniel Veditz [:dveditz]]

Comment on attachment 198980 [details] [diff] [review]
patch extracted from trunk for branch checkin

a=dveditz

Comment 43

[Daniel Veditz [:dveditz]]

Comment on attachment 199612 [details] [diff] [review]
fix v2

a=dveditz

Comment 44

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: array fixes, backporteed

The easiest way to verify this might be to apply it and diff against the MOZILLA_1_8_BRANCH.

Comment 45

[Tim Riley [:timr]]

Comment on attachment 211904 [details] [diff] [review]
array fixes, backporteed

a=timr for drivers.  Approved pending review.

Comment 46

[Brendan Eich [:brendan]]

Comment on attachment 211904 [details] [diff] [review]
array fixes, backporteed

Looks good, thanks for doing this.

/be

Comment 47

[Blake Kaplan (:mrbkap) (inactive)]

Fixes checked into the 1.7 branch.

Comment 48

[Bob Clary [:bc] (inactive)]

v ff on 1.7.13, 1.8.0.1, 1.8, 1.9a1 on 20060221 windows/linux/mac builds, moz on 1.7.13 20060221 windows build.

Comment 49

[Bob Clary [:bc] (inactive)]

RCS file: /cvsroot/mozilla/js/tests/js1_5/GC/regress-311497.js,v
done
Checking in regress-311497.js;
/cvsroot/mozilla/js/tests/js1_5/GC/regress-311497.js,v  <--  regress-311497.js
initial revision: 1.1
done