This should be considered evidence that C is not a good language to use in code that needs to be secure or reliable.
This should be considered evidence that C is not a good language to use in code that needs to be secure or reliable.
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.
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.
Because that is the point of an allocator. Your favorite language cannot have allocators in the same sense that C can. Instead of going on a crusade against the language, why not simply accept that some problem domains have to care about that?
In this discussion I am not here griping about my favorite criticisms of various higher level languages (some examples: lots of code out there that assumes memory allocation is free, data structures with lots of gratuitous pointers [oops sorry, "object references"!] that slow down access, over-reliance on exceptions i.e. thousands of gotos that cross stack frames) because I admit that these languages are good for certain problem sets.
A common refrain in these discussions is that C is good for some problem domains, and high level languages are good for others. The problem is that C is not being used only for one domain or some set of domains; it is being used everywhere. Web browsers and web servers are written in C. Email clients are written in C. Instant messaging programs. It is hard to see how my email program benefits from pointer acrobatics, unchecked array access, or a pile of undefined behavior -- so why was it written in C?
You could say this is my main issue. I can just assume that C is good in some domain, even if I never come across it; what I cannot understand is why high-level software is being written in a language that bogs programmers down with low-level concerns. Even implementing a small core in C, and the rest in a high-level language (e.g. Emacs) makes more sense than what we see today.
You must understand that from the low level perspective, the array and its bounds do not exist. This is an abstraction. An allocator needs to chop up and slice a larger block of memory and give different segments to different callers. You cannot do this if something is enforcing bounds.
What you can do is build higher level abstractions that track bounds and do runtime checks at every access. In C there is nothing to stop you from doing that as a library. In C++, some STL implementations even have bounds checking as a compile time option. But the languages don't force you into paying that cost.
Sure you can -- if the enforcement of array boundaries is based on types, and is not applied when dealing with a generic, low-level pointer type. Take a look at the implementation of SBCL (a Common Lisp compiler) to see this sort of thing in action.
Yes, building abstractions is the right thing to do, but libraries are the wrong way to do it. The problem with libraries is that the programmer needs to expend their mental energy on using the library, and needs to remember to not just use what the language provides them. If anything, the programmer should be forced to use a library to avoid bounds checking -- extra effort should be required to do dangerous things, rather than to be safe.
"the languages don't force you into paying that cost."
Neither do high-level languages, if you can guarantee that the cost does not need to be paid (and if you are using a half decent compiler). If your compiler can deduce that your array index cannot be out of bounds, it should generate code without a bounds check. That is why Lisp has type hints, and it is one of the arguments you hear in favor of static type checking.
Machines don't have concepts like "integers" at all. They have concrete functions that produce defined outputs with defined inputs, which can be interpreted as fixed size integers, components of arbitrary precision integers, or specifications of glyphs, or numerous other things. But none of those interpretations are inherent in the machine.
I suppose we can get philosophical and say that there is no such thing as a machine word, that when you operate on the memory using different instructions, or jump into the memory, or whatever, this "machine word" becomes something else... But IMO this is a pointless exercise. The fixed-size machine word is a reality in the machines we're talking about. (How that gets translated into a higher level language like C will vary from machine to machine, compiler to compiler, but the analogy still stands and I do not believe it is meaningful to argue such points unless engaged in purposeful misinterpretation.)
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)> 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.
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.
Defining (2^31 - 1) + 1 = -2^31 is no more of an "obvious right answer" than defining N/0 = 42 for all N. It's just one that we computer engineers have been trained to accept because it is occasionally useful.
But it's still madness which discourages us from using tools that emit more correct code.
> A consistently not taken branch has very, very close to 0 overhead in a modern processor.
Except the half a dozen or so bytes it consumes in the cache.
Nevertheless, I concede that others have thought about this a lot more than I have and done so with hard data in front of them.
The thing is I can hardly imagine a situation where a division by zero would be normal and expected, while having integers overflow as a normal part of a calculation is business as usual in many cases. Having to handle a trap (or disabling/enabling it dynamically) would slow things down way too much. Many crypto ciphers for instance specify operations "modulo 32" in order to take advantage of this "feature".
> To allow compilers (not just C) to emit safer code by default by removing the small but measurable instruction penalty.
Detecting overflow in asm is just testing the carry bit of the processor. A trap would be orders of magnitude slower on any modern architecture. You seem to be assuming that overflows are rare in C programs. I'm not sure this is true, but I have no hard data on that so who knows...
Which is one reason I'm specifically not advocating for doing away with nonsignaling modulo-2^2^n addition.
However, of all the addition operations in the gigabytes of object code on my hard drive, what percentage of them do you think actually encode the true desire of an application developer to perform wrapping arithmetic?
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.
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.
> 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).
How is that? The only numbers you would have trouble with are non-computable numbers, and I doubt you will find many software systems that deal with those. The only limiting factor should be the memory that is available, but that is beyond the scope of software; the software should work up to the limits of available memory, and increase the amount of memory should increase the range of numbers the program can deal with.
"I'm pretty satisfied with the tradeoffs made in our current integer representations"
I'm not, because (a) the semantics are counter-intuitive and (b) not a day goes by without people finding bugs related to integer overflows or weird, unexpected behavior. We have security problems. We have reliability problems. Voting machines get hacked and report negative vote totals.
At the very least, integer overflows should trigger an exception unless the programmer explicitly requests arithmetic modulo 2^32 (or 2^64, or 2^29, or whatever weird bit width the hardware supports).
I started out with the definition:
0x7FFFFFFF = 2^31 - 1
Adding one to that 0x7FFFFFFF + 1 = 2^31 - 1 + 1
should be 2^31, but it isn't.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.