Re: Integer overflow in operator new
On 4/9/07, Dave Korn <[EMAIL PROTECTED]> wrote: On 09 April 2007 21:49, Lawrence Crowl wrote: >>> The optimization above would be wrong for such machines because >>> the allocation would be smaller than the requested size. >> >> To request a size of ~size_t(0) is to request a size >> of 0x or 0xULL that the allocator >> will always "sorry, there is not memory of 0x or >> 0xULL bytes. > > Except on a segmented machine, where it will say "here you go!" > On segmented architectures sizeof(size_t) < sizeof(void*). Well, we could simply use uintptr_t instead of size_t. The standards are pretty insistent on uintptr_t. It appears, however, that gcc essentially requires a linear address space, so my objection is a moot. But it anyone were to do a segmented gcc, -- Lawrence Crowl
RE: Integer overflow in operator new
On 09 April 2007 21:49, Lawrence Crowl wrote: >>> The optimization above would be wrong for such machines because >>> the allocation would be smaller than the requested size. >> >> To request a size of ~size_t(0) is to request a size >> of 0x or 0xULL that the allocator >> will always "sorry, there is not memory of 0x or >> 0xULL bytes. > > Except on a segmented machine, where it will say "here you go!" > On segmented architectures sizeof(size_t) < sizeof(void*). Well, we could simply use uintptr_t instead of size_t. cheers, DaveK -- Can't think of a witty .sigline today
Re: Integer overflow in operator new. Solved? Experimental i686 code.
#include // by J.C. Pîzarro
...
// This function doesn't touch the ECX register that is touched by OptionC.
__volatile__ static const int minus_one = -1;
void *__allocate_array_OptionD(size_t num, size_t size) {
register unsigned int result;
__asm__ __volatile__
(
"imull %2" // See the flags OF, SF, CF, .. are affected or not.
"\n\t" "cmovol %3,%%eax" // i dude if it works or not. Not tested ...
//"\n\t" "cmovcl %3,%%eax"
:"=a"(result)
:"a"(num),"m"(size),"m"(minus_one)
:"%edx"/*???*/); // There are 0 conditional jumps!!! hehehehe!
return operator new[](result);
}
-
* gcc version 4.1.3 20070326 (prerelease)
* 6 instructions of i686 !!! (cmovo came from i686)
* no conditional jump !!!
_Z24__allocate_array_OptionDjj:
subl$12, %esp# <- unneeded
movl16(%esp), %eax
#APP
imull 20(%esp)
cmovol minus_one,%eax
#NO_APP
movl%eax, (%esp) # <- better movl %eax, 4(%esp)
call_Znaj# <- better jmp _Znaj
addl$12, %esp# <- unneeded
ret # <- unneeded
minus_one:
.long -1
-
* hand-written
* 5 instructions of i686 !!! (cmovo came from i686)
* no conditional jump !!!
_Z24__allocate_array_OptionDjj:
movl4(%esp), %eax
#APP
imull 8(%esp)
cmovol minus_one,%eax
#NO_APP
movl%eax, 4(%esp)
jmp _Znaj
minus_one:
.long -1
-
Here has reached 5 instructions.
Anyone with 4 instructions?
J.C. Pizarro
allocate_array_20070409-2.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
"Lawrence Crowl" <[EMAIL PROTECTED]> writes: [...] | Intel has had several popular processors with segmented addresses | including the 8086, 80186, and 80286. (Actually, the 80386 and | successors are segmented, but the operating systems typically hide | that fact.) The also had the i432. | | I think the IBM AS400 series may be segmented, though I'm not sure. I'm under the impression that none of them is GCC's target. Am I wrong? -- Gaby
Re: Integer overflow in operator new. Solved? Experimental i686 code.
#include // by J.C. Pîzarro
...
// See http://www.cs.sjsu.edu/~kirchher/CS047/multDiv.html
// One-operand imul: & Unsigned mul:
// warning: 32 bit, i686, possible risk of -x * -y = valid x * y, ...
// warning: it's made quick & dirty, possible to give clobbered situations.
// warning: it is not ready for x86-64, ppc, ppc64, etc.
// NO WARRANTY!!! IT'S VERY EXPERIMENTAL!!! NOT TESTED YET!!!
void *__allocate_array_OptionC(size_t num, size_t size) {
unsigned int result;
__asm__ __volatile__
(
"orl $-1,%%ecx"
"\n\t" "imull %2" // See the flags OF, SF, CF, .. are affected or not.
"\n\t" "cmovol %%ecx,%%eax" // i dude if it works or not. Not tested ...
//"\n\t" "cmovcl %%ecx,%%eax"
:"=a"(result)
:"a"(num),"g"(size)
:/*???*/); // There are 0 conditional jumps!!! hehehehe!
return operator new[](result);
}
-
* gcc version 4.1.3 20070326 (prerelease)
* 6 instructions of i686 !!! (cmovo came from i686)
* no conditional jump !!!
_Z24__allocate_array_OptionCjj:
movl4(%esp), %eax
#APP
orl $-1,%ecx
imull 8(%esp)
cmovol %ecx,%eax
#NO_APP
movl%eax, 4(%esp)
jmp _Znaj
-
J.C. Pizarro
allocate_array_20070409-1.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
On Mon, Apr 09, 2007 at 01:49:09PM -0700, Lawrence Crowl wrote: > On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote: > >We've working in linear address spaces. > >How for segmented address spaces? You give me examples. > > Intel has had several popular processors with segmented addresses > including the 8086, 80186, and 80286. (Actually, the 80386 and > successors are segmented, but the operating systems typically hide > that fact.) The also had the i432. Your objection doesn't matter, as gcc assumes a flat address space.
Re: Integer overflow in operator new
On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote:
2007/4/9, Lawrence Crowl <[EMAIL PROTECTED]>:
> On 4/7/07, Joe Buck <[EMAIL PROTECTED]> wrote:
> > Consider an implementation that, when given
> >
> > Foo* array_of_foo = new Foo[n_elements];
> >
> > passes __compute_size(elements, sizeof Foo) instead of
> > n_elements*sizeof Foo to operator new, where __compute_size is
> >
> > inline size_t __compute_size(size_t num, size_t size) {
> > size_t product = num * size;
> > return product >= num ? product : ~size_t(0);
> > }
> >
> > This counts on the fact that any operator new implementation has to
> > fail when asked to supply every single addressible byte, less one.
>
> This statement is true only for linear address spaces. For segmented
> address spaces, it is quite feasible to have a ~size_t(0) much smaller
> than addressable memory.
We've working in linear address spaces.
How for segmented address spaces? You give me examples.
Intel has had several popular processors with segmented addresses
including the 8086, 80186, and 80286. (Actually, the 80386 and
successors are segmented, but the operating systems typically hide
that fact.) The also had the i432.
I think the IBM AS400 series may be segmented, though I'm not sure.
> The optimization above would be wrong for such machines because
> the allocation would be smaller than the requested size.
To request a size of ~size_t(0) is to request a size
of 0x or 0xULL that the allocator
will always "sorry, there is not memory of 0x or
0xULL bytes.
Except on a segmented machine, where it will say "here you go!"
On segmented architectures sizeof(size_t) < sizeof(void*).
> > It would appear that the extra cost, for the non-overflow case, is
> > two instructions (on most architectures): the compare and the
> > branch, which can be arranged so that the prediction is not-taken.
>
> That is the dynamic count. The static count, which could affect
> density of cache use, should also include the alternate return value.
With CoreDuo, the density of cache use is not our problem because there
are L2 caches of 2 MiB! 4 MiB! and even more 6 MiB!!!.
Our main problem is to reach the maximum performance for future days.
The L1 (or sometimes L0) caches are much smaller, and execution speed
can be affected by instruction cache pressure. One can avoid the effect,
but not without basic block outlining.
--
Lawrence Crowl
Re: Integer overflow in operator new. Solved?
On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote: Of course, i'm a novice because i like and i don't like the GCC development's model. Of course the user manual explains all what I have mentioned in my previous email so it sounds like you like 95% of the other people who don't read the manual (yes we can improve it but that problem is different than the above one of not reading it period). How will it be the code using __builtin_constant_p that i don't know? Read the manual, it is listed there. -- Pinski
Re: Integer overflow in operator new. Solved?
On Apr 9, 2007, at 12:14 PM, J.C. Pizarro wrote: How many code's species are they? One for every problem... 7. Code for IPA??? <- i don't know this weird language. Is it with attributes?. 8. Code for GIMPLE??? <- i don't know this weird language. 9. Code for RTL??? <- i don't know this weird language. We can only write a 500 page manual that describes this, we can't force you to read it. :-)
Re: Integer overflow in operator new. Solved?
2007/4/9, J.C. Pizarro <[EMAIL PROTECTED]> wrote: 2007/4/9, Andrew Pinski <[EMAIL PROTECTED]> wrote: > On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote: > Well lets say this, we already support this to some extend, by using > __builtin_constant_p and then just inlining. Also there exists > already an optimization pass which does IPA constant prop. > > Guess you are not well into GCC development after all. > > -- Pinski > Of course, i'm a novice because i like and i don't like the GCC development's model. How will it be the code using __builtin_constant_p that i don't know? How many code's species are they? A compiler has codes that contains ...: 1. Middle level code of the language C. 2. Little higher level code of the language C++. 3. Code of the preprocessor of the language C/C++. 4. Low level code of the language ASM. 5. Inline asm code embedded into the language C/C++. 6. High level code of the language Java. 7. Code for IPA??? <- i don't know this weird language. Is it with attributes?. 8. Code for GIMPLE??? <- i don't know this weird language. 9. Code for RTL??? <- i don't know this weird language. 10. ...
Re: Integer overflow in operator new
> "Ross" == Ross Ridge <[EMAIL PROTECTED]> writes: Ross> So long as whatever switch is used to enable this check isn't on by Ross> default and its effect on code size and speed is documented, I don't Ross> think it matters that much what those effects are. Anything that works Ross> should make the people concerned about security happy. People more Ross> concerned with size or speed aren't going to enable this feature. I think it would be preferable to default to being safe, and let people who are concerned about shaving every byte or cycle disable the check. I suppose I think this because I have a preference for safety, and also because I suspect that the cost of this will be small. Naturally the latter should be measured first. Tom
Re: Integer overflow in operator new. Solved?
2007/4/9, Andrew Pinski <[EMAIL PROTECTED]>: On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote: > 3. To modify the C-preprocessor and/or C/C++ compiler for: >#if argument X is a constant then > use this code specific of constant X >#else if argument Y is not a constant then > use this code specific of non-constant Y >#else > use this general code >#endif Well lets say this, we already support this to some extend, by using __builtin_constant_p and then just inlining. Also there exists already an optimization pass which does IPA constant prop. Guess you are not well into GCC development after all. -- Pinski Of course, i'm a novice because i like and i don't like the GCC development's model. How will it be the code using __builtin_constant_p that i don't know?
Re: Integer overflow in operator new
2007/4/9, Lawrence Crowl <[EMAIL PROTECTED]>:
On 4/7/07, Joe Buck <[EMAIL PROTECTED]> wrote:
> Consider an implementation that, when given
>
> Foo* array_of_foo = new Foo[n_elements];
>
> passes __compute_size(elements, sizeof Foo) instead of
> n_elements*sizeof Foo to operator new, where __compute_size is
>
> inline size_t __compute_size(size_t num, size_t size) {
> size_t product = num * size;
> return product >= num ? product : ~size_t(0);
> }
>
> This counts on the fact that any operator new implementation has to
> fail when asked to supply every single addressible byte, less one.
This statement is true only for linear address spaces. For segmented
address spaces, it is quite feasible to have a ~size_t(0) much smaller
than addressable memory.
We've working in linear address spaces.
How for segmented address spaces? You give me examples.
The optimization above would be wrong for such machines because
the allocation would be smaller than the requested size.
To request a size of ~size_t(0) is to request a size
of 0x or 0xULL that the allocator will always
"sorry, there is not memory of 0x or 0xULL bytes.
> It would appear that the extra cost, for the non-overflow case, is
> two instructions (on most architectures): the compare and the
> branch, which can be arranged so that the prediction is not-taken.
That is the dynamic count. The static count, which could affect
density of cache use, should also include the alternate return value.
--
Lawrence Crowl
With CoreDuo, the density of cache use is not our problem because there are
L2 caches of 2 MiB! 4 MiB! and even more 6 MiB!!!.
Our main problem is to reach the maximum performance for future days.
J.C. Pizarro
Re: Integer overflow in operator new. Solved?
On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote: 3. To modify the C-preprocessor and/or C/C++ compiler for: #if argument X is a constant then use this code specific of constant X #else if argument Y is not a constant then use this code specific of non-constant Y #else use this general code #endif Well lets say this, we already support this to some extend, by using __builtin_constant_p and then just inlining. Also there exists already an optimization pass which does IPA constant prop. Guess you are not well into GCC development after all. -- Pinski
Re: Integer overflow in operator new
On 4/7/07, Joe Buck <[EMAIL PROTECTED]> wrote:
Consider an implementation that, when given
Foo* array_of_foo = new Foo[n_elements];
passes __compute_size(elements, sizeof Foo) instead of
n_elements*sizeof Foo to operator new, where __compute_size is
inline size_t __compute_size(size_t num, size_t size) {
size_t product = num * size;
return product >= num ? product : ~size_t(0);
}
This counts on the fact that any operator new implementation has to
fail when asked to supply every single addressible byte, less one.
This statement is true only for linear address spaces. For segmented
address spaces, it is quite feasible to have a ~size_t(0) much smaller
than addressable memory.
The optimization above would be wrong for such machines because
the allocation would be smaller than the requested size.
It would appear that the extra cost, for the non-overflow case, is
two instructions (on most architectures): the compare and the
branch, which can be arranged so that the prediction is not-taken.
That is the dynamic count. The static count, which could affect
density of cache use, should also include the alternate return value.
--
Lawrence Crowl
Re: Integer overflow in operator new. Solved?
"J.C. Pizarro" <[EMAIL PROTECTED]> writes: > To optimize even more the x86, it still has to use: > 1. Use imul instead of mul because it's little bit faster in cycles. > 2. Use jns/js (sign's conditional jump) instead of jnc/jc (carry's > conditional jump). > 3. To modify the C-preprocessor and/or C/C++ compiler for: >#if argument X is a constant then > use this code specific of constant X >#else if argument Y is not a constant then > use this code specific of non-constant Y >#else > use this general code >#else > > The 3rd option is too complex but powerful like nearly Turing machine ;) I think you may be looking at this at the wrong level. If we implement this (I don't care one way or the other, myself), it would be done by having the C++ frontend generate the appropriate GENERIC code before the call to operator new[]. Issues like imul vs. mul, or constant folding, are irrelevant at that level. Ian
Re: Integer overflow in operator new. Solved?
4. Conditional moves (cmov).
Re: Integer overflow in operator new. Solved?
2007/4/9, Joe Buck <[EMAIL PROTECTED]>:
On Mon, Apr 09, 2007 at 09:47:07AM -0700, Andrew Pinski wrote:
> On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote:
> >#include
> >
> >void *__allocate_array_OptionA(size_t num, size_t size) { // 1st best
> > unsigned long long tmp = (unsigned long long)size * num;
> > if (tmp >= 0x8000ULL) tmp=~size_t(0);
> > return operator new[](tmp);
> >}
>
> First this just happens to be the best for x86, what about PPC or
> really any embedded target where people are more concern about code
> size than say x86.
It's nowhere close to best for x86. But to get the best, you'd need
to use assembly language, and the penalty in time is one instruction:
insert a jnc (jump short if no carry), with the prediction flag set
as "taken", after the mull instruction. This would jump over code
to load all-ones into the result. You have to multiply, and the processor
tells you if there's an overflow.
A general approach would be to have an intrinsic for unsigned multiply
with saturation, have a C fallback, and add an efficient implemention of
the intrinsic on a per-target basis.
To optimize even more the x86, it still has to use:
1. Use imul instead of mul because it's little bit faster in cycles.
2. Use jns/js (sign's conditional jump) instead of jnc/jc (carry's
conditional jump).
3. To modify the C-preprocessor and/or C/C++ compiler for:
#if argument X is a constant then
use this code specific of constant X
#else if argument Y is not a constant then
use this code specific of non-constant Y
#else
use this general code
#else
The 3rd option is too complex but powerful like nearly Turing machine ;)
J.C. Pizarro
Re: Integer overflow in operator new. Solved?
On Mon, Apr 09, 2007 at 09:47:07AM -0700, Andrew Pinski wrote:
> On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote:
> >#include
> >
> >void *__allocate_array_OptionA(size_t num, size_t size) { // 1st best
> > unsigned long long tmp = (unsigned long long)size * num;
> > if (tmp >= 0x8000ULL) tmp=~size_t(0);
> > return operator new[](tmp);
> >}
>
> First this just happens to be the best for x86, what about PPC or
> really any embedded target where people are more concern about code
> size than say x86.
It's nowhere close to best for x86. But to get the best, you'd need
to use assembly language, and the penalty in time is one instruction:
insert a jnc (jump short if no carry), with the prediction flag set
as "taken", after the mull instruction. This would jump over code
to load all-ones into the result. You have to multiply, and the processor
tells you if there's an overflow.
A general approach would be to have an intrinsic for unsigned multiply
with saturation, have a C fallback, and add an efficient implemention of
the intrinsic on a per-target basis.
Re: Integer overflow in operator new. Solved?
On 4/9/07, J.C. Pizarro <[EMAIL PROTECTED]> wrote:
#include
void *__allocate_array_OptionA(size_t num, size_t size) { // 1st best
unsigned long long tmp = (unsigned long long)size * num;
if (tmp >= 0x8000ULL) tmp=~size_t(0);
return operator new[](tmp);
}
First this just happens to be the best for x86, what about PPC or
really any embedded target where people are more concern about code
size than say x86.
Also what about x86_64 where sizeof(size_t) == sizeof(unsigned long
long) so this trick is not going to work
-- Pinski
Re: Integer overflow in operator new. Solved?
#include
void *__allocate_array_OptionA(size_t num, size_t size) { // 1st best
unsigned long long tmp = (unsigned long long)size * num;
if (tmp >= 0x8000ULL) tmp=~size_t(0);
return operator new[](tmp);
}
void *__allocate_array_OptionB(size_t num, size_t size) { // 2nd best
unsigned long long tmp = (unsigned long long)size * num;
if (tmp >= 0x8000ULL) return(operator new[](~size_t(0)));
return operator new[](tmp);
}
-
_Z24__allocate_array_OptionAjj:
[ gcc 4.1.3 20070326 (prerelease) : 9 instructions ]
movl8(%esp), %eax
mull4(%esp)
cmpl$0, %edx
ja .L11
cmpl$2147483647, %eax
jbe .L9
.L11:
orl $-1, %eax
.L9:
movl%eax, 4(%esp)
jmp _Znaj
_Z24__allocate_array_OptionBjj:
[ gcc 4.1.3 20070326 (prerelease) : 10 instructions ]
movl8(%esp), %eax
mull4(%esp)
cmpl$0, %edx
ja .L4
cmpl$2147483647, %eax
jbe .L2
.L4:
movl$-1, 4(%esp)
jmp .L7# <- why not jmp _Znaj directly?
.L2:
movl%eax, 4(%esp)
.L7:
jmp _Znaj
-
It seems to be solved the integer overflow in operator new.
J.C. Pizarro.
allocate_array_longmult_april2007.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
On Tue, Apr 10, 2007 at 03:44:26AM +1200, Ross Smith wrote: > On Monday, 9 April 2007 13:09, J.C. Pizarro wrote: > > > > This code is bigger than Joe Buck's. > > > > Joe Buck's code: 10 instructions > > Ross Ridge's code: 16 instructions > > Ross Smith's code: 16 instructions > > Well, yes, but it also doesn't have the bug Joe's code had. That was > sort of the whole point. If you don't care whether it gives the right > answer you might as well just leave the status quo. Agreed; it's bogus to compare my bad code with anything else. But on most common platforms, I'm sure that there are assembly language sequences that will beat any of these.
Re: Integer overflow in operator new
2007/4/9, Ross Smith <[EMAIL PROTECTED]> wrote: On Monday, 9 April 2007 13:09, J.C. Pizarro wrote: > > This code is bigger than Joe Buck's. > > Joe Buck's code: 10 instructions > Ross Ridge's code: 16 instructions > Ross Smith's code: 16 instructions Well, yes, but it also doesn't have the bug Joe's code had. That was sort of the whole point. If you don't care whether it gives the right answer you might as well just leave the status quo. -- Ross Smith [EMAIL PROTECTED] Auckland, New Zealand "Those who can make you believe absurdities can make you commit atrocities."-- Voltaire I'm sorry Ross Smith due to my bug. In http://gcc.gnu.org/ml/gcc/2007-04/msg00232.html appears I'm sorry, the previous 3rd source code .c is an error mine. Joe Buck's code: 10 instructions Ross Ridge's code: 16 instructions Ross Smith's code: 23 instructions # <- rectified. J.C. Pizarro
Re: Integer overflow in operator new
On Monday, 9 April 2007 13:09, J.C. Pizarro wrote: > > This code is bigger than Joe Buck's. > > Joe Buck's code: 10 instructions > Ross Ridge's code: 16 instructions > Ross Smith's code: 16 instructions Well, yes, but it also doesn't have the bug Joe's code had. That was sort of the whole point. If you don't care whether it gives the right answer you might as well just leave the status quo. -- Ross Smith [EMAIL PROTECTED] Auckland, New Zealand "Those who can make you believe absurdities can make you commit atrocities."-- Voltaire
Re: Integer overflow in operator new
#include
void *__allocate_array_of_RossRidge(size_t num, size_t size, size_t max_num) {
if (num > max_num)
size = ~size_t(0);
else
size *= num;
return operator new[](size);
}
void *__allocate_array_of_JCPizarro(size_t num, size_t size, size_t
max_num) {
if (num > max_num) return operator new[](~size_t(0));
return operator new[](size*num);
}
void *__allocate_array_of_JCPizarro2(size_t num, size_t size, size_t max_num) {
size_t result;
if (num > max_num) return operator new[](~size_t(0));
__asm __volatile("mull
%%edx":"=a"(result):"a"(num),"d"(size):/*???*/); // quick & dirty
// See http://www.cs.sjsu.edu/~kirchher/CS047/multDiv.html
// One-operand imul: & Unsigned mul:
return operator new[](result);
}
-
_Z29__allocate_array_of_RossRidgejjj:
[ gcc v3.4.6 : 11 instructions ]
movl4(%esp), %edx
cmpl12(%esp), %edx
movl8(%esp), %eax
jbe .L2
orl $-1, %eax
jmp .L3
.L2:
imull %edx, %eax # signed multiply!!! 1 bit signed + unsigned
31x31!!!
.L3:
pushl %eax
call_Znaj
popl%edx
ret
_Z29__allocate_array_of_RossRidgejjj:
[ gcc 4.1.3 20070326 (prerelease) : 9 instructions ]
movl4(%esp), %eax
orl $-1, %ecx
cmpl12(%esp), %eax
movl8(%esp), %edx
ja .L16
movl%edx, %ecx
imull %eax, %ecx # signed multiply!!! 1 bit signed + unsigned
31x31!!!
.L16:
movl%ecx, 4(%esp)
jmp _Znaj
_Z29__allocate_array_of_JCPizarrojjj:
[ gcc 4.1.3 20070326 (prerelease) and gcc 3.4.6 : 9 instructions ]
movl4(%esp), %edx
cmpl12(%esp), %edx
movl8(%esp), %eax
jbe .L8
movl$-1, 4(%esp)
jmp .L12# <- why not jmp _Znaj directly?
.L8:
imull %edx, %eax # signed multiply!!! 1 bit signed + unsigned
31x31!!!
movl%eax, 4(%esp)
.L12:
jmp _Znaj
_Z30__allocate_array_of_JCPizarro2jjj:
[ gcc 4.1.3 20070326 (prerelease) and gcc 3.4.6 : 9 instructions ]
movl4(%esp), %eax
cmpl12(%esp), %eax
movl8(%esp), %edx
jbe .L2
movl$-1, 4(%esp)
jmp .L6# <- why not jmp _Znaj directly?
.L2:
#APP
mull %edx # unsigned 32x32!!! mul is little bit slower than imul
in clock cycles.
#NO_APP
movl%eax, 4(%esp)
.L6:
jmp _Znaj
-
J.C. Pizarro
allocate_array_april2007_2.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
2007/4/9, Robert Dewar <[EMAIL PROTECTED]>:
J.C. Pizarro wrote:
> The multiply is signed. It is need more researching a little bit.
So what, the low order 32 bits are unaffected. I think this is just
confusion on your part!
Yes, i accidently eliminated the lines containing the point '.' for
removing redundant info.
--
void *__allocate_array(size_t num, size_t size, size_t max_num) {
if (num > max_num) return mynewXX(~size_t(0));
return mynewXX(size*num);
}
_Z16__allocate_arrayjjj:
.LFB6:
movl4(%esp), %edx
cmpl12(%esp), %edx
movl8(%esp), %eax
jbe .L11
movl$-1, 4(%esp)
jmp .L15
.L11:
imull %edx, %eax
movl%eax, 4(%esp)
.L15:
jmp _Z7mynewXXj
--
#include
#include
#include
/* Objective: to detect numbers that are vulnerable to __allocate_array(..).
*
* Mainly about the effects of "imull %edx, %eax".
* With 3 assumptions for good effects to research.
*
* All quick & dirty by J.C. Pizarro
*/
size_t my_num, my_size, my_max_num;
void* mynewXX(size_t size) {
unsigned long long mult;
if (my_num > my_max_num) {
// size is ~size_t(0)
} else {
if (size > 200) return NULL; // 3rd assumption of that used size
<= 200 bytes of memory
mult = (unsigned long long)my_size * (unsigned long long)my_num;
if ((mult >= 0x8000ULL) || (((unsigned int)size) >=
0x8000)
|| (mult > size)) {
printf("oh!: num=%u; size=%u; max_num=0x%08X; num*size=%u (0x%08X);
long=%llu (0x%08X%08X)\n",
my_num,
my_size,
my_max_num,
size,size,
mult,((unsigned int)(mult>>32)),((unsigned int)(mult&~0)));
fflush(stdout);
}
}
return NULL;
}
void *__allocate_array(size_t num, size_t size, size_t max_num) {
if (num > max_num) return mynewXX(~size_t(0));
return mynewXX(size*num);
}
void randattack_allocate_array_start_until_infinity(void) {
srand(time(NULL));
while(1) {
my_num = rand();
my_size = rand();
my_max_num = (rand() << 29) + ((~0)>>(32-29));
my_size &= 0x003F; // 1st assumption of that my_size <= 63
bytes of element
if (my_num <= my_max_num) // 2nd assumption of that my_num is
<= my_max_num
__allocate_array(my_num,my_size,my_max_num);
}
}
int main(int argc,char *argv[]) {
randattack_allocate_array_start_until_infinity();
}
--
# gcc version 4.1.3 20070326 (prerelease)
oh!: num=715827888; size=36; max_num=0x9FFF; num*size=192
(0x00C0); long=25769803968 (0x000600C0)
oh!: num=1762037869; size=39; max_num=0xDFFF; num*size=155
(0x009B); long=68719476891 (0x0010009B)
oh!: num=460175073; size=28; max_num=0x5FFF; num*size=156
(0x009C); long=12884902044 (0x0003009C)
oh!: num=1073741826; size=28; max_num=0xDFFF; num*size=56
(0x0038); long=30064771128 (0x00070038)
...
--
J.C. Pizarro
randattack_allocate_array_april2007.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
2007/4/9, J.C. Pizarro <[EMAIL PROTECTED]> wrote: _Z29__allocate_array_of_RossRidgejjj: [ gcc v3.4.6 : 9 instructions ] movl4(%esp), %edx cmpl12(%esp), %edx # comparing and ?? i lose me movl8(%esp), %eax orl $-1, %eax imull %edx, %eax # signed multiply!!! 1 bit signed + unsigned 31x31!!! pushl %eax call_Znaj popl%edx ret _Z29__allocate_array_of_RossRidgejjj: [ gcc 4.1.3 20070326 (prerelease) : 8 instructions ] movl4(%esp), %eax orl $-1, %ecx cmpl12(%esp), %eax # comparing and ?? i lose me movl8(%esp), %edx movl%edx, %ecx imull %eax, %ecx # signed multiply!!! 1 bit signed + unsigned 31x31!!! movl%ecx, 4(%esp) jmp _Znaj _Z29__allocate_array_of_JCPizarrojjj: [ gcc 4.1.3 20070326 (prerelease) and gcc 3.4.6 : 7 instructions ] movl4(%esp), %edx cmpl12(%esp), %edx # comparing and ?? i lose me movl8(%esp), %eax movl$-1, 4(%esp) imull %edx, %eax # signed multiply!!! 1 bit signed + unsigned 31x31!!! movl%eax, 4(%esp) jmp _Znaj - J.C. Pizarro I don't see a conditional jump or a test of the zero flag. Am i confuse? The multiply is signed. It is need more researching a little bit. allocate_array_april2007.tar.gz Description: GNU Zip compressed data
Re: Integer overflow in operator new
allocate_array_april2007.tar.gz Description: GNU Zip compressed data
Re: Integer overflow in operator new
2007/4/9, Ross Ridge <[EMAIL PROTECTED]> wrote:
Florian Weimer writes:
>Yeah, but that division is fairly expensive if it can't be performed
>at compile time. OTOH, if __compute_size is inlined in all places,
>code size does increase somewhat.
Well, I believe the assumption was that __compute_size would be inlined.
If you want to minimize code size and avoid the division then a library
function something like following might work:
void *__allocate_array(size_t num, size_t size, size_t max_num) {
if (num > max_num)
size = ~size_t(0);
else
size *= num;
return operator new[](size);
}
GCC would caclulate the constant "~size_t(0) / size" and pass it as the
third argument. You'ld be trading a multiply for a couple of constant
outgoing arguments, so the code growth should be small. Unfortunately,
you'd be trading what in most cases is a fast shift and maybe add or
two for slower multiply.
So long as whatever switch is used to enable this check isn't on by
default and its effect on code size and speed is documented, I don't
think it matters that much what those effects are. Anything that works
should make the people concerned about security happy. People more
concerned with size or speed aren't going to enable this feature.
Ross Ridge
Hi Ross Ridge,
I tuned it a little bit.
-
#include
void *__allocate_array_of_RossRidge(size_t num, size_t size, size_t max_num) {
if (num > max_num)
size = ~size_t(0);
else
size *= num;
return operator new[](size);
}
void *__allocate_array_of_JCPizarro(size_t num, size_t size, size_t max_num) {
if (num > max_num) return operator new[](~size_t(0));
return operator new[](size*num);
}
-
_Z29__allocate_array_of_RossRidgejjj:
[ gcc v3.4.6 : 9 instructions ]
movl4(%esp), %edx
cmpl12(%esp), %edx
movl8(%esp), %eax
orl $-1, %eax
imull %edx, %eax
pushl %eax
call_Znaj
popl%edx
ret
_Z29__allocate_array_of_RossRidgejjj:
[ gcc 4.1.3 20070326 (prerelease) : 8 instructions ]
movl4(%esp), %eax
orl $-1, %ecx
cmpl12(%esp), %eax
movl8(%esp), %edx
movl%edx, %ecx
imull %eax, %ecx
movl%ecx, 4(%esp)
jmp _Znaj
_Z29__allocate_array_of_JCPizarrojjj:
[ gcc 4.1.3 20070326 (prerelease) and gcc 3.4.6 : 7 instructions ]
movl4(%esp), %edx
cmpl12(%esp), %edx
movl8(%esp), %eax
movl$-1, 4(%esp)
imull %edx, %eax
movl%eax, 4(%esp)
jmp _Znaj
-
J.C. Pizarro
Re: Integer overflow in operator new
Florian Weimer writes:
>Yeah, but that division is fairly expensive if it can't be performed
>at compile time. OTOH, if __compute_size is inlined in all places,
>code size does increase somewhat.
Well, I believe the assumption was that __compute_size would be inlined.
If you want to minimize code size and avoid the division then a library
function something like following might work:
void *__allocate_array(size_t num, size_t size, size_t max_num) {
if (num > max_num)
size = ~size_t(0);
else
size *= num;
return operator new[](size);
}
GCC would caclulate the constant "~size_t(0) / size" and pass it as the
third argument. You'ld be trading a multiply for a couple of constant
outgoing arguments, so the code growth should be small. Unfortunately,
you'd be trading what in most cases is a fast shift and maybe add or
two for slower multiply.
So long as whatever switch is used to enable this check isn't on by
default and its effect on code size and speed is documented, I don't
think it matters that much what those effects are. Anything that works
should make the people concerned about security happy. People more
concerned with size or speed aren't going to enable this feature.
Ross Ridge
Re: Integer overflow in operator new
> > Florian Weimer writes: > >>I don't think this check is correct. Consider num = 0x3334 and > >>size = 6. It seems that the check is difficult to perform efficiently > >>unless the architecture provides unsigned multiplication with overflow > >>detection, or an instruction to implement __builtin_clz. Right; sorry for the bad code. We need a saturating multiply, and the most efficient implementations can't be expressed in C/C++ directly. I don't think that fixing my code is the right approach. If there's an unsigned multiply instruction that sets an overflow flag, or a 32x32->64 unsigned multiply, then it suffices to say "if overflow, replace product with all-ones." The penalty for doing that should be a lot smaller.
Re: Integer overflow in operator new
One instruction more in GCC-4.1.x vs GCC-3.4.6? Joe Buck's code: 10 instructions [ -Os of gcc-4.1.3-20070326 ] __compute_size: pushl %ebp movl%esp, %ebp movl8(%ebp), %eax movl%eax, %edx imull 12(%ebp), %edx cmpl%eax, %edx orl $-1, %edx popl%ebp movl%edx, %eax # <--- this extra instruction because return EAX = EDX? ret Joe Buck's code: 9 instructions [ -Os of gcc-3.4.6 ] __compute_size: pushl %ebp movl%esp, %ebp movl8(%ebp), %edx movl%edx, %eax imull 12(%ebp), %eax cmpl%edx, %eax orl $-1, %eax popl%ebp # <--- no extra instruction because return EAX = EAX? ret J.C. Pizarro
Re: Integer overflow in operator new
And this tarball. J.C. Pizarro. compute_size_april2007_2.tar.gz Description: GNU Zip compressed data
Re: Integer overflow in operator new
Joe Buck wrote:
> > > inline size_t __compute_size(size_t num, size_t size) {
> > > size_t product = num * size;
> > > return product >= num ? product : ~size_t(0);
> > > }
2007/4/9, Ross Smith <[EMAIL PROTECTED]> wrote:
On Monday, 9 April 2007 10:23, Florian Weimer wrote:
> * Ross Ridge:
> > Florian Weimer writes:
> >>I don't think this check is correct. Consider num = 0x3334 and
> >>size = 6. It seems that the check is difficult to perform
> >> efficiently unless the architecture provides unsigned
> >> multiplication with overflow detection, or an instruction to
> >> implement __builtin_clz.
> >
> > This should work instead:
> >
> > inline size_t __compute_size(size_t num, size_t size) {
> > if (num > ~size_t(0) / size)
> > return ~size_t(0);
> > return num * size;
> > }
>
> Yeah, but that division is fairly expensive if it can't be performed
> at compile time. OTOH, if __compute_size is inlined in all places,
> code size does increase somewhat.
You could avoid the division in nearly all cases by checking for
reasonably-sized arguments first:
inline size_t __compute_size(size_t num, size_t size) {
static const int max_bits = sizeof(size_t) * CHAR_BITS;
int low_num, low_size;
low_num = num < ((size_t)1 << (max_bits * 5 / 8));
low_size = size < ((size_t)1 << (max_bits * 3 / 8));
if (__builtin_expect(low_num && low_size, 1)
|| num <= ~(size_t)0 / size)
return num * size;
else
return ~size_t(0);
}
This code is bigger than Joe Buck's.
I'm sorry, the previous 3rd source code .c is an error mine.
-
Joe Buck's code: 10 instructions
Ross Ridge's code: 16 instructions
Ross Smith's code: 23 instructions
-
Joe Buck's code: 9 instructions
__compute_size:
pushl %ebp
movl%esp, %ebp
movl8(%ebp), %edx
movl%edx, %eax
imull 12(%ebp), %eax
cmpl%edx, %eax
orl $-1, %eax
popl%ebp
ret
Ross Ridge's code: 16 instructions
__compute_size:
pushl %ebp
movl%esp, %ebp
orl $-1, %eax
xorl%edx, %edx
movl12(%ebp), %ecx
divl%ecx
pushl %ebx
movl8(%ebp), %ebx
orl $-1, %edx
cmpl%eax, %ebx
movl%ebx, %edx
imull %ecx, %edx
popl%ebx
movl%edx, %eax
popl%ebp
ret
Ross Smith's code: 23 instructions
__compute_size:
pushl %ebp
movl%esp, %ebp
pushl %ebx
movl8(%ebp), %ebx
cmpl$1048575, %ebx
movl12(%ebp), %ecx
setbe %dl
xorl%eax, %eax
cmpl$4095, %ecx
setbe %al
andb$1, %dl
testl %eax, %eax
orl $-1, %eax
xorl%edx, %edx
divl%ecx
orl $-1, %edx
cmpl%eax, %ebx
movl%ebx, %edx
imull %ecx, %edx
popl%ebx
movl%edx, %eax
popl%ebp
ret
J.C. Pizarro
Re: Integer overflow in operator new
Joe Buck wrote:
> > > inline size_t __compute_size(size_t num, size_t size) {
> > > size_t product = num * size;
> > > return product >= num ? product : ~size_t(0);
> > > }
2007/4/9, Ross Smith <[EMAIL PROTECTED]> wrote:
On Monday, 9 April 2007 10:23, Florian Weimer wrote:
> * Ross Ridge:
> > Florian Weimer writes:
> >>I don't think this check is correct. Consider num = 0x3334 and
> >>size = 6. It seems that the check is difficult to perform
> >> efficiently unless the architecture provides unsigned
> >> multiplication with overflow detection, or an instruction to
> >> implement __builtin_clz.
> >
> > This should work instead:
> >
> > inline size_t __compute_size(size_t num, size_t size) {
> > if (num > ~size_t(0) / size)
> > return ~size_t(0);
> > return num * size;
> > }
>
> Yeah, but that division is fairly expensive if it can't be performed
> at compile time. OTOH, if __compute_size is inlined in all places,
> code size does increase somewhat.
You could avoid the division in nearly all cases by checking for
reasonably-sized arguments first:
inline size_t __compute_size(size_t num, size_t size) {
static const int max_bits = sizeof(size_t) * CHAR_BITS;
int low_num, low_size;
low_num = num < ((size_t)1 << (max_bits * 5 / 8));
low_size = size < ((size_t)1 << (max_bits * 3 / 8));
if (__builtin_expect(low_num && low_size, 1)
|| num <= ~(size_t)0 / size)
return num * size;
else
return ~size_t(0);
}
This code is bigger than Joe Buck's.
-
Joe Buck's code: 10 instructions
Ross Ridge's code: 16 instructions
Ross Smith's code: 16 instructions
-
Joe Buck's code: 10 instructions
__compute_size:
pushl %ebp
movl%esp, %ebp
movl8(%ebp), %eax
movl%eax, %edx
imull 12(%ebp), %edx
cmpl%eax, %edx
orl $-1, %edx
popl%ebp
movl%edx, %eax
ret
Ross Ridge's code: 16 instructions
__compute_size:
pushl %ebp
orl $-1, %eax
movl%esp, %ebp
xorl%edx, %edx
movl12(%ebp), %ecx
pushl %ebx
movl8(%ebp), %ebx
divl%ecx
orl $-1, %edx
cmpl%eax, %ebx
movl%ebx, %edx
imull %ecx, %edx
popl%ebx
movl%edx, %eax
popl%ebp
ret
Ross Smith's code: 16 instructions
__compute_size:
pushl %ebp
orl $-1, %eax
movl%esp, %ebp
xorl%edx, %edx
movl12(%ebp), %ecx
pushl %ebx
movl8(%ebp), %ebx
divl%ecx
orl $-1, %edx
cmpl%eax, %ebx
movl%ebx, %edx
imull %ecx, %edx
popl%ebx
movl%edx, %eax
popl%ebp
ret
compute_size_april2007.tar.gz
Description: GNU Zip compressed data
Re: Integer overflow in operator new
On Monday, 9 April 2007 10:23, Florian Weimer wrote:
> * Ross Ridge:
> > Florian Weimer writes:
> >>I don't think this check is correct. Consider num = 0x3334 and
> >>size = 6. It seems that the check is difficult to perform
> >> efficiently unless the architecture provides unsigned
> >> multiplication with overflow detection, or an instruction to
> >> implement __builtin_clz.
> >
> > This should work instead:
> >
> > inline size_t __compute_size(size_t num, size_t size) {
> > if (num > ~size_t(0) / size)
> > return ~size_t(0);
> > return num * size;
> > }
>
> Yeah, but that division is fairly expensive if it can't be performed
> at compile time. OTOH, if __compute_size is inlined in all places,
> code size does increase somewhat.
You could avoid the division in nearly all cases by checking for
reasonably-sized arguments first:
inline size_t __compute_size(size_t num, size_t size) {
static const int max_bits = sizeof(size_t) * CHAR_BITS;
int low_num, low_size;
low_num = num < ((size_t)1 << (max_bits * 5 / 8));
low_size = size < ((size_t)1 << (max_bits * 3 / 8));
if (__builtin_expect(low_num && low_size, 1)
|| num <= ~(size_t)0 / size)
return num * size;
else
return ~size_t(0);
}
--
Ross Smith [EMAIL PROTECTED] Auckland, New Zealand
"Those who can make you believe absurdities can
make you commit atrocities."-- Voltaire
Re: Integer overflow in operator new
Bradley Lucier wrote: Robert Dewar wrote: I have always been told that -ftrapv is nowhere near fully working or reliable (I think Eric is the source of that advice). Is this just a rumor, or are there data that backs this up. (That - fwrapv doesn't work, not that Dewar was always told that it doesn't work.) Well there are a couple of bugs filed, but the real issue is whether there really exists experience of routinely building large scale applications with this switch, and I am under the impression the answer is no, but of course I could be wrong. For Ada, the desire would be to use this as the default on all targets for all applications, which represents pretty strenuous usage!
Re: Integer overflow in operator new
* Ross Ridge:
> Florian Weimer writes:
>>I don't think this check is correct. Consider num = 0x3334 and
>>size = 6. It seems that the check is difficult to perform efficiently
>>unless the architecture provides unsigned multiplication with overflow
>>detection, or an instruction to implement __builtin_clz.
>
> This should work instead:
>
> inline size_t __compute_size(size_t num, size_t size) {
> if (num > ~size_t(0) / size)
> return ~size_t(0);
> return num * size;
> }
Yeah, but that division is fairly expensive if it can't be performed
at compile time. OTOH, if __compute_size is inlined in all places,
code size does increase somewhat.
Re: Integer overflow in operator new
Andrew Pinski writes: > On 4/8/07, Bradley Lucier <[EMAIL PROTECTED]> wrote: > > Is this just a rumor, or are there data that backs this up. (That - > > fwrapv doesn't work, not that Dewar was always told that it doesn't > > work.) > > If you look into the bugzilla, you will see now two bugs filed against > -ftrapv. One because the rtl back-end removes the libcall and another > because we optimize away the overflow checks in libgcc2.c (PR 19020 > and PR 31477). I don't know why people can't look this up themselves, > it is not like it is private information or anything. You're really good at Bugzilla searches -- I find it really hard to locate anything in Bugzilla, but I've seen you can do so in an instant. So, I know it's possible, but... :-) Andrew. -- Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SL4 1TE, UK Registered in England and Wales No. 3798903
Re: Integer overflow in operator new
On 4/8/07, Bradley Lucier <[EMAIL PROTECTED]> wrote: Is this just a rumor, or are there data that backs this up. (That - fwrapv doesn't work, not that Dewar was always told that it doesn't work.) If you look into the bugzilla, you will see now two bugs filed against -ftrapv. One because the rtl back-end removes the libcall and another because we optimize away the overflow checks in libgcc2.c (PR 19020 and PR 31477). I don't know why people can't look this up themselves, it is not like it is private information or anything. -- Pinski
Re: Integer overflow in operator new
Robert Dewar wrote: I have always been told that -ftrapv is nowhere near fully working or reliable (I think Eric is the source of that advice). Is this just a rumor, or are there data that backs this up. (That - fwrapv doesn't work, not that Dewar was always told that it doesn't work.) Brad
Re: Integer overflow in operator new
Joe Buck writes:
> inline size_t __compute_size(size_t num, size_t size) {
> size_t product = num * size;
> return product >= num ? product : ~size_t(0);
> }
Florian Weimer writes:
>I don't think this check is correct. Consider num = 0x3334 and
>size = 6. It seems that the check is difficult to perform efficiently
>unless the architecture provides unsigned multiplication with overflow
>detection, or an instruction to implement __builtin_clz.
This should work instead:
inline size_t __compute_size(size_t num, size_t size) {
if (num > ~size_t(0) / size)
return ~size_t(0);
return num * size;
}
Ross Ridge
Re: Integer overflow in operator new
Dave Korn wrote: Wouldn't using -ftrapv do what we want? Would a possible answer be to make an ftrapv attribute that could be selectively applied to security-critical library routines such as operator new? I have always been told that -ftrapv is nowhere near fully working or reliable (I think Eric is the source of that advice). Right now we generate somewhat nasty code for required overflow checking in GNAT based on that advice.
Re: Integer overflow in operator new
In article <[EMAIL PROTECTED]> you write: >The assert should not overflow. I suggest > >#include >#include >assert( n < SIZE_MAX / sizeof(int) ); > >which requires two pieces of information that the programmer >otherwise wouldn't need, SIZE_MAX and sizeof(type). > >Asking programmers to write extra code for rare events, has >not been very successful. It would be better if the compiler >incorporated this check into operator new, though throwing >an exception rather than asserting. The compiler should be >able to eliminate many of the conditionals. The compiler and its runtime should be correct, and programmers should be able to depend on it. When you read the documentation for new or calloc, there is no mention of integer overflow, it is not expected that the programmer has to know about that. Adding an extra test in user code even less sense than checking that pointers are not null before calling free...
Re: Integer overflow in operator new
In article <[EMAIL PROTECTED]> you write: >On Fri, Apr 06, 2007 at 06:51:24PM -0500, Gabriel Dos Reis wrote: >> David Daney <[EMAIL PROTECTED]> writes: >> >> | One could argue that issuing some type of diagnostic (either at >> | compile time or run time) would be helpful for people that don't >> | remember to write correct code 100% of the time. >> >> I raised this very issue a long time ago; a long-term GCC contributor >> vocally opposed checking the possible overflow. I hope something will >> happen this time. > >I don't like slowing programs down, but I like security holes even less. > >If a check were to be implemented, the right thing to do would be to throw >bad_alloc (for the default new) or return 0 (for the nothrow new). If a >process's virtual memory limit is 400M, we throw bad_alloc if we do new >int[200], so we might as well do it if we do new int[20]. >There would be no reason to use a different reporting mechanism. > >There might be rare cases where the penalty for this check could have >an impact, like for pool allocators that are otherwise very cheap. >If so, there could be a flag to suppress the check. > Considering the issue is only for new [], I'd assume anyone who wants less correct, but faster behavior would simply handle the computation themselves, and deal with the overflow manually, then override whatever operator/class they need to make things work.
RE: Integer overflow in operator new
On 08 April 2007 13:58, Andreas Schwab wrote: > "Dave Korn" <[EMAIL PROTECTED]> writes: > >> Wouldn't using -ftrapv do what we want? > > -ftrapv only modifies signed arithmetic. Unsigned arithmetic never traps. > > Andreas. Meh, I'm an idiot. Still, maybe we want to create a -futrapv flag/attribute? cheers, DaveK -- Can't think of a witty .sigline today
Re: Integer overflow in operator new
"Dave Korn" <[EMAIL PROTECTED]> writes: > Wouldn't using -ftrapv do what we want? -ftrapv only modifies signed arithmetic. Unsigned arithmetic never traps. Andreas. -- Andreas Schwab, SuSE Labs, [EMAIL PROTECTED] SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany PGP key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5 "And now for something completely different."
RE: Integer overflow in operator new
On 08 April 2007 10:43, Florian Weimer wrote:
> * Joe Buck:
>
>> Consider an implementation that, when given
>>
>> Foo* array_of_foo = new Foo[n_elements];
>>
>> passes __compute_size(elements, sizeof Foo) instead of n_elements*sizeof
>> Foo to operator new, where __compute_size is
>>
>> inline size_t __compute_size(size_t num, size_t size) {
>> size_t product = num * size;
>> return product >= num ? product : ~size_t(0);
>> }
>
> I don't think this check is correct. Consider num = 0x3334 and
> size = 6. It seems that the check is difficult to perform efficiently
> unless the architecture provides unsigned multiplication with overflow
> detection, or an instruction to implement __builtin_clz.
Wouldn't using -ftrapv do what we want? Would a possible answer be to make
an ftrapv attribute that could be selectively applied to security-critical
library routines such as operator new?
cheers,
DaveK
--
Can't think of a witty .sigline today
Re: Integer overflow in operator new
* Joe Buck:
> Consider an implementation that, when given
>
>Foo* array_of_foo = new Foo[n_elements];
>
> passes __compute_size(elements, sizeof Foo) instead of n_elements*sizeof Foo
> to operator new, where __compute_size is
>
> inline size_t __compute_size(size_t num, size_t size) {
> size_t product = num * size;
> return product >= num ? product : ~size_t(0);
> }
I don't think this check is correct. Consider num = 0x3334 and
size = 6. It seems that the check is difficult to perform efficiently
unless the architecture provides unsigned multiplication with overflow
detection, or an instruction to implement __builtin_clz.
Re: Integer overflow in operator new
Joe Buck writes:
>Consider an implementation that, when given
>
>Foo* array_of_foo = new Foo[n_elements];
>
>passes __compute_size(elements, sizeof Foo) instead of n_elements*sizeof Foo
>to operator new, where __compute_size is
>
>inline size_t __compute_size(size_t num, size_t size) {
>size_t product = num * size;
>return product >= num ? product : ~size_t(0);
>}
Yes, doing something like this instead would largely answer my concerns.
>This counts on the fact that any operator new implementation has to fail
>when asked to supply every single addressible byte, less one.
I don't know if you can assume "~size_t(0)" is equal to the number of
addressable bytes, less one. A counter example would be 16-bit 80x86
compilers where size_t is 16-bits and an allocation of 65535 bytes can
succeed, but I don't know if GCC supports any targets where something
similar can happen.
>I haven't memorized the standard, but I don't believe that this
>implementation would violate it. The behavior differs only when more
>memory is requested than can be delivered.
It differs because the actual amount of memory requested is the result
of the unsigned multiplication of "n_elements * sizeof Foo", using your
example above. Since this result of this caclulation isn't undefined,
even if it "overflows", there's no room for the compiler to calculate
a different value to pass to operator new().
Ross Ridge
Re: Integer overflow in operator new
[EMAIL PROTECTED] (Ross Ridge) writes: [...] | Gabriel Dos Reis writes: | >I believe you're confused about the semantics. | >The issue here is that the *size of object* requested can be | >represented. That is independent of whether the machine has enough | >memory or not. So, new_handler is a red herring | | The issue is what GCC should do when the calculation of the size of | memory to allocate with operator new() results in unsigned wrapping. | Currently, GCC's behavior is standard conforming but probably isn't the | expected result. I don't understand this. -- Gaby
Re: Integer overflow in operator new
Joe Buck <[EMAIL PROTECTED]> writes: | This is why I suggested that, should we implement a better check, | there should be an option to turn it off, so programmers who cannot | afford an extra byte are taken care of. I agree. -- Gaby
Re: Integer overflow in operator new
On Sat, Apr 07, 2007 at 07:41:59AM -0400, Robert Dewar wrote: > J.C. Pizarro wrote: > > >A solution is using the -shared option to generate ".so" library. > > That does not solve things in environments like embedded > environments where there are no shared libraries. > > > >Another future solution is pack the big ".so" library with UPX > >(Ultimate Packer for eXecutables) or extend the ELF format to > >permit pack the sections with GZ, BZ2 or LZMA. > > We are worried about code space in memory, not space on disk! This is why I suggested that, should we implement a better check, there should be an option to turn it off, so programmers who cannot afford an extra byte are taken care of. However, the extra code might amount to 2-4 instructions per call to array-new (for objects of size > 1), and this is not that common an operation in any case.
Re: Integer overflow in operator new
On Sat, Apr 07, 2007 at 04:01:57PM -0500, Gabriel Dos Reis wrote: > [EMAIL PROTECTED] (Ross Ridge) writes: > > | Joe Buck writes: > | >If a check were to be implemented, the right thing to do would be to throw > | >bad_alloc (for the default new) or return 0 (for the nothrow new). > | > | Ross Ridge writes: > | >What do you do if the user has defined his own operator new that does > | >something else? > | > | Gabriel Dos Reis writes: > | >More precisely? > | > | Well, for example, like all other things that a new_handler can do, > | like throwing an exception derived from bad_alloc or calling exit(). > | In addition, any number of side effects are possible, like printing > | error messages or setting flags. > > I believe you're confused about the semantics. > The issue here is that the *size of object* requested can be > represented. That is independent of whether the machine has enough > memory or not. So, new_handler is a red herring. The user's new function will be passed a size that has been converted into bytes. If gcc's implementation does multiply-with-saturation instead of straight multiply to get this size, user-defined new operators will work as expected.
Re: Integer overflow in operator new
Gabriel Dos Reis writes:
> >I believe you're confused about the semantics.
> >The issue here is that the *size of object* requested can be
> >represented. That is independent of whether the machine has enough
> >memory or not. So, new_handler is a red herring
On Sat, Apr 07, 2007 at 06:05:35PM -0400, Ross Ridge wrote:
> The issue is what GCC should do when the calculation of the size of
> memory to allocate with operator new() results in unsigned wrapping.
> Currently, GCC's behavior is standard conforming but probably isn't the
> expected result. If GCC does something other than what operator new()
> does when there isn't enough memory available then it will be doing
> something that is both non-conforming and probably not what was expected.
Consider an implementation that, when given
Foo* array_of_foo = new Foo[n_elements];
passes __compute_size(elements, sizeof Foo) instead of n_elements*sizeof Foo
to operator new, where __compute_size is
inline size_t __compute_size(size_t num, size_t size) {
size_t product = num * size;
return product >= num ? product : ~size_t(0);
}
This counts on the fact that any operator new implementation has to fail
when asked to supply every single addressible byte, less one. It would
appear that the extra cost, for the non-overflow case, is two
instructions (on most architectures): the compare and the branch, which
can be arranged so that the prediction is not-taken.
I haven't memorized the standard, but I don't believe that this
implementation would violate it. The behavior differs only when more
memory is requested than can be delivered.
Re: Integer overflow in operator new
[EMAIL PROTECTED] (Ross Ridge) writes: > Well, for example, like all other things that a new_handler can do, > like throwing an exception derived from bad_alloc or calling exit(). > In addition, any number of side effects are possible, like printing > error messages or setting flags. Gabriel Dos Reis writes: >I believe you're confused about the semantics. >The issue here is that the *size of object* requested can be >represented. That is independent of whether the machine has enough >memory or not. So, new_handler is a red herring The issue is what GCC should do when the calculation of the size of memory to allocate with operator new() results in unsigned wrapping. Currently, GCC's behavior is standard conforming but probably isn't the expected result. If GCC does something other than what operator new() does when there isn't enough memory available then it will be doing something that is both non-conforming and probably not what was expected. Ross Ridge
Re: Integer overflow in operator new
[EMAIL PROTECTED] (Ross Ridge) writes: | Joe Buck writes: | >If a check were to be implemented, the right thing to do would be to throw | >bad_alloc (for the default new) or return 0 (for the nothrow new). | | Ross Ridge writes: | >What do you do if the user has defined his own operator new that does | >something else? | | Gabriel Dos Reis writes: | >More precisely? | | Well, for example, like all other things that a new_handler can do, | like throwing an exception derived from bad_alloc or calling exit(). | In addition, any number of side effects are possible, like printing | error messages or setting flags. I believe you're confused about the semantics. The issue here is that the *size of object* requested can be represented. That is independent of whether the machine has enough memory or not. So, new_handler is a red herring. -- Gaby
Re: Integer overflow in operator new
Joe Buck writes: >If a check were to be implemented, the right thing to do would be to throw >bad_alloc (for the default new) or return 0 (for the nothrow new). Ross Ridge writes: >What do you do if the user has defined his own operator new that does >something else? Gabriel Dos Reis writes: >More precisely? Well, for example, like all other things that a new_handler can do, like throwing an exception derived from bad_alloc or calling exit(). In addition, any number of side effects are possible, like printing error messages or setting flags. >Those programs willing to do anything to avoid imagined or perceived >"excessive code size growth" may use the suggested switch. The code size growth would be real, and there are enough applications out there that would consider any unnecessary growth in code excessive. The switch would be required both for that reason, and for Standard conformance. Ross Ridge
Re: Integer overflow in operator new
On Sat, Apr 07, 2007 at 12:15:10PM +0200, Florian Weimer wrote: > * Karl Chen: > > > "4 * n", unchecked, is vulnerable to integer overflow. On IA-32, > > "new int[0x4001]" becomes equivalent to "new int[1]". I've > > verified this on gcc-2.95 through 4.1. For larger objects the > > effects are exaggerated; smaller counts are needed to overflow. > > This PR19351, by the way. Also by the way, it's triggered in the libstdc++ testsuite in at least one place :-) I can't remember which test any more, but last month I discovered that there is a use of operator new[] with a subscript of INT_MAX - 1 (INT_MAX is handled specially). In general this still works out to be more memory than can be allocated and the test tests what it wanted to (bad_alloc). -- Daniel Jacobowitz CodeSourcery
Re: Integer overflow in operator new
[EMAIL PROTECTED] (Ross Ridge) writes: | Joe Buck writes: | >If a check were to be implemented, the right thing to do would be to throw | >bad_alloc (for the default new) or return 0 (for the nothrow new). | | What do you do if the user has defined his own operator new that does | something else? More precisely? | >There cases where the penalty for this check could have | >an impact, like for pool allocators that are otherwise very cheap. | >If so, there could be a flag to suppress the check. | | Excessive code size growth could also be problem for some programs. Those programs willing to do anything to avoid imagined or perceived "excessive code size growth" may use the suggested switch. -- Gaby
Re: Integer overflow in operator new
2007/4/7, Robert Dewar <[EMAIL PROTECTED]>: > > A solution is using the -shared option to generate ".so" library. > > That does not solve things in environments like embedded > environments where there are no shared libraries. Use -Os and "strip --strip-all". And remove code if you don't like it. > > Another future solution is pack the big ".so" library with UPX > > (Ultimate Packer for eXecutables) or extend the ELF format to > > permit pack the sections with GZ, BZ2 or LZMA. > > We are worried about code space in memory, not space on disk! Or extend the ELF format to permit pack non-solidly the many subsections with GZ, BZ2, UPX or LZMA (<=1MiB to uncompress e.g.). Theirs buffers are very small to permit to raise an exception. Like squashfs for embedded systems instead cramfs. This same idea is applicable to pack the gigant /usr/lib/libgcj.so that its current non-packed size on disk is >=9 MiB, sometimes >=50 MiB. Remember, Java is generated to C++ with gcj and compiled with g++.
Re: Integer overflow in operator new
2007/4/7, Robert Dewar <[EMAIL PROTECTED]>: > A solution is using the -shared option to generate ".so" library. That does not solve things in environments like embedded environments where there are no shared libraries. Use -Os and "strip --strip-all". And remove code if you don't like it. > Another future solution is pack the big ".so" library with UPX > (Ultimate Packer for eXecutables) or extend the ELF format to > permit pack the sections with GZ, BZ2 or LZMA. We are worried about code space in memory, not space on disk! Or extend the ELF format to permit pack non-solidly or solidly (=> slower stream) the many subsections with GZ, BZ2, UPX or LZMA (<=1MiB to uncompress e.g.). Theirs buffers are very small to permit to raise an exception. Like squashfs for embedded systems instead cramfs.
Re: Integer overflow in operator new
J.C. Pizarro wrote: A solution is using the -shared option to generate ".so" library. That does not solve things in environments like embedded environments where there are no shared libraries. Another future solution is pack the big ".so" library with UPX (Ultimate Packer for eXecutables) or extend the ELF format to permit pack the sections with GZ, BZ2 or LZMA. We are worried about code space in memory, not space on disk!
Re: Integer overflow in operator new
2007/4/7, Ross Ridge <[EMAIL PROTECTED]>: Joe Buck writes: >If a check were to be implemented, the right thing to do would be to throw >bad_alloc (for the default new) or return 0 (for the nothrow new). What do you do if the user has defined his own operator new that does something else? The callees checkers should to be with optional stubs, by example, the user wants to catch the error, log and send an e-mail to him and to data center. >There cases where the penalty for this check could have >an impact, like for pool allocators that are otherwise very cheap. >If so, there could be a flag to suppress the check. Excessive code size growth could also be problem for some programs. A solution is using the -shared option to generate ".so" library. Another future solution is pack the big ".so" library with UPX (Ultimate Packer for eXecutables) or extend the ELF format to permit pack the sections with GZ, BZ2 or LZMA. Ross Ridge J.C. Pizarro.
Re: Integer overflow in operator new
Florian Weimer wrote: This PR19351, by the way. The most widespread interpretation of the standard is that conforming implementations aren't allowed to raise an exception in this case: the arithmetic is defined to occur in terms of an unsigned type. Well for sure the standard does not allow you to generate junk code silently, so given the two choices of bad code or an exception I think the interpretation of the standard is not the relevent criterion. Anyway, you can always raise an exception if you run out of storage, and the standard has nothing formal to say on that topic. The official response from the C++ folks is here: http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_closed.html#256 | Each implementation is required to document the maximum size of an | object (Annex B limits). It is not difficult for a program to check | array allocations to ensure that they are smaller than this | quantity. Implementations can provide a mechanism in which users | concerned with this problem can request extra checking before array | allocations, just as some implementations provide checking for array | index and pointer validity. However, it would not be appropriate to | require this overhead for every array allocation in every program. You are quoting rationale. Surely that has no normative force. A standard cannot meaningfully talk about what is or what is not appropriate code generation anyway.
Re: Integer overflow in operator new
* Karl Chen: > "4 * n", unchecked, is vulnerable to integer overflow. On IA-32, > "new int[0x4001]" becomes equivalent to "new int[1]". I've > verified this on gcc-2.95 through 4.1. For larger objects the > effects are exaggerated; smaller counts are needed to overflow. This PR19351, by the way. The most widespread interpretation of the standard is that conforming implementations aren't allowed to raise an exception in this case: the arithmetic is defined to occur in terms of an unsigned type. See the 2005 discussion on comp.std.c++ on this topic. > This is similar to the calloc integer overflow vulnerability in > glibc, which was fixed back in 2002. Interestingly, RUS-CERT > 2002-08:02 did mention 'operator new', and so did Bugtraq 5398. > http://cert.uni-stuttgart.de/advisories/calloc.php > http://www.securityfocus.com/bid/5398/discuss Yeah, I've essentially given up on this one. The official response from the C++ folks is here: http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_closed.html#256 | Each implementation is required to document the maximum size of an | object (Annex B limits). It is not difficult for a program to check | array allocations to ensure that they are smaller than this | quantity. Implementations can provide a mechanism in which users | concerned with this problem can request extra checking before array | allocations, just as some implementations provide checking for array | index and pointer validity. However, it would not be appropriate to | require this overhead for every array allocation in every program.
Re: Integer overflow in operator new
Joe Buck writes: >If a check were to be implemented, the right thing to do would be to throw >bad_alloc (for the default new) or return 0 (for the nothrow new). What do you do if the user has defined his own operator new that does something else? >There cases where the penalty for this check could have >an impact, like for pool allocators that are otherwise very cheap. >If so, there could be a flag to suppress the check. Excessive code size growth could also be problem for some programs. Ross Ridge
Re: Integer overflow in operator new
On Fri, Apr 06, 2007 at 06:51:24PM -0500, Gabriel Dos Reis wrote: > David Daney <[EMAIL PROTECTED]> writes: > > | One could argue that issuing some type of diagnostic (either at > | compile time or run time) would be helpful for people that don't > | remember to write correct code 100% of the time. > > I raised this very issue a long time ago; a long-term GCC contributor > vocally opposed checking the possible overflow. I hope something will > happen this time. I don't like slowing programs down, but I like security holes even less. If a check were to be implemented, the right thing to do would be to throw bad_alloc (for the default new) or return 0 (for the nothrow new). If a process's virtual memory limit is 400M, we throw bad_alloc if we do new int[200], so we might as well do it if we do new int[20]. There would be no reason to use a different reporting mechanism. There might be rare cases where the penalty for this check could have an impact, like for pool allocators that are otherwise very cheap. If so, there could be a flag to suppress the check.
Re: Integer overflow in operator new
> On 2007-04-06 16:12 PDT, Lawrence Crowl writes: Lawrence> Asking programmers to write extra code for rare Lawrence> events, has not been very successful. Well put Lawrence, I agree; I didn't expect strong opposition. I doubt we'd find much code in the wild that checks for integer overflow before every 'new'. I'd like to reiterate that the equivalent calloc issue was treated as a serious vulnerability and fixed right away. >From the programmer's point of view, the multiplication isn't obvious. For all they know, it's a 'for' loop that iterates per element, allocating (sizeof object) bytes in each iteration. So it's not obvious why a check would even be necessary to a typical user. I would also note that all non-char uses of operator new that I looked at in gcc's C++ headers are lacking integer overflow checks. Lawrence> It would be better if the compiler incorporated this Lawrence> check into operator new, though throwing an Lawrence> exception rather than asserting. The compiler Lawrence> should be able to eliminate many of the Lawrence> conditionals. Indeed, recent research has found that even checking for overflow on *every arithmetic operation* is only a 5% run-time overhead. A default check on only 'operator new' invocations is quite cheap - a single jump-if-overflow instruction that fares well with branch prediction. Handling the overflow case can be moved faraway so it doesn't affect instruction cache performance. Fixing it in user code at call sites is cumbersome - there's no way to wrap a macro around 'operator new', no way to do it in custom 'operator new' since the implicit multiplication has already occurred by then. It would have to be an explicitly typed check at every use of 'operator new'. -- Karl 2007-04-06 18:15
Re: Integer overflow in operator new
"J.C. Pizarro" <[EMAIL PROTECTED]> writes: [...] | But if someone implements one fastest bucket-based quickallocator then | the performance penalty with this check is considerable. I would like to see the actual performance penalty numbers for such thingy deployed in the real world. -- Gaby
Re: Integer overflow in operator new
06 Apr 2007 18:53:47 -0500, Gabriel Dos Reis <[EMAIL PROTECTED]>: "J.C. Pizarro" <[EMAIL PROTECTED]> writes: [...] | > The compiler should be able to eliminate many of the conditionals. | Yes but no, there are cases that the compiler can't eliminate the | conditionals that depend on run-time, e.g., "n" is non-constant parameter. What is the performance penalty compared to the actual allocation work on "typical" modern systems? -- Gaby It depends in the people's tastes. If the allocator is slow then there is no performance penalty. But if someone implements one fastest bucket-based quickallocator then the performance penalty with this check is considerable. I remember the Amdahl Law. J.C. Pizarro
Re: Integer overflow in operator new
"J.C. Pizarro" <[EMAIL PROTECTED]> writes:
| > Good points.
| >
| > Regarding negatives, I believe 'operator new' takes a size_t,
| > which is unsigned, but if it were signed it, the multiplication
| > would indeed be in danger of creating a negative.
| >
| > If possible, I would prefer a solution that's built-in to operator
| > new. I was thinking it should be implemented when code is
| > generated, for example using jc/jo/seto on i386.
| >
| > --
| > Karl 2007-04-06 15:41
|
| I've a good proposition for catching intruders in the code using
| an option -DCATCH_NEW_INTRUDER by example:
|
| int * allocate_int(size_t n)
| {
| int *p;
| #ifdef CATCH_NEW_INTRUDER
| log_and_raise_if_new_intruder_anomaly(n,4);
| #endif //CATCH_NEW_INTRUDER
| p = (int*) operator new[](4 * n);
| #ifdef CATCH_NEW_INTRUDER
| log_and_raise_if_new_intruder_anomaly_return_not_null(n,4,p);
| #endif //CATCH_NEW_INTRUDER
| return p;
| }
Yuck!
-- Gaby
Re: Integer overflow in operator new
"J.C. Pizarro" <[EMAIL PROTECTED]> writes: [...] | > The compiler should be able to eliminate many of the conditionals. | Yes but no, there are cases that the compiler can't eliminate the | conditionals that depend on run-time, e.g., "n" is non-constant parameter. What is the performance penalty compared to the actual allocation work on "typical" modern systems? -- Gaby
Re: Integer overflow in operator new
David Daney <[EMAIL PROTECTED]> writes: | One could argue that issuing some type of diagnostic (either at | compile time or run time) would be helpful for people that don't | remember to write correct code 100% of the time. I raised this very issue a long time ago; a long-term GCC contributor vocally opposed checking the possible overflow. I hope something will happen this time. -- Gaby
Re: Integer overflow in operator new
The assert should not overflow. I suggest #include #include assert( n < SIZE_MAX / sizeof(int) ); which requires two pieces of information that the programmer otherwise wouldn't need, SIZE_MAX and sizeof(type). Asking programmers to write extra code for rare events, has not been very successful. It would be better if the compiler incorporated this check into operator new, though throwing an exception rather than asserting. The compiler should be able to eliminate many of the conditionals. -- Lawrence Crowl The operator new is reused many times as many callers. So, the programmers don't have many times to write extra code for calling into operator new. The compiler should be able to eliminate many of the conditionals. Yes but no, there are cases that the compiler can't eliminate the conditionals that depend on run-time, e.g., "n" is non-constant parameter. J.C. Pizarro
Re: Integer overflow in operator new
On 4/6/07, Andrew Pinski <[EMAIL PROTECTED]> wrote: On 4/6/07, Karl Chen <[EMAIL PROTECTED]> wrote: > Regarding negatives, I believe 'operator new' takes a size_t, > which is unsigned, but if it were signed it, the multiplication > would indeed be in danger of creating a negative. Actually if it was signed, the whole result would be undefined if there was an overflow. Oh by the way unsigned integers don't overflow, they wrap. I think the best solution is allow the programer do the correct thing and have operator new assume what it gets as being right. The assert should not overflow. I suggest #include #include assert( n < SIZE_MAX / sizeof(int) ); which requires two pieces of information that the programmer otherwise wouldn't need, SIZE_MAX and sizeof(type). Asking programmers to write extra code for rare events, has not been very successful. It would be better if the compiler incorporated this check into operator new, though throwing an exception rather than asserting. The compiler should be able to eliminate many of the conditionals. -- Lawrence Crowl
Re: Integer overflow in operator new
Good points.
Regarding negatives, I believe 'operator new' takes a size_t,
which is unsigned, but if it were signed it, the multiplication
would indeed be in danger of creating a negative.
If possible, I would prefer a solution that's built-in to operator
new. I was thinking it should be implemented when code is
generated, for example using jc/jo/seto on i386.
--
Karl 2007-04-06 15:41
I've a good proposition for catching intruders in the code using
an option -DCATCH_NEW_INTRUDER by example:
int * allocate_int(size_t n)
{
int *p;
#ifdef CATCH_NEW_INTRUDER
log_and_raise_if_new_intruder_anomaly(n,4);
#endif //CATCH_NEW_INTRUDER
p = (int*) operator new[](4 * n);
#ifdef CATCH_NEW_INTRUDER
log_and_raise_if_new_intruder_anomaly_return_not_null(n,4,p);
#endif //CATCH_NEW_INTRUDER
return p;
}
J.C. Pizarro
Re: Integer overflow in operator new
Andrew Pinski wrote: On 4/6/07, Karl Chen <[EMAIL PROTECTED]> wrote: Regarding negatives, I believe 'operator new' takes a size_t, which is unsigned, but if it were signed it, the multiplication would indeed be in danger of creating a negative. Actually if it was signed, the whole result would be undefined if there was an overflow. Oh by the way unsigned integers don't overflow, they wrap. I think the best solution is allow the programer do the correct thing and have operator new assume what it gets as being right. Is that an argument for doing nothing? I couldn't tell. One could argue that issuing some type of diagnostic (either at compile time or run time) would be helpful for people that don't remember to write correct code 100% of the time. David Daney
Re: Integer overflow in operator new
On 4/6/07, Karl Chen <[EMAIL PROTECTED]> wrote: Regarding negatives, I believe 'operator new' takes a size_t, which is unsigned, but if it were signed it, the multiplication would indeed be in danger of creating a negative. Actually if it was signed, the whole result would be undefined if there was an overflow. Oh by the way unsigned integers don't overflow, they wrap. I think the best solution is allow the programer do the correct thing and have operator new assume what it gets as being right. -- Pinski
Re: Integer overflow in operator new
> On 2007-04-06 15:35 PDT, J C Pizarro writes:
J> A possible workaround could be it but it's vulnerable if
J> it's defined with -DNDEBUG :
J> int * allocate_int(size_t n) {
J> // it's another integer overflow, a positive can
J> // become to a negative.
J> //n=1073741823 (0x3FFF) => n*4=-4
J> //(0xFFFC) return (int*) operator
J> //new[](-4); !!! it's easy for
J> buffer overflow.
J> assert(0 <= (4 * n));
J> // it's an assert against your integer overflow.
J> assert((4ULL * n) <= ULONG_MAX); return (int*)
J> operator new[](4 * n);
J> }
Good points.
Regarding negatives, I believe 'operator new' takes a size_t,
which is unsigned, but if it were signed it, the multiplication
would indeed be in danger of creating a negative.
If possible, I would prefer a solution that's built-in to operator
new. I was thinking it should be implemented when code is
generated, for example using jc/jo/seto on i386.
--
Karl 2007-04-06 15:41
Re: Integer overflow in operator new
2007/4/6, Karl Chen <[EMAIL PROTECTED]>:
Hi all, apologies if this has been discussed before, but I
couldn't find anything about this issue in gcc mailing list
archives.
Use of operator new (et al) appears to have an integer overflow;
this function:
int * allocate_int(size_t n)
{
return new int[n];
}
with gcc-4.1 on IA-32 compiles to:
_Z12allocate_intj:
pushl %ebp
movl%esp, %ebp
subl$8, %esp
movl8(%ebp), %eax
sall$2, %eax
movl%eax, (%esp)
call_Znaj
leave
ret
which is equivalent to the compilation of:
int * allocate_int(size_t n)
{
return (int*) operator new[](4 * n);
}
"4 * n", unchecked, is vulnerable to integer overflow. On IA-32,
"new int[0x4001]" becomes equivalent to "new int[1]". I've
verified this on gcc-2.95 through 4.1. For larger objects the
effects are exaggerated; smaller counts are needed to overflow.
This is similar to the calloc integer overflow vulnerability in
glibc, which was fixed back in 2002. Interestingly, RUS-CERT
2002-08:02 did mention 'operator new', and so did Bugtraq 5398.
http://cert.uni-stuttgart.de/advisories/calloc.php
http://www.securityfocus.com/bid/5398/discuss
See also this 2004 article by Raymond Chen:
http://blogs.msdn.com/oldnewthing/archive/2004/01/29/64389.aspx
Possible fixes might be to abort or to pass ULONG_MAX (0x)
to 'operator new' and let it return NULL or throw bad_alloc.
At least one other compiler already specifically guards against
integer overflow in 'operator new'.
--
Karl 2007-04-06 07:30
You've reason! There was not anything about this issue in gcc mailing
list archives.
But, i've more discussion about it!.
A possible workaround could be it but it's vulnerable if it's defined
with -DNDEBUG :
int * allocate_int(size_t n)
{
// it's another integer overflow, a positive can become to a negative.
//n=1073741823 (0x3FFF) => n*4=-4 (0xFFFC)
//return (int*) operator new[](-4); !!! it's easy for
buffer overflow.
assert(0 <= (4 * n));
// it's an assert against your integer overflow.
assert((4ULL * n) <= ULONG_MAX);
return (int*) operator new[](4 * n);
}
