Reallocarray() in OpenBSD: Integer Overflow Detection for Free
lteo.net
lteo.net
Here's just a completely random example from the Linux kernel: https://lkml.org/lkml/2014/8/19/194
> You are implying that such an overflow could arise in this code.
> This is false.
[...]
> bNumEndpoints is an unsigned 8-bit integer.
This mindset is exactly why vulnerabilities in C code are still common. It really needs to stop.
One solution to both of these problems I have thought about, but do not work at a low enough level to know if it is already a thing, is an opcode for unlikely branches. Sementiclly, this would behave like a normal jmp instruction, but the CPU branch predictor would always assume that the jump is not taken, and not bother keeping track of it.
In this particular case, it would also involve a way of signalling to the compiler (or the compiler inferring), but for loops it could be usefull.
Of course, in this case it is also possible that the compiler can infer that the branch can never be taken and remove it, so you really do not loose anything.
x86 actually does have jump instructions with branch prediction hints, but surprisingly modern CPUs will completely ignore those hints. Perhaps they never really caused large enough performance improvements to be worthwhile, or something.
> In this particular case, it would also involve a way of signalling to the compiler (or the compiler inferring), [...]
This functionality does exist, and Linux does make use of them. See the macros likely() and unlikely() at http://lxr.free-electrons.com/source/include/linux/compiler....
Itanium had the exact instructions you propose - look up ".dpxx" and ".spxx" for more.
The thing is that I don't care. I'm still an OpenBSD advocate and run it whenever I get the chance. I don't actually care about performance at that level. What matters more to me is consistency, and good man pages.
I imagine more people are like me, but the thing about performance measurements is they're quantifiable. They can be easily measured. We all probably over optimize to some degree, whether we're C developers or not.
There's just something satisfying about getting a quantifiably better score. This is why we get code that sacrifices almost everything for runtime speed.
FreeBSD and, especially, Linux have optimizations all over the place. A call to time(2) or gettimeofday(2) is hundreds of times faster in Linux than on OpenBSD. In most scenarios the difference doesn't matter. But it does matter in, e.g., an asynchronous network service with lots of events with timeouts being constantly registered.
I prefer OpenBSD, and I like that they focus on correctness, bugs, and more high-level features. I run all my personal services on OpenBSD. But commercially and at scale I run Linux, and treat each box as a throw-away in terms of security.
Got a link to those benchmarks? Did anyone file a bug report?
>But commercially and at scale I run Linux
Wouldn't netbsd be a better option?
Plus you also have to hack userspace. Most importantly you need to add VDSO support to the linker. Refactoring time(2) would be easy, but for higher granularity clocks--gettimeofday(2) and clock_gettime(2)--you need to make careful use of RDTSC and similar instructions for each architecture. _And_ you need to be able to test it well because of synchronization issues on older platforms. On x86, for example, RDTSC is synchronized, but for a long time it varied across cores, and when Intel and AMD fixed that there was a still a small product window where it could vary across CPU packages.
It really is an intrusive change.
Another way of looking at the matter is that you shouldn't change code that's already correct.
I could very well imagine a security auditor (who is not an USB expert) reading this code.
> Another way of looking at the matter is that you shouldn't change code that's already correct.
I personally find this kind of attitude extremely worrying. Perceptions about what is bad/good code or secure/insecure code have definitely changed since the first days of Unix. We shouldn't let code slip through the cracks just because it's old.
Some overflows indicate internal errors that should panic the kernel. Others are configuration or resource issues that can bubble up some errno value to user space. Some can have a fallback strategy: this calculation overflowed, try another one. Some overflows can be handled by "saturation" (a.k.a clamping): common in digital signal processing and supported natively in some DSP machine languages.
In other words, a silly patch that fixes a non-problem in one tiny place in a huge codebase doesn't accomplish anything. It's a big, wide-reaching task.
I don't understand this line of thinking at all.
"reallocarray()/kmalloc_array() doesn't fix all the possible integer overflow issues in C, so why bother using it at all."
Several people in this discussion have mentioned exact vulnerabilities that would have been prevented by reallocarray():
meowface: "Here is one of many examples of an integer overflow resulting in an improper size being passed to a memory allocation function further leading to remote code execution: https://docs.google.com/document/d/1tHElG04AJR5OR2Ex-m_Jsmc8... "
tedunangst: "You've never heard of the one openssh exploit?"
It was useless because several calculations take place in every instance to produce the size, whereas realloc_array only checks one multiplication.
On 64-bit machines, this means if you use 32-bit values and properly promote them, or one 32-bit value and one 64-bit value, you don't have to instrument.
Also, often times the better strategy is to design your code to be immune to overflow. Garbage-in is garbage-out, so if somebody gives you garbage then they can expect to get garbage out. All that matters is that you don't allow that garbage to taint the state of your program. I usually use unsigned arithmetic, because then I don't need to worry about undefined behavior in C. And for general bounds checking tasks my only condition is whether something is >= object-size.
Some of us rigorously analyze our code for overflow problems.
Those of you who don't are like the programmers from 20 years ago who thought that it was too tedious to do bounds checking on buffers, and that because of all the existing code it wouldn't improve security.
Well it did matter. Like with buffer overflows, it's a collective action problem. The dilemma you point out doesn't exist if you stop being so resistant to change.
Fixing some realloc calls is possible only because the function has an error return code, and so when the overflow occurs in the multiplication, it can "piggy back" on that null return. The hope is that the caller is already handling null properly and so everything is cool. (Is it? Was a test case ever executed in which that particular realloc call returned null?)
In general, multiplications in C take place in situations where there is no expectation of an error, and so no error handling strategy in place in the surrounding code. It may be difficult to introduce it, and even more difficult to test all the cases.
> I usually use unsigned arithmetic, because then I don't need to worry about undefined behavior in C.
That is wrongheaded, I'm afraid. The unsigned types behave poorly under arithmetic, because they have a large discontinuity immediately to the left of zero. And because their wrapping behavior is well-defined, it basically means that unintended wrapping is not diagnosable as an error (without generating reams of false positives).
It is unfortunate that size_t is an unsigned type. This is for historic reasons. When C ran on machines where size_t was 16 bit, making it signed would have meant limiting the size of an allocation request to 32767, rather than allowing up to 65535. That would have hurt, and induced people into workarounds such as writing their own allocators. (Which, ironically, they do anyway, to this day.)
Unsigned types are best used for things like bit fields, and simulating the arithmetic of particular machines. They are also useful for doing clock arithmetic on a wrapping interrupt timer register. (This is best done with macros or functions that safely wrap it, like "time_is_before(t1, t2)".)
"unsigned char" is useful, but note that values of this type undergo default promotion (on most compilers, by and large) to a signed value of type int.
For addition one method would be to subtract the maximum possible positive value. The only way to do that is to use a pre-defined macro. Which means the logic for your check is divorced from the actual operation--in other words, if the type of the operand changes, your check becomes _silently_ worthless.
The alternative exhibits at least _two_ bad security practices: 1) an independent constraint on input divorced from the risky operation is a recipe for bugs because you have no warning when the conditions change such that your input verification fails to properly constrain the values; and more generally, 2) relying on assumptions about a type, rather than relying on the actual behavior of a type or information derived directly from the type, is especially bad form in C because of its loose typing.
I think I'll stick with my strategy, which has worked out well, doesn't rely on undefined behavior, and is less susceptible to bit rot.
Regarding your objection of making changes to existing code, I would just say that we shouldn't let the perfect be the enemy of the good. I also like tedunangst's description of that predisposition: whataboutism.
if you're going to overflow a size_t, you're already in trouble. realloc is used for.. um, reallocating data. it's probably grown many times before you come close to exhausting 32 bits of size (assuming i386). if you are coming close to 4gb allocations, you're already likely running out memory. as such, you're program is probably going to be killed for using too much memory before you are in any risk of overflowing size_t.
similarly, in a 64bit runtime.. well, you will certainly be killed by the kernel before you come close to overflowing size_t.
if you're reallocing based on untrusted user input.. well, again, you're already in trouble. "fixing" realloc will only make problems occur earlier (which i suppose is good).
EDIT: what i really should have said, is "make problems occur somewhere else".
finally, returning NULL for failure.. well, malloc doesn't fail. most (sane) codes don't check the return value of malloc because it doesn't make sense to. the kernel doesn't allocate memory until first access, at which point you're going to have trouble regardless.
colour me sceptical, but this seems like a fix to a non-existent problem.
Should we then abandon ASLR or PIE or other defensive measures as well, just because some code is "already in trouble" due to a bad strcpy or something similar?
OOM in general cannot be used for remote code execution. heap overflow can.
> Should we then abandon ASLR or PIE or other defensive measures as well, just because some code is "already in trouble" due to a bad strcpy or something similar
certainly not, ASLR is so general that it doesn't make sense to not do it. more importantly, they're entirely transparent to the programmer, and can be used on existing codes.
That was exactly my point. Using reallocarray() instead of malloc(x * sizeof(foo)) can prevent a heap overflow bug. For a concrete example (assuming 32-bit size_t):
size_t user_input = ...;
size_t* ptr = malloc(user_input * sizeof(size_t));
if (!ptr)
return "FAIL: Out of memory";
for (size_t i = 0; i < user_input; i++)
ptr[i] = whatever();
But if the code was this:
size_t user_input = ...;
size_t* ptr = reallocarray(NULL, user_input, sizeof(size_t));
if (!ptr)
return "FAIL: Out of memory";
for (size_t i = 0; i < user_input; i++)
ptr[i] = whatever();
Of course, that code is still somewhat bad, since a user_input of 2^30 - 1 will cause the program to use large amounts for memory.
as you correctly state, user input of 2^30 is.. well, it's unlikely. more likely, is a user being able cause a program to do billions of reallocs. in which case, OOM is going to happen before overflow and exploitation.
OpenBSD's slogan boasts that there have only ever been "two remote holes in the default install", one of those holes would have been prevented by this.
which, lets face it, in the BSD is space (and particularly with regard to memory allocations from user input), is highly unlikely to change any time soon.
I'm not sure how to parse your sentence. Are you saying OpenBSD (which should be known for its mass audits) isn't likely to make changes in its source code any soon?
Yes, you should certainly suppose it's good, because it means the difference between an early out-of-memory error and a serious security vulnerability that can result in arbitrary code execution, like a buffer overflow.
That is the point of wrappers like these: to improve security.
>if you're reallocing based on untrusted user input.. well, again, you're already in trouble.
You are in trouble, but the trouble will be considerably less severe if the untrusted input hits this function instead of hitting malloc or realloc.
my point is that this scenario is so improbable that it's not worth worrying about.
> You are in trouble, but the trouble will be considerably less severe if the untrusted input hits this function instead of hitting malloc or realloc
heartbleed, SQL injection, and hundreds of other vulnerabilities are more likely to occur from untrusted user input. if you overflow a realloc, you don't know where the destination address is. you're far away from the stack, too. there is very little (if any) risk. i have never come across a realloc based exploit.
as i previously mentioned, an exploit from allocating data based on unvalidated untrusted user input is.. practically a tautology.
10 years since i started programming, 7 of which i consider good enough to be "experience", is the answer to your statement. less than many here, but i'm certainly not a novice.
Here is one of many examples of an integer overflow resulting in an improper size being passed to a memory allocation function further leading to remote code execution: https://docs.google.com/document/d/1tHElG04AJR5OR2Ex-m_Jsmc8...
This one was in Mobile Chrome, discovered in 2013.
i must say, this is the first (or second..) time i've heard of such an attack. and, whilst i'm not saying you're incorrect, i will say this - if you take user input and act upon it without validation, you're going to have a bad time. realloc does exactly what it says it will do.
is this a fault of realloc, or the programmer that wrote that code? my opinion is that it's a fault of the programmer. and i can already see that others disagree with that.
but that's just my opinion.
Tools and wrappers like these try to mitigate the risk of these errors.
User input is not limited to 4 GB. Users can provide whatever they want; that's the point. You have to code for malicious users who are pushing your system towards its edge cases, trying to find holes to break through.
i don't buy this - if you are going to allocate space, you must know the size of the space you are allocating. which you can validate, and certainly does not require going into kernel space to do.
Oh come on, what do you think the purpose of reallocarray is? It's exactly to include that boilerplate for you so that you don't have write your own "validation" before every alloc.
What reallocarray does is the bare minimum validation that shoud always be done. And in many cases that is enough, though not always.
2) The issue isn't whether malloc returns NULL. Technically speaking, unsigned arithmetic doesn't even "overflow", which in C is a term meaning the result is undefined. It returns the value modulo 2^N. In other words, in the vast majority of situations malloc will succeed, but return a buffer smaller than you requested.
3) According to your logic, people shouldn't check object boundaries, either. Many buffer overflow exploits utilize arithmetic overflow, because usually the memory you're interested is nowhere near the object you're overflowing. And we know these overflows happen and can be triggered even when the application isn't using very much memory.
People with your opinions shouldn't be allowed anywhere near C code.
inline void *reallocarray(void *old, size_t x, size_t y)
{
switch (y) {
case 1:
return realloc(old, x);
...
case 2:
// drastically simplified overflow check
...
default:
// perhaps a switch (x) with mirror cases here
return realloc_array_general(old, x, y);
}
}
When the function is inlined, the non-matching cases turn to dead code since the switch expression is constant.
An overflow checking realloc won't help if the first multiplication oveflows.
If I make this version instead:
void *realloc_array(void *old,
size_t existing_size,
size_t resize_factor,
size_t elsize);
void *realloc_array(void *old,
size_t existing_size,
size_t resize_factor,
size_t elsize,
size_t *p_newsize_out);
void *resize_array(void *old,
size_t existing_size,
size_t new_size
size_t resize_factor,
size_t elsize);
If a nonzero resize_factor is supplied, then the calculation new_size = existing_size * resize_factor is checked for overflow, otherwise the zero value of resize_factor indicates that this check is not applicable; however, the function still at least validates that new_size > existing_size.
The calculation bytes = new_size * elsize is always checked for overflow.
In application development, you seldom have the need for maximum speed in all your coding. And always worrying about such things as what is addressed by this small enhancement, is a pain.
In most scripting languages, such details are just falling away.
I still program in C/C++ -- but just for very speed-intensive "hot-spot" functions, in form of Python enhancement modules. And in those, I have the time and patience to look for all these implementation details. All the rest, I do in Python.
That's what my comment was addressing: In C++ with vector, map, etc, you don't need to remember to safely realloc manually, because the containers do it for you automatically.
Under the current standards, isn't C a proper subset of C++, and therefore, isn't "C/C++" just a way of saying "C++" that emphasizes that that includes C?
Or are you saying C++ isn't a language?
"C/C++" is a word coined by recruiters/human resources department.
In my experience people use "C/C++" to refer to "C with class compiled with a C++ compiler" rather than to "C or C++".
[1] http://stackoverflow.com/questions/1201593/c-subset-of-c-whe...
C and C++ are very different philosophically. Minimalism vs. "maximalism".
The subjective experience of writing C and C++ is totally different, so I wonder at programmers who say they write "C/C++".
The way it is, you can do
/* obfuscated way of doing free(ptr); */
realloc_array(ptr, 0, whatever);
The program could be pass nmemb or size as zero due to a bug, rather than the intent to free.
Or as a compromise, zero could be accepted for nmemb (zero sized array), but not for size (the base elements must have nonzero sizes).
> ((SIZE_MAX / nmemb) >= size)
before doing the size_t multiplication. That's no rocket science. Anyone who's worried about his size_ts overflowing should be able to come up with this.
I think the main benefit of adding functions like reallocarray is that they make the right tool for the job available by default. Plain realloc for array resizing is a timebomb in the same way as strncpy for normal strings - it will work (by accident) until it doesn't, and when it fails, it's likely to be an exploitable security hole.
So, if this is available in libbsd it means that is also available for linux too, I'm right?