I recently read a great blog post from Felix Willhelm (@_fel1x) about some double-fetch vulnerabilities he discovered in the Xen Hypervisor. These bugs are described in the Xen Security Advisory XSA-155. This post is as a result of me trying to understand the bug better.
Double-fetch vulnerabilities are introduced when the same memory location is read from memory and assumed by the programmer to be the same value, when in fact the memory could have been modified by an attacker in a concurrent thread of execution, such as in a shared memory section. What was particularly interesting about this advisory was that upon inspection of the code, there was no apparent double-fetch, but it can clearly be seen in the compiled binary.
TL;DR – All pointers into shared memory should be labelled as volatile to avoid compiler optimisation introducing double-fetches. A good presentation about this is “Shattering Illusions in a Lock Free World” (especially slides 28+). The compiler is not doing anything wrong which is why this is a bug in Xen, not gcc.
To demonstrate the issue, here is the vulnerable code, distilled from the vulnerable Xen code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <stdio.h> #include <stdlib.h> void doStuff(int* ps) { printf("NON-VOLATILE"); switch(*ps) { case 0: { printf("0"); break; } case 1: { printf("1"); break; } case 2: { printf("2"); break; } case 3: { printf("3"); break; } case 4: { printf("4"); break; } default: { printf("default"); break; } } return; } void main(int argc, void *argv) { int i = rand(); doStuff(&i); } |
This vulnerability is specific to how gcc optimises switch statements with jump tables then there are 5 or more cases (more information here). Other cases where pointers to shared memory are not labelled as volatile could be exploitable, but in practise it seems relatively rare for the compiler to dereference a pointer twice.
And below is the resultant binary in IDA compiled with gcc 5.3.0 for Intel x64 (gcc 4.8.4 and x86 give the same result). The rbx registers points into a memory allocation, which could be shared memory and by defeferencing the pointer twice, we have our double-fetch vulnerability.
The compiler appears to do this to avoid using a register in the case where the default case is hit. Given that the two memory accesses are so close together, there is unlikely to be a big performance hit from the double fetch. But it’s not enough to prevent the race-condition from being winnable by the attacker (see the bochspwn research for techniques to try and win these tight race conditions).
The compiler is allowed to turn a single memory access in code into multiple accesses because without the ‘volatile’ attribute on the pointer, it’s assumed that the memory will not be changed by another thread of execution. Simply declaring the pointer as volatile as below resolves the issue.
1 |
void doStuff(volatile int* pi) |
The double-fetch has now dissappeared as a register is used to store the switch value:
To try and find other cases where double-fetches would be introduced, I used the following code to trash all current registers and to try and force the compiler to dereference a pointer a second time (code assumes that -fomit-frame-pointer is enabled).
1 2 3 4 5 |
#define CLOBBER_REGISTERS asm volatile ( "nop" \ : /* no outputs */ \ : /* no inputs */ \ : "eax", "ebx", "ecx", "edx", "esi", "edi" , "ebp" \ ); |
But in every case that I tried, the compiler used the local variable in preference to a double-fetch from memory. The compiler could eliminate the local variable by fetching the memory location twice, but this didn’t happen with gcc.
Here are the setups I’ve tried so far that exhibit the double-fetch behaviour in switch statements:
- Compilers: gcc 4.8.4 and 5.3.0
- Architectures: x86 and x64
- gcc Optimisation Levels: O1, O2, O3 and Os
Binaries compiled with optimisation disabled or with -fno-jump-tables
are not affected. Also, an initial experiment with an arm64 compiler from the Android SDK suggests that ARM binaries may not be affected.
Conclusion: Failing to label pointers to shared memory regions as volatile allows compilers to introduce double-fetches that aren’t reflected in source code. But in practice the compiler will only do this in specific circumstances. One case is switch statements that use jump tables on Intel procecessors. Further research is needed to figure out which other compilers, flow-control contructs and CPU architectures could introduce these double-fetches.
The code and build script are on GitHub.