4 ms·

Is that really a thing? That sounds almost as illogical as saying 'good programmers don't write bugs'. Should be more like 'good programmers are aware of undefi

by stinos 10y ago

Is that really a thing? That sounds almost as illogical as saying 'good programmers don't write bugs'. Should be more like 'good programmers are aware of undefined behaviour and try to not invoke it' or so.

jcranmer 10y ago
Yes, it totally is a thing, although it's usually described more as "C(++)'s undefined behavior isn't a problem because any good programmer should be able to easily avoid it"--a sentiment that I have seen (and challenged) on Hacker News a fair amount. The contention that I (and the authors) have is that integer overflows are so pervasive that it's not practicable to expect that even good developers are capable of avoiding them. Some things to really emphasize here: 1. This study found 47% of packages tested exhibited undefined integer overflow on their test suite. This isn't using fuzz testing or anything to try to find corner cases to make overflow far more likely, this is more or less "opening the application triggered undefined behavior"-level pervasiveness. 2. The study also looks at unsigned integer overflow, which is well-defined but often no less problematic. The classic example I'll give is the calloc bug--calloc takes two arguments and multiplies them to find the size to allocate, and virtually every time that I've seen this function implemented, an exploitable CVE can be found (when the multiplication overflows). 3. The prelude to this work (that produced the IOC, and, ultimately, Clang's UBSAN) is what really woke the community up to the problem. It actually did prompt the C and C++ specifications to make changes (INT_MIN % -1 is now considered UB, and C++, but not C, makes 1 << 31 == INT_MIN defined behavior). Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits. My personal opinion is that the treat integers as ℤ_{2³²} model is no longer a good idea as the default integer model, and we need to start looking at bringing back models like big integer (à la Python), saturating, or explicit trapping models (à la Ada); I was quite disappointed when Rust opted to keep the wraparound model.
- pcwalton 10y ago
  > Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits What fraction of integer overflow exploits crucially have to be combined with an unsafe memory model in order to be weaponizable? I suspect the number is close to 99%. (I know there are a handful of overflow-related security problems that are independent of memory safety--someone mentioned money overflow issues in online games when this topic came up last--but they are few and far between.) > I was quite disappointed when Rust opted to keep the wraparound model. That's oversimplified. In debug builds, Rust panics on overflow; in release builds, Rust may or may not panic. It doesn't right now out of performance considerations. That is not a decision that is set in stone if the performance becomes acceptable in the future.
  - marvy 10y ago
    This means that Rust has experience with wraparound and with panics. So this question should be answerable by someone on the Rust team: how much does the check cost? A few percent? A factor of 2? Surely not more than that?
    - pcwalton 10y ago
      Depends. The problem is not so much the overhead of the check itself as that it introduces a lot of control flow edges which interfere with optimizations. For example, on x86 you can kiss most uses of LEA goodbye...
      - marvy 10y ago
        Sure, but when all is said and done, what's the cost? There are plenty of Rust benchmarks by now, possibly some of them are part of the test suite. How much do they slow down?
  - wofo 10y ago
    Note that it is possible to enable overflow checking in release builds as well.
- Asooka 10y ago
  AFAIK the case for undefined integer overflow is optimisations regarding loop termination, carry bit handling, and usage of 64-bit vs 32-bit registers. In light of that can't we say that "The compiler may perform signed integer arithmetic using registers larger than the type's bits and truncate the result when writing to memory"? So e.g. int a = INT_MAX; int b = INT_MAX; int c = a + b; c > a; // true on 64 bit iff c was NOT written to memory (so -O1 and above); false on 32 bit (c&0x7fffffff) > a; // false always // i.e. you can always test if two positive values overflow with ((a+b)&0x7f..f)>a Another idea I haven't seen used enough is to put values in 64-bit doubles, do your arithmetic that way and check if the final value fits in your integer type. As long as you restrict yourself to adding, subtracting and multiplying you'll get an exact result back (ok unless you run on a buggy pentium from over 25 years ago, but I think all those were recalled). A problem you have to watch out for is if you've entered the range where your ulp is larger than 1 and your math gets inexact.
  - ArkyBeagle 10y ago
    I use float/double float values A Lot these days for arithmetic. So that reduces integer use to values read over a comms line or read otherwise from hardware. Of course, floats have their own quantum of grief.
  - nayuki 10y ago
    > Asooka wrote: // i.e. you can always test if two positive values overflow with ((a + b) & 0x7F..F) > a This is bad advice. The act of computing (a + b) is undefined behavior. Masking it afterward will not save you against a strict compiler that exploits (or traps) all undefined behaviors.
    - nkurz 10y ago
      I think the 'Asooka' is aware of this, and was not offering advice. Rather, he was proposing that the world would be simpler if the specs were changed so that signed addition never resulted in undefined behavior. In this simpler counterfactual world, his test would work. In our current easier to optimize world, it would not.
- ArkyBeagle 10y ago
  > Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits. Indeed. Progress! :) I think you may be right about Z_{2^32} but 'C' is hopelessly wedded to it. As practice, it might even be worth having separate types for things on that ring and things expected to not be on that ring. Whether tools to automatically check it exist or not, this at least moves it to be easier to inspect for.
  - burfog 10y ago
    Rust should have forced you to specify behavior whenever the compiler can't prove that the difference doesn't matter, like so: 1. default - fail the compile if an overflow could happen 2. wrap - like gcc's -fwrapv option, and C's unsigned type 3. trap - like gcc's -ftrapv option 4. saturate - common DSP behavior 5. unsafe - like gcc's C signed integer cruelty (fastest code) Eh, is it too late to add this? For compatibility with old code, there could be a compiler option to override the default behavior for a whole source file.
    - the_why_of_y 10y ago
      You're right, there does not appear to be a way to achieve 1. Rust arithmetic does 3. in debug builds, or something vaguely similar if requested by using the checked_* functions, and 2. in release builds, or if requested by using the wrapping_* functions, and 4. by using the saturating_* functions. Recommended reading: http://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/ http://huonw.github.io/blog/2016/04/myths-and-legends-about-...
- posterboy 10y ago
  > big integer If that's your use case, use it. Libraries like GMPrecision exist. Doesn't make a difference for one by off errors, e.g.
pcwalton 10y ago
Yes, it is. I've made a small HN career of countering this meme whenever it comes up :) It's a classic form of no-true-Scotsman, but very popular.
- posterboy 10y ago
  If it's a fallacy, why wouldn't a programmer do good to avoid UB?
  - nkurz 10y ago
    Avoiding undefined behavior is good, and a good programmer tries to avoid undefined behavior. The fallacy is that there exists a population of C and C++ programmers who are skilled enough to always recognize and avoid undefined behavior. While you could define "a good programmer" as one who always recognizes and avoids undefined behavior, the unhelpful result would be concluding that very few good C or C++ programmers exist, possibly none.
    - posterboy 10y ago
      By modus tollens, C can't be a good language, then. Gosh!

by stinos 10y ago

jcranmer 10y ago

Yes, it totally is a thing, although it's usually described more as "C(++)'s undefined behavior isn't a problem because any good programmer should be able to easily avoid it"--a sentiment that I have seen (and challenged) on Hacker News a fair amount. The contention that I (and the authors) have is that integer overflows are so pervasive that it's not practicable to expect that even good developers are capable of avoiding them. Some things to really emphasize here: 1. This study found 47% of packages tested exhibited undefined integer overflow on their test suite. This isn't using fuzz testing or anything to try to find corner cases to make overflow far more likely, this is more or less "opening the application triggered undefined behavior"-level pervasiveness. 2. The study also looks at unsigned integer overflow, which is well-defined but often no less problematic. The classic example I'll give is the calloc bug--calloc takes two arguments and multiplies them to find the size to allocate, and virtually every time that I've seen this function implemented, an exploitable CVE can be found (when the multiplication overflows). 3. The prelude to this work (that produced the IOC, and, ultimately, Clang's UBSAN) is what really woke the community up to the problem. It actually did prompt the C and C++ specifications to make changes (INT_MIN % -1 is now considered UB, and C++, but not C, makes 1 << 31 == INT_MIN defined behavior). Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits. My personal opinion is that the treat integers as ℤ_{2³²} model is no longer a good idea as the default integer model, and we need to start looking at bringing back models like big integer (à la Python), saturating, or explicit trapping models (à la Ada); I was quite disappointed when Rust opted to keep the wraparound model.

pcwalton 10y ago
> Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits What fraction of integer overflow exploits crucially have to be combined with an unsafe memory model in order to be weaponizable? I suspect the number is close to 99%. (I know there are a handful of overflow-related security problems that are independent of memory safety--someone mentioned money overflow issues in online games when this topic came up last--but they are few and far between.) > I was quite disappointed when Rust opted to keep the wraparound model. That's oversimplified. In debug builds, Rust panics on overflow; in release builds, Rust may or may not panic. It doesn't right now out of performance considerations. That is not a decision that is set in stone if the performance becomes acceptable in the future.
- marvy 10y ago
  This means that Rust has experience with wraparound and with panics. So this question should be answerable by someone on the Rust team: how much does the check cost? A few percent? A factor of 2? Surely not more than that?
  - pcwalton 10y ago
    Depends. The problem is not so much the overhead of the check itself as that it introduces a lot of control flow edges which interfere with optimizations. For example, on x86 you can kiss most uses of LEA goodbye...
    - marvy 10y ago
      Sure, but when all is said and done, what's the cost? There are plenty of Rust benchmarks by now, possibly some of them are part of the test suite. How much do they slow down?
- wofo 10y ago
  Note that it is possible to enable overflow checking in release builds as well.
Asooka 10y ago
AFAIK the case for undefined integer overflow is optimisations regarding loop termination, carry bit handling, and usage of 64-bit vs 32-bit registers. In light of that can't we say that "The compiler may perform signed integer arithmetic using registers larger than the type's bits and truncate the result when writing to memory"? So e.g. int a = INT_MAX; int b = INT_MAX; int c = a + b; c > a; // true on 64 bit iff c was NOT written to memory (so -O1 and above); false on 32 bit (c&0x7fffffff) > a; // false always // i.e. you can always test if two positive values overflow with ((a+b)&0x7f..f)>a Another idea I haven't seen used enough is to put values in 64-bit doubles, do your arithmetic that way and check if the final value fits in your integer type. As long as you restrict yourself to adding, subtracting and multiplying you'll get an exact result back (ok unless you run on a buggy pentium from over 25 years ago, but I think all those were recalled). A problem you have to watch out for is if you've entered the range where your ulp is larger than 1 and your math gets inexact.
- ArkyBeagle 10y ago
  I use float/double float values A Lot these days for arithmetic. So that reduces integer use to values read over a comms line or read otherwise from hardware. Of course, floats have their own quantum of grief.
- nayuki 10y ago
  > Asooka wrote: // i.e. you can always test if two positive values overflow with ((a + b) & 0x7F..F) > a This is bad advice. The act of computing (a + b) is undefined behavior. Masking it afterward will not save you against a strict compiler that exploits (or traps) all undefined behaviors.
  - nkurz 10y ago
    I think the 'Asooka' is aware of this, and was not offering advice. Rather, he was proposing that the world would be simpler if the specs were changed so that signed addition never resulted in undefined behavior. In this simpler counterfactual world, his test would work. In our current easier to optimize world, it would not.
ArkyBeagle 10y ago
> Now that memory errors are slowly disappearing, it's integer problems that are becoming the pain-in-the-neck for exploits. Indeed. Progress! :) I think you may be right about Z_{2^32} but 'C' is hopelessly wedded to it. As practice, it might even be worth having separate types for things on that ring and things expected to not be on that ring. Whether tools to automatically check it exist or not, this at least moves it to be easier to inspect for.
- burfog 10y ago
  Rust should have forced you to specify behavior whenever the compiler can't prove that the difference doesn't matter, like so: 1. default - fail the compile if an overflow could happen 2. wrap - like gcc's -fwrapv option, and C's unsigned type 3. trap - like gcc's -ftrapv option 4. saturate - common DSP behavior 5. unsafe - like gcc's C signed integer cruelty (fastest code) Eh, is it too late to add this? For compatibility with old code, there could be a compiler option to override the default behavior for a whole source file.
  - the_why_of_y 10y ago
    You're right, there does not appear to be a way to achieve 1. Rust arithmetic does 3. in debug builds, or something vaguely similar if requested by using the checked_* functions, and 2. in release builds, or if requested by using the wrapping_* functions, and 4. by using the saturating_* functions. Recommended reading: http://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/ http://huonw.github.io/blog/2016/04/myths-and-legends-about-...
posterboy 10y ago
> big integer If that's your use case, use it. Libraries like GMPrecision exist. Doesn't make a difference for one by off errors, e.g.

pcwalton 10y ago

Yes, it is. I've made a small HN career of countering this meme whenever it comes up :) It's a classic form of no-true-Scotsman, but very popular.

posterboy 10y ago
If it's a fallacy, why wouldn't a programmer do good to avoid UB?
- nkurz 10y ago
  Avoiding undefined behavior is good, and a good programmer tries to avoid undefined behavior. The fallacy is that there exists a population of C and C++ programmers who are skilled enough to always recognize and avoid undefined behavior. While you could define "a good programmer" as one who always recognizes and avoids undefined behavior, the unhelpful result would be concluding that very few good C or C++ programmers exist, possibly none.
  - posterboy 10y ago
    By modus tollens, C can't be a good language, then. Gosh!