Schema Rotation as a Moving-Target Defense against Explanation-Guided Extraction

Machine-learning services are caught in a squeeze. On one side, regulation and users demand explanations: feature attributions, counterfactuals, and recourse recommendations are increasingly mandatory rather than optional. On the other side, every explanation is a leak. The Tree Reconstruction Attack (TRA) shows that counterfactual explanations reveal exact split thresholds of tree ensembles, letting an adversary clone a random forest with 100% functional equivalence using a query budget that scales sub-linearly in the number of nodes From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks. Meanwhile, a separate line of work on streaming data has developed algorithms that keep predictors accurate while the feature space itself changes — sensors fail, new metrics come online, and the model's input schema evolves rather than staying fixed Learning with Feature Evolvable Streams, Online Learning from Capricious Data Streams: A Generative Approach. These two literatures have never met. This proposal argues their meeting point is productive in both directions: the security problem supplies a new reason to rotate feature spaces online, and the streaming machinery supplies the missing ingredient that makes rotation survivable for accuracy.

The core idea in plain language: an extraction attack works by patiently probing a model that stands still. If the service periodically retires part of its input feature set and replaces it with a new one — while using feature-evolvable learning to transfer its knowledge across the swap so predictions stay accurate — then every split threshold the attacker has discovered becomes obsolete the moment the schema changes. The attacker must restart extraction from scratch against each transient model. If the service rotates faster than the attacker can complete extraction, the attack never converges. Crucially, the defense does not lie: at every moment the API returns truthful explanations of the currently deployed model. Transparency is preserved per-query; what is denied is the persistence of any single stealable model.

Core Claim

The claim is that periodic online feature-space rotation, driven by security-aware feature selection, degrades explanation-guided model extraction from perfect to bounded, at a predictable and controllable cost in streaming accuracy. Formally, let $Q^*(M)$ be the query complexity of extracting model $M$ (for TRA against a forest, $\Theta(\text{Nodes}^{0.38})$ From Counterfactuals to Trees), and let $T$ be the number of queries a schema stays live before rotation. Then any attack accrues at most $\min(T, Q^*)$ useful queries against each transient model, and we conjecture a provable bound: extraction fidelity against the live service falls to the fidelity achievable with $\min(T, Q^*)$ queries, regardless of total budget spent. The defender's cost side is equally concrete: each rotation incurs a transition cost in cumulative streaming loss governed by the quality of the cross-space mapping, so the total regret over $K$ rotations grows with $K$ times the per-transition mapping error. The scientific deliverable is the characterization of this tradeoff curve — extraction fidelity as a function of rotation rate and mapping quality — which no existing work provides.

The key design question is which features to swap. Not all rotations cost the same: swapping a feature whose values are well predicted from the surviving features (low reconstruction error under a FESL-style mapping Learning with Feature Evolvable Streams) costs little accuracy, because the replacement schema carries the same information. So the security-aware online feature selector chooses swaps that minimize a combined objective,

$$\min_{\{S_t\}} \; \sum_t \ell\big(f_t(x_t), y_t\big) \; + \; \lambda \sum_t \Phi(S_t),$$

where $S_t$ is the live feature subset at time $t$, $\ell$ is the streaming prediction loss, and $\Phi(S_t)$ measures extraction exposure — concretely, the number of queries the current schema has already been live (its "age"), which is exactly the resource the attacker is accumulating. The selector retires and replaces the cheapest-to-lose high-exposure features before schema age reaches the measured extraction threshold $T_{\max}$. This turns online feature selection from a passive adaptation mechanism into an active defense policy.

What Prior Work Establishes, and What It Leaves Open

Four results motivate the design. First, extraction via explanations is brutally efficient: TRA achieves 100% fidelity on tabular benchmarks, extracting a depth-9 tree on COMPAS in an average of 153 queries against a theoretical worst case of 1,070 From Counterfactuals to Trees; and local counterfactual explanations collapse the query complexity of auditing a linear classifier from $O(\frac{1}{\epsilon}\log\frac{1}{\delta})$ label-only queries to a single query XAudit : A Learning-Theoretic Look at Auditing with Explanations. These attacks constrain the proposal: they assume a stationary target, which is precisely the assumption we break — but they also tell us how cheap extraction is when the assumption holds, which sets the rotation threshold $T_{\max}$.

Second, the streaming side supplies the machinery. FESL learns a linear map from a new feature space to a decommissioned one during an overlap window, preserving accuracy across the swap, with regret guarantees for both its model-combination and model-selection variants Learning with Feature Evolvable Streams; its successor handles asynchronous feature dropout without synchronized transitions Storage Fit Learning with Feature Evolvable Streams; OPFES extends to non-linear kernel mappings in a single pass with no data buffer One-Pass Feature Evolvable Learning with Theoretical Guarantees; and OCDS handles fully capricious appearance and disappearance of features, reaching 91.02% average accuracy where naive online learning that ignores missing features collapses to 65.44% Online Learning from Capricious Data Streams. None of these works considers an adversary; they are the method suppliers here.

Third, the closest existing intersection work does not preempt this proposal. Robust Regression via Online Feature Selection under Adversarial Data Corruption treats security as data poisoning on a fixed feature space — the attacker corrupts input values, not the transparency channel, and the schema never changes. EnsembleSHAP certifies attribution robustness for a random-subspace ensemble but on a fully static, predefined feature pool, and it defends the explanation from manipulation rather than asking whether attributions enable reconstruction of the underlying ensemble EnsembleSHAP: Faithful and Certifiably Robust Attribution for Random Subspace Method. TRA itself frames extraction as an "online discovery" problem, but only the attacker is online; the target is frozen. Our proposal is the inverse: the target moves, and we study what that does to the attacker's competitive bounds.

Fourth, two results shape the honest limits. Counterfactual explanations and adversarial perturbations are structurally near-identical, with Spearman rank correlation between their feature perturbations exceeding 0.90 on tabular benchmarks Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis — so an adaptive attacker may try to transfer boundary knowledge across rotations, and we must test this directly. And providing recourse drives users to change their features, which over 70 retraining rounds pushes decision boundaries upward ("standard creep") Understanding Endogenous Data Drift in Adaptive Models with Recourse-Seeking Users — rotation could accelerate recourse invalidation, and we measure this rather than assume it away.

Research Program

Three components. The first is a formal model of extraction against a non-stationary target: extend TRA's divide-and-conquer analysis to a setting where the feature space and decision boundary change at known-to-defender, unknown-to-attacker intervals, and prove (or refute) the $\min(T, Q^*)$ fidelity bound. The second is the rotation scheduler itself: an online feature selection policy that takes the streaming algorithms above as plug-in transition machinery (FESL-style linear mapping where overlap data exists, OPFES-style kernel mapping where it does not) and chooses which features to retire based on predicted mapping error versus accumulated schema exposure. The third is an adaptive-attacker suite, because the interesting question is not whether the naive TRA fails but whether any attacker can beat the rotation: candidates include a restart attacker (re-extracts after each detected rotation), a parallel attacker (splits budget across schemas), and a transfer attacker that exploits the counterfactual–adversarial equivalence to carry boundary information from one schema to the next Exploring Counterfactual Explanations Through the Lens of Adversarial Examples. The overlap windows used internally for mapping are never exposed through the query interface, so the attacker never sees paired old–new data — but we will test a worst case in which the attacker infers the mapping from correlations in public predictions.

Proposed Experiments

Utility is evaluated on the streaming suites in the literature: the feature-evolvable suite of nine UCI datasets mapped across spaces plus the Reuter multi-view and RFID streams Learning with Feature Evolvable Streams, the 15-dataset capricious suite with IMDB Online Learning from Capricious Data Streams, and the 20-dataset OpenML/UCI one-pass suite scored by cumulative error rate One-Pass Feature Evolvable Learning with Theoretical Guarantees. The headline utility check: rotating at rates that defeat extraction must keep cumulative loss close to the non-rotating streaming baseline; the reference point for how badly naive handling of vanishing features performs is the 65.44% accuracy of naive online learning versus 91.02% for OCDS on the capricious suite.

Security is evaluated on TRA's own benchmarks — Adult, COMPAS, and Credit Default — with the attack run against the live, rotating service. The reference number to beat: TRA reports 100% extraction fidelity, and on COMPAS extracts a depth-9 tree in an average of 153 queries From Counterfactuals to Trees. We sweep the rotation period $T$ from well above to well below the measured per-schema extraction budget and plot extraction fidelity and total queries; the theory predicts fidelity collapses once $T < Q^*$, and the location of the collapse tests the $\min(T, Q^*)$ bound directly. A separate policy-level check asks whether an attacker who archives every partial extraction can approximate the defender's evolving decision policy on future queries — if archive attacks also fail, the defense is stronger than the per-model analysis suggests. Transparency is verified by faithfulness tests on the live explanations (feature-removal label-flip, in the style where EnsembleSHAP reports 98% label flips on IMDb after removing its top-10% attributed words EnsembleSHAP) and by per-explanation latency, which must stay streaming-compatible. Finally, recourse stability under rotation is measured by adapting the 70-round retracking protocol of the endogenous-drift study to a rotating schema Understanding Endogenous Data Drift in Adaptive Models with Recourse-Seeking Users.

Baselines

The naive reference point is a static deployed model with fully truthful explanations and no defense. This is the strongest competitor for the security question precisely because it is what real services do today, and its failure is quantified: TRA extracts it with 100% fidelity, needing an average of 153 queries for a depth-9 COMPAS tree From Counterfactuals to Trees. It will be run on identical data and the same query interface as the rotating service, so the only difference is the rotation policy. Beating it means driving extraction fidelity far below 100% at equal or higher total query cost, while losing at most a few points of streaming accuracy.

The strongest existing defense is XRand, which randomizes top-$k$ feature rankings under a local differential privacy constraint and then solves a per-sample convex optimization to keep explanations close to true attributions XRand: Differentially Private Defense against Explanation-Guided Attacks. It is the competitor to beat because it is the only published mechanism in the corpus that hides explanation content while preserving interpretability, with a reported attack success rate drop from 77.8% to 10.2% on EMBER's LightGBM model at privacy budget $\epsilon = 1.0$ under 1% poisoning. It will be tuned with the same budget on the same tabular benchmarks, and combined with rotation as well as run alone, since the two defenses act on different channels (explanation content versus model persistence). Beating it means achieving comparable or better security against extraction — a threat XRand was not designed for and does not address — at per-query latency compatible with streaming, where its convex optimization loop is a known bottleneck.

The critical ablation isolates the online-learning ingredient: random feature rotation on a fixed schedule with no cross-space mapping, deployed on the same schemas and query budgets. This tests whether the defense comes from rotation alone or from the feature-evolvable machinery that keeps the rotated model accurate; the streaming literature predicts the ablation collapses toward naive handling of missing features, which loses roughly 25 points of accuracy against a generative reconstruction approach on the capricious suite (65.44% versus 91.02%) Online Learning from Capricious Data Streams. A second ablation rotates on a fixed schedule rather than the exposure-aware schedule, isolating the security-aware selection criterion itself.

Why not just…?

Why not just turn off the explanation API? It is the cheapest defense, and it genuinely slows attackers: label-only auditing needs far more queries than explanation-guided auditing — 905 versus roughly 54 on the Credit dataset in one study XAudit — but it does not stop extraction, and the transparency obligation is not optional in regulated domains, a constraint that the extraction literature itself treats as a premise rather than a suggestion From Counterfactuals to Trees. Opacity also has a strategic cost: work on ambiguous disclosure shows that full transparency can be optimal for the system when managed well, and pure black boxes discourage legitimate improvement Ambiguous Strategic Classification. Still, we will report label-only extraction against the rotating service as a head-to-head, because if rotation only helps when explanations are on, its scope is narrower than claimed.

Why not just add differential-privacy noise to the explanations? Uniform noise destroys explanation usefulness before it delivers security — XRand's authors state this explicitly, which is why their mechanism optimizes to stay near true attributions rather than perturbing blindly XRand. XRand itself is a real threat to this proposal's novelty, and we treat it as the primary baseline rather than arguing around it. But it has two structural limits here: it defends against explanation-guided backdoor crafting, not against TRA-style extraction of the model itself, and its per-query convex optimization is incompatible with streaming throughput. The decisive experiment is XRand-plus-static-model versus rotation-plus-truthful-explanations under the TRA attack at matched latency budgets; if XRand matches rotation's extraction defense at acceptable latency, the simpler method should win and we will say so.

Why not just rotate features randomly, without any online learning machinery? This is the most dangerous alternative, because per-query random masking resembles the Random Subspace Method already used for attribution EnsembleSHAP and requires no new theory. The problem is accuracy and auditability: a model randomly masking inputs at query time is effectively a model handling capricious missing features, and the measured cost of that is severe — naive online learning on capricious streams reaches 65.44% accuracy where reconstruction-based methods reach 91.02% Online Learning from Capricious Data Streams — and randomly varying explanations are difficult to present as faithful, auditable disclosures. Periodic rotation with learned mappings keeps one truthful, stable model between rotations. The random-rotation ablation settles this empirically: if its accuracy and faithfulness losses are small, the simpler design wins and the online-learning contribution shrinks to the scheduler.

Decisive Checks

The proposal lives or dies on three measurements. First, the fidelity-versus-rotation-rate curve on TRA's benchmarks must show a sharp collapse near $T = Q^*$, validating the $\min(T, Q^*)$ bound; a smooth, shallow decline would mean rotation is a mere nuisance factor, not a defense. Second, the adaptive transfer attacker must fail to stitch extractions across rotations; if it succeeds, the defense degrades to a query-budget multiplier and the honest conclusion is that rotation buys time, not security. Third, streaming accuracy under extraction-defeating rotation rates must stay within a few points of non-rotating baselines on the capricious and one-pass suites — the tradeoff curve, once mapped, is the paper.