Security Properties of Neural Networks as Decision Problems
Researchers classify neural-network security checks as co-NP-complete or harder, including backdoors and parameter faults.
The paper formalizes eight security decision problems for deployed neural networks, including planted backdoors, parameter faults, and private-input leakage. Using quantifier-free real-addition encodings and Sontag's theorem, it places properties by quantifier prefix. Over ReLU networks, non-interference, monotonicity, counterfactual fairness, and inversion resistance are co-NP-complete, while quantised backdoor-trigger detection is Sigma_2^P-complete. Quantifying over parameters, as in bit-flip and analog-fault models, makes verification exists-R-complete even for identity networks, and the related safety question forall-R-complete for ReLU.
- Eight neural-network security questions are placed in the polynomial or real hierarchy.
- Quantised-alphabet backdoor detection is Sigma_2^P-complete, above robustness certification.
- Non-interference, monotonicity, fairness and inversion resistance are co-NP-complete over ReLU.
- Parameter-fault verification is exists-R-complete even for identity-node networks.
From the original article
1 min read at arxiv.orgCertifying a deployed neural network raises decision problems that the verification literature has not classified: whether the model carries a backdoor planted in its training data, whether a fault in its stored parameters can drive it into an unsafe state, whether its output leaks a private part of its input. We formalise eight such problems and classify what we can. The organising observation is a logical one.
By Adrian Wurm · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.