Bug 68065 - Size calculations for VLAs can overflow
Summary: Size calculations for VLAs can overflow
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: sanitizer (show other bugs)
Version: 5.2.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-10-23 08:36 UTC by Alexander Cherepanov
Modified: 2019-09-18 11:45 UTC (History)
7 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2015-11-10 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Alexander Cherepanov 2015-10-23 08:36:04 UTC
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.
Comment 1 Andrew Pinski 2015-10-23 09:22:11 UTC
VLA also does not detect stack overflows either.
Comment 2 joseph@codesourcery.com 2015-10-23 16:22:38 UTC
This seems like a matter for -fsanitize=undefined as I suggested in 
<https://gcc.gnu.org/ml/gcc-patches/2013-09/msg00948.html>.
Comment 3 Alexander Cherepanov 2015-10-26 19:39:26 UTC
(In reply to joseph@codesourcery.com from comment #2)
> This seems like a matter for -fsanitize=undefined 

UBSAN is intended to help with invalid programs but this code looks like valid. Hence diagnostic for problems with such code seem to belong to core gcc.

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];
  printf("%zu\n", sizeof *p);
  p = malloc(sizeof *p);
  if (!p)
    return 1;
  for (unsigned i = 0; i < N; i++)
    (*p)[i] = 1;

Please note:
- size in this examples is tuned so that it crashes on 32-bit platform only and works fine on 64-bit one, i.e. the problem could arise in not quite evident situations;
- the approach to dynanmic arrays a-la Pascal -- "int (*p)[n]; p = malloc(sizeof *p);" -- is not common in C but could be expected to become more popular now that UBSAN supports bounds-checking for VLAs.
Comment 4 joseph@codesourcery.com 2015-10-26 23:27:49 UTC
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.

VLA size overflow, however, is undefined behavior at runtime, not compile 
time, hence a matter for ubsan.
Comment 5 Alexander Cherepanov 2015-10-27 00:06:15 UTC
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?
Comment 6 joseph@codesourcery.com 2015-10-27 00:15:17 UTC
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.
Comment 7 Alexander Cherepanov 2015-10-27 14:25:28 UTC
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?
Comment 8 joseph@codesourcery.com 2015-10-27 17:09:21 UTC
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.)
Comment 9 Daniel Micay 2015-10-27 18:29:28 UTC
> 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/.
Comment 10 Alexander Cherepanov 2015-10-28 11:27:59 UTC
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.
Comment 11 joseph@codesourcery.com 2015-10-28 13:15:23 UTC
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.
Comment 12 Eric Botcazou 2015-10-28 16:35:02 UTC
> 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.
Comment 13 Alexander Cherepanov 2015-10-28 23:30:06 UTC
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?
Comment 14 joseph@codesourcery.com 2015-10-28 23:38:51 UTC
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.
Comment 15 Alexander Cherepanov 2015-10-28 23:43:21 UTC
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.
Comment 16 Marek Polacek 2015-11-10 14:40:00 UTC
Recategorizing as a ubsan RFE.
Comment 17 Daniel Micay 2015-11-10 21:22:13 UTC
It's well-defined C code though. It shouldn't be possible to for anything to go wrong here when using -fstack-check, i.e. it should be guaranteed to trigger a stack overflow which is caught. The size wrapping back around is different.
Comment 18 Daniel Micay 2015-11-10 21:24:53 UTC
Also, it's possible to use segmented stacks to avoid stack overflow and this probably breaks in that context too. That's a very niche use case compared to -fstack-check though.
Comment 19 Martin Sebor 2015-11-10 23:52:14 UTC
By coincidence, I just raised the issue of sizeof overflow due to excessively large VLA types with WG14 last week.  I wasn't aware of this issue or the discussion until Marek pointed me at it (thanks!)  FWIW, I think this problem should be handled in GCC rather than in UBSAN, by emitting a runtime check (similar to what's done in the C++ new expression) at the point the excessively large VLA type (not the object) is used in a way that would cause sizeof to overflow, and trapping when the check fails.  I raised this with WG14 because by my reading the standard seems to allow creating excessively large VLA types and require the runtime sizeof expression to overflow (i.e., there is no undefined behavior).  Once it's clarified that the behavior is, in fact, undefined, the runtime check and trap will be justified.
Comment 20 joseph@codesourcery.com 2015-11-11 00:25:35 UTC
Undefined behavior when the type is created (not when an object of that 
type is declared or when sizeof is used) seems entirely in accordance with 
normal C practice in areas such as stack overflow[*] (that is, where the C 
standard fails to recognize limits in such areas but all implementations 
in practice have such limits, that's a defect in the C standard).

[*] The existence of stack limits cannot be deduced from the argument that 
all objects in C are required by the C standard to have addresses, because 
you can recurse, and even do Turing-complete computation, without creating 
any new objects.  Cf. <http://www.open-std.org/jtc1/sc22/wg14/12727>.

One way (for C) to get a check that is evaluated at the point where the 
size of the type is evaluated is to hook into how grokdeclarator stores 
array size expressions in *expr (other parts of the front end then ensure 
that *expr is evaluated at exactly the right time).  Instead of storing 
plain size expressions, it would be necessary to store a more complicated 
expression containing the checks.  *And* it would be necessary to put 
checks in there for the case where a constant-size array is declared but 
the elements of that array are of variable size, to make sure that 
overflow in the multiplication is detected in that case (right now, *expr 
is used only for variable size expressions, because they might have side 
effects so the time of evaluation matters).  This applies regardless of 
what the conditions are for when to enable such a check.
Comment 21 Daniel Micay 2015-11-11 00:36:59 UTC
(In reply to joseph@codesourcery.com from comment #20)
> Undefined behavior when the type is created (not when an object of that 
> type is declared or when sizeof is used) seems entirely in accordance with 
> normal C practice in areas such as stack overflow[*] (that is, where the C 
> standard fails to recognize limits in such areas but all implementations 
> in practice have such limits, that's a defect in the C standard).

Stack overflow is undefined with GCC, but MSVC++ and Clang on Windows guarantee that it will be caught if the program doesn't invoke any truly undefined behavior. Clang will be getting an implementation for other platforms soon, and it will probably end up being enabled by default since it really has no significant overhead.

The implementation of -fstack-check in GCC does have significant overhead, but it doesn't have to be that way. It shouldn't go out of the way to provide a proper stack trace with -O2/-O3 (or whatever other reasons it has for the slow implementation).
Comment 22 Martin Sebor 2015-11-11 00:53:50 UTC
(In reply to joseph@codesourcery.com from comment #20)
> where the C 
> standard fails to recognize limits in such areas but all implementations 
> in practice have such limits, that's a defect in the C standard).

I agree that that's one way to look at it (and the way I would prefer to see it).  Another way is that the standard requires sizeof(excessively-large-vla-type) to overflow/wrap.  That's how the implementations I've tested behave, including GCC.  This could, of course, be said to be a manifestation of undefined behavior rather than a feature.  Either way, the result is the same and the problem with it, as was pointed out in the WG14 discussion, is that it can lead to buffer overflow when the overflowed size of the VLA type is used is to allocate memory on the heap and the number of elements in the VLA to write to the memory.

> One way (for C) to get a check that is evaluated at the point where the 
> size of the type is evaluated is to hook into how grokdeclarator stores 
> array size expressions in *expr (other parts of the front end then ensure 
> that *expr is evaluated at exactly the right time).  Instead of storing 
> plain size expressions, it would be necessary to store a more complicated 
> expression containing the checks.  *And* it would be necessary to put 
> checks in there for the case where a constant-size array is declared but 
> the elements of that array are of variable size, to make sure that 
> overflow in the multiplication is detected in that case (right now, *expr 
> is used only for variable size expressions, because they might have side 
> effects so the time of evaluation matters).  This applies regardless of 
> what the conditions are for when to enable such a check.

Yes.  This is close to what C++ new expressions already do, except that they throw an exception rather than trapping (this is required by the C++ standard).
Comment 23 Alexander Cherepanov 2015-11-11 03:21:27 UTC
On 2015-11-11 03:53, msebor at gcc dot gnu.org wrote:
> Another way is that the standard requires
> sizeof(excessively-large-vla-type) to overflow/wrap.  That's how the
> implementations I've tested behave, including GCC.  This could, of course, be
> said to be a manifestation of undefined behavior rather than a feature.  Either
> way, the result is the same and the problem with it, as was pointed out in the
> WG14 discussion, is that it can lead to buffer overflow when the overflowed
> size of the VLA type is used is to allocate memory on the heap and the number
> of elements in the VLA to write to the memory.

1. Yes, the practical problem is potential buffer overflows (examples 
are in the description of this PR and in the comment #3).

2. The practical problem is size calculation in general, it's not 
limited to sizeof operation. You don't need to use sizeof to create 
oversized automatic VLA (an example in the description).

3. IMHO overflow in sizeof operation is UB due to C11, 6.5p5, and 
wrapping according to C11, 6.2.5p9, is not applicable (see the comment #7).

4. From the POV of the standard I don't see much difference between VLA 
and ordinary arrays in this question. AFAICT the standard doesn't place 
limits on constructed types of any kind and hence oversized types are 
permitted by the standard. See comment #3 (or pr68107) for a practical 
example of sizeof overflow with an array of a known constant size which 
works with the current gcc.

Gcc chooses to prohibit oversized types when it can easily catch them 
and fails compilation stumbling upon an oversized array of a known 
constant size (modulo pr68107) but is this a case of undefined behavior, 
implementation-defined behavior or what?

3. The same for sizes of objects. There is an environmental limit for 
"bytes in an object" but it's marked as "(in a hosted environment 
only)". So there is no such limit in the standard for a freestanding 
implementation, right? But I doubt that you are supposed to be able to 
create oversized arrays (either static or automatic) even in a 
freestanding implementation.

4. It's well known that there could be problems with the amount of 
automatic storage due to limited stack size. But the same is true for 
static storage. Even in a hosted environment and if you meet the limit 
of the compiler there is no guarantee that your program will 
successfully run. Try "char a[-1ul/2]; int main() { }". For me, it 
compiles fine but says "Killed" when run:-) That is, the "execution 
environment" part of the implementation failed.
Comment 24 Eric Botcazou 2015-11-11 08:16:55 UTC
> Stack overflow is undefined with GCC, but MSVC++ and Clang on Windows
> guarantee that it will be caught if the program doesn't invoke any truly
> undefined behavior.

Just as GCC on Windows...

> The implementation of -fstack-check in GCC does have significant overhead,
> but it doesn't have to be that way. It shouldn't go out of the way to
> provide a proper stack trace with -O2/-O3 (or whatever other reasons it has
> for the slow implementation).

Figures please, otherwise that's just FUD as usual.
Comment 25 Daniel Micay 2015-11-11 08:47:19 UTC
> Just as GCC on Windows...

Sure. I'm pointing out that Windows has had safety here for years, while Linux doesn't. It should. It really shouldn't be possible to exploit well-defined code. Running out of resources and aborting isn't ideal but that's at least sane and doing better doesn't seem possible for C.

> Figures please, otherwise that's just FUD as usual.

... pointing out that something isn't implemented ideally is FUD now? If it had no significant performance hit (which should be the case for optimized C, because it shouldn't need to reserve a register), then it would surely be enabled by default.

We tried enabling it in Arch Linux but it had to be backed out due to performance concerns. Some compatibility issues came up (due to inline assembly) and then investigation into it demonstrated that it wasn't really causing a negligible performance hit, especially on i686. Among other things, it causes a significant performance hit (over 5% slower in a malloc micro-benchmark on x86_64, more on i686) for jemalloc which has large enough stack frames to trigger it and essentially all of the code is inlined. It's usually pretty small... but a lot more than it should be.

Anyway, I was just trying to be helpful. I'm only really interested in Android these days so GCC isn't really something I care about... I just happened to have thoughts about this stuff because I worked on similar issues in the Rust compiler / standard libraries (Rust is why LLVM is getting proper stack checking at all, Clang implements -fstack-check as a no-op right now for 'compatibility') and recently Bionic.
Comment 26 Eric Botcazou 2015-11-11 09:46:22 UTC
> Sure. I'm pointing out that Windows has had safety here for years, while
> Linux doesn't.

Thanks for correcting, the initial formulation was quite misleading and could be understood as GCC not being on par with MSVC and Clang on Windows; it is.

> ... pointing out that something isn't implemented ideally is FUD now? If it
> had no significant performance hit (which should be the case for optimized
> C, because it shouldn't need to reserve a register), then it would surely be
> enabled by default.

Well, the sentence is "The implementation of -fstack-check in GCC does have significant overhead" so it seems to be talking about something implemented.
-fstack-check has a measurable overhead but doesn't cause a significant performance hit in most cases.

> We tried enabling it in Arch Linux but it had to be backed out due to
> performance concerns. Some compatibility issues came up (due to inline
> assembly) and then investigation into it demonstrated that it wasn't really
> causing a negligible performance hit, especially on i686. Among other
> things, it causes a significant performance hit (over 5% slower in a malloc
> micro-benchmark on x86_64, more on i686) for jemalloc which has large enough
> stack frames to trigger it and essentially all of the code is inlined. It's
> usually pretty small... but a lot more than it should be.

Thanks for the figures.  There is a specific issue on x86{-64}/Linux caused by the reservation of the frame pointer in order to be able to unwind the stack for propagating exceptions (stack checking was initially implemented for Ada and the Ada language requires stack overflows to be turned into exceptions that can be caught) and which also gives rise to PR target/67265; that's not the case on other platforms.  I'll propose a fix for the PR.
Comment 27 Alexander Cherepanov 2015-11-11 11:03:52 UTC
On 2015-11-11 11:16, ebotcazou at gcc dot gnu.org wrote:
 > On 2015-11-11 03:36, danielmicay at gmail dot com wrote:
>> The implementation of -fstack-check in GCC does have significant overhead,
>> but it doesn't have to be that way. It shouldn't go out of the way to
>> provide a proper stack trace with -O2/-O3 (or whatever other reasons it has
>> for the slow implementation).
>
> Figures please, otherwise that's just FUD as usual.

Are you saying that -fstack-check is ready for use? Why it's not 
documented (except for Ada and in gccint)?

According to comments[1][2] by Florian Wiemer (cc'd) in 2013 it's not 
production-ready and "used to be rather buggy". Is this changed?

[1] https://gcc.gnu.org/ml/gcc-patches/2013-09/msg01176.html
[2] http://www.openwall.com/lists/oss-security/2013/01/23/4
Comment 28 Eric Botcazou 2015-11-11 11:57:43 UTC
> Are you saying that -fstack-check is ready for use? Why it's not 
> documented (except for Ada and in gccint)?

!???  See 3.18 Options for Code Generation Conventions in the manual.

> According to comments[1][2] by Florian Wiemer (cc'd) in 2013 it's not 
> production-ready and "used to be rather buggy". Is this changed?
> 
> [1] https://gcc.gnu.org/ml/gcc-patches/2013-09/msg01176.html
> [2] http://www.openwall.com/lists/oss-security/2013/01/23/4

Yes, at least on mainstream architectures (x86, x86-64, Alpha, MIPS, SPARC, PowerPC, IA-64).  ARM and AArch64 need the PR middle-end/65958 changes.
Comment 29 Alexander Cherepanov 2015-11-11 12:46:52 UTC
On 2015-11-11 14:57, ebotcazou at gcc dot gnu.org wrote:
>> Are you saying that -fstack-check is ready for use? Why it's not
>> documented (except for Ada and in gccint)?
>
> !???  See 3.18 Options for Code Generation Conventions in the manual.

Ouch. Searching in Google for 'fstack-check gcc', gnat and gccint are 
the first hits but Code-Gen-Options is not on the first page. (For other 
options it usually works quite well.) And looking for it in the manual 
near -fstack-protector, i.e. in "3.10 Options That Control 
Optimization", doesn't find anything. I should have tried Option Index 
at least. It's documented even for gcc 2.95.3.

>> According to comments[1][2] by Florian Wiemer (cc'd) in 2013 it's not
>> production-ready and "used to be rather buggy". Is this changed?
>>
>> [1] https://gcc.gnu.org/ml/gcc-patches/2013-09/msg01176.html
>> [2] http://www.openwall.com/lists/oss-security/2013/01/23/4
>
> Yes, at least on mainstream architectures (x86, x86-64, Alpha, MIPS, SPARC,
> PowerPC, IA-64).  ARM and AArch64 need the PR middle-end/65958 changes.

Cool! One more question, if you don't mind: which version of gcc do I 
need for this -- is 4.9.2 ok or 5 is required? Links to additional info 
would be appreciated.
Comment 30 joseph@codesourcery.com 2015-11-11 22:51:55 UTC
On Wed, 11 Nov 2015, ch3root at openwall dot com wrote:

> 4. From the POV of the standard I don't see much difference between VLA 
> and ordinary arrays in this question. AFAICT the standard doesn't place 
> limits on constructed types of any kind and hence oversized types are 
> permitted by the standard. See comment #3 (or pr68107) for a practical 

"permitted by" only in the sense of "the standard does not require 
implementations to reject them".  It is not intended that the listed 
implementation limits are the only limits that there may be, at compile 
time or run time.

> 3. The same for sizes of objects. There is an environmental limit for 
> "bytes in an object" but it's marked as "(in a hosted environment 
> only)". So there is no such limit in the standard for a freestanding 
> implementation, right? But I doubt that you are supposed to be able to 

No, what's "in a hosted environment only" is the requirement that the 
implementation translate and execute some program with a 65535-byte object 
(and an instance of the other given limits, simultaneously); freestanding 
implementations may have an object size limit smaller than 65535 bytes.  
That is, effectively, C99 and above do not support hosted environments 
with a 16-bit address space; systems with a 16-bit address space are only 
supported for freestanding implementations.
Comment 31 Martin Sebor 2015-11-12 03:25:45 UTC
(In reply to Alexander Cherepanov from comment #23)

> 2. The practical problem is size calculation in general, it's not 
> limited to sizeof operation. You don't need to use sizeof to create 
> oversized automatic VLA (an example in the description).

Agreed.  Creating an automatic VLA object that exhausts the stack is bad.  In all likelihood it will crash the program.  I'm not sure to what extent it might be exploitable.  Allowing a sizeof expression to overflow given a VLA type is benign in an of itself, but can lead to more subtle bugs depending on how the result is used (e.g., to allocate an array on the heap whose elements are then written to).  Some of those bugs have known exploits.

> 
> 3. IMHO overflow in sizeof operation is UB due to C11, 6.5p5, and 
> wrapping according to C11, 6.2.5p9, is not applicable (see the comment #7).

No, that's not a correct interpretation.  It's exactly the other way around.  Sizeof is computed in an unsigned type.

> 4. From the POV of the standard I don't see much difference between VLA 
> and ordinary arrays in this question. AFAICT the standard doesn't place 
> limits on constructed types of any kind and hence oversized types are 
> permitted by the standard. See comment #3 (or pr68107) for a practical 
> example of sizeof overflow with an array of a known constant size which 
> works with the current gcc.

It is the intent of the standard to allow implementations to impose such a limit.  It may not be specified with sufficient clarity in the text, but the intent is reflected in the C99 Rationale.

> Gcc chooses to prohibit oversized types when it can easily catch them 
> and fails compilation stumbling upon an oversized array of a known 
> constant size (modulo pr68107) but is this a case of undefined behavior, 
> implementation-defined behavior or what?

For non-VLA types, creating a type whose size exceeds the implementation-defined limit is a constraint violation.  Violations of constraints are diagnosable; they lead to undefined behavior at runtime.  (IMO, the standard is unclear for VLAs but I think the same rule should apply and I'm working to get it clarified to that effect.)

> 
> 3. The same for sizes of objects. There is an environmental limit for 
> "bytes in an object" but it's marked as "(in a hosted environment 
> only)". So there is no such limit in the standard for a freestanding 
> implementation, right? But I doubt that you are supposed to be able to 
> create oversized arrays (either static or automatic) even in a 
> freestanding implementation.

Again, the limit is implementation-defined, and breaking it is a diagnosable constraint violation.
Comment 32 Alexander Cherepanov 2015-11-19 23:05:13 UTC
Sorry for the late reply. Decided to read DR 260 and got distracted. It 
so fundamentally undermines the base of classical C that it took me some 
time to grasp the scale:-)

On 2015-11-12 01:51, joseph at codesourcery dot com wrote:
>> 4. From the POV of the standard I don't see much difference between VLA
>> and ordinary arrays in this question. AFAICT the standard doesn't place
>> limits on constructed types of any kind and hence oversized types are
>> permitted by the standard. See comment #3 (or pr68107) for a practical
>
> "permitted by" only in the sense of "the standard does not require
> implementations to reject them".  It is not intended that the listed
> implementation limits are the only limits that there may be, at compile
> time or run time.

What does the following mean then?

C11, 4p5:
"A strictly conforming program[...] It [...] shall not exceed any 
minimum implementation limit."

C11, 4p6:
"A conforming hosted implementation shall accept any strictly conforming 
program."

>> 3. The same for sizes of objects. There is an environmental limit for
>> "bytes in an object" but it's marked as "(in a hosted environment
>> only)". So there is no such limit in the standard for a freestanding
>> implementation, right? But I doubt that you are supposed to be able to
>
> No, what's "in a hosted environment only" is the requirement that the
> implementation translate and execute some program with a 65535-byte object
> (and an instance of the other given limits, simultaneously); freestanding
> implementations may have an object size limit smaller than 65535 bytes.
> That is, effectively, C99 and above do not support hosted environments
> with a 16-bit address space; systems with a 16-bit address space are only
> supported for freestanding implementations.

I see, thanks for the info.
Comment 33 Alexander Cherepanov 2015-11-20 00:25:06 UTC
On 2015-11-12 06:25, msebor at gcc dot gnu.org wrote:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68065
>
> --- Comment #31 from Martin Sebor <msebor at gcc dot gnu.org> ---
> (In reply to Alexander Cherepanov from comment #23)
>
>> 2. The practical problem is size calculation in general, it's not
>> limited to sizeof operation. You don't need to use sizeof to create
>> oversized automatic VLA (an example in the description).
>
> Agreed.  Creating an automatic VLA object that exhausts the stack is bad.  In
> all likelihood it will crash the program.  I'm not sure to what extent it might
> be exploitable.

 From http://www.openwall.com/lists/oss-security/2014/11/03/2 :
"It can be exploitable in multithreaded programs though if there is
an unused stack allocation of at least one page further down in the
stack."

Sorry, don't have more info off-hand.

> Allowing a sizeof expression to overflow given a VLA type is
> benign in an of itself, but can lead to more subtle bugs depending on how the
> result is used (e.g., to allocate an array on the heap whose elements are then
> written to).  Some of those bugs have known exploits.

Sure.

>> 3. IMHO overflow in sizeof operation is UB due to C11, 6.5p5, and
>> wrapping according to C11, 6.2.5p9, is not applicable (see the comment #7).
>
> No, that's not a correct interpretation.  It's exactly the other way around.
> Sizeof is computed in an unsigned type.

IMHO, how sizeof is computed is an implementation detail. C11 doesn't 
describe it at all. E.g., for arrays it doesn't mention multiplication 
and just says that "the result is the total number of bytes in the 
array". From another side: an operand of sizeof is usually not unsigned. 
Even when the operand is unsigned, sizeof doesn't compute anything with 
it, sizeof work with its type.

>> 4. From the POV of the standard I don't see much difference between VLA
>> and ordinary arrays in this question. AFAICT the standard doesn't place
>> limits on constructed types of any kind and hence oversized types are
>> permitted by the standard. See comment #3 (or pr68107) for a practical
>> example of sizeof overflow with an array of a known constant size which
>> works with the current gcc.
>
> It is the intent of the standard to allow implementations to impose such a
> limit.  It may not be specified with sufficient clarity in the text, but the
> intent is reflected in the C99 Rationale.

Yeah, it seems to be a known problem without know solution:-) But IMHO:

* if C11, 4p6, (about acceptig any strictly conforming
program) is really mean what I think it means it should be fixed;

* the scope of the problem should be somehow acknowledged and preferably 
limited in the standard. Something like saying that an implementation 
can impose any other restrictions but those restrictions must be 
documented. It's a sad situation when arbitrary limits could be imposed 
but there is no way for a user to find out which. The ideal illustration 
here is pr67999. It's a limit which can lead to security problems, which 
is not documented and which is not detected at compile- or run-time.
Comment 34 joseph@codesourcery.com 2015-11-20 01:06:30 UTC
On Thu, 19 Nov 2015, ch3root at openwall dot com wrote:

> What does the following mean then?
> 
> C11, 4p5:
> "A strictly conforming program[...] It [...] shall not exceed any 
> minimum implementation limit."

It's well-known that, if you read the standard literally, strictly 
conforming programs may not exist; too much is unspecified or 
implementation-defined (including, in general, limits on supported 
programs; cf 1#2 "This International Standard does not specify ... the 
size or complexity of a program and its data that will exceed the capacity 
of any specific data-processing system or the capacity of a particular 
processor").

In general, you can only reason about C programs conditional on the 
program not exceeding any implementation limit.
Comment 35 Alexander Cherepanov 2015-11-21 00:45:32 UTC
On 2015-11-20 04:06, joseph at codesourcery dot com wrote:
>> What does the following mean then?
>>
>> C11, 4p5:
>> "A strictly conforming program[...] It [...] shall not exceed any
>> minimum implementation limit."
>
> It's well-known that, if you read the standard literally, strictly
> conforming programs may not exist;

I've heard about such a POV but I don't think I've seen a compelling 
reasoning backing it. The definition of a strictly conforming program 
depends only on requirement of the standard, it's not affected by 
properties of existing implementations.

Take e.g. "shall not exceed any minimum implementation limit" part. It 
talks about _minimum_ implementation limits which presumably refer to 
5.2.4.1. It doesn't say "shall not exceed any implementation limit of 
any implementation". The fact that gcc limits objects to 2^31-1 bytes on 
32-bits platforms is not relevant to a strictly conforming program, it 
should not exceed a _minimum_ implementation limit of 65535 bytes. 
Implementation don't define _minimum_ implementation limits.

The fact that the standard doesn't limit depth of recursion, as 
described e.g. in part VI of N1637, doesn't mean there are no strictly 
conforming program, it means that are no conforming implementations. And 
it would be nice if existing implementations try to be more conforming 
and at least try to detect such things.

> too much is unspecified or
> implementation-defined (including, in general, limits on supported
> programs;  cf 1#2 "This International Standard does not specify ... the
> size or complexity of a program and its data that will exceed the capacity
> of any specific data-processing system or the capacity of a particular
> processor").

Yes, the standard doesn't describe if a particular processor is suitable 
for building a conforming implementation. But it doesn't affect which 
programs are strictly conforming.

> In general, you can only reason about C programs conditional on the
> program not exceeding any implementation limit.

Yeah, in practice, it's not very important whether strictly conforming 
programs don't exist or conforming implementations:-) But it could 
affect views on responsibility of implementations to diagnose such bad 
situations as stack exhaustion.
Comment 36 Jakub Jelinek 2016-04-27 10:58:59 UTC
GCC 6.1 has been released.
Comment 37 Jakub Jelinek 2016-12-21 10:59:51 UTC
GCC 6.3 is being released, adjusting target milestone.
Comment 38 Richard Biener 2017-07-04 08:50:49 UTC
GCC 6.4 is being released, adjusting target milestone.