[Bug c/68065] New: Size calculations for VLAs can overflow

[Bug c/68065] New: Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

            Bug ID: 68065
           Summary: Size calculations for VLAs can overflow
           Product: gcc
           Version: 5.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ch3root at openwall dot com
  Target Milestone: ---

The following program crashes while writing to a buffer:

#include <stdint.h>
#include <stdio.h>

int main(void)
{
  size_t size = SIZE_MAX / sizeof(int) + 2;
  int buf[size];

  printf("%zu\n", sizeof(buf));
  for (size_t i = 0; i < size; i++)
    buf[i] = 1;

  return 0;
}

(Compile without optimization or make sure the loop is not optimized away.)

It would be better to detect an overflow in the size calculation and crash
right away, before any harm is done.

While at it, size of VLAs could probably be limited to PRTDIFF_MAX to be in
line with ordinary arrays.

[Bug c/68065] Size calculations for VLAs can overflow

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
VLA also does not detect stack overflows either.

[Bug c/68065] Size calculations for VLAs can overflow

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #2 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
This seems like a matter for -fsanitize=undefined as I suggested in 
<https://gcc.gnu.org/ml/gcc-patches/2013-09/msg00948.html>.

[Bug c/68065] Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #5 from Alexander Cherepanov <ch3root at openwall dot com> ---
On 2015-10-27 02:27, joseph at codesourcery dot com wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065
>
> --- Comment #4 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
> On Mon, 26 Oct 2015, ch3root at openwall dot com wrote:
>
>> The core issue is an overflow in size computations which is not limited to VLA.
>> You can as easily get a crash with non-VLA-array+sizeof+malloc:
>>
>> #define N /* complex computation leading to.. */ (UINT_MAX / sizeof(int) + 2)
>>    int (*p)[N];
>
> That sounds like a completely separate bug.  Please file a separate bug in
> Bugzilla for it.  Any construction of a non-VLA type whose size is half or
> more of the address space should receive a compile-time error, like you
> get if you don't use a pointer here.

Ok, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68107 .

> VLA size overflow, however, is undefined behavior at runtime, not compile
> time, hence a matter for ubsan.

VLA size overflow is very similar to overflow in "new". Shouldn't it be 
handled in a similar way?

[Bug c/68065] Size calculations for VLAs can overflow

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #6 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Tue, 27 Oct 2015, ch3root at openwall dot com wrote:

> > VLA size overflow, however, is undefined behavior at runtime, not compile
> > time, hence a matter for ubsan.
> 
> VLA size overflow is very similar to overflow in "new". Shouldn't it be 
> handled in a similar way?

I'm thinking of it as essentially like stack overflow, where it's 
traditionally been the user's job to bound their stack allocations.  I 
think ubsan should enable all of (VLA size overflow checks, stack checking 
for fixed-size allocations to ensure the amount of stack space allocated 
in one go is small enough that overflow is guaranteed to be detected, 
similar checks for variable size allocations whether from VLAs or alloca).  
Of course separate options for various cases may make sense as well.

[Bug c/68065] Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #7 from Alexander Cherepanov <ch3root at openwall dot com> ---
On 2015-10-27 03:15, joseph at codesourcery dot com wrote:
>> VLA size overflow is very similar to overflow in "new". Shouldn't it be
>> handled in a similar way?
>
> I'm thinking of it as essentially like stack overflow,

The problem is not limited to stack allocations. The example in comment 
#3 works for VLAs as well. This would a quite elegant way to deal with 
untrusted sizes but it seem you cannot get away without any arithmetic 
check at all:-( Maybe saturated arithmetic for sizes could help but 
that's another can of worms.

Well, the problem in non-stack case seems to be in sizeof. My take: 
sizeof is an operator and C11, 6.5p5 applies to it:

   If an exceptional condition occurs during the evaluation of
   an expression (that is, if the result is not mathematically
   defined or not in the range of representable values for its
   type), the behavior is undefined.

That is, an oversized VLA is fine but taking its sizeof is UB. This is 
somewhat similar to how pointer difference is UB when outside ptrdiff_t 
range.

There could be an argument that sizeof works with unsigned types and 
hence should wrap per C11, 6.2.5p9:

   A computation involving unsigned operands can never overflow,
   because a result that cannot be represented by the resulting
   unsigned integer type is reduced modulo the number that is
   one greater than the largest value that can be represented
   by the resulting type.

But sizeof doesn't directly compute anything with its operand (even if 
it's unsigned). Therefore this rule is not applicable.

It seems I can convince myself that non-stack case is Ok:-)

> where it's
> traditionally been the user's job to bound their stack allocations.

Yes, and it's a pity that there is no diagnostics for stack allocation 
problems by default given it's not UB and the code could be conforming 
according to the C standards.

> I think ubsan should enable all of (VLA size overflow checks,

Yes, catching overflows in "sizeof(int[size])" is definitely nice. But 
catching "_Alignof(int[size])" etc. for huge "size" is probably fine too.

> stack checking
> for fixed-size allocations to ensure the amount of stack space allocated
> in one go is small enough that overflow is guaranteed to be detected,
> similar checks for variable size allocations whether from VLAs or alloca).
> Of course separate options for various cases may make sense as well.

It's not practiced in gcc to track such things via the bug tracker?

[Bug c/68065] Size calculations for VLAs can overflow

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #8 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
I think it's undefined at the point where a type exceeds the limit on the 
size of an object (half the address space minus one byte), whether or not 
sizeof is used or any object with that type is constructed - that is, as 
soon as the language semantics involve evaluation of the array sizes for 
the VLA type in question.  (If the sizes are neither evaluated nor 
required, e.g. sizeof (int (*)[size]), or when replaced by [*] at function 
prototype scope, I don't consider that undefined; if required but not 
evaluated, as in certain obscure cases of conditional expressions, that's 
a different case of undefined behavior.)

[Bug c/68065] Size calculations for VLAs can overflow

[danielmicay at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

Daniel Micay <danielmicay at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |danielmicay at gmail dot com

--- Comment #9 from Daniel Micay <danielmicay at gmail dot com> ---
> VLA also does not detect stack overflows either.

Stack overflows are detected with -fstack-check, or at least they would be if
the option worked properly: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66479
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65958

I've always found it quite bad that well-defined code with GCC can actually be
exploited (arbitrary write vulnerabilities) due to the fact that -fstack-check
is not enabled by default. MSVC++ and Clang on Windows guarantee that stack
overflows from well-defined code (large stack frames, VLAs) will be caught.
However, the switch seems to cause a significant performance hit for functions
where it triggers (which are rare but sometimes performance critical, a good
example is jemalloc's rbtree implementation which uses arrays rather than
recursion) and compatibility issues due to the way it's currently implemented:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67265/.

[Bug c/68065] Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #10 from Alexander Cherepanov <ch3root at openwall dot com> ---
On 2015-10-27 20:09, joseph at codesourcery dot com wrote:
> I think it's undefined at the point where a type exceeds the limit on the
> size of an object

This would probably be the most reasonable approach but it's not clear 
if the text of the standard supports it. E.g., the list of UB (C11, 
J.2p1) includes this one:

   - The size expression in an array declaration is not a constant 
expression and evaluates at program execution time to a nonpositive 
value (6.7.6.2).

but I don't see anything like what you described. Perhaps I'm missing 
something?

> (half the address space minus one byte),

And this particular value for the limit on the size of an object is 
troublesome because it's completely undocumented (AFAICT) and goes 
against what the standard hints to (whole idea of size_t becomes 
useless, right?). It is also not supported by glibc (malloc), can lead 
to vulnerabilities etc. etc. but this discussion is for 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67999 .

> whether or not
> sizeof is used or any object with that type is constructed - that is, as
> soon as the language semantics involve evaluation of the array sizes for
> the VLA type in question.  (If the sizes are neither evaluated nor
> required, e.g. sizeof (int (*)[size]), or when replaced by [*] at function
> prototype scope, I don't consider that undefined; if required but not
> evaluated, as in certain obscure cases of conditional expressions, that's
> a different case of undefined behavior.)

This is also very nice approach. (Although it seems to differ from the 
approach to non-VLA arrays in 
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68107#c1 .) But, again, I 
don't see how to tie it to the standard. It doesn't mean that this 
approach is wrong, the standard probably just lacks necessary rules. But 
it would be nice to make it clear which rules are from the standard and 
which are gcc's own.

[Bug c/68065] Size calculations for VLAs can overflow

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #11 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Wed, 28 Oct 2015, ch3root at openwall dot com wrote:

> --- Comment #10 from Alexander Cherepanov <ch3root at openwall dot com> ---
> On 2015-10-27 20:09, joseph at codesourcery dot com wrote:
> > I think it's undefined at the point where a type exceeds the limit on the
> > size of an object
> 
> This would probably be the most reasonable approach but it's not clear 
> if the text of the standard supports it. E.g., the list of UB (C11, 
> J.2p1) includes this one:
> 
>    - The size expression in an array declaration is not a constant 
> expression and evaluates at program execution time to a nonpositive 
> value (6.7.6.2).
> 
> but I don't see anything like what you described. Perhaps I'm missing 
> something?

The standard has a list of minimum implementation limits, but it is not 
exhaustive as to all areas in which there may be limits.  I think it is 
reasonable to consider "bytes in an object" to cover such limits for any 
object type, whether or not an object of that type is constructed.

It is well-known that strictly conforming programs do not exist when you 
interpret the standard strictly.

The existence of rsize_t in Annex K hints at the likelihood of problems 
with objects larger than SIZE_MAX >> 1 bytes.

> This is also very nice approach. (Although it seems to differ from the 
> approach to non-VLA arrays in 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68107#c1 .) But, again, I 

It's universally the case that size-related things that are constraint 
violations (compile-time errors) for non-VLAs are runtime undefined 
behavior for VLAs.  This applies to size overflow just as to e.g. 
non-positive array sizes.

There are also lots of details around evaluation of VLA sizes that the C 
standard is silent on (the C standard doesn't really have a notion of type 
names being evaluated at all, only expressions, but VLAs in type names 
only make sense when type names get evaluated at an appropriate point in 
execution) that I had to fill out when sorting out constant expressions 
and VLAs issues for GCC 4.5.

[Bug c/68065] Size calculations for VLAs can overflow

[ebotcazou at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org

--- Comment #12 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Stack overflows are detected with -fstack-check, or at least they would be
> if the option worked properly:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66479
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65958

Yes, it works, i.e. it detects stack overflows in real life.  The first PR is
certainly annoying but largely artificial and the second PR is actually a
generic bug in the gimplifier with VLAs and alloca that the old implementation
happens to run into; the modern one doesn't.

> I've always found it quite bad that well-defined code with GCC can actually
> be exploited (arbitrary write vulnerabilities) due to the fact that
> -fstack-check is not enabled by default. MSVC++ and Clang on Windows
> guarantee that stack overflows from well-defined code (large stack frames,
> VLAs) will be caught.

Same for GCC on Windows (but it does out-of-line stack checking).

> However, the switch seems to cause a significant performance hit for functions 
> where it triggers (which are rare but sometimes performance critical, a good 
> example is jemalloc's rbtree implementation which uses arrays rather than 
> recursion) and compatibility issues due to the way it's currently implemented:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67265/.

This one is more of a register allocation issue actually.

[Bug c/68065] Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #13 from Alexander Cherepanov <ch3root at openwall dot com> ---
On 2015-10-27 20:09, joseph at codesourcery dot com wrote:
> I think it's undefined at the point where a type exceeds the limit on the
> size of an object (half the address space minus one byte)

Wait, "char a[SIZE_MAX / 2]" works in gcc 5.2. Should I file a bug?

[Bug c/68065] Size calculations for VLAs can overflow

[joseph at codesourcery dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #14 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Wed, 28 Oct 2015, ch3root at openwall dot com wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065
> 
> --- Comment #13 from Alexander Cherepanov <ch3root at openwall dot com> ---
> On 2015-10-27 20:09, joseph at codesourcery dot com wrote:
> > I think it's undefined at the point where a type exceeds the limit on the
> > size of an object (half the address space minus one byte)
> 
> Wait, "char a[SIZE_MAX / 2]" works in gcc 5.2. Should I file a bug?

That's half the address space minus one byte (SIZE_MAX is odd, equal to 
(size_t) -1).  That is, it's meant to be accepted, but one byte more 
shouldn't be.

[Bug c/68065] Size calculations for VLAs can overflow

[ch3root at openwall dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065

--- Comment #15 from Alexander Cherepanov <ch3root at openwall dot com> ---
On 2015-10-29 02:38, joseph at codesourcery dot com wrote:
>>> I think it's undefined at the point where a type exceeds the limit on the
>>> size of an object (half the address space minus one byte)
>>
>> Wait, "char a[SIZE_MAX / 2]" works in gcc 5.2. Should I file a bug?
>
> That's half the address space minus one byte (SIZE_MAX is odd, equal to
> (size_t) -1).  That is, it's meant to be accepted, but one byte more
> shouldn't be.

Sure, of course, sorry for the noise.