When a deployed classifier turns someone down for a loan, a job, or parole, the operator may have to offer algorithmic recourse: the smallest change to that person's features that would flip the decision — "raise savings by \$5,000 and reapply." This proposal treats the pattern of these "what would it take?" answers as a security audit channel. The premise comes from the transparency–security tradeoff: every recourse answer leaks information about the model's internal geometry, and attackers already exploit that leak to steal models — querying a classifier's recourse API yields 93% extraction fidelity with only 300 queries on the Adult dataset Classifier Reconstruction Through Counterfactual-Aware Wasserstein Prototypes. We propose turning the leak around and pointing it at a different adversary.
A backdoor, or neural Trojan, is a hidden behavior planted during training: the model performs normally on ordinary inputs but switches to an attacker-chosen output when a specific trigger pattern appears Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks. Backdoors evade pre-deployment audits precisely because clean accuracy is untouched. Our core observation is geometric: a backdoor is, among other things, a cheap and over-confident shortcut into one class. Recourse search hunts for the cheapest path into each class — indeed, counterfactual search and boundary attacks are provably near-identical operations Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis — so it should find that shortcut even when accuracy audits cannot. The proximity–robustness tradeoff, normally studied as a user-burden problem, becomes our measuring instrument: in a benign model, pushing a recommendation deeper into the favorable region so it survives noise and retraining costs a "reliability premium" Robust Counterfactual Explanations for Tree-Based Ensembles, and genuinely natural feature changes are systematically more expensive than adversarial ones Towards Non-Adversarial Algorithmic Recourse. A backdoor offers depth almost for free. That anomaly is the signal.
Core Claim
A black-box, query-only audit can detect backdoors in a deployed classifier by comparing its per-class recourse cost–robustness frontier against a reference band built from shadow models retrained on the same data. Formally, for audited model $f$ and class $c$, let
$$\rho_f^{(c)}(r) \;=\; \min_{x'}\; d(x, x') \quad \text{s.t. } f(x') = c \text{ and } \mathrm{IR}(x') \le r,$$
where $d$ is the feature-change cost the user must exert and $\mathrm{IR}(x')$ is the invalidation rate — the probability that noise or retraining pushes $x'$ back out of class $c$, the quantity PROBE computes in closed form under Gaussian perturbations Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse. In benign models $\rho^{(c)}$ rises smoothly as the robustness demand tightens (smaller $r$); PROBE's own results show standard recourses fail at 50–60% under noise unless one pays for margin, and robustness costs up to 3× more than the cheapest adversarial-style recourses. We claim a backdoor into class $c^\ast$ collapses $\rho^{(c^\ast)}$: the trigger basin is deep, flat, and over-confident — Trojaned inputs sit at near-zero prediction entropy STRIP: A Defence Against Trojan Attacks on Deep Neural Networks — so a tiny, off-manifold feature change achieves very low invalidation. No clean model in the reference family produces that collapse. As a bonus, the counterfactual the search returns in the anomalous class is itself a candidate trigger, recovered without ever observing a triggered input.
This differs from the closest existing work in kind, not degree. TrinityAI detects Trojans with "counterfactual attributions" — white-box gradient attributions evaluated toward unchosen output labels on clean inputs, exposing dormant "ghost neurons" Detecting Trojaned DNNs Using Counterfactual Attributions]. It needs weight access; we need only the query interface that transparency regulation already forces operators to expose. XGBD likewise uses explanations defensively, but only for graph topology and only on training data the defender controls XGBD: Explanation-Guided Graph Backdoor Detection. Gayathri et al. show explanations can help attackers place backdoors Adversarial Training for Mitigating Insider-Driven XAI-Based Backdoor Attacks; we show the same information channel helps auditors find them. Nobody, per our search of this literature, has connected input-space recourse cost, its robustness frontier, and backdoor presence at all.
Research Program
The program has three parts. First, a formal characterization: under what conditions does a backdoor necessarily bend $\rho^{(c)}$? The relevant tension is that poisoning isolates malicious behavior in dormant circuits, which raises the real technical risk that first-order recourse search from clean inputs never sees the shortcut. TrinityAI's own ghost-neuron findings suggest dormancy is incomplete — gradients toward the target class do excite the Trojan circuitry — but we treat this as an open empirical question, not an assumption. Second, we build RecourseAudit on top of existing tooling: CARLA's eleven recourse generators for the cost measurements CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms, RobustX's robustness evaluators for the frontier sweep RobustX: Robust Counterfactual Explanations Made Easy, and a shadow-model reference band that captures benign model multiplicity — the Rashomon effect that many near-optimal models disagree internally ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets]. The reference band matters because it separates "this model is unusual" from "this model is unusually cheap and deep in one class," which retraining variance alone cannot explain. Third, an adaptive attacker: a poisoning objective that adds a search-evasiveness penalty, trading trigger discoverability against attack success and clean accuracy.
A secondary question falls out for free and we will answer it along the way: do backdoors silently invalidate certified recourse guarantees? ElliCE derives robustness from a local Hessian ellipsoid; a Trojan's sharp, localized curvature distortion sits exactly where that approximation is weakest, so a Trojaned model may report near-100% validity while steering users toward the trigger zone. The audit doubles as a stress test of robust recourse under poisoning, a setting the robustness literature has never considered — it studies benign retraining shifts Towards Robust and Reliable Algorithmic Recourse, never adversarial ones.
Baselines
The do-nothing reference point is the standard pre-deployment clean-accuracy audit. It should sit at chance: TrojFair models pass clean audits with under 0.44% accuracy loss TrojFair: Trojan Fairness Attacks], and the spare-capacity argument says dormant circuits never touch clean validation data Fine-Pruning. We will quantify this to confirm the threat is live.
The cheapest black-box competitor is random perturbation probing in the spirit of STRIP, which blends an input with heavy noise and reads out prediction entropy STRIP. STRIP reports 0% false acceptance and 0% false rejection rates on CIFAR10 and GTSRB at 1.32× latency, but its own authors concede partial backdoors remain unsolved, and linear superimposition is meaningless on tabular features. We port it faithfully where its mechanics transfer and run a pure random-query variant everywhere, giving it the same query budget as RecourseAudit. Beating it means higher detection AUROC at equal queries, especially on partial and subgroup-gated backdoors.
The strongest existing detector is TrinityAI's white-box counterfactual-attribution pipeline Detecting Trojaned DNNs Using Counterfactual Attributions, which reports a 10% AUC improvement over Cassandra and Neural Cleanse on the IARPA/NIST TrojAI benchmarks (no absolute AUC value found on Lacuna). We run it in its home white-box setting on identical poisoned populations, and also in the query-only setting where it structurally cannot operate. Beating it means matching its white-box AUROC while remaining the only method that works through a recourse API. A composite competitor is extract-then-audit: reconstruct the model with counterfactual-anchored Wasserstein prototypes Classifier Reconstruction Through Counterfactual-Aware Wasserstein Prototypes, then run Neural Cleanse or fine-pruning on the surrogate; we give it the same query budget and compare at 300 queries, where the extraction stage alone reaches 93% fidelity on Adult. Finally, an ablation isolates our key ingredient: the same audit using only unconstrained Wachter-style cost z-scores, without the manifold-constrained generator and without the robustness sweep. If the frontier adds nothing over raw cost, the core claim is wrong and we will say so.
Why not just…?
Why not just probe with random noise instead of running recourse optimization? Random probing is cheap and black-box, and we include it. But it samples the input space blindly, while a structured trigger occupies a tiny, low-measure region; the probability a random tabular query hits a rare-value combination is negligible, whereas gradient-guided counterfactual search actively optimizes toward whatever basin the model makes easiest to reach. The STRIP authors' own admission that partial, source-class-conditioned backdoors defeat invariant entropy filtering STRIP reinforces this: their signal comes from what noise does to the model, ours from what the model invites. Experiment 1 settles it directly — if random probing matches RecourseAudit's AUROC at equal budgets, our mechanism story is wrong.
Why not just use white-box detectors, since a deployer auditing its own model has weight access? For the deployer, that is fair, and TrinityAI is a real threat to our contribution in that setting — we may lose the white-box comparison, and we report that honestly if so. But the constituency this proposal serves is the external auditor or regulator facing only an API, which is exactly the situation transparency mandates create Explanation Hacking: The perils of algorithmic recourse]. Prevention-side answers also fall short here: adversarial training hardens against small input noise, not dormant circuits Detecting Trojaned DNNs Using Counterfactual Attributions], inflates user recourse costs Towards Non-Adversarial Algorithmic Recourse, and even the tailored CWGAN-GP defense still paid a 0.038 precision loss Adversarial Training for Mitigating Insider-Driven XAI-Based Backdoor Attacks. Detection of already-deployed third-party models is a distinct problem, and none of these address it.
Why not just extract the model first and audit the surrogate? This is the alternative we take most seriously, since extraction through recourse queries is demonstrably efficient Classifier Reconstruction Through Counterfactual-Aware Wasserstein Prototypes]. The weakness is that a Trojan circuit is a low-density, poly-semantic feature — precisely what distillation and surrogate fitting tend to smooth away, and Zhao et al. themselves document overfitting fragility in low-query regimes. If the surrogate drops the trigger basin, downstream Neural Cleanse sees a clean model and the pipeline fails silently. We run this pipeline as a baseline at matched budgets; if it matches RecourseAudit, we will report that the simpler recipe wins and our contribution reduces to the frontier diagnostic's interpretability (candidate trigger recovery), which the extract-then-audit path cannot provide.
Decisive Experiments
Experiment 1 establishes the signature on tabular recourse benchmarks — Adult, COMPAS, German Credit, Give Me Some Credit, and HELOC — with label-consistent poisoning at ratios down to the 5% level where graph backdoor detection has proven feasible XGBD, using rare-categorical-value triggers and, for the hard case, demographic-subgroup gating in the TrojFair style TrojFair, whose triggers fire on target groups with over 88.77% success while clean bias stays near 13%. We measure model-level detection AUROC, per-class localization, and candidate-trigger overlap with the true trigger.
Experiment 2 tests the mechanism itself: we correlate the frontier anomaly with gradient attribution toward the target class on clean inputs — the ghost-neuron signal — across poisoning recipes. If dormant circuits are fully invisible to first-order search, the frontier collapse will not appear, and we will report the negative result together with whichever residual signal (cross-class cost asymmetry under manifold constraints) survives.
Experiment 3 runs the adaptive attacker: poisoning with a search-evasiveness penalty, sweeping the tradeoff between detector AUROC, attack success rate, and clean accuracy. The decisive outcome is a quantified frontier — evasion that preserves a TrojFair-level attack (sub-0.44% clean accuracy loss) must cost substantial detectability, or the proposal's practical value is bounded and we will say exactly where.
Experiment 4 moves to the shared benchmark ground: TrojAI and Triggered-MNIST for a matched white-box comparison against TrinityAI, and ISIC, FairFace, and Fitzpatrick17k for the subgroup-gated regime where entropy-based defenses are known to dilute. Experiment 5 closes with query-budget curves for RecourseAudit against random probing and extract-then-audit, because an audit method is only useful if a regulator can afford to run it.
References
- Classifier Reconstruction Through Counterfactual-Aware Wasserstein Prototypes
- Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks
- Exploring Counterfactual Explanations Through the Lens of Adversarial Examples: A Theoretical and Empirical Analysis
- Robust Counterfactual Explanations for Tree-Based Ensembles
- Towards Non-adversarial Algorithmic Recourse
- Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse
- STRIP: a defence against trojan attacks on deep neural networks
- Detecting Trojaned DNNs Using Counterfactual Attributions
- XGBD: Explanation-Guided Graph Backdoor Detection
- Adversarial Training for Mitigating Insider-Driven XAI-Based Backdoor Attacks
- CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms
- RobustX: Robust Counterfactual Explanations Made Easy
- ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets
- Towards Robust and Reliable Algorithmic Recourse
- TrojFair: Trojan Fairness Attacks
- Explanation Hacking: The perils of algorithmic recourse