Evasion-Robust Detectors at Extreme False Positive Budgets

Security detectors such as malware scanners and intrusion monitors are judged by one number that most adversarial-robustness research never reports: how many attacks they catch when they may falsely flag at most one benign file in ten thousand, or one in a hundred thousand. Robustness research hardens models against an attacker who edits inputs with full knowledge of the defense, and it measures the cost of that hardening as lost clean accuracy. Neither measurement says what happens in the far tail of the benign score distribution, which is where a deployed detector's alarm threshold actually sits. This proposal studies that tail directly. The first question is how much catch rate a hardened detector keeps against a defense-aware attacker when its clean false positive rate is held at $10^{-3}$ to $10^{-5}$. The second is whether a training method built around that operating point can keep more of it.

The core observation is simple, and the literature in this file tends to blur it. In the evasion setting, the attacker only modifies malicious inputs, so the benign stream stays untouched. The clean false positive rate can therefore be controlled with an ordinary held-out benign sample and a finite-sample order-statistic bound, with no robust or adversarial conformal machinery. Everything the adversary can damage sits on the other axis, the true positive rate. So the real trade-off is between how robust the catch rate is and how thin the benign score tail stays under hardening. We propose one-sided adversarial training, which perturbs only malicious training examples. We combine it with a training loss that concentrates on the highest-scoring benign examples, the ones that set the threshold. We test whether this beats symmetric adversarial training and uncertainty-based detectors at fixed extreme false positive budgets on EMBER2018 and SOREL-20M. We also run attack evaluations that are checked for optimizer failure.

Core Claim

The first claim is that the robustness–accuracy trade-off is badly understated when it is reported as clean accuracy or at a 5% clean rejection rate. Symmetric adversarial training pushes some benign examples toward the decision boundary. This thickens the upper tail of benign scores, so the threshold needed for $10^{-4}$ false positives rises, and catch rate on both clean and adversarial malware falls by much more than any change in accuracy or AUC would suggest.

The second claim concerns a detector trained with only the malicious class perturbed and with a loss that focuses on the benign tail. We expect it to reach a higher adversarial true positive rate at a fixed, validly calibrated false positive rate than symmetric adversarial training or uncertainty ensembles. We will say plainly if the gain comes mostly from one-sidedness alone.

Formally, let $s(x)$ be the detector's maliciousness score, let $\Delta(x)$ be the set of edits an attacker can make to malicious input $x$ without breaking its function, and let $t_\alpha$ be the threshold at which clean benign inputs are flagged with probability at most $\alpha$. The quantity we target is

$$ \mathrm{TPR}_{\mathrm{adv}}(\alpha) = \Pr_{x \sim \text{malicious}}\Big[\min_{x' \in \Delta(x)} s(x') > t_\alpha\Big], $$

which is the fraction of malware still caught after the attacker's best edit. The threshold is set on $n$ held-out benign scores. We take $t_\alpha$ to be the $\lceil (1-\alpha)(n+1) \rceil$-th smallest score, which bounds the expected false positive rate by $\alpha$ under exchangeability of benign data alone. A binomial tail bound gives a high-probability version. This form implies $n$ must be much larger than $1/\alpha$, which is why the $10^{-5}$ experiments require SOREL-20M.

Relation to Prior Work

Three lines of work motivate the gap.

Low-false-positive detection work optimizes exactly our operating point but ignores attackers. Leveraging Uncertainty for Improved Static Malware Detection Under Extreme False Positive Constraints uses ensembles and Monte Carlo dropout with validation-tuned thresholds down to $10^{-5}$. It also shows that thresholds tuned on the test set overestimate true positive rate by up to 35%. We reuse its discipline of disjoint validation, but it runs no evasion attacks, and we do. EMBER supplies the dataset and a LightGBM reference, also evaluated only on natural data.

Reject-option robustness work handles attackers but works at loose clean budgets. Adversarial Training with Rectified Rejection trains an auxiliary confidence predictor and reports accuracy when 95% of clean inputs are accepted. Revisiting Adversarial Robustness of Classifiers With a Reject Option trains classifiers that should not reject small perturbations. Towards Calibrated Losses for Adversarial Robust Reject Option Classification derives calibrated non-convex losses for linear models with a symmetric reject cost. All three treat rejection as a symmetric cost in multiclass classification. None operates at $10^{-3}$ clean false positives or below, and none separates the error the attacker controls from the error it cannot.

Adaptive-attack work constrains how we evaluate. Adversarial Examples Are Not Easily Detected broke ten detectors by putting the detector's score into the attack loss, and it asked for results at stringent false positive rates. Indicators of Attack Failure shows that broken attack optimization can inflate robustness from 1% to 95%. These papers are why every robustness number here is paired with optimizer diagnostics.

WARD is the nearest system to combine all three concerns. It co-trains an attacker and a guard for web-agent prompt injection and reports low false alarms. However, it gives no calibrated false positive guarantee and no operating-point curves, and it works on HTML and screenshots rather than feature-vector detectors.

Research Program

We will build detectors on EMBER2018's 2351-dimensional static features and on SOREL-20M. The threat model is problem-space-plausible feature manipulation. The attacker may only increase features that correspond to additive file edits, such as appended bytes, added imports, and added sections, and must leave features tied to the file's function unchanged. We encode this as a constraint set $\Delta(x)$ with per-group budgets.

The main models are feed-forward networks, so white-box gradient attacks apply. Gradient-boosted trees are attacked by transfer and by query-based search, so the comparison with the industry-standard model family stays honest.

The method has two ingredients. The first is one-sided adversarial training, where inner maximization is applied only to malicious training examples. The second is a tail-focused benign loss, which on each batch upweights the benign examples whose scores fall in the top fraction around the target budget. This is a smooth surrogate for pushing down the benign quantile that fixes $t_\alpha$, related in spirit to partial-AUC objectives. Thresholds are always set on a disjoint benign calibration split. We report both the empirical false positive rate and its binomial upper confidence bound.

The analysis has three parts. First, we measure the full adversarial and clean true-positive curves from $10^{-2}$ to $10^{-5}$ for every model and attack budget. Second, we measure how each hardening method changes the benign score tail, using the calibrated threshold and the tail's empirical quantiles. Third, we examine a separate availability threat, in which an attacker crafts benign-functioning files to trigger alarms. This is the one case where the false positive guarantee can break, and we quantify it rather than assume it away.

A small secondary study on CIFAR-10 adversarial-example detection lets us place the method against Rectified Rejection on its home benchmark. With only 10k clean test images, it is limited to $10^{-3}$.

Baselines

The naive reference is an unhardened detector: a standard EMBER LightGBM model and an equally sized feed-forward network trained with cross-entropy, with thresholds set on the calibration split. On clean data, EMBER reports a 93% detection rate at 0.1% FPR and an AUC of 0.999. We expect this model's adversarial detection rate under our attack to collapse, and that collapse is the gap to be closed.

The strongest low-false-positive competitor is the uncertainty ensemble of Leveraging Uncertainty for Improved Static Malware Detection Under Extreme False Positive Constraints. It reports TPR at FPR $10^{-5}$ on SOREL-20M improving from 0.69 to 0.80. We reimplement it on identical splits and attack the whole ensemble jointly, including its uncertainty-aware threshold, following the joint-loss recipe of Adversarial Examples Are Not Easily Detected.

The strongest robustness competitor is symmetric adversarial training on the same constraint set. This is the natural thing a reviewer would expect to work. Where it applies, we add Rectified Rejection's coupled confidence test, with any flagged or rejected input counted as an alarm. On CIFAR-10, the reported reference is roughly 58% accuracy at TPR-95 under PGD-100 (Adversarial Training with Rectified Rejection). No reported result was found on Lacuna for Rectified Rejection or SATR at clean false positive rates of $10^{-3}$ or below, or on malware features.

Fairness conditions are as follows. All methods share architecture, training data, the calibration split, epoch budget, and a matched hyperparameter search of equal trial count. All are attacked with the same adaptive attack at the same budget.

Two ablations isolate the proposal's ingredients. One-sided adversarial training without the tail loss isolates one-sidedness. The tail loss without adversarial training isolates tail focus.

The method counts as beating the baselines only if its adversarial true positive rate at $10^{-4}$ on EMBER and $10^{-5}$ on SOREL exceeds both the uncertainty ensemble and symmetric adversarial training. The margin must exceed the across-seed spread. Its calibrated false positive upper bound must stay within budget, and its clean true positive rate must not fall more than a few points below the unhardened reference.

Why not just…?

Why not just run symmetric adversarial training and recalibrate the threshold? This is the most serious threat, because recalibration alone restores the false positive guarantee. The question is purely whether the recalibrated threshold sits so high that catch rate suffers. The evidence that hardening harms rare benign inputs comes from nearby settings. Training set cleansing of backdoor poisoning by self-supervised representation learning finds that defenses reject rare benign samples, and robust training ceilings are documented in Adversarial Training with Rectified Rejection. None of that has been measured at $10^{-4}$. If recalibrated symmetric training matches our method, the proposal's contribution shrinks to the measurement study, and we will report it that way.

Why not just use the uncertainty ensemble, since it already wins at extreme budgets? Ensemble disagreement and dropout variance are among the signals that Adversarial Examples Are Not Easily Detected showed an attacker can optimize against. The Direction 1 evidence for the ensemble is on natural data only. The joint white-box and transfer attack on the ensemble will settle this directly.

Why not just apply adversarially robust conformal prediction to guarantee the false positive rate? Under evasion, the benign calibration data remain exchangeable with benign test data. The plain order-statistic threshold is therefore already valid, and robust conformal methods would only add conservatism. Where exchangeability truly fails, namely attacker-crafted benign files, we measure the violation explicitly in the availability experiment instead of paying for worst-case guarantees everywhere.

Why not just add a reject option as in SATR or Rectified Rejection? In a detector, rejecting an input sends it to an analyst, so it costs the same as an alarm. Those methods tune rejection against a symmetric cost at a 5% clean budget. We include Rectified Rejection with rejections counted as alarms, so the curves show whether its coupled test survives at extreme budgets.

Decisive Checks

Every robustness number must pass the diagnostics in pralab/IndicatorsOfAttackFailure. It must also pass an unbounded-budget sanity check that drives adversarial detection toward zero, and a cross-check against transfer and query attacks for the tree models. A method that looks robust only because its gradients are uninformative is disqualified.

The central test is the adversarial true-positive curve from $10^{-2}$ to $10^{-5}$ for all models at matched calibrated false positive bounds. Three outcomes are decisive. If the gap between symmetric and one-sided training widens as $\alpha$ shrinks, that confirms the tail-thickening mechanism. If there is no gap, the trade-off is not tail-specific and the method's premise fails. If the uncertainty ensemble's advantage vanishes under joint attack, the low-false-positive literature's best tool does not survive an adaptive attacker.

A final check measures the benign score quantiles near $t_\alpha$ before and after each hardening method, to show directly whether the benign tail moved as predicted.