As a follow on from our previous post on VirtualAlloc and the lack of randomization, and inspired by what the Chromium team did in their OS::Allocate function, we decided to sit down and write our version of VirtualAlloc_s. At which point it is only polite and fair to also give and tip of the hat and acknowledge Didier Stevens' work published in August and September 2011. Dider's work documented the EMET randomization  and his pseudo Address Space Layout Randomisation (ASLR) implementation.
Our VirtualAlloc_s and VirtualAllocEx_s functions are similar to the other Microsoft _s named safe versions of otherwise unsafe functions. The implementations are contained in a single header file and are designed as drop in replacements for any existing calls to VirtualAlloc or VirtualAllocEx.
At a high-level the implementation tries to randomize the address requested from VirtualAlloc (if the developer has not explicitly requested one). If the allocation fails due to say being an invalid address or already being allocated the implementation then falls back to using VirtualAlloc as-is, but alternating (after a random number of executions) between bottom-up or top-down allocations. This feature has the benefit of being guaranteed to work whilst also adding some unpredictability. In addition, we think that this behaviour is a very slight improvement over Google's solution to the problem. The finer details of the implementation are described below.
On the first call to VirtualAlloc_s or VirtualAllocEx_s the implementation initializes itself. This initialization includes seeding rand with the current PID, number of ticks and available RAM, randomly selecting the number of executions (between 1 and 3) that it'll switch between bottom-up and top-down allocations in the fall back scenario and finally selecting if it'll start in bottom-up or top-down fall backup mode. It also performs one low and one high allocation of the size requested by the user. These additional allocations are designed to add a bit more entropy to the fall back scenario. Once initialized and on each subsequent call the implementation generates a random address, attempts to allocate the address and if the allocation fails, falls back to the safe mode described previously.
We've tested the implementation using a number of unit tests. These tests have been in terms of performance overhead, thread safety, unique addresses and bias to specific addresses. Performance wise no noticeable overhead was observed in our unit test cases.
During an extended run (exceeding 110,000 iterations of the unit test cases on Windows 7 as a 32bit process) we recorded 2,048 different addresses being allocated. With regards to distribution while not perfectly uniform we did generally observe a good distribution across the address space as shown below:
|Click image for a larger version|
A similar run (exceeding 160,000 unit test cases on Windows 7 as a 64bit process) we observed 4,093 different addresses being allocated. Once again, the distribution it is not perfectly uniform. However, from a subjective perspective a good distribution was observed across the address space.
|Click image for a larger version|
Our proof of concept implementation is compatible with both 32 and 64bit platforms and is thread safe. However, we make no warranties implied or otherwise, that by using our implementation you won't run into issues, will actually gain any extra security or won't inadvertently introduce new security issues (the lawyers wrote that bit).
For developers looking to use the implementation it should simply be a case of search and replace for existing calls to VirtualAlloc/VirtualAllocEx. However, also keep in mind any static libraries or DLLs that your code uses won't benefit unless rebuilt to also use the new header. If you don't have the code to these components you'll need to work with your technology provider to get them to adopt it.
We've made all the code and materials associated with the implementation and testing available for download and additional peer review:
If you spot any mistakes or have any other feedback please feel free to get in touch with us.
Finally with regards to license, as we did borrow (copy) some of the Google V8 teams code the implementation falls under the BSD license, so pretty much usable by anyone; but please check to make sure it's compatible with your current policies and licensing.