Decoupling dynamic program analysis from execution in virtual environments

CROSS-REFERENCE TO RELATED APPLICATIONS

0001The present application claims the benefit of U.S. provisional patent application Ser. No. 61/074,236, filed on Jun. 20, 2008, and entitled “Decoupling Dynamic Program Analysis From Execution In Virtual Environments,” which is hereby incorporated by reference. The present application also incorporates by reference the following: U.S. patent application Ser. No. 12/239,648, entitled “Decoupling Dynamic Program Analysis From Execution Across Heterogeneous Systems” and filed on Sep. 26, 2008, U.S. patent application Ser. No. 12/239,674, entitled “Synchronous Decoupled Program Analysis In Virtual Environments” and filed on Sep. 26, 2008, and U.S. patent application Ser. No. 12/239,691, entitled “Accelerating Replayed Program Execution To Support Decoupled Program Analysis” and filed on Sep. 26, 2008.

BACKGROUND OF THE INVENTION

0002Dynamic program analysis involves the analysis of a computer program while it is executing in real-time. It may be used for various applications including intrusion detection and prevention, bug discovery and profiling, corruption detection and identifying non-fatal memory leaks.

0003Dynamic program analysis adds overhead to the execution of the computer program because it is executed “inline” with program execution. It requires dynamic loading of special libraries or recompiling the computer program to insert analysis code into the program's executable code. Some dynamic program analysis (e.g., instrumentation and probing functionality, etc.) can add sufficient overhead to the execution of the program to perturb the processor workload and even cause “heisenbugs,” i.e., where the phenomenon under observation is changed or lost due to the measurement itself. For example, dynamic program analysis commonly used for detecting buffer overflow or use of undefined memory routinely incurs overhead on the order of 10-40×, rendering many production workloads unusable. Even in nonproduction settings, such as program development or quality assurance, this overhead may dissuade use in longer more realistic tests. As such, to minimize performance costs, dynamic program analysis tools today perform a minimal set of checks, meaning that many critical software flaws can remain overlooked.

SUMMARY OF THE INVENTION

0004In one or more embodiments of the invention, dynamic program analysis is decoupled from execution in virtual computer environments so that program analysis can be performed on a running computer program without affecting or perturbing the workload of the system on which the program is executing. Decoupled dynamic program analysis is enabled by separating execution and analysis into two tasks: (1) recording, where system execution is recorded with minimal interference, and (2) analysis, where the execution is replayed and analyzed.

0005A method according to an embodiment of the invention is used in analyzing a computer program while the computer program is being executed in real-time. This method comprises steps of accessing a log recorded by a main workload virtual machine, replaying an execution behavior of the main workload virtual machine on an analysis virtual machine using the log, and executing program analysis code on the analysis virtual machine while execution behavior of the main workload virtual machine is replayed on the analysis virtual machine.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> depicts functional block diagrams of virtualized computer systems in which one or more embodiments of the invention may be practiced.

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram depicting one embodiment of a homogeneous record and replay platform.

<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart depicting an embodiment of a method for recording and replaying execution behavior on a homogeneous record and replay platform.

<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram depicting one embodiment of a heterogenous record and replay platform.

<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart depicting an embodiment of a method for recording and replaying execution behavior on a heterogeneous record and replay platform.

<figref idref="DRAWINGS">FIG. 6</figref> is a schematic diagram of dynamic analysis platforms according to one or more embodiments of the invention.

<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram depicting one embodiment of a heterogeneous record and replay platform using a relog file to improve performance.

<figref idref="DRAWINGS">FIGS. 8A and 8B</figref> are flow charts depicting an embodiment of a method for recording and replaying execution behavior on a heterogeneous record and replay platform using a relog file to improve performance.

<figref idref="DRAWINGS">FIG. 9A</figref> is a flow chart of an embodiment of a method for synchronizing a record and replay platform.

<figref idref="DRAWINGS">FIG. 9B</figref> is a flow chart of an embodiment of another method for synchronizing a record and replay platform.

<figref idref="DRAWINGS">FIG. 10A</figref> is a flow chart of an embodiment of a method for accelerating replay on an analysis platform.

<figref idref="DRAWINGS">FIG. 10B</figref> is a flow chart of an embodiment of another method for accelerating replay on an analysis platform.

DETAILED DESCRIPTION

0000A. Virtualization Platform Architecture

0018<figref idref="DRAWINGS">FIG. 1</figref> depicts functional block diagrams of virtualized computer systems in which one or more embodiments of the invention may be practiced. Computer system <b>100</b> may be constructed on a typical desktop or laptop hardware platform <b>102</b> such as an x86 architecture platform. Such a hardware platform may include CPU <b>104</b>, RAM <b>106</b>, network card <b>108</b>, hard drive <b>110</b> and other I/O devices such as a mouse and a keyboard (not shown in <figref idref="DRAWINGS">FIG. 1</figref>). Host operating system <b>112</b> such as Microsoft Windows, Linux or NetWare runs on top of hardware platform <b>102</b>. Virtualization software layer <b>114</b> is installed on top of host operating system <b>112</b> and provides a virtual machine execution space <b>116</b> within which multiple virtual machines (VMs) <b>118</b>₁-<b>118</b>_Nmay be concurrently instantiated and executed. In particular, virtualization layer <b>114</b> maps physical resources of hardware platform <b>102</b> (e.g., CPU <b>104</b>, RAM <b>106</b>, network card <b>108</b>, hard drive <b>110</b>, mouse, keyboard, etc.) to “virtual” resources of each virtual machine <b>118</b>₁-<b>118</b>_N, such that each virtual machine <b>118</b>₁-<b>118</b>_Nhas its own virtual hardware platform <b>120</b> with its own emulated CPU <b>122</b>, RAM <b>124</b>, network card <b>126</b>, hard drive <b>128</b> and other emulated I/O devices. For example, virtual hardware platform <b>120</b> may function as the equivalent of a standard x86 hardware architecture such that any x86 supported operating system such as Microsoft Windows, Linux, Solaris x86, NetWare, FreeBSD, etc. may be installed as guest operating system <b>130</b> to execute applications <b>132</b> for an instantiated virtual machine such as <b>118</b>₁. As part of virtualization layer <b>114</b>, virtual machine monitors (VMM) <b>134</b>_A-<b>134</b>_Nimplement virtual system support needed to coordinate operation between host operating system <b>112</b> and its corresponding virtual machines <b>118</b>₁-<b>118</b>_N. An example of software implementing virtualization layer <b>114</b> for a desktop or laptop hardware platform <b>102</b> is VMware Workstation 6™ which is available from VMware™ Inc. of Palo Alto, Calif.

0019Computer system <b>150</b> is an alternative system in which one or more embodiments of the invention may be practiced. Computer system <b>150</b> may be constructed on a conventional server-class, hardware platform <b>152</b> including host bus adapters (HBA) <b>154</b> in addition to conventional platform processor, memory, and other standard peripheral components (not separately shown). Hardware platform <b>152</b> may be coupled to an enterprise-class storage system <b>182</b>. Examples of storage systems <b>182</b> may be a network attached storage (NAS) device, storage area network (SAN) arrays, or any other similar disk arrays. It should also be recognized that enterprise-level implementations of the foregoing may have multiple computer systems similar to computer system <b>150</b> that may be connected through various different known topologies and technologies (e.g., switches, etc.) to multiple storage systems <b>182</b>. A virtualization software layer (also sometimes referred to as a hypervisor) such as, for example, VMware's VMkernel™ <b>156</b> in its server-grade VMware ESX™ product, is installed on top of hardware platform <b>152</b> and supports a virtual machine execution space <b>158</b> within which multiple VMs <b>160</b>₁-<b>160</b>_Nmay be concurrently instantiated and executed. Each such virtual machine <b>160</b>₁-<b>160</b>_Nimplements a virtual hardware (HW) platform <b>162</b> that supports the installation of a guest operating system <b>164</b> which is capable of executing applications <b>166</b>. Similar to guest operating system <b>130</b>, examples of guest operating system <b>164</b> may be Microsoft Windows, Linux, Solaris x86, NetWare, FreeBSD or any other supported operating system. In each instance, guest operating system <b>164</b> includes a native file system layer (not shown), for example, either an NTFS or an ext3 type file system layer. These file system layers interface with virtual hardware platform <b>162</b> to access, from the perspective of guest operating systems <b>164</b>, a data storage HBA, which in reality, is virtual HBA <b>168</b> implemented by virtual hardware platform <b>162</b> that provides the appearance of disk storage support (i.e., virtual disks <b>170</b>_A-<b>170</b>_X) to enable execution of guest operating system <b>164</b> transparent to the virtualization of the system hardware.

0020Although, from the perspective of guest operating systems <b>164</b>, file system calls to initiate file system-related data transfer and control operations appear to be routed to virtual disks <b>170</b>_A-<b>170</b>_X, in reality, such calls are processed and passed through virtual HBA <b>168</b> to adjunct virtualization software layers (for example, VMM layers <b>172</b>_A-<b>172</b>_N) that implement the virtual system support needed to coordinate operation with VMkernel <b>156</b>. In particular, host bus emulator <b>174</b> functionally enables guest operating system file system calls to be correctly handled by VMkernel <b>156</b> which passes such operations through to true HBAs <b>154</b> that connect to storage system <b>182</b>. For example, VMkernel <b>156</b> receives file system calls from VMM layers <b>172</b>_A-<b>172</b>_N, and converts them into file system operations that are understood by virtual machine file system (VMFS) <b>176</b> which in general, manages creation, use, and deletion of files stored on storage system <b>182</b>. VMFS <b>176</b>, in turn, converts the file system operations to volume block operations, and provides the volume block operations to logical volume manager (LVM) <b>178</b>, which supports volume oriented virtualization and management of the disk volumes in storage system <b>182</b>. LVM <b>178</b> converts the volume block operations into raw disk operations for transmission to device access layer <b>180</b>. Device access layer <b>180</b>, including device drivers (not shown), applies command queuing and scheduling policies to raw disk operations and sends them to HBAs <b>154</b> for delivery to storage system <b>182</b>.

0000B. Deterministic VM Record and Replay Functionality

0021One or more embodiments of the invention leverage the capability of certain virtual machine platforms to record and subsequently replay execution behavior of virtual machines. An example of a virtual machine with such record and replay features in which embodiments of the invention can be implemented is VMware Workstation 6 which is available from VMware Inc. of Palo Alto, Calif. To support replay, inputs to the CPU that are not included in the state of the guest operating system memory, registers or disk are supplied to the CPU of the replaying virtual machine. As depicted in <figref idref="DRAWINGS">FIG. 2</figref>, in one embodiment, VM <b>200</b> (the “recording VM”) records information corresponding to non-deterministic events that occur within its instruction stream in log file <b>260</b>. Examples of such non-deterministic events include reads from external devices (e.g., network, keyboard or timer, etc.) (see, e.g., <b>225</b> and <b>230</b>) and virtual machine interrupts (e.g., an indication after a data read instruction that DMA transfer from disk has been completed and is ready to be read, etc.). VM <b>235</b> (the “replaying VM”) replaying the instruction stream of recording VM <b>200</b> consumes the recorded information in log file <b>260</b>. Recording VM <b>200</b> and replaying VM <b>235</b> are instantiated from the same type of virtualization layer <b>205</b> and <b>245</b> (although they may be hosted on different hardware platforms <b>210</b> and <b>240</b>) and share the same types of emulated resources and devices (see <b>215</b> and <b>250</b>). Given a particular input to a particular emulated resource or device, both recording VM <b>200</b> and replaying VM <b>235</b> will deterministically output the same result. As such, non-deterministic inputs into emulated devices <b>215</b> (e.g., network data and user input) of recording VM <b>200</b> are recorded (as indicated by line <b>265</b>) into log file <b>260</b> so they can be delivered (as indicated by line <b>270</b>) to the corresponding emulated devices <b>250</b> of replaying VM <b>235</b>. If recording VM <b>200</b> and replaying VM <b>235</b> begin from the same initial VM state (e.g., same guest operating systems, see <b>220</b> and <b>255</b>, memory, registers, disk, etc.) and replaying VM <b>235</b> knows when to insert the next non-deterministic event occurring in the instruction stream of recording VM <b>200</b>, then replaying VM <b>235</b> will accurately recreate the instruction stream of recording VM <b>200</b>.

0022A record and replay functionality, as implemented in one or more embodiments of the invention, is depicted in the flowchart of <figref idref="DRAWINGS">FIG. 3</figref>. First, the VMM of recording VM <b>324</b> enables the recording feature (step <b>300</b>), takes a snapshot of the VM state (e.g., guest memory, registers, disks, etc.) (step <b>302</b>), and begins tracking system behavior (including CPU and device activity) as recording VM <b>324</b> executes (step <b>304</b>). When non-deterministic events such as device interrupts or other asynchronous events occur (step <b>306</b>), information relating to such events is recorded in a log file (step <b>308</b>). Such information includes timing (e.g., placement within the instruction stream, such as the n^thinstruction in the stream) of the occurrence so that replaying VM <b>326</b> can execute the event at the same time within its own instruction stream. For example, the timing of a virtual machine interrupt indicating that DMA transfer from an emulated hard drive has been completed may be recorded in the log file. However, the data value of the DMA transfer itself may not necessarily be recorded because the same type of hard drive is emulated on both recording VM <b>324</b> and replaying VM <b>326</b> such that the emulated hard drive of replaying VM <b>326</b> can deterministically output the correct data upon replaying the interrupt at the right time. For other non-deterministic events, additional data may be recorded in addition to timing information. For example, for emulated devices that support external inputs such as a keyboard, mouse, or network card, data values such as user key press, mouse movement and clicks, network data, etc. are recorded in the log file in addition to timing information since the corresponding emulated devices of replaying VM <b>326</b> cannot deterministically recreate such external inputs. Similarly, reads of a timer of recording VM <b>326</b> may also record the value of the timer since such a value cannot be deterministically obtained from the timer of replaying VM <b>326</b>. After such events are recorded in step <b>308</b>, the flow then returns to step <b>304</b>.

0023Replaying VM <b>326</b> is instantiated from the snapshot taken in step <b>302</b> (step <b>312</b>) and replaying VM <b>326</b> tracks the timing of the execution of its instruction stream in step <b>314</b>. If the log file recorded by recording VM <b>324</b> indicates the occurrence of a non-deterministic event (step <b>316</b>), the VMM of replay VM <b>326</b> feeds the non-deterministic event into the instruction stream of replay VM <b>326</b> at the same point in time that it occurred during the original execution (step <b>318</b>). Replaying VM <b>326</b> executes the event, for example, by timely delivering external input data recorded in the log file such as key presses, mouse movements and network data to the appropriate emulated devices (e.g., keyboard, mouse, network card, etc.) to be deterministically replayed by such devices or by timely inserting interrupts into the CPU instruction stream to retrieve outputs deterministically made available by emulated devices (e.g., hard drive data output responses after CPU read requests) (step <b>320</b>). The flow then returns to step <b>314</b> to handle subsequent non-deterministic events in the log file, if any.

0024<figref idref="DRAWINGS">FIG. 4</figref> is a block diagram depicting one embodiment of a “heterogenous” record and replay platform. In this embodiment, the execution behavior of a workload is recorded on one platform, such as virtual machine platform <b>400</b>, and then replayed on a different (i.e., heterogeneous) platform that does not share the same types of emulated devices as the first platform, such as processor simulator <b>430</b>. An example of processor simulator <b>430</b> in which embodiments of the invention can be implemented is the open source x86 simulator QEMU. Similar to the virtual machine platforms of <figref idref="DRAWINGS">FIG. 1</figref>, recording virtual machine platform <b>400</b> has a virtualization layer <b>405</b> that maps physical hardware <b>410</b> of the actual computer system to emulated hardware <b>415</b> (which may be different from the physical hardware) that is exposed to guest operating system <b>420</b>. Guest operating system <b>420</b> and emulated hardware <b>415</b> interact with each other through emulated hardware interfaces <b>425</b> (e.g., hardware port accesses, memory mapped I/O, etc.) which format requests to and responses from the emulated devices into data packages specific for such emulated devices. Similarly, replaying processor simulator platform <b>430</b> has processor simulator layer <b>435</b> that maps physical hardware <b>440</b> of its computer system to its emulated hardware <b>445</b> (which are different from emulated hardware <b>415</b> of virtual machine platform <b>400</b>) that is exposed to guest operating system <b>450</b> (i.e., the same operating system as guest operating system <b>420</b>) through emulated hardware interface <b>455</b>.

0025Because processor simulator platform <b>430</b> does not emulate the same hardware as virtual machine platform <b>400</b>, instructions from the instruction stream of virtual machine platform <b>400</b> that involve requests made to emulated devices <b>415</b> (e.g., reads of the hard drive, etc.) cannot be deterministically replayed by a corresponding emulated device as in the embodiment of <figref idref="DRAWINGS">FIG. 3</figref>. As such, instead of recording the non-deterministic external inputs to emulated devices, virtual machine platform <b>400</b> records (as indicated by line <b>460</b>) in log file <b>465</b> the outputs from emulated devices <b>415</b> to the CPU as well as the corresponding specific emulated device data formatting information (e.g., data formatting packet structures, etc.) from emulated device interface <b>425</b>, in addition to timing information. In turn, replaying processor simulator <b>430</b> is modified so that the device data outputs and formatting are consumed directly from log file <b>465</b> rather than from emulated device layer <b>445</b> (as indicated by line <b>485</b>).

0026A flowchart depicting record and replay between the heterogeneous platforms of <figref idref="DRAWINGS">FIG. 4</figref> is depicted in <figref idref="DRAWINGS">FIG. 5</figref>. First, the VMM of recording VM <b>524</b> enables the record feature (step <b>500</b>), takes a snapshot of the VM state (e.g., guest memory, registers, disks, etc.) (step <b>502</b>), and begins tracking system behavior (including CPU and device activity) as recording VM <b>524</b> executes (step <b>504</b>). When non-deterministic events such as device interrupts or other asynchronous events occur (step <b>506</b>), information relating to such events is recorded in a log file (step <b>508</b>). Such information includes the timing (e.g., placement within the instruction stream) of the occurrence and device data outputs to the CPU (as specifically formatted by the emulated devices of recording VM <b>524</b>) so that replaying simulator <b>526</b> can execute the event at the same place within its own instruction stream and simulate any data outputs from the emulated device associated with recording VM <b>524</b> by transmitting to the simulated processor system the data output recorded in the log file (in the format that would have been transmitted by the emulated device). Unlike step <b>320</b> in <figref idref="DRAWINGS">FIG. 3</figref>, the recording of external inputs to emulated devices such as user key presses, mouse movements and clicks, network data, etc. are not necessary in the embodiment of <figref idref="DRAWINGS">FIG. 5</figref> because the data outputs of these emulated devices that are recorded in the log file already capture such information. After recording such events, the flow then returns to step <b>504</b>.

0027Replaying simulator <b>526</b> is instantiated based upon information in the snapshot taken in step <b>502</b> (step <b>512</b>) and tracks the timing of the execution of its instruction stream in step <b>514</b>. If the log file recorded by recording VM <b>524</b> indicates the occurrence of a non-deterministic event (step <b>516</b>), replaying simulator <b>526</b> feeds the non-deterministic event into its instruction stream at the same point in time that it occurred during the original execution of recording VM <b>524</b> (step <b>518</b>). Processor simulator <b>526</b> executes the event, for example, by timely delivering any related device data output (in the proper emulated device format) in the log file for access by the emulated CPU of processor simulator <b>526</b> (step <b>520</b>). The flow then returns to step <b>514</b>.

0028It should be recognized that variations on the heterogeneity of the recording and replaying platforms may be implemented in an embodiment without departing from the spirit of the invention. For example, rather than a replaying simulator as in <figref idref="DRAWINGS">FIGS. 4 and 5</figref>, a different virtual machine platform supporting different emulated devices may be used to replay the recording VM's execution behavior.

0000C. Decoupling Analysis from Workload

0029<figref idref="DRAWINGS">FIG. 6</figref> is a schematic diagram of dynamic analysis platforms according to one or more embodiments of the invention. Dynamic program analysis is performed by decoupling analysis from a main workload while providing the analysis with the identical and complete sequence of states from the main workload as if they were not decoupled. Such decoupling allows the analysis to be added to a running system without fear of breaking the main workload. Furthermore, because the analysis is run on a separate system from the main workload, new analyses can be carried out without changing the running applications, operating system or VMM of the main workload.

0030In one embodiment, a record feature is enabled on a VM running main workload <b>600</b>, thereby creating replay log <b>605</b> that is fed into a different instantiated VM <b>610</b> that has been loaded with an initial recorded snapshot of main workload VM <b>600</b>. VMM <b>615</b> of replay VM <b>610</b> includes dynamic program analysis platform <b>620</b> that is executed during replay. A similar decoupled dynamic program analysis platform <b>625</b> can be built in simulation layer <b>630</b> of a replaying heterogeneous platform such as replay simulator <b>635</b>. In these systems, when analysis code is executed, the order of recorded and replayed instructions streams are not affected because dynamic program analysis platform <b>620</b> or <b>625</b> is implemented at the level of VMM <b>615</b> or simulation layer <b>630</b>, which are able to programmatically ignore or otherwise remove instructions relating to the analysis code when generating the virtual machine or simulated processor instruction streams.

0031The decoupling of analysis from the main workload as described herein further enables embodiments to scale and run multiple analyses as depicted in <b>650</b> and <b>655</b> for the same workload. In one embodiment, the decoupled analyses are run in parallel with the main workload. In another embodiment, the decoupled analyses are run in parallel with each other. Without decoupling, running multiple analyses would require separate execution runs per analysis and would therefore suffer from the likelihood of divergent runs and inconsistent analyses. Furthermore, decoupling enables optimization techniques to be separately applied to main workload VM <b>600</b> and the analysis platforms (e.g., <b>610</b> and <b>635</b>). For example, main workload VM <b>600</b> can be optimized for real-time performance and responsiveness while the analysis platforms (e.g., <b>610</b> and <b>635</b>) can be separately optimized for ease of instrumentation during analysis.

0032It should be recognized that dynamic analysis may be implemented in VMM layer <b>615</b> or simulation layer <b>630</b> of a replay system in a variety of ways. For example, in one embodiment, ad-hoc hooks that supply callbacks when events of interest happen may be built into the replaying environment OS. Similarly, dynamic analysis may be implemented through dynamic binary translation (BT), which dynamically translates a set of instructions into an alternative set of instructions on the fly, when are then executed. Performing dynamic analysis at the level of VMM <b>615</b> or simulation layer <b>630</b> provides visibility at all layers of the software stack, thereby enabling embodiments to analyze operating systems, applications, and interactions across components. For example, any individual process running in guest operating system as well as the guest OS kernel itself can be a target of analysis.

0033It should be recognized that decoupling analysis according to one or more embodiments of the invention may treat the timing of the analysis/replay system differently to achieve certain results in performance and safety. For example, for situations where timely analysis results are critical, such as intrusion detection and prevention, the analysis/replay system may be executed in parallel with the main workload VM, with the output of the workload synchronized with the analysis. For situations that can tolerate some lag between analysis and workload, the analysis/replay system may be run in parallel with the workload, but with no synchronization between the output of the workload and analysis. For situations where analyses are not known beforehand or are not time critical, such as debugging, the analysis/replay system can be run offline. For example, system administrators can use intensive checks for data consistency, taint propagation, and virus scanning on their production systems. Developers can run intensive analyses for memory safety and invariant checking as part of their normal debugging, or as additional offline checks that augment testing that must already be performed in a quality-assurance department. Computer architects can capture the execution of a production system with little overhead, then analyze the captured instruction stream on a timing-accurate, circuit-level simulator. Because decoupling can be done offline, analysis that was not foreseen during the original run can be performed with users iteratively developing and running new analysis on the original execution behavior of the main workload VM.

0000D. Improving Heterogeneous Replay

0034As previously discussed in the context of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>, heterogeneous record and replay systems require the recording VM to monitor and record more information into the replay log file than systems that utilize the same virtual machine platform (i.e., “homogeneous” systems), such as the systems of <figref idref="DRAWINGS">FIGS. 2 and 3</figref>. For example, the heterogeneous record and replay systems of <figref idref="DRAWINGS">FIGS. 4 and 5</figref> record the data outputs from emulated devices to the CPU, corresponding emulated device data formatting information (e.g., data formatting packet structures, etc.) from emulated device interface <b>425</b> and timing information into the log file while the homogenous record and replay embodiment of <figref idref="DRAWINGS">FIGS. 2 and 3</figref> record only the timing of non-deterministic events and external inputs to emulated devices. The increased level of recording in heterogeneous systems can affect the overall execution behavior of the main workload in the recording VM, for example, by slowing it down.

0035<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram depicting one embodiment of a heterogeneous record and replay platform using a relog file to improve performance. An intermediary homogeneous replay VM <b>725</b> is placed in between main workload recording VM <b>700</b> and heterogeneous replay and analysis simulator <b>755</b> to reduce the level of recording responsibilities on main workload recording VM <b>700</b>. Similar to recording VM <b>200</b> in <figref idref="DRAWINGS">FIG. 2</figref>, recording VM <b>700</b> assumes that a virtual machine instantiated on the same virtual machine platform replays its log file <b>785</b>. External inputs to physical devices <b>710</b> such as incoming network data <b>702</b> and user interaction with a keyboard and mouse <b>704</b> are mapped by virtualization layer <b>705</b> into external inputs to corresponding emulated devices <b>715</b>. The timing and values of these external inputs are recorded into log file <b>785</b> (as indicated by line <b>742</b>), in addition to timing for other non deterministic events such as interrupts.

0036To replay the execution behavior of recording VM <b>700</b>, replaying VM <b>725</b> consumes the recorded information in log file <b>785</b>. In particular, virtualization layer <b>730</b> delivers the external input values and related timing information in log file <b>785</b> (as indicated by line <b>744</b>) to corresponding emulated devices <b>740</b> of replaying VM <b>725</b> (i.e., any external inputs to physical layer <b>735</b> of replaying VM <b>725</b> are ignored during a replay session). Corresponding emulated devices <b>740</b> of replaying VM <b>725</b> are thus able to deterministically replay the receiving of external inputs and format the data inputs into a data package understandable by guest operating system <b>750</b> through emulated device interface <b>745</b>. To support heterogeneous replay, virtualization layer <b>730</b> further records the data format packet structures supported by emulated device interface <b>745</b> as well as the data values themselves and timing information (i.e., timing of the device interrupts) into relog file <b>790</b> (as indicated by line <b>782</b>).

0037Analysis platform <b>755</b> of <figref idref="DRAWINGS">FIG. 7</figref> is a processor simulator that does not share the same emulated devices as recording VM <b>700</b> and replaying VM <b>725</b>. For example, while recording VM <b>700</b> and replaying VM <b>725</b> are each virtual machines running the same type of guest operating system <b>720</b> and <b>750</b> (such as Microsoft Windows) on top of emulated x86 virtual platforms <b>705</b> and <b>730</b> (such as VMware Workstation 6) with the same emulated devices <b>715</b> and <b>740</b> running on top of Microsoft Windows as their hosted operating systems (not shown) on top of an actual x86 architecture platform <b>710</b> and <b>735</b>, analysis simulator <b>755</b> is implemented on an AMD hardware platform <b>765</b> running Linux as its hosted operating system (not shown) with the open source emulator QEMU as simulator layer <b>760</b> running on top of Linux with a set of emulated devices <b>770</b> that are different from emulated devices <b>715</b> and <b>740</b>. Guest operating system <b>775</b> running on top of simulator layer <b>760</b> in such an embodiment would also be Microsoft Windows to replay the execution behavior of recording VM <b>700</b>. To replay the execution behavior of recording VM <b>700</b>, simulator layer <b>760</b> consumes the information in relog file <b>790</b> to recreate the instruction stream of recording VM <b>700</b>. In one embodiment, simulator layer <b>760</b> is modified (e.g., a modified QEMU) such that its original emulated device interfaces <b>780</b> are removed or otherwise supplanted by the delivery of device outputs recorded in the proper emulated device format to the simulated processor (and ultimately to be acted upon by guest operating system <b>775</b>) through relog file <b>790</b> represented by arrow <b>784</b>.

0038<figref idref="DRAWINGS">FIGS. 8A and 8B</figref> are flow charts depicting an embodiment of a method for recording and replaying execution behavior on a heterogeneous record and replay platform using a relog file to improve performance. Recording VM <b>800</b> executes and records the main workload of the system and consumes the same amount of computing resources as recording VM <b>324</b> of <figref idref="DRAWINGS">FIG. 3</figref> to provide a recording log file (steps <b>300</b> to <b>308</b> in <figref idref="DRAWINGS">FIG. 8</figref>) for replaying VM <b>805</b> that is instantiated from the same virtual platform as recording VM <b>800</b> and that has the same emulated devices as recording VM <b>800</b>.

0039Replaying VM <b>805</b> can be thought of as a combination of replaying VM <b>326</b> of <figref idref="DRAWINGS">FIG. 3</figref> and recording VM <b>524</b> of <figref idref="DRAWINGS">FIG. 5</figref>. In particular, replaying VM <b>805</b> consumes the contents of the log file created by recording VM <b>800</b> to recreate the execution behavior of recording VM <b>800</b> in a similar manner as replaying VM <b>326</b> of <figref idref="DRAWINGS">FIG. 3</figref> (see steps <b>312</b> to <b>320</b> in <figref idref="DRAWINGS">FIG. 8</figref>) but additionally has recording steps similar to recording VM <b>524</b> to further support replay on a heterogeneous platform. In particular, the VMM of replaying VM <b>805</b> turns on the recording feature in step <b>810</b> (analogous to step <b>500</b> of <figref idref="DRAWINGS">FIG. 5</figref>) and subsequently monitors the execution behavior for non-deterministic events such as device interrupts in step <b>815</b> (analogous to step <b>506</b> of <figref idref="DRAWINGS">FIG. 5</figref>) which have been inserted into the instruction stream in step <b>320</b> through the log file created by recording VM <b>800</b>. Similar to step <b>508</b> of <figref idref="DRAWINGS">FIG. 5</figref>, upon the occurrence of such non-deterministic events within the instruction stream, in step <b>820</b>, the VMM records the timing (e.g., placement within the instruction stream) of the occurrence and device data outputs to the CPU (as specifically formatted by the emulated devices of replaying VM <b>805</b>, which are the same types of emulated devices of recording VM <b>800</b>) into a second “relog” file such as <b>790</b> of <figref idref="DRAWINGS">FIG. 7</figref> so that replaying simulator <b>825</b> can execute the event at the same place within its own instruction stream and simulate any data outputs from replaying VM's <b>805</b> associated emulated device by transmitting to the simulated processor system the data output recorded in the relog file (in the format that would have been transmitted by the emulated device).

0040To replay the recording, replaying simulator <b>825</b> may be created based upon information in the snapshot taken in step <b>300</b> (step <b>512</b> in <figref idref="DRAWINGS">FIG. 8</figref>). By tracking the timing of the execution of its instruction stream in step <b>514</b> (in <figref idref="DRAWINGS">FIG. 8</figref>), replay simulator <b>825</b> delivers the non-deterministic events recorded in the relog file (step <b>830</b>) into the instruction stream of replay simulator <b>825</b> at the same point in time (i.e., within the instruction stream of recording VM <b>800</b>) that they occurred during the original execution (step <b>518</b> in <figref idref="DRAWINGS">FIG. 8</figref>). Replaying simulator <b>825</b> thereby recreates recording the instruction stream of recording VM's <b>800</b> by executing the event and delivering any related device data output (in the proper emulated device format) in the relog file to the CPU (step <b>835</b>). The flow then returns to step <b>514</b>.

0041It should be recognized that the particular embodiments of <figref idref="DRAWINGS">FIGS. 7, 8A and 8B</figref> are merely exemplary and that variations in certain flows or components may be made without departing from the spirit of the invention. For example, while <figref idref="DRAWINGS">FIGS. 7, 8A and 8B</figref> (as well as the previous figures) depict embodiments having log and relog files stored persistently on disk, it should be recognized that the non-deterministic event information of such files may also be stored and consumed at the RAM level or through a shared cache between the record and replay platforms without necessarily storing such files in persistent storage (e.g., analysis can take place by reading the log over the network without saving to disk).

0000E. Synchronizing Analysis and Workload

0042In certain embodiments, the decoupled analysis system runs in a synchronized fashion with the main workload. In one example, the decoupled analysis system executes analysis relating to security checks and upon identifying an intrusion, halts the main workload. In such embodiments, a feedback channel is used to provide communication between the main workload and the decoupled analysis system.

0043<figref idref="DRAWINGS">FIGS. 9A and 9B</figref> are flowcharts of embodiments of methods for synchronizing a main workload recording VM and a heterogeneous replay analysis simulator. It should be recognized that the same techniques may be used in an homogeneous embodiment using record and replay VMs, similar to <figref idref="DRAWINGS">FIG. 3</figref>. In the embodiment of <figref idref="DRAWINGS">FIG. 9A</figref>, main workload VM <b>900</b> performs the same recording and logging features as recording VM <b>524</b> (see steps <b>500</b> to <b>508</b>). However, whenever main workload VM <b>900</b> generates data outputs (e.g., data to be output to the network, etc.) (step <b>905</b>), the VMM intercepts such data output (step <b>910</b>) and blocks the execution of main workload VM <b>900</b> (step <b>915</b>). In <figref idref="DRAWINGS">FIG. 9A</figref>, main workload VM <b>900</b> requests a confirmation from replay analysis simulator <b>935</b> that it has reached the same point in its replay of the instruction stream of main workload VM <b>900</b> and has completed its analytics (e.g., for a intrusion detection embodiment, it has found no intrusions) (step <b>920</b>). When replay analysis simulator <b>935</b> receives such a request and has reached such a point, it will transmit a confirmation to main workload VM <b>900</b> (step <b>940</b>). When main workload VM <b>900</b> receives such a confirmation (step <b>925</b>), it then releases the data output (e.g., to the network) (step <b>930</b>). It should be recognized that slight variations in the flow of <figref idref="DRAWINGS">FIG. 9A</figref> do not detract from the scope or spirit of the invention. For example, in an alternative embodiment, main workload VM <b>900</b> does not transmit a request for confirmation to replay analysis simulator <b>925</b> as in step <b>920</b>; instead, main workload VM <b>900</b> blocks and waits for a communication of such confirmation from replay analysis simulator <b>925</b> which transmits such confirmations every time it generates a corresponding data output.

0044In <figref idref="DRAWINGS">FIG. 9B</figref>, main workload VM <b>945</b> does not block its execution when it has data to output. Instead, after main workload VM <b>945</b> generates data outputs (step <b>950</b>) and the VMM intercepts such data output (step <b>955</b>), the VMM places the data outputs in a queue for release (step <b>960</b>) but continues execution of main workload VM's <b>945</b> instruction stream. In the embodiment of <figref idref="DRAWINGS">FIG. 9B</figref>, replay analysis simulator <b>975</b> periodically transmits to main workload VM <b>945</b> the current timing of its instruction stream (and confirmation that is has conducted its program analysis up to that point) (step <b>980</b>). When main workload VM <b>945</b> receives such timing information (step <b>965</b>), it releases those data outputs in the queue that occurred up to that same time in main workload VM's <b>945</b> instruction stream (step <b>970</b>).

0045In certain embodiments implementing synchronization between a primary workload VM and an analysis platform (i.e., simulator or VM), the primary VM does not block the release of output until the analysis platform's instruction stream reaches the same output release point (as in <figref idref="DRAWINGS">FIGS. 9A and 9B</figref>). For certain types of analysis, the characteristics that are being analyzed on the analysis platform can be guaranteed in a discrete step prior to the occurrence of data outputs. For example, in one embodiment, the analysis platform performs a virus scan of all executables prior to their execution. In such an embodiment, the outputs of the primary workload VM are released as soon as the analysis platform completes the last applicable virus scan. Rather than waiting for the analysis platform to reach the data output point in its instruction stream, the primary workload VM waits until completion of the virus scan, which can occur prior to any related data output points.

0046Alternative embodiments may further enhance the synchronization between the main workload VM and analysis platform by limiting how far the main workload VM is allowed to run ahead of the analysis platform. For example, the analysis platform may transmit its current time in the replay of the main workload's instruction stream such that the main workload VM is able to verify that its own timing in the instruction stream is no greater than a predetermined time interval after the current time of the analysis platform. If the main workload VM is too far ahead, it may block until its timing falls within the predetermined time interval. Limiting the lag between the main workload VM and analysis platform limits the amount of time that the main workload's outputs are deferred, which in turn limits the amount of timing perturbation the main workload may observe (e.g., when it measures the round-trip time of a network).

0000F. Improving Performance of Analysis System

0047Because an analysis VM executes the same instructions as the primary workload VM in addition to performing the work of analysis, the analysis VM can become a bottleneck and slow down execution of the primary VM, for example, when running in a synchronous fashion as discussed in Section E. Optimizations may be made to the analysis platform to improve its execution performance. One such optimization, according to an embodiment of the invention, is based upon an observation that during replay on an analysis VM, interrupt delivery is or can be made immediate. For example, in x86 operating systems, the hit instruction is used to wait for interrupts; this saves power compared to idle spinning. One hit invocation waiting for a 10 ms timer interrupt can consume equal time to tens of millions of instructions on modern 1+GHz processors. During analysis, hit time passes instantaneously. As an example, the primary workload VM may be a typical interactive desktop workload with a user surfing the web. Idle times during which the user may be reading on the web or where human reaction times on the desktop are slow (e.g., opening applications, selecting menus, etc.) enable the execution of the analysis VM to catch up to the primary workload VM. As such, idle time can be deliberately increased in many run-time environments to assist the analysis VM in keeping up with the main workload VM. For example, idle time can be increased in server farms by adding more servers and balancing load across them.

0048Additionally, device I/O can be accelerated during replay. For example, in one embodiment, network writes need not be sent and network data is recorded in the replay log (similar to a heterogeneous system) such that network reads can use the network data from the replay log. This frees the analysis VM from waiting for network round-trip times, because disk throughput (to access the log) is often greater than end-to-end network throughput. Disk reads can similarly be satisfied from the replay log rather than the emulated hard disk of the analysis VM, and this can accelerate the analysis VM because the replay log is always read sequentially. This optimization can also free the analysis VM from executing disk writes during replay, which frees up physical disk bandwidth and allows completion interrupts to be delivered as soon as the instruction stream arrives at an appropriate spot to receive them. Disk reads done by the primary VM may also prefetch data and thereby accelerate subsequent reads by the analysis VM. In one exemplary embodiment, device I/O is further accelerated through the use of a shared cache of disk blocks when a primary workload VM and analysis VM are run on the same hardware platform. In this embodiment, when the primary workload VM executes, device I/O data and/or other log information is stored in the shared cache so that the analysis VM can access such data during replay rather than repeating the same device I/O.

0049<figref idref="DRAWINGS">FIG. 10A</figref> depicts a flowchart of an embodiment of a method for accelerating replay in a homogeneous environment. First, the VMM of recording VM <b>1024</b> enables the record feature (step <b>1000</b>), takes a snapshot of the VM state (step <b>1002</b>), and begins tracking system behavior as recording VM <b>1024</b> executes (step <b>1004</b>). When non-deterministic events such as device interrupts or other asynchronous events occur (step <b>1006</b>), information relating to such events are recorded in a log file (step <b>1008</b>). Such information includes the timing of the occurrence and device data outputs to the CPU (e.g., disk reads, network reads, etc.) so that analysis VM <b>1026</b> can consume the data directly from the log and avoid waiting for device I/O round trip times during replay. The flow then returns to step <b>1004</b>.

0050Analysis VM <b>1026</b> is instantiated based upon information in the snapshot taken in step <b>1002</b> (step <b>1012</b>) and tracks the timing of the execution of its instruction stream in step <b>1014</b>. If the log file recorded by recording VM <b>1024</b> indicates the occurrence of a non-deterministic event (step <b>1016</b>), analysis VM <b>1026</b> feeds the non-deterministic event into its instruction stream at the same point in time that it occurred during the original execution of the recording VM <b>1024</b> (step <b>1018</b>). Analysis VM <b>1026</b> executes the event and delivers any related device data output in the log file to its virtual processor, thereby avoiding any device I/O round trip times during replay (step <b>1020</b>). Because the log file is read contiguously by analysis VM <b>1026</b>, replay is accelerated in comparison to a slower random-access style disk I/O event that would have occurred had data been delivered to analysis VM's <b>1026</b> emulated hard disk to perform the device I/O (as in step <b>320</b> of <figref idref="DRAWINGS">FIG. 3</figref>). The flow then returns to step <b>1014</b>.

0051In another embodiment, operations that are executed during record are not replayed. One such example of this is exception checking. For example, x86 systems often check for exceptional conditions. Although these checks rarely raise exceptions, executing them adds overhead to an embodiment's emulated CPU. For example, with segment limit checks, every memory reference or instruction fetch must be checked that it is within bounds for an appropriate segment. Most accesses do not raise exceptions and interrupts are utilized to replay any exceptions that do occur. Decoupled analysis enables one to reduce the overhead of exception checking on an analysis simulator by leveraging the exception checking that has already occurred on the main workload VM. During logging, the time and location in the instruction stream of any exceptions are recorded, and these exceptions are delivered during replay just like other asynchronous replay events. This strategy frees the analysis simulator from the overhead of explicitly checking for exceptions during replay. Skipping these checks on the analysis simulator makes the CPU simulator faster and less complex, while still guaranteeing proper replay of a workload that contains violations of any checks (as reflected by the exceptions recorded in the log file). It should be recognized that many checks can be similarly skipped in embodiments of the invention, including debug exceptions, control transfer checks for segment changes, the alignment check (which when enabled, ensures all memory accesses are performed through pointers aligned to appropriate boundaries) and others.

0052<figref idref="DRAWINGS">FIG. 10B</figref> depicts a flowchart of an embodiment of a method for accelerating replay on a heterogeneous system where analysis simulator <b>1040</b> skips exception checking that has already been performed by recording VM <b>1024</b>. Recording VM <b>1024</b> takes the same initial steps <b>1000</b> to <b>1004</b> as the embodiment of <figref idref="DRAWINGS">FIG. 10A</figref>. When non-deterministic events such as device interrupts or other asynchronous events occur (step <b>1006</b>), information relating to such events are recorded in a log file (step <b>1009</b>, which is similar to step <b>508</b> in heterogeneous environments). Such events include exceptions that are generated pursuant to exception checking, because exceptions are non-deterministic events. The flow then returns to step <b>1004</b>.

0053Analysis simulator <b>1040</b> is instantiated based upon information in the snapshot taken in step <b>1002</b> (step <b>1028</b>), turns off exception checking (step <b>1030</b>), and tracks the timing of the execution of its instruction stream in step <b>1032</b>. By turning off exception checking, analysis simulator <b>1040</b> is able to utilize computing resources that would have been allocated for exception checking to accelerate execution. If the log file recorded by recording VM <b>1024</b> indicates the occurrence of a non-deterministic event (step <b>134</b>), analysis simulator <b>1040</b> feeds the non-deterministic event into its instruction stream at the same point in time when it occurred during the original execution of the recording VM <b>1024</b> (step <b>1036</b>). As noted previously, exceptions are non-deterministic events and would be recorded in the log file. In step <b>1038</b>, analysis simulator <b>1040</b> executes events (including exceptions) and delivers external input data recorded in the log file such as key presses, mouse movements and network data to the appropriate emulated devices (e.g., keyboard, mouse, network card, etc.) to be deterministically replayed by such devices or timely inserting interrupts into the CPU instruction stream to retrieve outputs deterministically made available by emulated devices (e.g., hard drive data output responses after CPU read requests). The flow then returns to step <b>1032</b>.

0054It should be recognized that various optimization techniques such as those discussed in this Section F can be combined into a single embodiment of the invention which may utilize either a VM or CPU simulator for analysis, depending upon the techniques selected.

0055The invention has been described above with reference to specific embodiments. Persons skilled in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. For example, while the foregoing discussions have generally discussed recording and replay VMs having the same emulated devices, it should be recognized that many of the teachings herein can also be performed at the hardware level, so long as the recording and replay VMs have the same physical hardware devices as well. Similarly, the foregoing discussions have discussed timing of the instruction stream in a general sense. It should be recognized that such timing may be measured at the instruction level (i.e., the n^thinstruction in the instruction stream) but that other measurements of time may be implemented in certain embodiments, for example, clock cycles, assuming certain guarantees of timing in the hardware platform.

0056The various embodiments described herein may employ various computer-implemented operations involving data stored in computer systems. For example, these operations may require physical manipulation of physical quantities usually, though not necessarily, these quantities may take the form of electrical or magnetic signals where they, or representations of them, are capable of being stored, transferred, combined, compared, or otherwise manipulated. Further, such manipulations are often referred to in terms, such as producing, identifying, determining, or comparing. Any operations described herein that form part of one or more embodiments of the invention may be useful machine operations. In addition, one or more embodiments of the invention also relate to a device or an apparatus for performing these operations. The apparatus may be specially constructed for specific required purposes, or it may be a general purpose computer selectively activated or configured by a computer program stored in the computer. In particular, various general purpose machines may be used with computer programs written in accordance with the teachings herein, or it may be more convenient to construct a more specialized apparatus to perform the required operations.

0057The various embodiments described herein may be practiced with other computer system configurations including hand-held devices, microprocessor systems, microprocessor-based or programmable consumer electronics, minicomputers, mainframe computers, and the like.

0058One or more embodiments of the present invention may be implemented as one or more computer programs or as one or more computer program modules embodied in one or more computer readable media. The term computer readable medium refers to any data storage device that can store data which can thereafter be input to a computer system computer readable media may be based on any existing or subsequently developed technology for embodying computer programs in a manner that enables them to be read by a computer. Examples of a computer readable medium include a hard drive, network attached storage (NAS), read-only memory, random-access memory (e.g., a flash memory device), a CD (Compact Discs) CD-ROM, a CD-R, or a CD-RW, a DVD (Digital Versatile Disc), a magnetic tape, and other optical and non-optical data storage devices. The computer readable medium can also be distributed over a network coupled computer system so that the computer readable code is stored and executed in a distributed fashion.

0059Although one or more embodiments of the present invention have been described in some detail for clarity of understanding, it will be apparent that certain changes and modifications may be made within the scope of the claims. Accordingly, the described embodiments are to be considered as illustrative and not restrictive, and the scope of the claims is not to be limited to details given herein, but may be modified within the scope and equivalents of the claims. In the claims, elements and/or steps do not imply any particular order of operation, unless explicitly stated in the claims.

0060In addition, while described virtualization methods have generally assumed that virtual machines present interfaces consistent with a particular hardware system, persons of ordinary skill in the art will recognize that the methods described may be used in conjunction with virtualizations that do not correspond directly to any particular hardware system. Virtualization systems in accordance with the various embodiments, implemented as hosted embodiments, non-hosted embodiments, or as embodiments that tend to blur distinctions between the two, are all envisioned. Furthermore, various virtualization operations may be wholly or partially implemented in hardware. For example, a hardware implementation may employ a look-up table for modification of storage access requests to secure non-disk data.

0061Many variations, modifications, additions, and improvements are possible, regardless the degree of virtualization. The virtualization software can therefore include components of a host, console, or guest operating system that performs virtualization functions. Plural instances may be provided for components, operations or structures described herein as a single instance. Finally, boundaries between various components, operations and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of the invention(s). In general, structures and functionality presented as separate components in exemplary configurations may be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component may be implemented as separate components. These and other variations, modifications, additions, and improvements may fall within the scope of the appended claims(s).