Powered by Linux
Re: Can smatch detect this bug? — Semantic Matching Tool

Re: Can smatch detect this bug?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


I've CC'd the Smatch list.  I hope you don't mind.

On Thu, Aug 24, 2017 at 02:24:13PM -0700, Luis R. Rodriguez wrote:
> https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
> BTW lib/bsearch.c is not affected. It seems to carry the more advanced
> fast method, and the original code which added the library for it is
> fine:
>                size_t mid = start + (end - start) / 2;
> The bug would be if we had something like:
>  int mid =(low + high) / 2;
> Coccinelle definitely can't be used to find the bug given this would
> require context of the fact that both low and high are part of a given
> shared range. Unless of course we just treat any type of operation as
> dangerous without any context at all.
> Julia seems to believe smatch might be able to detect the bug though
> since it seems to have representation of values. Thoughts?
>  Luis

I've looked at detecting integer overflows but I haven't published any
of my work yet.  There are several problems.

First, Smatch can't really parse that code properly because it doesn't
handle loops right.  There is the --two-passes option which should work
in theory, but in real life is very buggy.  The --two-passes option is
also too slow.  I'm on a quad core system now, but I'm hoping to get a
16 core system maybe by the end of the year so I can fix up loop

The other problem is it's just very tricky to detect integer overflows
without false positives.  You have to know the value of every single
variable.  Even if you tracked 95% of all variables that would
still be too many untracked variables and false positives to manage.

One way around this is we could only warn if we knew the variables that
come from the user.  Even this generates too many warnings which are
true instances of integer overflows but we just don't care.  A typical
example is that the user is allowed to set a timeout to any value so we
take the user's value and multiply by the number of seconds in a minute
or whatever.  No one cares if the user picks a bad value and suffers the
consequences.  So then you further limit the warnings to "the value must
come from the user and then we pass it as the size to an allocation

Also tracking the values is not enough, you have to track relationships
between two variables because you have code like:

	if (a + b < a)
		return -EINVAL;
	c = a + b;

We don't know the limits on either a or b but we know they can't
overflow.  I've got a couple approaches in mind for dealing with this,
but looking at it now, my code here is really incomplete.  Anyway, my
idea is to detect the condition and just mark "a" and "b" as checked
against integer overflows and not complain when you do any arithmatic
with them.  That's not an especially good assumption because integer
overflow checks are bug prone.

Another idea which I just had now is that I could re-write the condition
in smatch_extra.c so we'd record that "a + b" is in the 0-u32max range.
Smatch sometimes records the value of simple math, not just tracking
individual variables.  That information is lost at the function boundary
though, it's not stored in the cross function DB.

dan carpenter
To unsubscribe from this list: send the line "unsubscribe smatch" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[Index of Archives]     [Linux USB Devel]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]     [Big List of Linux Books]

  Powered by Linux