Re: [PATCH] warn for integer overflow in allocation calls (PR 96838)

[Martin Sebor <msebor@gmail.com>]

On 9/17/20 12:39 PM, Andrew MacLeod wrote:
> On 9/17/20 12:08 PM, Martin Sebor via Gcc-patches wrote:
>> On 9/16/20 9:23 PM, Jeff Law wrote:
>>>
>>> On 9/15/20 1:47 PM, Martin Sebor wrote:
>>>> Overflowing the size of a dynamic allocation (e.g., malloc or VLA)
>>>> can lead to a subsequent buffer overflow corrupting the heap or
>>>> stack.  The attached patch diagnoses a subset of these cases where
>>>> the overflow/wraparound is still detectable.
>>>>
>>>> Besides regtesting GCC on x86_64-linux I also verified the warning
>>>> doesn't introduce any false positives into Glibc or Binutils/GDB
>>>> builds on the same target.
>>>>
>>>> Martin
>>>>
>>>> gcc-96838.diff
>>>>
>>>> PR middle-end/96838 - missing warning on integer overflow in calls 
>>>> to allocation functions
>>>>
>>>> gcc/ChangeLog:
>>>>
>>>>     PR middle-end/96838
>>>>     * calls.c (eval_size_vflow): New function.
>>>>     (get_size_range): Call it.  Add argument.
>>>>     (maybe_warn_alloc_args_overflow): Diagnose overflow/wraparound.
>>>>     * calls.h (get_size_range): Add argument.
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>>
>>>>     PR middle-end/96838
>>>>     * gcc.dg/Walloc-size-larger-than-19.c: New test.
>>>>     * gcc.dg/Walloc-size-larger-than-20.c: New test.
>>>
>>> If an attacker can control an integer overflow that feeds an 
>>> allocation, then they can do all kinds of bad things.  In fact, when 
>>> my son was asking me attack vectors, this is one I said I'd look at 
>>> if I were a bad guy.
>>>
>>>
>>> I'm a bit surprised you can't just query the range of the argument 
>>> and get the overflow status out of that range, but I don't see that 
>>> in the APIs.  How painful would it be to make that part of the API? 
>>> The conceptual model would be to just ask for the range of the 
>>> argument to malloc which would include the range and a status bit 
>>> indicating the computation might have overflowed.
>>
>   Do we know if it did/would have wrapped? sure.  since we have to do 
> the math.    so you are correct in that the information is there. but is 
> it useful?
> 
> We are in the very annoying habit of subtracting one by adding 
> 0xFFFFFFF.  which means you get an overflow for unsigned when you 
> subtract one.   From what I have seen of unsigned math, we would be 
> flagging very many operations as overflows, so you would still have the 
> difficulty of figuring out whether its a "real" overflow or a fake one 
> because of the way we do unsigned math

You and me both :)

> 
> At the very start, I did have an overflow flag in the range class... but 
> it was turning out to be fairly useless so it was removed.
> .
> 
>> I agree that being able to evaluate an expression in an as-if
>> infinite precision (in addition to its type) would be helpful.
> 
> SO again, we get back to adding 0x0fffff when we are trying to subtract 
> one...  now, with infinite precision you are going to see
> 
>   [2,10]  - 1      we end up with [2,10]+0xFFFFFF, which will now give 
> you  [0x100000001, 0x100000009]    so its going to look like it overflowed?
> 
> 
> 
>> But just to make sure I understood correctly, let me ask again
>> using an example:
>>
>>   void* f (size_t n)
>>   {
>>     if (n < PTRDIFF_MAX / 2)
>>       n = PTRDIFF_MAX / 2;
>>
>>     return malloc (n * sizeof (int));
>>   }
>>
>> Can the unsigned wraparound in the argument be readily detected?
>>
>> On trunk, this ends up with the following:
>>
>>   # RANGE [4611686018427387903, 18446744073709551615]
>>   _6 = MAX_EXPR <n_2(D), 4611686018427387903>;
>>   # RANGE [0, 18446744073709551615] NONZERO 18446744073709551612
>>   _1 = _6 * 4;
>>   ...
>>   p_5 = mallocD.1206 (_1); [tail call]
>>   ...
>>   return p_5;
>>
>> so _1's range reflects the wraparound in size_t, but _6's range
>> has enough information to uncover it.  So detecting it is possible
>> and is done in the patch so we get a warning:
>>
>> warning: argument 1 range [18446744073709551612, 0x3fffffffffffffffc] 
>> is too large to represent in ‘long unsigned int’ 
>> [-Walloc-size-larger-than=]
>>     6 |   return malloc (n * sizeof (int));
>>       |          ^~~~~~~~~~~~~~~~~~~~~~~~~
>>
>> The code is very simplistic and only handles a small subset of cases.
>> It could be generalized and exposed by a more generic API but it does
>> seem like the ranger must already have all the logic built into it so
>> if it isn't exposed now it should be a matter of opening it up.
> 
> everything is exposed in range-ops.  well, mostly.
> if we have _1 = _6 * 4
> 
> if one wanted to do that infinite precision, you query the range for _6, 
> and the range for 4 (which would be [4,4] :-)
> range_of_expr (op1r, _6, stmt)
> range_of_expr (op2r, 4, stmt)
> 
> you could take their current types, and cast those ranges to whatever 
> the next higher precsion is,
> range_cast  (op1r, highertype)
> range_cast (op2r, highertype)
> then invoke the operation on those parameters
> 
> gimple_range_fold (r, stmt,  op1r, op2r)
> 
> and that will do your operation in the higher precision.  you could 
> compare that to the value in regular precision too i suppose.

The patch does pretty much exactly what you described, except in
offset_int, and only for a limited set of arithmetic operations.
It figures out if an unsigned expression wrapped simply by checking
to see if the mathematically correct result fits in its type.

It sounds like I should be able to use the range APIs above instead
and get the same result, but for arbitrary expressions.  I don't
need to (and very well can't) compare the infinitely precise result
to the regular result because when it's a range that wraps the result
is the full range of the type (i.e., [0, SIZE_MAX] in the test above).

> 
> The ranger is designed to track ranges as they are represented in the 
> IL.  You are asking for us to interpret the IL as something other than 
> what is there, and increase the precision.  Thats a different task.
> 
> could that be done?    maybe. It might involve parallel tracking of 
> ssa-Name ranges in a higher precision... and recalculating every 
> expression using those values.   Im not convinced that a generalized 
> ranger which works in higher precision is really going to solve the 
> problem the way you hope it would.. i think we'd get a lot of false info 
> when unsigned values are involved

I don't think that's necessary for unsigned wrapping.  Most of
the time the (possibly) wrapped result is what we need because
that's what the languages say is supposed to happen.  The cases
when we need to check for the dangerous wraparound (or overflow)
should be rare (just allocation calls) and can be handled on
demand by walking the IL and doing the computation in the infinite
precision.

For signed overflow, though, computing the mathematically correct
result seems preferable.  Or at least tracking (and propagating)
the overflow bit should be.  That way we could tell when
an expression is definitely invalid.

> 
> If I were to see a clear solution/description as to what is a 
> problematic overflow and what isnt, there might be something more 
> general that could be done...

Does the distinction above (unsigned wrapping/signed overflow) help?

> 
>> I mentioned it to Aldy in response to the irange best practices
>> document.  He says there's no way to do that and no plans to
>> make it possible.
>>
> Thats not quite what he said.   . He said  "If the operation may wrap or 
> overflow, it will show up as so in the range.  I don't think we have any 
> plans of changing this behavior."
> 
> In fact. looking back, he said the same thing I just did....  There IS a 
> mechanism there for working in higher precision should one desire to do 
> so, but as I pointed out above, Im not convinced as a general thing in 
> the ranger it will work how you imagine.
> 
> My guess is what you really want is to be invoking range-ops on stmts 
> you care about whether they might overflow or not with higher precision 
> versions and then identify the cases which trigger that you actually 
> care about.

Yes, it looks like that's the way to go.  I was hoping the ranger
had an API that would do all that for me (i.e., walk the IL and
compute the range of the result on demand in the precision of
my choice), since it has to do that as it is, except that it uses
the precision of the expression.  But if not, it sounds like with
range_ops I should be able to fairly easily write one myself.

> So maybe you want an "overflow calculator" which is similar to the 
> ranger, and  identifies which kinds of stmts expect certain range of 
> results, and if they get results outside of  the expected ranges, 
> triggers a flag.
> maybe it could convert all unsigned and signed  values to signed, and 
> then work in a higher precision,  and then if any intermediate result 
> cant be accurately cast back to the original type,  it gets flagged?  is 
> that the kind of overflow that is cared about?

There are two kinds of "overflow:" unsigned wrapping and signed
overflow.  Both are a problem in allocation calls like:

   int *p = malloc (nelts * size);

If nelts and size are signed, the compile-time result seems to
be done in saturation arithmetic (its range looks to be capped
at TYPE_MAX).  If they are unsigned, they wrap around zero.
Neither is usually intended by the user but the wraparound is
the more dangerous of the two because it's well-defined and
because it shrinks the size to a very small number.

> 
> I dont know... this isnt my space :-)       Im just telling you that I'm 
> not sure the current range query mechanism is the right place to be 
> asking if an "overflow" occurred because I think the general answer wont 
> be useful.. too many kinds of overflows thrown together.
> 
> I think this requires more specifoc detailed information, and maybe a 
> simple overflow analyzer will do the trick based on range-ops.... I 
> think range-ops has the required abilities.  whether it needs some 
> enhancing, or something else exposed,  I'm not sure yet

Thank you!  This was a useful clarification to what Aldy said.
I'd been meaning to follow up with him on this point when I was
done with what I'm working on but Jeff's question just got me
the answers I was looking for quicker.  Let me experiment with
range_ops and get back to you.

> 
> 
> Andrew
> 
> PS  One could always take a ranger and overload the range_of_stmt() 
> routine that calculates results, so that it calls current functionality, 
> then try converting the arguements to  higher precision ranges and 
> re-invoking range-ops on those arguments, get a new higher precision 
> range back and then look at the results vs the normal ones.  Might be a 
> place to start experimenting...   then pass a flag along sayign an 
> overflow occurred.

That sounds like something to look into.  I don't see range_of_stmt
on trunk.  Is that the right name or has it not been merged yet?

Thanks again.
Martin