受 Heartbleed 启发的偏执内存分配器

#Original (English)

Source: https://www.mikeash.com/pyblog/friday-qa-2014-05-23-a-heartbleed-inspired-paranoid-memory-allocator.html

The Heartbleed vulnerability made a big splash a couple of months ago, and rightly so. It could be described as a “memory leak”, but it’s not the standard kind where a program fails to free allocated memory. Instead, it allowed an attacker to dump memory contents from a remote program nearly at will, potentially leaking private keys, passwords, source code, and other data intended to stay secret. This got me thinking about ways to protect sensitive data against similar attacks. The result is MAParanoidAllocator, and in this article I’ll discuss the implementation.

BackgroundThe Heartbleed bug involves a heartbeat message added to the TLS protocol used for secure HTTP connections and many other encrypted internet protocols. The message is a simple ping, where one side can ask, “Are you still there?” and the other side will respond with, “Yes.” As with many pings, the requester can include a payload which the other side will repeat back to it. The payload consists of a string of bytes prefixed with a 16-bit length to indicate how many bytes are in the payload.

The Heartbleed bug is fundamentally due to mishandling the length prefix. It’s possible for the requester to send a request with a large value in the length field but with a shorter payload. The proper response to this would be to treat it as a fatal error and terminate the connection.

OpenSSL failed to check, and so proceeded with the response in this case. It copied the payload from the request to the response, using the length field to determine how many bytes to copy. If the actual payload is shorter than what the length field says, it ended up copying whatever data was sitting beyond the incoming packet data.

OpenSSL uses an internal allocator for this and other tasks, and that allocator doesn’t zero memory when it’s allocated or freed. Thus, the extra data that’s copied into the response ends up being whatever arbitrary data happened to be stored there from the last allocation at that spot. Since that same allocator is used for things like private key storage, that data can end up being sent back to the requester.

To scoop up as much data as possible, the attacker can specify the a long length field with no payload. A vulnerable TLS implementation will then reply with kilobytes of data from its internal memory. Depending on luck, the attacker stands a good chance of getting something interesting in that dump. If there’s no interesting data, the attacker can just try again. The process is quick and can be repeated without limit.

A Paranoid AllocatorThe proper fix for Heartbleed is to validate the length against the provided payload before sending a reply. There are various ways to try to avoid this whole class of security vulnerabilities.

One way is to have better processes for developing security-critical software. There was no particularly good reason to add the heartbeat extension to TLS in the first place, or to implement it in OpenSSL, so the whole thing should have been stopped before it even got started.

Another way is to use static analysis tools that are able to detect when too much trust is placed in input data. Unfortunately, the Heartbleed bug was too subtle for most static analyzers to detect, and while it’s prompted a lot of work in that area, it’s hard to know how much of that work will help to detect similar bugs in the future, and how much of it really just helps them detect Heartbleed specifically.

Finally, another way to avoid these vulnerabilities is to program in a safer language than C. C can be enormously unforgiving, and its concept of undefined behavior means that mistakes can easily turn into security vulnerabilities. The use of a safer language has been suggested for ages, but security-critical code keeps being written in C despite the problems.

Interestingly, I’m not too sure if a better language would have prevented this particular bug. It would be relatively natural to recycle buffers even in a language with more guarantees, and that could end up recycling the contents as well. If the buffer isn’t truncated to the actual length of each incoming packet, bounds checking won’t catch the excessively large copy. That said, better languages will shut out whole classes of security vulnerabilities and it would probably be wise to start seriously looking at alternatives to C.

In theory, the above should be enough. In practice, it’s a good idea to take a layered approach to security and not only try to avoid vulnerabilities, but also try to mitigate them if and when they do occur. For example, OS X and most other operating systems will mark memory as being non-executable by default. This means that even if an attacker is able to write out machine code into your process’s memory and jump to it, the attempt to take control will fail unless the attacker can first arrange for that code to be marked as executable.

Given that, I thought about what measures could be taken when allocating memory for sensitive data, such as private keys, that could help keep it safe even after a vulnerability is exploited. I came up with these features:

• Memory should be zeroed when allocated, and again when freed.

• Guard pages with no read or write permission should be placed before and after the memory allocation so that any overflow from an adjacent allocation turns into a crash.

• The memory used for storage should be kept with minimal permissions. It should be unreadable or unwriteable by default. When a read is requested, it should be changed to read-only, and when a write is requested, it should be changed to read-write.

• The API should be designed such that it’s difficult to leave read or write permissions enabled for longer than necessary, and especially to accidentally leave them enabled permanently.

CodeThe code is available on GitHub as usual:

https://github.com/mikeash/MAParanoidAllocator

APIThis is the public-facing API for the class:

1
    @interface MAParanoidAllocator : NSObject
2

3
    - (id)init;
4
    - (id)initWithSize: (size_t)size;
5

6
    - (size_t)size;
7
    - (void)setSize: (size_t)size;
8

9
    - (void)read: (void (^)(const void *ptr))block;
10
    - (void)write: (void (^)(void *ptr))block;
11

12
    @end

Most of it is obvious, but read: and write: need some explaining.

Conceptually, this class is similar to NSMutableData. It’s an object wrapper around an arbitrary chunk of bytes. The NSMutableData API provides the bytes method for reading, and the mutableBytes method for reading and writing. However, these methods make it impossible for the data object to know when the caller is done reading or writing. It would be possible to add a method that’s called at the end to explicitly signal that the operation is done, so that calling code would look like:

1
    const void *ptr = [dataObject bytes];
2
    // ...use ptr here...
3
    [dataObject recycleBytes: ptr];

However, it would be too easy to forget the recycleBytes: call and thus leave the memory readable forever.

The read: and write: methods each take a block as a parameter. The block is called synchronously and is passed in a pointer to the memory held by the object. This pointer is only valid inside the block, and the permissions are automatically reset to make the memory unreadable and unwriteable as soon as the block returns.

Implementation StrategyThe usual memory allocation APIs like malloc and free won’t suffice for this class.

Instead, it will allocate memory using mmap. This allows it to use mprotect to change permissions on the memory. Both mmap and mprotect work with page granularity, meaning that the class has to allocate memory in 4kB chunks. When allocating memory, it will round the requested size up to the nearest multiple of 4kB. It will add two more 4kB pages to the size, one for a guard page before and after. The guard pages will be permantly marked as unreadable and unwriteable. The allocated memory in the middle will normally be marked as unreadable and unwriteable, but the permissions will be temporarily changed using mprotect when necessary.

To resize an existing allocation, the approach is nothing special: allocate new memory, copy the contents across, deallocate the old memory. Since the memory is allocated with mmap, it’s deallocated with munmap, and for the sake of paranoia, the code will zero out the allocated memory before returning it to the operating system.

Instance VariablesThe class needs three instance variables: the current allocation size, a pointer to the allocated memory, and the system’s page size. The page size could be a global variable, but it’s mildly more convenient to keep it as an instance variable:

1
    @implementation MAParanoidAllocator {
2
        size_t _size;
3
        char *_memory;
4
        size_t _pageSize;
5
    }

Error CheckingThis code doesn’t try too hard to report or recover from errors. The calls generally shouldn’t fail, and if they do, something has gone terribly wrong. If they fail, the code just logs the error and then calls abort(). Error checking is essential in all code, but it’s especially true for security-critical code, as unchecked errors can easily turn into exploitable vulnerabilities. (See for example Exploitable Userland NULL Pointer Dereference.)

I wrote a simple error checking macro that’s little more than a custom assert:

1
    #define CHECK(condition) do { \
2
            if(!(condition)) { \
3
                NSLog(@"%s: %s (%d)", #condition, strerror(errno), errno); \
4
                abort(); \
5
            } \
6
        } while(0)

In addition to logging the failed condition and calling abort(), it also prints out the value of errno to help indicate what went wrong.

Initialization and DeallocationThe init method calls super, then sets the page size variable:

1
    - (id)init {
2
        if((self = [super init])) {
3
            CHECK((_pageSize = sysconf(_SC_PAGESIZE)) > 0);
4
        }
5
        return self;
6
    }

The other variables are left as zero, indicating that a freshly initialized instance has a size of zero. The class will be built so that a size of zero means no memory is allocated and no resources need to be freed. This means that making the first allocation can be done by just calling setSize: with the desired size, and that cleaning up in dealloc can be done by setting the size back to zero.

The initWithSize: method therefore just calls init, then setSize:

1
    - (id)initWithSize: (size_t)size {
2
        self = [self init];
3
        [self setSize: size];
4
        return self;
5
    }

The dealloc method again just calls setSize:

1
    - (void)dealloc {
2
        [self setSize: 0];
3
    }

Page Size RoundingThe API promises byte granularity, but all of the calls behind the scenes have to work with entire pages. This isn’t a problem, but it does require rounding the requested sizes up to the nearest multiple of the page size. This simple method takes care of that:

1
    - (size_t)roundToPageSize: (size_t)size {
2
        size_t pageCount = (size + _pageSize - 1) / _pageSize;
3
        return pageCount * _pageSize;
4
    }

Changing Memory PermissionsSeveral places in the code need to call mprotect on the entire chunk of allocated memory. This entails rounding the allocation size up to the nearest page size, calling mprotect, and checking for errors. That process is wrapped in a small helper method:

1
    - (void)mprotect: (int)prot {
2
        size_t size = [self roundToPageSize: _size];
3
        if(size > 0) {
4
            CHECK(mprotect(_memory, size, prot) == 0);
5
        }
6
    }

Setting the SizeMost of the complexity of this class is in setSize:. That’s where memory is allocated, deallocated, and copied from an old allocation to a new one.

The first thing it does is round both new and old sizes to multiples of the page size:

1
    - (void)setSize: (size_t)newSize {
2
        size_t beforeSize = [self roundToPageSize: _size];
3
        size_t afterSize = [self roundToPageSize: newSize];

These values get used a lot, so it’s easiest to compute them once up front. Next, check if they’re actually different. If the rounded sizes are equal, no memory needs to be reallocated:

1
        if(beforeSize != afterSize) {

If they are different, then the next task is to allocate a new chunk of memory with the new size. Since size zero is handled by having no memory allocated at all, this is only done if the new size is not zero:

1
            char *afterPointer = NULL;
2
            if(afterSize > 0) {

The total amount of memory to allocate is the new size plus two additional guard pages:

1
                size_t guardPagesSize = _pageSize * 2;
2
                size_t toAllocate = afterSize + guardPagesSize;

Then it’s time to call mmap. It requests an anonymous, private mapping (in other words, it’s not trying to memory map a file or anything like that) with read and write permissions. It needs to copy the existing data into the new allocation, so making the new memory unreadable and unwriteable comes later.

1
                char *allocatedPointer;
2
                CHECK((allocatedPointer = mmap(NULL, toAllocate, PROT_READ | PROT_WRITE, MAP_ANON | MAP_PRIVATE, 0, 0)) != MAP_FAILED);

The pointer returned by mmap points to the leading guard page. The pointer to the memory that’s actually used to store data is one page beyond that:

1
                afterPointer = allocatedPointer + _pageSize;

The memory returned from mmap is already zeroed by the operating system, so it’s not necessary to explicitly clear it in code.

With the new allocation in place, the leading and trailing pages are set to be unreadable and unwriteable so that they act as guard pages:

1
                CHECK(mprotect(allocatedPointer, _pageSize, PROT_NONE) == 0);
2
                CHECK(mprotect(afterPointer + afterSize, _pageSize, PROT_NONE) == 0);
3
            }

If there’s an existing allocation and a new allocation, then the data needs to be copied across. The new allocation is currently writeable, but the existing allocation is completely inaccessible. Thus, the copy is done inside of a call to the read: method:

1
            if(beforeSize > 0 && afterSize > 0) {
2
                [self read: ^(const void *ptr) {
3
                    memcpy(afterPointer, ptr, MIN(beforeSize, afterSize));
4
                }];
5
            }

At this point, the new memory is allocated (if necessary) and the existing data (if any) has been copied into it. The next step is to deallocate the old memory, if there is any:

1
            if(beforeSize > 0) {

Before returning it to the operating system, zero it out:

1
                [self write: ^(void *ptr) {
2
                    memset(ptr, 0, beforeSize);
3
                }];

This is probably unnecessary. The munmap documentation doesn’t guarantee that memory is zeroed out, but it should be safe since the only way to get the memory back again is with a call to mmap, and mmap zeroes all memory before providing it to the caller. However, this is a class with “paranoid” in its name, and that guarantee is a little too indirect for my comfort.

(Aside: there’s a common problem in code like this where the memset call gets optimized away by the compiler. Compilers are intelligent enough to know that writing to a buffer that is then immediately passed to free() is pointless, and the write can be eliminated. While this is correct according to the language standard, it’s undesirable behavior for paranoid, security-conscious code like this. To work around that problem, the memset_s function was introduced in the C11 standard. It does the same thing as memset, but is guaranteed not to be optimized away. It’s available on Apple platforms starting with Mac OS X 10.9 and iOS 7. Fortunately, memset_s is unnecessary here, as the indirection of calling memset in a block, and the fact that the memory is freed using munmap rather than free, mean that it can’t be optimized away. Using plain memset here allows the code to be compatible with earlier OS releases.)

Now that the memory is zeroed, it has to calculate the total size of the original allocation, and the pointer to the beginning of the allocation, taking into account the leading and trailing guard pages:

1
                size_t guardPagesSize = _pageSize * 2;
2
                size_t toDeallocate = beforeSize + guardPagesSize;
3
                char *pointerWithGuards = _memory - _pageSize;

Then a call to munmap deallocates the memory.

1
                CHECK(munmap(pointerWithGuards, toDeallocate) == 0);
2
            }

With the new memory allocated and the old memory deallocated, it’s time to update the instance variables:

1
            _memory = afterPointer;
2
            _size = newSize;

Finally, the newly allocated memory can be made unreadable and unwriteable.:

1
            [self mprotect: PROT_NONE];

In the case where the two allocations are the same (rounded) size, not much needs to be done. In addition to updating the _size instance variable, it also zeroes out any extra memory beyond the end of the new size in the case where the size shrinks. This ensures that leftover, potentially sensitive data doesn’t remain after the caller expected it to be gone:

1
        } else {
2
            if (newSize < _size) {
3
                [self write:^(void *ptr) {
4
                    memset((char *)ptr + newSize, 0, _size - newSize);
5
                }];
6
            }
7
            _size = newSize;
8
        }
9
    }

Size GetterCompared to setSize:, the implementation of the size method is somewhat less exciting:

1
    - (size_t)size {
2
        return _size;
3
    }

Reading and WritingLet’s look at the implementation of read: and write:. Both methods follow the same basic pattern: mprotect the allocation to have some permissions, call a block, then mprotect the allocation again to make it inaccessible. This pattern can be wrapped up in a common method:

1
    - (void)withProtections: (int)prot call: (void (^)(void))block {
2
        [self mprotect: prot];
3
        block();
4
        [self mprotect: PROT_NONE];
5
    }

With that available, the read: method just calls withProtections:call: with PROT_READ:

1
    - (void)read: (void (^)(const void *))block {
2
        [self withProtections: PROT_READ call: ^{
3
            block(_memory);
4
        }];
5
    }

The write: method is nearly identical, just with PROT_READ | PROT_WRITE:

1
    - (void)write: (void (^)(void *))block {
2
        [self withProtections: PROT_READ | PROT_WRITE call: ^{
3
            block(_memory);
4
        }];
5
    }

TestsI wanted to be sure to test all of the features of this code. A lot of those features involve ensuring that code crashes when it tries to access stuff outside of the provided API. My first approach was to write code that would crash, then use something like PLCrashReporter to catch the crash and resume execution. Unfortunately, this doesn’t play well with the debugger, as lldb strongly insists on stopping execution when the program crashes even if the crash was going to be caught. Since debugging tests is really useful, I didn’t want to settle for that approach.

After a lot of pain and suffering trying to get a custom mach exception handler set up, I realized that I could use mach calls like mach_vm_read and mach_vm_write to perform illegal memory reads and writes without crashing. These calls allow reading and writing memory, but when the given address is inaccessible, they return an error instead of raising a signal. This simplified the test code a lot. I won’t get into details here, but if you’re interested, you can read through the test code on GitHub.

ConclusionThis code defends against a scenario that should never happen, and where you’ve effectively already lost the game. Bugs which allow an attacker to bump into the various protections used here shouldn’t happen in the first place. However, since bugs are inevitable, a layered approach to security can help mitigate their effects. I’m not sure if it’s truly useful in this case, but it’s an interesting exercise to work through, and it doesn’t seem unreasonable to make sensitive data unreadable when it’s not explicitly being used. The techniques used to do that are all fairly straightforward POSIX calls, albeit ones that don’t see a lot of use in normal code.

That’s it for today. Come back next time for more frightening adventures. Friday Q&A is driven by reader ideas, so as always, if you have an idea for a topic that you’d like to see covered here, please send it in!