Creating concise and efficient dynamic analyses with ALDA

A dynamic analysis is a tool that watches a program run and checks it for bugs — a data race, an uninitialized read, a use-after-free — but writing a fast one means burying the idea under pages of hand-tuned low-level instrumentation, so many useful analyses are never built or run too slowly to use; this paper (Georgia Tech) argues most dynamic analyses share the same shape (attach metadata to values, propagate it as the program runs, check it at certain events), captures that shape in a small high-level language called ALDA, and builds an optimizing compiler (ALDAcc) that turns a short ALDA description into instrumentation the authors report performs on par with hand-tuned code.

The argument in one glance

Problem

Writing a fast dynamic analysis buries the idea under low-level tuning

A dynamic analysis watches a program as it runs and checks it for a class of bug: a race detector flags two threads touching the same memory without a lock, a memory-safety checker catches reads of uninitialized or freed memory, a taint tracker follows untrusted data through the program. The core idea of each is usually simple to state. But making one run at acceptable speed is not: the analysis has to be woven into the program as instrumentation at thousands of points, and every added instruction slows the program down, so a usable tool demands heavy, expert low-level optimization of that instrumentation. The analysis logic ends up buried under pages of performance tuning that has nothing to do with the idea. The result is that many analyses that would be valuable are simply never built, and many that exist are too slow to run in practice.
What people did

Hand-write and hand-tune each analysis as a bespoke instrumentation pass

The standard practice is to build each analysis directly against an instrumentation framework — inserting shadow-state updates and checks around loads, stores, calls, and lock operations by hand, then optimizing that code painstakingly. MemorySanitizer, ThreadSanitizer, and the classic Eraser race detector were each built and tuned this way.
Why it fell short

The tuning expertise is a barrier separate from the analysis idea

Every new analysis pays the full cost again: even when the idea is small, achieving usable performance requires the same low-level optimization craft, which is a specialized skill unrelated to the analysis being expressed. So the effort does not amortize, and the barrier keeps useful analyses unwritten or leaves them with inefficient implementations. Nothing captures what dynamic analyses have in common so the tuning could be done once, generically.
This paper's idea

Describe the analysis in a small language and let a compiler do the tuning

The paper argues that most dynamic analyses share one shape: attach metadata to program values or memory, propagate that metadata as the program executes, and check or update it at certain events. ALDA is a high-level language built around exactly that shape, and because it restricts the developer to only the essential operations, an optimizing compiler (ALDAcc, targeting LLVM instrumentation) can generate implementations the authors report perform on par with hand-tuned analyses — from descriptions the authors describe as succinct and simple.

Why this problem is worth solving

The value of these tools is enormous and the cost of building them is what limits their reach.

A dynamic program analysis observes a program while it actually runs and checks a property of that concrete execution, as opposed to a static analysis that reasons about the code without running it. Because it sees real values, real pointers, and the real interleaving of threads, a dynamic analysis can catch things static analysis cannot pin down: a use-after-free that only happens on one path, a data race that only appears under a particular schedule, the flow of an untrusted input all the way to a dangerous sink. The catch is how it works — the analysis is realized as instrumentation, extra code inserted throughout the program that maintains bookkeeping alongside the real computation. That bookkeeping runs on every relevant operation, so a naive implementation can slow a program down by large multiples, and the entire engineering challenge is making the instrumentation cheap enough that people will actually run it.

Almost all of these tools maintain a hidden layer of bookkeeping shaped the same way.

Shadow metadata is extra state that a dynamic analysis keeps for the values and memory locations of the program under observation, held off to the side rather than in the program’s own variables. A memory-safety checker keeps a bit per memory byte saying whether it has been initialized; a race detector keeps, for each memory location, the set of locks held and threads that have accessed it; a taint tracker keeps a taint label for each value. As the program runs, the analysis propagates this shadow state — when a value is copied, its metadata is copied; when memory is written, its shadow is updated — and at certain events it checks the shadow state and reports a violation. Recognizing that attach-propagate-check over shadow metadata is the common skeleton of dynamic analyses is exactly what lets a language capture the pattern once and a compiler optimize it for every analysis built on it.

What people did before, and where it broke

Hand-write each analysis against an instrumentation framework. Build the tool directly on a system like the LLVM instrumentation passes or a binary-rewriting framework, inserting and tuning shadow-state code by hand. Where it broke. Every analysis re-pays the full low-level optimization cost, which is a specialized skill separate from the analysis idea, so building a new one is slow and many are never built.
Ship a few heavily-optimized sanitizers and expect everyone to use those. Invest deeply in a handful of tools — MemorySanitizer, ThreadSanitizer, AddressSanitizer — and make them fast and robust. Where it broke. This produces excellent versions of the specific checks the authors chose, but a researcher or engineer with a new property to check gets none of that leverage; the optimization work is locked inside each bespoke tool rather than available as reusable machinery.
Provide a general instrumentation or interception API. Frameworks let a developer run a callback on every load, store, or call, which makes analyses easy to prototype. Where it broke. Generality is the enemy of speed here: a general callback interface cannot make the assumptions a specialized implementation makes, so prototypes built this way are typically far too slow for real use, and closing that gap sends the developer right back to hand-tuning.
Write analyses in a general-purpose language and hope the compiler helps. Implement the analysis logic in ordinary code and rely on a standard optimizing compiler. Where it broke. A general-purpose compiler cannot exploit the specific structure of dynamic analysis — the shadow-state layout, the propagation pattern, the fact that only essential operations are needed — because that structure is invisible in general-purpose code, so the crucial analysis-specific optimizations are left on the table.
The gap. No approach let a developer state a dynamic analysis at a high level, in terms of the metadata it keeps and the events it hooks, and then had a compiler that understood that structure well enough to generate instrumentation competitive with expert hand-tuning. Expressiveness and performance were traded against each other; the tuning never became reusable.

How ALDA and ALDAcc are put together

From a short ALDA description to optimized LLVM instrumentation

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Find the shape all dynamic analyses share, and make that shape the language. The core claim is that dynamic analyses are not each a unique engineering problem but variations on one template: they associate metadata with program entities, propagate it through execution, and act on it at chosen events. ALDA turns that template into a language with four kinds of declaration — the metadata types, the storage for metadata (a set, or a map from a program value to metadata), the propagation functions, and the insertion points that hook them into the program. A developer expressing an analysis writes only these, describing what to track and where, never how to instrument. Building a high-level description language around the common structure of a whole class of tools, so that a short specification replaces pages of bespoke low-level code, is the same raise-the-abstraction move the collective-communication language work covered elsewhere on this site makes, letting an engineer state the intent and leaving a compiler to produce an implementation that rivals what an expert would hand-write.

Restrict the language on purpose, because restriction is what lets the compiler optimize. The reason a general instrumentation API stays slow is that it must support arbitrary callback code, which the surrounding compiler cannot see into or specialize. ALDA takes the opposite stance: it deliberately supports only the essential operations of dynamic analysis — a constrained set of arithmetic, logical, and bitwise expressions, simple conditionals, and structured access to declared metadata — and nothing more. Because the compiler knows the full space of what an ALDA program can do and exactly how its metadata is laid out, ALDAcc can generate and optimize the instrumentation with assumptions a general framework can never make, which is how the authors reach performance they report as comparable to hand-tuned analyses. Trading away general expressiveness to give a compiler the closed, well-understood vocabulary it needs to generate efficient code is the same discipline the fine-grained value-profiling framework covered elsewhere on this site relies on, where confining what an analysis may express is precisely what keeps its instrumentation cheap enough to run at scale.

Attach to the program by naming events, not by editing instrumentation. The mechanism that connects an analysis to the running program is the insert declaration: it says, in effect, before every memory load call this function with the loaded pointer, or after every function entry call this one with the current thread. The developer names the event and the operands, and ALDAcc weaves in the actual instrumentation. This keeps the analysis description entirely at the level of what happens on which event, and lets the same description drive whatever the compiler decides is the fastest way to insert the hooks. Expressing instrumentation as declarative before- and after-event hooks that a tool inserts, rather than as hand-placed code, is the same non-intrusive instrumentation philosophy the dynamic WebAssembly instrumentation work covered elsewhere on this site is built on, separating what to observe from the machinery that observes it.

Following an analysis through ALDA

Sketching a race detector in ALDA

An illustrative walk, based on the ALDA design and syntax, of how a lockset-style race detector like Eraser would be expressed and compiled. Specific compiler optimizations and performance figures are not drawn from the paper's main text, which was not available for this draft.

Step 1 of 5

Declare the metadata the analysis keeps

A lockset race detector keeps, for each shared memory location, the set of locks consistently held when it is accessed, plus per-thread and per-lock identifiers. In ALDA this is expressed as metadata declarations: analysis-specific types for a lock identifier and a thread identifier, and a map from a memory location to the metadata tracked for it.

The type declarations fix widths and can be marked for synchronization, so the generated runtime structures are concrete and known to the compiler rather than open-ended.

Why it works

A shared skeleton means the tuning can be done once. Every hand-built analysis re-pays the low-level optimization cost because nothing captures what they share → but modeling all of them as attach-propagate-check over declared metadata lets one compiler carry the optimization burden → so a new analysis inherits the tuning instead of re-earning it.
Restriction gives the compiler the closure it needs. A general callback interface hides arbitrary code the compiler cannot specialize → but confining ALDA to only the essential operations makes the full behavior of any program known → so ALDAcc can apply analysis-specific optimizations that reach, by the authors’ account, hand-tuned-level performance.
Declared metadata layout lets the runtime be specialized. Shadow state built ad hoc in general code is opaque to optimization → but declaring metadata as typed sets and maps with fixed widths fixes the storage the compiler and runtime library must support → so the generated bookkeeping structures are concrete and can be made efficient rather than generic.
Event hooks separate what to observe from how to instrument. Hand-placed instrumentation ties the analysis logic to the mechanics of insertion → but naming events with before- and after-hooks and their operands leaves insertion entirely to the compiler → so the developer writes short, portable descriptions and the tool controls the low-level weaving.
A high-level description is short enough to actually write. The barrier that leaves analyses unbuilt is the volume of tuning code, not the idea → but ALDA descriptions are, the authors report, succinct and simple, expressing an analysis in a small program → so the analyses that were never realized because of the effort become feasible to write.

What it costs (trade-offs and scope)

This is a draft written without the paper’s main text. The abstract, the public ALDA syntax appendix, and the project README were available; the paper body — the specific optimizations ALDAcc performs and the evaluation numbers — was behind a publisher access wall for this draft. Statements here about mechanism come from the syntax and abstract, and no performance figures are invented.
Restriction bounds what can be expressed. The same confinement to essential operations that enables optimization also limits the language: an analysis needing behavior outside ALDA’s arithmetic, logical, conditional, and metadata operations may not be expressible, and the paper’s own framing is about the common structure of dynamic analyses, not every conceivable one.
The performance claim is a comparability claim. The reported result is that ALDA-generated analyses are on par with hand-tuned implementations for the cases compared (Eraser and MemorySanitizer), not that they are faster; the general question of how close the match is across all analyses, and where it falls short, lives in the evaluation not covered here.
The evidence is eight analyses on one framework. Universality is argued by building eight analyses, including well-known ones, against the LLVM instrumentation framework (LLVM 6.0 in the released artifact); this is a demonstration of range rather than a guarantee that any dynamic analysis fits, and portability to other instrumentation backends is not something this draft can speak to.
Correctness of a generated analysis rests on the description and the compiler. As with any high-level-to-instrumentation compiler, a bug can live in the ALDA description, in ALDAcc, or in the runtime library; the approach moves the tuning burden into the compiler, which is the point, but also concentrates trust there.

The evaluation

Three ways to build a dynamic analysis

Property	Hand-tuned bespoke pass	General instrumentation API	ALDA + ALDAcc
Effort to build a new analysis
Who does the performance optimization
Reported performance
Expressiveness
Analyses demonstrated		Varies

A qualitative comparison based on the paper's abstract and the public ALDA syntax and repository; the paper's main body, including its concrete optimization techniques and performance measurements, was not available for this draft, so cells state the reported claims and design rather than specific figures.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is an honest draft assembled from the paper’s abstract, the publicly released ALDA syntax appendix, and the project’s repository README; the main text was behind a publisher access wall, so the concrete optimizations ALDAcc performs and the evaluation numbers are not reproduced and nothing quantitative is invented here. What is solid is the design: ALDA models a dynamic analysis as metadata declarations, propagation functions in a restricted C-like subset, and before- and after-event insertion hooks, and ALDAcc compiles that to an LLVM instrumentation pass with a runtime library for the built-in metadata structures. The paper’s central argument is that restricting the language to the essential operations of dynamic analysis is exactly what lets the compiler generate instrumentation the authors report as on par with hand-tuned implementations, demonstrated by building eight analyses including MemorySanitizer and Eraser. Read the specific performance and optimization claims against the paper itself; treat this page as a faithful account of the idea and structure, not of the measured results.

Background

Why fast dynamic analyses matter enough to build a language for

It is worth seeing why the speed of these tools is worth a whole compiler. Dynamic analyses are how a great deal of real software is kept safe: memory-safety checkers catch the uninitialized reads and use-after-free bugs behind countless security vulnerabilities, race detectors find the concurrency bugs that are nearly impossible to reproduce by hand, and taint trackers trace how untrusted input reaches dangerous operations. The reason they are not run even more than they are is overhead — instrumentation that maintains shadow state on every relevant operation can slow a program by large multiples, so teams run these checks sparingly, and any analysis too slow to tolerate simply does not get used. That pressure, where the usefulness of a correctness tool is gated by how cheaply its bookkeeping can be made to run, is the same pressure the memory-sanitization work covered elsewhere on this site operates under, redesigning how shadow state is stored and checked precisely so the safety check is fast enough to keep on. ALDA attacks the same pressure from a different angle: instead of optimizing one analysis by hand, make the optimization reusable so every analysis expressed in the language inherits it, and so the analyses that were never built because tuning them was too much work finally become worth writing.

If you remember only three things

1. Dynamic analyses — race detectors, memory-safety checkers, taint trackers — are essential but slow and painful to build, because acceptable performance demands heavy low-level tuning of the instrumentation, a craft separate from the analysis idea; so many useful analyses are never built or run too slowly, and the tuning effort never amortizes across tools.
2. ALDA is a high-level language that captures the common shape of dynamic analyses — declare metadata (as typed sets or maps), write propagation functions in a restricted C-like subset, and hook them to events with before- and after-insertion points — and ALDAcc, its optimizing compiler, turns a short description into an LLVM instrumentation pass; the deliberate restriction to essential operations is what lets the compiler apply analysis-specific optimizations a general framework cannot.
3. The paper reports building eight analyses this way (including MemorySanitizer, Eraser, FastTrack-style race detection, and use-after-free checking) from succinct descriptions, and reports that the generated Eraser and MemorySanitizer perform on par with hand-tuned references. This explainer is a draft from the abstract, the public syntax appendix, and the repository, without the paper body, so its specific optimization techniques and performance figures should be confirmed against the paper itself.

Check yourself

Check your understanding

1. What common structure does ALDA assume dynamic analyses share?
2. Why does ALDA deliberately restrict what a developer can express?
3. How does an ALDA analysis attach to the running program?
4. What should a reader keep in mind about this particular explainer?

Sources

The paper is “Creating Concise and Efficient Dynamic Analyses with ALDA” by Xiang Cheng and David Devecsery, published at ASPLOS 2022, pages 740-752, DOI 10.1145/3503222.3507760.

This explainer is a draft. The paper’s main text was behind a publisher access wall (the ACM Digital Library page returned a bot-verification challenge, there is no arXiv version, no author preprint was found, and no web-archive snapshot of the gold PDF exists). It is written from three available sources: the paper’s full abstract; the publicly released ALDA full-syntax appendix (which specifies the language’s four declaration sections — metadata types, metadata storage as sets and maps, propagation functions over a restricted C-like operation set, and before- and after-event insertion declarations with their call arguments); and the project’s open-source repository README (which describes the toolchain as a DSL parser and code generator, a runtime library of built-in data structures, and an LLVM instrumentation pass targeting LLVM 6.0, supporting Eraser, FastTrack, MemorySanitizer, and use-after-free analyses). The abstract’s claims are reproduced faithfully: that ALDA descriptions are succinct and simple, that eight analyses were built including MemorySanitizer, and that the generated Eraser and MemorySanitizer are comparable in performance to hand-tuned implementations. The paper’s specific optimization techniques and its quantitative evaluation are not reproduced here and should be read from the paper itself; no performance numbers have been invented for this draft.