Tackling ML-based Dynamic Mispredictions using Statically Computed Invariants for Attack Surface Reduction

A program carries far more code than any single run uses, and that idle code hands attackers the gadgets they chain into exploits — so debloating disables what a run does not need, and a machine-learning model can predict that tight set very precisely, but when it guesses wrong you cannot tell a harmless misprediction from a real attack; this paper (Georgia Tech, IBM Research — Chris Porter, Sharjeel Khan, Kangqi Ni, Santosh Pande) presents PDSG, which keeps only ML-predicted functions live and, on every misprediction, audits the call history against a statically computed invariant (the ensue relation) to soundly separate mistakes from attacks — cutting most gadgets while triggering that check on just 3.8 percent of predictions.

The argument in one glance

Problem

A program keeps far more code loaded than any run needs, and attackers exploit it

When a program runs, only a fraction of its code actually executes for a given input, yet all of it sits in memory, executable. That idle code is a gift to attackers. Modern exploits often use code-reuse attacks: rather than injecting new code (which defenses block), the attacker finds small snippets of the program's own existing code — gadgets — that each end in a jump or return, and chains them together, using a memory bug to redirect control flow through the chain, to assemble malicious behavior out of legitimate pieces. The more code is live and reachable, the more gadgets are available, and the easier the attack. Program debloating fights this by removing or disabling the code a run does not need, shrinking the attack surface so fewer gadgets exist to chain. A powerful form does this dynamically: keep functions disabled (non-executable) and enable them only just before they are actually called, so at any instant only the currently-needed functions are live and everything else, if an attacker jumps to it, simply faults. The question that decides how well this works is: how tightly can you predict which functions will be needed, and how do you stay safe when the prediction is wrong?
What people did

Predict the needed functions from the static callgraph, or from a machine-learning model

Two prediction strategies exist. Static approaches (like Decker) analyze the program's callgraph ahead of time to compute, at each point, the set of functions statically reachable from there, and enable exactly that set at runtime. Machine-learning approaches (like BlankIt) instead train a model on profiling runs to predict, from the current calling context, the specific set of functions that will actually be called next — a much tighter, input-sensitive prediction. The ML route is attractive because its predictions can be far more precise than the conservative static reachable set, so it leaves far fewer functions live and far fewer gadgets available.
Why it fell short

Static prediction is too loose; ML is precise but cannot tell a misprediction from an attack

Each strategy has a fatal gap. Static callgraph prediction is sound — it never wrongly disables a function that could legitimately be called — but it is conservative: it must keep active every function reachable in principle, including rare error handlers and, crucially, code an attacker wants to reach, even when the current run will almost never call them. So the attack surface stays larger than it needs to be. Machine learning fixes the precision problem, predicting the tight set that will really be used, but it introduces a worse one: ML gives no guarantees, so it sometimes mispredicts — a function that genuinely needs to run was not in the predicted set, so it was disabled, and calling it faults. Now the system faces an unanswerable question: is this off-prediction call a benign misprediction, or an attacker redirecting control flow? You cannot simply block it (that would break the program on every honest misprediction) nor simply allow it (that would wave attacks through). Prior ML work (BlankIt) only handled infrequent library calls and resolved mispredictions with a heavy audit thread; applied to whole-program application code, where mispredictions are frequent, that means constant costly interruptions. What was missing was a lightweight, sound way to tell mispredictions and attacks apart.
This paper's idea

Keep only ML-predicted code live, and audit every misprediction against a static invariant

PDSG (Predictive Debloat with Static Guarantees) combines the precision of ML with the soundness of static analysis. At runtime it enables only the functions an ML model predicts will be called next — the predicted sub-callgraph, always a subset of the statically reachable set — so the live attack surface, and the gadgets in it, are minimized (the paper reports reducing gadgets active at runtime by 97.8 percent, and 82.5 percent of total gadgets on SPEC CPU 2017, the highest among comparable techniques). The novelty is how it handles the model's inevitable mispredictions. Offline, PDSG computes a static invariant it calls the ensue relation: ensue(i, j) holds when the function called at one callsite can legally immediately follow the function called at another under some valid execution — a sound description, derived from the callgraph and control flow, of which function-to-function transitions are ever possible. It computes this by capturing seven static program properties and composing them in a Datalog solver, and keeps the relations in memory. When a misprediction occurs (control flows outside the predicted set), PDSG runs a lightweight audit: it checks that the traced sequence of executed functions is a valid chain of ensue relations. If every adjacent pair conforms, the misprediction is legitimate and execution continues; if any pair is an impossible transition, PDSG has caught an attack (or bug) and can alert or exit. In experiments this check triggers on only 3.8 percent of predictions on SPEC, with runtime overhead of 7.5 percent on SPEC and 3 percent on real-world applications.

Why this problem is worth solving

Attack surface is not an abstraction — it is literally the amount of the program’s own code an attacker can turn against it, and shrinking it directly weakens exploits.

A running program is mostly latent: for any given input, huge portions of its code never execute, yet remain loaded and executable in memory. This matters because of how modern attacks work. Defenses have made it hard to inject and run new code, so attackers instead reuse the code already present. In a code-reuse attack such as return-oriented programming, the attacker locates gadgets — short instruction sequences ending in a return or jump — scattered throughout the program’s existing code, and uses a memory vulnerability to hijack control flow and chain gadgets together into an exploit, all from legitimate instructions. The supply of gadgets grows with how much code is live and reachable, so every function that is loaded-but-unneeded is extra ammunition. Debloating attacks this directly: if the program keeps unneeded functions disabled and only enables what a run actually requires, the pool of usable gadgets shrinks dramatically, and any attempt to jump into disabled code faults instead of executing. Because the reduction is measured in how many gadgets an attacker has to work with, a tighter prediction of what to keep live translates straight into a harder attack. That is why the precision of the prediction is the whole game, and why it is worth doing well.

The deeper obstacle is a mismatch between what machine learning offers and what security requires, and resolving it is the paper’s real contribution.

Machine learning is appealing here precisely because it is more precise than static analysis: it can predict the tight, input-specific set of functions a run will use, keeping far less code live. But security demands guarantees, and ML offers none — it will sometimes be wrong. The consequence is a dilemma unique to using prediction for defense. When execution tries to enter a function the model did not predict, that event is ambiguous: either the model simply mispredicted and the program legitimately needs that function, or an attacker is redirecting control flow into disabled code. A purely ML system cannot tell these apart, and both naive responses fail — blocking every unpredicted call would crash the program on ordinary mispredictions, while allowing them would defeat the whole defense. This is why earlier ML-based debloating was confined to infrequent library calls and leaned on expensive re-execution audits that do not scale to frequent, whole-program mispredictions. The insight that unlocks the problem is that soundness and precision can be separated and combined: let the ML model provide precision, deciding what to keep live, and let a soundly-computed static invariant provide the guarantee, deciding whether an off-prediction transition was ever legal. The invariant does not need to be precise about what will happen, only sound about what possibly can — so it can serve as an incorruptible referee for the model’s mistakes. Getting that division of labor right is what finally makes ML-based debloating safe.

What people did before, and where it broke

Static callgraph debloating (Decker). Compute the statically reachable function set at each point and enable exactly that set at runtime. Where it broke. It is sound but conservative — it must keep every reachable function live, including rarely-used handlers and attacker-desired code, so the attack surface stays larger than necessary.
ML-based prediction for library calls (BlankIt). Train a model to predict the next set of calls from context, applied to library code. Where it broke. It only handled relatively infrequent library calls, and resolved mispredictions with a heavy parallel audit (re-running under a memory checker), which does not scale to frequent whole-program application mispredictions.
Blocking any off-prediction call. Treat every function call outside the ML prediction as an attack. Where it broke. Mispredictions are normal for a precise model, so this would crash honest programs constantly.
Allowing off-prediction calls. Let unpredicted calls through to avoid breaking the program. Where it broke. This lets an attacker’s control-flow redirection through as well, defeating the defense.
The gap. No approach paired the precision of ML prediction with a lightweight, sound mechanism to decide, on each misprediction, whether the transition was ever legal — leaving ML-based debloating either unsafe or impractically slow.

How PDSG works

From loose static debloating to precise ML debloating with a sound audit

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

The idea

Shrink the attack surface by disabling the code a run does not need. PDSG keeps functions non-executable until they are needed, so only live, predicted code can be used as gadget material. Reducing what an attacker can exploit by mapping in only the code actually required at each moment, rather than leaving the whole program executable, is the same attack-surface-reduction idea the work on attack surface reduction via on-demand code mapping (Decker) covered elsewhere on this site is built on, enabling code just in time to minimize exposure. PDSG takes that on-demand mapping and drives it with a far more precise predictor, so even less code is ever live.

Let a learned model make the precise prediction a rigid rule cannot. Rather than a conservative static rule, PDSG uses a machine-learning model trained on real behavior to predict the tight, context-specific set of functions coming next. Replacing a rigid, worst-case heuristic with a learned model that predicts actual behavior from observed patterns, to act more precisely than a fixed rule allows, is the same learning-based-prediction idea the work on a learning-based flash translation layer (LeafTL) covered elsewhere on this site is built on, learning the behavior instead of assuming the worst. PDSG applies learned prediction to control flow, where the tighter the prediction, the fewer gadgets stay live.

Compute a sound static invariant to referee the model’s mistakes. PDSG derives the ensue relation offline — a sound over-approximation of which function transitions are ever legal — and uses it to validate every misprediction. Computing precise, sound static invariants about a program’s possible behaviors, and relying on them as a trustworthy foundation, is the same invariant-guided static-analysis approach the work on precise invariant-guided pointer analysis (Kaleidoscope) covered elsewhere on this site takes, establishing what the program can possibly do independent of any run. PDSG turns such an invariant into a runtime referee: the model decides what is likely, the invariant decides what is possible, and only their combination is both precise and safe.

Following a misprediction through PDSG

From an unpredicted function call to a verdict of mistake or attack

A trace, drawn from the paper, of how PDSG handles a call that falls outside the model's prediction during a release run.

Step 1 of 5

The model enables a predicted region of code

At a decision point in the callgraph, PDSG's model predicts the set of functions about to execute (the predicted sub-callgraph) and marks just those executable, leaving the rest of the program read-only and inert.

This predicted set is always a subset of the statically reachable set.

Why it works

Precise prediction keeps fewer gadgets live. A conservative static set leaves too much code executable → but an ML model predicts the tight set actually needed → so the live attack surface, and its gadgets, shrink far more.
Disabled code faults instead of executing. Attackers reuse whatever code is live → but marking unpredicted functions read-only → so a redirected jump into them crashes rather than running a gadget.
A sound invariant referees every misprediction. Off-prediction calls are ambiguous between mistake and attack → but checking them against the ensue relation of legal transitions → so legitimate mispredictions pass and impossible transitions are caught.
Separating soundness from precision beats needing both at once. No single predictor is both tight and guaranteed → but pairing a precise model with a sound static invariant → so precision comes from the model and safety from the invariant.
The audit is rare and cheap enough to be practical. Re-running code to validate every misprediction is too slow → but a lightweight table lookup on the 3.8 percent of predictions that miss → so overhead stays around a few percent.

What it costs (trade-offs and scope)

The invariant is sound but not precise. The ensue relation over-approximates legal transitions, so an attack that only ever follows individually-legal function transitions would satisfy the check; it guarantees illegal transitions are caught, not that every attack is, so it is one layer of a defense, not a complete control-flow-integrity solution.
It needs representative profiling to train the model. The precision of the ML prediction depends on training data that reflects real usage; behavior far outside the profiled inputs would raise the misprediction rate and thus the audit cost.
Runtime overhead is real, if modest. Enabling and disabling code, tracing calls, and auditing mispredictions cost 7.5 percent on SPEC and 3 percent on real-world applications in the paper’s measurements — small, but not free.
It requires source and a full toolchain. PDSG is built from LLVM compiler passes, offline Datalog analysis, and a runtime library, so it applies to applications one can rebuild through its pipeline, not arbitrary binaries.
Coverage varies with application complexity. The paper reports the audit triggering on 3.8 percent of predictions on SPEC but higher on some application classes, so the practical cost depends on how predictable a given program’s control flow is.

The comparison

Predicting what code to keep live for debloating

Property	Static callgraph (Decker)	ML for library calls (BlankIt)	PDSG
Prediction precision
Scope of code covered
Handling mispredictions
Distinguishes attack from mistake
Reported outcome

A comparison of ways to predict which code to keep executable for debloating. Static callgraph analysis (Decker) is sound but conservative, keeping too much code live; ML prediction (BlankIt) is precise but was limited to library calls and used a heavy re-execution audit for mispredictions. PDSG predicts the tight callee set for whole-program application code with an ML model, and validates each misprediction against the statically computed ensue relation to soundly separate mistakes from attacks — cutting 82.5 percent of total gadgets and 97.8 percent of runtime-active gadgets on SPEC CPU 2017 while triggering its audit on only 3.8 percent of predictions, at 7.5 percent overhead. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text via the authors’ arXiv preprint (2404.00196, “Combined Static Analysis and Machine Learning Prediction for Application Debloating”), which presents the same system, PDSG (Predictive Debloat with Static Guarantees), as the ASPLOS 2025 paper “Tackling ML-based Dynamic Mispredictions using Statically Computed Invariants for Attack Surface Reduction” by the same authors. The described system is the paper’s: PDSG dynamically debloats application code by enabling only the functions an ML model predicts will be called (the predicted sub-callgraph, always a subset of the statically reachable set) and marking the rest non-executable, then resolving each misprediction with a lightweight audit against a statically computed invariant — the ensue relation, ensue(i, j), capturing which function-to-function transitions are legal under some execution, computed offline from seven static program properties in a Datalog solver and checked at runtime by verifying the traced call history is a valid chain of ensue relations. The reported results — reducing 82.5 percent of total gadgets and 97.8 percent of gadgets active at runtime on SPEC CPU 2017 (the highest among comparable techniques), triggering misprediction checks on only 3.8 percent of predictions on SPEC, and runtime overhead of 7.5 percent on SPEC and 3 percent on real-world applications — are from the paper’s evaluation; the ASPLOS abstract additionally frames the gadget reduction as roughly 90 percent of code-reuse gadgets and cites misprediction-check trigger rates of 3.8 percent, 16 percent, and 2.3 percent for SPEC and low- and high-complexity applications. The ensue relation is a sound but over-approximate invariant, so PDSG is a strong attack-surface-reduction layer rather than a complete control-flow-integrity guarantee. Background on code-reuse attacks, gadgets, debloating, and Datalog is standard context. The step-by-step walkthrough illustrates the described mechanism. Exact algorithms and full results should be read from the paper.

Background

Why defense keeps shrinking what an attacker can reach

It helps to see PDSG within the long arms race over control-flow attacks. Once defenses made injecting new code impractical, attackers turned to reusing the program’s own code, chaining gadgets to build exploits from legitimate instructions. Defenders responded with a family of techniques aimed at limiting what code an attacker can reach or reuse — control-flow integrity that restricts where jumps may land, memory-safety mechanisms that prevent the corruptions used to hijack control, and debloating that removes or disables unneeded code so fewer gadgets exist at all. The recurring theme is that the size and reachability of a program’s live code is itself a security parameter, and squeezing it makes every exploit harder to assemble. The recurring tension is precision versus soundness: the tighter you try to constrain the program, the more you risk breaking legitimate behavior, so the best designs find a way to be both aggressive and safe. This drive to blunt exploits by tightly limiting the code and state an attacker can turn against a program is the same terrain the work on drop-in use-after-free prevention (Minesweeper) covered elsewhere on this site occupies, closing off the memory-corruption avenues attacks depend on. PDSG’s particular contribution is to let an imprecise-but-precise machine-learning predictor drive aggressive debloating while a sound static invariant guards against the mistakes, so the defense can be both tight and trustworthy.

If you remember only three things

1. A program keeps far more code live and executable than any single run uses, and that idle code supplies the gadgets attackers chain into code-reuse exploits — so debloating, which disables the code a run does not need, shrinks the attack surface and makes exploits harder to build. The precision of predicting what to keep live is decisive: static callgraph analysis is sound but conservative, keeping too much code (including attacker-desired functions) active, while a machine-learning model can predict the tight, context-specific set of functions actually needed. But ML gives no guarantees, so when a call falls outside its prediction, there is no sound way to tell a benign misprediction from an attacker redirecting control flow — and blocking every such call would crash honest programs while allowing them would defeat the defense.
2. PDSG (Predictive Debloat with Static Guarantees) combines ML precision with static soundness. At runtime it enables only the functions its model predicts (the predicted sub-callgraph, always within the statically reachable set) and marks the rest non-executable, so the live gadget pool is minimized and any jump into disabled code faults. To handle mispredictions, it computes offline a sound static invariant, the ensue relation — ensue(i, j) captures which function-to-function transitions are ever legal, derived from the callgraph and control flow via seven static properties composed in a Datalog solver. On each misprediction it runs a lightweight audit, verifying the traced call history is a valid chain of ensue relations: if every transition is possible, it is a legitimate mistake and execution continues; if any is impossible, an attack (or bug) is caught. The model decides what is likely; the invariant decides what is possible.
3. This separation of concerns — precision from the model, safety from the sound invariant — is what finally makes ML-based whole-program debloating practical, where prior ML work was confined to infrequent library calls with heavy re-execution audits. On SPEC CPU 2017, PDSG reduces 82.5 percent of total gadgets and 97.8 percent of gadgets active at runtime (the highest among comparable techniques), while its audit triggers on only 3.8 percent of predictions, at 7.5 percent runtime overhead on SPEC and 3 percent on real-world applications. The trade-offs: the ensue invariant is sound but over-approximate, so PDSG is a strong attack-surface-reduction layer rather than a complete control-flow-integrity guarantee; it needs representative profiling and a full LLVM-plus-Datalog toolchain; and its audit cost rises for programs with less predictable control flow.

Check yourself

Check your understanding

1. Why does the amount of live code in a program matter for security?
2. What dilemma does using a machine-learning predictor for debloating create?
3. What is the ensue relation, and how does PDSG use it?
4. How does PDSG combine precision and soundness, and what did it achieve?

Sources

The paper is “Tackling ML-based Dynamic Mispredictions using Statically Computed Invariants for Attack Surface Reduction” by Chris Porter, Sharjeel Khan, Kangqi Ni, and Santosh Pande (Georgia Institute of Technology; Chris Porter now at IBM Research), published at ASPLOS 2025, DOI 10.1145/3676641.3716276.

This explainer is written from the authors’ arXiv preprint (2404.00196, “Combined Static Analysis and Machine Learning Prediction for Application Debloating”), which presents the same system — PDSG, Predictive Debloat with Static Guarantees — as the ASPLOS 2025 paper. PDSG dynamically debloats application code by enabling only the functions an ML model predicts will be called and marking the rest non-executable, minimizing the live gadget pool; and it resolves mispredictions with a lightweight audit against a statically computed invariant, the ensue relation (which function-to-function transitions are legal under some execution), computed offline from seven static program properties in a Datalog solver and checked at runtime. Evaluated on SPEC CPU 2017, the paper reports reducing 82.5 percent of total gadgets and 97.8 percent of runtime-active gadgets (the highest among comparable techniques), triggering misprediction checks on only 3.8 percent of predictions, and runtime overhead of 7.5 percent on SPEC and 3 percent on real-world applications; the ASPLOS abstract additionally cites roughly 90 percent code-reuse gadget reduction and trigger rates of 3.8 percent, 16 percent, and 2.3 percent across SPEC and low- and high-complexity applications. The ensue relation is a sound but over-approximate invariant, so PDSG is an attack-surface-reduction layer, not a complete control-flow-integrity guarantee. Background on code-reuse attacks, gadgets, debloating, and Datalog is standard context. The numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.