SimuBoost: Scalable Parallelization of Functional System Simulation

Für das Sammeln detaillierter Laufzeitinformationen, wie Speicherzugriffsmustern, wird in der Betriebssystem- und Sicherheitsforschung häufig auf die funktionale Systemsimulation zurückgegriffen. Der Simulator führt dabei die zu untersuchende Arbeitslast in einer virtuellen Maschine (VM) aus, indem er schrittweise Instruktionen interpretiert oder derart übersetzt, sodass diese auf dem Zustand der VM arbeiten. Dieser Prozess ermöglicht es, eine umfangreiche Instrumentierung durchzuführen und so an Informationen zum Laufzeitverhalten zu gelangen, die auf einer physischen Maschine nicht zugänglich sind.
... mehr

Obwohl die funktionale Systemsimulation als mächtiges Werkzeug gilt, stellt die durch die Interpretation oder Übersetzung resultierende immense Ausführungsverlangsamung eine substanzielle Einschränkung des Verfahrens dar. Im Vergleich zu einer nativen Ausführung messen wir für QEMU eine 30-fache Verlangsamung, wobei die Aufzeichnung von Speicherzugriffen diesen Faktor verdoppelt. Mit Simulatoren, die umfangreichere Instrumentierungsmöglichkeiten mitbringen als QEMU, kann die Verlangsamung um eine Größenordnung höher ausfallen. Dies macht die funktionale Simulation für lang laufende, vernetzte oder interaktive Arbeitslasten uninteressant. Darüber hinaus erzeugt die Verlangsamung ein unrealistisches Zeitverhalten, sobald Aktivitäten außerhalb der VM (z. B. Ein-/Ausgabe) involviert sind.

In dieser Arbeit stellen wir SimuBoost vor, eine Methode zur drastischen Beschleunigung funktionaler Systemsimulation. SimuBoost führt die zu untersuchende Arbeitslast zunächst in einer schnellen hardwaregestützten virtuellen Maschine aus. Dies ermöglicht volle Interaktivität mit Benutzern und Netzwerkgeräten. Während der Ausführung erstellt SimuBoost periodisch Abbilder der VM (engl. Checkpoints). Diese dienen als Ausgangspunkt für eine parallele Simulation, bei der jedes Intervall unabhängig simuliert und analysiert wird. Eine heterogene deterministische Wiederholung (engl. heterogeneous deterministic Replay) garantiert, dass in dieser Phase die vorherige hardwaregestützte Ausführung jedes Intervalls exakt reproduziert wird, einschließlich Interaktionen und realistischem Zeitverhalten.

Unser Prototyp ist in der Lage, die Laufzeit einer funktionalen Systemsimulation deutlich zu reduzieren. Während mit herkömmlichen Verfahren für die Simulation des Bauprozesses eines modernen Linux über 5 Stunden benötigt werden, schließt SimuBoost die Simulation in nur 15 Minuten ab. Dies sind lediglich 16% mehr Zeit, als der Bau in einer schnellen hardwaregestützten VM in Anspruch nimmt. SimuBoost ist imstande, diese Geschwindigkeit auch bei voller Instrumentierung zur Aufzeichnung von Speicherzugriffen beizubehalten.

Die vorliegende Arbeit ist das erste Projekt, welches das Konzept der Partitionierung und Parallelisierung der Ausführungszeit auf die interaktive Systemvirtualisierung in einer Weise anwendet, die eine sofortige parallele funktionale Simulation gestattet. Wir ergänzen die praktische Umsetzung mit einem mathematischen Modell zur formalen Beschreibung der Beschleunigungseigenschaften. Dies erlaubt es, für ein gegebenes Szenario die voraussichtliche parallele Simulationszeit zu prognostizieren und gibt eine Orientierung zur Wahl der optimalen Intervalllänge. Im Gegensatz zu bisherigen Arbeiten legt SimuBoost einen starken Fokus auf die Skalierbarkeit über die Grenzen eines einzelnen physischen Systems hinaus. Ein zentraler Schlüssel hierzu ist der Einsatz moderner Checkpointing-Technologien. Im Rahmen dieser Arbeit präsentieren wir zwei neuartige Methoden zur effizienten und effektiven Kompression von periodischen Systemabbildern.

Gathering detailed run-time information such as memory access traces in operating system and security research often involves functional full
system simulation (FFSS). The simulator runs the workload of interest in a virtual machine (VM), gradually interpreting or translating instructions so that they operate on the state of the VM and allow for comprehensive
instrumentation.

While functional full system simulation is a powerful tool, a severe
limitation is its immense slowdown. For QEMU, we have measured average slowdowns of 30x and 60x for plain simulation and tracing of memory accesses, respectively. ... mehrSimulators offering more advanced instrumentation capabilities can even be an order of magnitude slower. This quickly renders functional simulation impractical for long-running, networked, or interactive workloads. Furthermore, the slowdown creates unrealistic timing behavior whenever activities external to the virtual machine (e.g., I/O) are involved.

In this thesis, we present SimuBoost, a method for drastically accelerating functional full system simulation. SimuBoost runs the workload in a fast and interactive hardware-assisted virtual machine while periodically taking checkpoints. These checkpoints then serve as starting points for simulations, enabling to simulate and analyze each interval simultaneously in one job per interval. Heterogeneous deterministic replay guarantees that the simulations repeat the exact same execution as in the hardware-assisted run, including interactions and recorded timing.

Our prototype is able to significantly reduce the run time of functional full
system simulation while providing full interactivity. Simulating an entire
kernel build completes in just 16% more time than needed to run the same
workload in a regular hardware-assisted virtual machine. SimuBoost is able
to maintain this performance even with full instrumentation for memory
tracing.

This thesis represents the first project to apply the concept of partitioning and parallelization of execution time to interactive full system virtualization in a manner that allows for immediate parallel functional simulation. We complement the practical implementation with a performance model to formally describe the properties of the acceleration method and predict speedups. In contrast to previous work, SimuBoost places a strong focus on scalability beyond the limits of a single physical machine. It therefore makes heavy use of virtual machine checkpointing technology. In this course, we present two novel methods for efficiently and effectively reducing the size of periodic checkpoints.