# Flexible Non-intrusive Dynamic Instrumentation for WebAssembly

Ben L. Titzer<EMAIL_ADDRESS>Carnegie Mellon
UniversityPittsburghPAUSA ,  Elizabeth Gilbert<EMAIL_ADDRESS>Carnegie Mellon UniversityPittsburghPAUSA ,  Bradley Wei Jie Teo
<EMAIL_ADDRESS>Carnegie Mellon UniversityPittsburghPAUSA ,  Yash
Anand<EMAIL_ADDRESS>Carnegie Mellon UniversityPittsburghPAUSA ,
Kazuyuki Takayama<EMAIL_ADDRESS>Carnegie Mellon
UniversityPittsburghPAUSA and  Heather Miller<EMAIL_ADDRESS>Carnegie Mellon UniversityPittsburghPAUSA

###### Abstract.

A key strength of managed runtimes over hardware is the ability to gain
detailed insight into the dynamic execution of programs with instrumentation.
Analyses such as code coverage, execution frequency, tracing, and debugging,
are all made easier in a virtual setting. As a portable, low-level bytecode,
WebAssembly offers inexpensive in-process sandboxing with high performance.
Yet to date, Wasm engines have not offered much insight into executing
programs, supporting at best bytecode-level stepping and basic source maps,
but no instrumentation capabilities. In this paper, we show the first non-
intrusive dynamic instrumentation system for WebAssembly in the open-source
Wizard Research Engine††https://github.com/titzer/wizard-engine. Our
innovative design offers a flexible, complete hierarchy of instrumentation
primitives that support building high-level, complex analyses in terms of low-
level, programmable probes. In contrast to emulation or machine code
instrumentation, injecting probes at the bytecode level increases
expressiveness and vastly simplifies the implementation by reusing the
engine’s JIT compiler, interpreter, and deoptimization mechanism rather than
building new ones. Wizard supports both dynamic instrumentation insertion and
removal while providing consistency guarantees, which is key to composing
multiple analyses without interference. We detail a fully-featured
implementation in a high-performance multi-tier Wasm engine, show novel
optimizations specifically designed to minimize instrumentation overhead, and
evaluate performance characteristics under load from various analyses. This
design is well-suited for production engine adoption as probes can be
implemented to have no impact on production performance when not in use.

##  1\. Introduction

Programs have bugs and sometimes run slow. Understanding the dynamic behavior
of programs is key to debugging, profiling, and optimizing programs so that
they execute correctly and efficiently. Program behavior can be extremely
complex with millions of interesting events (SideEffectRewriting, )
(DynamicMetricsForJava, ) (DynPrefetch, ) (RuntimeObjProfiler, ) (JPortal, ).
Clearly manual inspection cannot scale and programmatic observation is
required.

###  1.1. Monitors and M-code

Just as we use the common term _application_ to refer to a self-contained
program, we will use the term _monitor_ to refer to a self-contained
_analysis_ which monitors an application and observes execution events and
internal states. For example, a profile monitor might count the number of
runtime iterations of a loop or the execution count of basic blocks. A monitor
may _instrument_ programs using various mechanisms, before or during
execution, execute runtime logic during program execution, and generate a
post-execution report. Of particular interest is a monitor’s additional
runtime storage and logic, which we refer to as _monitor data_ and _monitor
code_. For example, a profile monitor’s data includes counters and the monitor
code includes the updates and reporting of counters. Monitor code may be
written in a high-level language and compiled to a lower form. We will use
M-code to refer to the actual monitor code that will be executed at runtime.
M-code may take many forms, including injected bytecode, source code, or
machine code, utilities in the engine itself such as tracing modes, or
extensions to the engine.

While most monitors aim to observe program behavior without changing it, the
implementation technique may not always guarantee this. For example, injecting
M-code by overwriting machine code in a native program is fraught with peril
because native programs can observe machine-level details such as reading
their own code as data. Robustly separating monitor data from program data is
a common problem. Some approaches, such as emulation, avoid these low-level
complexities and are inherently _side-effect free_ as they fully virtualize
the execution model and M-code can operate outside of this virtual execution
context.

####  1.1.1. Intrusive approaches

We say a monitor is _intrusive_ if it alters program behavior in a
semantically observable way, i.e. it has side-effects on program state.
Intrusiveness is a property of the monitor together with the chosen technique
for implementing instrumentation. For example, instrumenting a native program
that reads its own code as data could be intrusive if done with code
injection, but non-intrusive with an emulator. The intrusiveness of a monitor
is independent of whether it _perturbs_ performance characteristics such as
execution time and memory consumption111Often, non-intrusive implementation
techniques allow measuring memory consumption of the program and monitor
separately..

Instrumentation implementations that risk intrusiveness include static and
dynamic code rewriting techniques.

Static rewriting. If the execution platform does not directly offer debugging
and inspection services, _static rewriting_ is often used where source code,
bytecode, or machine code is injected directly into the program before
execution. Static rewriting has its advantages:

  * $\bm{+}$

no support from the execution platform is necessary; will work anywhere

  * $\bm{+}$

not limited by the instrumentation capabilities of underlying execution
platform; can do anything

  * $\bm{+}$

inserted M-code can be small and inline; approaches minimal overhead

  * $\bm{+}$

instrumentation overhead is fixed before runtime; no dynamic instrumentation
costs

However, static rewriting can also have disadvantages:

  * $\bm{-}$

M-code intrudes on the state space of the code under test; easier to break the
program

  * $\bm{-}$

for machine- and bytecode-level instrumentation, M-code must necessarily be
low-level; more tedious to implement

  * $\bm{-}$

for machine code, the binary may need to be reorganized to fit
instrumentation; may not always be possible

  * $\bm{-}$

offline instrumentation must instrument all possible events of interest;
cannot dynamically adapt

  * $\bm{-}$

source-level locations and mappings are altered by added code; additional
mapping needed

  * $\bm{-}$

M-code perturbs performance in subtle and potentially complex ways;
unpredictable performance impacts

  * $\bm{-}$

pervasive instrumentation could massively increase code size; binary bloat

  * $\bm{-}$

some information is only dynamically discoverable; could miss libraries,
indirect calls, and generated code

Given these properties, this approach is frequently used and is demonstrated
in the source-level tool Oron (Oron, ), the bytecode-level tools BISM (BISM, )
and Wasabi (Wasabi, ), and the machine-code-level tool EEL (EEL, ), among
others.

Dynamic rewriting. In contrast to static rewriting, _dynamic rewriting_ allows
a monitor to add M-code at runtime. This remedies some of the static rewriting
disadvantages:

  * $\bm{+}$

can discover information only available at runtime

  * $\bm{+}$

can instrument 100% of the code

  * $\bm{+}$

does not require recompilation or relinking of binary

  * $\bm{+}$

potentially less code bloat

  * $\bm{+}$

can dynamically adapt to program behavior, instrumenting more or less

  * $\bm{+}$

implementation technique may be able to preserve some of the original
addresses

However, it can have its own disadvantages:

  * $\bm{-}$

more instrumentation cost is paid at runtime

  * $\bm{-}$

may make the execution platform vastly more complicated, e.g. requiring
dynamic recompilation

  * $\bm{-}$

the monitor is heavily coupled to the framework used to implement dynamic
instrumentation

This approach is very common and is demonstrated in the source-level tool
Jalangi (Jalangi, ), the bytecode-level tool DiSL (DISL, ), the machine-code-
level tools Dyninst (Dyninst, ), Pin (Pin, ) and Dtrace (DTrace, ), among
others (see Section 6).

####  1.1.2. Non-intrusive approaches

Several techniques exist that do not alter the program code or behavior; they
are side-effect free as their logic runs non-intrusively outside of the
program space. Debuggers for native binaries can use hardware-assisted
techniques such as debug registers, JTAG, and process tracing APIs to debug
programs directly on a CPU. Emulators can support debugging and tracing easily
in their interpreters.

Typically non-intrusive native mechanisms are slow, imposing orders of
magnitude execution time overhead. Yet accurately profiling high-frequency
events that happen millions of times per second (branches, method calls,
loops, and memory accesses) requires a more high-performance mechanism. For
limited cases such as profiling, Linux Perf (LinuxPerf, ) is a non-intrusive
sampling profiler that can analyze programs directly running on the CPU.
Valgrind (Valgrind, ) and QEMU (QEMU, ) are emulators with analysis features
and use dynamic binary translation via JIT compilation to reduce overheads.
Intel CPUs support a tracing mode known as Intel Processor Trace (IntelPT, )
that emits a densely-encoded history of branches, which can be used to
reconstruct program execution paths.

Managed runtime environments offer high-performance implementations of
languages and bytecode. Many offer APIs for observing and interacting with a
running program. Support for instrumentation can be standard tracing modes,
APIs for bytecode injection, or hot code reload (i.e. swapping the entire code
of a function or class at a time). For example, the Java Virtual Machine
offers JVMTI (JvmTI, ), and the .NET platform offers the .NET profiling API
(DotNetProfiling, ). JVMTI offers both intrusive (dynamic bytecode rewriting
with java.lang.instrument) and non-intrusive (Agents 222In JVMTI, users can
write _Agents_ in native code that fire when _Events_ occur in the running
application. They then interface with the program to query state or control
the execution itself.) mechanisms.

The flexible sensor network simulator Avrora (Avrora, ), powered by a
microcontroller emulator, allows monitors to attach M-code to code and memory
locations as well as clock events (NonIntrusive, ). The M-code is written in
Java and therefore runs outside of the emulated CPU. Its cycle-accurate
interpreter runs microcontroller code faster than realtime on desktop CPUs
without the need for a JIT.

Emulator and VM-based approaches still have the disadvantages of dynamic
rewriting, but have more advantages:

  * $\bm{+}$

non-intrusive instrumentation; side-effect free

  * $\bm{+}$

simplifies source-level address mapping

  * $\bm{+}$

no need to reorganize binaries

  * $\bm{+}$

can reuse existing JIT in engine; no instrumentation-specific JIT

  * $\bm{+}$

does not require writing M-code in a low-level language

  * $\bm{+}$

does not perturb memory consumption; logical separation between program and
monitor memory

###  1.2. WebAssembly

WebAssembly (WasmPldi, ), or Wasm for short, is a portable, low-level bytecode
that serves as a compilation target for many languages, including C/C++, Rust,
AssemblyScript, Java, Kotlin, OCaml, and many others. Initially released for
the Web, it has since seen uptake in many new contexts such as Cloud
(CloudflareWasm, ) and Edge computing (WasmEdgeDancer, ; FastlyEdge, ), IoT
(WasmIotOs, ; Aerogel, ), and embedded and industrial (WasmIndMach, ) systems.
Wasm is gaining momentum as the primary sandboxing mechanism in many new
computing platforms, as its execution model robustly separates Wasm module
instance state. The format is designed to be load- and run-time efficient with
many high-performance implementations. Wasm comes with strong safety
guarantees, starting with a strict formal specification (WasmSpec, ), a
mechanically-proven sound type system (WasmMechSpec, ), and implementations
being subjected to verification (WasmSandboxing, ).

Yet to date, no standard APIs for Wasm instrumentation exist. Only intrusive
instrumentation techniques exist today. To work around the lack of standard
APIs for instrumentation, several static bytecode rewriting tools have emerged
(Wasabi, ) (AspectWasm, ).

Wasm engines achieve near-native performance through AOT or JIT compilation.
Compilation is greatly simplified (over dynamic binary translation) as Wasm’s
code units are modules and functions rather than unstructured, arbitrarily-
addressable machine code. While Wasm JITs give excellent performance, some
engines such as JavaScriptCore (JavaScriptCore, ) and wasm3 (Wasm3, ) employ
interpreters either for startup time or memory footprint. Interpreters also
help debuggability and introspection; recent work (FastWasmInterp, ) outlined
a fast in-place interpreter design in the Wizard Research Engine.

###  1.3. Our contributions

Flexible Non-Intrusive Instrumentation. In this work, we describe the first
dynamic, non-intrusive (side-effect free) instrumentation framework for
WebAssembly and detail its implementation in the open-source Wizard
(WizardEngine, ) Research engine 333https://github.com/titzer/wizard-engine.
We show how to implement efficient support for _probes_ in a multi-tier Wasm
engine and how to build useful, complex analyses from this basic building
block, including tracing, profiling, and debugging.

Consistent Dynamic Instrumentation. In contrast with prior work, our system
also supports the dynamic insertion _and removal_ of individual probes. For
example, Pin supports dynamic clearing of instrumentation on a region of code,
but it is not probe-specific. Further, we make consistency guarantees about
when insertion and removal take effect, which allows multiple analyses to be
seamlessly composed.

Zero Overhead When Not Used. This framework imposes zero overhead for disabled
instrumentation. To our knowledge, it is the first system that leverages
_dispatch table switching_ to implement global probes, _bytecode overwriting_
for local probes, and specific JIT compiler support to achieve zero overhead
in all execution tiers.

JIT Intrinsification. We further show novel JIT optimizations that reduce the
overhead of common instrumentation tasks by intrinsifying some probes. We
evaluate the effectiveness on a standard suite of benchmarks and place our
system’s performance in context with related work.

Engine Mechanism Reuse. In contrast to Pin (Pin, ) and DynamoRIO (DynamoRIO,
), our work makes only minor additions to the existing execution tiers of the
Wasm engine (a few hundred lines of code), rather than a new, purpose-built
JIT (tens of thousands of lines of code). In the Wizard multi-tier research
engine, we cleverly444We observe that the deoptimization (and on-stack
replacement) mechanism already solves the hard problem of correct transfer
between optimization levels and can be repurposed for instrumentation, saving
tons of code. reuse its deoptimization mechanism to achieve these consistency
guarantees without needing to build a custom mechanism or resort to
interpretation only.

Feasible Production Adoption. Together, these innovations make it feasible for
production engines to provide direct support for instrumentation without
adding unnecessary complexity, putting powerful capabilities into the hands of
application developers.

Figure 1. Illustration of instrumentation in the interpreter. Global probes
can be inserted into the interpreter loop and local probes are implemented via
bytecode overwriting. The FrameAccessor API allows a probe programmatic access
to the state in the Wasm frame.

##  2\. Non-intrusive instrumentation in Wizard

High-performance virtual machines optimize execution time by cheating. JIT
compiler optimizations skip some unobservable execution steps of the abstract
machine. For example, not every update of a local variable or operand stack
value is modeled at runtime, but function-local storage is virtualized and
register-allocated. Yet monitoring a program for dynamic analysis inherently
observes intermediate states of a program, rather than just its final outcome.
Dynamic analyses typically observe states of the abstract machine, so VMs that
support introspection must materialize the abstract states whenever requested.
For example, a dynamic analysis can observe any of the function-level storage
such as the local variables and operand stack.

Where to instrument programs? Most monitors instrument code to observe the
flow of execution or program data. With code instrumentation, locations in the
original program code (e.g. bytecode offset, address, line number) become the
natural points of reference. This makes it intuitive to use an instrumentation
API to attach M-code to program locations which will fire when that point is
reached during execution.

Monitoring in Wizard with probes. A dynamic analysis for Wizard involves
writing a Monitor in Virgil (VirgilPldi, ) against an engine API. With this
API, everything about a Wasm program’s execution can be observed _on demand_ ,
including any/every bytecode executed, any/every internal state computed, and
all interaction with the environment. Monitors observe execution by inserting
_probes_ that fire callbacks before specified events or states occur.
Callbacks are dynamic logic but their M-code can be statically compiled into
the engine. Their M-code is efficient machine code that the engine invokes
directly from either the interpreter or JIT-compiled code. Since this M-code
executes as part of the engine and the engine virtualizes Wasm program state,
monitors are inherently non-intrusive.

Probes are maximally general. While many systems (TuningFork, ; JPortal, ;
ShadowVM, ; Roadrunner, ) offer event traces that can be analyzed
asynchronously or offline, probes are more fundamental since they enable the
insertion of arbitrary code at arbitrary locations. For example, probes can
_generate_ event traces or react to program behavior, but event traces do not
offer the ability to influence execution, an inherent capability of
synchronous probes. Thus, we say that probes are _complete_ in the sense that
every type of instrumentation can be built from them.

Figure 1 illustrates the probe hooks offered by Wizard and their
implementation in the interpreter.

###  2.1. Global Probes

The simplest type of probe is a _global probe_ , which fires a callback _for
every instruction executed by the program_. Clearly global probes are
_complete_ since they can execute arbitrary logic at any point in execution.
Despite their inefficiency, global probes are still useful. A global probe is
the easiest way to implement tracing, counting, or the step-instruction
operation of a debugger.

Global probes are easy to implement in an interpreter; its main loop or
dispatch sequence simply contains a check for any global probe(s) and calls
them at each iteration. They also are the slowest M-code because, even with a
JIT, they effectively reduce the VM to an interpreter555E.g. in a compile-only
engine, a compilation mode which inserts a call to fire global probes before
_every_ instruction suffices, but bloats generated code and has marginal
performance benefit over an interpreter..

Unfortunately, the simple implementation technique of an extra check per
interpreted instruction imposes overhead even when not enabled, which tempts
VMs to have different production and debug builds. A key innovation in Wizard
(Section 4) is to implement global probes with _dispatch table switching_ ,
which imposes zero overhead when global probes are not enabled, obviating the
need for a separate debug build. This technique also allows efficient dynamic
insertion and removal of global probes, which we have found to be a useful
mechanism for implementing some analyses, shown in Section 2.6. Regardless of
implementation efficiency, an engine can achieve instrumentation-completeness
by adding only global probe support.

###  2.2. Local Probes

Many dynamic analyses are _sparse_ , only needing to instrument a subset of
code locations. For this reason, Wizard also allows _local probes_ to be
attached to specific locations in the bytecode. At runtime, the engine fires
local probes just _before_ executing the respective instruction. Each Wasm
instruction can be identified uniquely by its module, function, and byte
offset from the start of the function, making the triple (module, funcdecl,
pc) a natural location identifier in the API. Since local probes only fire
when reaching a specific location, they are more convenient for implementing
analyses such as branch profiling, call graph analysis, code coverage,
breakpoints, etc.

Local probes can be significantly more efficient than global probes for
several reasons:

  * •

zero overhead for uninstrumented instructions

  * •

efficient implementation in interpreter and compilers

  * •

compilers can optimize around local probes

Like global probes, local probes are _complete_ ; both can be implemented in
terms of each other at the cost of efficiency666Emulating local probes with
global probes can be done with logic that looks up each local probe in
M-state, and global probes can be emulated by inserting local probes
everywhere, but incurs overhead from data structure lookups in the engine..

###  2.3. The FrameAccessor API

While many analyses need only the sequence of program locations executed, more
advanced dynamic analyses like taint tracking, fuzzing and debugging observe
program states. To allow probe callbacks access to program state, they receive
not only the program location, but also a lazily-allocated object with an API
for reading state, called the _FrameAccessor_.

The FrameAccessor provides callbacks a façade (DesignPatterns, ) with methods
to read frame state, abstracting over the machine-level details of frames,
which often differ between execution tiers and engine versions. They offer a
stable interface to a frame where, due to dynamic optimization and
deoptimization, the engine may change the frame representation during the
execution of a function.

A FrameAccessor object represents a single stack frame and is allocated when a
callback first requests state other than the easily-available WasmFunction and
pc. Importantly, the identity of this object is observable to probes so that
they can implement higher-level analyses across multiple callbacks. At the
implementation level, execution frames maintain the mapping to their accessor
by storing a reference in the frame itself, called the _accessor slot_. The
slot is not used in normal execution, but imposes a one machine word space
overhead; its execution time impact should be negligible.

Stackwalking and callstack depth. The FrameAccessor API allows walking up the
callstack to callers so monitors can implement context-sensitive analyses and
stacktraces. The depth of the call stack alone is also often useful for
tracing or context-sensitive profiling, so FrameAccessor objects include a
depth() method, which a VM can implement slightly more efficiently.

Dangling accessor objects. FrameAccessor objects are allocated in the engine’s
state space (for Wizard, the managed heap), and since probes are free to store
references to them across multiple callbacks, it is possible that the accessor
object outlives the execution frame that it represents777With ownership, as in
Rust, lifetime annotations can statically prevent a FrameAccessor object from
escaping from a _single_ callback, yet some monitors legitimately want to
track frames across multiple callbacks.. While the accessor object itself will
be eventually reclaimed, it is problematic if M-code accesses frames that have
been unwound. We identified a number of implementation mechanisms to protect
the runtime system from buggy monitors.

Possible solutions include:

  1. (1)

Clear accessor on entry. Upon entry to a Wasm function, the accessor slot in
the execution frame is unconditionally set to null.

  2. (2)

Invalidate accessor on return. A dynamic check is performed on all returns
from a function; if the accessor slot points to a valid FrameAccessor object,
the object itself is invalidated (e.g. by setting a field in the object to
false).

  3. (3)

Invalidate accessors on unwind. When unwinding frames for a trap or exception
thrown, which is typically done in the runtime rather than compiled code, the
accessor object itself is invalidated.

  4. (4)

Return guards invalidate accessor. When an accessor slot is set, the return
address for the frame is also redirected to a trampoline that will invalidate
the accessor object before returning to the actual caller.

  5. (5)

FrameAccessor methods check frame validity. Every call to an accessor object
checks that the underlying machine frame points back at the accessor object.

  6. (6)

FrameAccessor methods check self validity. Every call to an accessor object
checks the object’s validity field.

Our solution is to minimize checks in the interpreter and compiled code and
favor checks at the FrameAccessor API boundary and corresponds to a
combination of 1, 4, and 5. This relies on stack frame layout invariants:
function entry clears the accessor slot, the first request for the
FrameAccessor materializes the object, and subsequent accessor calls compare
the accessor slot to a cached stack pointer in the object. To make these
checks bulletproof to monitor bugs, FrameAccessors should be invalidated on
return, e.g. with a runtime check888Or a return guard trampoline, which avoids
any runtime overhead..

###  2.4. Consistency guarantees

Many analyses can be implemented by making use of dynamic probe insertion and
removal. Other analyses, particularly debuggers, could make modifications to
frames that alter program behavior. When do new probes and frame modifications
take effect? Providing consistency guarantees is a key innovation in our
system that makes composing multiple analyses reliable. With these guarantees,
probes from multiple monitors do not interfere, making monitors _composable_
and _deterministic_. Monitors can be used in any combination without explicit
foresight in their implementation.

####  2.4.1. Deterministic firing order

What should happen if a probe $p$ at location $L$ fires and inserts another
probe $q$ at the same location $L$? Should the new probe $q$ also fire before
returning to the program, or not? Similarly, if probes $p$ and $q$ are
inserted on the same event, is their firing order predictable?

We found that a guaranteed probe firing order is subtly important to the
correctness of some monitors (e.g. the function entry/exit utility shown in
Section 2.5). For this reason, we guarantee three _dynamic probe consistency_
properties:

  * •

Insertion order is firing order: Probes inserted on the same event $E$ fire in
the same order as they were inserted.

  * •

Deferred inserts on same event: When a probe fires on event $E$ and inserts
new probes on the same $E$, the new probes do not fire until the next
occurrence of $E$.

  * •

Deferred removal on same event: When a probe fires on event $E$ and removes
probes on the same $E$, the removed probes _do_ fire on this occurrence of $E$
but not subsequent occurrences.

####  2.4.2. Frame modifications

As shown, the FrameAccessor provides a mostly _read-only_ interface to program
state. Since monitors run in the engine’s state space, and not the Wasm
program’s state space, by construction this guarantees that monitors do not
alter the program behavior. However, some monitors, such as a debugger’s fix-
and-continue operation, or fault-injection, intentionally change program
state.

For an interpreter, modifications to program state, such as local variables,
require no special support, since interpreters typically do not make
assumptions across bytecode boundaries. For JIT-compiled code, any assumption
about program state could potentially be violated by M-code frame
modifications. Depending on the specific circumstance, continuing to run JITed
code after state changes might exhibit unpredictable program behavior999 True
even for baseline compilers like Wizard’s compiler, which perform limited
optimizations like register allocation and constant propagation..

It’s important for the engine to provide a consistency model for state changes
made through the FrameAccessor. When monitors explicitly _intend_ to alter the
program’s behavior, it is natural for them to expect state changes to take
effect immediately, _as if_ the program is running in an interpreter. Thus,
our system guarantees:

  * •

Frame modification consistency: State changes made by a probe are immediately
applied, and execution after a probe resumes with those changes.

This effectively requires immediate deoptimization of a frame, also guaranteed
by JVMTI. Otherwise, if execution continues in JIT-compiled code, almost any
invariant the JIT relied on could be invalid, and it may appear that updates
have not occurred yet, violating consistency.

####  2.4.3. Multi-threading

While Wizard is not currently multi-threaded, WebAssembly does have proposals
to add threading capabilities which Wizard must eventually support. That
brings with it the possibility of multi-threaded instrumentation. Locks around
insertion and removal of probes should maintain our consistency guarantees
through serializing dynamic instrumentation requests. Our design inherently
separates monitor state from program state. Thus data races on the monitor
state are the responsibility of the monitors, for example by using lock-free
data structures and/or locks at the appropriate granularity. The FrameAccessor
can also include synchronization to prevent data races on Wasm
state101010Note: frames are by-definition thread local; races can only exist
if the monitor itself is multi-threaded and FrameAccessor objects are shared
racily..

###  2.5. Function Entry/Exit Probes

Probes are a low-level, instruction-based instrumentation mechanism, which is
natural and precise when interfacing with a VM. Yet many analyses focus on
function-level behavior and are interested in calls and returns.
Instrumentation hooks for function entry/exit make such analyses much easier
to write.

At first glance, detecting function entry can be done by probing the first
bytecode of a function, and exit can be detected by probing all returns,
throws, and brs that target the function’s outermost block. However, some
special cases make this tricky. First, a function may begin with a loop; the
entry probe must distinguish between the first entry to a function, a backedge
of the loop, and possible (tail-)recursive calls. Second, local exits are not
enough: frames can be unwound by a callee throwing an exception caught higher
in the callstack.

Should the VM support function entry/exit as special hooks for probes?
Interestingly, we find this is not strictly necessary. This functionality can
be built from the programmability of local probes and offered as a library.
There are several possible implementation strategies: 1) use entry probes that
push the FrameAccessor objects onto an internal stack, with exit probes
popping; 2) sampling the stack depth via the FrameAccessor’s depth() method;
or 3) by instrumenting, and thus ignoring, loop backedges. Thus, function
entry/exit reside above global/local probes in the hierarchy of
instrumentation mechanisms. This is further evidence that the programmability
of probes allows building higher-level instrumentation utilities for more
expressive dynamic analyses.

###  2.6. After-instruction

Some analyses, such as branch profiling or dynamic call graph construction,
are naturally expressed as M-code that should run _after_ an instruction
rather than _before_. For example, profiling which functions are targets of a
call_indirect would be easiest if a probe could fire _after_ the instruction
is executed and a frame for the target function has been pushed onto the
execution stack. However, the API has no such functionality.

Should the VM support an “after-instruction” hook directly? Interestingly, we
find that like function entry/exit, the unlimited programmability of probes
allows us to invoke M-code _seemingly after_ instructions. For example,
suppose we want to execute probe $p$ after a br_table (i.e. Wasm’s switch
instruction). We identified at least three strategies:

  * •

A probe $q_{p}$ executed _before_ the br_table can use the FrameAccessor
object to read the top (i32 value) of the operand stack, determine where the
branch will go, and dynamically insert probe $p$ at that location.

  * •

Insert probes into all targets of the br_table. Since br_table has a fixed set
of targets, we can insert probes once and use M-state to distinguish reaching
each target from the br_table versus another path. This only works in limited
circumstances; other instructions like call_indirect have an unlimited set of
targets.

  * •

Insert a global probe for just one instruction and remove it after. The probe
will fire on the next instruction, wherever that is, then the probe will
remove itself. For a use case like this, it’s important that dynamically
enabling global probes doesn’t ruin performance, e.g. by deoptimizing all JIT-
compiled code. We show in Section 4.1 how dispatch-table switching can make
this use case efficient.

With multiple strategies to emulate its behavior, an after-instruction hook
resides above global/local probes in the instrumentation mechanism hierarchy.

##  3\. The Monitor Zoo

The wide variety and ease with which analyses are implemented111111Most
monitors required a dozen or two lines of instrumentation code; in fact, most
lines are usually spent on making pretty visualizations of the data! showcases
the flexibility of having a fully programmable instrumentation mechanism in a
high-level language. Users activate monitors with flags when invoking Wizard
(e.g. wizeng --monitors=MyMonitor), which instrument modules at various stages
of processing before execution and may generate post-execution reports.
Examples of monitors we have built include a variety of useful tools.

The Trace monitor prints each instruction as it is executed. While many VMs
have tracing flags and built-in modes that may be spread throughout the code,
Wizard already offers the perfect mechanism: the global probe. Instruction-
level tracing in Wizard simply uses one global probe. Other than a short flag
to enable it, there is nothing special about this probe; it uses the standard
FrameAccessor API as it prints instructions and the operand stack.

The Coverage monitor measures code coverage. It inserts a local probe at every
instruction (or basic block), which, when fired, sets a bit in an internal
datastructure and then _removes itself_. By removing itself, the probe will no
longer impose overhead, either in the interpreter or JITed code. Eventually,
all executed paths in the program will be probe-free and JITed code quality
will asymptotically approach zero overhead. This is a good example of a
monitor using dynamic probe removal.

The Loop monitor counts loop iterations. It inserts CountProbes at every loop
header and then prints a nice report. This is a good example of a counter-
heavy analysis.

The Hotness monitor counts every instruction in the program. It inserts
CountProbes at every instruction and then prints a summary of hot execution
paths. Another example of a counter-heavy analysis.

The Branch monitor profiles the direction of all branches. It instruments all
if, br_if and br_table instructions and uses the top-of-stack to predict the
direction of each branch. It is a good example of non-trivial FrameAccessor
usage.

The Memory monitor traces all memory accesses. It instruments all loads and
stores and prints loaded and stored addresses and values. Another good example
of non-trivial FrameAccessor usage.

The Debugger REPL implements a simple read-eval-print loop that allows
interactive debugging at the Wasm bytecode level. It supports breakpoints,
watchpoints, single-step, step-over, and changing the state of value stack
slots. It primarily uses local probes but uses a global probe to implement
single-step functionality. This monitor is a good example of dynamic probe
insertion and removal. It is also the only monitor (so far) that modifies
frames.

The Calls monitor instruments callsites in the program and records statistics
on direct calls and the targets of indirect calls. Its output can be used to
build a dynamic call graph from an execution.

The Call tree profiler measures execution time of function calls and prints
self and nested time using the full calling-context tree. It can also produce
flame graphs. It inserts local probes at all direct and indirect callsites and
all return locations 121212Wizard has preliminary support for the proposed
Wasm exception handling mechanism, but does not yet have monitoring hooks for
unwind events.. It is a good example of a monitor that measures non-
virtualized metrics like wall-clock time.

##  4\. Optimizing probe overhead

Figure 2. Code generated by Wizard’s baseline JIT for different types of
M-code implemented with probes. The machine code sequence for generic probes
is more general than for probes that only need the top-of-stack value, versus
a fully-intrinsified counter probe.

Optimizations in Wizard’s interpreter and JIT compiler reduce overhead for
both global and local probes, see the effectiveness of this technique in
Section 5.3. We define _overhead_ as the execution time spent in neither
application code nor M-code, but in transitions _between_ application and
M-code or additional work in the runtime system and compiler.

###  4.1. Optimizing global probes in the interpreter

Global probes, being the most heavyweight instrumentation mechanism, are
supported only in the interpreter. It is straightforward to add a check to the
interpreter loop that checks for any global probes at each instruction.
However, this naive approach imposes overhead on all instructions executed,
even if global probes are not enabled. One option to avoid overhead when
global probes are disabled is to have two different interpreter loops, one
with the check and one without, and dynamically switch between them. This
comes at some VM code space cost, since it duplicates the entire interpreter
loop and handlers. Another approach described in (FastWasmInterp, ) avoids the
code space cost by maintaining a pointer to the _dispatch table_ in a hardware
register. When global probes are not in use, this register points to a
“normal” dispatch table without instrumentation; inserting a global probe
switches the register to point to an “instrumented” dispatch table where all
(256) entries point to a small stub that calls the probe(s) and then
dispatches to the original handler via the “normal” dispatch table. Both code
duplication and dispatch-table switching are suitable for production, as they
allow the VM to support global probes while imposing no overhead when
disabled.

Dynamically adding and removing global probes shouldn’t ruin performance, as
they might be used to implement “after-instruction” or to trace a subset of
the code, such as an individual function or loop. Our design further extends
(FastWasmInterp, ) by supporting global probes without deoptimizing JITed
code. This can be done by temporarily returning to the interpreter in the
global probe mode. In global probe mode, a different dispatch table is used,
which, in addition to calling probes for every instruction, can use special
handlers for certain bytecodes. For example, the loop bytecode does not check
for dynamic tier-up (which would cause a transfer to JITed code), call
instructions reenter the interpreter (rather than entering the callee’s JITed
code, if any), and return returns only to the interpreter (rather than the
caller’s JIT code). Otherwise, JIT code remains in-place. Removing global
probes leaves this mode and JIT code will naturally be reentered as normal.
See Section 4.6 for how we guarantee consistency after state modifications. To
our knowledge, our design is the first to support switching into a heavyweight
instrumentation mode and back without discarding any JITed code, preserving
performance.

###  4.2. Optimizing local probes in the interpreter

Both Wizard’s interpreter and baseline JIT support local probes. In the
interpreter, local probes impose no overhead on non-probed instructions by
using in-place bytecode modifications. With _bytecode overwriting_ , inserting
a local probe at a location $L$ overwrites its original opcode with an
otherwise-illegal probe opcode. The original unmodified opcode is saved on the
side. When the interpreter reaches a probe opcode, the Wasm program state
(e.g. value stack) is already up-to-date; it saves the interpreter state,
looks up the local probe(s) at the current bytecode location, and simply calls
that M-code callback. This is somewhat reminiscent of machine code
overwriting, a technique sometimes used to implement debugging or machine code
instrumentation (Pin, gdb and DynamoRIO). However, our approach is vastly
simpler and more efficient as it doesn’t require hardware traps or solving a
nasty code layout issue —only a single bytecode is overwritten.

In Wizard, since the callback is compiled machine code, the overhead is a
small number of machine instructions to exit the interpreter context and enter
the callback context. After returning from M-code, $L$’s original opcode is
loaded (e.g. by consulting an unmodified copy of the function’s code) and
executed. Removing a probe is as simple as copying the original bytecode back;
the interpreter will no longer trip over it. In contrast, Pin allows disabling
by removing _all instrumentation_ from a specified region of the original
code, which effectively reinstalls the original code, an all-or-nothing
approach rather than having control at the probe granularity. Overwriting has
two primary advantages over bytecode injection; the original bytecode offsets
are maintained, making it trivial to report locations to M-code, and
insertion/removal of probes is a cheap, constant-time operation. Consistency
is trivial; the bytecode is always up-to-date with the state of inserted
instrumentation.

###  4.3. Local probes in the JIT

In a JIT compiler, local probes can be supported by injecting calls to M-code
into the compiled code at the appropriate places. Since probe logic could
potentially access (and even modify) the state of the program through the
FrameAccessor, a call to unknown M-code must checkpoint the program and VM-
level state. For baseline code from Wizard’s JIT, the overhead is a few
machine instructions more than a normal call between Wasm
functions131313Primarily because the calling convention models an explicit
value stack.. Compilation speed is paramount to a baseline compiler, and
bytecode parsing speed actually matters. Similar to the benefits to
interpreter dispatch, bytecode overwriting avoids any compilation speed
overhead because the probe opcode marks instrumented instructions and
additional checks aren’t needed. Overall, supporting probes adds little
complexity to the JIT compiler; in Wizard’s JIT, it requires less than 100
lines of code.

###  4.4. JIT intrinsification of probes

While probes are a fully-programmable instrumentation mechanism to implement
unlimited analyses, there are a number of common building blocks such as
counters, switches, and samplers that many different analyses use. For logic
as simple as incrementing a counter every time a location is reached, it is
highly inefficient to save the entire program state and call through a generic
runtime function to execute a single increment to a variable in memory. Thus,
we implemented optimizations in Wizard’s JIT to _intrinsify_ counters as well
as probes that access limited frame state.

Figure 2 shows how Wizard’s baseline JIT optimizes different kinds of probes.
At the left, we have uninstrumented code. For the generic probe case, the JIT
inserts a call to a generic runtime routine calls the user’s probe. For the
next more specialized case, the top-of-stack, it inserts a direct call to the
probe’s fire method, passing the top-of-stack value, skipping the runtime call
overhead and the cost of reifying an expensive FrameAccessor object. In
general values from the frame can be directly passed from the JITed code to
M-code. Lastly, for the counter probe, we see that Wizard’s JIT simply inlines
an increment instruction to a _specific_ CountProbe object without looking it
up.

Other systems allow building custom inline M-code. For example, Pin offers
using a type of macro-assembler that builds IR that it compiles into the
instrumented program, which is very low-level, tedious, and error-prone.

###  4.5. Monitor consistency for JITed code

We just saw how a JIT can inline M-code into the compiled code. However,
M-code can change as probes can be inserted and removed during execution,
making compiled code that has been specialized to M-code out-of-date. This
problem can be addressed by standard deoptimization techniques such as on-
stack-replacement back to the interpreter and invalidating relevant machine
code. To our knowledge, no prior bytecode-based system has employed
deoptimization to support dynamic instrumentation of an executing frame, but
offer only hot code replacement.

###  4.6. Strategies for multi-tier consistency

There are several different strategies for guaranteeing monitor consistency in
a multi-tier engine like Wizard. We identified four plausible strategies:

  1. (1)

When instrumentation is enabled, disable the JIT.

  2. (2)

When instrumentation is enabled, disable only _relevant_ JIT optimizations.

  3. (3)

Upon frame modification, recompile the function under different assumptions
about frame state and perform on-stack-replacement from JITed to JITed code.

  4. (4)

Upon frame modification, perform on-stack-replacement from JITed code to the
interpreter.

Strategy 1) is the simplest to implement for engines with interpreters, but
slow. A production Wasm engine could achieve functional correctness and the
key consistency guarantees at little engineering cost, leaving instrumented
performance as a later product improvement. Strategy 2) eliminates interpreter
dispatch cost, but, ironically, is actually a lot of work in practice, since
it introduces modes into the JIT compiler and optimizations must be audited
for correctness. The compiler becomes littered with checks to disable
optimization and ultimately the JIT emits very pessimistic code. Strategy 3)
has other implications for JIT compilation, such as requiring support for
arbitrary OSR locations141414Most JITs that allow tier-up OSR into compiled
code only do so at loop headers., which is also significant engineering work.

In Wizard, we chose strategy 4, which we believe to be not only the simplest,
but most robust. Frame modifications trigger immediate deoptimization of _only
the modified frame_ 151515We observe that the JIT-compiled code for a function
is not _invalid_ , it is only the state of the single frame that now differs
from assumptions in the JIT code. New calls to the involved function can still
legally enter the existing JIT code., rewriting it in place to return to the
interpreter. In the _dynamic_ tiering configuration mode, sending an execution
frame back to the interpreter due to modification doesn’t banish it there
forever; if it remains hot, it can be recompiled under new
assumptions161616Pathological cases can occur where hot frames are repeatedly
modified, constantly transferring between interpreter and JITed code. A
typical fix employed in many VMs is to simply limit the number of times a
function can be optimized and offer user diagnostics.. This means frame
modification support requires the interpreter; Wizard will not allow
modifications in the JIT-only configuration.

Inserting or removing probes in a function also triggers deoptimization of
JITed code for the function and sends existing frames back to the interpreter.
This is different than a frame modification, because the JIT may have
specialized the code to instrumentation at the time of compilation; the code
is actually invalid w.r.t. the instrumentation it should execute. Like with
frame modifications, hot functions will eventually be recompiled. It’s likely
that such highly dynamic instrumentation scenarios would perform better by
using M-state to enable and disable their probes rather than repeatedly
inserting and removing them, which confounds engine tiering heuristics.

Figure 3. Average relative execution time for the hotness monitor (left) and
branch monitor (right), when implemented with local probes and when
implemented with a global probe on the PolyBenchC suite. Points above the bars
denote number of probe fires.

##  5\. Evaluation

In this section, we evaluate performance of monitoring code using three suites
of benchmarks and several different implementation strategies. We compare
instrumenting Wasm code in Wizard, bytecode rewriting, bytecode injection with
Wasabi, and native code instrumentation with DynamoRIO.

###  5.1. Evaluation setup

We evaluate the performance of Wizard by executing Wasm code under both the
interpreter and JIT using different monitors and measure total execution time
of the entire program, including engine startup and program load. We chose the
“hotness” and “branch” monitors (described in Section 3). The hotness monitor
instruments every instruction171717Obviously, it is more efficient to count
basic blocks. We chose to count every instruction in order to _maximize_
instrumentation workload. with a local CountProbe, which is representative of
monitors with many simple probes. The branch monitor probes branch
instructions and tallies each destination by accessing the top of the operand
stack. Compared to the hotness monitor, probes in the branch monitor are more
sparse but more complex.

These monitors were chosen because they strike a balance between being
powerful enough to capture insights about the execution of a program, yet
simple enough to be implemented in other systems. They are also likely to
instrument a nontrivial portion of program bytecode.

Benchmark Suites. We run Wasm programs from three benchmark suites:
PolyBench/C (PolyBench, ) with the medium dataset, Ostrich (Ostrich, ) and
Libsodium (Libsodium, ) and average execution time over 5 runs.

Given instrumented execution time $T_{i}$ and uninstrumented execution time
$T_{u}$, we define _absolute overhead_ as the quantity $T_{i}-T_{u}$ and
_relative execution time_ as the ratio $T_{i}/T_{u}$. We report relative
execution time for Wizard’s interpreter, Wizard’s JIT (with and without
intrinsification), DynamoRIO, Wasabi, and bytecode rewriting in Figures 6 and
7.

###  5.2. Global vs local probes

Global probes can emulate the behavior of local probes, but impose a greater
performance cost by introducing checks at every bytecode instruction. We
compare two implementations of the branch and hotness monitors, one using a
global probe and the other using local probes. Both are executed in Wizard’s
interpreter, since Wizard’s JIT doesn’t support global probes. The results can
be found in Figure 3. For the hotness monitor, since the number of probe fires
is the same for local and global probes, the relative overhead is similar
across all programs. For the branch monitor, local probes on branch
instructions have relative execution times between $1.0$–$2.2\times$, whereas
it is between $7.7$–$16.4\times$ for global probes.

Figure 4. Average relative execution times for the hotness (left) and branch
monitors (right), with and without probe intrinsification on the PolyBenchC
suite. Ratios are relative to uninstrumented JIT execution time. Points above
the bars denote number of probe fires.

###  5.3. JIT optimization of count and operand probes

Section 4 describes how Wizard’s JIT intrinsifies some types of probes to
reduce overhead. We evaluate JIT intrinsification in Figure 4 and report the
relative execution time of instrumented over uninstrumented execution.

For the hotness monitor, which counts the execution frequency of every
instruction, we observed relative execution times between $7$–$134\times$.
This is due to the high cost of switching between JIT code and the engine at
every instruction. With intrinsification, the same monitor has relative
execution times between $2.2$–$7.7\times$.

We performed a similar experiment to evaluate the effectiveness of JIT
intrinsification of top-of-stack operand probes by measuring execution times
with the branch monitor. We see that intrinsification improves relative
execution times from $1.0$–$16.6\times$ with the base JIT to
$1.0$–$2.8\times$. The improvement is smaller for branch probes than for
CountProbes, because a call into the probe’s M-code remains, whereas
CountProbes are fully inlined (see Figure 2).

Figure 5. Execution time decomposition of hotness (left) and branch monitors
(right) into M-code and probe dispatch overhead with and without probe
intrinsification on the PolyBenchC suite. The cross-hatched regions represent
overhead saved by intrinsification.

We further decompose the runtime of the benchmarks into the time spent in the
program’s JIT-compiled code ($T_{\text{JIT}}$), time in M-code ($T_{M}$), and
time in the probe dispatch logic ($T_{\text{PD}}$). This decomposition is done
by recording:

  1. (1)

The uninstrumented execution time of code in the JIT, which approximates
$T_{\text{JIT}}$;

  2. (2)

The instrumented execution time with empty probes (probes with empty fire
functions), which approximates $T_{\text{PD}}+T_{\text{JIT}}$;

  3. (3)

The instrumented execution time with actual probes, which gives
$T_{\text{PD}}+T_{M}+T_{\text{JIT}}$.

The results of this analysis for the branch and hotness monitors are in Figure
5. Execution time without JIT intrinsification is shown as the entire bar for
each program. The cross-hatched portions of each bar represent the execution
time saved by intrinsification. For the non-intrinsified branch monitor, the
overhead $T_{\text{PD}}+T_{M}$ is dominated by M-code. In the intrinsified
case, the overhead is dominated by probe dispatch, and the M-code overhead is
reduced substantially: calling the top-of-stack operand probe’s M-code still
requires significant spilling on the stack and a call, contributing to runtime
overhead. The M-code overhead no longer includes time for construction of the
FrameAccessor as it is not necessary.

As for the non-intrinsified hotness monitor, the overhead is dominated by the
probe dispatch overhead as probes are simpler but fired more frequently. In
the intrinsified case, there is almost no M-code overhead as counter probes do
not have custom fire functions; the counter increment is entirely inlined. The
remaining probe dispatch overhead comes from the monitor setup and reporting.

###  5.4. Interpreter vs. JIT

We find that the relative overhead of monitors running in Wizard’s interpreter
is much lower than the JIT, for two reasons: the interpreter runs much slower,
and less additional work is done in checkpointing state. In contrast, calls to
local probes in the JIT require checkpointing to support the FrameAccessor
API. Data in Figures 6 and 7 show that, for the branch monitor, the relative
execution time in the interpreter is $1.0$–$2.2\times$ as compared to
$1.0$–$16.6\times$ in Wizard’s JIT. In the higher-workload hotness monitor,
this difference is exacerbated: the relative execution time in the interpreter
is $7.0$–$13.5\times$ as compared to $7.0$–$134\times$ in the JIT. Although
relative execution times differ substantially, absolute overhead between the
two modes is comparable: for the branch monitor, the mean overhead in the
interpreter is $2.6$s and $2.3$s in the JIT.

Figure 6. Relative execution times of the hotness monitor (bottom) and branch
monitor (top) in Wizard, Wasabi, and DynamoRIO across all programs on all
suites, sorted by absolute execution time. Ratios are relative to
uninstrumented execution time.

Figure 7. Mean relative execution times of the hotness monitor (left) and
branch monitor (right) in Wizard, Wasabi, and DynamoRIO across the three
suites. Ratios are relative to uninstrumented execution time.

###  5.5. Comparison with bytecode rewriting

Bytecode rewriting is an example of static instrumentation described in
Section 1.1.1. Using Walrus (Walrus, ), a Wasm transformation library written
in Rust, we implemented the hotness and branch monitors by rewriting bytecode
(wasm-bytecode-instrumenter, ). For the hotness monitor, we inject counting
instructions before each instruction, and for the branch monitor, before each
branching instruction. Counters are stored in memory, necessitating loads and
stores. We evaluated the performance of the transformed Wasm bytecode when run
in Wizard’s JIT, and compared it to their respective monitors in Wizard. From
Figure 7, we observe that the intrinsified JIT execution time is lower than
that of bytecode rewriting for both monitors.

###  5.6. Comparison with Wasabi

Wasabi is a dynamic instrumentation tool that runs analyses on Wasm bytecode
using a JavaScript engine. Since Wasabi instrumentation must be written in
JavaScript, it requires a Wasm engine that also runs JavaScript, such as V8
(V8, ). For this comparison, we use V8 in its default mode (two compiler
tiers)181818We also conducted experiments limiting V8 to its baseline
compiler, for a closer comparison to Wizard’s JIT. Results indicate that the
Wasm compiler makes little difference; the overhead is dominated by JavaScript
execution and transitions between JavaScript. For more JIT comparisons see
(WizardJit, ).. Figure 6 includes data for Wasabi on v8. Wasabi
instrumentation is vastly slower than Wizard instrumentation due to the
overhead of calling JavaScript functions. On average, a hotness monitor in
Wasabi increases execution time $36.8$–$6350.2\times$, compared to
$7$–$134\times$ for Wizard’s JIT (or $2.2$–$7.7\times$ with intrinsification).
The branch monitor also has a drastic performance impact of
$29.9$–$4721.5\times$ in Wasabi, compared to $1.0$–$16.6\times$ for Wizard’s
JIT (or $1.0$–$2.8\times$ with intrinsification).

###  5.7. Comparison with DynamoRIO

We also compare with machine code instrumentation. We cannot make a direct
comparison, so instead, we compile the same benchmark programs to x86-64
assembly and instrument them with DynamoRIO, with analogous machine-code
hotness and branch monitors.

The results are shown in Figures 6 and 7. Executing the native programs
instrumented with a DynamoRIO hotness monitor is about $3.9$–$192\times$
slower than without instrumentation. The hotness monitor has a substantial
relative overhead because, among other things, DynamoRIO inserts instructions
to spill and restore EFLAGS for each counter increment. On the other hand, the
DynamoRIO branch monitor slows execution time from $4.4$–$153\times$, again
compared to $1.0$–$16.6\times$ for Wizard’s JIT (or $1.0$–$2.8\times$ with
intrinsification). This is likely because our DynamoRIO monitor is implemented
with a function call at every basic block, which DynamoRIO can sometimes
inline, since it works at the machine code level. Its default inlining
heuristics seem to give rise to unpredictable overheads.

###  5.8. Evaluation summary

We evaluated Wizard’s instrumentation overheads by measuring the relative
execution times of a branch and a hotness monitor across multiple standardized
benchmarks and instrumentation approaches. For monitors with sparse probes,
like the branch monitor, local probes improve on the performance of global
probes (relative execution time of $1.0$–$2.2\times$ versus
$7.7$–$16.4\times$). Running monitors in Wizard’s JIT further improves this
performance to a relative execution time of $1.0$–$16.6\times$ without
intrinsification and $1.0$–$2.8\times$ with intrinsification. This greatly
outperforms DynamoRIO and Wasabi, with relative execution times of
$4.4$–$153\times$ and $29.9$–$4721.5\times$ respectively. Surprisingly, JIT
intrinsification can produce instrumentation overhead even lower than
intrusive bytecode rewriting, shown in Figure 7. Our results show Wizard’s
instrumentation architecture is both flexible and efficient.

##  6\. Related work

Techniques for studying program behavior have been the subject of a vast
amount of research. They differ in _when_ to instrument (statically or
dynamically), at _which level_ (source, IR, bytecode, or machine code), and
_what_ mechanism is used to do so. A key issue is that the analysis and the
mechanism work together to analyze a program’s behavior _intrusively_ or _non-
intrusively_ , yet some mechanisms make it easier to implement non-intrusive
analyses.

###  6.1. Code injection

A common approach is to inject M-code directly into programs
(BinRewriteSurvey, ), either statically or dynamically. Injecting code into a
program can be done _inline_ (directly inserted into code, often requiring
binary reorganization), with _trampolines_ (jumps to out-of-line
instrumentation code), or both.

Static. Early tools for Java static bytecode instrumentation include Soot
(Soot, ) and Bloat (NystromThesis, ). Later, with the rise of Aspect-Oriented
Programming (AOP), tools emerged to target _joinpoints_ , such as DiSL (DISL,
), AspectJ (AspectJ, ) and BISM (BISM, ). Oron (Oron, ) reduced the
performance overhead of JavaScript source-level instrumentation by targetting
AssemblyScript and compiling the instrumented program to Wasm for execution.
For Wasm, tools are now emerging such as the aspect-oriented (AspectWasm, ),
and Wasabi (Wasabi, ), which injects trampolines into Wasm bytecode that call
instrumentation code provided as JavaScript.

Dynamic. FERRARI (FERRARI, ) statically instruments core JDK classes while
dynamically instrumenting all others using java.lang.instrument. SaBRe (SaBRe,
) injects instrumentation at load-time, thus paying the rewriting cost once at
startup rather than continuously during execution. DTrace (DTrace, ; DTrace2,
), inspired by Paradyn (Paradyn, ) and other tools, enables tracing at both
the user and kernel layer of the OS by operating inside the kernel itself and
uses dynamically-injected trampolines. Dyninst (Dyninst, ) interfaces with a
program’s CFG and maps modifications to concrete binary rewrites. A user can
tie M-code to instructions or CFG abstractions (e.g. function entry/exit). It
can do this statically or at any point during execution and changes are
immediate. Recent research in this direction (ToggleProbe, ) (Odin, )
(TowardMinimalMonitoring, ) focuses on reducing instrumentation overhead with
a variety of low-level optimizations.

###  6.2. Recompilation.

Compiled programs can be _recompiled_ to inject code using several techniques.

Static. Early examples of static lifting for instrumentation include ATOM
(AtomTools, ), followed by EEL (EEL, ) with finer-grained instrumentation.
Etch (Etch, ), through observing an initial program execution, discovered
dynamic program properties to inform static instrumentation. Other examples
include Vulcan (Vulcan, ), which injects code into lifted Win32 binaries.

Dynamic. Both DynamoRIO (DynamoRIO, ) and Pin (Pin, ) use dynamic
recompilation of native binaries to implement instrumentation. They differ
somewhat on subtle implementation details, how M-code is injected, and
performance characteristics, but fundamentally work by recompiling machine
code for a given ISA to the same ISA. Their JIT compilers are purpose-built
for instrumentation and are basic-block and trace-cache based. They run code
in the original process and reorganize binaries, and can be intrustive,
particularly if M-code is supplied as low-level native code. We are not aware
of strong consistency guarantees (Section 2.4) in the face of dynamically
adding and removing instrumentation.

RoadRunner (Roadrunner, ) is a dynamic analysis system for Java based on event
streams, primarily focused on race detection. It uses a custom classloader to
inject calls to instrumentation. Analyses are formulated in terms of pipes and
filters over event streams, allowing composability. It offers some specific
inlining optimizations that avoid the overhead of events in some
circumstances. Since the analysis code runs in the same state space and on the
same threads, it can both perturb performance and alter concurrency
characteristics of highly-multithreaded programs.

ShadowVM (ShadowVM, ) builds on JVMTI to provide non-intrusive instrumentation
with low perturbation by running the monitor on a separate JVM and
asynchronously processing events as they occur. It is primarily suited for
program observation, as it does not directly support state modifications. On
load, an instrumentation process dynamically inserts hooks through bytecode
rewriting that trap to native code to asynchronously communicate event
notifications to the monitor. According to published material, ShadowVM does
not support dynamically inserting and removing hooks during program execution.

###  6.3. Emulation

QEMU (QEMU, ) is a widely-used CPU emulator that virtualizes a user-space
process while supporting non-intrusive instrumentation. Valgrind (Valgrind, ),
primarily used as a memory debugger, is similar. As emulators, both can run a
guest ISA on a different host ISA, and both use JIT compilers to make
emulation fast. Thus, their JIT compilers are not necessarily “purpose-built”
for instrumentation, but for cross-compilation. Avrora (Avrora, ), a
microcontroller emulator and sensor network simulator, provides an API to
attach M-code to clock events, instructions, and memory locations.

###  6.4. Direct engine support

Runtime systems can be designed with specific support for instrumentation. In
.NET (DotNetProfiling, ), users build profiler DLLs that are loaded by the CLR
into the same process as a target application. The CLR then notifies the
profiler of events occurring in the application through a callback interface.
The JVM Tool Interface (JvmTI, ) allows Java bytecode instrumentation and also
_agents_ to be written against a lower-level internal engine API that supports
attaching callbacks to events. Examples of events are method entry and exit,
but nothing as fine-grained as reaching individual bytecodes. To assess the
performance overhead of handling MethodEntry events, we wrote a Calls monitor
using JVMTI in C. When run on the famously indirect-call-heavy Richards
benchmark it imposes $50$–$100\times$ overhead. In contrast, for the same
program compiled to Wasm and running with Wizard’s Calls monitor, the overhead
was measured to be $2.5$–$3\times$.

##  7\. Conclusion and Future Work

In this paper, we showed the first non-intrusive dynamic instrumentation
framework for Wasm in a multi-tier Wasm research engine that imposes zero
overhead when not in use. Modifications to the interpreter and compiler tiers
of Wizard are minimal; just a few hundred lines of code. Novel optimizations
reduce instrumentation overhead and perform well for sparse analysis and
acceptably well for heavy analysis. Our robust consistency guarantees make our
system the first to support composing multiple analyses seamlessly.

While probes offer a complete instrumentation mechanism for code, many
analyses instrument other events, such as memory accesses, traps, etc. As we
saw with function entry/exit and after-instruction hooks, libraries can
implement higher-level hooks _using_ probes; but if directly supported by the
engine, these hooks can be implemented more efficiently, e.g. hardware
watchpoints for memory accesses.

In this work, we showed monitors written against Wizard’s engine APIs in a
high-level language. Generic probes use runtime calls to compiled M-code.
Massive speedups are possible from intrinsifying _certain_ probes by inlining
all or part of their M-code. What if M-code was instead supplied in an _IR_
the JIT could _inline_? We plan to explore _Wasm bytecode_ as just that IR.

###### Acknowledgements.

This work is supported in part by NSF Grant Award #2148301, as well as funding
and support from the WebAssembly Research Center. Thanks to Anthony Rowe and
Arjun Ramesh for important discussions and comments on drafts of this work.
Thanks to Saúl Cabrera, Erin Ren, and Jeff Charles at Shopify, Ulan Degenbaev
and Yan Chen at DFinity, and Chris Woods at Siemens.

## References

  * [1] The edge of the multi-cloud.  https://www.fastly.com/cassets/6pk8mg3yh2ee/79dsHLTEfYIMgUwVVllaa4/5e5330572b8f317f72e16696256d8138/WhitePaper-Multi-Cloud.pdf, 2020\.  (Accessed 2021-07-06).
  * [2] Wasm3: The fastest WebAssembly interpreter, and the most universal runtime.  https://github.com/wasm3/wasm3, 2020.  (Accessed 2021-08-11).
  * [3] Java Virtual Machine Tools Interface.  https://docs.oracle.com/javase/8/docs/technotes/guides/jvmti/, 2021\.  (Accessed 2021-07-29).
  * [4] JavaScriptCore, the built-in JavaScript engine for WebKit.  https://trac.webkit.org/wiki/JavaScriptCore, 2021.  (Accessed 2021-07-29).
  * [5] V8 development site.  https://v8.dev, 2021.  (Accessed 2021-07-29).
  * [6] WebAssembly specifications.  https://webassembly.github.io/spec/, 2021.  (Accessed 2021-07-29).
  * [7] Intel 64® and IA-32 Architectures Software Developer’s Manual Volume 3 (3A, 3B, 3C & 3D): System Programming Guide, chapter 33: Intel Processor Trace.  2023\.
  * [8] Walrus: A WebAssembly transformation library.  https://github.com/rustwasm/walrus, 2023.
  * [9] Wasm bytecode instrumenter.  https://github.com/yashanand1910/wasm-bytecode-instrumenter, 2023\.
  * [10] Paul-Antoine Arras, Anastasios Andronidis, Luís Pina, Karolis Mituzas, Qianyi Shu, Daniel Grumberg, and Cristian Cadar.  SaBRe: load-time selective binary rewriting.  International Journal on Software Tools for Technology Transfer, 24(2):205–223, Apr 2022.
  * [11] Linux Wiki Authors.  Linux perf main page.  https://perf.wiki.kernel.org/index.php/Main_Page, 2012.  (Accessed 2023-8-4).
  * [12] .NET Wiki Authors.  The .NET Profiling API.  https://learn.microsoft.com/en-us/dotnet/framework/unmanaged-api/profiling/profiling-overview, 2021\.  (Accessed 2023-8-4).
  * [13] David F. Bacon, Perry Cheng, and David Grove.  TuningFork: A platform for visualization and analysis of complex real-time systems.  In Companion to the 22nd ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications Companion, OOPSLA ’07, page 854–855, New York, NY, USA, 2007. Association for Computing Machinery.
  * [14] Fabrice Bellard.  QEMU: A generic and open source machine emulator and virtualizer.  http://qemu.org, 2020.  (Accessed 2023-8-07).
  * [15] Andrew R. Bernat and Barton P. Miller.  Anywhere, any-time binary instrumentation.  In Proceedings of the 10th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools, PASTE ’11, page 9–16, New York, NY, USA, 2011. Association for Computing Machinery.
  * [16] Walter Binder, Jarle Hulaas, and Philippe Moret.  Advanced Java bytecode instrumentation.  In Proceedings of the 5th International Symposium on Principles and Practice of Programming in Java, PPPJ ’07, page 135–144, New York, NY, USA, 2007. Association for Computing Machinery.
  * [17] Jay Bosamiya, Wen Shih Lim, and Bryan Parno.  Provably-safe multilingual software sandboxing using WebAssembly.  In Proceedings of the USENIX Security Symposium, August 2022.
  * [18] D Bruening, T Garnett, and S Amarasinghe.  An infrastructure for adaptive dynamic optimization.  In International Symposium on Code Generation and Optimization, 2003\. CGO 2003. IEEE Comput. Soc, 2003.
  * [19] Rodrigo Bruno, Duarte Patricio, José Simão, Luis Veiga, and Paulo Ferreira.  Runtime object lifetime profiler for latency sensitive big data applications.  In Proceedings of the Fourteenth EuroSys Conference 2019, EuroSys ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [20] Buddhika Chamith, Bo Joel Svensson, Luke Dalessandro, and Ryan R. Newton.  Living on the edge: Rapid-toggling probes with cross-modification on x86.  In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’16, page 16–26, New York, NY, USA, 2016. Association for Computing Machinery.
  * [21] Greg Cooper.  DTrace: Dynamic tracing in Oracle Solaris, Mac OS X, and Free BSD by Brendan Gregg and Jim Mauro.  SIGSOFT Softw. Eng. Notes, 37(1):34, jan 2012.
  * [22] Frank Denis.  Libsodium, 2021.
  * [23] Bruno Dufour, Karel Driesen, Laurie Hendren, and Clark Verbrugge.  Dynamic metrics for Java.  SIGPLAN Not., 38(11):149–168, oct 2003.
  * [24] Cormac Flanagan and Stephen N. Freund.  The RoadRunner dynamic analysis framework for concurrent programs.  In Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE ’10, page 1–8, New York, NY, USA, 2010. Association for Computing Machinery.
  * [25] E. Gamma, R. Helm, R. Johnson, and J. Vlissides.  Design Patterns: Elements of Reusable Object-Oriented Software.  Addison-Wesley Professional Computing Series. Pearson Education, 1994\.
  * [26] Manuel Geffken and Peter Thiemann.  Side effect monitoring for Java using bytecode rewriting.  In Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, PPPJ ’14, page 87–98, New York, NY, USA, 2014\. Association for Computing Machinery.
  * [27] Brendan Gregg and Jim Mauro.  DTrace: Dynamic Tracing in Oracle Solaris, Mac OS X and FreeBSD.  Prentice Hall Press, USA, 1st edition, 2011.
  * [28] Andreas Haas, Andreas Rossberg, Derek L. Schuff, Ben L. Titzer, Michael Holman, Dan Gohman, Luke Wagner, Alon Zakai, and JF Bastien.  Bringing the web up to speed with WebAssembly.  In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, page 185–200, New York, NY, USA, 2017. Association for Computing Machinery.
  * [29] David Herrera, Hanfeng Chen, Erick Lavoie, and Laurie Hendren.  Numerical computing on the web: Benchmarking for the future.  In Proceedings of the 14th ACM SIGPLAN International Symposium on Dynamic Languages, DLS 2018, page 88–100, New York, NY, USA, 2018. Association for Computing Machinery.
  * [30] Saba Jamilan, Tanvir Ahmed Khan, Grant Ayers, Baris Kasikci, and Heiner Litz.  APT-GET: Profile-guided timely software prefetching.  In Proceedings of the Seventeenth European Conference on Computer Systems, EuroSys ’22, page 747–764, New York, NY, USA, 2022. Association for Computing Machinery.
  * [31] Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G. Griswold.  An overview of AspectJ.  In Proceedings of the 15th European Conference on Object-Oriented Programming, ECOOP ’01, page 327–353, Berlin, Heidelberg, 2001\. Springer-Verlag.
  * [32] James R. Larus and Eric Schnarr.  EEL: Machine-independent executable editing.  In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, PLDI ’95, page 291–300, New York, NY, USA, 1995. Association for Computing Machinery.
  * [33] Daniel Lehmann and Michael Pradel.  Wasabi: A framework for dynamically analyzing WebAssembly.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’19, page 1045–1058, New York, NY, USA, 2019. Association for Computing Machinery.
  * [34] Borui Li, Hongchang Fan, Yi Gao, and Wei Dong.  ThingSpire OS: A WebAssembly-based IoT operating system for cloud-edge integration.  In Proceedings of the 19th Annual International Conference on Mobile Systems, Applications, and Services, MobiSys ’21, page 487–488, New York, NY, USA, 2021. Association for Computing Machinery.
  * [35] Renju Liu, Luis Garcia, and Mani Srivastava.  Aerogel: Lightweight access control framework for WebAssembly-based bare-metal IoT devices.  In 2021 IEEE/ACM Symposium on Edge Computing (SEC), pages 94–105, 2021.
  * [36] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood.  Pin: Building customized program analysis tools with dynamic instrumentation.  SIGPLAN Not., 40(6):190–200, June 2005.
  * [37] Lukáš Marek, Stephen Kell, Yudi Zheng, Lubomír Bulej, Walter Binder, Petr Tůma, Danilo Ansaloni, Aibek Sarimbekov, and Andreas Sewe.  ShadowVM: Robust and comprehensive dynamic program analysis for the Java platform.  In Proceedings of the 12th International Conference on Generative Programming: Concepts and Experiences, GPCE ’13, page 105–114, New York, NY, USA, 2013. Association for Computing Machinery.
  * [38] Lukáš Marek, Alex Villazón, Yudi Zheng, Danilo Ansaloni, Walter Binder, and Zhengwei Qi.  DiSL: A domain-specific language for bytecode instrumentation.  In Proceedings of the 11th Annual International Conference on Aspect-Oriented Software Development, AOSD ’12, page 239–250, New York, NY, USA, 2012. Association for Computing Machinery.
  * [39] Barton P. Miller, Mark D. Callaghan, Jonathan M. Cargille, Jeffrey K. Hollingsworth, R. Bruce Irvin, Karen L. Karavanic, Krishna Kunchithapadam, and Tia Newhall.  The Paradyn parallel performance measurement tool.  Computer, 28(11):37–46, nov 1995.
  * [40] Aäron Munsters, Angel Luis Scull Pupo, Jim Bauwens, and Elisa Gonzalez Boix.  Oron: Towards a dynamic analysis instrumentation platform for AssemblyScript.  In Companion Proceedings of the 5th International Conference on the Art, Science, and Engineering of Programming, Programming ’21, page 6–13, New York, NY, USA, 2021. Association for Computing Machinery.
  * [41] Otoya Nakakaze, István Koren, Florian Brillowski, and Ralf Klamma.  Retrofitting industrial machines with WebAssembly on the edge.  In Richard Chbeir, Helen Huang, Fabrizio Silvestri, Yannis Manolopoulos, and Yanchun Zhang, editors, Web Information Systems Engineering – WISE 2022, pages 241–256, Cham, 2022. Springer International Publishing.
  * [42] Nicholas Nethercote and Julian Seward.  Valgrind: A framework for heavyweight dynamic binary instrumentation.  SIGPLAN Not., 42(6):89–100, jun 2007.
  * [43] Manuel Nieke, Lennart Almstedt, and Rüdiger Kapitza.  Edgedancer: Secure mobile WebAssembly services on the edge.  In Proceedings of the 4th International Workshop on Edge Systems, Analytics and Networking, EdgeSys ’21, page 13–18, New York, NY, USA, 2021. Association for Computing Machinery.
  * [44] Nathaniel John Nystrom.  Bytecode-level analysis and optimization of Java classes.  Master’s thesis, Purdue University, August 1998.
  * [45] Louis-Noël Pouchet.  PolyBench, May 2016.
  * [46] David Georg Reichelt, Stefan Kühne, and Wilhelm Hasselbring.  Towards solving the challenge of minimal overhead monitoring.  In Companion of the 2023 ACM/SPEC International Conference on Performance Engineering, ICPE ’23 Companion, page 381–388, New York, NY, USA, 2023. Association for Computing Machinery.
  * [47] João Rodrigues and Jorge Barreiros.  Aspect-oriented WebAssembly transformation.  In 2022 17th Iberian Conference on Information Systems and Technologies (CISTI), pages 1–6, 2022.
  * [48] Ted Romer, Geoff Voelker, Dennis Lee, Alec Wolman, Wayne Wong, Hank Levy, Brian Bershad, and Brad Chen.  Instrumentation and optimization of Win32/Intel executables using Etch.  In Proceedings of the USENIX Windows NT Workshop on The USENIX Windows NT Workshop 1997, NT’97, page 1, USA, 1997. USENIX Association.
  * [49] Koushik Sen, Swaroop Kalasapur, Tasneem Brutch, and Simon Gibbs.  Jalangi: A selective record-replay and dynamic analysis framework for JavaScript.  In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, page 488–498, New York, NY, USA, 2013\. Association for Computing Machinery.
  * [50] Chukri Soueidi, Ali Kassem, and Yliès Falcone.  BISM: bytecode-level instrumentation for software monitoring.  In Runtime Verification: 20th International Conference, RV 2020, Los Angeles, CA, USA, October 6–9, 2020, Proceedings 20, pages 323–335. Springer, 2020.
  * [51] A. Srivastava, A. Edwards, and H. Vo.  Vulcan: Binary transformation in a distributed environment.  Technical report, Microsoft Research, 2001.
  * [52] Amitabh Srivastava and Alan Eustace.  ATOM: A system for building customized program analysis tools.  New York, NY, USA, 1994. Association for Computing Machinery.
  * [53] Ben L. Titzer.  Harmonizing classes, functions, tuples, and type parameters in Virgil III.  In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, page 85–94, New York, NY, USA, 2013. Association for Computing Machinery.
  * [54] Ben L. Titzer.  Wizard, An advanced Webassembly Engine for Research.  https://github.com/titzer/wizard-engine, 2021.  (Accessed 2021-07-29).
  * [55] Ben L. Titzer.  A fast in-place interpreter for WebAssembly.  Proc. ACM Program. Lang., 6(OOPSLA2), October 2022.
  * [56] Ben L. Titzer.  Whose baseline compiler is it anyway?  CGO ’24, New York, NY, USA, 2024. Association for Computing Machinery.
  * [57] Ben L. Titzer, Daniel K. Lee, and Jens Palsberg.  Avrora: Scalable sensor network simulation with precise timing.  In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, IPSN ’05, page 67–es. IEEE Press, 2005.
  * [58] Ben L. Titzer and Jens Palsberg.  Nonintrusive precision instrumentation of microcontroller software.  In Proceedings of the 2005 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES ’05, page 59–68, New York, NY, USA, 2005. Association for Computing Machinery.
  * [59] Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan.  Soot: A Java bytecode optimization framework.  In CASCON First Decade High Impact Papers, CASCON ’10, page 214–224, USA, 2010. IBM Corp.
  * [60] Kenton Varda.  WebAssembly on Cloudflare Workers.  https://blog.cloudflare.com/webassembly-on-cloudflare-workers/.  (Accessed 2021-07-06).
  * [61] Mingzhe Wang, Jie Liang, Chijin Zhou, Zhiyong Wu, Xinyi Xu, and Yu Jiang.  Odin: On-demand instrumentation with on-the-fly recompilation.  In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022, page 1010–1024, New York, NY, USA, 2022. Association for Computing Machinery.
  * [62] Conrad Watt.  Mechanising and verifying the WebAssembly specification.  In Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs, CPP 2018, page 53–65, New York, NY, USA, 2018\. Association for Computing Machinery.
  * [63] Matthias Wenzl, Georg Merzdovnik, Johanna Ullrich, and Edgar Weippl.  From hack to elaborate technique – a survey on binary rewriting.  ACM Comput. Surv., 52(3), jun 2019.
  * [64] Zhiqiang Zuo, Kai Ji, Yifei Wang, Wei Tao, Linzhang Wang, Xuandong Li, and Guoqing Harry Xu.  JPortal: Precise and efficient control-flow tracing for JVM programs with Intel Processor Trace.  In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, page 1080–1094, New York, NY, USA, 2021. Association for Computing Machinery.

##  Appendix A Artifact Appendix

###  A.1. Abstract

This artifact description contains information for how to reproduce all
results in this paper. We describe system requirements, how to set up an
environment and run our scripts that produce data and exact figures in the
paper, as well as how to modify the artifact to run your own custom
experiments. Our package contains all scripts, benchmarks, monitors, and
engines used. We also provided all of our results in the package so others can
do direct data comparison.

###  A.2. Artifact Meta-Information

  * •

Benchmarks: The following benchmarking suites are used in our experiments:

    * –

PolyBench/C [45] with the medium dataset, version 4.2.

    * –

Ostrich [29], version 1.0.0.

    * –

Libsodium [22], there are three different variations of the Libsodium
benchmark as follows:

      * *

libsodium, the base libsodium suite, version 0.7.13.

      * *

libsodium-2021, a variation pulled from the 2021-Q1 directory at
https://github.com/jedisct1/webassembly-benchmarks.

      * *

libsodium-no-bulk-mem, a variation of base libsodium above without bulk memory
operations.

All of these benchmark suites have been included in the suites directory of
the artifact.

  * •

Compilation: Since we provide the benchmarks compiled to Wasm, a Wasm compiler
is unnecessary. However, a Rust compiler for the wasm-bytecode-instrumenter
and Wasabi tools is necessary. See the next section for the required version
of rustc.

  * •

Transformations: For the bytecode rewriting experiment, we use Walrus (version
0.20.1), a Rust library for Wasm transformations, in our wasm-bytecode-
rewriter to inject our Wasm instrumentation. This crate’s repo is publicly
available at: https://github.com/rustwasm/walrus. Wasabi also does Wasm
transformations to inject calls, follow instructions in the README.md file at
the root directory of the artifact for how to set up this tool.

  * •

Binaries: We used Wizard [54] version 23a.1617 for our experimentation. Since
this version did not have support for enabling/disabling certain features via
command line flags, we directly manipulated flags in the source code and
compiled each required Wizard configuration for our experiments and made them
available in the bin folder. The following describes each binary’s
configuration:

    * –

base/wizeng.x86-64-linux. This is the base compilation of Wizard with no flags
modified.

    * –

local-global/wizeng.x86-64-linux. In order to use a monitor in Wizard, its
code must be present in the binary. We extended the base Wizard to contain
both the local and global implementations of the hotness and branch monitors
in this binary.

    * –

fast-count/wizeng.x86-64-linux. This binary was compiled with the
intrinsifyCountProbe and intrinsifyOperandProbe flags enabled in the
src/engine/Tuning.v3 file.

    * –

empty-probes/wizeng.x86-64-linux. To reiterate, in order to use a monitor in
Wizard, its code must be present in the binary. We extended the base Wizard to
contain variations of the hotness and branch monitors with no M-code in their
inserted probes.

    * –

empty-probes-fast-count/wizeng.x86-64-linux. This binary is a combination of
the above fast-count and empty-probes configurations.

We have also included the binary btime in the bin folder that calculates
various types of timing characteristics of a program’s execution.

  * •

Run-time environment: This project must be run on an x86_64 Linux machine. It
is not necessary to have sudo access as software can be installed/symlinked in
a user’s home directory. However, having sudo access would substantially
simplify the installation process.

  * •

Metrics: We report _relative execution time_ and _absolute overhead_ for
Wizard’s interpreter, Wizard’s JIT (with and without intrinsification),
DynamoRIO, Wasabi, and bytecode rewriting. Given instrumented execution time
$T_{i}$ and uninstrumented execution time $T_{u}$, we define _absolute
overhead_ as the quantity $T_{i}-T_{u}$ and _relative execution time_ as the
ratio $T_{i}/T_{u}$.

  * •

Output: There are two different outputs for our scripts. The experiment*.bash
scripts output CSV files. The plot*.py scripts output graphs as PDF and SVG
files. We have provided our own results inside the csv and figures folders for
comparison.

  * •

Experiments: Follow the instructions in the README.md file at the base
directory of the artifact for how to run experiments.

  * •

How much disk space required (approximately)?: 10 GB

  * •

How much time is needed to prepare workflow (approximately)?: We expect
experiment preparation to take around 30 minutes (if all builds/installs work
well).

  * •

How much time is needed to complete experiments (approximately)?: To run 5
iterations per experiment, you should expect the runtime to take about 7 days
when running on an Ubuntu 20.04.5 machine with 19 GiB of RAM and an Intel®
Core™ i7-4790 processor running at 3.60 GHz. This is primarily due to Wasabi
being significantly slower with instrumentation.

  * •

Publicly available?: Yes, this artifact is available at the following URL:
https://zenodo.org/doi/10.5281/zenodo.10795556

  * •

Code license: Licensed under the Apache License, Version 2.0
(https://www.apache.org/licenses/LICENSE-2.0).

###  A.3. Description

####  A.3.1. How to access

This artifact can be accessed at:
https://zenodo.org/doi/10.5281/zenodo.10795556

####  A.3.2. Software dependencies

This artifact has the following software dependencies:

  * •

V8 [5], commit hash f200321. V8 can be downloaded from
https://github.com/v8/v8. To run experiments scripts, this binary must be
available on the PATH to be called with the d8 command.

  * •

Wasabi [33], commit hash fe12347. Wasabi can be downloaded from
https://github.com/danleh/wasabi. To run experiments scripts, this binary must
be available on the PATH to be called with the wasabi command.

  * •

DynamoRIO [18], commit hash fc4c25f. DynamoRIO can be downloaded from
https://github.com/DynamoRIO/dynamorio. To run experiments scripts, this
binary must be available on the PATH to be called with the drrun command.

  * •

Python, version 3.8.10 To run experiment scripts, both the python3 and python
(symlinked to python3) commands must be available on the PATH.

  * •

Python’s venv package, python3.8-venv for Debian/Ubuntu systems

  * •

wasm-bytecode-instrumenter, commit hash 3ea2003. The bytecode-instrumenter can
be downloaded from the repo. To run experiments scripts, this binary must be
available on the PATH to be called with the following command: wasm-bytecode-
instrumenter

  * •

rustc, version 1.71.0.

###  A.4. Installation and Testing

####  A.4.1. Installation

To install all required dependencies, follow the detailed instructions in the
README.md file in the base directory of the artifact.

####  A.4.2. Basic Test

To verify that an environment is correctly configured to run all scripts
provided in this artifact, edit the SUITES variable in the common.bash file to
only contain the polybench suite, then run the following command: RUNS=2
./experiment-all-suites.sh. We expect this initial test to run in about 1 day
(as opposed to the 7 days for all experiments as mentioned above). When
running experiments for polybench, a successful run should result in the CSV
directory containing subfolders with CSV output files for each suite script.
Refer to the README for instructions on how to run individual experiments.

###  A.5. Experiment workflow

The workflow of our experiments has two phases: collecting runtime data (saved
to CSV files) and generating the corresponding figures (saved to PDF and SVG
files). It is important to remember to save off any data/figures by copying
the csv/figures folder to alternate locations prior to running scripts. If
this is not done, the contents will be overwritten. To collect the runtime
data, a user can run any of the experiment*.bash scripts (experiment-all-
suites.bash to run all experiments). Logging information will be output to
stdout. Before plotting data, all experiments should be successfully run (as
some figures require data across multiple experiments). To generate figures,
run the plot-figure*.py scripts.

###  A.6. Evaluation and expected results

If you run these experiments, you will find the generated CSV and figure files
in their respective folders. To verify our own results, a side-by-side
comparison can be done with the figures in our paper.

###  A.7. Experiment customization

To add your own suite:

  1. (1)

Compile your suite to Wasm. The binary can only contain Wasm features
supported by the Wasabi and Walrus tools, which tends to be aligned with the
core specification.

  2. (2)

Make your new suite available in the suites folder following the conventions
shown by the other available suites.

  3. (3)

Update the SUITES variable in common.bash to contain your new suite.

  4. (4)

Update the suites variable in plot.py to contain your new suite.

Helpful variables in common.bash:

  1. (1)

RUNS: configure the number of times run to collect average execution times.

  2. (2)

SUITES: configure the suites that will run during experimentation.

###  A.8. JVMTI Experiment Artifact

####  A.8.1. Abstract

We also did a brief experiment discussed in Related Work, Section 6, to assess
the performance overhead imposed by JVMTI’s [3] handling of MethodEntry
events. To keep our core evaluations separate from this experiment, we have
placed this artifact discussion below. This can be found in the directory
jvmti at the base of the artifact located at
https://zenodo.org/doi/10.5281/zenodo.10795556.

####  A.8.2. Meta-Information

  * •

Benchmarks: We leveraged the Richards benchmark for experimenting with JVMTI.
An equivalent Richards benchmark for Java and Wasm has been provided as part
of this artifact.

  * •

Compilation: To compile the CallsMonitor, we require gcc version 9.4.0 to be
installed. To compile and run the Richards Java benchmark, we require Java
version 1.8 to be installed.

  * •

Binaries: We used the base Wizard binary in our experiment, version 23a.1617.
This binary has been provided as part of the artifact at the location
bin/base/wizeng.x86-64-linux.

  * •

Run-time environment: We ran this experiment on an x86_64 machine running
Ubuntu 20.04.1. It is not necessary to have sudo access as software can be
installed/symlinked in a user’s home directory. However, having sudo access
would substantially simplify the installation process.

  * •

Metrics: Our scripts report _relative execution time_ and _absolute overhead_
for JVMTI and Wizard. To ignore the base startup time required by the engines,
we measure instrumented and uninstrumented runs of the Richards benchmark with
0 loops ($Tb_{i}$ and $Tb_{u}$ below). Given:

    * –

instrumented execution time $T_{i}$

    * –

instrumented base execution time $Tb_{i}$

    * –

uninstrumented execution time $T_{u}$

    * –

uninstrumented base execution time $Tb_{u}$

We define _absolute overhead_ as the quantity $(T_{i}-Tb_{i})-(T_{u}-Tb_{u})$
and _relative execution time_ as the ratio $(T_{i}-Tb_{i})/(T_{u}-Tb_{u})$.

  * •

Output: We log all of our output to stdout which should be redirected to a
file for inspection. To view the summary of each Richard benchmark iteration,
grep the file for the term _SUMMARY_. The specific iteration of the Richard
benchmark is shown in the prefix of each line, e.g. [wasm-9-SUMMARY] means
that this line is part of the summary of the Wasm execution of the Richard
benchmark with 9 iterations. Each iteration is summarized by outputting all
execution times for instrumented and uninstrumented variants of the Java and
Wasm executions, then reporting the absolute overhead and relative execution
time. To view the absolute overhead, grep the file for _On average, runtime
with monitor took_. To view the relative execution time for each Richard
benchmark iteration, grep the file for the term _Factor_. We have included our
own results inside the runs_richards directory for reference.

  * •

Experiments: The artifact scripts run instrumented and uninstrumented
variations of the Richards benchmark at 9, 99, 999, 9999, and 99999 loops.
Each of these variations is run 10x to collect execution time averages across
all runs.

  * •

How much disk space required (approximately)?: Requires about 2 MB for the
jvmti directory and the Wizard engine binary.

  * •

How much time is needed to prepare workflow (approximately)?: Shouldn’t take
longer than 30 minutes since there are few dependencies.

  * •

How much time is needed to complete experiments (approximately)?: The
experiment takes about 3 hours when running on an Ubuntu 20.04.6 machine with
394 GB of RAM and an Intel®Xeon®Platinum 8168 processor running at 2.70 GHz.

  * •

Publicly available?: Yes, this artifact is available at the following URL:
https://zenodo.org/doi/10.5281/zenodo.10795556

  * •

Code license: Licensed under the Apache License, Version 2.0
(https://www.apache.org/licenses/LICENSE-2.0).

####  A.8.3. Software dependencies

Running the JVMTI experiment requires following software dependencies:

  * •

Java, version 1.8

  * •

gcc, version 9.4.0

###  A.9. Installation and Testing

####  A.9.1. Installation

To install all required dependencies to run the scripts, follow the detailed
instructions in the jvmti/README.md file.

####  A.9.2. Basic Test

The jvmti/README.md file also describes how to run a basic test to verify your
environment setup.

###  A.10. Experiment workflow

The execution workflow is pretty straightforward and outputs all logging
information to stdout. The run_richards.sh script iterates over the different
loops to execute (configured with the BENCHMARKS variable). For each of these
loops to execute, it calculates the average _absolute overhead_ and average
_relative execution time_ over 10 runs (configured with the NUM_RUNS variable)
when running the Richards benchmark for both Java, on the JVM, and Wasm, on
Wizard. If there are issues during execution, errors or warnings will be
output.

###  A.11. Evaluation and expected results

Evaluating the results can be done by grep-ing for various types of
information as described under “Output” in the Meta-Information section above.
The results should be similar to what our own execution found, located in
jvmti/runs_richards. It is possible that the _absolute overhead_ has
variations due to differences in the underlying system; however, the _relative
execution time_ should be similar.

###  A.12. Experiment customization

As described above, it is possible to customize the execution by manipulating
the following variables:

  * •

NUM_RUNS: Fluctuate the number of times each experiment is run to get an
average across execution time.

  * •

BENCHMARKS: Configure the loops to run on the Richards benchmark.

###  A.13. Methodology

Submission, reviewing and badging methodology:

  * •

https://www.acm.org/publications/policies/artifact-review-and-badging-current

  * •

http://cTuning.org/ae/submission-20201122.html

  * •

http://cTuning.org/ae/reviewing-20201122.html