10 ms·

Understanding Integer Overflow in C/C++ (2012) [pdf]

65 points by 0xmohit 10y ago

hellofunk 10y ago
>a truncation error on a cast of a floating point value to a 16-bit integer played a crucial role in the destruction of Ariane 5 flight 501 in 1996. These errors are also a source of serious vulnerabilities, such as integer overflow errors in OpenSSH [MITRE Corporation 2002] and Firefox [MITRE Corporation 2010], both of which allow attackers to execute arbitrary code. In their 2011 report MITRE places integer overflows in the “Top 25 Most Dangerous Software Errors” [Christey et al. 2011]. Wow, that's more than a little enlightening.
- aomix 10y ago
  The OpenBSD devs were really enthusiastic about reallocarray as a way to catch some integer overflow issues like the OpenSSH issue.
- ArkyBeagle 10y ago
  This is absolutely true and greatly increases the cognitive load from using 'C'. IMO, all systems which use 'C' need a great deal of test furniture and possibly code analyzers to manage this. And of course, nobody wants to pay for this. But I mean - if you have not done a basic fuzz test of the thing then you have really no idea. What would be interesting is a series of experiments to directly contrast the Therac, Ariane and OpenSSL errors using something like Rust. As I understand it, there still may well have been a crash of some sort.
- _kst_ 10y ago
  It's interesting that the article mentions the Ariane 5 bug, but doesn't mention that the Ariane 5 software (at least the component that caused the bug) was written in Ada, not C. The real problem is that the Ariane 4 software was used without re-testing for the new rocket. The overflow could not occur on the Ariane 4. The higher acceleration of the Ariane 5 resulted in the overflow. The overflow was caught by the Ada runtime system, and generated an error message. The error message was then processed as data.
  - junke 10y ago
    This is not targetted directly at you, but when I spot people talk about Ariane 5, it is generally only to cover one particular aspect of the bug which confirms their personal opinion or agenda. So for reference, here is the full report: https://www.ima.umn.edu/~arnold/disasters/ariane5rep.html https://www.ima.umn.edu/~arnold/disasters/ariane5rep.html > 3.2 CAUSE OF THE FAILURE > The failure of the Ariane 501 was caused by the complete loss of guidance and attitude information 37 seconds after start of the main engine ignition sequence (30 seconds after lift- off). This loss of information was due to specification and design errors in the software of the inertial reference system. > The extensive reviews and tests carried out during the Ariane 5 Development Programme did not include adequate analysis and testing of the inertial reference system or of the complete flight control system, which could have detected the potential failure. </quote> Some interpretations: Put it in the contract: The lessons of Ariane (https://www.irisa.fr/pampa/EPEE/Ariane5.html https://www.irisa.fr/pampa/EPEE/Ariane5.html) The Ariane 5 bug and a few lessons (http://www.leshatton.org/Documents/Ariane5_STQE499.pdf http://www.leshatton.org/Documents/Ariane5_STQE499.pdf) I heard tell that Ada was to blame for the Ariane V disaster. Is this true? (http://www.adapower.com/index.php?Command=Class&ClassID=FAQ&CID=328 http://www.adapower.com/index.php?Command=Class&ClassID=FAQ&...)
adrianN 10y ago
In fact, in the course of our work, we have found that even experts writing safe integer libraries or tools to detect integer errorssometimes make mistakes due to the subtleties of C/C++ semantics for numerical operations Another nail in the coffin for the meme that "good programmers don't write code with undefined behavior".
- 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.
ArkyBeagle 10y ago
Integer overflows don't kill people; people kill people with integer overflows. I'll show myself out :)
akkartik 10y ago
Wild and whacky idea: has anyone ever built a language with separate types for ordinal/cardinal numbers and nominal numbers? The idea would be that with nominal numbers you don't care about the precise result of individual calculations, just statistical properties like determinism, distribution, etc. So arithmetic on nominal numbers would be permitted to overflow, as operations are just various ways to jump from one nominal to another. However, most numbers would be ordinals/cardinals, and any overflow when generating an ordinal/cardinal would be considered an error. https://en.wikipedia.org/wiki/Nominal_number https://en.wikipedia.org/wiki/Nominal_number
- marvy 10y ago
  What can you usefully do with a nominal number, besides input/output and comparing two of them for equality? I don't think you need language support here, library support should suffice, unless I'm missing something.
  - akkartik 10y ago
    I was imagining that you could do everything with nominals that you normally do with integers. Arithmetic saving results in nominal numbers would just disable overflow checking. This would allow all operations involving regular numbers to double down and perform extremely strict overflow checking.
    - Noseshine 10y ago
      The question is (and I think was), what arithmetic do you do with numbers whose values don't matter and what concrete value they happen to have is purely accidental and arbitrary and unimportant.
      - akkartik 10y ago
        From the OP, examples of intentional overflow are "..hashing, cryptography, random number generation, and finding the largest representable value for a type."
nkurz 10y ago
Do there exist any good tools for identifying undefined behavior in C or C++ code? Compiler warnings are getting better, and "sanitizers" can catch undefined behavior that actually happens at runtime, but I still haven't found anything that consistently catches unwanted optimizations based on compiler assumptions of "no undefined behavior". Stack (https://css.csail.mit.edu/stack/ https://css.csail.mit.edu/stack/) is the best tool that I've found, and while it's a great start, it's extremely difficult to install, clumsy to use, doesn't appear to have been touched in years, and only catches a limited subset of constructs. Is there anything else out there? If not, is it because it's perceived as too difficult to do, or is it just not perceived as a need?
- telotortium 10y ago
  Not all undefined behavior can be caught at compile time. However, LLVM and GCC can detect a lot of undefined behavior at runtime with ubsan. I'm not sure how much performance penalty there is. Presumably checks are added on every signed integer arithmetic operation, pointer dereference, etc., but some checks can probably be removed by the optimizer (for example, a branch may be taken if a pointer is not null, which means the optimizer can remove all null checks in that branch as long as the pointer hasn't been modified). Edit: oops, I missed the part where you said you're aware of sanitizers.
- deleted 10y ago
  [deleted]
- tacostakohashi 10y ago
  Probably Coverity (http://www.synopsys.com/software/coverity/Pages/default.aspx http://www.synopsys.com/software/coverity/Pages/default.aspx) is the best / most complete implementation of this idea. Although it has impressive capabilities, you'll need to deal with their sales people, get a license, and invest a non-trivial amount of time learning the system, modifying your software build, etc, to get a lot out of in. Unless your code is mission-critical, it's probably more trouble than it's worth.
- Too 10y ago
  GCC has -fsanitize which is pretty good.
0xmohit 10y ago
Also, Robbert Krebbers's PhD thesis titled "The C standard formalized in Coq" [0]. From the summary: Our formal specification of C is faithful to the C11 standard, which means it describes all undefined behaviors of C11. As a consequence, when one proves something about a given program with respect to our semantics, it should behave that way with any ostensibly C11 compliant compiler such as GCC or Clang. [0] http://robbertkrebbers.nl/thesis.html http://robbertkrebbers.nl/thesis.html
dtzWill 10y ago
Author here. FWIW the linked paper is the extended edition as published in TOSEM 2015, not the original ICSE 2012 paper, which I was surprised by given the year in the subject. That said, I'm glad this edition is getting a bit of attention as we were able to be more thorough given the longer format (as well as more time), including an automated study of the top 10k Debian packages. The paper details what's new in more detail. Let me know if you have any questions or comments. May your integers be safe!
- akkartik 10y ago
  I'm curious to hear your thoughts on https://news.ycombinator.com/item?id=12063597 https://news.ycombinator.com/item?id=12063597! The long thread beneath it basically convinced me that calling them 'nominal' was a bad idea, but perhaps if we had a chance to do C over again we should replace the dichotomy between signed and unsigned with abort-on-overflow and wrap-on-overflow?

65 points by 0xmohit 10y ago

>a truncation error on a cast of a floating point value to a 16-bit integer played a crucial role in the destruction of Ariane 5 flight 501 in 1996. These errors are also a source of serious vulnerabilities, such as integer overflow errors in OpenSSH [MITRE Corporation 2002] and Firefox [MITRE Corporation 2010], both of which allow attackers to execute arbitrary code. In their 2011 report MITRE places integer overflows in the “Top 25 Most Dangerous Software Errors” [Christey et al. 2011]. Wow, that's more than a little enlightening.

aomix 10y ago
The OpenBSD devs were really enthusiastic about reallocarray as a way to catch some integer overflow issues like the OpenSSH issue.
ArkyBeagle 10y ago
This is absolutely true and greatly increases the cognitive load from using 'C'. IMO, all systems which use 'C' need a great deal of test furniture and possibly code analyzers to manage this. And of course, nobody wants to pay for this. But I mean - if you have not done a basic fuzz test of the thing then you have really no idea. What would be interesting is a series of experiments to directly contrast the Therac, Ariane and OpenSSL errors using something like Rust. As I understand it, there still may well have been a crash of some sort.
_kst_ 10y ago
It's interesting that the article mentions the Ariane 5 bug, but doesn't mention that the Ariane 5 software (at least the component that caused the bug) was written in Ada, not C. The real problem is that the Ariane 4 software was used without re-testing for the new rocket. The overflow could not occur on the Ariane 4. The higher acceleration of the Ariane 5 resulted in the overflow. The overflow was caught by the Ada runtime system, and generated an error message. The error message was then processed as data.
- junke 10y ago
  This is not targetted directly at you, but when I spot people talk about Ariane 5, it is generally only to cover one particular aspect of the bug which confirms their personal opinion or agenda. So for reference, here is the full report: https://www.ima.umn.edu/~arnold/disasters/ariane5rep.html https://www.ima.umn.edu/~arnold/disasters/ariane5rep.html > 3.2 CAUSE OF THE FAILURE > The failure of the Ariane 501 was caused by the complete loss of guidance and attitude information 37 seconds after start of the main engine ignition sequence (30 seconds after lift- off). This loss of information was due to specification and design errors in the software of the inertial reference system. > The extensive reviews and tests carried out during the Ariane 5 Development Programme did not include adequate analysis and testing of the inertial reference system or of the complete flight control system, which could have detected the potential failure. </quote> Some interpretations: Put it in the contract: The lessons of Ariane (https://www.irisa.fr/pampa/EPEE/Ariane5.html https://www.irisa.fr/pampa/EPEE/Ariane5.html) The Ariane 5 bug and a few lessons (http://www.leshatton.org/Documents/Ariane5_STQE499.pdf http://www.leshatton.org/Documents/Ariane5_STQE499.pdf) I heard tell that Ada was to blame for the Ariane V disaster. Is this true? (http://www.adapower.com/index.php?Command=Class&ClassID=FAQ&CID=328 http://www.adapower.com/index.php?Command=Class&ClassID=FAQ&...)

adrianN 10y ago

In fact, in the course of our work, we have found that even experts writing safe integer libraries or tools to detect integer errorssometimes make mistakes due to the subtleties of C/C++ semantics for numerical operations Another nail in the coffin for the meme that "good programmers don't write code with undefined behavior".

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.

ArkyBeagle 10y ago

Integer overflows don't kill people; people kill people with integer overflows. I'll show myself out :)

akkartik 10y ago

Wild and whacky idea: has anyone ever built a language with separate types for ordinal/cardinal numbers and nominal numbers? The idea would be that with nominal numbers you don't care about the precise result of individual calculations, just statistical properties like determinism, distribution, etc. So arithmetic on nominal numbers would be permitted to overflow, as operations are just various ways to jump from one nominal to another. However, most numbers would be ordinals/cardinals, and any overflow when generating an ordinal/cardinal would be considered an error. https://en.wikipedia.org/wiki/Nominal_number https://en.wikipedia.org/wiki/Nominal_number

marvy 10y ago
What can you usefully do with a nominal number, besides input/output and comparing two of them for equality? I don't think you need language support here, library support should suffice, unless I'm missing something.
- akkartik 10y ago
  I was imagining that you could do everything with nominals that you normally do with integers. Arithmetic saving results in nominal numbers would just disable overflow checking. This would allow all operations involving regular numbers to double down and perform extremely strict overflow checking.
  - Noseshine 10y ago
    The question is (and I think was), what arithmetic do you do with numbers whose values don't matter and what concrete value they happen to have is purely accidental and arbitrary and unimportant.
    - akkartik 10y ago
      From the OP, examples of intentional overflow are "..hashing, cryptography, random number generation, and finding the largest representable value for a type."

nkurz 10y ago

Do there exist any good tools for identifying undefined behavior in C or C++ code? Compiler warnings are getting better, and "sanitizers" can catch undefined behavior that actually happens at runtime, but I still haven't found anything that consistently catches unwanted optimizations based on compiler assumptions of "no undefined behavior". Stack (https://css.csail.mit.edu/stack/ https://css.csail.mit.edu/stack/) is the best tool that I've found, and while it's a great start, it's extremely difficult to install, clumsy to use, doesn't appear to have been touched in years, and only catches a limited subset of constructs. Is there anything else out there? If not, is it because it's perceived as too difficult to do, or is it just not perceived as a need?

telotortium 10y ago
Not all undefined behavior can be caught at compile time. However, LLVM and GCC can detect a lot of undefined behavior at runtime with ubsan. I'm not sure how much performance penalty there is. Presumably checks are added on every signed integer arithmetic operation, pointer dereference, etc., but some checks can probably be removed by the optimizer (for example, a branch may be taken if a pointer is not null, which means the optimizer can remove all null checks in that branch as long as the pointer hasn't been modified). Edit: oops, I missed the part where you said you're aware of sanitizers.
deleted 10y ago
[deleted]
tacostakohashi 10y ago
Probably Coverity (http://www.synopsys.com/software/coverity/Pages/default.aspx http://www.synopsys.com/software/coverity/Pages/default.aspx) is the best / most complete implementation of this idea. Although it has impressive capabilities, you'll need to deal with their sales people, get a license, and invest a non-trivial amount of time learning the system, modifying your software build, etc, to get a lot out of in. Unless your code is mission-critical, it's probably more trouble than it's worth.
Too 10y ago
GCC has -fsanitize which is pretty good.

0xmohit 10y ago

Also, Robbert Krebbers's PhD thesis titled "The C standard formalized in Coq" [0]. From the summary: Our formal specification of C is faithful to the C11 standard, which means it describes all undefined behaviors of C11. As a consequence, when one proves something about a given program with respect to our semantics, it should behave that way with any ostensibly C11 compliant compiler such as GCC or Clang. [0] http://robbertkrebbers.nl/thesis.html http://robbertkrebbers.nl/thesis.html

dtzWill 10y ago

Author here. FWIW the linked paper is the extended edition as published in TOSEM 2015, not the original ICSE 2012 paper, which I was surprised by given the year in the subject. That said, I'm glad this edition is getting a bit of attention as we were able to be more thorough given the longer format (as well as more time), including an automated study of the top 10k Debian packages. The paper details what's new in more detail. Let me know if you have any questions or comments. May your integers be safe!

akkartik 10y ago
I'm curious to hear your thoughts on https://news.ycombinator.com/item?id=12063597 https://news.ycombinator.com/item?id=12063597! The long thread beneath it basically convinced me that calling them 'nominal' was a bad idea, but perhaps if we had a chance to do C over again we should replace the dichotomy between signed and unsigned with abort-on-overflow and wrap-on-overflow?