[ubsan] Add VLA bound instrumentation

This patch adds the instrumentation of VLA bounds.  Basically, it just checks that
the size of a VLA is positive.  I.e., We also issue an error if the size of the
VLA is 0.  It catches e.g.

int i = 1;
int a[i][i - 2];

It is pretty straightforward, but I had
issues in the C++ FE, mainly choosing the right spot where to instrument...
Hopefully I picked up the right one.  Also note that in C++1y we throw
an exception when the size of a VLA is negative; hence no need to perform
the instrumentation if -std=c++1y is in effect.

Regtested/ran bootstrap-ubsan on x86_64-linux, also
make check -C gcc RUNTESTFLAGS='--target_board=unix\{-m32,-m64\} ubsan.exp'
passes.

Ok for trunk?

2013-09-12  Marek Polacek  <polacek@redhat.com>

	* opts.c (common_handle_option): Handle vla-bound.
	* sanitizer.def (BUILT_IN_UBSAN_HANDLE_VLA_BOUND_NOT_POSITIVE):
	Define.
	* ubsan.c (ubsan_type_descriptor): Handle IDENTIFIER_NODEs.
	* flag-types.h (enum sanitize_code): Add SANITIZE_VLA.
	* asan.c (initialize_sanitizer_builtins): Build BT_FN_VOID_PTR_PTR.

c-family/
	* c-ubsan.c: Don't include hash-table.h.
	(ubsan_instrument_vla): New function.
	* c-ubsan.h: Declare it.

cp/
	* decl.c (create_array_type_for_decl): Add VLA instrumentation.

c/
	* c-decl.c (grokdeclarator): Add VLA instrumentation.

testsuite/
	* g++.dg/ubsan/cxx1y-vla.C: New test.
	* c-c++-common/ubsan/vla-3.c: New test.
	* c-c++-common/ubsan/vla-2.c: New test.
	* c-c++-common/ubsan/vla-4.c: New test.
	* c-c++-common/ubsan/vla-1.c: New test.


	Marek

On Thu, Sep 12, 2013 at 02:26:55PM +0200, Marek Polacek wrote:
> the size of a VLA is positive.  I.e., We also issue an error if the size of the

s/We also/we/

On Thu, 12 Sep 2013, Marek Polacek wrote:

> This patch adds the instrumentation of VLA bounds.  Basically, it just 
> checks that the size of a VLA is positive.  I.e., We also issue an error 
> if the size of the VLA is 0.  It catches e.g.

This is not an objection to this patch, but there are a few other bits of 
VLA bound instrumentation that could be done as well.  If the size has a 
wide-enough type to be bigger than the target's SIZE_MAX, and is indeed 
bigger than SIZE_MAX, that could be detected at runtime as well.  Or if 
the multiplication of array size and element size exceeds SIZE_MAX (this 
covers both elements of constant size, and elements that are themselves 
VLAs, but the former can be handled more efficiently by comparing against 
an appropriate constant rather than needing a runtime test for whether a 
multiplication in size_t overflows).

(Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not 
just SIZE_MAX, should be caught, because pointer subtraction cannot work 
reliably with larger objects.  So it's not just when the size or 
multiplication overflow size_t, but when they overflow ptrdiff_t.)

On Thu, 12 Sep 2013, Joseph S. Myers wrote:

> (Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not 
> just SIZE_MAX, should be caught, because pointer subtraction cannot work 
> reliably with larger objects.  So it's not just when the size or 
> multiplication overflow size_t, but when they overflow ptrdiff_t.)

And, to add a bit more to the list of possible ubsan features (is this 
todo list maintained anywhere?), even if the size is such that operations 
on the array are in principle defined, it's possible that adjusting the 
stack pointer by too much may take it into other areas of memory and so 
cause stack overflow that doesn't get detected by the kernel.  So maybe 
ubsan should imply -fstack-check or similar.

Everything about VLA checking - checks on the size being positive and on 
it not being larger than PTRDIFF_MAX, and on avoiding stack overflow - 
applies equally to alloca: calls to alloca should also be instrumented.  
(But I think alloca (0) is valid.)

On Thu, Sep 12, 2013 at 03:52:18PM +0000, Joseph S. Myers wrote:
> On Thu, 12 Sep 2013, Marek Polacek wrote:
> 
> > This patch adds the instrumentation of VLA bounds.  Basically, it just 
> > checks that the size of a VLA is positive.  I.e., We also issue an error 
> > if the size of the VLA is 0.  It catches e.g.
> 
> This is not an objection to this patch, but there are a few other bits of 
> VLA bound instrumentation that could be done as well.  If the size has a 
> wide-enough type to be bigger than the target's SIZE_MAX, and is indeed 
> bigger than SIZE_MAX, that could be detected at runtime as well.  Or if 
> the multiplication of array size and element size exceeds SIZE_MAX (this 
> covers both elements of constant size, and elements that are themselves 
> VLAs, but the former can be handled more efficiently by comparing against 
> an appropriate constant rather than needing a runtime test for whether a 
> multiplication in size_t overflows).
> 
> (Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not 
> just SIZE_MAX, should be caught, because pointer subtraction cannot work 
> reliably with larger objects.  So it's not just when the size or 
> multiplication overflow size_t, but when they overflow ptrdiff_t.)

Yup, this all sounds good.  I'll look at this tomorrow.  I think I'd
prefer doing this as a follow-up, after the C/C++ FE parts are
reviewed; doing SIZE_MAX/PTRDIFF_MAX checking then should require
changes only in c-ubsan.c.

	Marek

On Thu, Sep 12, 2013 at 04:05:48PM +0000, Joseph S. Myers wrote:
> On Thu, 12 Sep 2013, Joseph S. Myers wrote:
> 
> > (Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not 
> > just SIZE_MAX, should be caught, because pointer subtraction cannot work 
> > reliably with larger objects.  So it's not just when the size or 
> > multiplication overflow size_t, but when they overflow ptrdiff_t.)
> 
> And, to add a bit more to the list of possible ubsan features (is this 
> todo list maintained anywhere?), even if the size is such that operations 

No, I don't have such a list (at least nothing online/public).

> on the array are in principle defined, it's possible that adjusting the 
> stack pointer by too much may take it into other areas of memory and so 
> cause stack overflow that doesn't get detected by the kernel.  So maybe 
> ubsan should imply -fstack-check or similar.

Works for me.

> Everything about VLA checking - checks on the size being positive and on 
> it not being larger than PTRDIFF_MAX, and on avoiding stack overflow - 
> applies equally to alloca: calls to alloca should also be instrumented.  
> (But I think alloca (0) is valid.)

Yes, good idea.  I've just checked and clang doesn't check the size
passed to alloca, I think it'd be good addition to have it.

And yeah - alloca (0) seems to be valid; when expanding
__builtin_alloca we call allocate_dynamic_stack_space and that
contains

  /* If we're asking for zero bytes, it doesn't matter what we point
     to since we can't dereference it.  But return a reasonable
     address anyway.  */
  if (size == const0_rtx)
    return virtual_stack_dynamic_rtx;

Thanks,

	Marek

On Thu, Sep 12, 2013 at 04:05:48PM +0000, Joseph S. Myers wrote:
> cause stack overflow that doesn't get detected by the kernel.  So maybe 
> ubsan should imply -fstack-check or similar.

Well, I have a patch for that, but I no longer think that ubsan should
imply -fstack-check, since e.g. 

int
main (void)
{
  int x = -1;
  int b[x - 4];
  /* ... */
  return 0;
}

segfaults at runtime on int b[x - 4]; line when -fstack-check is used
(even without sanitizing), so we wouldn't give proper diagnostics
for stmts following that line...

	Marek

> Well, I have a patch for that, but I no longer think that ubsan should
> imply -fstack-check, since e.g.
> 
> int
> main (void)
> {
>   int x = -1;
>   int b[x - 4];
>   /* ... */
>   return 0;
> }
> 
> segfaults at runtime on int b[x - 4]; line when -fstack-check is used
> (even without sanitizing), so we wouldn't give proper diagnostics
> for stmts following that line...

In Ada we catch the sigsegv, turn it into an exception and unwind.

On Fri, 13 Sep 2013, Marek Polacek wrote:

> On Thu, Sep 12, 2013 at 04:05:48PM +0000, Joseph S. Myers wrote:
> > cause stack overflow that doesn't get detected by the kernel.  So maybe 
> > ubsan should imply -fstack-check or similar.
> 
> Well, I have a patch for that, but I no longer think that ubsan should
> imply -fstack-check, since e.g. 
> 
> int
> main (void)
> {
>   int x = -1;
>   int b[x - 4];
>   /* ... */
>   return 0;
> }
> 
> segfaults at runtime on int b[x - 4]; line when -fstack-check is used
> (even without sanitizing), so we wouldn't give proper diagnostics
> for stmts following that line...

A guaranteed segfault is better than doing something undefined.  But I'd 
expect sanitizing to make the initial check that the array size in bytes 
is in the range [1, PTRDIFF_MAX] and -fstack-check only to come into play 
if that passes (for sizes that are too large for the stack limit in effect 
at runtime although within the range that is in principle valid).  You 
probably don't want to enable -fstack-check from ubsan until the checks 
for the range [1, PTRDIFF_MAX] are in place.

(Those checks, incidentally, would need to apply not just to arrays whose 
specified size is variable, but also to constant-size arrays of 
variable-size arrays - if you have a VLA type, then define an array 
VLA array[10]; then you need to check that the result of the 
multiplication of sizes in bytes doesn't exceed PTRDIFF_MAX.  So the more 
general checks can't all go in the place where you're inserting the checks 
for a single variable size in isolation.)

On Thu, Sep 12, 2013 at 04:05:48PM +0000, Joseph S. Myers wrote:
> On Thu, 12 Sep 2013, Joseph S. Myers wrote:
> 
> > (Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not 
> > just SIZE_MAX, should be caught, because pointer subtraction cannot work 
> > reliably with larger objects.  So it's not just when the size or 
> > multiplication overflow size_t, but when they overflow ptrdiff_t.)
> 
> And, to add a bit more to the list of possible ubsan features (is this 
> todo list maintained anywhere?), even if the size is such that operations 
> on the array are in principle defined, it's possible that adjusting the 
> stack pointer by too much may take it into other areas of memory and so 
> cause stack overflow that doesn't get detected by the kernel.  So maybe 
> ubsan should imply -fstack-check or similar.
> 
> Everything about VLA checking - checks on the size being positive and on 
> it not being larger than PTRDIFF_MAX, and on avoiding stack overflow - 
> applies equally to alloca: calls to alloca should also be instrumented.  
> (But I think alloca (0) is valid.)

Problem here is that libubsan doesn't contain appropriate routines for
this VLA/alloca extended checking, it really can only issue "variable
length array bound evaluates to non-positive value", nothing else.

So perhaps reach out to some clang mailing list and try to implement
it first in the libubsan...

	Marek

On 09/12/2013 06:05 PM, Joseph S. Myers wrote:
> On Thu, 12 Sep 2013, Joseph S. Myers wrote:
>
>> (Actually, I believe sizes (in bytes) greater than target PTRDIFF_MAX, not
>> just SIZE_MAX, should be caught, because pointer subtraction cannot work
>> reliably with larger objects.  So it's not just when the size or
>> multiplication overflow size_t, but when they overflow ptrdiff_t.)
>
> And, to add a bit more to the list of possible ubsan features (is this
> todo list maintained anywhere?), even if the size is such that operations
> on the array are in principle defined, it's possible that adjusting the
> stack pointer by too much may take it into other areas of memory and so
> cause stack overflow that doesn't get detected by the kernel.  So maybe
> ubsan should imply -fstack-check or similar.

I have on my to-do list to make -fstack-check production-ready, by 
avoiding unnecessary instrumentation.  My initial experiments weren't 
too successful, but I think it should be possible to greatly reduce its 
overhead.  If everything else fails, the idea is to reuse the Go split 
stack limit and check against that.

The idea is that this would eventually be enabled in production code, 
much like -fstack-protector.

I'm quite busy with other work at the moment, and a patch from me is 
probably months away, though. :-(