Most programming languages have a lot of restrictions on the kinds of pointers that programs can create. C and C++ are unusually permissive in this respect: pointers to arbitrary objects and subobjects, usually all the way down to bytes, can be constructed. Consequently, most address computations can be expressed either in terms of integer arithmetic or pointer arithmetic. For example, a function based on array lookup:
void *memcpy(void *dst, const void *src, size_t n) {
const char *s = src;
char *d = dst;
for (int i = 0; i < n; ++i)
d[i] = s[i];
return dst;
}
can just as easily be expressed in terms of pointers:
void *memcpy(void *dst, const void *src, size_t n) {
const char *s = src;
char *d = dst;
while (n--)
*d++ = *s++;
return dst;
}
Idiomatic C tends to favor pointer-based code. For one thing, pointers are more expressive: a pointer can name any memory location while an integer index only makes sense when combined with a base address. Also, developers have a sense that the lower-level code will execute faster since it is closer to how the machine thinks. This may or may not be true: the tradeoffs are complex due to details of the semantics of pointers and integers, and also because different compiler optimizations will tend to fire for pointer code and integer code. Modern compilers can be pretty bright, at least for very simple codes: the version of GCC that I happen to be using for testing (GCC 5.3.0 at -O2) turns both functions above into exactly the same object code.
It is undefined behavior to perform pointer arithmetic where the result is outside of an object, with the exception that it is permissible to point one element past the end of an array:
int a[10]; int *p1 = a - 1; // UB int *p2 = a; // ok int *p3 = a + 9; // ok int *p4 = a + 10; // ok, but can't be dereferenced int *p5 = a + 11; // UB
Valgrind and ASan are intended to catch dereferences of invalid pointers, but not their creation or use in comparisons. UBSan catches the creation of invalid pointers in simple cases where bounds information is available, but not in the general case. tis-interpreter can reliably detect creation of invalid pointers.
A lot of C programs (I think it’s safe to say almost all non-trivial ones) create and use invalid pointers, and often they get away with it in the sense that C compilers usually give sensible results when illegal pointers are compared (but not, of course, dereferenced). On the other hand, when pointer arithmetic overflows, the resulting pointers can break assumptions being made in the code.
For the next part of this piece I’ll borrow some examples from a LWN article from 2008. We’ll start with a buffer length check implemented like this:
void awesome_length_check(unsigned len) {
char *buffer_end = buffer + BUFLEN;
if (buffer + len >= buffer_end)
die_a_gory_death();
}
Here the arithmetic for computing buffer_end is totally fine (assuming the buffer actually contains BUFLEN elements) but the subsequent buffer + len risks UB. Let’s look at the generated code for a 32-bit platform:
awesome_length_check:
cmpl $100, 4(%esp)
jl .LBB0_1
jmp die_a_gory_death
.LBB0_1:
retl
In general, pointer arithmetic risks overflowing when either the base address lies near the end of the address space or when the offset is really big. Here the compiler has factored the pointer out of the computation, making overflow more difficult, but let’s assume that the offset is controlled by an attacker. We’ll need a bit of a driver to see what happens:
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define BUFLEN 100
char buffer[BUFLEN];
void die_a_gory_death(void) { abort(); }
void awesome_length_check(unsigned len) {
char *buffer_end = buffer + BUFLEN;
if (buffer + len >= buffer_end)
die_a_gory_death();
}
int main(void) {
// volatile to suppress constant propagation
volatile unsigned len = UINT_MAX;
awesome_length_check(len);
printf("length check went well\n");
return 0;
}
And then:
$ clang -O -m32 -Wall ptr-overflow5.c $ ./a.out length check went well $ gcc-5 -O -m32 -Wall ptr-overflow5.c $ ./a.out length check went well
The problem is that once the length check succeeds, subsequent code is going to feel free to process up to UINT_MAX bytes of untrusted input data, potentially causing massive buffer overruns.
One thing we can do is explicitly check for a wrapped pointer:
void awesome_length_check(unsigned len) {
char *buffer_end = buffer + BUFLEN;
if (buffer + len >= buffer_end ||
buffer + len < buffer)
die_a_gory_death();
}
But this is just adding further reliance on undefined behavior and the LWN article mentions that compilers have been observed to eliminate the second part of the check. As the article points out, a better answer is to just avoid pointer arithmetic and do the length check on unsigned integers:
void awesome_length_check(unsigned len) {
if (len >= BUFLEN)
die_a_gory_death();
}
The problem is that we can’t very well go and retrofit all the C code to use integer checks instead of pointer checks. We can, on the other hand, use compiler support to catch pointer overflows as they happen: they are always UB and never a good idea.
Will Dietz, one of my collaborators on the integer overflow checking work we did a few years ago, extended UBSan to catch pointer overflows and wrote a great blog post showing some bugs that it caught. Unfortunately, for whatever reason, these patches didn’t make it into Clang. The other day Will reminded me that they exist; I dusted them off and submitted them for review — hopefully they will get in this time around.
Recently I’ve been thinking about using UBSan for hardening instead of just bug finding. Android is doing this, for example. Should we use pointer overflow checking in production? I believe that after the checker has been thoroughly tested, this makes sense. Consider the trapping mode of this sanitizer:
clang -O3 -fsanitize=pointer-overflow -fsanitize-trap=pointer-overflow
The runtime overhead on SPEC CINT 2006 is about 5%, so probably acceptable for code that is security-critical but not performance-critical. I’m sure we can reduce this overhead with some tuning of the optimizers. The 400.perlbench component of SPEC 2006 contained two pointer overflows that I had to fix.
Pointer overflow isn’t one of the UBs that we can finesse away by adjusting the standard: it’s a real machine-level phenomenon that is hard to prevent without runtime checks.
There’s plenty more work we could do in this sanitizer, such as catching arithmetic involving null pointers.
Update: I built the latest releases of PHP and FFmpeg using the pointer overflow sanitizer and both of them execute pointer overflows while running their own test suites.
14 responses to “Pointer Overflow Checking”
the first memcpy code snippet will behave incorrectly (negative index into dst) for cases where n > INT_MAX because i is a signed int.
Hi blarg, it’s true that i would have been better declared as a size_t, though as the post says, the generated code is exactly the same as memcpy2, therefore the runtime behavior of memcpy1 and memcpy2 is precisely the same.
The behavior of undefined behavior is undefined. That it happened to work with this version of your compiler is merely one possible outcome of UB. ;-]
You can do your overflow checks with signed integers just fine:
void awesome_check(int size)
{
if (size > BUFFER_LENGTH)
die_a_gory_death();
}
Better leave the unsigned integers for things like bitfields, and wrap-around clocks.
With unsigned integers, you can’t be sure that you can refactor a + b < c into a < c – b, even when you know that the absolute values of a, b and c fit into a couple of decimal digits.
John, thank you very much for this amazing post and your work on getting this adopted into LLVM. However, when I apply the patch to the current LLVM git, I’m stuck with the following error:
clang -fsanitize=undefined pointer-overflow.c
/tmp/pointer-overflow-7b5301.o: In function `blah’:
pointer-overflow.c:(.text+0x8a): undefined reference to `__ubsan_handle_pointer_overflow’
pointer-overflow.c:(.text+0x11a): undefined reference to `__ubsan_handle_pointer_overflow’
clang-3.9: error: linker command failed with exit code 1 (use -v to see invocation)
When combining with fsanitize-trap=pointer-overflow, it compiles, but execution just fails with an illegal instruction error (in this particular test). As a sideeffect, most previously reported nullptr memcpy/memset, shifting and alignment errors are now mostly silenced when using -fsanitize=address,undefined -fsanitize-trap=pointer-overflow on a larger codebase.
What am I missing? 🙁
Hi Daniel, luckily this is easily fixed! You must also build (and patch, using the patch linked to the main clang patch) compiler-rt, which is where the error handling functions live:
http://compiler-rt.llvm.org/
Oh, how embarrassing. That makes sense, should’ve read more carefully, even at a late hour 😉
Thanks!
Is it legal to perform arithmetic in this case:
#include
#include
int main(void) {
struct {
char sentinel;
char bytes[4];
} order;
strncpy(order.bytes, “123”, 4);
order.sentinel = ‘D’;
char *t = order.bytes;
t–;
printf(“%c\n”, *t);
}
If not which object does t start in?
Anon, this code is perfectly legal.
It seems to me that the wrapping around will only occur if the pointers are at the top end of the address range. This seems rather unlikely, which would make debugging hard. Even if you use the fsanitize-trap=pointer-overflow flag, you wouldn’t expect that incorrect code will display the behavior on most “normal” workloads.
Is there any way to force malloc to give you memory near the top of the address space or artificially limit the address space so you can debug this behavior?
Hi David, I think that rather than playing games with the allocator, it’s best to try out address sanitizer instead. It won’t catch pointer overflows but it will catch most OOB accesses. I’m not sure if ASan can be easily modified to catch OOB pointer creation, but if so that would seem like a useful hack.
Hi David Harris,
The issue is that the “len” parameter can be arbitrary garbage. What is len is size_t and a negative value is passed in? You have an instantly huge size. In this code snippet:
void awesome_length_check(unsigned len) {
char *buffer_end = buffer + BUFLEN;
if (buffer + len >= buffer_end ||
buffer + len < buffer)
die_a_gory_death();
}
Of course "buffer" is valid (this is some object known to the function) and so is "buffer_end". These are all under the control of the function.
What is not under control of the function is "len", which could be anything.
The expression "buffer + len" is what overflows.
This could happen even if buffer is nowhere near the end of the address space. Buffer could be (char *) 0x1000, just past a 4 kB unmapped zero page, and yet with a sufficiently large len, the calculation blows past the address 0xFFFFFFFF (let's go with 32 bits), wrapping to some low address which is below 0x1000.
The function is failing to do the job of taking any value of that integer type and validating that it's within the length range.
Kaz, thanks for the clarification. Is it usually the case that these pointer overflows occur when the len parameter is basically a mis-interpreted field (i.e. the values are random garbage, which is being treated like a length field for some reason) or do the problems come when len is indeed a length field, and is roughly the correct order of magnitude size, but happens to be slightly larger than the true length of the array? (The first case definitely seems more dangerous)
Just want to point out there is a well-known idiom using pointers:
| if (buffer_end – buffer < len) {
| die_a_gory_death();
| }
That is exactly equivalent to the "BUFSIZE < len" solution.