💻 computer science

Mystra: Declarative Dynamic Taint Analysis via Shadow Virtual Machine

This paper introduces Mystra, a declarative language and Shadow Virtual Machine architecture for dynamic taint analysis that decouples taint semantics from runtime instrumentation, enabling the Shar tool to achieve high accuracy and significantly lower overhead across multiple JavaScript and Python runtimes compared to existing solutions.

Original authors: Zhuohao Zhang, Junkun Liu, Rui Yang, Yinzhi Cao, Ziyang Li

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhuohao Zhang, Junkun Liu, Rui Yang, Yinzhi Cao, Ziyang Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to catch a mischievous ghost (a security vulnerability) as it sneaks through a giant, bustling city (a computer program). The ghost starts as a harmless drop of ink (untrusted data) in a letter, but if it reaches a specific door (a sensitive operation like reading a file), it can destroy the whole building.

For a long time, security experts tried to catch this ghost using two main methods, and both had big problems. One method was like rewriting the city's blueprints before anyone moved in (source-rewriting). It was safe, but it slowed the city down to a crawl—making it 20 to 50 times slower! The other method was like hiring a special detective who only knew how to work in one specific neighborhood (engine-native). It was fast, but if the city changed its layout or you moved to a different neighborhood, the detective had to be fired and retrained from scratch.

Enter Mystra and Shar, a new team of investigators from Johns Hopkins University who decided to build a "Shadow City" right next to the real one.

The Shadow City (Shadow Virtual Machine)

Instead of changing the real city or rewriting its blueprints, the researchers built a parallel, invisible "Shadow Virtual Machine" that runs alongside the real program. Think of it as a ghostly twin city that mirrors every move the real city makes.

When a real operation happens—like a function calling another function or a file being opened—the Shadow City instantly sees it. But here's the magic: the Shadow City doesn't care how the real city is built. Whether the real city is running on a fast, modern engine (like V8 in Node.js) or an older one (like CPython), the Shadow City sees the exact same "events." It's like having a universal translator that lets the investigators watch the action without getting tangled in the specific machinery of the engine.

The Rulebook (Mystra)

Watching the city isn't enough; you need to know what to look for. That's where Mystra comes in. Mystra is a special, easy-to-read language (a "declarative" language) where security experts write simple rules like: "If a file path comes from a user, and that path is used to open a file, sound the alarm!"

The paper argues that previous tools were too rigid, forcing experts to write complex, messy code that was tied to specific engines. Mystra is different. It's like a set of LEGO instructions that can be snapped onto any engine.

The "Inject" and "Extract" Trick: One of the coolest features is how Mystra handles "higher-order functions" (like Array.map in JavaScript). Imagine a factory where a machine takes a box, passes it to a worker to paint, and then puts it back. Mystra can say, "Inject the dirtiness of the box into the worker's hands, and when the worker finishes, extract that dirtiness back onto the box." This allows the system to track the "ghost" even when it jumps into a callback function, something previous tools struggled to do without getting confused.

The Results: Fast and Accurate

The researchers built a tool called Shar to test this idea. They didn't just guess; they measured it against real-world benchmarks.

Speed: When they ran Shar on Node.js, the program only slowed down by 1.85 times. Compare that to the old source-rewriting tools, which were 22.7 times slower than Shar! Shar is also 22.7 times faster than the previous best tool, NodeMedic-FINE, on the exact same workloads.
Accuracy: On a test set of 493 known vulnerabilities (called SecBench.js), Shar caught 95.5% of them. Even better, when they tested it on fixed versions of the software (where the holes were already patched), Shar made zero false alarms. It didn't cry wolf once.
Portability: The team proved their idea works across different worlds. They took the same core engine and rules and successfully ported them to three different runtimes: V8 (used in Node.js and Chrome), SpiderMonkey (used in Firefox), and CPython (used in Python). They only had to write a small "adapter" for each; the main brain remained the same.

What They Didn't Solve

It's important to know what this tool doesn't do. The paper explicitly states that Shar does not track "implicit flows." Imagine if the ghost didn't leave a trail of ink but instead changed the color of the sky to signal a trap. Shar doesn't watch the sky; it only watches the ink. The authors note that tracking those invisible signals would slow the system down massively (by 36.7 times in other studies), so they chose to focus on the visible trails for now.

They also found that if a program breaks a string of text into tiny pieces (like splitting a sentence into words), the connection to the original "dirty" text can sometimes get lost. This is a known limitation of this type of tracking, and they suggest future work might need to look at character-by-character tracking to fix it.

The Bottom Line

The paper presents Shar and Mystra not as a magic wand that solves every security problem, but as a major step forward in how we track data. By separating what we track (the rules) from how we watch the program (the Shadow VM), they created a system that is fast, accurate, and flexible.

In their tests, they showed that you can have a security tool that is both a speed demon and a sharp-eyed detective, capable of spotting 95.5% of vulnerabilities without slowing down the program it's protecting. It's a proof that you don't have to choose between speed and safety anymore.

Technical Summary: Mystra and Shar

Problem Statement

Dynamic Taint Analysis (DTA) for interpreted languages like JavaScript and Python faces a fundamental architectural fragmentation. Existing systems typically couple the capabilities of observing host-runtime operations, maintaining parallel taint states, and defining taint propagation within a single instrumentation mechanism.

Source-rewriting systems (e.g., Jalangi2, NodeMedic) instrument code before execution. While engine-agnostic, they introduce a source-transformation boundary that requires modules to be available and transpiled (often via Babel). This approach forgoes native and Just-In-Time (JIT) compiled execution, resulting in order-of-magnitude performance slowdowns.
Engine-native systems (e.g., Foxhound, PanoptiChrome) modify runtime representations or execution handlers to gain visibility. However, their shadow state, propagation logic, and instrumentation are tightly bound to a specific engine's internals. This makes the analysis logic inseparable from the engine, hindering portability across different execution tiers, embeddings, or languages.

The core problem is the absence of a runtime-independent execution model for DTA. Different runtimes expose operations through varying bytecodes, stacks, and compilation strategies, yet taint analysis requires the same logical information (identity, arguments, results, context) from each. Current approaches fail to separate the observation of host operations from the semantics of taint state transitions, leading to high overhead or poor portability.

Methodology

The authors propose a solution consisting of three main components: a Shadow Virtual Machine (Shadow VM), the Mystra declarative specification language, and the Shar implementation framework.

1. The Shadow Virtual Machine (Shadow VM)

The Shadow VM is a parallel virtual machine that executes alongside diverse host runtimes (e.g., V8, SpiderMonkey, CPython). It maintains a parallel state $\sigma = \langle S, H, G, C \rangle$ :

Shadow Stack ( $S$ ): Tracks active operation frames in event-nesting order, mapping operands to taint identifiers. It handles non-local control transfers (exceptions, async suspensions) by synchronizing with the host's logical continuation.
Shadow Heap ( $H$ ): Tracks object properties persisting across frames, mapping object-address/property-key pairs to taint identifiers to avoid over-tainting entire objects.
Provenance DAG ( $G$ ): Records the origin of taint, linking flow nodes to operand taints to reconstruct source-to-sink paths.
Specification Context ( $C$ ): Provides named stores for data persisting across invocation boundaries (e.g., file I/O), bridging gaps where the shadow stack/heap would otherwise lose connection.

The Shadow VM interacts with the host via a Host Interface mediated by adapters. This interface standardizes six capabilities: operation events (entry/exit), operand addressing, operation identity, object lifecycle, runtime queries, and continuation synchronization. This allows the Shadow VM to observe interpreted, native, and JIT-compiled execution uniformly without forcing deoptimization.

2. Mystra: Declarative Taint Specification Language

Mystra is a compiled, declarative domain-specific language (DSL) with formal operational semantics designed to drive the Shadow VM. It separates what to track from how it is tracked.

Core Constructs: Rules define source (entry points), sink (dangerous operations), propagate (flow between operations), and clear (sanitization).
Higher-Order Functions (HOF): A key innovation is the inject and extract actions. These model native higher-order functions (e.g., Array.map) by bridging taint across the opaque native loop and the visible user-defined callback. inject transfers taint from the container to the callback parameter; extract aggregates return taints back to the container.
Guarded Predicates: Rules can include where clauses to condition actions on runtime predicates (e.g., checking if an object is a prototype), reducing false positives.
Specification Context: The set action allows rules to persist taint across boundaries (e.g., writing a file path to a global store and retrieving it later).
Compilation: Mystra rules are compiled ahead-of-time into a binary representation (.tbin). The compiler performs type-checking and schedules actions into pre- and post-hook instruction lists, enabling $O(1)$ dispatch with no runtime parsing.

3. Shar Implementation

Shar is the concrete DTA framework implementing this architecture. It features a shared core engine (taint engine, interpreter, rule loader, DAG, context) and runtime-specific adapters. The authors instantiated Shar on three orthogonal axes:

Embedding: V8 in Node.js and Chromium.
Engine: SpiderMonkey.
Language: CPython.

Key Contributions

Shadow VM Abstraction: A runtime-independent abstract machine that separates runtime observation from taint state and transitions, enabling portability across engines and languages.
Mystra Language: A compiled declarative language with formal operational semantics that supports expressive taint behaviors, including native higher-order function bridging via inject/extract.
Shar Framework: A multi-lingual DTA framework demonstrating portability across V8 (Node.js/Chromium), SpiderMonkey, and CPython with a shared core.
Systematic Evaluation: Comprehensive benchmarks on detection accuracy, performance overhead, expressiveness, and portability.

Results

Detection Accuracy

Evaluated on SecBench.js (493 in-scope CVEs across four CWE categories):

Recall: Shar achieved 95.5% overall recall.
Precision: Zero false positives were observed on patched-version testing.
Comparison: On the subset of Code Injection and Command Injection cases (136 total), Shar detected 97.1% (132/136), significantly outperforming NodeMedic-FINE, which detected 63.9% (87/136). Shar uniquely detected 46 cases missed by NodeMedic-FINE, primarily due to NodeMedic's inability to instrument certain packages via Babel or its loss of taint before the sink.
Real-World Vulnerabilities: Shar successfully detected 11 out of 12 real-world vulnerabilities disclosed between 2024–2026 across Node.js, Chromium, and CPython. One case (n8n) was partially detected due to a limitation in bridging SQL persistence boundaries without explicit bridging rules.

Performance

Evaluated on NodeMedic's benchmark:

Overhead: Shar incurred only 1.85× runtime overhead over vanilla Node.js.
Comparison: This is 22.7× lower overhead than NodeMedic-FINE (41.95×) and significantly better than source-rewriting tools like Jalangi (28.78×).
JIT Impact: The overhead remained low even with Maglev JIT enabled (1.28× over baseline), demonstrating that the Shadow VM does not force deoptimization.

Expressiveness and Portability

Rule Synthesis: The authors demonstrated that LLMs could synthesize valid Mystra rules. With one round of diagnostic feedback, the pass rate of synthesized rules for 32 patterns increased from 19/32 to 29/32.
Conciseness: Mystra rules for Node.js standard libraries covered 97.2% of APIs modeled by CodeQL with 18× fewer lines of code (63 LoC vs. 1,149 LoC).
Portability: The shared core (3,941 LoC) remained identical across V8, SpiderMonkey, and CPython. Porting effort was concentrated in adapters and runtime-specific bindings (e.g., 446 LoC for CPython adapter), confirming the runtime-independent design.

Significance

The paper claims that Mystra and Shar represent a shift from instrumentation-heavy, engine-specific DTA to a runtime-independent, declarative approach. By separating the observation mechanism (Shadow VM) from the taint semantics (Mystra rules), the system achieves:

Portability: The ability to deploy the same analysis logic across different engines (V8, SpiderMonkey) and languages (JS, Python) with minimal modification.
Performance: Drastically reduced overhead compared to source-rewriting approaches, making DTA viable for production environments and JIT-optimized code.
Expressiveness: The ability to declaratively model complex behaviors like higher-order function callbacks and cross-boundary state (file I/O) without hardcoding engine-specific logic.
AI-Readiness: The formal semantics and concise syntax of Mystra make it suitable for automated synthesis by Large Language Models (LLMs), facilitating the rapid creation of rules for new vulnerability classes.

The authors conclude that while challenges remain regarding implicit flows, string decomposition, and external storage boundaries, this architecture provides a scalable foundation for next-generation dynamic taint analysis.