Unrooted pivot in js_HeapSort

VERIFIED FIXED

Status

()

Core
JavaScript Engine
--
critical
VERIFIED FIXED
12 years ago
11 years ago

People

(Reporter: Igor Bukanov, Assigned: brendan)

Tracking

({verified1.7.13, verified1.8})

Trunk
x86
Linux
verified1.7.13, verified1.8
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.7.13 +
blocking-aviary1.0.8 +
blocking1.8rc1 +
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:critical] arbitrary code execution (see comment 10))

Attachments

(7 attachments, 3 obsolete attachments)

(Reporter)

Description

12 years ago
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.
(Reporter)

Comment 1

12 years ago
Created attachment 198796 [details] [diff] [review]
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.
Attachment #198796 - Flags: review?(brendan)
(Reporter)

Comment 2

12 years ago
Created attachment 198971 [details]
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.
(Reporter)

Comment 3

12 years ago
This can be used to crash JS engine embedding.
Severity: normal → critical
(Assignee)

Comment 4

12 years ago
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
Attachment #198796 - Flags: review?(brendan)
Attachment #198796 - Flags: review+
Attachment #198796 - Flags: approval1.8rc1+
(Assignee)

Comment 5

12 years ago
Created attachment 198980 [details] [diff] [review]
patch extracted from trunk for branch checkin
Attachment #198980 - Flags: review+
Attachment #198980 - Flags: approval1.8rc1?
(Assignee)

Comment 6

12 years ago
Fixed on trunk.

/be
Status: NEW → RESOLVED
Last Resolved: 12 years ago
Flags: blocking1.8rc1+
Resolution: --- → FIXED
(Reporter)

Comment 7

12 years ago
(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.

Status: RESOLVED → REOPENED
Resolution: FIXED → ---
We're using "fixed" for the trunk state, and nomination flags for the branches.
Re-closing and plussing for aviary/17 branches
Status: REOPENED → RESOLVED
Last Resolved: 12 years ago12 years ago
Flags: blocking1.7.13+
Flags: blocking-aviary1.0.8+
Resolution: --- → FIXED
Whiteboard: [sg:low] memory read at least, maybe more
(Assignee)

Comment 9

12 years ago
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
(Reporter)

Comment 10

12 years ago
> [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?
(Assignee)

Comment 11

12 years ago
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

Updated

12 years ago
Whiteboard: [sg:low] memory read at least, maybe more → [sg:critical] arbitrary code execution (see comment 10)

Comment 12

12 years ago
Created attachment 199039 [details]
testcase  js1_5/Regress/regress-311497.js

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

Updated

12 years ago
Flags: testcase?
(Reporter)

Comment 13

12 years ago
Created attachment 199062 [details]
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.
Attachment #199039 - Attachment is obsolete: true

Updated

12 years ago
Attachment #198980 - Flags: approval1.8rc1? → approval1.8rc1+
(Assignee)

Comment 14

12 years ago
Fixed on branch too.

/be
Keywords: fixed1.8
Blocks: 256195

Comment 15

12 years ago
(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

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

Comment 17

12 years ago
(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.
(Reporter)

Comment 18

12 years ago
Reopening per above comment :(
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Reporter)

Comment 19

12 years ago
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))
(Assignee)

Comment 20

12 years ago
(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
(Assignee)

Comment 21

12 years ago
(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
(Assignee)

Updated

12 years ago
Blocks: 312069
(Reporter)

Comment 22

12 years ago
Created attachment 199542 [details]
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...);
Attachment #199062 - Attachment is obsolete: true
(Reporter)

Comment 23

12 years ago
Created attachment 199543 [details] [diff] [review]
Fix for fun->extra bug
(Reporter)

Updated

12 years ago
Attachment #199543 - Flags: review?(brendan)
(Assignee)

Comment 24

12 years ago
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
Attachment #199543 - Flags: review?(brendan) → review+
(Assignee)

Comment 25

12 years ago
Created attachment 199564 [details] [diff] [review]
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
Assignee: general → brendan
Status: REOPENED → ASSIGNED
Attachment #199564 - Flags: superreview?(shaver)
Attachment #199564 - Flags: review?(igor.bukanov)
(Reporter)

Comment 26

12 years ago
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.
Attachment #199564 - Flags: review?(igor.bukanov) → review+
(Reporter)

Comment 27

12 years ago
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. 
(Assignee)

Comment 28

12 years ago
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
Attachment #199564 - Attachment is obsolete: true
Attachment #199564 - Flags: superreview?(shaver)
Attachment #199564 - Flags: review+
(Assignee)

Updated

12 years ago
Blocks: 311161
(Assignee)

Comment 29

12 years ago
Created attachment 199612 [details] [diff] [review]
fix v2

Works, even.

/be
Attachment #199612 - Flags: superreview?(shaver)
Attachment #199612 - Flags: review+
(Assignee)

Comment 30

12 years ago
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 on attachment 199612 [details] [diff] [review]
fix v2

sr=shaver
Attachment #199612 - Flags: superreview?(shaver) → superreview+
(Assignee)

Comment 32

12 years ago
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
Attachment #199612 - Flags: approval1.8rc1?
(Assignee)

Comment 33

12 years ago
Fixed on the trunk.

/be
Status: ASSIGNED → RESOLVED
Last Resolved: 12 years ago12 years ago
Resolution: --- → FIXED
(Assignee)

Updated

12 years ago
No longer blocks: 311161
(Assignee)

Comment 34

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

Updated

12 years ago
Attachment #199612 - Flags: approval1.8rc1? → approval1.8rc1+

Comment 35

12 years ago
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?
(Assignee)

Comment 36

12 years ago
Fix v2 checked in.

/be

Comment 37

12 years ago
verified firefox 1.5 rc2 linux/win32 2005-11-07
Keywords: fixed1.8 → verified1.8

Comment 38

12 years ago
testcase+ to get this off my radar. when this is made public, i will check in the test.
Flags: testcase? → testcase+
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.
Attachment #199612 - Flags: approval1.7.13+
Attachment #199612 - Flags: approval-aviary1.0.8+
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?
Attachment #199612 - Flags: approval1.7.13?
Attachment #199612 - Flags: approval1.7.13+
Attachment #199612 - Flags: approval-aviary1.0.8?
Attachment #199612 - Flags: approval-aviary1.0.8+

Updated

12 years ago
Attachment #198980 - Flags: approval1.7.13?
Attachment #198980 - Flags: approval-aviary1.0.8?

Comment 41

12 years ago
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 on attachment 198980 [details] [diff] [review]
patch extracted from trunk for branch checkin

a=dveditz
Attachment #198980 - Flags: approval1.7.13?
Attachment #198980 - Flags: approval1.7.13+
Attachment #198980 - Flags: approval-aviary1.0.8?
Attachment #198980 - Flags: approval-aviary1.0.8+
Comment on attachment 199612 [details] [diff] [review]
fix v2

a=dveditz
Attachment #199612 - Flags: approval1.7.13?
Attachment #199612 - Flags: approval1.7.13+
Attachment #199612 - Flags: approval-aviary1.0.8?
Attachment #199612 - Flags: approval-aviary1.0.8+
Created attachment 211904 [details] [diff] [review]
array fixes, backporteed

The easiest way to verify this might be to apply it and diff against the MOZILLA_1_8_BRANCH.
Attachment #211904 - Flags: review?(brendan)
Attachment #211904 - Flags: approval1.7.13?
Attachment #211904 - Flags: approval-aviary1.0.8?

Comment 45

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

a=timr for drivers.  Approved pending review.
Attachment #211904 - Flags: approval1.7.13?
Attachment #211904 - Flags: approval1.7.13+
Attachment #211904 - Flags: approval-aviary1.0.8?
Attachment #211904 - Flags: approval-aviary1.0.8+
(Assignee)

Comment 46

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

Looks good, thanks for doing this.

/be
Attachment #211904 - Flags: review?(brendan) → review+
Fixes checked into the 1.7 branch.
Keywords: fixed-aviary1.0.8, fixed1.7.13

Comment 48

12 years ago
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.
Status: RESOLVED → VERIFIED
Keywords: fixed-aviary1.0.8, fixed1.7.13 → verified-aviary1.0.8, verified1.7.13
Group: security

Comment 49

11 years ago
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
You need to log in before you can comment on or make changes to this bug.