424558 - Use after free in decompiler

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Bob Clary [:bc] (inactive)]

Attachment: test.js

CentOS 5 64 bit

==24943== Invalid read of size 1
==24943==    at 0x4A06990: memmove (mc_replace_strmem.c:503)
==24943==    by 0x4813DA: SprintPut (jsopcode.c:455)
==24943==    by 0x481435: SprintCString (jsopcode.c:463)
==24943==    by 0x48654F: Decompile (jsopcode.c:2079)
==24943==    by 0x48A04A: Decompile (jsopcode.c:2988)
==24943==    by 0x491EA6: DecompileCode (jsopcode.c:4606)
==24943==    by 0x4928D7: js_DecompileFunction (jsopcode.c:4786)
==24943==    by 0x41FBB0: JS_DecompileFunction (jsapi.c:4830)
==24943==    by 0x45B963: fun_toStringHelper (jsfun.c:1491)
==24943==    by 0x45B9E7: fun_toSource (jsfun.c:1508)
==24943==    by 0x467FF6: js_Invoke (jsinterp.c:1186)

Comment 1

[Bob Clary [:bc] (inactive)]

appears to be 64 bit only.

Comment 2

[Mats Palmgren (inactive)]

's' is within the buffer, then SprintEnsureBuffer() realloc's the
buffer making 's' point to free'd memory.
http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/js/src/jsopcode.c&rev=3.307&root=/cvsroot&mark=448,455#417

With some debug printf's:

sp->base=0x55abb48 sp->offset=985 sp->size=989 s=0x55abeed
  (missing 49 bytes to fit this string at sp->offset)
  ('s' is 933 bytes into sp->base, 3 bytes follows it. 's' does not overlap with sp->offset)
len=52: (code.indexOf("<") == -1 || code.indexOf(".") == -1)
sp->base was reallocated!, now at 0x55ac080 with size 1038

==6994== Invalid read of size 1
==6994==    at 0x4C23290: memmove (mc_replace_strmem.c:516)
==6994==    by 0x458276: SprintPut (jsopcode.c:466)
==6994==    by 0x4582BC: SprintCString (jsopcode.c:474)
==6994==    by 0x45A1BA: Decompile (jsopcode.c:2090)
==6994==    by 0x45C874: Decompile (jsopcode.c:2999)
==6994==    by 0x461D67: DecompileCode (jsopcode.c:4617)
==6994==    by 0x4638D3: js_DecompileFunction (jsopcode.c:4797)
==6994==    by 0x40C993: JS_DecompileFunction (jsapi.c:4835)
==6994==    by 0x43F919: fun_toStringHelper (jsfun.c:1485)
==6994==    by 0x43F966: fun_toSource (jsfun.c:1502)
==6994==    by 0x447C55: js_Invoke (jsinterp.c:1186)
==6994==    by 0x4473FC: js_InternalInvoke (jsinterp.c:1359)
==6994==    by 0x44F6CD: js_TryMethod (jsobj.c:4750)
==6994==    by 0x4857A9: js_ValueToSource (jsstr.c:2733)
==6994==    by 0x4568B6: obj_toSource (jsobj.c:802)
==6994==    by 0x447C55: js_Invoke (jsinterp.c:1186)
==6994==    by 0x4473FC: js_InternalInvoke (jsinterp.c:1359)
==6994==    by 0x44F6CD: js_TryMethod (jsobj.c:4750)
==6994==    by 0x4857A9: js_ValueToSource (jsstr.c:2733)
==6994==    by 0x485814: str_uneval (jsstr.c:470)
==6994==    by 0x4A7404: js_Interpret (jsinterp.c:4820)
==6994==    by 0x44729A: js_Execute (jsinterp.c:1526)
==6994==    by 0x40C777: JS_ExecuteScript (jsapi.c:4876)
==6994==    by 0x408DCC: Process (js.c:272)
==6994==    by 0x409730: main (js.c:500)
==6994==  Address 0x55abf20 is 1,016 bytes inside a block of size 1,063 free'd
==6994==    at 0x4C22082: realloc (vg_replace_malloc.c:429)
==6994==    by 0x4186BC: JS_ArenaRealloc (jsarena.c:230)
==6994==    by 0x45800E: SprintEnsureBuffer (jsopcode.c:430)
==6994==    by 0x45822F: SprintPut (jsopcode.c:456)
==6994==    by 0x4582BC: SprintCString (jsopcode.c:474)
==6994==    by 0x45A1BA: Decompile (jsopcode.c:2090)
==6994==    by 0x45C874: Decompile (jsopcode.c:2999)
==6994==    by 0x461D67: DecompileCode (jsopcode.c:4617)
==6994==    by 0x4638D3: js_DecompileFunction (jsopcode.c:4797)
==6994==    by 0x40C993: JS_DecompileFunction (jsapi.c:4835)
==6994==    by 0x43F919: fun_toStringHelper (jsfun.c:1485)
==6994==    by 0x43F966: fun_toSource (jsfun.c:1502)
==6994==    by 0x447C55: js_Invoke (jsinterp.c:1186)
==6994==    by 0x4473FC: js_InternalInvoke (jsinterp.c:1359)
==6994==    by 0x44F6CD: js_TryMethod (jsobj.c:4750)
==6994==    by 0x4857A9: js_ValueToSource (jsstr.c:2733)
==6994==    by 0x4568B6: obj_toSource (jsobj.c:802)
==6994==    by 0x447C55: js_Invoke (jsinterp.c:1186)
==6994==    by 0x4473FC: js_InternalInvoke (jsinterp.c:1359)
==6994==    by 0x44F6CD: js_TryMethod (jsobj.c:4750)
==6994==    by 0x4857A9: js_ValueToSource (jsstr.c:2733)
==6994==    by 0x485814: str_uneval (jsstr.c:470)
==6994==    by 0x4A7404: js_Interpret (jsinterp.c:4820)
==6994==    by 0x44729A: js_Execute (jsinterp.c:1526)
==6994==    by 0x40C777: JS_ExecuteScript (jsapi.c:4876)
==6994==    by 0x408DCC: Process (js.c:272)
==6994==    by 0x409730: main (js.c:500)

Comment 3

[Mats Palmgren (inactive)]

Attachment: wip

FWIW, this fixes the testcase, I haven't investigated other callers of
SprintEnsureBuffer() though...

Comment 4

[Jesse Ruderman]

Attachment: testcase 2

This triggers the same Valgrind warning on 32-bit Mac.

Comment 5

[Igor Bukanov]

Attachment: fix v2

Backup of an untested patch.

Comment 6

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to comment #5)
> Created an attachment (id=414568) [details]
> fix v2
> 
> Backup of an untested patch.

Drive-by fuzzing of 64-bit js shell binary of this patch on TM tip on 10.6.2 without -j:

a += 0;

asserts at Assertion failure: s + len <= sp->base, at ../jsopcode.cpp:563


=====

$ ./js-dbg-tm-darwin 
js> a += 0;
Assertion failure: s + len <= sp->base, at ../jsopcode.cpp:563
Abort trap

Comment 7

[Igor Bukanov]

Attachment: fix v3

The fix changes SprintCString to insist that the function is never called with a string pointing into the buffer that could be reallocated. This required to fix a few its callers to use offsets rather then char* strings and rely on a special SprintOffset when printing. 

Strictly speaking the fix from the comment 3 would also work as it turned (at least AFAICS) there is no code that does something like:

lval = POP_STR();
rval = POP_STR();

SprintCString(lval)
SprintCString(rval)

That type of code would defeat the minimal fix as the code could reallocate twice defeating the checks there. 

With a bigger fix from this patch that would be detected immediately via an assert in SprintCString.

Gary, could you fuzz this?

Comment 8

[Igor Bukanov]

Regarding severity of this bug. As a consequences of this bug code can read (and only read!) memory that is freed when realloc moves the allocated memory to a bigger allocation size. In an embedding with many threads that could be used in principle to read the memory allocated by other threads.

Comment 9

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to comment #7)
> Created an attachment (id=414777) [details]
> fix v3

var f = new Function("for (var z = 0; z < 21; ++z) { if (z % 3 == 0) { yield function ([y]) { }; } else {}  } ");
try {
    g = eval("(" + "" + f + ")");
    "" + g;
} catch(e) {
    var a = b;
}


throws a typein:6: ReferenceError: b is not defined in 64-bit js debug shells on 10.6 without -j on TM tip, but does not throw an error without this patch.

Is this intended?


===

$ ./js-dbg-tm-darwin 
js> var f = new Function("for (var z = 0; z < 21; ++z) { if (z % 3 == 0) { yield function ([y]) { }; } else {}  } ");
js> try {
    g = eval("(" + "" + f + ")");
    "" + g;
} catch(e) {
    var a = b;
}
typein:6: ReferenceError: b is not defined
js>

Comment 10

[Igor Bukanov]

(In reply to comment #9)
> throws a typein:6: ReferenceError: b is not defined in 64-bit js debug shells
> on 10.6 without -j on TM tip, but does not throw an error without this patch.

This is a bug that is covered by 2 tests under js/src/tests/. I have not find it since I have generated the base failures with the patch applied :(

Comment 11

[Igor Bukanov]

Attachment: fix v3

The new version fixes the regression from the comment 9 and improves the assert coverage.

Comment 12

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to comment #11)
> Created an attachment (id=414832) [details]
> fix v3
> 
> The new version fixes the regression from the comment 9 and improves the assert
> coverage.

This patch seems pretty good. The fuzzers aren't showing up anything after a few hours of work. :)

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 414832 [details] [diff] [review]
fix v3

>+        JS_ASSERT(sp->size > 0);

Use != 0 for unsigned types to avoid a warning (historically this can get you a warning; it's also perilously close to the degenerate unsigned comparison error).

>+    /*
>+     * Check s + len does not overflow. We use that s != 0 implies s - 1 < s
>+     * using unsigned arithmetic.

"We use that P implies Q" should be reworded, either to "Note that P implies Q" or "We use the fact that P implies Q" -- the former is shorter.

>+SprintOffset(Sprinter *sp, ptrdiff_t offset)
>+{
>+    size_t len;
>+    const char *chars;
>+    char *bp;
>+
>+    JS_ASSERT(offset >= 0);
>+    JS_ASSERT((size_t) offset < sp->size);
>+    len = strlen(OFF2STR(sp, offset));
>+
>+    /*
>+     * Check that 0 that terminates the string starting at off is inside the

s/that 0/that the 0/
s/that terminates/terminating/

Patch seems fine, wondering if there isn't a less invasive one that copes with realloc moving the buffer that SprintCString is both reading from and writing to. That would minimize the change and be no less safe AFAICT.

/be

Comment 14

[Igor Bukanov]

(In reply to comment #13)
> Patch seems fine, wondering if there isn't a less invasive one that copes with
> realloc moving the buffer that SprintCString is both reading from and writing
> to.

The minimal version is in the attachment from the comment 3. It works since as far as I can see after checking the code few times there is no sequences like

    lval = POP_STR();
    rval = POP_STR();
    SprintCString(lval)
    SprintCString(rval)

Such sequences may realloc the buffer twice defeating the checks proposed in the minimal fix. 

Now, the minimal fix does not guarantee that future modifications of the code would not introduce the above sequences resurrecting the bug. To protect against that via an assert coverage on the hot path in the decompiler I do not see how it is possible to be less invasive than the patch from the comment 11.

Comment 15

[Igor Bukanov]

Attachment: fix v4

The new version addresses the comment 13.

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #14)
> (In reply to comment #13)
> > Patch seems fine, wondering if there isn't a less invasive one that copes with
> > realloc moving the buffer that SprintCString is both reading from and writing
> > to.
> 
> The minimal version is in the attachment from the comment 3. It works since as
> far as I can see after checking the code few times there is no sequences like
> 
>     lval = POP_STR();
>     rval = POP_STR();
>     SprintCString(lval)
>     SprintCString(rval)

That's right, by design the only safe pattern is pop*;push where * is Kleene closure and pop is POP_STR and variants, push is todo = Sprint* | PushOff(todo).

This is an old design and it's unchecked, so unreliable. On the other hand, we have not had many bugs in it because it fits the pattern of the decompiler's abstract interpreter. I'm therefore inclined toward a minimal patch with asserts.

> To protect
> against that via an assert coverage on the hot path in the decompiler I do not
> see how it is possible to be less invasive than the patch from the comment 11.

Hmm, it is hard to check. An assertion that no two SprintCString calls, both taking arguments on the sprint stack, occur without an intervening PopOff, might be enough.

I'll review the bigger patch in detail.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 414917 [details] [diff] [review]
fix v4

>+#define POP_OFF()             PopOff(ss, op)

No problem having a macro for symmetry but please #undef in the right order at the bottom of the function.

Another way to go would be a C++ auto-storage class helper or two, e.g., a StringOffset type, to sugar the OFF2STR a bit. But this can wait for another bug, if it is worth doing at all.

r=me with that, thanks.

/be

Comment 18

[Igor Bukanov]

https://hg.mozilla.org/tracemonkey/rev/b774250f04d3

Comment 19

[Igor Bukanov]

I backed out the patch due to regression in the bug 531746. Instead I suggest to land the patch from the comment 3.

Comment 20

[Igor Bukanov]

Comment on attachment 311400 [details] [diff] [review]
wip

Minimal fix that works.

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 311400 [details] [diff] [review]
wip

>-    char *bp;
>+    ptrdiff_t offset = sp->size; /* save old size */
>+    char *bp = sp->base;         /* save old base */
> 
>     /* Allocate space for s, including the '\0' at the end. */
>     if (!SprintEnsureBuffer(sp, len))
>         return -1;
> 
>+    if (sp->base != bp && /* buffer was realloc'ed */
>+        s >= bp && s < bp + offset /* s was within the buffer */) {
>+        s = sp->base + (s - bp); /* this is where it lives now */

Please put the comments on the right of code, indented to start in the same c-basic-offset=4 column if possible.

What was the bug with the bigger patch? Switching to offsets instead of strings shouldn't have regressed anything if that's all that changed.

/be

Comment 22

[Igor Bukanov]

> What was the bug with the bigger patch? 

A single typo of using += instead of = in GetLocal has caused the regressin in the bug 531746. But there is a bigger problem with the patch. Right now GetLocal callers ignore OOM failures. That is no good since in couple of places that is feed right into SprintCString leading to straigh NULL deref (I will file a bug about it). But the patch made things worse since with it GetLocal returns -1 and now those unchecked callers will access Sprint->buf[-1].

Comment 23

[Robert Sayre]

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

Comment 24

[Daniel Veditz [:dveditz]]

Is this a regression or does it affect the 1.9.1 branch as well?

Comment 25

[Bob Clary [:bc] (inactive)]

test 2 reproduces the error on 64bit linux and mac 10.5 on 1.9.1.

Comment 26

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 414917 [details] [diff] [review]
fix v4

a1922=beltzner

Comment 27

[timeless]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/0a68d9c698da

Comment 28

[Mats Palmgren (inactive)]

The 2009-11-29 m-c checkin (comment 23) was backed out 2009-11-30:
https://hg.mozilla.org/mozilla-central/rev/e101dddbc432
AFAICT, the bug is still not fixed in mozilla-central, and probably
shouldn't have landed for 1.9.2.2 if I'm right.

Comment 29

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 414917 [details] [diff] [review]
fix v4

Mats: thanks for noticing. That backout really should have been recorded here, and this bug should have been re-opened. This sort of sloppy recordkeeping gets us into a lot of trouble.

Comment 30

[Mike Beltzner [:beltzner, not reading bugmail]]

Timeless: why did you check this patch in, by the way? It wasn't marked checkin-needed, and I don't see you anywhere else on the bug (did you even understand the patch) or a request from Igor to land it ...

Comment 31

[Brendan Eich [:brendan]]

What caused the backout?

/be

Comment 32

[Robert Sayre]

yikes, I must have missed the backout.

Comment 33

[timeless]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/9ae6affe7bba
http://hg.mozilla.org/releases/mozilla-1.9.2/rev/282811d159ab

perhaps i shouldn't have, i did intentionally select to include it. for trunk, i had recently pushed a change of igor's which had sat waiting for 11 days. personally for my changes i appreciate it when others push for me.
there was no indication in the bug of any reason not to push it, and had the necessary stamps.

Comment 34

[Mike Beltzner [:beltzner, not reading bugmail]]

timeless: in the future, unless it includes the "checkin-needed" keyword, please make sure to check with patch owners before checking things in. Of course there was no way for you to tell from reading this bug, but generally it's better form.

Comment 35

[Igor Bukanov]

(In reply to comment #32)
> yikes, I must have missed the backout.

It is my fault. I forgot to land the small patch from the comment 3 and forgot to cite the changeset for bigger patch backout. So the big patch should be taken out and the small should be landed instead with nit fixed.

Comment 36

[Brendan Eich [:brendan]]

Attachment: tm-based nit-picked version of "wip" patch

I will land this on tm right now.

/be

Comment 37

[Brendan Eich [:brendan]]

http://hg.mozilla.org/tracemonkey/rev/eea1a473c074

/be

Comment 38

[Brendan Eich [:brendan]]

Is this waiting on a tm->m-c merge? Or could the patch go into the release repo/branch(s/es, I'm not remembering the details) too?

/be

Comment 39

[Mats Palmgren (inactive)]

Please land on trunk ASAP so we can get this onto branches soon...

Comment 40

[Reed Loden [:reed]]

(In reply to comment #37)
> http://hg.mozilla.org/tracemonkey/rev/eea1a473c074

In the future, please correctly attribute patches to their actual authors. You can do this using the "-u" option to `hg commit`. Example: `hg commit -u "John Doe <[e-mail]>"`. The days of CVS are long past; Hg gives us far more abilities and features, so let's use them.

Comment 41

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/eea1a473c074

Comment 42

[LegNeato]

This is too late for 1.9.2.4 & 1.9.1.10. We'll want it for  .5 and .11

Comment 43

[Reed Loden [:reed]]

(In reply to comment #42)
> This is too late for 1.9.2.4 & 1.9.1.10. We'll want it for  .5 and .11

So, shouldn't the blocking flags be set to "needed" or even ".5+" and ".11+"?

Comment 44

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

We need the flags to exist first, Reed. If you want to make them, please do. :-)

Comment 45

[Reed Loden [:reed]]

(In reply to comment #44)
> We need the flags to exist first, Reed. If you want to make them, please do.
> :-)

Done. In the future, please file a bug under mozilla.org :: Bugzilla: Other b.m.o Issues when you need new ones. If nobody asks us to make them, we won't ever know that they need to be created.

Comment 46

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 432446 [details] [diff] [review]
tm-based nit-picked version of "wip" patch

a=beltzner for 1.9.1.10 and 1.9.2.4; for the latter, please land both on default and GECKO1924_20100413_RELBRANCH tags

Comment 47

[Benjamin Smedberg]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/00808b7f0f58
http://hg.mozilla.org/releases/mozilla-1.9.2/rev/d9516c652290

Comment 48

[LegNeato]

We need this landed on 1.9.1 as well.

Comment 49

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

BC, can you verify this for 1.9.1 (assuming it lands) and 1.9.2 with tonight's nightly builds?

Comment 50

[Bob Clary [:bc] (inactive)]

verified 1.9.2, 1.9.3 with test case 2 on linux x86_64 and mac os x x86.
note that 1.9.1 shows the valgrind error in the unthreaded shell but not the threaded shell.

Comment 51

[LegNeato]

Bob, that means we don't need this on 1.9.1, correct?

Comment 52

[Bob Clary [:bc] (inactive)]

yep

Comment 53

[LegNeato]

Awesome, removing blocking flags.

Comment 54

[Daniel Veditz [:dveditz]]

lowering severity to reflect comment 8

Comment 55

[Mats Palmgren (inactive)]

The absence of an error does not prove correctness.
I feel uncomfortable leaving SprintPut() as is on 1.9.1.

Comment 56

[Bob Clary [:bc] (inactive)]

(In reply to comment #51)
> Bob, that means we don't need this on 1.9.1, correct?

crap. i misread this and missed the "don't".  We do need this on 1.9.1.

Christian and dveditz: I can't fix the flags. Can you reset them to their original values?

Comment 57

[LegNeato]

Blocking it is then. Let's get this landed on 1.9.1 to be safe. Code complete for 1.9.1 is tonight @ 11:59 pm PST.

Comment 58

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.1/rev/a45bb5757782

Comment 59

[Bob Clary [:bc] (inactive)]

v 1.9.1 linux x86_64, mac os x x86 using threaded/nonthreaded shell.