6 ms·

"The fact that one must watch out for integer overflow on a buffer size calculation for malloc, realloc, etc." This should be considered evidence that C is not

"The fact that one must watch out for integer overflow on a buffer size calculation for malloc, realloc, etc." This should be considered evidence that C is not a good language to use in code that needs to be secure or reliable.

marshray 13y ago
After all these years, why do we still have CPU architectures that don't trap on integer overflow?
- kevinnk 13y ago
  Because in the vast majority of cases you don't need to and it would unnecessarily slow down a lot of legitimate computation? You can already detect integer overflow extremely easily, why would the cpu need to trap?
  - marshray 13y ago
    Because if 0x7FFFFFFF = 2^31 - 1 0x7FFFFFFF + 1 = 0x80000000 = -2^31 then 2^31 - 1 + 1 = -2^31 2^31 + 1 = -2^31 + 1 (adding 1) 2^31 = -2^31 (subtracting 1) 1 = -1 (dividing by 2^31)
    - kevinnk 13y ago
      I think you may not have understood my question. It is _trivial_ to detect integer overflow in virtually every major cpu I've ever seen. x86, ARM, PPC, MIPS, and many, many more all support this in a single instruction. Trapping, on the other hand, is extreamly expensive in modern processors, on the order of tens of thousands of cycles wasted. Furthermore, there are many cases where integer overflow is actually desired. My question is would be why would a cpu trap be a better solution than what we already have?
      - marshray 13y ago
        For the same reason we trap on integer division by zero. > It is _trivial_ to detect integer overflow I think if we counted the number of + operations in a typical C program and multiplied that by the instruction(s) needed to implement a conditional branch path (often never taken dead code), it would be nontrivial. This overhead should be easily measurable on benchmarks. > Furthermore, there are many cases where integer overflow is actually desired. I'm not arguing against the ability to do that, but I think those cases are far less common. > My question is would be why would a cpu trap be a better solution than what we already have? To allow compilers (not just C) to emit safer code by default by removing the small but measurable instruction penalty.
        deleted 13y ago
        [deleted]
        kevinnk 13y ago
        > For the same reason we trap on integer division by zero. We trap on division because it is objectively a programmer error that has no obvious right answer. Division is also a relatively expensive and much less common operation for the cpu. The overhead of adding trapping is much smaller compared to addition. Furthermore, integer overflow has an easy solution: widen the computation. Divide by 0 has no quick answer. > I think if we counted the number of + operations in a typical C program and multiplied that by the instruction(s) needed to implement a conditional branch path (often never taken dead code), it would be nontrivial. This overhead should be easily measurable on benchmarks. A consistently not taken branch has very, very close to 0 overhead in a modern processor. Not to mention that adding trapping to addition would hinder things like instruction reordering and speculative execution, which adds an overhead that can't be disabled when overflow can provably not occur or not matter. The cpu would also have to treat unsigned and signed addition differently, which means an additional opcode, which adds complexity to the control logic and decreases code density. Finally, there are plenty of languages and libraries which do almost exactly what you propose and automatically widen variables when they overflow and do not experience significant slowdown. >I'm not arguing against the ability to do that, but I think those cases are far less common. You are wrong. Consider the pointer arithmetic expression "ptr += x;" on a cpu that has two trapping add instructions (add unsigned and add signed) and ptr is a pointer and x is a signed value. Note that this is extreamly common for things like array access. Suppose the compiler generated an unsigned add. If the ptr value was 0x1 and x was -1 that would generate an overflow because 0x00000001 + 0xFFFFFFFF results in an unsigned overflow. Suppose it instead generated a signed add. If the ptr value was 0x7FFFFFFF and x was 1 this would also generate an overflow because 0x00000001 + 0x7FFFFFFF results in signed overflow. To resolve this you would need 4 different instructions, which would only get worse as you add various operand lengths to the mix. Now I wouldn't say this is a problem for a majority of add instructions, but adding a signed and unsigned number is a very common operation. In addition, if you actually look at generated assembly code, many of the add instructions do not correspond to a '+' but instead do things like stack management or pointer offset adjustment which do not care about overflow because they can be proved to not occur. > To allow compilers (not just C) to emit safer code by default by removing the small but measurable instruction penalty. Again, there is virtually no overhead on a modern out of order, branch predicting processor. And adding trapping does have an overhead, a significant one, that cannot be removed when overflow can be proved to not occur or isn't important. As a final argument, consider this: of all the major cpu architectures I've studied (MIPS, x86, ARM) not a single one has a trapping add instruction. Very smart people have also considered this problem and have come to the same conclusion: trapping is bad and should only be used in truly exceptional circumstances where no recovery is obvious. I agree with you that integer overflow is a big problem in languages like C that do not have a good way to detect it. However, this is truly a language only problem NOT a cpu one.
    - azernik 13y ago
      (Assuming you meant 2^31) The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic - there is no 2^31. The real weirdness is that -(-2^31) = -2^31. The fundamental issue here is that computer representations of numbers aren't accurate and don't follow the usual rules, in more ways than just overflow.
      - marshray 13y ago
        > Assuming you meant 2^31 Where? > The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic My point exactly. > computer representations of numbers aren't accurate The numbers which can be represented in a computer are perfectly accurate. > and don't follow the usual rules, in more ways than just overflow. At a low level, we program computers to perfom bit operations on registers. Some operations are more straightforward and efficient than others, but ultimately it's how we interpret the bit patterns that makes them "numbers". So if they "don't follow the usual rules", it's our own fault. Security of low-level code has been enough a royal fuckup for long enough now that perhaps we should start to reevaluate some of our traditional assumptions about how CPUs should behave.
        azernik 13y ago
        >> The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic > My point exactly. It doesn't make sense because there's no such number as 2^31 in 32-bit two's complement arithmetic, and I don't think the finite range of finite-length number representations is really a solvable problem. This inevitably leads to a lot of mathematical weirdness, because our math is built on the set of integers being infinite (which is the only kind of set of integers in which closure on addition makes any sense at all). >> and don't follow the usual rules, in more ways than just overflow. > At a low level, we program computers to perfom bit operations on registers. Some operations are more straightforward and efficient than others, but ultimately it's how we interpret the bit patterns that makes them "numbers". Any finite representation of numbers is going to have to break the familiar mathematical rules somehow; I'm pretty satisfied with the tradeoffs made in our current integer representations (unsigned more than signed, but that's in some ways an easier problem).
    - deleted 13y ago
      [deleted]
- tsuyoshi 13y ago
  We kind of already do. For example, there is the INTO (interrupt on overflow) x86 instruction, which calls an interrupt if the overflow flag is set. Nobody ever uses it, though. Probably because it saves you nothing over just using JO (jump on overflow) after every arithmetic instruction, which itself has so little cost (overflow doesn't usually happen, so the branch will almost always be predicted) that many languages have compilers that already do this by default. But C is a terribly primitive language. If I remember correctly, unsigned integers don't really have overflow; the result of any arithmetic operation is supposed to be modulo whatever the maximum is. UINT_MAX + 1 is required to be 0. Signed overflow is supposed to be undefined, but I suppose C programmers care more about saving one instruction plus a usually-predicted branch than they care about making programs more reliable. Of course, a lot of programs depend on signed integers behaving just like unsigned integers, so fixing this would be painful.
asveikau 13y ago
I feel like this statement does not reflect an understanding of the problem. Machines do not have arbitrary-precision integers. If you need to take X units of Y bytes, and your integers are 32 bits, and X is big enough so that X * Y will not fit in 32 bits... Then this problem has to exist somewhere - the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right. The allocator doesn't and can't know whether you really meant "the lower 32 bits of X * Y" or "the product of X and Y", because the former is a totally valid input. You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default: create an array of a size based on an expression with an integer overflow. The difference is that it will blow up in a "safer" manner when you index beyond the end of the array. You could argue that this is the real benefit of the higher level language and perhaps you're right, but somebody at some layer of the system must implement that check; the machine does not have it as an inherent feature.
- betterunix 13y ago
  "Machines do not have arbitrary-precision integers" Nor do they typically have multidimensional arrays. The reason we use compilers and high-level languages is so that we can think in terms of an abstract machine that is easier to work with. Languages exist for the benefit of programmers, and the less mental effort programmers have to spend on nonsense (like remembering that arithmetic is done modulo 2^32 -- or is it 2^64, or 2^29 [yes, really], etc.?) the better able they are to create useful programs. "the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right" Right, and that is why the compiler should translate "x * y" into an arbitrary-precision multiplication -- because programmers assume that "int" refers to "integers," which do not get truncated when they are multiplied. The only reason a compiler should not do such a thing is when it can deduce bounds on the operands that ensure no truncation will occur. Languages that use arbitrary precision arithmetic by default are better and make programmers more productive. "You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default" Yeah, but integer overflows can be and should be reported as errors in languages that do not support arbitrary precision arithmetic. It is very unusual for an overflow to be the desired behavior of a program, and more often than not, overflows are bugs. There was an attack on an electronic voting machine (shown in Hacking Democracy) that exploited an integer overflow -- had the software simply entered an error state, the attack would have been stopped regardless. "You could argue that this is the real benefit of the higher level language and perhaps you're right" Yes, that is basically the point I was making. Let's ignore the part about arbitrary precision arithmetic, and simply assume that overflows will go unreported. Why should it be possible to read or write arbitrary locations in memory as a result? If you try to access an array index that is out of bounds, an exception should be thrown. If the compiler can guarantee that you'll never be out of bounds, i.e. that the exception would never be thrown, it can remove the bounds check as an optimization -- but only when there is such a guarantee. "somebody at some layer of the system must implement that check" That is why we have compilers: they can insert checks for us, automatically, everywhere the checks are needed. It is not different from having your compiler ensure that all functions use the same argument passing convention. Again, this is why we use compilers -- compilers are better at doing mundane, tedious tasks like setting up stack frames or checking array boundaries. Programmers tend to make mistakes with these things, and those mistakes usually lead to disastrous problems later on.

marshray 13y ago

After all these years, why do we still have CPU architectures that don't trap on integer overflow?

kevinnk 13y ago
Because in the vast majority of cases you don't need to and it would unnecessarily slow down a lot of legitimate computation? You can already detect integer overflow extremely easily, why would the cpu need to trap?
- marshray 13y ago
  Because if 0x7FFFFFFF = 2^31 - 1 0x7FFFFFFF + 1 = 0x80000000 = -2^31 then 2^31 - 1 + 1 = -2^31 2^31 + 1 = -2^31 + 1 (adding 1) 2^31 = -2^31 (subtracting 1) 1 = -1 (dividing by 2^31)
  - kevinnk 13y ago
    I think you may not have understood my question. It is _trivial_ to detect integer overflow in virtually every major cpu I've ever seen. x86, ARM, PPC, MIPS, and many, many more all support this in a single instruction. Trapping, on the other hand, is extreamly expensive in modern processors, on the order of tens of thousands of cycles wasted. Furthermore, there are many cases where integer overflow is actually desired. My question is would be why would a cpu trap be a better solution than what we already have?
    - marshray 13y ago
      For the same reason we trap on integer division by zero. > It is _trivial_ to detect integer overflow I think if we counted the number of + operations in a typical C program and multiplied that by the instruction(s) needed to implement a conditional branch path (often never taken dead code), it would be nontrivial. This overhead should be easily measurable on benchmarks. > Furthermore, there are many cases where integer overflow is actually desired. I'm not arguing against the ability to do that, but I think those cases are far less common. > My question is would be why would a cpu trap be a better solution than what we already have? To allow compilers (not just C) to emit safer code by default by removing the small but measurable instruction penalty.
      - deleted 13y ago
        [deleted]
      - kevinnk 13y ago
        > For the same reason we trap on integer division by zero. We trap on division because it is objectively a programmer error that has no obvious right answer. Division is also a relatively expensive and much less common operation for the cpu. The overhead of adding trapping is much smaller compared to addition. Furthermore, integer overflow has an easy solution: widen the computation. Divide by 0 has no quick answer. > I think if we counted the number of + operations in a typical C program and multiplied that by the instruction(s) needed to implement a conditional branch path (often never taken dead code), it would be nontrivial. This overhead should be easily measurable on benchmarks. A consistently not taken branch has very, very close to 0 overhead in a modern processor. Not to mention that adding trapping to addition would hinder things like instruction reordering and speculative execution, which adds an overhead that can't be disabled when overflow can provably not occur or not matter. The cpu would also have to treat unsigned and signed addition differently, which means an additional opcode, which adds complexity to the control logic and decreases code density. Finally, there are plenty of languages and libraries which do almost exactly what you propose and automatically widen variables when they overflow and do not experience significant slowdown. >I'm not arguing against the ability to do that, but I think those cases are far less common. You are wrong. Consider the pointer arithmetic expression "ptr += x;" on a cpu that has two trapping add instructions (add unsigned and add signed) and ptr is a pointer and x is a signed value. Note that this is extreamly common for things like array access. Suppose the compiler generated an unsigned add. If the ptr value was 0x1 and x was -1 that would generate an overflow because 0x00000001 + 0xFFFFFFFF results in an unsigned overflow. Suppose it instead generated a signed add. If the ptr value was 0x7FFFFFFF and x was 1 this would also generate an overflow because 0x00000001 + 0x7FFFFFFF results in signed overflow. To resolve this you would need 4 different instructions, which would only get worse as you add various operand lengths to the mix. Now I wouldn't say this is a problem for a majority of add instructions, but adding a signed and unsigned number is a very common operation. In addition, if you actually look at generated assembly code, many of the add instructions do not correspond to a '+' but instead do things like stack management or pointer offset adjustment which do not care about overflow because they can be proved to not occur. > To allow compilers (not just C) to emit safer code by default by removing the small but measurable instruction penalty. Again, there is virtually no overhead on a modern out of order, branch predicting processor. And adding trapping does have an overhead, a significant one, that cannot be removed when overflow can be proved to not occur or isn't important. As a final argument, consider this: of all the major cpu architectures I've studied (MIPS, x86, ARM) not a single one has a trapping add instruction. Very smart people have also considered this problem and have come to the same conclusion: trapping is bad and should only be used in truly exceptional circumstances where no recovery is obvious. I agree with you that integer overflow is a big problem in languages like C that do not have a good way to detect it. However, this is truly a language only problem NOT a cpu one.
  - azernik 13y ago
    (Assuming you meant 2^31) The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic - there is no 2^31. The real weirdness is that -(-2^31) = -2^31. The fundamental issue here is that computer representations of numbers aren't accurate and don't follow the usual rules, in more ways than just overflow.
    - marshray 13y ago
      > Assuming you meant 2^31 Where? > The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic My point exactly. > computer representations of numbers aren't accurate The numbers which can be represented in a computer are perfectly accurate. > and don't follow the usual rules, in more ways than just overflow. At a low level, we program computers to perfom bit operations on registers. Some operations are more straightforward and efficient than others, but ultimately it's how we interpret the bit patterns that makes them "numbers". So if they "don't follow the usual rules", it's our own fault. Security of low-level code has been enough a royal fuckup for long enough now that perhaps we should start to reevaluate some of our traditional assumptions about how CPUs should behave.
      - azernik 13y ago
        >> The first equation in that second block (and so the rest of the block) doesn't really make sense in 32 bit two's complement arithmetic > My point exactly. It doesn't make sense because there's no such number as 2^31 in 32-bit two's complement arithmetic, and I don't think the finite range of finite-length number representations is really a solvable problem. This inevitably leads to a lot of mathematical weirdness, because our math is built on the set of integers being infinite (which is the only kind of set of integers in which closure on addition makes any sense at all). >> and don't follow the usual rules, in more ways than just overflow. > At a low level, we program computers to perfom bit operations on registers. Some operations are more straightforward and efficient than others, but ultimately it's how we interpret the bit patterns that makes them "numbers". Any finite representation of numbers is going to have to break the familiar mathematical rules somehow; I'm pretty satisfied with the tradeoffs made in our current integer representations (unsigned more than signed, but that's in some ways an easier problem).
  - deleted 13y ago
    [deleted]
tsuyoshi 13y ago
We kind of already do. For example, there is the INTO (interrupt on overflow) x86 instruction, which calls an interrupt if the overflow flag is set. Nobody ever uses it, though. Probably because it saves you nothing over just using JO (jump on overflow) after every arithmetic instruction, which itself has so little cost (overflow doesn't usually happen, so the branch will almost always be predicted) that many languages have compilers that already do this by default. But C is a terribly primitive language. If I remember correctly, unsigned integers don't really have overflow; the result of any arithmetic operation is supposed to be modulo whatever the maximum is. UINT_MAX + 1 is required to be 0. Signed overflow is supposed to be undefined, but I suppose C programmers care more about saving one instruction plus a usually-predicted branch than they care about making programs more reliable. Of course, a lot of programs depend on signed integers behaving just like unsigned integers, so fixing this would be painful.

asveikau 13y ago

I feel like this statement does not reflect an understanding of the problem. Machines do not have arbitrary-precision integers. If you need to take X units of Y bytes, and your integers are 32 bits, and X is big enough so that X * Y will not fit in 32 bits... Then this problem has to exist somewhere - the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right. The allocator doesn't and can't know whether you really meant "the lower 32 bits of X * Y" or "the product of X and Y", because the former is a totally valid input. You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default: create an array of a size based on an expression with an integer overflow. The difference is that it will blow up in a "safer" manner when you index beyond the end of the array. You could argue that this is the real benefit of the higher level language and perhaps you're right, but somebody at some layer of the system must implement that check; the machine does not have it as an inherent feature.

betterunix 13y ago
"Machines do not have arbitrary-precision integers" Nor do they typically have multidimensional arrays. The reason we use compilers and high-level languages is so that we can think in terms of an abstract machine that is easier to work with. Languages exist for the benefit of programmers, and the less mental effort programmers have to spend on nonsense (like remembering that arithmetic is done modulo 2^32 -- or is it 2^64, or 2^29 [yes, really], etc.?) the better able they are to create useful programs. "the machine will have to truncate the product into a 32 bit entity, the bit pattern of which is a legitimate quantity in its own right" Right, and that is why the compiler should translate "x * y" into an arbitrary-precision multiplication -- because programmers assume that "int" refers to "integers," which do not get truncated when they are multiplied. The only reason a compiler should not do such a thing is when it can deduce bounds on the operands that ensure no truncation will occur. Languages that use arbitrary precision arithmetic by default are better and make programmers more productive. "You could very well make the same mistake in a higher level language since AFAIK most of them don't have arbitrary precision integers by default" Yeah, but integer overflows can be and should be reported as errors in languages that do not support arbitrary precision arithmetic. It is very unusual for an overflow to be the desired behavior of a program, and more often than not, overflows are bugs. There was an attack on an electronic voting machine (shown in Hacking Democracy) that exploited an integer overflow -- had the software simply entered an error state, the attack would have been stopped regardless. "You could argue that this is the real benefit of the higher level language and perhaps you're right" Yes, that is basically the point I was making. Let's ignore the part about arbitrary precision arithmetic, and simply assume that overflows will go unreported. Why should it be possible to read or write arbitrary locations in memory as a result? If you try to access an array index that is out of bounds, an exception should be thrown. If the compiler can guarantee that you'll never be out of bounds, i.e. that the exception would never be thrown, it can remove the bounds check as an optimization -- but only when there is such a guarantee. "somebody at some layer of the system must implement that check" That is why we have compilers: they can insert checks for us, automatically, everywhere the checks are needed. It is not different from having your compiler ensure that all functions use the same argument passing convention. Again, this is why we use compilers -- compilers are better at doing mundane, tedious tasks like setting up stack frames or checking array boundaries. Programmers tend to make mistakes with these things, and those mistakes usually lead to disastrous problems later on.