How Many Clean Images Does It Take to Find a Frequency Backdoor?

A backdoored neural network behaves normally until its input carries a secret pattern, the trigger, and then it switches to the attacker's chosen output. A common defense, called trigger inversion, searches for the smallest input change that flips many clean images to one target class. If that change is unusually small, the model is flagged. Frequency-domain attacks hide the trigger in a few Fourier coefficients, the complex numbers that describe an image as a sum of waves. Spread back over the pixels, such a trigger is faint everywhere and concentrated nowhere, and pixel-space inversion misses it. Separately, compressed sensing (recovering a sparse signal from fewer measurements than unknowns) has a known result for complex signals. Each complex entry's real and imaginary parts are zero or nonzero together. A solver that penalizes the two parts as a unit can recover signals up to twice as dense, at the same number of measurements, as a solver that treats them independently.

This note proposes treating frequency-trigger inversion as a sparse recovery problem in which the clean probe images are the measurements. That framing turns two practical questions into measurable phase diagrams: how many clean images a defender needs, and whether tying real and imaginary parts together cuts that number. Defenders are usually short on clean data. If coupled inversion succeeds with roughly half the probes that uncoupled inversion needs, that is a concrete gain. Mapping where the boundary between success and failure sits also gives scanners a principled stopping rule in place of a tuning heuristic.

Core Claim

Linearize the target-class margin $m(x)$ of a network around a clean probe image $x_i$. A Fourier-domain trigger $\Delta \in \mathbb{C}^N$ then changes the margin by $a_i^{\top}\Delta$, where $a_i$ is the input gradient at $x_i$ expressed in the Fourier basis. Stacking $n$ probes gives a complex linear system,

$$ y = A\Delta, \qquad A = [a_1, \dots, a_n]^{\top} \in \mathbb{C}^{n \times N}, $$

with one row per probe and a $k$-sparse unknown. This has exactly the shape analyzed in Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP). That paper solves complex sparse regression with a penalty on the magnitude of each complex entry. It derives exact equations that track the solver's error as the problem grows (state evolution) and shows that, with very few measurements, the complex solver handles signals about twice as dense as real-valued sparse regression. On Phase Transition of Compressed Sensing in the Complex Domain confirms empirically that this complex boundary matches that of block-sparse recovery with blocks of two, across Gaussian, Bernoulli, ternary and Fourier sensing matrices.

The claim is in two parts. First, the probes-versus-sparsity plane for frequency-trigger inversion shows a sharp success/failure boundary. Second, coupling the real and imaginary parts of each coefficient, together with its conjugate partner (a real image's spectrum is conjugate-symmetric), moves that boundary toward fewer probes, by up to a factor of two in the probe-scarce regime. Inversion itself still runs on the full nonlinear network. The linear model serves only to predict where the boundary should fall and how large the gain should be. Whether those predictions survive the network's nonlinearity is the central empirical question.

The same structure appears natively in radio-frequency (RF) fingerprinting. There, networks classify complex I/Q time series (in-phase and quadrature components of the radio signal), and a trigger occupies chosen time segments in both channels at once. Explanation-Guided Backdoor Attacks Against Model-Agnostic RF Fingerprinting Systems shows that such triggers reach over 97% attack success against CNNs that split I and Q into separate real channels. A defender who couples I and Q at each time step is using exactly this joint sparsity.

Relation to Prior Work

Two papers motivate the gap. Check Your Other Door! Establishing Backdoor Attacks in the Frequency Domain injects an additive signal into the top-$k$ most sensitive complex Fourier coefficients. It reports over 99% attack success on CIFAR-10 at a 0.4% poisoning rate, with SSIM 0.9975, and shows Neural Cleanse fails against it. The trigger is complex-sparse by construction, and no defense uses that fact. Rethinking the Backdoor Attacks' Triggers: A Frequency Perspective detects poisoned inputs from their real cosine-transform energy, with a 98.5% average detection rate. It also shows that low-pass "smooth" triggers evade this detector while keeping about 97% attack success. Both papers treat detection as input classification, not as recovering an unknown trigger.

Three papers supply methods and constraints. Better Trigger Inversion Optimization in Backdoor Scanning shows that mask-times-pattern inversion has a rugged loss landscape and replaces it with a mask-free tanh parameterization. We reuse that smooth parameterization but move it to Fourier coordinates. UNICORN: A Unified Backdoor Trigger Inversion Framework inverts arbitrary transformations, including frequency edits, using two auxiliary networks. It reaches 95.60% average inverted-trigger attack success but runs about 2.7x slower than Neural Cleanse and gives no account of how many probes it needs. We trade its generality for a structured linear basis whose sample requirements can be predicted. Trojans in Artificial Intelligence (TrojAI) Final Report finds trigger inversion the most reliable model-level detector, with ROC-AUC above 0.90. It also warns that "natural Trojans", shortcut features clean models learn on their own, confound inversion. That warning is why we score support recovery and false flags on clean models, not just whether inversion produces some small flipping perturbation.

One paper constrains the theory. Phase retrieval in high dimensions: Statistical and computational phase transitions shows that practical algorithms can need more measurements than information theory requires (a "hard phase"), and that the gap behaves differently for complex signals. We should therefore expect the boundary our optimizer reaches to lag any linear prediction, and we will measure that lag directly. The rule that greedy solvers lose the complex advantage when they decouple real and imaginary parts (A Class of Deterministic Sensing Matrices and Their Application in Harmonic Detection) is the reason the key ablation below compares coupled and decoupled penalties under the same optimizer.

Research Program

The defender's inversion objective over $n$ clean probes is

$$ \min_{\Delta} \; \sum_{i=1}^{n} \ell\big(f(x_i + \mathcal{F}^{-1}\Delta),\, t\big) \; + \; \lambda \sum_{g} \lVert \Delta_g \rVert_2 , $$

where $f$ is the suspect model, $t$ a candidate target class, $\mathcal{F}^{-1}$ the inverse 2D Fourier transform, and $\ell$ the cross-entropy loss. Each group $g$ collects the real and imaginary parts of one frequency and its conjugate partner, so the penalty $\lVert \Delta_g \rVert_2$ switches a whole group on or off. $\lambda$ sets the strength of the sparsity penalty.

The decoupled ablation replaces the group penalty with an independent absolute-value penalty on every real number. This is the real-valued sparse regression arm of the CAMP comparison. For RF, groups are I/Q pairs at each time sample. We will optimize with proximal gradient steps that shrink each group's magnitude while keeping its phase (complex soft-thresholding), using the tanh reparameterization for stability.

The work has three parts. First, we train controlled populations of backdoored models with Check-Your-Other-Door-style triggers, sweeping trigger sparsity $k$ and trigger phase statistics (random-phase versus purely real coefficients). Second, we draw empirical phase diagrams of inversion success as a function of probe count $n$ and $k$ for each inverter. Third, we compute the linearized prediction by running state evolution on $A$ built from real input gradients. This tests whether the network's Fourier gradients behave enough like a random sensing matrix for the theory to say anything useful. The CAMP guarantees are proven only for i.i.d. Gaussian matrices, so this is a genuine test, not an assumption.

Baselines

The naive reference is Neural Cleanse-style pixel-space inversion with the same probe images. The frequency-attack paper reports that it fails completely against these triggers, so it should sit near chance in our diagrams. Any proposal that merely ties it would have no value.

The strongest existing method is UNICORN, run from its released configuration with its frequency transformation enabled, on the same probes and with the same compute budget (matched wall-clock, a hyperparameter search of equal size). Its reported average inverted-trigger attack success is 95.60% across benchmarks. That figure was measured at its own probe budget, and we found no result on Lacuna for UNICORN's success as a function of probe count on Fourier triggers. Beating it means a lower 50%-success probe count at equal or better support recovery, not a higher attack success at abundant data.

The second strong baseline is the mask-free tanh inverter of Better Trigger Inversion, run in pixel space as published and also in Fourier coordinates with an elementwise penalty. On ImageNet it found an 822-pixel trigger with 70% attack success, against Neural Cleanse's 27,000 pixels at 28%.

The Fourier-coordinate elementwise-penalty inverter is also the key ablation. It shares the basis, optimizer, parameterization and tuning budget with the proposal and differs only in coupling real and imaginary parts. Any gain over it is attributable to joint sparsity alone.

For RF, the baseline is inversion on the published real two-channel CNN with independent I and Q penalties, compared against I/Q-coupled inversion on the same model. The attack paper reports over 97% attack success and a 6% benign-accuracy drop on ORACLE.

Why not just…?

Why not just collect more clean probe images? If probes are cheap, the coupling gain matters less, and we accept that. The phase diagrams show where the gain lives: we predict it shrinks toward zero as $n$ grows past the decoupled boundary. The contribution in that regime is then a principled probe budget, not accuracy. Defender settings like TrojAI's supply only a handful of clean examples per class, which places them on the scarce side.

Why not just run UNICORN, which already inverts frequency transformations? It may well recover the trigger given enough probes and time, and its 2.7x slowdown is the cost of generality. Our head-to-head at matched compute and matched probe count settles it. If UNICORN's success boundary sits at or below the coupled inverter's, the structured approach adds only speed and predictability, and we will say so.

Why not just use a spectral input detector like the one in Rethinking Frequency? That detector needs poisoned inputs at test time. It is a different threat model from model-level scanning, and the same paper shows smooth triggers defeat it. We include smooth low-pass Fourier triggers in our attack sweep to check whether coupled inversion still finds them. If it does not, that is a real limitation.

Why not just add an elementwise sparsity penalty in Fourier coordinates? This is the most serious threat, because the network's nonlinearity could wash out the theoretical factor of two. It is exactly the key ablation. An adaptive attacker who injects purely real coefficients removes the random-phase energy split. We expect a smaller but nonzero gain there, because the conjugate-pair grouping still applies. If the gain vanishes in that case, joint sparsity offers no robust advantage against adaptive attackers.

Proposed Experiments

On CIFAR-10 and GTSRB with ResNet-scale models, we will train backdoored and clean populations with frequency triggers at several values of $k$ and phase distributions, plus smooth low-pass variants. On ImageNet (the 200-class subset UNICORN uses) we will repeat a reduced sweep. On ORACLE, and on WiSig for transfer, we will plant the explanation-guided RF triggers.

Metrics are as follows. Support recovery is the overlap (Jaccard index) between the inverted trigger's active groups and the true injected frequencies or time segments. Inverted-trigger attack success is measured on held-out images. Model-level ROC-AUC is computed over clean versus backdoored populations, including the false-flag rate on clean models as a check on natural Trojans. Each inverter's empirical phase boundary is the 50%-success contour in the $(n, k)$ plane.

The decisive checks are three. First, the ratio between the coupled and decoupled inverters' boundary heights at low $n$ should land well above one, approaching two for random-phase triggers and shrinking for real-only triggers. If it falls below about 1.2, or disappears when the decoupled arm gets extra optimization steps, the hypothesis fails. Second, the boundary predicted by state evolution from real gradient matrices should track the empirical boundary's shape. A systematic offset would measure the algorithmic lag that the phase-retrieval results lead us to expect. Third, at the coupled inverter's 50% probe count, it should match or beat UNICORN's support recovery at equal compute, without raising false flags on clean models.