Lockstep Forced Execution for Dynamic-Language Programs

Dynamic analysis studies a program by running it, so it can only see code that actually runs. In JavaScript and Python this blind spot is especially costly. Static tools cannot fill it either: call edges hidden behind computed property names and runtime-added methods defeat them. The leading workaround is forced execution: flip a branch the tests never took and see what happens downstream. Each flip normally costs a full re-execution. A tool that wants to flip hundreds of branches per program therefore pays hundreds of times the cost of a single run, and most of that work re-computes state that every variant shares.

We propose to run all the flipped variants of one test inside a single interpreter, borrowing the oldest trick in parallel hardware. While the variants follow the same control path, they execute as one instruction stream over a vector of per-variant values, the way SIMD hardware (single instruction, multiple data) applies one instruction to many lanes. When their control flow splits, they peel off into independent executions, the way MIMD hardware (multiple instruction, multiple data) lets each unit run its own program. When their paths rejoin, they merge back into lockstep. The heap is stored as one shared base plus small per-variant differences. The cost of exploring $N$ flips then grows with how much the variants actually differ, not with $N$ times the size of the program state. The bet is that data movement, not computation, is the dominant cost of forced exploration in garbage-collected runtimes, and that sharing state removes most of it.

Core Claim

Forced-branch exploration in dynamic languages is bottlenecked by duplicated state. Every variant re-builds and re-traverses nearly the same heap. An interpreter that executes variants in lockstep where they agree, diverges where they disagree, and re-merges at control-flow reconvergence points should explore many more flipped branches per CPU-hour than per-flip re-execution or OS-level process forking. In a fixed budget it should reach measurably more security-relevant sinks. What is new is not forced execution itself, which Dasty and predicate switching already do. The new parts are the divergence-and-reconvergence execution model applied to forced exploration of a dynamic-language runtime, and a heap representation whose memory traffic scales with variant differences.

As a rough cost model, let $T_s$ be the time of the shared lockstep portion of a run, $T_k$ the time variant $k$ spends diverged, $B$ the bytes of the shared heap, and $\Delta_k$ the bytes in which variant $k$'s heap differs. Lockstep execution then costs about

$$ C_{\text{lockstep}} \approx T_s + \sum_{k=1}^{N} T_k, \qquad M_{\text{lockstep}} \approx B + \sum_{k=1}^{N} \Delta_k, $$

while re-execution costs about $N \cdot (T_s + \bar{T})$ and roughly $N \cdot B$ bytes moved, where $\bar{T}$ is the average diverged time. This form simply counts shared work once and divergent work per variant. The speedup is large exactly when variants spend little time diverged and differ in few heap objects. That is an empirical question, and the experiments measure it directly rather than assuming it.

Background and Positioning

The coverage gap is well documented. Towards locating execution omission errors shows that dynamic slicing cannot see bugs caused by code that never ran. It fixes this by predicate switching, which inverts a branch outcome and then aligns the new execution with the original one region by region. Its software dependence tracking costs an 18.3× to 154.9× slowdown, on C utilities only. Unveiling the Invisible: Detection and Evaluation of Prototype Pollution Gadgets with Dynamic Taint Analysis brings forced branch execution to Node.js. Its tool, Dasty, inverts branches that depend on attacker-polluted properties, using AST-level instrumentation (instrumentation inserted at the level of the program's syntax tree) on GraalVM/NodeProf. These two papers motivate the work and also supply its method. We reuse Dasty's choice of which branches to flip and the predicate-switching idea of aligning executions after a flip. We change how the flipped runs are executed: together rather than one by one.

The dynamic-language work explains why static pruning cannot substitute for this. CALLME: Call Graph Augmentation with Large Language Models for Javascript reports that the static analyzer Jelly reaches only 0.43 F1 on dynamic property-access calls. It recovers edges one at a time with a language model. Call Me Maybe: Enhancing JavaScript Call Graph Construction using Graph Neural Networks predicts missing edges with a graph neural network. It finds that adding dynamic edges from unit tests improves top-1 predictions by up to 106% on some packages, which is direct evidence that more dynamic coverage feeds better static models. PoTo: A Hybrid Andersen's Points-to Analysis for Python shows that running opaque code concretely in the real interpreter beats both pure static tools and neural type inference. These papers constrain the design. Any acceleration must stay concrete, executing real code, rather than predicting behavior, because predictors are the weak link. HardTaint: Production-Run Dynamic Taint Analysis via Selective Hardware Tracing cuts taint overhead to 9.06%, but only because static analysis of C binaries can prune about 89% of instructions. That pruning is unavailable when dispatch targets are unknown until runtime. We do not compete with HardTaint on native code. We attack the dynamic-language case it leaves open.

The execution model comes from the hybrid SIMD-MIMD line. The DADO tree machine, described in DADO: A Tree-Structured Machine Architecture for Production Systems, broadcasts one instruction stream down a tree and lets subtrees detach to run their own logic. NON-VONs Applicability to Three AI Task Areas switches between global SIMD and multiple-SIMD modes for local branching. We transfer this decouple-and-rejoin discipline from hardware processing elements to program variants inside an interpreter.

The memory-wall work frames the cost model. Space Efficient Sequence Alignment for SRAM-Based Computing: X-Drop on the Graphcore IPU obtains its 10× gain over a GPU largely by shrinking the per-instance memory footprint 55× so that problems fit near compute. Our delta heap pursues the same lever, footprint per explored variant, in software. We deliberately do not propose new hardware. In-memory crossbars are built for uniform dot products and handle pointer-chasing interpreter state poorly, as the research file's survey of compute-in-memory limits notes. A manycore study is a follow-on only if the measurements below justify it.

Research Program

We will build the prototype, which we call Lockstep, on Truffle/NodeProf so that it shares Dasty's instrumentation substrate and the comparison isolates the execution model. The program has four parts.

The first part is the value representation. A variant value is a compact object holding one value per active variant. It collapses to a scalar when all variants agree, so the common case runs unmodified.

The second part is the heap. Objects carry a shared base layout plus a sparse per-variant overlay. Writes made by a subset of variants go into that subset's overlay. Reads check the overlay first. Object-shape changes, such as adding a property at runtime, are recorded as overlay entries rather than forcing a copy of the object.

The third part is control. At a branch whose condition is a variant value with mixed outcomes, the active set splits. We will try two strategies. In the first, variants execute the two sides in turn under a mask, the GPU-style approach, which keeps sharing. In the second, a variant detaches into its own interpreter thread with a frozen copy of its overlay, the MIMD-style approach, used when the diverged region is long, contains I/O, or calls native code. The choice between them is made by a simple threshold on observed diverged length.

The fourth part is reconvergence. Divergent variants rejoin at the immediate post-dominator of the split branch when that point is known: the post-dominator is the first later point that every path from the branch must pass through. When it is unknown, as with exceptions or callbacks scheduled by the event loop, they rejoin at the return of the enclosing function. This adapts the region alignment of predicate switching. Variants that crash, hit timeouts, or violate a cheap invariant are dropped and logged as infeasible.

The taint layer and the policy for which branches to flip are taken from Dasty as unchanged as practical. The flip set for a test is every branch whose predicate reads a polluted property. It is flipped all at once as $N$ variants of a single run, rather than as $N$ re-runs.

Baselines

The naive reference point is Dasty-style forced execution as published: one re-execution of the test per flipped branch on the same machine. It defines the cost we claim to reduce. The strongest existing method on this question is Dasty itself, which flips polluted-property branches on NodeProf/GraalVM. On the Libraries.io corpus of 9,564 heavily depended-upon packages plus Kibana, it reports candidate gadgets in 1,269 server-side packages and 49 packages with verified proof-of-concept exploits, a speedup of over 784% against Augur, and about 11 minutes of manual verification per candidate (Unveiling the Invisible). It is the right competitor because it attacks the same coverage gap, in the same language, with the same instrumentation stack. We will run it on the same package subset, the same test suites, the same machine, and the same wall-clock budget per package, with both tools using identical flip policies and sink lists.

Beating Dasty means one of two things. Lockstep either reaches the same sinks in at most half the CPU time, or it finds strictly more distinct candidate gadget flows within the same budget. In either case, the precision of manually sampled candidates must not drop.

The second baseline is a parallel fork-based explorer. It runs the test to each flip point once, then forks the Node.js process there with operating-system copy-on-write and explores each flip in a child, using all cores. This is the competitor a systems reviewer would build first. It gets the same core count and memory cap as Lockstep.

Three ablations isolate the key ingredients. The first disables re-merging, so variants diverge but never rejoin. This tests whether reconvergence carries the gain. The second replaces the per-object overlay with whole-object copying on first write. This tests whether the fine-grained delta heap matters. The third forces every divergence into detached mode. This tests whether the masked, SIMD-like mode earns its complexity.

For the predicate-switching setting we have only the published 18.3×–154.9× slowdown range for software dependence tracking on C (Towards locating execution omission errors). We found no reported result on Lacuna for predicate switching on JavaScript or Python workloads, so this number serves as context rather than a head-to-head target.

Why not just…?

Why not just fork a process at each flip point and use all the cores? This is the real threat, and the proposal stands or falls on it. Copy-on-write forking already shares the prefix of each run, and it parallelizes trivially. Our reason to doubt it is specific to garbage-collected runtimes. Copy-on-write shares memory in 4KB pages, while a collector moves and marks objects across the whole heap. A collection in each child may therefore dirty most pages and turn sharing into near-full duplication. Fork also never re-merges: a variant that rejoins the main path after ten statements still pays for the entire rest of the run. Both claims are measurable. We will record resident memory and pages copied per child as $N$ grows, and the fraction of variants that reconverge within a function. If forking is within 1.5× of Lockstep on throughput at equal memory, we will report that the simpler design wins and treat Lockstep's contribution as reconvergence-driven pruning alone.

Why not just predict the missing behavior with a language model or graph network instead of executing it? The file's evidence argues against prediction replacing concrete execution. Direct language-model abstraction failed to converge on over half of the benchmarks in ABSINT-AI: Language Models for Abstract Interpretation, and neural type inference was right 2 times in 100 versus 89 for PoTo's concrete hybrid (PoTo). Predictors and executors are also complementary rather than rival. GRAPHIA improves when fed dynamic edges, so a secondary experiment feeds Lockstep-discovered call edges into GRAPHIA's training to test whether cheaper coverage translates into better predicted call graphs.

Why not just generate better tests or fuzz harder so fewer branches need forcing? Better inputs reach branches honestly, which forced execution cannot claim. However, prototype-pollution gadgets live behind properties the tests never set, and Dasty's limitation is precisely that forcing only helps once some test reaches the branch. Lockstep is orthogonal to input generation: it lowers the cost per flip for whatever tests exist. We will check this by running both tools on the original and a fuzzer-augmented test suite. The gain should persist on both if the claim is right.

Proposed Experiments

The primary experiment uses a stratified sample of a few hundred packages from Dasty's Libraries.io corpus, chosen to cover small libraries and large frameworks, together with Kibana as a stress test. For each package and tool, we measure four things: distinct flipped branches explored per CPU-hour; distinct statements and sinks newly reached relative to the unforced test run; peak memory and bytes copied per explored variant; and candidate gadget flows found within a fixed budget. We will also manually verify a random sample of candidates per tool, so that a throughput gain bought with more infeasible garbage is visible. Infeasibility rate, meaning the share of variants dropped by crash, timeout, or invariant failure, is reported alongside, because forcing many flips at once could compound infeasible states.

The decisive check is the $N$-scaling curve. We will plot throughput and memory against the number of simultaneous flips, from 1 to several hundred, for Lockstep, the fork explorer, and the ablations. The cost model predicts that Lockstep's memory grows with the summed differences $\sum_k \Delta_k$, while fork's grows close to $N \cdot B$ once collections run. If the measured differences are not small, or if most variants never reconverge, the model predicts no win, and we will say so.

A second, smaller experiment ports the approach to Python under the same interpreter framework. It uses the ten PoTo packages (ansible, bokeh, pygal and others, 3,500 to over 285,000 lines of code) and flips branches that guard dynamic imports and attribute lookups. It measures how many new points-to facts the concrete runs contribute to a PoTo-style solver. This tests whether the gains generalize beyond one language and one vulnerability class.

Finally, we will report a profile of the fraction of exploration time spent in masked lockstep versus detached mode. This profile serves only as evidence for or against a later manycore implementation in the style of MemPool: A Scalable Manycore Architecture With a Low-Latency Shared L1 Memory, not as a claim this proposal makes.