1205157 - (CVE-2015-7183) NSPR overflow in PL_ARENA_ALLOCATE can lead to crash (under ASAN), potential memory corruption

Status: RESOLVED FIXED

(NSPR :: NSPR, defect)

Description

[Ryan Sleevi]

Consider the following (simple) application, which uses NSS (rather than NSPR directly)

#include <secport.h>
int main(int argc, char** argv)
{
  PLArenaPool* temparena = NULL;
  temparena = PORT_NewArena(2048);
  if (temparena == NULL) return -1;  // Fatal allocation error

  void* foo = PORT_ArenaAlloc(temparena, 808464432);
  if (foo == NULL) return 0;  // Benign allocation failure (too large)

  PORT_FreeArena(temparena, PR_FALSE);
  return 0;
}

Run the above application with
ASAN_OPTIONS=verbosity=3:allocator_may_return_null=1 ./a.out

And see it crash with a message somewhat similar to the followin:
Trying to unpoison memory region [0xf4900fa0, 0x24c03fd0)

The crash is on the PORT_ArenaAlloc call, which, if you dig into further, is in the call to PL_ARENA_ALLOCATE ( http://mxr.mozilla.org/nss/source/lib/util/secport.c#272 )

The crash itself is in the expansion of the macro PL_MAKE_MEM_UNDEFINED, called / expanded at http://mxr.mozilla.org/nspr/source/lib/ds/plarena.h#149

The problem is that PL_ARENA_ALLOCATE doesn't check for overflow before determining whether or not enough memory exists, and as a result, overflows. The crash is ASAN yelling at the overflow.

Specifically, http://mxr.mozilla.org/nspr/source/lib/ds/plarena.h#142 and http://mxr.mozilla.org/nspr/source/lib/ds/plarena.h#143

Example values of _p and _nb in my case
_p = 4109373344
_nb = 808464432
_q = _p + _nb = 622870480

_q < _p, therefore NSPR assumes the memory can be used directly from _p (that it already allocated enough), and Bad Things Happen. What's supposed to happen is that it would call PL_ArenaAllocate and let that yell at the user for the (large) allocation. Instead, it sets _a->avail = _q, which includes a wide swath of memory not allocated, and then returns _p to the caller, as if the large allocation succeeded.

In ASAN mode, this crashes when PL_MAKE_MEM_UNDEFINED is called, because _q < _p.
In non-ASAN mode, no crashes, just wild writes.

Comment 1

[Ryan Sleevi]

Because this is in plarena.h, this affects every NSPR-using application and requires they be recompiled.

The 'correct' check can be found in PL_ArenaAllocate - http://mxr.mozilla.org/nspr/source/lib/ds/plarena.c#156

"if (nb <= a->limit - a->avail) {" then it's safe to use the current arena. Otherwise, allocate.

The following needs to be rewritten from http://mxr.mozilla.org/nspr/source/lib/ds/plarena.h#141

PRUword _p = _a->avail;
if (_nb > (_a->limit - _a->avail)) {
  _p = (PRUWord)PL_ArenaAllocate(pool, _nb);
} else {
  _a->avail += _nb;
}

Comment 2

[Ryan Sleevi]

Note: PL_ARENA_GROW suffers from a similar overflow issue.

Comment 3

[Ryan Sleevi]

More overflow: PL_ArenaGrow itself can cause overflow during addition, resulting in arbitrary writes:

http://mxr.mozilla.org/nspr/source/lib/ds/plarena.c#233

Comment 4

[Ryan Sleevi]

Attachment: Fix overflows and make ASAN friendly

wtc: Please take an initial look and see if I botched the math.

This patch does three things:
1) Fix PL_ARENA_ALLOCATE for the overflow for large sizes
2) (Partially) fix PL_ARENA_GROW for the overflow for large sizes
3) Make the existing poisoning functions ASAN-friendly by handling situations where allocation fails and we get a NULL return (useful when ASAN_OPTIONS=allocator_may_return_null=1 , which is useful for fuzzing the allocator)

Comment 5

[Wan-Teh Chang]

Comment on attachment 8661611 [details] [diff] [review]
Fix overflows and make ASAN friendly

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

Hi Ryan,

I only skimmed through the bug report, but I read this patch
very carefully. I have some suggested changes. Thanks.

::: lib/ds/plarena.h
@@ +101,5 @@
>  void __asan_poison_memory_region(void const volatile *addr, size_t size);
>  void __asan_unpoison_memory_region(void const volatile *addr, size_t size);
>  #define PL_MAKE_MEM_NOACCESS(addr, size) \
> +    PR_BEGIN_MACRO \
> +        if ((addr)) { \

IMPORTANT: ideally we should not silently ignore null pointers.
Can this be avoided? I found one instance in PL_ARENA_ALLOCATE
where this can be avoided.

@@ +157,3 @@
>          } \
>          p = (void *)_p; \
>          PL_MAKE_MEM_UNDEFINED(p, nb); \

I would do a null pointer check here and skip all remaining
statements if |p| is null:

    p = (void *)_p; \
    if (p) { \
      PL_MAKE_MEM_UNDEFINED(p, nb); \
      PL_ArenaCountAllocation(pool, nb); \
    } \

@@ +167,1 @@
>          if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \

It seems that we don't need the local variable |_p| and can just
use _a->avail in this conditional expression.

@@ +167,2 @@
>          if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
> +            (_a->limit - _a->avail) > _incr) { \

1. I think we should use >= here (allowing equality) as the
original code does. It is OK for _a->avail to become
equal to _a->limit.

2. Nit: it would be better to reverse the comparison so that
it is in the same order as the comparison in PL_ARENA_ALLOCATE:

    incr <= (_a->limit - _a->avail)) { \

@@ +169,1 @@
>              PL_MAKE_MEM_UNDEFINED((unsigned char *)(p) + size, incr); \

Hmm... I wonder if we need to sanity-check |size| here.

@@ +171,5 @@
>              PL_ArenaCountInplaceGrowth(pool, size, incr); \
>          } else { \
>              p = PL_ArenaGrow(pool, p, size, incr); \
>          } \
>          PL_ArenaCountGrowth(pool, size, incr); \

This probably should be put inside a null pointer check for |p|:

    if (p) { \
        PL_ArenaCountGrowth(pool, size, incr); \
    } \

Comment 6

[Wan-Teh Chang]

Attachment: Additional checks

Ryan: please incorporate these changes into your patch. Thanks.

Comment 7

[Wan-Teh Chang]

Comment on attachment 8661611 [details] [diff] [review]
Fix overflows and make ASAN friendly

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

These two callers of PL_ARENA_ALIGN should defend against
integer overflow. Please incorporate these changes into
your patch.

::: lib/ds/plarena.h
@@ +149,5 @@
>      PR_BEGIN_MACRO \
>          PLArena *_a = (pool)->current; \
>          PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \
>          PRUword _p = _a->avail; \
> +        if (_nb > (_a->limit - _a->avail)) { \

I found that the addition inside the PL_ARENA_ALIGN macro
may overflow if |nb| is close to the maximum value of PRUword.
Since |nb| is PRUint32, this only affects 32-bit builds.

We must not use _nb if _nb < nb. So here we should do something
like this:

    PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \
    PRUword _p = _a->avail; \
    if (_nb < nb) { \
        _p = 0; \
    } else if (_nb > (_a->limit - _a->avail)) { \
        _p = (PRUword)PL_ArenaAllocate(pool, _nb); \
    } else { \
    ...

@@ +167,1 @@
>          if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \

Here we also need to detect _incr < incr and reject it:

    PRUint32 _incr = PL_ARENA_ALIGN(pool, incr); \
    if (_incr < incr) { \
        p = NULL; \
    } else if (_a->avail == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
               incr <= (_a->limit - _a->avail)) { \
        _a->avail += _incr; \
        PL_ArenaCountInplaceGrowth(pool, size, incr); \
    } else { \
    ...

Comment 8

[Wan-Teh Chang]

Attachment: Other places that need auditing

I did a careful review for other integer overflows in
the three nspr/lib/ds/plarena* files. I searched for
the following strings in these files:
    ->limit
    +

I believe these, especially "+", should cover this
class of integer overflow exhaustively.

I've fixed four additional problems. This patch marks
the remaining places that still need auditing.

Comment 9

[Ryan Sleevi]

Comment on attachment 8661611 [details] [diff] [review]
Fix overflows and make ASAN friendly

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

::: lib/ds/plarena.h
@@ +101,5 @@
>  void __asan_poison_memory_region(void const volatile *addr, size_t size);
>  void __asan_unpoison_memory_region(void const volatile *addr, size_t size);
>  #define PL_MAKE_MEM_NOACCESS(addr, size) \
> +    PR_BEGIN_MACRO \
> +        if ((addr)) { \

Right, the API contract is that we shouldn't be calling these with NULLs. We could PR_ASSERT, or we could make sure the callers to this (which should only be internal) are consistent. I'll go your route and make it the consistency contract of the caller to check allocation failures, rather than swallowing the error here in the macro.

@@ +169,1 @@
>              PL_MAKE_MEM_UNDEFINED((unsigned char *)(p) + size, incr); \

We already check size by virtue of the earlier check on _a->avail ==

Since PL_ARENA_ALIGN should return >= size, and we know _a->avail == p + size, and we know incr is valid, we should be fine here for this call.

Comment 10

[Ryan Sleevi]

Comment on attachment 8662084 [details] [diff] [review]
Other places that need auditing

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

::: lib/ds/plarena.c
@@ +104,5 @@
>       * sizeof(PLArena) + pool->mask is the header and alignment slop
>       * that PL_ArenaAllocate adds to the net size.
>       */
> +    // XXX verify pool->mask = PR_BITMASK(PR_CeilingLog2(align)) is small.
> +    // This is very likely to be true because of the log2 operation.

Agreed

::: lib/ds/plarena.h
@@ +127,5 @@
> +// XXX Audit the callers of PL_ARENA_ALIGN because the addition of
> +// PL_ARENA_CONST_ALIGN_MASK or (pool)->mask may overflow.
> +// Callers must verify that the return value of PL_ARENA_ALIGN is >= the second
> +// argument. The second argument can be a byte count or an address. The callers
> +// that pass a byte count must be audited.

Why don't the callers that pass a pointer need to be audited? Wouldn't the same risk occur?

@@ +160,5 @@
>          PLArena *_a = (pool)->current; \
>          PRUint32 _incr = PL_ARENA_ALIGN(pool, incr); \
>          PRUword _p = _a->avail; \
>          PRUword _q = _p + _incr; \
> +        /* XXX can this addition overflow? */ \

It can overflow, yes, but the overflow itself would lead to the conditional being valse (_p == _a->avail), unless _a->avail was already botched. The only way would be if PL_ARENA_ALIGN(pool, size) were to == PR_UWORD_MAX, but that'd arguably be a violation of the macros' unstated but seemingly implied contract of size being <= PR_UWORD_MAX >> 1

@@ +165,3 @@
>          if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
>              _q <= _a->limit) { \
> +            /* XXX can this addition overflow? */ \

No, so long as the invariant on line 165 holds, and that sizeof(unsigned char*) == sizeof(PRUword)

Comment 11

[Ryan Sleevi]

Attachment: Merged patch

Wan-Teh: This integrates your changes and the documentation update. I didn't mark this as obsoleting the audit because I didn't do all the alignment checks yet, but the major ones I think are resolved.

Comment 12

[Wan-Teh Chang]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

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

r=wtc. Thanks.

::: lib/ds/plarena.c
@@ +94,5 @@
>  
>      pool->first.next = NULL;
> +    /* Set all three addresses in pool->first to the same dummy value.
> +     * These addresses are only compared with each other, but never
> +     * dereferenced. */

Ryan, I assume you verified what I wrote here is correct.

I also wondered if we should just set these three addresses to 0
to make it clear it's a dummy value, but didn't want to risk
introducing a bug in a bug fix.

::: lib/ds/plarena.h
@@ +136,5 @@
>  
>  #define PL_ARENA_ALLOCATE(p, pool, nb) \
>      PR_BEGIN_MACRO \
>          PLArena *_a = (pool)->current; \
>          PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \

Additional notes:

1. I verified with a test in 32-bit Linux that the addition inside
PL_ARENA_ALIGN does overflow. PRUword is an unsigned integer type.
I remember the C language specifies the unsigned overflow behavior
to be a wraparound. So we can detect an overflow after the fact by
checking if the result is less than the input.

2. PL_ARENA_ALIGN has two definitions. The first definition uses
the PL_ARENA_CONST_ALIGN_MASK symbolic constant. I think the
PL_ARENA_CONST_ALIGN_MASK constant must as long as a PWUword,
otherwise its bitwise negation ~PL_ARENA_CONST_ALIGN_MASK will be
too short and set the most significant 32 bits of a pointer input
to 0 (in a 64-bit build).

We should make sure we are not using PL_ARENA_CONST_ALIGN_MASK,
and add a comment to point that out. Perhaps we should change

    ~PL_ARENA_CONST_ALIGN_MASK

to

    ~(PRUword)PL_ARENA_CONST_ALIGN_MASK

Comment 13

[Ryan Sleevi]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

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

::: lib/ds/plarena.c
@@ +94,5 @@
>  
>      pool->first.next = NULL;
> +    /* Set all three addresses in pool->first to the same dummy value.
> +     * These addresses are only compared with each other, but never
> +     * dereferenced. */

Yes :)

I had wondered the same thing too when I was initially debugging, but I felt the same apprehension.

::: lib/ds/plarena.h
@@ +136,5 @@
>  
>  #define PL_ARENA_ALLOCATE(p, pool, nb) \
>      PR_BEGIN_MACRO \
>          PLArena *_a = (pool)->current; \
>          PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \

Neither the NSS nor NSPR code are using this, so it might be suitable to defer.

However, you are correct that if defined, it MUST be of the same length as a PRUword

Changing the ~(PRUword)PL_ARENA_CONST_ALIGN_MASK wouldn't address this, however, would it? It'd still promote a smaller type and zero out the most significant bits.

Comment 14

[Ryan Sleevi]

Poking Dan on this bug to see if there's any coordination required here.

I think it's preferable that we land the fixes for NSS and NSPR as close together as possible, and the fixes to Firefox and Chrome as coordinated as possible, given the nature of risk.

Consider this a "checkin-needed-but-don't-do-it-yet"

Comment 15

[Wan-Teh Chang]

Comment on attachment 8662084 [details] [diff] [review]
Other places that need auditing

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

::: lib/ds/plarena.h
@@ +127,5 @@
> +// XXX Audit the callers of PL_ARENA_ALIGN because the addition of
> +// PL_ARENA_CONST_ALIGN_MASK or (pool)->mask may overflow.
> +// Callers must verify that the return value of PL_ARENA_ALIGN is >= the second
> +// argument. The second argument can be a byte count or an address. The callers
> +// that pass a byte count must be audited.

My assumption is that the pointer is an address return by malloc().
Then, the pointer should not be close to the maximum value of PRUword
in practice.

It may be safer to just audit all callers of PL_ARENA_ALIGN.

@@ +160,5 @@
>          PLArena *_a = (pool)->current; \
>          PRUint32 _incr = PL_ARENA_ALIGN(pool, incr); \
>          PRUword _p = _a->avail; \
>          PRUword _q = _p + _incr; \
> +        /* XXX can this addition overflow? */ \

I studied this code more. The PL_ARENA_GROW macro assumes we previously
requested |size| bytes at address |p| successfully from |pool|. Under
that assumption, I think the addition

    (PRUword)(p) + PL_ARENA_ALIGN(pool, size)

and the addition inside PL_ARENA_ALIGN(pool, size) cannot overflow because
it merely recreates what |pool| did when it allocated |size| bytes at
address |p|.

Re: the implied contract of the PL_ARENA_ALIGN macro:

I verified with a test that the PL_ARENA_ALIGN macro works for the input
PR_UWORD_MAX - 128. So size doesn't need t be <= PR_UWORD_MAX >> 1.

The input PR_UWORD_MAX - 4 causes an overflow.

@@ +165,3 @@
>          if (_p == (PRUword)(p) + PL_ARENA_ALIGN(pool, size) && \
>              _q <= _a->limit) { \
> +            /* XXX can this addition overflow? */ \

You are right. This is also guaranteed by the assumption that
|p| and |size| are the results of a previous successful allocation
from |pool|.

Comment 16

[Wan-Teh Chang]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

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

::: lib/ds/plarena.h
@@ +136,5 @@
>  
>  #define PL_ARENA_ALLOCATE(p, pool, nb) \
>      PR_BEGIN_MACRO \
>          PLArena *_a = (pool)->current; \
>          PRUint32 _nb = PL_ARENA_ALIGN(pool, nb); \

I found that if PL_ARENA_CONST_ALIGN_MASK is defined
as a 32-bit (signed) int constant, the current code
~PL_ARENA_CONST_ALIGN_MASK still works. I presume the
most significant 32 bits are 1s due to sign extension.

I can only break the code if PL_ARENA_CONST_ALIGN_MASK
is defined as a 32-bit unsigned integer constant. (This
is unlikely to happen, which makes this bug unimportant.)
Here is a demo. I use the C99 uintptr_t type to simulate
PRUword.

$ cat cast.c
#include <stdio.h>
#include <inttypes.h>

#define PL_ARENA_CONST_ALIGN_MASK 15U

int main() {
  uintptr_t a = ~PL_ARENA_CONST_ALIGN_MASK;
  uintptr_t b = ~(uintptr_t)PL_ARENA_CONST_ALIGN_MASK;

  printf("a=%" PRIxPTR ", b=%" PRIxPTR "\n", a, b);
  return 0;
}
$ gcc -m64 -Wall cast.c
$ ./a.out
a=fffffff0, b=fffffffffffffff0

Comment 17

[Daniel Veditz [:dveditz]]

(In reply to Ryan Sleevi from comment #14)
> I think it's preferable that we land the fixes for NSS and NSPR as close
> together as possible, and the fixes to Firefox and Chrome as coordinated as
> possible, given the nature of risk.
> 
> Consider this a "checkin-needed-but-don't-do-it-yet"

Let's use the nss-dev list and call to coordinate timing on these

Comment 18

[Wan-Teh Chang]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

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

::: lib/ds/plarena.h
@@ +166,5 @@
>              PL_ArenaCountInplaceGrowth(pool, size, incr); \
>          } else { \
>              p = PL_ArenaGrow(pool, p, size, incr); \
>          } \
> +        if (p) {\

Nit: add a space before the backslash.

Comment 19

[Daniel Veditz [:dveditz]]

Use CVE-2015-7183 for this issue

Comment 20

[Sylvestre Ledru [:Sylvestre]]

David, do you know if esr38 is affected? Thanks

Comment 21

[Ryan Sleevi]

Firefox 43 is not (yet) fixed, as we haven't landed any changes. Affected, perhaps?
Firefox 38 is affected by this issue.

Comment 22

[Sylvestre Ledru [:Sylvestre]]

Typo, sorry about that.

Comment 23

[Wan-Teh Chang]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

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

::: lib/ds/plarena.h
@@ +156,5 @@
>  #define PL_ARENA_GROW(p, pool, size, incr) \
>      PR_BEGIN_MACRO \
>          PLArena *_a = (pool)->current; \
>          PRUint32 _incr = PL_ARENA_ALIGN(pool, incr); \
> +        if (_incr < incr) { \

I verified what we do here is the postcondition test for unsigned integer addition
recommended by CERT C Coding Standard in INT30-C:

https://www.securecoding.cert.org/confluence/display/c/INT30-C.+Ensure+that+unsigned+integer+operations+do+not+wrap

Here, the addition is hidden inside the PL_ARENA_ALIGN macro, which makes the
precondition test inconvenient. So I use the postcondition test instead.

Comment 24

[Ryan Sleevi]

Adding Apple Product Security due to this affecting libsecurity_asn1 ( https://opensource.apple.com/source/Security/Security-57031.40.6/Security/libsecurity_asn1/lib/ )

Comment 25

[Kai Engert [:KaiE:]]

Comment on attachment 8662101 [details] [diff] [review]
Merged patch

Landed into NSPR trunk:
https://hg.mozilla.org/projects/nspr/rev/c9c965b2b19c

Comment 26

[Kai Engert [:KaiE:]]

This failed to build in Firefox.

A call to PL_ARENA_ALLOCATE caused:
xpcom/ds/nsPersistentProperties.cpp:31:119: error: comparison between signed and unsigned integer expressions [-Werror=sign-compare]

Looks like we must use typecasts for the parameters. We should check all comparisons introduced in the patch.

Comment 27

[Kai Engert [:KaiE:]]

The new comparisons in the .c file all look fine to me, all comparisons are between variables of the same types.

For the new comparisons in the .h file, the type depends on what parameter the caller provides.

To fix the warning/error about comparisons of different sizes, it would be sufficient to use a typecast in the comparison statements, only. However, I don't like the idea that we use the parameter with a different type in the other operations.

I suggest that we use a typecast for all operations in the macro that use the affected parameter.

Comment 28

[Kai Engert [:KaiE:]]

Attachment: typecast fixes v1

Comment 29

[Tim Taubert [:ttaubert] (inactive)]

Comment on attachment 8674727 [details] [diff] [review]
typecast fixes v1

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

LGTM.

Comment 30

[Kai Engert [:KaiE:]]

Comment on attachment 8674727 [details] [diff] [review]
typecast fixes v1

Thanks for the review.
https://hg.mozilla.org/projects/nspr/rev/bd8fb4498fa6

Comment 31

[Kai Engert [:KaiE:]]

How should this issue be documented in the future release notes?

Comment 32

[Kai Engert [:KaiE:]]

Attachment: patch with bustage/typecast fixes merged in

Comment 33

[Ryan Sleevi]

A logic bug in the handling of large allocations would allow exceptionally large allocations to be reported as successful, without actually allocating the requested memory. This may allow attackers to bypass security checks and obtain control of arbitrary memory.

This issue affects applications that were compiled with or linked against an affected NSPR version; to resolve this issue, affected applications must be recompiled with a non-affected NSPR version.

Comment 34

[Sylvestre Ledru [:Sylvestre]]

We landed these changes, updating the tracking flags accordingly.

Comment 35

[Kai Engert [:KaiE:]]

This is fixed in NSPR 4.10.10, which is scheduled to be released on Nov 3.

I've just requested to add the 4.10.10 target milestone in bug 1219838, once done, let's mark this bug fixed.

Comment 36

[Elio Maldonado]

CVE-2015-7183 is no longer embargoed and release notes updated. What's keeping this bug from being made public?