Thursday, July 12, 2007

Overcoming bias

Not strictly virtualization-related, but overcoming bias is one of the more consistently interesting cross-disciplinary blogs I've come across. The same sorts of cognitive biases that cause people to make bad decisions about their happiness, finances, political preferences, etc., often cause errors in software engineering. Pawing through Wikipedia's list of cognitive biases, I can associate almost every single bias with one (or more) mistakes I've made in my professional life. Optimism bias? Zounds, what engineer isn't guilty of it on a daily bias? Information bias has often led me to waste hours in debugging collecting useless trivia. Some have even entered the lore of computing; ingroup bias is nothing but "NIH syndrome."

While "overcoming bias" is certainly a laudable goal in many professional fields, I wonder about its tractability. These biases are clearly hardwired, and I suspect no amount of mindfulness will prevent us from committing them. Getting rid of one of these well-attested biases would probably require the neurological equivalent of, e.g., making humans able to digest grass, or giving a human the VO2Max of a horse. Oh well; if nothing else, at least being aware of our limitations as thinking machines might prevent us from trying anything too impossibly stupid...

Monday, July 02, 2007

BluePill detection in two easy steps.

In our HotOS submission, we alluded to a large number of theoretically possible methods of detecting the presence of a hypervisor. I'm not sure which of these many ways the well-publicised BluePill challengers have chosen, but I thought I'd make things a bit more concrete.

In our paper, we outline family of detection methods based on resource consumption. In short, the hypervisor must use cache, memory bandwidth, TLB entries, etc., in the course of multiplexing the CPU. A guest can be made intentionally sensitive to these resources in order to detect a hypervisor. For instance, you can obtain a good estimate of the effective size of the hardware TLB with psuedo-code like the following:

PPN oldPhysPage, newPhysPage = Alloc...();
VA oldVirtAddr = MapSomewhere(oldPhysPage);
VA newVirtAddr = MapSomewhere(newPhysPage);
memset(oldVirtAddr, 0x11, PAGE_SIZE);
memset(newVirtAddr, 0x22, PAGE_SIZE);
PTE=base of hardware page table;
for (i = 0; i < BIGNUM; i++) {
PTE[i] = MAKE_PTE(oldPhysPage); // map old page
(void)*(volatile char*)(i * PAGE_SIZE); // bring it into the TLB
* TLB now contains between 0 and BIGNUM old mappings.
* Now modify the PTEs *without* flushing the TLB,
* and wait for the hardware to leak an entry
for (i = 0; i < BIGNUM; i++) {
PTE[i] = MAKE_PTE(newPhysPage); // map old page
if ((*(volatile char*)(i * PAGE_SIZE)) == 0x22) {
printf("apparent tlb size: %d\n", i);

OK, so you can size the TLB. So what? Well, just run the above loop twice, but the second time, stick an instruction that's guaranteed to trap out to the hypervisor (e.g., CPUID) before the loop. On bare hardware, this inocuous instruction will have no impact on the TLBs. In the presence of a hypervisor, the instruction will either flush the TLB entirely (on current Intel VT implementations), or, if you're on a clever SVM hypervisor that uses the ASID facility to avoid TLB flushes on every hypervisor invocation, at least 1 fewer TLB entry. (Every hypervisor must at least read the VMCB's exit code, requiring 1 data TLB entry. For increased sensitivity, you could also detect the VMM's code footprint by rejiggering the above to measure ITLB entries, an exercise left to the reader. Hint: the return instruction is a single byte on x86.)

This detection technique uses only TLB capacity, but a more sophisticated approach could easily include the hardware eviction policy. We could also apply these same technique to instruction and data caches. (Even the x86's coherent data caches can be sized using the INVD instruction, which discards cache contents without writing back dirty data.) A less naive approach that uses the hardware's event-based performance monitoring support (RDPMC and friends) would have an even richer menu of options for noticing virtualization-induced perturbations.

I've seen zero evidence that Rutkowska has pondered resource-based detection attempts like this, or indeed, any attacks more sophisticated than a "go-slow" loop between reads of the PIT. It is hard for me to imagine a "hypervisor" worthy of the name that doesn't leave noticable traces in resource usage. In fact, to the degree that a hypervisor goes to heroic lengths to prevent such a detection technique, e.g., by running a hardware-accurate cache simulator on every guest memory access, it will only open up wider timing discrepancies for the guest's HV-detector to exploit.

I can only conclude that in 2006 Rutkowska was either naive about the possibilities of such attacks, or that she consciously chose to make an outrageous and indefensible claim ("undetectable malware!!!!111") in order to draw attention to herself and her company. Given the peripheral evidence of Rutkowska's competence, I think the evidence favors the latter, but I'd simply love to hear from her on the subject...