13 ms·
Cap'n'Proto remote vuln: pointer overflow check optimized away by compiler
- deleted 10y ago[deleted]
- azinman2 10y agoIt'd be nice if there was a way that when compilers "re-write" or eliminate parts, those could be highlighted or otherwise nicely conveyed in our IDEs. I don't know why we expect phones and apps to have modern great UX, solving all kinds of problems, but our text editors should remain essentially the same as in the 70s.
- reitanqild 10y agobut our text editors should remain essentially the same as in the 70s Not everybody expexts that: I use sublime text for smaller editing tasks (although vscode and notepad++ are kind of ok too) and Visual studio or in my case preferably Netbeans for anything bigger (although I accept that this might sound weird). Only if I connect over ssh or work on a console I prefer vim. Edit: also my preferred IDE already does something similar by telling me whenever it thinks something can obviously be simplified or written in a more idiomatic way.
- adrianN 10y agoThat would be a nice research project for a PhD or two, but I think it will be very difficult to present optimizations in a way that is useful for the programmer. In this case for example the optimization concerns an inline function. The compiler might optimize it in completely different ways depending on the context. How do you present that in the editor? It would also make compilation much slower, I think, because you have to schlepp around all the information that you use for the optimizations. There are some tools that go in that direction. For example clang can help you help the optimizer auto vectorize loops: http://llvm.org/docs/Vectorizers.html#diagnostics http://llvm.org/docs/Vectorizers.html#diagnostics
- azinman2 10y agoTo both replies so far, I'd say open your mind a bit. Think about it this way... email was invented long, long ago, yet people have moved onto facebook and snapchat and instagram and all these completely different experiences there are more nuanced and richer. If you squint your eyes, programming is basically the same.... there are vast opportunities to change how it fundamentally works. Having feedback loops from the compiler into your source code (it can be visualized in a wide number of ways) is just one area that's low-hanging fruit that could also help with such security vulnerabilities.
- BuuQu9hu 10y agoHi, compiler author here. You're not being downvoted for your POV, but because you're not grokking that the thing that you are asking for is fundamentally difficult. Nearly all serious compilers have at least one representation which is not isomorphic for all programs. (It is homomorphic, which is required for the compiler to be correct.) As a consequence, at least some programs will be mangled beyond recognition.
- azinman2 10y agoHi, creative programmer here. Just because it's hard doesn't mean it isn't worthwhile to do, or that everything the compiler does must be reserved and shown in the IDE. I'm also not suggesting that this compiler feedback is the only IDE improvement we make. I'm observing that the entire way we develop software hasn't fundamentally changed in decades, yet every other aspect of computing has. Even something that roughly seems the same like word processing is now collaborative and in the cloud with real-time updates and social threads. Light table is one IDE that is trying to question some assumptions -- like that files are important and that everything must be 1 line spaces apart in mono font. This is the kind of progress I'd like to see. It does seem reasonable that there be a way, even if difficult, to highlight a bounds check that gets optimized away. If we start from the problem we're trying to solve (show eliminated code that poses security risks... such as bounds checks or erasing memory) rather than the general problem (reverse all compiler changes), then things become more tractable.
- chrisseaton 10y agoThe 70s era bit of this is the thinking that compilers 'sometimes re-write parts' of your program. Really they completely break your entire program down and then build it up from the ground again. Everything would show up as having been rewritten.
- rainforest 10y agoIn this specific case an IDE could conceivably highlight a check that the compiler will omit, or point at undefined behaviour directly. The general aim is probably unachievable as you suggest - if 3 functions are rewritten to one it'd be hard to point out where the change was applied.
- johncolanduoni 10y agoMost C/C++ compilers support outputting line number information even for optimized code (DWARF for example has a specific mechanism for identifying inlined code in stack traces). That's more than enough location data to provide something useful.
- MaulingMonkey 10y agoSeeing e.g. the original source in the disassembly window is useful. And the same info lets you do things like: https://gcc.godbolt.org/ https://gcc.godbolt.org/ Taking that information into any sort of "yeah, this still represents the original intent of the author" highlight/lack of highlight/summary as it sounds like azinman2 wants might be a little more difficult. (After all, if you can implement that, why not have your compiler only emit 'sane' code in the first place?)
- nickm12 10y agoThis isn't the first security vulnerability caused by optimizing compilers assuming programs don't exhibit undefined behavior and it won't be the last. Some relevant literature: https://people.csail.mit.edu/nickolai/papers/wang-undef-2012-08-21.pdf https://people.csail.mit.edu/nickolai/papers/wang-undef-2012... http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf http://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_201...
- mpweiher 10y agoAnd the claim that this is not a bug in the compiler is laughable. All this is stuff that used to work. The compiler changed and now removes code. That's a compiler bug.
- frederikvs 10y agoThe standard says the compiler is allowed to make that change. The standard says the programmer writing that piece of code is wrong. So no, it's not a bug in the compiler, the compiler is complying with the standard. You could make a case that it's a bug in the standard though :-)
- mpweiher 10y agoNo, the compiler is interpreting the standard in a particular way. It doesn't have to do this. I had a C compiler (paid for it) before there was a C standard. So in your opinion, this compiler could do anything at all and nothing could possibly ever be a bug. UPDATE: A lot of mindless downvotes, but no actual substantive rebuttals. As expected.
- kutkloon7 10y agoWell, of course the author of the compiler could argue that the compiler is bug-free, and all behavior is intentional. While this would be laughable in most cases, there is no 'hard evidence' that this is not the case. A standard is needed in some cases where there is no 'obvious' behavior. I think this is the way that the 'Ruby standard' is defined, by a reference implementation which is assumed to be bug-free. About the interpretation of the standard: this is probably true, but this kind of technical documents is meant to be mono-interpretable, if you know what I mean. Ultimately there might be a few limitations which you don't encounter in practice (if you give your variables names of more than 4k characters, I doubt if it will compile), so you might argue this is an 'interpretation of the standard'. I would argue that in such a case technically, the compiler doesn't comply with the standard, but for all purposes and intents, it does (and so, in practice no one would doubt that the compiler complies to the standard).
- cperciva 10y agoAmusingly, the "technically-correct solution" is also incorrect, albeit probably well-behaved on most widely used systems. Rather than comparing pointers, they cast to uintptr_t and compared those, but as I commented on the commit in github: This is not guaranteed to work. C guarantees that casting a pointer to a uintptr_t and back results in a pointer which compares equal to the original; but it does not guarantee that (uintptr_t)p + 1 == (uintptr_t)((char *)p + 1), that p1 < p2 is equivalent to (uintptr_t)(p1) < (uintptr_t)(p2), or even that (uintptr_t)(p) == (uintptr_t)(p); an evil but standard-compliant compiler could implement casting from pointer to uintptr_t as "stash the pointer in a table and return the table index" and casting back as "look up the index in the table".
- unwind 10y agoAgreed. I don't see any comments on the commit though (assuming "the commit in github" is the first link in the article, i.e. https://github.com/sandstorm-io/capnproto/commit/52bc956459a5e83d7c31be95763ff6399e064ae4 https://github.com/sandstorm-io/capnproto/commit/52bc956459a...). Is there another commit? Also, I'd be very interested in hearing a suggestion as to how this should be implemented. Of course you might have mentioned that in the comment I can't find, so don't repeat it if a link suffices of course. I'd look into working explicitly with uint64_t, and stop doing pointer subtractions. EDIT: Here's the technically correct code from the bottom of the advisory, that I failed to see: https://github.com/sandstorm-io/capnproto/commit/2ca8e41140ebc618b8fb314b393b0a507568cf21 https://github.com/sandstorm-io/capnproto/commit/2ca8e41140e....
- cperciva 10y agoThere's a link at the bottom of the article to "A technically-correct solution has been implemented in the next commit". Also, I'd be very interested in hearing a suggestion as to how this should be implemented I don't know enough about the problem space to say for certain, but in general I'd say that "work with unsigned integers and convert them to pointers only after performing all necessary sanitization" is good advice.
- 10y ago
- m_eiman 10y agoIs there a way to make the compiler list the applied optimizations for a specific function, in e.g. the .lst output? Would be very helpful when the compiler is doing something creative and you can't figure out how to make it do what you intended.
- adrianN 10y agoYou could start by not relying on undefined behavior ;)
- mpweiher 10y agoCompiler writers could/should start by not treating undefined behavior as blank checks. This is so idiotic, and no, it's not a bug in Cap'n'Proto, it is very definitely a bug in the compiler (and/or the current version of the C spec. if it actually allows this).
- frederikvs 10y agoThe C standard allows the compiler to do this, so it's definitely not a bug in the compiler.
- mpweiher 10y agoAs I wrote earlier: I had a C compiler before there was C standard. So by your definition, this compiler could not have bugs? As an exercise, try to express the difference between "standards-compliant" and "bug-free".
- kutkloon7 10y agoI think the main point is that if there is a standard, an implementation should comply. If there is no standard, you have to use intuition and common sense to say what's a bug. Different people may have different expectations, so bugs become subjective. Ideally, there is a water-tight standard. In this case every deviation from the standard is a bug and vice versa.
- kutkloon7 10y agoFor people claiming that this is a compiler bug, it really is not. I am no expert, but what I understood is that the C standard defines some situations (such as an overflow error) which result in "undefined behaviour". In this situation, the compiler is free to do whatever he wants. This is in fact what happens here. This is clearly annoying to programmers. In this case, it is even hard to avoid undefined behaviour even if the source of undefined behaviour (a pointer overflow) is known. Why is this done? This way the compiler can do some aggresive optimizations which are only valid if there is no undefined behaviour (e.g. no overflow, null pointer acces...). There are various good articles about this. To make the situation more complex for programmers, it is possible to write programs which exhibit undefined behaviour but work fine in practice. Until the compiler tries to do a specific optimization. This is basically why you shouldn't use C. Long-time C programmers know a list of operations which are undefined behaviour, and are usually able to point out a few of these in a program written by newbie (ironically, these programs may run and pass tests just fine).
- frederikvs 10y agoTo be specific, only certain types of overflow are undefined behaviour. Signed integers and pointers have undefined behaviour on overflow. Unsigned integers on the other hand are defined to wrap around to 0. For those interested, good places to start learning more about this are John Regehr's blog [0], or the llvm blog [1]. [0] http://blog.regehr.org/archives/213 http://blog.regehr.org/archives/213 [1] http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
- cperciva 10y agoTechnically unsigned integer wrapping isn't considered to be "overflow".
- cperciva 10y agoReplying to myself because it's too late to edit the comment: I'm not sure why people are voting that down. Section 6.2.5 paragraph 9 of the C99 standard states that: A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
- lmm 10y agoI thought sandstorm was supposed to be a security-focused project? But they're writing new C code and connecting it to the Internet. And surprise surprise, this happens. Fuzzers will catch a certain proportion of this type of problem, sure. But for a ground-up project like this there's really no excuse not to use a better language.
- _pmf_ 10y agoI'm usually not in the No-C camp, but your argument (new software with focus on secure infrastructure) is actually solid.
- detaro 10y agoThere is also a Rust implementation, which is the one Sandstorm uses as far as I know.
- staticassertion 10y agoIs there a source for this? I was unaware.
- steveklabnik 10y agohttps://github.com/dwrensha/capnproto-rust https://github.com/dwrensha/capnproto-rust
- staticassertion 10y agoThanks, this is what I was looking for (found through your link): https://github.com/sandstorm-io/collections-app https://github.com/sandstorm-io/collections-app So it does seem to be the case that they are using the rust version here. That's nice.
- kentonv 10y agoDynamic languages are susceptible to their own kind of security bugs. I've found lots of bugs in Node apps where they accepted some JSON from the client and then passed it directly into a Mongo query without type-checking it. Or look at Ruby's YAML security issues. Nearly every language is vulnerable to integer overflow. C++ is one of the few languages (possibly the only popular language) where you can reasonably check for overflows at compile time, as Cap'n Proto now does: https://capnproto.org/news/2015-03-02-security-advisory-and-integer-overflow-protection.html https://capnproto.org/news/2015-03-02-security-advisory-and-... So, I don't accept the assertion that C++ is inherently a security problem. In any case, Sandstorm's low-level container management bits pretty much had to be written in C/C++ since they interact closely with the operating system. Or if we were starting over today, Rust might now be an option, but it wasn't when we started.
- jononor 10y agoWe need a -Wundefined-behavior, which can be used in combination with -Werror. It is a practically impossible job to be so aware of the standard while working to get this right without assistance.
- masklinn 10y ago> We need a -Wundefined-behavior, which can be used in combination with -Werror. The problem is that you probably won't be able to use any optimising compiler if you do that. As a result of a bunch of optimisation (mainly inlining) the compiler "uncovers" lots of UBs which it can use to pare down the code, that's why inlining is one of the most important intermediate/early optimisation. Here's an old example by mikeash: int ComputeStuff(int *value) { if(value == NULL) { long and complex computation for a NULL value return result } else { long and complex computation using the data pointed to by value return result } } void DoStuff(int *value) { int pointedTo = *value; // value *must* be non-NULL // do some work with pointedTo int computedResult = ComputeStuff(value); // do some more work with whatever } Here the compiler can inline ComputeStuff, at which point it can rely on UB to assert that half the inlined code is dead and can remove it. What would it even do on "-Werror -Wundefined-behavior", fault on the original DoStuff? On the inlined one? On both? Would -Wundefined-behaviour forbid assuming a pointer is non-null ever, requiring (and outputting) a check before each use of a pointer in a given scope/lifetime?
- jononor 10y agoFor such inlining optimization it is the compiler that 'introduces' the UB in its intermediate step. That is not a fault of the input code, so no warning should be emitted? If the compiler can know that the pointer is non-null, why would it need to rely on UB to optimize it? Problem I guess is the ever-present possibility of pointer aliasing and such nearly allowing anything to change anything else at any time... Not easy making things more sound on such a foundation.
- derf_ 10y ago
- deleted 10y ago[deleted]
- jbb67 10y agoThis is a broken compiler. It might well meet the "standard", but it's still broken because it doesn't do what any reasonable person would expect it to do.
- kutkloon7 10y agoWhich means the standard is broken, not the compiler.
- Pxtl 10y agoPlease tell me this reply is a joke. If not, the irony is hilarious.
- jjnoakes 10y agoI don't know why you think my reply is a joke. The person I replied to basically said (paraphrasing) "compilers which optimize based on undefined behavior and follow the standards are written by idiots", and I don't think that's accurate by any stretch of the imagination. Now, if you want to talk about changes that should perhaps be made to the standards, that's a different discussion all together (and also has nothing to do with intelligence, since the UB in the standard today is there to facilitate portability and optimizations, both of which are highly important to C and C++).
- geocar 10y ago> The person I replied to basically said (paraphrasing) "compilers which optimize based on undefined behavior and follow the standards are written by idiots" That's not what I said, it's not what I meant, and I don't think a reasonable person reading my statement would interpret it that way. That you think I'm stupid simply because you didn't understand what I meant, is a common programmer trait, and I don't think it's a good one.
- jjnoakes 10y agoWhere did I say I thought you were stupid?
- lawnchair_larry 10y agoI think I understand your sentiment, but it doesn't apply here. Folks arguing technical correctness in the context of compilers and the C standards are not doing so in order to be pedantic over hypotheticals. Being "technically correct" is important in C because compiler authors reasonably take many liberties in order to improve both compile-time and run-time performance, not to mention reducing cost and complexity of developing the compiler itself. C makes certain guarantees, and compilers will take those for granted where it benefits them, rather than conservatively analyze for situations that are theoretically impossible. You can't say a compilers is dumb because the user gave it invalid code, and in no way is this hiding behind technicalities. It's also not much of a stretch to say that invoking undefined behavior can do things like delete everything on your hard drive. In fact, I've seen it happen many times. Any memory corruption exploit fundamentally relies on the fact that the author invoked undefined behavior. Although it may be undefined, it's still deterministic, so an attacker can construct an input that abuses the failure modes of your particular implementation to run arbitrary code of their choosing, like spawning a shell process and binding it to a port, or fetching some malware. C guarantees that none of this can happen, but when you don't follow the rules of C, they really do mean it when they say anything can happen. It's not because the compiler authors are being trolls and feel entitled to delete your files or launch a rocket out of spite. It's because your machine is now executing who-knows-what.
- willvarfar 10y agoC/C++ coding standards I've seen always warned against using unsigned to mean "cannot be negative", because of precisely this kind of bug. The standards I'm recalling were in-house standards, but a quick Google shows that Google have published their standard and they warn against unsigned too: https://google.github.io/styleguide/cppguide.html#Integer_Types https://google.github.io/styleguide/cppguide.html#Integer_Ty... Bottom line: avoid unsigned for numbers. Use unsigned only for bags of bits.
- esrauch 10y agoI think the situation is a lot more nuanced than that. The issue was that additition overflow is undefined behavior for both signed ints and pointers (but it is defined for unsigned ints). The fix commit changes it to use an unsigned integer type instead, so it seems like a concrete example for the exact opposite of your suggestion.
- raverbashing 10y agoI'm going to be honest here, whenever I read things like this more I'm convinced C belongs in the trash can I would accept that pointer overflow is implementation dependent. Allowing it to be "undefined behaviour" is sincerely BS. Every processor has a "pointer register". Increment it until it overflows. What happens then? Most of the time it will roll over. I suspect this happens in even early RISC architectures that faint if you look at it too hard. There's your answer It's right, it's not a compiler bug. C tries to solve all problems and cops out on the real issues. The language is broken.
- banachtarski 10y agoNo, it's definitely a compiler bug here.
- banachtarski 10y agoThere is no undefined behavior here? Unsigned overflow wraps around and this is correct. Always has been in C++ for as long as I can remember.
- detaro 10y agoI don't think pointer arithmetic is defined to behave as unsigned. Unsigned is the exception in that it's overflow behavior is defined.
- kentonv 10y agoUnsigned overflow wraps around, but signed and pointer overflow are UB. In this case, the code was depending on pointer overflow wrapping around.
- banachtarski 10y agoedit: oh gosh I totally misread something > Since farPointer.offset is an unsigned number, the compiler is able to conclude that target < segmentStart always evaluates false. Thus, the compiler removes this part of the check. Unfortunately, in the case of overflow, this is exactly the part of the check that we need. This certainly seems like a compiler bug!