Understanding Integer Overflow in C/C++ (2012) [pdf]
cs.utah.edu
cs.utah.edu
Another nail in the coffin for the meme that "good programmers don't write code with undefined behavior".
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.
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.
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
Of course, floats have their own quantum of grief.
// i.e. you can always test if two positive values overflow with
((a + b) & 0x7F..F) > a
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.
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.
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-...
If that's your use case, use it. Libraries like GMPrecision exist. Doesn't make a difference for one by off errors, e.g.
It's a classic form of no-true-Scotsman, but very popular.
This involves at least doing a depth-first examination of all invocations of that operation, and possibly writing tests for all of them. That encourages keeping things local.
I think the safety-think here is slightly inappropriate. Of course you can do it wrong. But it is in no way an unreasonable expectation that you not do that.
And again- for the general population out there - perhaps 'C' is not for you. I am a 'C' programmer only because of path dependencies in what's happened to me. I would not recommend it to anyone. That's not elitist - it's just how things played out.
I suppose if you're not interested in that ( and I understand that impulse, believe me ) then ...
I have to, by training, attribute all defects to process and human behavior. But as things emerge, maybe the tools will really fill the gap. But again, at a cost.
I am, say, pretty good with Python but I am by no means a master. It would take having a full time exposure for months, perhaps years to make that claim. And this fragments us. It may well be that I'd actually be better fit for a job using Python but because I can't make this claim now, we get a false negative on fitness.
I'm just using "me" and "Python" to construct an example.
C, like unix, is a small payload spreading like a virus, depending on the coder to keep it alive. The simplicity and the emergent behavior are as much an evolutionary advantage as a burden because of the UB. At 600 pages, the standard is not really simple anymore, as the RNA accrues more inputs from different vectors.
I started to read the The UNIX-Haters Handbook [1] after I installed a Windows VM and saw the link here the other day.
> Nominal numbers or categorical numbers are numeric codes, meaning numerals used for identification only. The numerical value is in principle irrelevant, and they do not indicate quantity, rank, or any other measurement.
You talked about nominal numbers up to (but excluding) this post.
"nominal" means "in name only", so it's a "number", not a number. It just happens to have the same name as a number with a value.
> "I don't care what the precise results of arithmetic are."
I already quoted it, "nominal numbers" have no value!
You are absolutely right though: This conversation has lead nowhere. I'm not sure your identification of who is to blame is correct though.
You asked about nominal numbers, and when asked for details your examples all are about actual numbers. When I point that out your reaction is to be offended. How mature.
You can't talk about "nominal numbers" and then be miffed that people don't understand that you are not actually talking about nominal numbers at all! I only come to understand that now. Tip: Don't talk about water when you mean sand, and then act confused when someone brings you water instead of sand.
The examples you quoted above are NOT using nominal numbers. Those are ACTUAL numbers. Those are modulo operations - that is NOT "nominal numbers".
Personal attacks won't help, they never do in any discussion. You should seriously consider changing your discussion style.
If your question was about modular arithmetic, it confuses two different issues. It would be just a coincidence if the highest number representable with the given amount of bits happens to be the same number you want for your modulo operations. Those are only accidentally related issues.
If you choose to add two phone numbers, I think we both agree that the phone numbers are still nominal. But I think we also agree that you have computed nonsense. There's nothing you can do with that sum. Which naturally raises the question: why should a programming language support this operation?
If you think adding two phone numbers can have no possible useful application, what do you say to taking strings of text, converting them to numbers, and repeatedly folding them over each other to compute a cryptographic digest? You're right that it is meaningless in the context of the original domain, but it clearly has application. The two are distinct ideas.
So I'm not sure what your plan really is here. To support modulo operations in hardware by using the limited bits of the registers limits your modulo operations to the size of the registers. If you are talking about purely software operations and not the hardware - I'm not sure - well, that exists. We already have modulo operations in all programming languages, it's not missing. And if you are talking about the hardware support, you are free to ignore the flags (which you only get to access in assembler anyway) and use the registers as a kind of "implied modulo", that's the point of the discussion that when overflow happens your code won't notice.
checked(a+b) // crash on overflow
unchecked(a+b) // wrap on overflow
a+b // use the default of the surrounding context
Thanks for letting me know my idea finally got across. I was massively under-estimating its subtlety.
Maybe eventually the world will agree with you. We already eat the slowdown that comes with bounds-checked arrays. And indeed, compilers are getting better at removing that bit of overhead, compared to, say, the 1970s.
That said, it's been surprisingly ergonomic. If it had a compiler and could generate binaries, and if it had parity in libraries with C, I think I would strongly prefer using it to C. The massively increased safety is worth giving up a lot of expressivity for, IMO. No comparison with HLL languages for prototyping, of course. Eventually I hope to get the usual HLLs reimplemented atop it. One subtle point is that since it's refcounted at the Assembly level, any language built atop it requires minimal GC support.
The fact that it's Assembly has caused some confusion with others, so I want to point out that:
a) you can add any number of numbers in a single instruction; that gets handled behind the scenes. Many instructions are variadic where it makes sense.
b) you don't need push/pop/call to call a function, function calls look just like primitive operations.
c) Mu knows about types, so it knows how to allocate them, how to print them, and (eventually) how to serialize/unserialize them. These things can be overridden, but they work out of the box for any new types you create.
d) Mu supports generic types. Here's a generic linked-list, for example: http://akkartik.github.io/mu/html/064list.mu.html. Types starting with underscores are type parameters.
e) You get structured programming by default using the break and loop instructions which translate to jumps just after the enclosing '}' and '{' label, respectively. Factorial in Mu looks surprisingly clean: http://akkartik.github.io/mu/html/factorial.mu.html
What's common to these features is that I could imagine implementing them in a compiler using just machine language and Mu. What I'm trying to avoid is having to write a complex optimizer. These features (I think) don't massively increase the impedance mismatch between Mu and machine code; they can be implemented with basically glorified search-and-replace.
The Mu editor is built in Mu, yes. That's just because I don't have a HLL yet. It's not to say that I think everyone should build apps only in the Assembly layer. It's a little like the early days of C and Unix: until the language got stable people built the original versions of compiler and OS in Assembly. But they were eventually able to move to C.
a) next-ingredient is still around, and I still teach it first before graduating students to headers.
b) Headers get translated to next-ingredient calls behind the scenes, but without the need to type-check ingredients at runtime.
c) You might still choose to use next-ingredient if you want to implement optional arguments, or variadic functions. A weird one is interpolate (in http://akkartik.github.io/mu/html/061text.mu.html), which scans through its arguments twice, first to compute the size of the array to allocate to hold them, and then a second time to copy them over. Since calls to next-ingredient can get arbitrarily complex, Mu doesn't bother type-checking them. It just moves the type-checking for explicit calls to next-ingredient to run-time.
I'll update that post. Thanks again.
(1) It's a good question. I think small benchmarks will likely be much slower in Mu since Python probably has optimized primitives for the common things whereas Mu is still (naïvely) interpreted. On larger apps I think the gap might come down, since Python will start relying more on unoptimized primitives. But I should probably measure at some point..
(2) Lol. I actually modeled Mu's on JVM to some extent, so it's intended to be a better replacement of that layer of the stack, something that compiles down to native rather than relying on a bytecode interpreter, and also something that is designed with higher-order functional programming in mind, as well as generics out of the box (so no type erasure and so on).
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!
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.
Wow, that's more than a little enlightening.
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.
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.
> 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)
The Ariane 5 bug and a few lessons (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&...)
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?
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.
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.
I'll show myself out :)