mopdf.com

1) CPU and Memory Virtualization: In the past, hypervisors relied on a technique called binary translation to implement full CPU and memory virtualization [9]. That means allcritical instructions (e.g., memory access or branch instructions) are translated into another piece of code that enforcescertain policies, while emulating the virtual behavior. Forexample, a memory access is replaced by code that emulatesa virtual page table and adheres to the access policies definedby the hypervisor. By using binary translation, the hypervisorhas complete control over all vCPUs and can emulate highprivileged instructions such as MOV CR3. Therefore, the hypervisor can ensure that the software is not able to escapefrom the virtualized context. The same applies to memoryvirtualization and all memory-accessing instruction.TABLE I: Overview of hypervisor attack surfaces.InterfacePort I/OMMIOPCI DMAHypercall InterfacesInstructionsComponentDevice Emulator / CoreDevice Emulator / CoreDevice EmulatorGuest Tools Interface / CoreInstruction EmulatorB. Input/Output on x86An Intel x86 processor implements multiple mechanismand instructions to communicate with attached devices. To understand how the OS interacts with these devices, we providein the following a brief overview of the different primitivesof Input/Output (I/O) on x86. An overview of the availableinterfaces is presented in Table I.However, implementing virtualization without hardwaresupport introduces a significant performance overhead andseveral other challenges such as interrupt handling need tobe addressed [8]. Therefore, all major CPU manufacturerssuch as Intel or AMD introduced hardware extensions thatallow to increase the performance by using so-called hardwareaccelerated virtualization. Intel calls its technology “Intel VTx”, while AMD’s technology is called “AMD-V”. In thecontext of this paper, we only focus on Intel VT-x. However,it is worth mentioning that while the implementation detailsof these extensions vary, the overall idea is the same: anew execution mode is introduced in the CPU that has evenhigher privileges than the OS kernel. A hypervisor runningin this higher privilege level has various methods to interceptdifferent kinds of events, to restrict the guest’s kernel fromaccessing actual hardware, and to provide direct access tophysical memory dedicated to a VM without emulating certaininstructions.a) Port I/O: The first mechanism to interface withexternal devices is the legacy port I/O address bus: besidesthe main memory, on x86, there is a second address space thatcan only be accessed using the in and out instructions.b) Memory-Mapped I/O: The second mechanism to interface with external devices are memory-mapped I/O (MMIO)regions. Writing or reading these memory regions correspondsto a direct access to device registers or device memory. Inmodern hardware, this mode of communication is preferredover port I/O as it is more flexible and allows much higherbandwidths. Additionally, there are well-known ways to enumerate most available MMIO regions.c) Direct Memory Access: The last mechanism to implement communication between the host and its devices isDirect Memory Access (DMA). PCI/PCI-Express based-DMAis implemented via bus mastering, which allows the PCI deviceto read from and write to the host’s main memory directly.Note that this effectively swaps the roles that the CPU and thedevice play: in contrast to MMIO, the devices decide whenand which memory to read and write. In the context of thispaper, we ignore legacy ISA DMA since it is hardly used thesedays in practice.2) Device Emulation: To be able to boot a COTS OS, ahypervisor has to emulate standard hardware such as an interrupt controller, a timer, and various other peripheral devices.The two main mechanisms for interaction with hardware areMMIO and port I/O. To emulate the interaction with hardware,the hypervisor must first intercept the interaction with thehardware. It should be noted that in the case of DMA, thehypervisor does not need to intercept memory accesses, as itis only used by the emulated hardware rather than the guestOS. An example of the implementation of device emulationand its trap and emulate approach is given in Figure 1. In thefollowing, we will outline the process of emulating a port I/Oinstruction based on KVM and QEMU. To capture MMIO orport I/O interactions, hypervisors typically use two differenttechniques. In both techniques, interacting with the emulatedhardware causes a trap and a VM-exit 1 , which the hypervisorhandles by emulating the side effects. No matter what kind oftrap the hypervisor receives, to obtain information on the actualinteraction (such as which value was written), the hypervisorwill typically have to disassemble and emulate the instructionitself.C. HypervisorA hypervisor, also known as Virtual Machine Monitor(VMM), is a privileged software which provides physical hardware resources, such as memory and virtual CPUs (vCPU), ina controlled environment to their VMs. Generally speaking, theVMs have no control or access to physical hardware devicesexcept for assigned ones. Instead, the hypervisor providesvCPUs and virtualized physical memory, and it also emulatesall necessary devices such as interrupt controllers. Wheneverthe VM needs to perform a privileged operation, such asaccessing the real hardware, it triggers a trap that causes a VMexit. A VM-exit transfers the control back to the hypervisorwhich emulates the privileged operation on behalf of the VM,after ensuring that the operation is legitimate. This mechanismis called trap and emulate. By providing a fully virtualizedenvironment, the hypervisor allows to simultaneously executemultiple COTS OSs on the same physical host.In the first case, the hypervisor has to emulate MMIO.To trap access on MMIO pages, the hypervisor typicallymarks the corresponding pages as non-accessible. Accessingthe MMIO page from within the virtual machine triggers apage fault. The hypervisor installs a handler for these pagefaults. Whenever a page fault occurs, the handler then checkswhether the requested page is registered for MMIO by one3

current fuzzers target individual interfaces in isolation andtry to avoid restarting the VMM. At the same time, theattacker model is very strong: typically the security modelof hypervisors assumes that the whole guest OS is maliciousand any interface available is also part of the attack surface.Consequently, any kind of memory corruption issues—andeven some denial-of-service bugs—are highly security-relevantin the context of hypervisors. Especially memory corruptionsmight lead to virtual machine escapes, which is the worst-casescenario for the whole cloud hosting industry that relies onsecure isolation.of the emulated devices. Finally, the hypervisor passes thecorresponding memory access to the device emulator. Afterthe device emulator simulated all relevant side effects of theMMIO access, the hypervisor passes control back to the VM.In the second case, the hypervisor has to emulate the portI/O. To trap on port I/O interactions, the hypervisor limitsthe execution of certain instructions such as in and outusing the hardware virtualization extension. Executing sucha restricted instruction will also cause a VM-exit. Similar tothe previous case, the hypervisor passes the interactions to thecorresponding device emulator 2 and returns control backto the VM 5 after the device emulator finished 4 . If thecorresponding device emulator implements DMA capabilities,the emulator may read or write data from the guest’s mainmemory 3 .So far, most research on the security of hypervisors wasperformed in industry [6], [7], [25], [26], [46]. For instance,Tang et al. [46] implemented an AFL extension with hypervisor fuzzing capabilities. It is implemented as a customextension to QEMU’s SeaBIOS. They extended the BIOS withan ability to consume inputs from the outside of the VM and touse them to interact with devices provided by the hypervisor.They also instrumented the code used for device emulation toprovide coverage feedback to AFL. In the academic domain, tothe best of our knowledge, there is only a single project (VDF)for fuzzing hypervisor related software [30]. The authors ofVDF manually extracted individual devices from the QEMUcodebase and fuzz them in AFL [54]. This approach has asignificant drawback: manual work is needed for each deviceemulator and hypervisor to enable fuzzing.Current hypervisors typically only support a limited set ofstandard hardware to be emulated. However, the code baseused in device emulation is rather large, posing a significantattack surface. For example, QEMU in version 4.0 containsmore than 400k lines of C code used to emulate devices.3) Para-Virtualization: To reduce the amount of codeneeded and to improve the performance significantly, modernhypervisors implement so-called para-virtualization interfaces.In a para-virtualized environment, the OS is aware that it isrunning inside a VM and it does not try to use actual hardware.Instead, a specialized driver (typically referred to as VirtIOdriver) uses a custom protocol specific to the hypervisor. Usinga custom protocol increases the performance of the virtualmachine and can reduce the attack surface in the hypervisor, aslegacy corner cases no longer have to be simulated faithfully.III.D ESIGNSince hypervisors perform a multitude of complex tasks,there are many ways one can approach testing the implementation of a given hypervisor. As a consequence, we begin byanalyzing the challenges one faces when designing a fuzzingframework for hypervisors. We then formulate the goals thatwe want to achieve with our fuzzer. Lastly, we describe ourdesign choices, which are all tailored towards addressing theidentified challenges and achieving the goals discussed earlier.To facilitate the communication between the guest OS andthe hypervisor (e.g., to implement para-virtualization protocol),modern hardware-accelerated virtualization introduces a newinstruction that performs a so-called hypercall. From a conceptual perspective, hypercalls are closely related to systemcalls (syscalls), but instead of jumping from userland to ring0, they jump directly to the hypervisor by triggering a VMexit. To implement hypercalls, Intel VT-x has introduced adedicated instruction called vmcall. However, to implementhypercall interfaces, some hypervisors use other privileged x86instructions, which always or conditionally result in a VM-exit.For instance, the VMware hypervisor series uses the in andout instruction for implementing para-virtualized interfaces,which are used by their VMware guest tools. The Parallelshypervisor uses the rdpmc instruction for this purpose. It iscommon that upon encountering a hypercall, the hypervisordirectly accesses the memory of the guest and reads dataor provides results by directly writing them into the guest’smemory. Similar to classic device emulation, this propertymakes hypercalls an interesting target for fuzzing.A. Threat ModelThroughout the rest of this paper, we assume the followingthreat model that is also reflected in the design of our approach.First, an attacker has full control over the kernel running insidethe virtual machine. Her goal is to either obtain control overother virtual machines hosted on the same physical machineor the host itself (i.e., the underlying system). This assumptionis commonly valid in various cloud hosting scenarios, wheremany virtual machines with unknown tenants are co-locatedon the same server [43]. If an attack can escape her rentedVM at any time, all data that is stored on the same physicalserver is at risk. Additionally, with the rise of private clouds,similar scenarios occur after an attacker compromised oneservice and now plans to escalate horizontally. Additionally,we are interested in Denial-of-Service (DoS) attacks, in whichan attacker might prevent the operator from taking control of itsVM or the attacker can circumvent load limiting mechanisms.D. Fuzzing HypervisorFuzzing hypervisors has its own set of challenges. Thehigher number of interfaces that can be used interactivelymandates a different setup than for ring 3 file format fuzzing.The guest system can trigger hypercalls, I/O operations aswell as reading or writing to memory mapped I/O regions.Likewise, restarting the hypervisor is much more expensivethan restarting an user-space process. Consequently, manyB. Challenges in Fuzzing HypervisorsCurrent hypervisors have a large and diverse attack surface.As described in Section II, there are many ways in which theguest interacts with the hypervisor. To make matters worse,4

Therefore, we require a very deterministic setup to obtain goodstability during fuzzing, especially given that we interact witha low-level component of the software stack. In the following,we demonstrate how we can achieve these goals by describingthe design of our fuzzer named H YPER -C UBE.HypervisorPCI DeviceDMAMMIO Area 1MMIO Area 2IO Area 1 VMMiscHyperCube OSInstructionEmulatorScratchMemoryMSRHypercalls TesseractISA DeviceInterpreterIO Area 1IO Area 2 1) High-Level Overview: Our fuzzer consists of three maincomponents as illustrated in Figure 2.CorePICHPETAPICChipset 1)HostMinimizer2)LoggerDecompilerFig. 2: High-level overview of the system architecture of H YPER -C UBE3)testing the various interfaces in isolation is not sufficient toevaluate the security of modern hypervisors: as our experienceand evaluation results show, a comprehensive evaluation has toconsider all interactions between different interfaces, typicallya sequence of such interactions is needed to uncover a vulnerability. Additionally, it is often non-trivial to find documentationfor different interfaces a given hypervisor exposes. Therefore,the fuzzer needs to be able to provide meaningful interactionswith undocumented interfaces. As another challenge, we foundthat even for well-known interfaces or devices, the normalstart-up routine of COTS OSs such as Linux or Windowsmight influence the bug finding process. For example, largeparts of the emulator might be initialized during boot time.However, given that an attacker can reboot the machine, theinitialization code also needs to be considered when studyingthe attack surface. Yet, testing the device from a COTS OSnever exercises this code in an uninitialized state. The sameboot process can also slow down hypervisors during fuzzing—restarting a hypervisor from scratch (e.g., after finding a crash)takes a significant amount of time that would slow down thefuzzing progress substantially. Lastly, depending on the OSrunning inside of the hypervisor, the behavior of hardwareaccelerated hypervisors can be rather non-deterministic.The first component is a specialized OS calledH YPER -C UBE OS which boots inside the target hypervisor and enumerates existing hardware interfaces.A custom OS enables us full control over the complete process.Afterwards, H YPER -C UBE OS spawns a second component and passes the information about availableinterfaces to the spawned task. The task runs our bytecode interpreter named T ESSERACT. It can consumearbitrary byte strings and uses them to actually fuzzthe hypervisor.Additionally, there is a set of external, independenttools that are able to provide bytecode strings tothe T ESSERACT interpreter, decompile executed bytecode programs, and observe the machine’s behaviorusing channels such as a serial interface.As we explain in the following, this architecture allows usto achieve our three aforementioned goals.a) High Performance Fuzzing: Rebooting a COTS OSsuch as Linux requires a significant amount of time. If thereare easy-to-find bugs within the hypervisor, the fuzzer spendsa significant portion of its time on rebooting the COTS OS.Using a small custom OS such as H YPER -C UBE OS candrastically decrease the boot time of the OS. H YPER -C UBEOS does not interact with other interrupts, nor does it have anyhardware initialization routine. Additionally, H YPER -C UBEOS is very small, and uses only an absolute minimum amountof memory. During fuzzing, this design choice allows us torapidly reload the OS after each crash and thus significantlyimprove the fuzzing performance.Additionally, and more importantly, we took measures toimprove the performance of the fuzzing process itself, sincethe process of compiling and loading a new program foreach test case can be very time consuming. The ability toexecute as many test cases as possible in any given timeperiod still remains one of the most important performancecriteria for fuzzers [27]. To increase the test throughput, weavoid compiling code. Instead, we use our specialized bytecodeinterpreter, named T ESSERACT, that runs in ring 0 of theH YPER -C UBE OS.C. ArchitectureIn the following, we first provide an overview of our designgoals and then present the architecture of our approach. Primarily, our design aims at providing high-performance fuzzingfor a given hypervisor. Besides being as fast as possible, ourapproach should be generic and applicable to a wide rangeof both open source and proprietary hypervisors. Furthermore,our approach should have the ability to find bugs resultingfrom (complex) interactions between different communicationchannels. To this end, we improve upon the idea of twodimensional fuzzing, as introduced by Xu et al. [52]. In twodimensional fuzzing, two different interfaces are attacked in afixed sequence. In our approach, we want to be able to attackan arbitrary number of interfaces in any order, we therefore aimat designing a “high-dimensional” fuzzer. Lastly, any fuzzeris only as good as its ability to reproduce the bugs found.The embedded interpreter T ESSERACT takes any stream ofinput bytes and interprets it as a sequence of interactions withthe hypervisor. The custom nature of this interpreter allows usto design the bytecode in such a way that it is very “fuzzerfriendly”. All instruction encodings are designed to maximizethe likelihood of producing useful instructions. The encoding ischosen such that there are no invalid instructions. Additionally,memory addresses are not encoded as pointers, but as pairof memory region and an offset. Since T ESSERACT is awareof all interesting memory regions, it can avoid interactingwith addresses that contain no relevant content, even though5

with available interfaces require access to physical memory.Our memory manager contains a simple heap that can be usedto allocate memory when required. Overall, running H YPER C UBE OS and T ESSERACT only requires a very small amountof memory. Therefore, it is possible to use a simplistic implementation of a heap manager. To provide access to the physicalmemory, H YPER -C UBE OS creates multiple linear one-to-onemappings that make relevant physical address ranges availablewithin the virtual address space.the fuzzer generates random data. To further increase theprobability of producing reasonable opcodes, all argumentssuch as region IDs and offsets are interpreted modulo theava

open source hypervisors. Because of our generic design, we can easily target even proprietary hypervisors as long as the hypervisor is able to boot commercial off-the-shelf (COTS) OSs. Based on these evaluation results, we conclude that our design is