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 handling. 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 function." 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. regards, 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
