In February 2014 Apple published their Secure Coding Guide. I glanced through it and noticed that their sample code for detecting integer overflow was buggy – it triggered undefined behavior, could be optimized away, and was thus unsafe to use.
I tweeted this, then Jon Kalb blogged it, and then Apple quietly fixed their guide.
But their code is still broken, still triggers undefined behavior, and fails completely on 64-bit builds.
Update, June 17, 2014: no change. Apple’s security guidance is still entirely broken for 64-bit builds.
Update, August 6, 2014: No change. Apple’s security guidance is still entirely broken for 64-bit builds. The document was updated 7/22/2014 but the revision history gives no indication of what changed, and page 28 is still completely broken for 64-bit builds. And yes, this does matter.
Apple’s Secure Coding Guide is available here. And I think the guide is mostly correct. But they sure are having trouble with detecting integer overflow. To be fair, it is tricky, but still. They should be able to do better.
The problem is on page 28, in their “Avoiding Integer Overflow and Underflows” section. This page contains two code snippets. The first is an example of a common mistake, and the second is Apple’s recommended guidance on how to avoid integer overflow when multiplying.
The original problem
Their recommended code originally looked like this:
size_t bytes = n * m;
if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
… /* allocate “bytes” space */
}
The types of ‘n’ and ‘m’ are never mentioned, which is unforgivably ambiguous for a security document. If you carefully read the surrounding text and its discussion of undefined behavior on overflow, in particular its reference to CWE-733, CERT VU#162289, it is clear that ‘n’ and ‘m’ are both signed integers. If they were unsigned then their previous discussion about the C language specification allowing compilers to optimize out the tests makes no sense.
Unsigned overflow is defined to “obey the laws of arithmetic modulo 2^n”
The problem with their initial recommended code is that signed overflow gives undefined behavior in C/C++. It doesn’t matter if the results of the signed overflow are never used – the entire execution of the program is undefined as soon as signed integer overflow happens. Since Apple did the check for overflow after doing the multiply they have closed the undefined door after the metaphorical horse has left. They checked too late. If ‘n’ and ‘m’ overflow then the compiler is permitted to launch nethack, format your drive, or sing sea shanties in Spanish.
(Singing sea shanties in Spanish requires the optional voice module, or an embedded web browser for multimedia functionality)
More practically speaking (since most compilers are not actively evil), an optimizing compiler could detect that the checks are unnecessary, and omit them, thus creating a perfect example of security theater.
(Examples of deleted security checks due to undefined behavior can be found here)
Some optimizing compilers exploit undefined behavior by using it to prune the state tree. Since signed integer overflow is undefined the compiler is allowed to assume that it cannot happen. Therefore, at the time of the ‘if’ statement the compiler is allowed to assume that n*m does not overflow, and the compiler may therefore determine that the overflow checks will always pass, and can therefore be removed. We loves the optimizations.
This is not a theoretical concern. Serious security bugs have happened because compilers removed checks that were provably unnecessary due to undefined behavior.
In short, you have to check for overflow before you overflow. Doing the signed integer overflow and then checking is not legal.
The new problem
At some point Apple quietly fixed their document. They didn’t change the date (the footer still says February 11 but the properties now say March 10) or acknowledge the error (the revision history is silent), but they fixed the code. This is now their recommended code for avoiding integer overflow when multiplying:
if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
size_t bytes = n * m;
… /* allocate “bytes” space */
}
Much better! Except not really.
They now avoid doing the multiplication until they have done the check, but their code is still wrong.
SIZE_MAX is the maximum value of a size_t typed variable. We’ve already established that ‘n’ and ‘m’ are not size_t types – they appear to be signed integers. The maximum value for a signed integer is INT_MAX. Apple is using the wrong constant!
In order to avoid integer overflow (undefined behavior, dragons be here) they either need to check against INT_MAX instead of SIZE_MAX, or they need to cast ‘n’ and ‘m’ to size_t before doing the multiplication.
The fact that the result of the multiplication is assigned to a size_t is irrelevant. The multiplication is a signed integer multiplication, it produces a signed integer result, and this result is then converted to a size_t during the assignment.
When compiling 64-bit code this is a disaster. For 64-bit code the value of SIZE_MAX is 2^64-1 and (assuming 32-bit integers) there are no values of ‘n’ and ‘m’ that could possibly exceed it, so all positives values will pass the test. For a 64-bit build Apple’s code offers precisely zero protection. goto fail. Do not pass go. Do not collect $200.
When compiling 32-bit code the outcome is not so clear. On every CPU I have ever used a signed multiply gives the same results in the bottom word of the result as an unsigned multiply, so it is highly likely that the result will always be correct. But the behavior is still undefined. And anytime you find yourself saying “I’m sure that this undefined behavior won’t matter” you should make sure you aren’t working on software where security matters. And you certainly shouldn’t be writing security guides…
Code that works
The code below should work – and I hereby license this fixed version to Apple with the only requirement being that they acknowledge the original errors so that developers who followed their advice might hear about the problems:
if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
size_t bytes = (size_t)n * (size_t)m;
… /* allocate “bytes” space */
}
If using C++ then you could also use numeric_limits<>::max() and a typedef to ensure that your MAX values match your types.
This stuff is crazy tricky. If you want to get serious about this you should check out SafeInt, for code or for ideas. Or check out this guide (mentioned in the reddit discussion):
Maybe they meant size_t
One could argue that Apple’s code is fine as long as ‘m’ and ‘n’ have type size_t. That is true, but that supposition is just not supported by the surrounding text. And, if ‘n’ and ‘m’ are intended to be of type size_t then that needs to be explicitly stated. Failing to list such a crucial requirement is absolutely unforgivable.
Perspective
It’s nice to take a break from critiquing Microsoft…
Random ASCII - tech blog of Bruce Dawson 
I’m pretty sure that in your zeal to fix the real bug, you managed to introduce a harmless one into your logic:
> In order to avoid integer overflow (undefined behavior, dragons be here) they either need to check against INT_MAX instead of SIZE_MAX, or they need to cast ‘n’ and ‘m’ to size_t before doing the multiplication.
Actually, casting either ‘n’ or ‘m’ is sufficient.
Yes, casting just one of them would be fine. I like the symmetry of casting both of them, so I allowed myself a slight exaggeration in my rhetoric.
I feel it adds readability, eliminating any doubt about what type is actually being evaluated
Actually, while on any reasonable platform casting only one of ‘n’ or ‘m’ is sufficient on a strange platform that has int types having a greater rank than size_t types casting both values is required.
I don’t see how, if int has a greater rank than size_t, then there are two options:
1. numeric_limits::max() > numeric_limits::max() and in that case, because size_t has lesser rank, it can be promoted to signed int or unsigned int due to integral promotions. Because in this case int cannot represent all possible values of size_t, it is promoted to unsigned int. And now the binary multiplication operator, seeing signed and unsigned type of the same rank, will return unsigned result.
2. numeric_limits::max() <= numeric_limits::max() – in this case, the check in the line above (SIZE_MAX/n >= m) is enough to ensure that there is no integer overflow.
so, wordpress ate my template parameters.
errata:
1. numeric_limits{size_t}::max() > numeric_limits{int}::max()
2. numeric_limits{size_t}::max() <= numeric_limits{int}::max()
If you’re going to be pedantic, please be pedantic in a way that clearly expresses the INTENTION of the program and falls as far as possible on the side of safety and unambiguity as you can, without breaking the meaning of the program or increasing the difficulty of humans to understand it. Any other form of pedantism is simply obnoxious and counterproductive. Got that? Ok, thanks! Bye!
The original statement wasn’t entirely correct and I pointed that out. No need to get snippy about that.
For readability, I agree that casting both is better, but I would probably recommend static casts or constructor-style casts and, more importantly, not doing all this in a single line in the first place.
Reading this post is like reading a Harry Potter novel: the winy analyzing over something very unimportant.
“One could argue that Apple’s code is fine as long as ‘m’ and ‘n’ have type size_t. That is true, but that supposition is just not supported by the surrounding text.”
Hey Apple, put this entire post to waste by:
size_t n,m;
…
if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
size_t bytes = (size_t)n * (size_t)m;
… /* allocate “bytes” space */
}
Sorry you think it’s winy [sic], but as recent news (heartbleed, Apple SSL fail, etc.) have shown, tiny errors in security code matter. Apple’s advice is wrong. Dangerously wrong. They need to fix it. Your fix would be fine, although personally I prefer the cast to size_t as being more idiot-proof.
I’m more “winy” that I just had to rekey all of my SSL certificates. The road to fail is paved in goto intentions.
There is also ANOTHER bug in that documentation
The docs said that this is bad because of undefined behavior potentially removing the ‘if’ check
size_t bytes = n * m;
if (bytes < n || bytes < m) { /* BAD BAD BAD */
… /* allocate "bytes" space */
}
Forgetting about UB for a moment, This works if, as proposed by the guide, n or m is negative. But it doesn't protect against all kinds of overflow.
The snippet is wrong. The following code passes that tests, even though the multiplication is clearly overflowing and there is no undefined behavior:
uint32_t a = 100000;
uint32_t b = 100000;
uint32_t val = a * b;
int32_t val2 = (int)val;
cout << val << endl;
cout << val2 << endl;
Both val & val2 result is 1.410.065.408; which passes the test 'if (bytes < n || bytes < m) but does not pass 'if (n > 0 && m > 0 && SIZE_MAX/n >= m)’
The Apple security guide is comparing broken code with functioning code, claiming that Undefined Behavior is the reason the broken code is broken (it’s not just that); and claiming that the 2nd snippet is free from UB (which as you pointed out, it’s not).
That’s a double fail. Triple fail if you consider they “fixed” the snippet and was still wrong.
The original author clearly doesn’t understand what’s going on*, or is too lazy to care.
*To be honest, the C/C++ standard is incredibly complex. It’s understandable, but not an excuse.
For 32-bit on some processors it’s simple. For example, ARM has an instruction that can do 32bit x 32bit = 64bit result. After the multiply, you check top-32bits if non-zero then you have a problem, otherwise the bottom-32-bit result is ok.
My post meant “unsigned” values. For sign, it’s a little bit more work, but similar concept.
I’m sure all processors have a 32×32=64 multiply instruction. To access it from C/C++ you have to cast the inputs to 64- bit.
Just one page behind from where you quote the snippets (pg 27); it’s written:
>>Also, any bits that overflow past the length of an integer variable (whether signed or unsigned) are dropped.
Overflow for signed integers causes Undefined-Behavior, not just dropping the overflowing bit.
I don’t understand, where are they doing with this !!
Truly odd, I agree.
For unsigned n and m, the check `n > 0 && m > 0` isn’t needed, the multiplication couldn’t overflow.
The check for ‘n > 0’ is needed to avoid a divide-by-zero. I agree that the check for ‘m > 0’ is odd. I guess they want to treat an attempt to allocate zero bytes as an error, but that is a completely separate decision from trying to avoid integer overflow.
For the specific case of allocating a buffer of q = m*n bytes, it seems to me that it would be more secure to sanity check m and n instead of worrying about multiplication overflow.
Even with overflow prevention, naively allocating m*n bytes, where m and n are untrusted, will allow a DoS attack through the allocation of an arbitrarily large block of memory.
Set a design target on the maximum valid value for m and n and cap them there e.g.
uint32 SaferM = min(MAX_M, abs(m));
uint32 SaferN = min(MAX_N, abs(n));
uint64 q = (uint64)SaferM * (uint64)SaferN;
if (q > 0 && q < MAX_Q) ptr = malloc(q);
Agreed, that can be better, in many domains. Many image decoders clamp width/height to 16Ki or 32 Ki in order to avoid overflow. The downside is that you end up with image editors that refuse to load some images — I have images of the earth that are 43,200×43,200 and lots of programs won’t touch them.
If you’re trying to prevent DoS attacks then clamping the total size is more appropriate, so that someone can still create, say, request 200,000×10 items.
“The problem with their initial recommended code is that signed overflow gives undefined behavior in C/C++.”
This is incorrect and I wish people would stop spreading this incorrect interpretation of the standard.
That standard states that IF the underlying architecture has undefined behavior for signed integer overflows than the behavior will be undefined, however, if the behavior of signed integer overflows is defined by the architecture the emitted code will follow the same rules. As far as I can recall, every major architecture in use today not only has well defined signed integer overflow behavior, but uses essentially the same rules for it.
In other words, the compiler is required to preserve the behavior of the underlying architecture the code is running on, and on every major architecture in use today that is well defined. Optimizing out those sign checks is invalid.
I believe the intention was that compilers should not be required to emit additional code to change the behavior, but are just required to maintain it.
It is worth noting that the GCC developers have horribly misinterpreted this as well, so while the standard DOES define what to expect, there have been non-conforming implementations in popular use.
Do you have a reference for your claim that signed integer overflow is defined? From my reading of the C++ standard it is clearly not. Section 5/4 of the draft C++14 standard says:
“If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.”
They later explain that unsigned math is expected to follow modulo 2^n rules, so this doesn’t apply to unsigned math, but I have seen no similar escape valve for signed arithmetic. I think that if gcc/clang were misinterpreting the standard then somebody on the C++ committee would have pointed it out by now.
I agree that all modern computers implement signed arithmetic identically, but the C/C++ standard tells us not to rely on this. I am not convinced that this is a good idea, but it is what we have.
Of course, the code is still broken for 64-bit compiles, regardless of the state of undefined behavior.
Looking at the C99 and C++11 draft specs (the only ones I had available at the moment), I was unable to find the section I mentioned. I originally found it in a copy of the spec linked as proof for the GCC debate on the subject, and I’m not sure which version it was. I’m assuming early ANSI C perhaps?
I concede that the section I referred to has apparently been removed.
However, there are other things which clarify this as a non-conforming defect.
I put together a quick test in GCC in which optimization breaks behavior of signed int wrapping. In this test, std::numeric_limits::is_modulo returns true.
Regarding is_modulo the C++11 spec states:
“True if the type is modulo. A type is modulo if, for any operation involving +, -, or * on values of that type whose result would fall outside the range [min(),max()], the value returned differs from the true value by an integer multiple of max() – min() + 1.”
Per the C++11 spec (as well as LIA-1), by defining it’s signed int implementation as modulo it’s required to wrap on overflow.
I tried the same test with clang, which also stated signed int was modulo, and thus must wrap on overflow. My simple test did not break under clang’s optimization.
I suppose my original statement should be changed to state signed overflow IS defined when an implementation defines signed types as modulo, which is true of at least gcc and clang.
We don’t want to be writing code whose behavior is different based on the implementation of the language specification. If the specification said anywhere that the behavior of signed integer overflow is left up to the implementer then avoid it like the plague. For [another] example, if the language specification leaves the sign of ‘char’ to be decided by the implementation then will you take a chance or will you check every time to know for sure and never assume the sign? Also in C++11 under fundamental types section 3.9.1, footnote 46 states ‘This implies that unsigned arithmetic does not 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 unsigned integer type.’ And there is no corresponding footnote for signed integer overflow or lack thereof, presuming that the standard deals with overflow differently in the context of signed integer versus unsigned integer.
I suspect the bug is that gcc an clang are incorrectly setting is_modulo, and they will correct how they set it. I agree with Robert that having signed overflow defined for some compilers/settings is dangerous. I think I’d like to see it defined for all conforming implementations.
is_modulo is correct for all hardware which uses two’s compliment for storing signed values, as that is the behavior caused in two’s compliment on overflow.
The idea of signed int overflow being undefined is due to when the C language was originally drafted there had been other methods of storing signed values in use, specifically one’s compliment, in which signed int overflow did not have a mathematical definition. Requiring specific behavior for non-two’s complement hardware would have required significant additional code emitted for every signed integer arithmetic operation.
As far as I am aware there is no modern architecture which does not use two’s complement representation of signed integers, and given how entrenched two’s complement is as well as the myriad of benefits it has, I have serious doubts anyone will consider not using it.
I do not agree it is dangerous nor that it should be avoided to rely on this behavior at this point. If you feel your code could be at risk you should be able to add a static assert against std::numeric_limits::is_modulo, though it should be true for every modern architecture.
The only “problem case” I’m aware of is GCC’s current optimization behavior, which due to the definition of is_modulo providing a mathematical definition for signed int overflow I strongly say is erroneous and non-conforming behavior on GCC’s part.
Is this straightforward? No. Should it be better explained in the spec? Yes. Should signed int overflow undefined? Given it being defined as modulo on all modern architecture, IMO, no, it should not be treated as undefined, as there is a clear mathematical definition.
I think you are correct that the ‘only “problem case”‘ is gcc’s/clang’s current behavior, but that’s a pretty big if.
The reason I often hear for leaving signed overflow undefined is that it allows some constructs to be compiled to significantly faster code. That is, it allows some valid code constructs that do not overflow to generate faster code than if signed overflow was defined to have modulo behavior. I’m sorry that I don’t have references handy right now.
I’m not saying that I agree with this calculation, but it is something that has to be understood and addressed on the road to defining signed overflow.
Git has a (imho) very elegant solution for signed/unsigned addition – extending to multiplication would require turning it into a function (to avoid evaluating the arguments twice) or requiring that the operands be nonzero.
It’s at https://git.kernel.org/cgit/git/git.git/tree/git-compat-util.h
Not bad. It has the usual macro problems of potential double evaluation, and it also has the requirement that a be >= 0, and that the types match. So, it is safe as long as it is used very carefully. I’d prefer an inline template function to make it truly safe.
Still, it does show some good techniques.
If you reported it and it got fixed last time, I’m gonna make the bet that someone at Apple will read the comments: just use Clang’s checked arithmetic builtins (http://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins) and be done with it. They’re more expressive and visibly safer.
This time I sent e-mail to product-security@apple.com with the full set of concerns. They said they will address my concerns in a future version of the guide.
Intrinsics would be a good idea. It is hard for developers to write C/C++ code that does significant math on arbitrary numbers without hitting undefined behavior. SafeInt and other efforts try to make it easier, but it’s still complex. Intrinsics that exploit the CPUs carry and overflow flags would be very helpful.
Or, how about something like this:
if (safeeval(result = x + y * w + 7))
p = malloc(result);
else
// Handle failure.
A compiler can safely evaluate that expression in machine code far more easily than a developer constrained by C/C++.
Apple has a separate website for submitting bugs, it may be more helpful in the future then sending an email (or do both and reference the bug number in the email). https://bugreport.apple.com/
If they meant size_t, it’s a different problem, as size_t is unsigned and unsigned overflow is not undefined behavior in C. In the specific example (allocating space for n items, each m bytes long), all values are by their nature positive or zero, so all the work should be done in unsigned values anyway.
The proposed fix is still not ideal, and size_t is a poorly chosen type to handle this sort of problem. The first problem is that the code uses division at all. A div instruction is very expensive. If we’re assuming a 32-bit signed input, then the best and easiest thing to do is to just do this:
__int64 ret = (__int64)x * (__int64)y;
if (ret > 32) != 0) complain;
It also doesn’t reject 0 as a legal input. And yes, signed overflow is indeed undefined by the standard, and _some_ compilers will indeed remove non-standard code. Their example is broken. This approach also only incurs a couple of extra instructions and doesn’t waste expensive instructions on something we won’t use later in the common case, which is that it won’t overflow.
An additional problem is that the typical intent when we’re accepting 2 ints as sizes is that the size of the allocation also ought to fit into a 32-bit int – very likely all sorts of internal structures think that 2GB ought to be enough memory. So the fixed version that would calculate a 64-bit size_t (and never overflow, so the division isn’t needed) could actually end up asking for up to 2^62 -1 bytes, and no practical allocator that exists today can do that.
BTW, SafeInt is fully supported on their compiler, and will quite happily solve most of the problem for them, except the part where the allocation size needs an artificial limit of INT_MAX, though it can be made to do it like so:
p = malloc( (unsigned int)(SafeInt(x) * y) );
This will first check that the multiplication doesn’t overflow an int, and then the cast checks whether it ended up negative, and because a non-negative int won’t exceed 2^31-1, you now have an upper limit.
Pingback: Undefined Behavior *Can* Format Your Drive | Random ASCII
Actually, I’m not sure that your (Bruce’s) assumption about m and n being signed is correct.
If you look at the if statement, it is checking if m and n are *greater than zero* and not that they are *greater than or equal to zero*. Allocating zero bytes (as would be done if m or n were zero) doesn’t make sense. Further, zero is a perfectly valid value regardless if you’re talking about signed or unsigned, so that portion of the if statement wouldn’t be nuked.
I do emphatically agree, however, that it is sloppy of Apple to not specify the types of m and n.
The most we can say with certainty about ‘m’ and ‘n’ is that they might be unsigned, so the behavior *might* be defined, which I think we all agree is pretty weak. However I think the surrounding text makes it clear that Apple assumes that they are signed, due to their discussion of undefined behavior earlier on the page.
The >0 check is compatible with them being signed or unsigned so it doesn’t help either way.
But, it’s all mostly irrelevant. The main remaining issue is that if ‘m’ and ‘n’ are 32-bit and size_t is 64-bit (true for any 64-bit build environment) then the code is 100% busted, regardless of whether ‘m’ and ‘n’ are signed or not.