1208665 - TempAllocPolicy::pod_* suffer from integer overflow issues

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jeff Walden [:Waldo]]

For example:

    template <typename T>
    T* pod_malloc(size_t numElems) {
        T* p = js_pod_malloc<T>(numElems);
        if (MOZ_UNLIKELY(!p))
            p = static_cast<T*>(onOutOfMemory(AllocFunction::Malloc, numElems * sizeof(T)));
        return p;
    }

js_pod_malloc does just fine with integer overflow, returning nullptr in that case.  But then we call the onOutOfMemory function, passing in a multiplication that may well have overflowed.  And that function ultimately delegates to this:

JS_FRIEND_API(void*)
JSRuntime::onOutOfMemory(AllocFunction allocFunc, size_t nbytes, void* reallocPtr,
                         JSContext* maybecx)
{
    MOZ_ASSERT_IF(allocFunc != AllocFunction::Realloc, !reallocPtr);

    if (isHeapBusy())
        return nullptr;

    if (!oom::IsSimulatedOOMAllocation()) {
        /*
         * Retry when we are done with the background sweeping and have stopped
         * all the allocations and released the empty GC chunks.
         */
        gc.onOutOfMallocMemory();
        void* p;
        switch (allocFunc) {
          case AllocFunction::Malloc:
            p = js_malloc(nbytes);
            break;
          ...
        }
        if (p)
            return p;
    }

So something like this:

    typedef struct { uint32_t arr[1024]; } Bunch;

    TempAllocPolicy talloc(cx);
    Bunch* b = talloc.pod_malloc<Bunch>(2 * 1048576);
    if (!b)
        return false;
    for (size_t i = 0; i < 2 * 1048576; i++)
        b[i].arr[1023] = 17;

would result in JSRuntime::onOutOfMemory being called (on a 32-bit system) with nbytes=0, and so the above loop would write beyond the (0-byte, probably 4-byte under the hood) allocation that backs far, far less than the entirety of |b|.

This is obviously bad, but I don't know if it's used in a place that doesn't have its *own* integer overflow detection.  Vector has its own, and Vector is probably one of the bigger users of this.  But it seems a fool's errand to try to check every caller, so I think we should assume the worst and fix this.

I found this while investigating bug 1207519, for what it's worth.  We probably should audit all the other AllocPolicy implementations and ensure none of them have a similar problem, too, while we're at it.

Comment 1

[Jeff Walden [:Waldo]]

The MallocProvider class I *think* doesn't have the problems noted here, but it has some very screwy-reading code where multiplications are performed, then there's reliance on integer overflow checks in other method calls, then yet another integer overflow check in case of failure:

    template <class T>
    T* pod_calloc(size_t numElems) {
        size_t bytes = numElems * sizeof(T);  // overflow
        T* p = js_pod_calloc<T>(numElems); // but this checks for intoverflow, returns null
        if (MOZ_LIKELY(p)) {
            client()->updateMallocCounter(bytes);  // not overflown because not null
            return p;
        }
        if (numElems & mozilla::tl::MulOverflowMask<sizeof(T)>::value) { // intoverflow if null returned
            client()->reportAllocationOverflow();
            return nullptr;
        }
        p = (T*)client()->onOutOfMemory(AllocFunction::Calloc, bytes); // safe, not overflown
        if (p)
            client()->updateMallocCounter(bytes);
        return p;
    }

I think this is safe, but it's very unclearly so, and it could use some clarification -- perhaps when this bug is fixed, as camouflage.

Comment 2

[Jon Coppeard (:jonco)]

Attachment: temp-alloc-policy-overflow

Patch to add onOutOfMemoryTyped() method to TempAllocPolicy to check for overflow and call onOutOfMemory() if necessary.

I looked through the other AllocPolicy classes and I didn't find any other instances of this problem.  I did tidy up a couple of details however:
 - made maybe_pod_* call straight to maybe_pod_malloc rather then plain pod_malloc where this itself delegated to maybe_pod_malloc
 - made LifoAlloc::maybe_pod_calloc check for failure before calling memset() regardless of whether the allocation is infallible or not, to catch overflow
 - moved the calculation of bytes to its only use in MallocProvider methods

Comment 3

[Jon Coppeard (:jonco)]

Attachment: abstract-byte-calculations

To tidy things up some more, here's a patch to abstract the calculation of allocation size into functions which also check for overflow.

Comment 4

[Jeff Walden [:Waldo]]

Comment on attachment 8668527 [details] [diff] [review]
abstract-byte-calculations

Review of attachment 8668527 [details] [diff] [review]:
-----------------------------------------------------------------

Has anyone observed yet that _with_extra is an awful hack?  So fugly and fragile and pfui.

::: js/public/Utility.h
@@ +346,5 @@
> + * Calculate the number of bytes needed to allocate |numElems| contiguous
> + * instances of type |T|.  Return false if the calculation overflowed.
> + */
> +template <typename T>
> +inline bool CalculateAllocSize(size_t numElems, size_t& bytesOut)

size_t*, please, for an outparam.  Also blank line between type and method name.

@@ +358,5 @@
> + * |T| followed by |numExtra| contiguous instances of type |U|.  Return false if
> + * the calculation overflowed.
> + */
> +template <typename T, typename U>
> +inline bool CalculateAllocSizeWithExtra(size_t numExtra, size_t& bytesOut)

Same.

Also, could you make the types T for array-of and Extra for the extra?  With T/U I can't easily tell which is which without looking at this arithmetic, *and* that at call sites.

@@ +412,2 @@
>          return nullptr;
> +    return (T*)js_malloc(bytes);

static_cast<>, C++-style.  And below.

::: js/src/jit/JitAllocPolicy.h
@@ -48,5 @@
>          return p;
>      }
>  
> -    template <size_t ElemSize>
> -    void* allocateArray(size_t n)

Ye gods.  How did you JIT people ever live with yourselves?  ;-)

::: js/src/vm/Runtime.h
@@ +1464,4 @@
>              reportAllocationOverflow();
>              return nullptr;
>          }
> +        return (T*)onOutOfMemoryCanGC(js::AllocFunction::Calloc, bytes);

static_cast<> these too

Comment 5

[Jeff Walden [:Waldo]]

Oh, smack MOZ_WARN_UNUSED_RESULT onto the size-computing functions, please.

Comment 6

[Jon Coppeard (:jonco)]

Comment on attachment 8668526 [details] [diff] [review]
temp-alloc-policy-overflow

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

Possible with a bit of effort but not trivial. 

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

No.

Which older supported branches are affected by this flaw?

Everything back to FF35.

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

Bug 1033442.

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

This patch should apply or if not it should be a simple merge.

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

Unlikely to cause regressions.

Comment 7

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

Comment on attachment 8668526 [details] [diff] [review]
temp-alloc-policy-overflow

Sec-approval+ for trunk. Please nominate for branches, including ESR38 if the patch applies (or add patches and nominate those if it doesn't).

Comment 8

[Jon Coppeard (:jonco)]

Attachment: bug1208665-temp-alloc-policy

This is a rolled up patch containing the two previous patches and incorporating review feedback which is I'm going to land.  Carrying r+.

Comment 9

[Jon Coppeard (:jonco)]

Attachment: bug1208665-temp-alloc-policy-aurora

Patch for aurora.

Comment 10

[Jon Coppeard (:jonco)]

Attachment: bug1208665-temp-alloc-policy-beta

Patch for beta.

Comment 11

[Jon Coppeard (:jonco)]

Attachment: bug1208665-temp-alloc-policy-esr38

Patch for ESR38.

Comment 12

[Jon Coppeard (:jonco)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e2feb3a13f83

Comment 13

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

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

Comment 14

[Sylvestre Ledru [:Sylvestre]]

Jon, could you fill the uplift requests? thanks

Comment 15

[Jon Coppeard (:jonco)]

Comment on attachment 8670711 [details] [diff] [review]
bug1208665-temp-alloc-policy-aurora

Approval Request Comment
[Feature/regressing bug #]: Bug 1033442.
[User impact if declined]: Potential security vulnerability.
[Describe test coverage new/current, TreeHerder]: On central for two days.
[Risks and why]: Low.
[String/UUID change made/needed]: None.

Comment 16

[Jon Coppeard (:jonco)]

Comment on attachment 8670712 [details] [diff] [review]
bug1208665-temp-alloc-policy-beta

Approval Request Comment
[Feature/regressing bug #]: Bug 1033442.
[User impact if declined]: Potential security vulnerability.
[Describe test coverage new/current, TreeHerder]: On central for two days.
[Risks and why]: Low.
[String/UUID change made/needed]: None.

Comment 17

[Jon Coppeard (:jonco)]

Comment on attachment 8670730 [details] [diff] [review]
bug1208665-temp-alloc-policy-esr38

[Approval Request Comment]
[User impact if declined]: Potential security vulnerability.
Fix Landed on Version: 44
Risk to taking this patch (and alternatives if risky): Low.
String or UUID changes made by this patch: None.

Comment 18

[Sylvestre Ledru [:Sylvestre]]

Comment on attachment 8670711 [details] [diff] [review]
bug1208665-temp-alloc-policy-aurora

Taking it in aurora to have some backing time.

Comment 19

[Carsten Book [:Tomcat]]

Hi, this failed to apply:

patching file js/src/vm/MallocProvider.h
Hunk #1 FAILED at 53
Hunk #2 FAILED at 104
Hunk #3 FAILED at 159
3 out of 3 hunks FAILED -- saving rejects to file js/src/vm/MallocProvider.h.rej
patching file js/src/vm/Runtime.h
Hunk #1 FAILED at 1451
1 out of 1 hunks FAILED -- saving rejects to file js/src/vm/Runtime.h.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working directory
errors during apply, please fix and refresh bug1208665-temp-alloc-policy-aurora.patch

Comment 20

[Jon Coppeard (:jonco)]

(In reply to Carsten Book [:Tomcat] from comment #19)
I had landed this myself but forgot to post the link:

https://hg.mozilla.org/releases/mozilla-aurora/rev/71d66bec5570

Comment 21

[Carsten Book [:Tomcat]]

setting flag per comment #20

Comment 22

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

Is there a reason we haven't taken this on Beta? It is a sec-high security bug.

Comment 23

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

(Same question applies to ESR38 as well)

Comment 24

[Sylvestre Ledru [:Sylvestre]]

Comment on attachment 8670712 [details] [diff] [review]
bug1208665-temp-alloc-policy-beta

Because the patch was pretty big and I wanted to check for potential fall out in aurora.

Comment 25

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/releases/mozilla-beta/rev/a304fc92ad35

Comment 26

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/releases/mozilla-esr38/rev/a6799573f909

Comment 27

[Carsten Book [:Tomcat]]

Hi, this failed for 2.2

merging js/public/Utility.h
warning: conflicts during merge.
merging js/public/Utility.h incomplete! (edit conflicts, then use 'hg resolve --mark')
merging js/src/ds/LifoAlloc.h
warning: conflicts during merge.
merging js/src/ds/LifoAlloc.h incomplete! (edit conflicts, then use 'hg resolve --mark')
merging js/src/jit/FixedList.h
warning: conflicts during merge.
merging js/src/jit/FixedList.h incomplete! (edit conflicts, then use 'hg resolve --mark')
merging js/src/jit/JitAllocPolicy.h
warning: conflicts during merge.
merging js/src/jit/JitAllocPolicy.h incomplete! (edit conflicts, then use 'hg resolve --mark')
merging js/src/jit/LIR.cpp
merging js/src/jit/MIRGenerator.h
merging js/src/jit/MIRGraph.cpp
merging js/src/vm/MallocProvider.h
warning: conflicts during merge.
merging js/src/vm/MallocProvider.h incomplete! (edit conflicts, then use 'hg resolve --mark')
merging js/src/vm/Runtime.h
abort: unresolved conflicts, can't continue

could you take a look, thanks!

Comment 28

[Jon Coppeard (:jonco)]

Attachment: bug1208665-temp-alloc-policy-b2g37_2_2

Here's a merged patch.