A backdoor is a hidden rule planted in a neural network. The model behaves normally on ordinary inputs, but when a small, attacker-chosen pattern such as a sticker-like pixel patch is stamped onto any input, it outputs the attacker's target label. The only existing method that formally decides whether a given network contains such a rule is Verifying Neural Networks Against Backdoor Attacks. It combines a sequential statistical test over sampled clean inputs with an over-approximate analysis of the network's activations, and it handles only small MNIST networks, sometimes taking hours. Separately, compositional verification has shown how to get past the memory limits of whole-network analysis. Compositional verification means proving a property of a large system by checking pieces in isolation, under explicit "assume this input, guarantee this output" contracts that are chained together. CoVeNN uses this approach to verify ResNets with up to 110 convolutional layers, but only for robustness of single inputs, never for backdoors.
We propose to verify backdoor absence compositionally. The obvious move is to plug a backdoor property into CoVeNN, and it fails for a specific reason. A backdoor is one trigger shared across all inputs, so its definition has the form "there exists a trigger such that, for most inputs, the output flips." CoVeNN's contracts turn each cut into a plain numeric box, which erases exactly that sharing. Our contracts at each cut stay symbolic in the trigger itself. They are linear bounds whose only free variable is the small trigger vector, written separately for each sampled clean input. All the per-input relaxations can then be joined into a single solver query over one shared trigger. A plain box per cut would lose this coupling.
Core Claim
Fix a target label $t$, a trigger region (a patch location set) with trigger values $\delta \in \Delta \subset \mathbb{R}^d$, and a success threshold $\theta$. The network $f$ is backdoor-vulnerable if
$$\exists \delta \in \Delta:\ \Pr_{x \sim \mathcal{D}}\big[f(x \oplus \delta) = t\big] \ge \theta,$$
where $x \oplus \delta$ stamps the trigger onto clean input $x$ and $\mathcal{D}$ is the clean input distribution. As in verifyX, the outer probability is handled by sequential sampling of clean inputs $x_1,\dots,x_n$. Our change is in how the inner existence question is answered for a deep network split into subnetworks $f = f_K \circ \dots \circ f_1$.
For each sample $i$ and cut $k$, the contract is a pair of affine bounds in $\delta$ alone:
$$L_k^i \delta + l_k^i \;\le\; h_k^i(\delta) \;\le\; U_k^i \delta + u_k^i \quad \text{for all } \delta \in \Delta,$$
Here $h_k^i(\delta)$ is the activation vector after subnetwork $k$ on input $x_i \oplus \delta$, and $L, U, l, u$ are matrices and offsets computed by a bound-propagation verifier run only on subnetwork $k$. The clean image is fixed and concrete, so the symbolic dimension at every cut is $d$, the trigger size (tens of values for a patch), not the image size. Contracts are therefore cheap to store. Chaining requires that subnetwork $k$'s guarantee imply subnetwork $k{+}1$'s assumption, exactly as in CoVeNN. The final step is one mixed-integer program over the shared $\delta$, with one indicator per sample, asking whether at least $\lceil \theta n \rceil$ samples can be pushed to label $t$. An infeasible program gives a SAFE certificate for that sample batch. A feasible solution yields a concrete candidate trigger, which we execute on the real network. If it works, we have a witness and an UNSAFE verdict. This addresses the falsification weakness that the research file notes for current compositional neural verifiers.
The claim to be tested is that this coupling is what makes compositional backdoor verification non-vacuous. If each sample were verified independently, the guarantee would reduce to per-input patch robustness, which deep networks typically lack for large patches even when they carry no backdoor. If cuts were concretized into numeric boxes, the shared-trigger structure would be lost at every cut.
Research Program
The first component is the contract engine. We cut networks along the graph cuts CoVeNN uses, at residual-block boundaries. We compute per-sample affine-in-$\delta$ bounds with a linear-relaxation verifier restricted to one subnetwork. We compose them across cuts by substituting the incoming affine bounds, splitting signs in the usual interval-arithmetic way. We reuse CoVeNN's sample-guided refinement as the method for tightening loose cuts. The sampling here draws trigger values $\delta$ rather than nearby clean inputs, which guess tighter intermediate bounds that the subnetwork verifier then confirms or loosens.
The second component is the outer loop. We keep verifyX's sequential probability ratio test so that the overall verdict carries the same statistical meaning, and we change only the inner decision procedure. This keeps the comparison to verifyX clean.
The third component is an analysis of where looseness enters. For each verdict we record how much each cut widens the affine bounds. Early convolutional blocks have local receptive fields, so a patch trigger initially touches few neurons, and we expect the symbolic dependence to stay tight there and diffuse later. If this holds, the most effective placement puts more cuts late in the network. We will measure this rather than assume it.
The scope is deliberately narrow. It covers universal, input-agnostic triggers within a norm- or value-bounded patch domain, the same class verifyX handles. Sample-specific or warping triggers are outside this formulation, and we will not claim them.
Baselines
The naive reference point is reporting clean accuracy plus attack success rate under the known planted trigger. This tells us nothing about unknown triggers, but it gives the ground truth we use to score verdicts. Each network is trained either clean or with a BadNets patch backdoor, the attack used by PECAN.
The strongest existing method for the same question is verifyX from Verifying Neural Networks Against Backdoor Attacks. It runs monolithic DeepPoly abstraction, then a constraint solver over a universal trigger, then trigger search. On its MNIST suite it reports verifying backdoor absence for 89% of networks (455 of 510 tasks) and generating triggers for 73% of the networks where a backdoor was deemed possible. We will rerun it on that suite and on our CIFAR-10 ResNets, using the same sampled clean inputs, the same SPRT parameters, the same trigger domain, and the same per-task wall-clock and GPU-memory budget. On MNIST, beating it means matching its decided fraction with lower runtime. On CIFAR-10 ResNets, no reported result was found on Lacuna for backdoor verification of any kind, so beating it means producing correct decided verdicts where it runs out of memory or time.
The second baseline is a monolithic but stronger back end. Here verifyX's inner query is replaced by a single linear-relaxation pass over the whole network, symbolic in $\delta$ across all samples. This isolates whether decomposition helps at all, as opposed to simply using a better verifier. CoVeNN reports that standalone monolithic verifiers solve 14 of 140 robustness problems versus 95 for compositional verification, and that they hit memory limits around nine residual blocks. Those numbers are for robustness, so they are motivation and not a backdoor result.
Two ablations isolate the key ingredient. The first, per-sample decoupled, runs CoVeNN on each sample's patch-robustness problem independently and declares SAFE only if fewer than $\lceil \theta n \rceil$ samples are non-robust. The second, box cuts, keeps the shared-trigger MILP but concretizes each cut into a numeric interval as CoVeNN does. Both are sound. If either matches the full method's decided fraction, then symbolic coupling is not the operative ingredient. All variants share cut locations, verifier, refinement budget, and hardware.
Why not just…?
Why not just run CoVeNN on patch robustness for each input? This is the most serious alternative, since it requires no new machinery. It is the per-sample decoupled ablation above, and it is sound. Its weakness is predictable. Clean networks are often not robust to large adversarial patches on individual inputs, so it will return "possibly vulnerable" on many clean models, while the backdoor question asks only about one trigger shared across inputs. If patches are small enough that clean networks are already patch-robust, this alternative may perform just as well. We will report the patch size at which the two methods diverge, and if they never diverge on realistic patch sizes we will say so.
Why not just use a certified detector such as CBD, or a provable defense such as RAB or PECAN? CBD certifies detection of backdoors against $\ell_2$-bounded triggers through a noise-stability statistic calibrated on benign shadow models. It reports a certified true positive rate of 98% on GTSRB and 84% on SVHN, with false positive rates of up to 10%. Its guarantee is a bounded false-positive rate across a population of models, not a proof about this particular model, and it produces no witness trigger. RAB and PECAN certify a training procedure against a bounded amount of poisoning. They require retraining with noise or with data partitions: RAB reports certified accuracy of only around 23% on CIFAR-10, and PECAN is limited by CROWN-IBP's scaling. Neither can inspect a model that has already been delivered. We will run CBD on the same planted and clean models to show where its verdicts and ours disagree, but we treat it as a complementary tool rather than the same guarantee.
Why not just prune dormant neurons or use trigger inversion? Fine-Pruning and inversion-style detectors are cheap and often effective, but they say nothing when they find nothing. A pruned model still lacks a proof of absence, and adaptive attacks evade such heuristics, as On Evaluating Neural Network Backdoor Defenses discusses. Our method can be applied after pruning to check whether pruning actually removed the rule. We will report this pairing on the planted ResNets.
Proposed Experiments
We will first reproduce verifyX's MNIST setting, including its fully connected networks with 1024 neurons per layer and its convolutional networks. This is a sanity check that our verdicts agree with verifyX's on every task both methods decide. Any disagreement on a decided task would indicate a soundness bug and stop the project until it is fixed. We will then move to the CoVeNN ResNet family on CIFAR-10, from ResNet-6 up to ResNet-36, training a clean and a BadNets-backdoored copy of each architecture over a sweep of patch sizes and target labels.
The metrics are the fraction of tasks decided, verdict correctness against the planted ground truth, witness validity (attack success rate of the returned trigger on held-out clean inputs), wall-clock time, and peak GPU memory.
The decisive check has three parts that must hold together. On deep ResNets, the full method must decide a substantially larger share of tasks than both the monolithic baseline and the two ablations. It must never call a planted model SAFE. Its UNSAFE witnesses must recover triggers whose real attack success rate exceeds $\theta$. If coupling helps only on shallow networks, or the box-cut ablation closes the gap, that falsifies the central claim. That outcome would point instead to better cut placement, which our per-cut looseness analysis is designed to diagnose.
References
- Verifying Neural Networks Against Backdoor Attacks
- Compositional Neural Network Verification via Assume-Guarantee Reasoning
- PECAN: A Deterministic Certified Defense Against Backdoor Attacks
- CBD: A Certified Backdoor Detector Based on Local Dominant Probability
- RAB: Provable Robustness Against Backdoor Attacks
- Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks
- On Evaluating Neural Network Backdoor Defenses