[RFC] UBSan unsafely uses VRP

[RFC] UBSan unsafely uses VRP

[Marat Zakirov]

[-- Attachment #1: Type: text/plain, Size: 1770 bytes --]

Hi all!

I found that UBSan uses vrp pass to optimize generated checks. Keeping 
in mind that vrp pass is about performance not stability I found example 
where UBSan may skip true positive.

Example came from spec2006 perlbench:

int ext;

int
Perl_do_sv_dump()
{
     int freq[10];
     int i;
     int max = 0;
     int t = INT_MAX - 20;

     if (max < ext)
       max = ext;

     for (i = 0; i <= max; i++)
         if (freq[i])
           ext = 0;

     t += i;  <<< (*)
     return t;
}

vrp pass here sets vrp('i') to [0..10] in assumption that 'freq[i]' wont 
violate array bound (vrp uses loop iteration number calculation, see 
adjust_range_with_scev in tree-vrp.c). This means that UBSAN_CHECK_ADD 
build for (*) should be deleted as redundant (and actually it is deleted 
by vrp pass). So if at the execution max = 30, freq[5] != 0 uncaught 
overflow will occur.

There are also some unsafe code in functions 
ubsan_expand_si_overflow_addsub_check, 
ubsan_expand_si_overflow_mul_check which uses get_range_info to reduce 
checks number. As seen before vrp usage for sanitizers may decrease 
quality of error detection.

Potentially unsafe vrp decisions should preferably not be exploited by 
any sanitizer pass. I have several ideas how we could achieve that:
1) Do not use vrp info for sanitizers.
2) Do not use unsafe conclusions during vrp pass if sanitizers are enabled.
3) Make two versions of value range data safe and unsafe.

P.S.

To reproduce the issue use appropriate GCC options 
(-fsanitize=signed-integer-overflow -S -O3) and attached trivial patch 
which disables UBSan check build in inner loops. This patch is needed 
because currently iteration number calculation used by vrp pass do not 
supports yet UBSAN_CHECK_[ADD/SUB/MUL].

--Marat

[-- Attachment #2: ubsan.diff --]
[-- Type: text/x-patch, Size: 412 bytes --]

diff --git a/gcc/ubsan.c b/gcc/ubsan.c
index dde0418..97dbf33 100644
--- a/gcc/ubsan.c
+++ b/gcc/ubsan.c
@@ -1014,6 +1014,10 @@ instrument_si_overflow (gimple_stmt_iterator gsi)
       || GET_MODE_BITSIZE (TYPE_MODE (lhstype)) != TYPE_PRECISION (lhstype))
     return;
 
+  // skip for inner loops 
+  if (gimple_bb(stmt)->loop_father->inner == NULL)
+    return;
+
   switch (code)
     {
     case MINUS_EXPR:

Re: [RFC] UBSan unsafely uses VRP

[Jakub Jelinek]

On Tue, Nov 11, 2014 at 05:02:55PM +0300, Marat Zakirov wrote:
> I found that UBSan uses vrp pass to optimize generated checks. Keeping in
> mind that vrp pass is about performance not stability I found example where
> UBSan may skip true positive.
> 
> Example came from spec2006 perlbench:
> 
> int ext;
> 
> int
> Perl_do_sv_dump()
> {
>     int freq[10];
>     int i;
>     int max = 0;
>     int t = INT_MAX - 20;
> 
>     if (max < ext)
>       max = ext;
> 
>     for (i = 0; i <= max; i++)
>         if (freq[i])
>           ext = 0;
> 
>     t += i;  <<< (*)
>     return t;
> }
> 
> vrp pass here sets vrp('i') to [0..10] in assumption that 'freq[i]' wont
> violate array bound (vrp uses loop iteration number calculation, see
> adjust_range_with_scev in tree-vrp.c). This means that UBSAN_CHECK_ADD build
> for (*) should be deleted as redundant (and actually it is deleted by vrp
> pass). So if at the execution max = 30, freq[5] != 0 uncaught overflow will
> occur.

Well, if max is >= 10, then you should get -fsanitize=bounds error already.
-fsanitize=undefined already disables -faggressive-loop-optimizations,
perhaps it can also disable other optimizations (I thought deriving number
of iterations from assuming undefined behavior doesn't occur in loop stmts
is already guarded by -faggressive-loop-optimizations though).

> There are also some unsafe code in functions
> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
> which uses get_range_info to reduce checks number. As seen before vrp usage
> for sanitizers may decrease quality of error detection.

Using VRP is completely intentional there, we don't want to generate too
slow code if you decide you want to optimize your code (for -O0 VRP isn't
performed of course).

	Jakub

Re: [RFC] UBSan unsafely uses VRP

[Richard Biener]

On Tue, Nov 11, 2014 at 3:15 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Tue, Nov 11, 2014 at 05:02:55PM +0300, Marat Zakirov wrote:
>> I found that UBSan uses vrp pass to optimize generated checks. Keeping in
>> mind that vrp pass is about performance not stability I found example where
>> UBSan may skip true positive.
>>
>> Example came from spec2006 perlbench:
>>
>> int ext;
>>
>> int
>> Perl_do_sv_dump()
>> {
>>     int freq[10];
>>     int i;
>>     int max = 0;
>>     int t = INT_MAX - 20;
>>
>>     if (max < ext)
>>       max = ext;
>>
>>     for (i = 0; i <= max; i++)
>>         if (freq[i])
>>           ext = 0;
>>
>>     t += i;  <<< (*)
>>     return t;
>> }
>>
>> vrp pass here sets vrp('i') to [0..10] in assumption that 'freq[i]' wont
>> violate array bound (vrp uses loop iteration number calculation, see
>> adjust_range_with_scev in tree-vrp.c). This means that UBSAN_CHECK_ADD build
>> for (*) should be deleted as redundant (and actually it is deleted by vrp
>> pass). So if at the execution max = 30, freq[5] != 0 uncaught overflow will
>> occur.
>
> Well, if max is >= 10, then you should get -fsanitize=bounds error already.
> -fsanitize=undefined already disables -faggressive-loop-optimizations,
> perhaps it can also disable other optimizations (I thought deriving number
> of iterations from assuming undefined behavior doesn't occur in loop stmts
> is already guarded by -faggressive-loop-optimizations though).

You could use -fno-strict-overflow ...

>> There are also some unsafe code in functions
>> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
>> which uses get_range_info to reduce checks number. As seen before vrp usage
>> for sanitizers may decrease quality of error detection.
>
> Using VRP is completely intentional there, we don't want to generate too
> slow code if you decide you want to optimize your code (for -O0 VRP isn't
> performed of course).

Indeed.  Note that the strict-overflow warnings are already a bad burden
on VRP quality - a way out to me was always to track two lattices,
one assuming strict-overflow and one assuming wrapping overflow.
For strict-overflow warnings you then can compare simplification outcome
against two lattices and warn if the result differs.  Instead of that odd
+-INF(OVF) saturation.

Richard.

>         Jakub

Re: [RFC] UBSan unsafely uses VRP

[Marat Zakirov]

On 11/11/2014 05:26 PM, Richard Biener wrote:
> On Tue, Nov 11, 2014 at 3:15 PM, Jakub Jelinek <jakub@redhat.com> wrote:
>> On Tue, Nov 11, 2014 at 05:02:55PM +0300, Marat Zakirov wrote:
>>> I found that UBSan uses vrp pass to optimize generated checks. Keeping in
>>> mind that vrp pass is about performance not stability I found example where
>>> UBSan may skip true positive.
>>>
>>> Example came from spec2006 perlbench:
>>>
>>> int ext;
>>>
>>> int
>>> Perl_do_sv_dump()
>>> {
>>>      int freq[10];
>>>      int i;
>>>      int max = 0;
>>>      int t = INT_MAX - 20;
>>>
>>>      if (max < ext)
>>>        max = ext;
>>>
>>>      for (i = 0; i <= max; i++)
>>>          if (freq[i])
>>>            ext = 0;
>>>
>>>      t += i;  <<< (*)
>>>      return t;
>>> }
>>>
>>> vrp pass here sets vrp('i') to [0..10] in assumption that 'freq[i]' wont
>>> violate array bound (vrp uses loop iteration number calculation, see
>>> adjust_range_with_scev in tree-vrp.c). This means that UBSAN_CHECK_ADD build
>>> for (*) should be deleted as redundant (and actually it is deleted by vrp
>>> pass). So if at the execution max = 30, freq[5] != 0 uncaught overflow will
>>> occur.
>> Well, if max is >= 10, then you should get -fsanitize=bounds error already.
>> -fsanitize=undefined already disables -faggressive-loop-optimizations,
>> perhaps it can also disable other optimizations (I thought deriving number
>> of iterations from assuming undefined behavior doesn't occur in loop stmts
>> is already guarded by -faggressive-loop-optimizations though).
> You could use -fno-strict-overflow ...
>
>>> There are also some unsafe code in functions
>>> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
>>> which uses get_range_info to reduce checks number. As seen before vrp usage
>>> for sanitizers may decrease quality of error detection.
>> Using VRP is completely intentional there, we don't want to generate too
>> slow code if you decide you want to optimize your code (for -O0 VRP isn't
>> performed of course).
> Indeed.  Note that the strict-overflow warnings are already a bad burden
> on VRP quality - a way out to me was always to track two lattices,
> one assuming strict-overflow and one assuming wrapping overflow.
> For strict-overflow warnings you then can compare simplification outcome
> against two lattices and warn if the result differs.  Instead of that odd
> +-INF(OVF) saturation.
>
> Richard.
>
>>          Jakub
>>
It is seems that -fsanitize=something do not set 
flag_aggressive_loop_optimizations to 0 in current GCC version. I made a 
watchpoint on it but changes after init_options_struct weren't found. I 
will make fix for both 
flag_aggressive_loop_optimizationsno-strict-overflow and 
flag_strict_overflow.

--Marat

Re: [RFC] UBSan unsafely uses VRP

[Jakub Jelinek]

On Tue, Nov 11, 2014 at 07:12:55PM +0300, Marat Zakirov wrote:
> It is seems that -fsanitize=something do not set
> flag_aggressive_loop_optimizations to 0 in current GCC version. I made a
> watchpoint on it but changes after init_options_struct weren't found. I will
> make fix for both flag_aggressive_loop_optimizationsno-strict-overflow and
> flag_strict_overflow.

Ah, you're right, we only have:
        /* When instrumenting the pointers, we don't want to remove
           the null pointer checks.  */
        if (opts->x_flag_sanitize & (SANITIZE_NULL | SANITIZE_NONNULL_ATTRIBUTE
                                     | SANITIZE_RETURNS_NONNULL_ATTRIBUTE))
          opts->x_flag_delete_null_pointer_checks = 0;
and as Joseph said, even that is misplaced, it should be done after all
options are processed, so that it isn't dependent on whether
-fsanitize=undefined or
--fdelete-null-pointer-checks/-faggressive-loop-optimizations come first.

	Jakub

Re: [RFC] UBSan unsafely uses VRP

[Yury Gribov]

On 11/11/2014 05:15 PM, Jakub Jelinek wrote:
>> There are also some unsafe code in functions
>> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
>> which uses get_range_info to reduce checks number. As seen before vrp usage
>> for sanitizers may decrease quality of error detection.
>
> Using VRP is completely intentional there, we don't want to generate too
> slow code if you decide you want to optimize your code (for -O0 VRP isn't
> performed of course).

On the other hand detection quality is probably more important than 
important regardless of optimization level. When I use a checker, I 
don't want it to miss bugs due to overly aggressive optimization.

I wish we had some test to check that sanitizer optimizations are indeed 
conservative.

-Y

Re: [RFC] UBSan unsafely uses VRP

[Marek Polacek]

On Wed, Nov 12, 2014 at 11:42:39AM +0300, Yury Gribov wrote:
> On 11/11/2014 05:15 PM, Jakub Jelinek wrote:
> >>There are also some unsafe code in functions
> >>ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
> >>which uses get_range_info to reduce checks number. As seen before vrp usage
> >>for sanitizers may decrease quality of error detection.
> >
> >Using VRP is completely intentional there, we don't want to generate too
> >slow code if you decide you want to optimize your code (for -O0 VRP isn't
> >performed of course).
> 
> On the other hand detection quality is probably more important than
> important regardless of optimization level. When I use a checker, I don't
> want it to miss bugs due to overly aggressive optimization.
 
Yes, but as said above, VRP is only run with >-O2 and -Os.

> I wish we had some test to check that sanitizer optimizations are indeed
> conservative.

I think most of the tests we have are tested with various optimization
levels.

	Marek

Re: [RFC] UBSan unsafely uses VRP

[Yury Gribov]

On 11/12/2014 11:45 AM, Marek Polacek wrote:
> On Wed, Nov 12, 2014 at 11:42:39AM +0300, Yury Gribov wrote:
>> On 11/11/2014 05:15 PM, Jakub Jelinek wrote:
>>>> There are also some unsafe code in functions
>>>> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
>>>> which uses get_range_info to reduce checks number. As seen before vrp usage
>>>> for sanitizers may decrease quality of error detection.
>>>
>>> Using VRP is completely intentional there, we don't want to generate too
>>> slow code if you decide you want to optimize your code (for -O0 VRP isn't
>>> performed of course).
>>
>> On the other hand detection quality is probably more important than
>> important regardless of optimization level. When I use a checker, I don't
>> want it to miss bugs due to overly aggressive optimization.
>
> Yes, but as said above, VRP is only run with >-O2 and -Os.

Hm, I must be missing something.  99% of users will only run their code 
under -O2 because it'll be too slow otherwise.  Why should we penalize 
them for this by lowering analysis quality?  Isn't error detection the 
main goal of sanitizers (performance being the secondary at best)?

>> I wish we had some test to check that sanitizer optimizations are indeed
>> conservative.
>
> I think most of the tests we have are tested with various optimization
> levels.

Existing tests are really a joke when we consider interblock 
optimization.  Most don't even contain any non-trivial control flow.

-Y

Re: [RFC] UBSan unsafely uses VRP

[Marat Zakirov]

On 11/12/2014 11:45 AM, Marek Polacek wrote:
> Yes, but as said above, VRP is only run with >-O2 and -Os.
You meant >= -O2?

--Marat

Re: [RFC] UBSan unsafely uses VRP

[Marek Polacek]

On Wed, Nov 12, 2014 at 01:04:58PM +0300, Marat Zakirov wrote:
> 
> On 11/12/2014 11:45 AM, Marek Polacek wrote:
> >Yes, but as said above, VRP is only run with >-O2 and -Os.
> You meant >= -O2?

Yes.

	Marek

Re: [RFC] UBSan unsafely uses VRP

[Jakub Jelinek]

On Wed, Nov 12, 2014 at 12:58:37PM +0300, Yury Gribov wrote:
> On 11/12/2014 11:45 AM, Marek Polacek wrote:
> >On Wed, Nov 12, 2014 at 11:42:39AM +0300, Yury Gribov wrote:
> >>On 11/11/2014 05:15 PM, Jakub Jelinek wrote:
> >>>>There are also some unsafe code in functions
> >>>>ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
> >>>>which uses get_range_info to reduce checks number. As seen before vrp usage
> >>>>for sanitizers may decrease quality of error detection.
> >>>
> >>>Using VRP is completely intentional there, we don't want to generate too
> >>>slow code if you decide you want to optimize your code (for -O0 VRP isn't
> >>>performed of course).
> >>
> >>On the other hand detection quality is probably more important than
> >>important regardless of optimization level. When I use a checker, I don't
> >>want it to miss bugs due to overly aggressive optimization.
> >
> >Yes, but as said above, VRP is only run with >-O2 and -Os.
> 
> Hm, I must be missing something.  99% of users will only run their code
> under -O2 because it'll be too slow otherwise.  Why should we penalize them
> for this by lowering analysis quality?  Isn't error detection the main goal
> of sanitizers (performance being the secondary at best)?

But, if -O0 isn't too slow for them, having unnecessary bloat even at -O2
is bad the same.  But not using VRP at all, you are giving up all the cases
where you know something won't overflow because you e.g. sign extend
or zero extend from some smaller type, sum op such values, and something
with constant, or you can use a cheaper code to multiply etc.
Turning off -faggressive-loop-optimizations is certainly the right thing for
-fsanitize=undefined (any undefined I'd say), so are perhaps selected other
optimizations.

	Jakub

Re: [RFC] UBSan unsafely uses VRP

[Yury Gribov]

On 11/12/2014 04:26 PM, Jakub Jelinek wrote:
> But, if -O0 isn't too slow for them, having unnecessary bloat even at -O2
> is bad the same.  But not using VRP at all, you are giving up all the cases
> where you know something won't overflow because you e.g. sign extend
> or zero extend from some smaller type, sum op such values, and something
> with constant, or you can use a cheaper code to multiply etc.

Sure, I was not suggesting anything like that - just pointing out that 
we must be careful about potential loss of precision and do all we can 
to avoid it.  Faster code should not justify lower quality (as used to 
be in 1960-s).

> Turning off -faggressive-loop-optimizations is certainly the right thing for
> -fsanitize=undefined (any undefined I'd say), so are perhaps selected other
> optimizations.

Totally agree.

-Y

Re: [RFC] UBSan unsafely uses VRP

[Yury Gribov]

On 11/12/2014 04:26 PM, Jakub Jelinek wrote:
> On Wed, Nov 12, 2014 at 12:58:37PM +0300, Yury Gribov wrote:
>> On 11/12/2014 11:45 AM, Marek Polacek wrote:
>>> On Wed, Nov 12, 2014 at 11:42:39AM +0300, Yury Gribov wrote:
>>>> On 11/11/2014 05:15 PM, Jakub Jelinek wrote:
>>>>>> There are also some unsafe code in functions
>>>>>> ubsan_expand_si_overflow_addsub_check, ubsan_expand_si_overflow_mul_check
>>>>>> which uses get_range_info to reduce checks number. As seen before vrp usage
>>>>>> for sanitizers may decrease quality of error detection.
>>>>>
>>>>> Using VRP is completely intentional there, we don't want to generate too
>>>>> slow code if you decide you want to optimize your code (for -O0 VRP isn't
>>>>> performed of course).
>>>>
>>>> On the other hand detection quality is probably more important than
>>>> important regardless of optimization level. When I use a checker, I don't
>>>> want it to miss bugs due to overly aggressive optimization.
>>>
>>> Yes, but as said above, VRP is only run with >-O2 and -Os.
>>
>> Hm, I must be missing something.  99% of users will only run their code
>> under -O2 because it'll be too slow otherwise.  Why should we penalize them
>> for this by lowering analysis quality?  Isn't error detection the main goal
>> of sanitizers (performance being the secondary at best)?
>
> But, if -O0 isn't too slow for them, having unnecessary bloat even at -O2
> is bad the same.  But not using VRP at all, you are giving up all the cases
> where you know something won't overflow because you e.g. sign extend
> or zero extend from some smaller type, sum op such values, and something
> with constant, or you can use a cheaper code to multiply etc.
> Turning off -faggressive-loop-optimizations is certainly the right thing for
> -fsanitize=undefined (any undefined I'd say), so are perhaps selected other
> optimizations.
>
> 	Jakub
>