The Eighth IEEE Workshop on Hot Topics in Operating Systems
`
`HotOS-VIII
`
`May 20-23, 2001
`Schoss Elmau, Germany
`
`Sponsored by
`IBM Research
`HP Labs
`Microsoft Research
`
`Microsoft Ex. 1012, p. 1
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`This page is intentionally almost blank.
`
`ii
`
`Microsoft Ex. 1012, p. 2
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Table of Contents
`The Eighth Workshop on Hot Topics in Operating Systems - HotOS-VIII
`
`Core OS
`
`Beyond Address Spaces - Flexibility, Performance, Protection, and Resource Management
`in the Type-Safe JX Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
`Michael Golm, J ¨urgen Klein¨oder, Frank Bellosa
`
`Design Issues in System Support for Programmable Routers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
`Prashant Pradhan, Kartik Gopalan, Tzi-cker Chiueh
`
`Lazy Process Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
`Jochen Liedtke, Horst Wenske
`Fault Tolerance
`
`Robustness in Complex Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
`Steven D. Gribble
`
`Using Abstraction To Improve Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
`Miguel Castro, Rodrigo Rodrigues, Barbara Liskov
`
`Fail-Stutter Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
`Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau
`Frameworks for Mobility
`
`Reconsidering Internet Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
`Alex C. Snoeren, Hari Balakrishnan, M. Frans Kaashoek
`
`Protium, an Infrastructure for Partitioned Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
`Cliff Young, Y. N. Lakshman, Tom Szymanski, John Reppy, David Presotto, Rob Pike,
`Girija Narlikar, Sape Mullender, Eric Grosse
`Modelling and (Self-)Tuning
`
`Probabilistic Modelling of Replica Divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
`Antony I. T. Rowstron, Neil Lawrence, Christopher M Bishop
`
`Self-Tuned Remote Execution for Pervasive Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
`Jason Flinn, Dushyanth Narayanan, M. Satyanarayanan
`
`Energy is just another resource: Energy accounting and energy pricing in the Nemesis OS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
`Rolf Neugebauer, Derek McAuley
`Peer-to-Peer Computing
`
`PAST: A large-scale, persistent peer-to-peer storage utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65
`Peter Druschel, Antony Rowstron
`
`Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
`Frank Dabek, Emma Brunskill, M. Frans Kaashoek, David Karger, Robert Morris, Ion
`Stoica, and Hari Balakrishnan
`Herald: Achieving a Global Event Notification Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
`Luis Felipe Cabrera, Michael B. Jones, Marvin Theimer
`
`iii
`
`Microsoft Ex. 1012, p. 3
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`New Devices
`
`HeRMES: High-Performance Reliable MRAM-Enabled Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
`Ethan L. Miller, Scott A. Brandt, Darrell D. E. Long
`
`Better Security via Smarter Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
`Gregory R. Ganger, David F. Nagle
`
`Research Issues in No-Futz Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
`David A. Holland, William Josephson, Kostas Magoutis, Margo I. Seltzer, Christopher
`A. Stein, Ada Lim
`Security & FT
`
`Don’t Trust your File Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
`David Mazi`eres, Dennis Shasha
`
`Active Protocols for Agile, Censor-Resistant Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
`Robert Ricci, Jay Lepreau
`
`Recursive Restartability: Turning the Reboot Sledgehammer into a Scalpel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
`George Candea, Armando Fox
`Virtualisation
`
`When Virtual is Better than Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
`Peter M. Chen, Brian D. Noble
`
`Virtualization Considered Harmful: OS Design Directions for Well-Conditioned Services . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
`Matt Welsh, David Culler
`Networking and OS
`
`Systems Directions for Pervasive Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
`Robert Grimm, Janet Davis, Ben Hendrickson, Eric Lemar, Adam MacBeth, Steven
`Swanson, Tom Anderson, Brian Berhsad, Gaetano Borriello, Steven Gribble, David
`Wetherall
`The Case for Resilient Overlay Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
`David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris
`Position Summaries
`
`Position Summary: Toward a Rigorous Data Type Model for HTTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
`Jeffrey C Mogul
`
`Position Summary: The Conquest File System: Life after Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
`An-I A Wang, Geoffrey H Kuenning, Peter Reiher, Gerald J Popek
`
`Position Summary: Supporting Coordinated Adaption in Networked Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
`Patrick G Bridges, Wen-Ke Chen, Matti A Hiltunen, Richard D Schlichting
`
`Position Summary: Middleware for Mobile Computing: Awareness vs Transparency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
`Licia Capra, Wolfgang Emmerich, Cecilia Mascola
`
`Position Summary: Separating Mobility from Mobile Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
`K˚are J Lauvset, Dag Johansen, Keith Marzullo
`
`Position Summary: The Importance of Good Plumbing - Reconsidering Infrastructure in Distributed Systems . . . . . . . . . 144
`Andrew Warfield, Norm Hutchinson
`
`Position Summary: Towards Global Storate Management and Data Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
`Alistair Veitch, Erik Riedel, Simon Towers, John Wilkes
`
`iv
`
`Microsoft Ex. 1012, p. 4
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Position Summary: Towards Zero-Code Software Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
`Emre Kiciman, Laurence Melloul, Armando Fox
`
`Position Summary: Aspect-Oriented System Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
`Yvonne Coady, Gregor Kiczales, Michael Feeley, Norman Hutchinson, Joon Suan Ong
`
`Position Summary: A Streaming Interface for Real-Time Interprocess Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
`Jork L¨oser, Hermann H ¨artig, Lars Reuther
`
`Position Summary: Eos - the dawn of the resource economy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
`John Wilkes, G. (John) Janakiramn, Patrick Goldsack, Lance Russel, Sharad Singhal,
`Andrew Thomas
`Position Summary: Transport Layer Support for Highly-Available Network Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
`Florin Sultan, Kiran Srinivasan, Liviu Iftode
`
`Position Summary: MANSION: A Room-based Mult-Agent Middleware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
`Guido J. van’t Noordende, Frances M.T. Brazier, Andrew S. Tanenbaum, Maarten R.
`van Steen
`Position Summary: Active Streams: An Approach to Adaptive Distributed Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
`Fabi´an E. Bustamante, Greg Eisenhauer, Patrick Widener, Karsten Schwan
`
`Position Summary: Smart Messages: A system Architecture for Large Networks of Embedded Systems . . . . . . . . . . . . . . 153
`Phillip Stanley-Marbell. Cristian Borcea, Kiran Nagaraja, Liviu Iftode
`
`Position Summary: Supporting Hot-Swappable Components for System Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
`Kevin Hui, Jonathan Appavoo, Robert Wisniewski, Marc Auslander, David Edelsohn,
`Ben Gamsa, Orran Krieeger, Bryan Rosenburg, Michael Stumm
`Position Summary: Applying the VVM Kernel to Flexible Web Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
`Ian Piumarta, Frederic Ogel, Bertil Folliot, Carine Baillarguet
`
`Position Summary: Hinting for goodness’ sake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
`David Petro, Dushyanth Narayanan, Gregory R. Ganger, Garth A. Gibson, Elizabeth
`Shriver
`Position Summary: Censorship Resistant Publishing Through Document Entanglements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
`Marc Waldman, David Mazieres
`
`Position Summary: Architectures For Adaption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
`Eyal de Lara, Dan S Wallach, Willy Zwaenepoel
`
`Position Summary: Anypoint Communication Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
`Ken Yocum, Darrell Anderson, Jeff Chase, Amin Vahdat
`
`Position Summary: Secure OS Extensibility That Doesn’t Cost an Arm and a Leg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
`Antony Edwards, Gernot Heiser
`
`Position Summary: The Lana Approach to Wireless Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .161
`Chrislain Razafimahefa, Ciaran Bryce, Michel Pawlak
`
`Position Summary: A Backup Appliance Composed of High-capacity Disk Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
`Kimberley Keeton, Eric Anderson
`
`Position Summary: Balance of Power: Energy Management for Server Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
`Jeffrey S Chase, Ron Doyle
`
`Position Summary: Bossa: a DSL framework for Application-Specific Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . 164
`Luciano Porto Barreto, Gilles Muller
`
`Position Summary: Authentication Confidences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`Gregory R Granger
`
`v
`
`Microsoft Ex. 1012, p. 5
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`Position Summary: Supporting Disconnected operation in DOORS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
`Nuno Preguica J Legatheaux Martins, Henrique Domingos, Sergio Duarte
`
`Position Summary: DiPS: a unifying approach for developing system software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
`Sam Michiels, Frank Matthijs, Dirk Walravens, Pierre Verbaeten
`
`vi
`
`Microsoft Ex. 1012, p. 6
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`When Virtual Is Better Than Real
`
`Peter M. Chen and Brian D. Noble
`Department of Electrical Engineering and Computer Science
`University of Michigan
`pmchen@umich.edu, bnoble@umich.edu
`
`Abstract
`This position paper argues that the operating system and
`applications currently running on a real machine should
`relocate into a virtual machine. This structure enables ser-
`vices to be added below the operating system and to do so
`without trusting or modifying the operating system or
`applications. To demonstrate the usefulness of this struc-
`ture, we describe three services that take advantage of it:
`secure logging, intrusion prevention and detection, and
`environment migration.
`
`1. Introduction
`
`First proposed and used in the 1960s, virtual machines
`are experiencing a revival in the commercial and research
`communities. Recent commercial products
`such as
`VMware and VirtualPC faithfully emulate complete x86-
`based computers. These products are widely used (e.g.
`VMware has more than 500,000 registered users) for pur-
`poses such as running Windows applications on Linux and
`testing software compatibility on different operating sys-
`tems. At least two recent research projects also use virtual
`machines: Disco uses virtual machines to run multiple
`commodity operating systems on large-scale multiproces-
`sors [4]; Hypervisor uses virtual machines to replicate the
`execution of one computer onto a backup [3].
`Our position is that the operating system and applica-
`tions that currently run directly on real machines should
`relocate into a virtual machine running on a real machine
`(Figure 1). The only programs that run directly on the real
`machine would be the host operating system, the virtual
`machine monitor, programs that provide local administra-
`tion, and additional services enabled by this virtual-
`machine-centric structure. Most network services would
`run in the virtual machine; the real machine would merely
`forward network packets for the virtual machine.
`This virtual-machine-centric model allows us to pro-
`vide services below most code running on the computer,
`similar to providing services in the hardware of a real
`
`machine. Because these services are implemented in a
`layer of software (the virtual machine monitor or the host
`operating system), they can be provided more easily and
`flexibly than they could if they were implemented by mod-
`ifying the hardware. In particular, we can provide services
`below the guest operating system without trusting or mod-
`ifying it. We believe providing services at this layer is
`especially useful for enhancing security and mobility.
`This position paper describes the general benefits and
`challenges that arise from running most applications in a
`virtual machine, then describes some example services
`and alternative ways to provide those services.
`
`2. Benefits
`
`Providing services by modifying a virtual machine has
`similar benefits to providing services by modifying a real
`machine. These services run separately from all processes
`in the virtual machine, including the guest operating sys-
`tem. This separation benefits security and portability.
`Security is enhanced because the services do not have to
`trust the guest operating system; they have only to trust the
`virtual machine monitor, which is considerably smaller
`and simpler. Trusting the virtual machine monitor is akin
`to trusting a real processor; both expose a narrow interface
`(the instruction set architecture). In contrast, services in an
`operating system are more vulnerable to malicious and
`random faults, because operating systems are larger and
`more prone to security and reliability holes. Separating the
`services from the guest operating system also enhances
`portability. We can implement the services without need-
`ing to change the operating system, so they can work
`across multiple operating system vendors and versions.
`While providing services in a virtual machine gains
`similar benefits to providing services in a real machine,
`virtual machines have some advantages over the physical
`machines they emulate. First, a virtual machine can be
`modified more easily than a physical machine, because the
`virtual machine monitor that creates the virtual machine
`
`116
`
`Microsoft Ex. 1012, p. 7
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`guest
`application
`
`guest
`application
`
`guest
`application
`
`guest operating system
`
`local
`administrative
`tool
`
`virtual machine monitor + proposed services
`
`host operating system + proposed services
`
`host machine
`
`Figure 1: Virtual-machine structure. In this model, most applications that currently run on real machines re-
`locate into a virtual machine running on the host machine. The virtual machine monitor and local administrative
`programs run directly on the host machine. In VMware, the virtual machine monitor issues I/O through the host
`operating system, so services that manipulate I/O events can be implemented in the host operating system [2].
`
`abstraction is a layer of software. Second, it is much easier
`to manipulate the state of a virtual machine than the state
`of a physical machine. The state of the virtual machine can
`be saved, cloned, encrypted, moved, or restored, none of
`which is easy to do with physical machines. Third, a vir-
`tual machine has a very fast connection to another comput-
`ing system, that is, the host machine on which the virtual
`machine monitor
`is
`running.
`In contrast, physical
`machines are separated by physical networks, which are
`slower than the memory bus that connects a virtual
`machine with its host.
`
`3. Challenges
`
`Providing services at the virtual-machine level holds
`two challenges. The first
`is performance. Running all
`applications above the virtual machine hurts performance
`due to virtualization overhead. For example, system calls
`in a virtual machine must be trapped by the virtual
`machine monitor and re-directed to the guest operating
`system. Hardware operations issued by the guest must be
`trapped by the virtual machine monitor, translated, and re-
`issued. Some overhead is unavoidable in a virtual
`machine; the services enabled by that machine must out-
`weigh this performance cost. Virtualizing an x86-based
`machine incurs additional overheads because x86 proces-
`sors don’t trap on some instructions that must be virtual-
`ized (e.g. reads of certain system registers). One way to
`implement a virtual machine in the presence of these
`“non-virtualizable” instructions is to re-write the binaries
`at run time to force these instructions to trap [13], but this
`incurs significant overhead.
`The second challenge of virtual-machine services is the
`semantic gap between the virtual machine and the service.
`Services in the virtual machine operate below the abstrac-
`tions provided by the guest operating system and applica-
`tions. This can make it difficult to provide services. For
`example, it is difficult to provide a service that checks file
`
`system integrity without knowledge of on-disk structures.
`Some services do not need any operating system abstrac-
`tions; secure logging (Section 4.1) is an example of such a
`service. For services that require higher-level information,
`one must re-create this information in some form. Full
`semantic information requires re-implementing guest OS
`abstractions in or below the virtual machine. However,
`there are several abstractions—virtual address spaces,
`threads of control, network protocols, and file system for-
`mats—that are shared across many operating systems. By
`observing manipulations of virtualized hardware, one can
`reconstruct these generic abstractions, enabling services
`that require semantic information.
`
`4. Example services
`
`In this section, we describe three services that can be
`provided at the virtual-machine level. Others have used
`virtual machines for many other purposes, such as prevent-
`ing one server from monopolizing machine resources,
`education, easing the development of privileged software,
`and software development for different operating systems
`[10].
`
`4.1. Secure logging
`
`Most operating systems log interesting events as part of
`their security strategy. For example, a system might keep a
`record of login attempts and received/sent mail. System
`administrators use the logged information for a variety of
`purposes. For example, the log may help administrators
`understand how a network intruder gained access to the
`system, or it may help administrators know what damage
`the intruder inflicted after he gained access. Unfortunately,
`the logging used in current systems has two important
`shortcomings:
`integrity and completeness. First, an
`attacker can easily turn off logging after he takes over the
`system; thus the contents of the log cannot be trusted after
`
`117
`
`Microsoft Ex. 1012, p. 8
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`the point of compromise. Second, it is difficult to antici-
`pate what information may be needed during the post-
`attack analysis; thus the log may lack information needed
`to discern how the intruder gained access or what actions
`he took after gaining access.
`Virtual machines provide an opportunity to correct both
`shortcomings of current logging. To improve the integrity
`of logging, we can move the logging software out of the
`operating system and into the virtual machine monitor.
`The virtual machine monitor is much smaller and simpler
`than the guest operating system and hence is less vulnera-
`ble to attack. By moving the logging software into the vir-
`tual machine monitor, we move it out of the domain that
`an intruder can control. Even if the intruder gains root
`access or completely replaces the guest operating system,
`he cannot affect the logging software or the logged data.
`Logged data can be written quickly to the host file system,
`taking advantage of the fast connection between the virtual
`machine monitor and the host computer.
`To improve the completeness of logging, we propose
`logging enough data to replay the complete execution of
`the virtual machine [3]. The information needed to accom-
`plish a faithful replay is limited to a checkpoint with
`which to initialize the replaying virtual machine, plus the
`non-deterministic events that affected the original execu-
`tion of the virtual machine since the time of the saved
`checkpoint. These non-deterministic events fall into two
`categories: external input and time. External input refers to
`data sent by a non-logged entity, such as a human user or
`an external computer (e.g. a web server). Time refers to
`the exact point in the execution stream at which an event
`takes place. For example, to replay the interleaving pattern
`between threads, we must log which instruction is pre-
`empted by a timer interrupt [17] (we assume the virtual
`machine monitor is not running on a multi-processor).
`Note that most
`instructions executed by the virtual
`machine do not need to be logged; only the relatively
`infrequent non-deterministic events need to be logged.
`Using the virtual machine monitor to perform secure
`logging raises a number of research questions. The first
`question regards the volume of log data needed to support
`replay. We believe that the volume of data that needs to be
`logged will not be prohibitive. Local non-deterministic
`events, such as thread scheduling events and user inputs,
`are all small. Data from disk reads can be large, but these
`are deterministic (though the time of the disk interrupts are
`non-deterministic). The largest producer of log data is
`likely to be incoming network packets. We can reduce the
`volume of logged network data greatly by using message-
`logging techniques developed in the fault-tolerance com-
`munity. For example, there is no need to log message data
`received from computers that are themselves being logged,
`because these computers can be replayed to reproduce the
`
`sent message data [11]. If all computers on the same local
`network cooperate during logging and replay, then only
`messages received from external sites need to be logged.
`For an important class of servers (e.g. web servers), the
`volume of data received in messages is relatively small
`(HTTP GET and POST requests). Last, as disk prices con-
`tinue to plummet, more computers (especially servers
`worthy of being logged) will be able to devote many
`gigabytes to store log data [20].
`A second research direction is designing tools to ana-
`lyze the behavior of a virtual machine during replay. Writ-
`ing useful analysis tools in this domain is challenging
`because of the semantic gap between virtual machine
`events and the corresponding operating system actions.
`The analysis tool may have to duplicate some operating
`system functionality to distill the log into useful informa-
`tion. For example, the analysis tool may need to under-
`stand the on-disk file system format to translate the disk
`transfers seen by the virtual machine monitor into file-sys-
`tem transfers issued by the operating system. Translating
`virtual machine events into operating system events
`becomes especially challenging (and perhaps impossible)
`if the intruder modifies the operating system. One family
`of analysis tools we hope to develop trace the flow of
`information in the system, so that administrators can ask
`questions like “What network connections caused the
`password file to change?”.
`
`4.2. Intrusion prevention and detection
`
`Another important component to a security strategy is
`detecting and thwarting intruders. Ideally, these systems
`prevent intrusions by identifying intruders as they attack
`the system [9]. These systems also try to detect intrusions
`after the fact by monitoring the events and state of the
`computer for signs that a computer has been compromised
`[8, 12]. Virtual machines offer the potential for improving
`both intrusion prevention and intrusion detection.
`Intrusion preventers work by monitoring events that
`enter or occur on the system, such as incoming network
`packets. Signature-based preventers match these input
`events against a database of known attacks; anomaly-
`based preventers look for input events that differ from the
`norm. Both these types of intrusion preventers have flaws,
`however. Signature-based systems can only thwart attacks
`that have occurred in the past, been analyzed, and been
`integrated into the attack database. Anomaly-based sys-
`tems can raise too many false alarms and may be suscepti-
`ble to re-training attacks.
`A more trustworthy method of recognizing an attack is
`to simply run the input event on the real system and seeing
`how the system responds. Of course, running suspicious
`events on the real system risks compromising the system.
`
`118
`
`Microsoft Ex. 1012, p. 9
`Microsoft v. Daedalus Blue
`IPR2021-00832
`
`

`

`However, we can safely conduct this type of test on a clone
`of the real system. Virtual machines make it easy to clone
`a running system, and an intrusion preventer can use this
`clone to test how a suspicious input event would affect the
`real system. The clone can be run as a hot standby by
`keeping it synchronized with the real system (using pri-
`mary-backup techniques), or it can be created on the fly in
`response to suspicious events. In either case, clones admit
`more powerful
`intrusion preventers by looking at
`the
`response of the system to the input event rather than look-
`ing only at the input event. Because clones are isolated
`from the real system, they also allow an intrusion preven-
`ter to run potentially destructive tests to verify the sys-
`tem’s health. For example, an intrusion preventer could
`forward a suspicious packet to a clone and see if it crashes
`any running processes. Or it could process suspicious
`input on the clone, then see if the clone still responds to
`shutdown commands.
`A potential obstacle to using clone-based intrusion pre-
`vention is the effect of clone creation or maintenance on
`the processing of innocent events. To avoid blocking the
`processing of innocent events, an intrusion preventer
`would ideally run the clone in the background. Allowing
`innocent events to go forward while evaluating suspicious
`events implies that these events have loose ordering con-
`straints. For example, a clone-based preventer could be
`used to test e-mail messages for viruses, because ordering
`constraints between e-mail messages are very loose.
`Intrusion detectors try to detect the actions of intruders
`after they have compromised a system. Signs of an
`intruder might include bursts of outgoing network packets
`(perhaps indicating a compromised computer launching a
`denial-of-service attack), modified system files [12], or
`abnormal system-call patterns from utility programs [8].
`As with system logging, these intrusion detectors fall short
`in integrity or completeness. Host-based intrusion detec-
`tors (such as those that monitor system calls) may be
`turned off by intruders after they compromise the system,
`so they are primarily useful only for detecting the act of an
`intruder breaking into a system. If an intruder evades
`detection at the time of entry, he can often disarm a host-
`based intrusion detector to avoid detection in the future.
`Network-based intrusion detectors can provide better
`integrity by being separate from the host operating system
`(e.g. in a standalone network router), but they suffer from
`a lack of completeness. Network intrusion detectors can
`see only network packets; they cannot see the myriad other
`events occurring in a computer system, such as disk traffic,
`keyboard events, memory usage, and CPU usage.
`Implementing post-intrusion detection at the level of a
`virtual machine offers the potential for providing both
`integrity and completeness. Like a network-based intru-
`sion detector, virtual-machine-based intrusion detectors
`
`are separate from the guest operating system and applica-
`tions. Unlike network intrusion detectors, however, vir-
`tual-machine intrusion detectors can see all events
`occurring in the virtual machine they monitor. Virtual-
`machine intrusion detectors can use this additional infor-
`mation to implement new detection policies. For example,
`it could detect if the virtual machine reads certain disk
`blocks (e.g. containing passwords), then issues a burst of
`CPU activity (e.g. cracking the passwords). Or it could
`detect if the virtual machine has intense CPU activity with
`no corresponding keyboard activity.
`As with secure logging, a key challenge in post-intru-
`sion detection in a virtual machine is how to bridge the
`semantic gap between virtual machine events and operat-
`ing system events. This challenge is similar to that encoun-
`tered by network-based intrusion detectors, which must
`parse the contents of IP packets.
`
`4.3. Environment migration
`
`Process migration has been a topic of interest from the
`early days of distributed computing. Migration allows one
`to package a running computation—either a process or
`collection of processes—and move it to a different physi-
`cal machine. Using migration, a user’s computations can
`move as he does, taking advantage of hardware that is
`more convenient to the user’s current location.
`The earliest systems, including Butler [15], Condor
`[14], and Sprite [6], focused on load sharing across
`machines rather than supporting mobile users. These load-
`sharing systems typically left residual dependencies on the
`source machine for transparency, and considered an indi-
`vidual process as the unit of migration. This view differs
`from that of mobile users, who consider the unit of migra-
`tion to be the collection of all applications running on their
`current machine.
`Recently, migration systems have begun to address the
`needs of mobile users. Examples of systems supporting
`mobility include the Teleporting system [16] and SLIM
`[18]. These systems migrate the user interface of a
`machine, leaving the entire set of applications to run on
`their host machine. In the limit, the display device can be a
`stateless,
`thin client. This approach provides a better
`match to the expectations of a migrating user, and need not
`deal with residual dependencies. However, these systems
`are intolerant of even moderate latency between the inter-
`