Closed Bug 466445 Opened 16 years ago Closed 6 years ago

|new []| can integer-overflow with gcc (g++)

Categories

(Core :: Security, defect)

Product:
Core
Component:
Security
Platform:
x86
Linux
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED WORKSFORME

People

(Reporter: guninski, Unassigned)

References

(
URL
)

Details

(Keywords: meta, sec-want, Whiteboard: [sg:want P2][gcc bug])

Attachments

(4 files, 1 obsolete file)

demo - new1.cc
201 bytes, text/plain
Details
new2.cc - crashing testcase
574 bytes, text/plain
Details
Test case
12.38 KB, patch
Details | Diff | Splinter Review
Patch
2.57 KB, patch
Details | Diff | Splinter Review
Attached file demo - new1.cc — 
once upon a time |calloc(BIG,BIG)| silently overflowed, now it is fixed.

nowadays |new int[bignumber]| overflows as in:

volatile size_t n;
n= 4+((size_t)-1)/sizeof(int);
int *ptr;
cout << "n=" << n << endl;
ptr=new int[n];
cout << "ptr=" << ptr << endl;

|int| may be replaced by another |Class|.

ironically, fixing with checking for overflow of sizeof(Class)*numclasses is not enough because g++ adds |epsilon| >= sizeof(size_t) probably to know how many |this| to destruct later.

another oddity is a class that has no properties, just methods, has sizeof(Class) == 1 ( i naiively expected 0) and it is possible to |new []| *a lot of them* with completely invalid |this| without crashing, though such cases are probably not very realistic.

testcase attached.
to clarify:
1. the testcase returns valid |ptr| that is quite underallocated, not 0
2. probably this should be fixed in g++ or the implementation of |new|
Product: Firefox → Core
QA Contact: firefox → toolkit
/tmp$ ./a.out 
size=4
n=4611686018427387903 (size_t) (n * sizeof(Class))=18446744073709551612
Segmentation fault
so i wrote on the gcc mailing list:
http://gcc.gnu.org/ml/gcc/2008-11/msg00313.html

this is a known bug documented here:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19351
GCC Bugzilla Bug 19351 operator new[] can return heap blocks which are too small
Attachment #349729 - Attachment mime type: text/x-c++src → text/plain
Attachment #349731 - Attachment mime type: text/x-c++src → text/plain
"Patches wanted" they say, can we supply them?
URL: http://gcc.gnu.org/bugzilla/show_bug....
Keywords: meta
Whiteboard: [sg:investigate] bug in gcc
To confirm: we cannot fix this problem by using a user-defined ::operator new, right, because the problem is in the parameter passed *into* that function? cc'ing a few people who've hacked GCC...
(In reply to comment #5)
> To confirm: we cannot fix this problem by using a user-defined ::operator new,
> right, because the problem is in the parameter passed *into* that function?

Correct.  For a trivial 

  int* foo(size_t n) { return new int[n]; }

I get this with gcc 3.4.3 (linux, amd64):

	salq	$2, %rdi
	jmp	_Znam

the damage having already been done by the salq.  Similar bugs (within the runtime library) were fixed in the past, but I guess not this one :-(

> cc'ing a few people who've hacked GCC...

I used to know my way around the C++ front end pretty well; there's about a 75% chance this is an easy fix.  You will have to be careful not to trip over the, um, unclear semantics of the internal "size_type".  I recommend an early transformation from

   return new T[n];

to

   if (n > SIZE_MAX/sizeof(T)) {
      throw std::bad_alloc;
   } else {
      return new T[n];
   }

which I do not believe the optimizer will mess up.  I have too many other bugs on my plate to do it myself, but I'd be happy to kibitz a patch someone else wrote.

Also, I see Andrew Pinski was very negative about the possibility of fixing this in GCC.  In general, one should not take anything he says as the last word on the subject; he's just the guy who goes through GCC bugzilla looking for duplicates.  He's been told several times to stop being so nasty to people who write bug reports, and he doesn't listen. :-(  If Richard Guenther says patches are welcome, that means a hell of a lot more than anything Andrew says.
Just poking around without really knowing anything about gcc, but build_new_1() in init.c seemed promising (I was looking at 4.0.2 source).

   size = size_in_bytes (elt_type);
   if (array_p)
     {
       size = size_binop (MULT_EXPR, size, convert (sizetype, nelts));
       ...

where 'nelts' is number of elements. For arrays it also adds in a "cookie_size" a bit later so we need to make sure that doesn't cause an overflow as well.
Yeah, that looks like the place.
on the gcc mailing list i got personal reply from  Florian Weimer <fw@deneb.enyo.de> who seems involved with debian and seems interested in fixing this.

probably spamming some @redhat.com may help.

this is easily exploitable in cases like:

size_t n;
n=atol(str);
array=new T[n];
for(i=0;i<n;i++) {
	x=readfromnetworkorfile(...);
	if networkerror() break; [A]
	array[i]=x;
}

[A] gives exit condition that may stop a crash.

there is obstruction this to be generically exploitable.
so |new T[n]| basically multiplies n by sizeof(T).

if |n| comes from stuff in memory, the obstruction is to make |n| big enough without hitting OOM. greater sizeof(T) helps.

>To confirm: we cannot fix this problem by using a user-defined ::operator new,
>right, because the problem is in the parameter passed *into* that function?
>cc'ing a few people who've hacked GCC...

i *suspect* it is possible to fix it with overloading global |new|, though i am not ready to bet on it. overloading global |new| may help with the bug that |new| throws on OOM and doesn't return NULL as the codebase wrongly expects - there is a bug on it, something like |new throws in canvas|.
(In reply to comment #9)
> on the gcc mailing list i got personal reply from  Florian Weimer
> <fw@deneb.enyo.de> who seems involved with debian and seems interested in
> fixing this.

Yeah, I know him, he's good people.

> probably spamming some @redhat.com may help.

No, don't do that, you'll just annoy people and then it'll be harder to get patches reviewed later.

> i *suspect* it is possible to fix it with overloading global |new|, though
> i am not ready to bet on it.

I don't see how; the multiplication will still happen before the call.

> overloading global |new| may help with the bug that
> |new| throws on OOM and doesn't return NULL as the codebase wrongly expects -
> there is a bug on it, something like |new throws in canvas|.

I'm not sure what you mean by that, don't we compile everything with -fno-exceptions?  Maybe we also need -fcheck-new, or possibly #define new new(std::nothrow) somewhere.
>> i *suspect* it is possible to fix it with overloading global |new|, though
>> i am not ready to bet on it.

>I don't see how; the multiplication will still happen before the call.

ok, i am not sure about this.

>I'm not sure what you mean by that, don't we compile everything with
>-fno-exceptions?

the way firefox is compiled on linux, |new char[1UL << 38]| throws exception and calls abort() - it doesn't return NULL on 64 bit platforms.
this is Bug 353144
	
>or possibly #define new new(std::nothrow) somewhere.

sure this is possible.
Attached patch WIP (obsolete) — — Splinter Review 
Here's a first try, for gcc 4.3.0. I used a mix of zwol's idea and something that MSVC is said to do in the GCC bug. Passing a big value to the allocator seemed like the easiest way to cause a bad_alloc to be thrown.

I think this is almost what it needs to be, except to really work, cookie_size needs to be subtracted first. But I figured I'd get the strategy critiqued first, fixing that detail later should not be too hard.
I haven't read the code in detail, but ...

> Passing a big value to the allocator
> seemed like the easiest way to cause a bad_alloc to be thrown.

... don't do this; it'll never fly upstream.  What you need to do instead is check whether the operator new being called is declared throw().  If it is, write zero to the result.  If not, synthesize a call to std::__throw_bad_alloc().
(In reply to comment #14)
> I haven't read the code in detail, but ...
> 
> > Passing a big value to the allocator
> > seemed like the easiest way to cause a bad_alloc to be thrown.
> 
> ... don't do this; it'll never fly upstream.  

Can you expand on that? I was just asking for help getting your suggested alternative to work on #gcc, and someone mentioned the size_t max idea, and it met with approval from the 3 people that were talking with me on there.

If we can't use size_t max, then there are a few choices:

1. synthesize a throw. The problem here is that throw is not a statement, so this can't be done simply by modifying code generation of new[] expressions. It would have to reach up into the containing expression.

2. call something. The easy something is 'abort', I have that working. A harder something is to add a function to libsupc++ to throw a std::bad_alloc and then synthesize a call to that function.
I was thinking that we didn't really have a guarantee that passing size_t max to operator new would cause it to fail reliably, so people wouldn't like that.  Maybe there is such a guarantee that I don't know about; in any event, folks on #gcc are a more reliable authority than I am for what's likely to fly with upstream.
(In reply to comment #16)

I see. Their reasoning was that any conforming implementation would have to try to allocate the entire virtual address space, which would necessarily fail in any actual program. I'm gonna finish off my first try and send it to their patches list.
Attached patch Patch — — Splinter Review 
Here's a better patch. I added builtin_expect because someone asked me to. I'll send this to GCC if it looks good.
Attachment #352460 - Attachment is obsolete: true
hm, since current |new| implementation can fail now (either throw or NULL) there must be an existing codepath dealing with it?
Two comments on the patch: first, 

+  if (get_global_value_if_present (get_identifier ("__builtin_expect"),
+                                   &expect_fn))
+    ifexp = (build_function_call
+             (expect_fn,
+              tree_cons (NULL_TREE, ifexp, 
+                         build_tree_list (NULL_TREE, integer_zero_node))));

This can be written rather more simply as

+  expect_fn = implicit_built_in_decls[BUILT_IN_EXPECT];
+  gcc_assert (expect_fn);
+  ifexp = build_call_n (expect_fn, 2, ifexp, integer_zero_node);

-- see e.g. call_builtin_trap in cp/call.c.  Also, I am not sure whether you should be using size_type_node or just plain sizetype at this point in the code.  (I no longer remember exactly what the difference is, but I know that getting it wrong has a nasty way of appearing to work in simple cases but blowing up horribly on edge cases or platforms with weird memory characteristics.)

georgi: Yes, there is an existing codepath dealing with failure; it's not visible in the patch.  The point of this patch is to make a failure trigger when the array size is so big that the multiplication overflows.  I'm not sure what you're trying to get at.
i thought it was not trivial for the patch to trigger the failure so i suggested reusing the existing code path to trigger the failure.
Thanks for better way to call __builtin_expect. 

I started with sizetype and it didn't work at all. That's the first thing I tried to IRC you on. sizetype ended up doing everything with 64-bit arithmetic (on a 32-bit system, and with sizetype.precision == 32 -- very weird).

The code path to trigger the failure is inside the default allocator, which is presumably in libsupc++. Thus, this patch does actually reuse the existing code path by passing the allocator a value that will certainly trigger a failure.
fwiw, it looks like gcc expects tabs (8chars) for indentation
> it looks like gcc expects tabs (8chars) for indentation

It's true.
dmandelin, are you planning to submit a patch to gcc?  They seem to agree it's a bug.
Summary: |new []| better not overflow with g++ → |new []| can integer-overflow with g++
Whiteboard: [sg:investigate] bug in gcc → [sg:want P2][gcc bug]
GCC developers have rejected a patch with even less code footprint than the patch proposed here. I also think it's incomplete because it doesn't deal with wraparound in VLA size computation.
lol
how does the m$ compiler score on this  ?
(In reply to comment #27)
> lol
> how does the m$ compiler score on this  ?

It's fixed in Visual Studio 2005, using basically the same approach as in my patch for GCC: the size calculation happens inline, at the caller, and if it overflows, -1 is passed to the underlying allocation function.
10x Florian. do you happen to know if vendor-sec@lst.de have opinion about "not trusting the compiler"    ?
...or they are too busy filing CVE(tm)(r) IDs?
(In reply to comment #29)
> 10x Florian. do you happen to know if vendor-sec@lst.de have opinion about "not
> trusting the compiler"    ?
> ...or they are too busy filing CVE(tm)(r) IDs?

The consensus seems to be that it's a compiler bug worth fixing, it's just that none of the vendors have told their GCC contributors to review and shepherd one of the existing patches (or maybe they aren't structured that way as a company, making that close to impossible).  I also didn't feel comfortable pushing non-accepted patches into Debian.

By the way, C++0X seems to require throwing a subclass of std::bad_alloc, so it might eventually be fixed.  It's a PITA, though, because that change requires an ABI bump (expanding the necessary code inline is too costly in terms of code size). There's also some compatibility issue with GCC's variable-length array extension. C++ implies that the multiplication in operator new[] is always constant times variable (only once dimension can vary), but with VLAs, you can actually end up with variable times variable times constant, which introduces additional overflow opportunities and is difficult to optimize for GCC.
Summary: |new []| can integer-overflow with g++ → |new []| can integer-overflow with gcc (g++)
Blocks: 615465
No longer blocks: 615465
may i beg to see the dependent bug 623998?
I just discovered this bug. It's terrifying! There must be a gold mine of security holes here, not just in our code but in everyone's C++ code.

(In reply to comment #30)
> The consensus seems to be that it's a compiler bug worth fixing, it's just that
> none of the vendors have told their GCC contributors to review and shepherd one
> of the existing patches (or maybe they aren't structured that way as a company,
> making that close to impossible).

OK, are there any GCC contributors we can bribe^H^H^H^H^Hpay to do that?
>OK, are there any GCC contributors we can bribe^H^H^H^H^Hpay to do that?

for a start you can try spamming the elitarian CVE® dispatchers at vendor-sec@lst.de (or whatever their spam alias is these days). if you play on their paranoia relatively well, they can do the delicate job of communicating with the gnu monoks for you.
(In reply to comment #33)
> >OK, are there any GCC contributors we can bribe^H^H^H^H^Hpay to do that?
> 
> for a start you can try spamming the elitarian CVE® dispatchers at
> vendor-sec@lst.de (or whatever their spam alias is these days). if you play on
> their paranoia relatively well, they can do the delicate job of communicating
> with the gnu monoks for you.

... or you could just ask Steve at MITRE directly. He's a pretty nice guy.
This has come up on vendor-sec a number of times, it's never received any traction from upstream. You guys may have more luck, let me know if I can be of any assistance.
If Mozilla is willing to pay someone to fix this, the obvious place to look for that someone is CodeSourcery (http://www.codesourcery.com/gnu_toolchains/services.html) (disclaimer: I used to work there)  They just got bought out by Mentor Graphics and I'm not sure how that's changed things, but custom improvements to GCC (including "get this into the official release") was their core business for many years.
assuming reasonable pricing, we're willing.  can someone spin it up?
(In reply to comment #35)
> This has come up on vendor-sec a number of times, it's never received any
> traction from upstream. You guys may have more luck, let me know if I can be of
> any assistance.

As mentioned above, a patch exist.  Someone who is familiar with the GCC type system needs to review it.  My current best fix is hampered by the fact that GCC's internal representation of size_t appears to be signed.
(In reply to comment #37)
> assuming reasonable pricing, we're willing.  can someone spin it up?

I'm contacting codesourcery.
I've posted a better GCC patch:

  http://gcc.gnu.org/ml/gcc-patches/2011-01/msg01593.html

Let's see if we can resolve the issue this time around.
pls ignore this. bugspam test.
Has there been any resolution as to what to do generally with the code? Review as suggested by bz in bug 576447, comment 8 (I believe nobody did that yet) or wait?

Simply grepping the source tree of mozilla-central gives roughly 750 occurences of potential problems, although many are either safe or not even a new[], it still is quite an interesting number.

IMHO GCC isn't likely to be fixed before 4.6.x or 4.7, which will be in several months (read 'a year'). (And it might not be the only compiler suffering from this problem.)
I don't think it makes sense to fix this anywhere other than the compiler. It's fixed in Visual C++, and gcc is the only other compiler we really care about.
Agree with comment 43, although we are looking forward to Clang on Mac soon-ish. Cc'ing Rafael in case he knows what it does for this bug.

/be
Looks like clang will call new with -1 if there is an overflow. Is that the expected behavior? The test function

int* foo(size_t n) { return new int[n]; }

compiles to

%0 = type { i64, i1 }

define noalias i32* @_Z3foom(i64 %n) nounwind optsize {
  %1 = tail call %0 @llvm.umul.with.overflow.i64(i64 %n, i64 4)
  %2 = extractvalue %0 %1, 1
  %3 = extractvalue %0 %1, 0
  %4 = select i1 %2, i64 -1, i64 %3
  %5 = tail call noalias i8* @_Znam(i64 %4) nounwind optsize
  %6 = bitcast i8* %5 to i32*
  ret i32* %6
}

Or if you like x86_64 asm:

__Z3foom:
        movl    $4, %ecx
        movq    %rdi, %rax
        mulq    %rcx
        movq    $-1, %rdi
        cmovnoq %rax, %rdi
        jmp     __Znam
FWIW, this feature has now been implemented in GCC: http://gcc.gnu.org/ml/gcc-cvs/2012-08/msg00523.html
Component: Security → Security: S/MIME
Target Milestone: --- → mozilla14
Version: Trunk → 16 Branch
Component: Security: S/MIME → Security
Target Milestone: mozilla14 → ---
Version: 16 Branch → Trunk
Hey Nathan, can we close this out?
Flags: needinfo?(nfroyd)
GCC 6 produces, for the code in comment 45:

.LFB0:
	.cfi_startproc
	movabsq	$2305843009213693950, %rax
	cmpq	%rax, %rdi
	ja	.L2
	salq	$2, %rdi
	jmp	operator new[](unsigned long)
.L2:
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	call	__cxa_throw_bad_array_new_length
	.cfi_endproc

GCC 5 gives:

.LFB0:
	.cfi_startproc
	leaq	0(,%rdi,4), %rax
	movabsq	$2287828610704211968, %rdx
	cmpq	%rdx, %rdi
	movq	$-1, %rdi
	cmovbe	%rax, %rdi
	jmp	operator new[](unsigned long)
	.cfi_endproc

So I think we are good here.  We compile release versions with GCC 6 and we'll soon make GCC 6 or GCC 7 the minimum required version.
Status: NEW → RESOLVED
Closed: 6 years ago
Flags: needinfo?(nfroyd)
Resolution: --- → WORKSFORME
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: