Complexity of neural network security checks placed in decision classes

Security Properties of Neural Networks as Decision Problems

Logic in Computer ScienceComputational ComplexityCryptography and SecurityMachine Learning

Summary

Checking whether a neural network is safe or has hidden problems is not well understood in terms of difficulty. The authors identify eight specific safety and privacy questions about neural networks and analyze their computational complexity. They show these problems fit into established complexity classes based on the network type and what is being checked. This helps clarify which security checks can be done efficiently and which are inherently harder to solve.

What this means in practice

  • For machine learning engineers: Determine which neural network safety and privacy verification problems can be efficiently checked and which require more complex analysis.
  • For hardware reliability teams: Understand the increased difficulty of verifying neural network safety when parameters are subject to faults like bit flips or radiation.

A theory result. No direct application yet.

Authors

Adrian Wurm

Abstract

Certifying 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. The function computed by a piecewise linear network, together with all its node values, is definable by a quantifier-free formula of real addition of size linear in the network, so a property of the network is a quantifier-alternation sentence, which Sontag's 1985 theorem places in the polynomial hierarchy at the level of its prefix. Membership results are thus corollaries, and the argument makes plain what they need: that the quantified objects are inputs rather than the network's own parameters. Non-interference, monotonicity and counterfactual fairness have exactly the complexity of network equivalence and of interval verification, all co-NP- complete over ReLU. Detection of backdoor triggers from a quantised alphabet is Sigma_2^P-complete, one level above robustness certification, so it does not reduce to polynomially many robustness queries unless the hierarchy collapses. Inversion resistance is co-NP-complete for every l_p metric, p a fixed positive integer. Quantifying over parameters instead of inputs - the fault model of bit-flip attacks, radiation upsets and analog accelerators - makes verification exists-R-complete already for networks of identity nodes, for which every previously studied problem is in P, and it stays so when each parameter is confined to a box of inverse-polynomial width; the corresponding safety question is forall-R-complete for ReLU.