www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The case for integer overflow checks?

reply Guillaume Piolat <contact spam.com> writes:
As a die-hard native programmer I was always disgusted by integer 
overflow checks and array bounds checks. Littering code with 
branches everywhere? Just let me go as fast possible please!

Last week I was explained by security people how a part of 
vulnerabilities todays are attacks on image parsers, and how 
integer overflow checks may help there.

IIRC a typical attack on image format parser is to forge an image 
with a width and height that will overflow an int.

On allocation, the result of the multiplied wraps around like 
this:

     int width = parse_width_from_stream();     // eg: 131072
     int height = parse_height_from_stream();   // eg: 131073
     ubyte[] data = malloc(width * height * 4); // wraps around, 
allocates way less memory than that

This prepare the program to access data that is outside the truly 
allocated area, for example in another block.
The other part of the job is to actually jump in the injected 
code, but I've not understood this part (somehow implied knowing 
how the specific allocator work in this case). Somehow integer 
overflows are part of sophisticated attacks for which it's a 
building block.

If overflow checks happen to be more or less cheap like 
(surprinsingly) array bounds checks are, it could be a nice thing 
to pay for.

References:
- Integer Overflow into Information Disclosure 
http://nullprogram.com/blog/2017/07/19/
- Basic Integer Overflows http://phrack.org/issues/60/10.html
Sep 15 2017
next sibling parent reply Kagamin <spam here.lot> writes:
On Friday, 15 September 2017 at 08:46:57 UTC, Guillaume Piolat 
wrote:

     int width = parse_width_from_stream();     // eg: 131072
     int height = parse_height_from_stream();   // eg: 131073


Do you hope to see such code? Since width can't be negative, C 
programmer would use unsigned integer for it, and you can't 
prohibit overflow for unsigned integer. It is unfixable for array 
length, because unsigned integers are invariably used for length. 
Blueborn vulnerabilities rely on overflow of unsigned integers 
(for buffer length) to trigger buffer overflow in calls to 
memcopy. But buffer overflow would normally be prevented by bound 
checks in case of integer overflow. Just have a safer wrapper 
around malloc in your example.
Sep 15 2017
next sibling parent reply Guillaume Piolat <contact spam.com> writes:
On Friday, 15 September 2017 at 12:04:27 UTC, Kagamin wrote:

 Do you hope to see such code? Since width can't be negative, C 
 programmer would use unsigned integer for it, and you can't 
 prohibit overflow for unsigned integer. It is unfixable for 
 array length, because unsigned integers are invariably used for 
 length. Blueborn vulnerabilities rely on overflow of unsigned 
 integers (for buffer length) to trigger buffer overflow in 
 calls to memcopy.


This code isn't to be taken literally, the important bit is that 
silent integer overflow allows this kind of attacks.



 But buffer overflow would normally be prevented by bound checks 
 in case of integer overflow.


Well here I don't think so: this attack is used to adress a very 
large space, while having a very small actually allocated memory 
space. Bounds would be too large to matter.


 have a safer wrapper around malloc in your example.


That would be calloc.
The point is that it's easy to make the vulnerability disappear, 
once you know about such things and traps. It falls under the 
"unknown unknowns" category of risk most of the time though.
Sep 15 2017
parent reply Kagamin <spam here.lot> writes:
On Friday, 15 September 2017 at 12:25:10 UTC, Guillaume Piolat 
wrote:

 Well here I don't think so: this attack is used to adress a 
 very large space, while having a very small actually allocated 
 memory space. Bounds would be too large to matter.


As long as it works in bounds it should be more or less ok.


 That would be calloc.


I mean allocator that returns bound checked array. And you can 
call calloc incorrectly too.


 The point is that it's easy to make the vulnerability 
 disappear, once you know about such things and traps.


It's not because nobody knows about buffer overflows. C leaves 
the task on the programmer, and the task is too huge for manual 
labor without help from the language, ecosystem and coding 
practices, of course nobody does it.
Sep 15 2017
next sibling parent Guillaume Piolat <first.last gmail.com> writes:
Point taken about proper allocator with returned size. It's 
indeed a minority of cases in regular D.

On Friday, 15 September 2017 at 16:39:46 UTC, Kagamin wrote:

 It's not because nobody knows about buffer overflows. C leaves 
 the task on the programmer, and the task is too huge for manual 
 labor without help from the language, ecosystem and coding 
 practices, of course nobody does it.


I was wondering because some image libraries do use malloc(), for 
the decreased memory usage and possibility of false positives.
Sep 15 2017
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/15/2017 9:39 AM, Kagamin wrote:

 It's not because nobody knows about buffer overflows. C leaves the task on the 
 programmer, and the task is too huge for manual labor without help from the 
 language, ecosystem and coding practices, of course nobody does it.


The problem with C is that it isn't mechanically checkable. There's no way to 
reliably tell if a piece of code is memory safe or not, regardless of how 
competent the programmer is or how hard he works.

The programming community is coming around, very slowly, to what the airframe 
industry learned generations ago. I.e. you *never* rely on people in the system 
not making mistakes.
Sep 16 2017
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/16/2017 2:55 AM, Walter Bright wrote:

 The programming community is coming around, very slowly, to what the airframe 
 industry learned generations ago. I.e. you *never* rely on people in the
system 
 not making mistakes.


The Equifax disaster is another lesson the airframe industry learned
generations 
ago. Compartmentalization. (Battleships and spy networks learned that centuries 
ago.)

A single security error in the Equifax system led to losing ALL of their data.

Sensitive data should be compartmentalized, i.e. being spread among systems
each 
with their own security. Access to one compartment does not give access to any 
other compartments.
Sep 16 2017
prev sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Friday, 15 September 2017 at 12:04:27 UTC, Kagamin wrote:

 Since width can't be negative, C programmer would use unsigned 
 integer for it


That's often a big mistake. Lots of people do it... but you 
shouldn't, exactly because of the wraparound behavior.
Sep 15 2017
parent reply Neia Neutuladh <neia ikeran.org> writes:
On Friday, 15 September 2017 at 12:33:56 UTC, Adam D. Ruppe wrote:

 On Friday, 15 September 2017 at 12:04:27 UTC, Kagamin wrote:

 Since width can't be negative, C programmer would use unsigned 
 integer for it


 That's often a big mistake. Lots of people do it... but you 
 shouldn't, exactly because of the wraparound behavior.


Signed integers have the same issue, no? Using int32s:

2147483635 * 400000000 * 4 = 674836480

It's just that you're more likely to be able to detect it, since 
a lot of inputs result in negative numbers.

One solution is to switch to the next larger integer size. That 
works up to 32-bit numbers. When you hit 64-bit, you've got to 
switch to BigInt.

Another solution is to check the overflow bit as appropriate. The 
checkedint package automates that.

The last solution that I can think of, specific to this type of 
thing, is to use the result to allocate a bounds-checked array, 
where the allocation function yields the appropriately sized 
array. You'll get an array bounds error that may be inscrutable.
Sep 15 2017
parent Guillaume Piolat <first.last gmail.com> writes:
On Friday, 15 September 2017 at 16:04:08 UTC, Neia Neutuladh 
wrote:

 The last solution that I can think of, specific to this type of 
 thing, is to use the result to allocate a bounds-checked array, 
 where the allocation function yields the appropriately sized 
 array. You'll get an array bounds error that may be inscrutable.


It's true that my example doesn't fail in the same way if eg.

    new ubyte[width * height]

was used.
Sep 15 2017
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/15/2017 1:46 AM, Guillaume Piolat wrote:

 If overflow checks happen to be more or less cheap like (surprinsingly) array 
 bounds checks are, it could be a nice thing to pay for.


https://dlang.org/phobos/std_experimental_checkedint.html
Sep 15 2017
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Friday, 15 September 2017 at 21:21:01 UTC, Walter Bright wrote:

 On 9/15/2017 1:46 AM, Guillaume Piolat wrote:

 If overflow checks happen to be more or less cheap like 
 (surprinsingly) array bounds checks are, it could be a nice 
 thing to pay for.


 https://dlang.org/phobos/std_experimental_checkedint.html


Will this ever be integrated directly into the compiler?
Sep 15 2017
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/15/2017 5:00 PM, bitwise wrote:

 On Friday, 15 September 2017 at 21:21:01 UTC, Walter Bright wrote:

 https://dlang.org/phobos/std_experimental_checkedint.html


 
 Will this ever be integrated directly into the compiler?


No plans to do so.
Sep 15 2017
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Friday, September 15, 2017 19:01:18 Walter Bright via Digitalmars-d 
wrote:

 On 9/15/2017 5:00 PM, bitwise wrote:

 On Friday, 15 September 2017 at 21:21:01 UTC, Walter Bright wrote:

 https://dlang.org/phobos/std_experimental_checkedint.html


 Will this ever be integrated directly into the compiler?


 No plans to do so.


There also really isn't a need to do so. If you care about having the
overflow checks, then you use Checked. If you don't, you don't. And from
what I recall of Andrei's talk on it, Checked is insanely customizable -
which a built-in feature wouldn't be.

Personally, I've never had a need for checked ints. I've rarely seen code
that would care, and when you do, it's usually pretty easy to deal with it
properly. But Checked is there for those who feel the need.

- Jonathan M Davis
Sep 18 2017
next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 18 September 2017 at 08:27:21 UTC, Jonathan M Davis 
wrote:

 There also really isn't a need to do so.


If there was no need then C/C++ compilers wouldn't provide it as 
an option…
Sep 18 2017
next sibling parent reply Kagamin <spam here.lot> writes:
On Monday, 18 September 2017 at 08:35:44 UTC, Ola Fosheim Grøstad 
wrote:

 If there was no need then C/C++ compilers wouldn't provide it 
 as an option…


Do they check unsigned integers?
Sep 18 2017
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 18 September 2017 at 11:42:19 UTC, Kagamin wrote:

 Do they check unsigned integers?


No, I don't believe they do, as unsigned integers are modular in 
C/C++. (And in D also signed integers are modular).
Sep 18 2017
parent reply Kagamin <spam here.lot> writes:
On Monday, 18 September 2017 at 17:46:52 UTC, Ola Fosheim Grøstad 
wrote:

 No, I don't believe they do, as unsigned integers are modular 
 in C/C++.


So you can't check third party code because it pervasively uses 
unsigned integers for lengths, sizes and everything else, obvious 
example: 
https://fossies.org/dox/libpng-1.6.32/structpng__info__def.html
Sep 20 2017
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Wednesday, 20 September 2017 at 10:01:14 UTC, Kagamin wrote:

 On Monday, 18 September 2017 at 17:46:52 UTC, Ola Fosheim 
 Grøstad wrote:

 No, I don't believe they do, as unsigned integers are modular 
 in C/C++.


 So you can't check third party code because it pervasively uses 
 unsigned integers for lengths, sizes and everything else, 
 obvious example: 
 https://fossies.org/dox/libpng-1.6.32/structpng__info__def.html


For more complex third party code you have to vet it anyway for 
bad practices.

For utilitarian libraries it could be quite useful. So, it all 
depends.
Sep 20 2017
prev sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Monday, September 18, 2017 08:35:44 Ola Fosheim Grøstad via Digitalmars-d 
wrote:

 On Monday, 18 September 2017 at 08:27:21 UTC, Jonathan M Davis

 wrote:

 There also really isn't a need to do so.


 If there was no need then C/C++ compilers wouldn't provide it as
 an option…


We have std.experimental.checkedint, so why would there be any need for it
to be in the compiler? The library solution provides the functionality and
does so in a much more flexible manner than the compiler reasonably could.

- Jonathan M Davis
Sep 18 2017
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 18 September 2017 at 14:36:35 UTC, Jonathan M Davis 
wrote:

 We have std.experimental.checkedint, so why would there be any 
 need for it to be in the compiler? The library solution 
 provides the functionality and does so in a much more flexible 
 manner than the compiler reasonably could.


So that you can use third party libraries?

Or debug your application?
Sep 18 2017
prev sibling parent Guillaume Piolat <contact spam.com> writes:
On Monday, 18 September 2017 at 08:27:21 UTC, Jonathan M Davis 
wrote:

 If you care about having the overflow checks


On Monday, 18 September 2017 at 08:27:21 UTC, Jonathan M Davis 
wrote:

 Personally, I've never had a need for checked ints. I've rarely 
 seen code that would care, and when you do, it's usually pretty 
 easy to deal with it properly. But Checked is there for those 
 who feel the need.


That we don't feel the need or care doesn't mean the problem 
doesn't exist. That's why I gave an example that I always felt 
was safe ( malloc(w*h)) but wasn't.

I'd wager no native programmer feel the need for overflow checks 
or Checked!int, that's why we have security problems in the first 
place.
Sep 18 2017
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/15/2017 04:46 AM, Guillaume Piolat wrote:

 As a die-hard native programmer I was always disgusted by integer 
 overflow checks and array bounds checks. Littering code with branches 
 everywhere? Just let me go as fast possible please!
 
 Last week I was explained by security people how a part of 
 vulnerabilities todays are attacks on image parsers, and how integer 
 overflow checks may help there.
 
 IIRC a typical attack on image format parser is to forge an image with a 
 width and height that will overflow an int.
 
 On allocation, the result of the multiplied wraps around like this:
 
      int width = parse_width_from_stream();     // eg: 131072
      int height = parse_height_from_stream();   // eg: 131073
      ubyte[] data = malloc(width * height * 4); // wraps around, 
 allocates way less memory than that


For the record, with the help of std.experimental.checkedint, the change 
that fixes the code would be:

malloc(width * height * 4) ==> malloc((checked(width) * height * 4).get)

That aborts the application with a message if a multiplication overflows.


Andrei
Sep 18 2017
parent reply Dennis Cote <private secret.com> writes:
On Monday, 18 September 2017 at 13:25:55 UTC, Andrei Alexandrescu 
wrote:

 For the record, with the help of std.experimental.checkedint, 
 the change that fixes the code would be:

 malloc(width * height * 4) ==> malloc((checked(width) * height 
 * 4).get)

 That aborts the application with a message if a multiplication 
 overflows.


Can it do something other than abort? Can it throw an overflow 
exception that could be caught to report the error and continue?

Dennis Cote
Sep 18 2017
parent reply Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 18 September 2017 at 22:32:28 UTC, Dennis Cote wrote:

 On Monday, 18 September 2017 at 13:25:55 UTC, Andrei 
 Alexandrescu wrote:

 For the record, with the help of std.experimental.checkedint, 
 the change that fixes the code would be:

 malloc(width * height * 4) ==> malloc((checked(width) * height 
 * 4).get)

 That aborts the application with a message if a multiplication 
 overflows.


 Can it do something other than abort? Can it throw an overflow 
 exception that could be caught to report the error and continue?


Yes. Use one of the provided hooks (e.g. [1][2][3]) or write one 
that fits your use case.

[1] 
https://dlang.org/phobos/std_experimental_checkedint.html#Abort
[2] 
https://dlang.org/phobos/std_experimental_checkedint.html#Throw
[3] https://dlang.org/phobos/std_experimental_checkedint.html#Warn
Sep 18 2017
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Monday, September 18, 2017 22:39:09 Moritz Maxeiner via Digitalmars-d 
wrote:

 On Monday, 18 September 2017 at 22:32:28 UTC, Dennis Cote wrote:

 On Monday, 18 September 2017 at 13:25:55 UTC, Andrei

 Alexandrescu wrote:

 For the record, with the help of std.experimental.checkedint,
 the change that fixes the code would be:

 malloc(width * height * 4) ==> malloc((checked(width) * height
 * 4).get)

 That aborts the application with a message if a multiplication
 overflows.


 Can it do something other than abort? Can it throw an overflow
 exception that could be caught to report the error and continue?


 Yes. Use one of the provided hooks (e.g. [1][2][3]) or write one
 that fits your use case.

 [1]
 https://dlang.org/phobos/std_experimental_checkedint.html#Abort
 [2]
 https://dlang.org/phobos/std_experimental_checkedint.html#Throw
 [3] https://dlang.org/phobos/std_experimental_checkedint.html#Warn


Yeah, it's really quite flexible with minimal code. Andrei talked about it
in his dconf 2017 talk:

https://www.youtube.com/watch?v=29h6jGtZD-U

- Jonathan M Davis
Sep 18 2017