Skip to content

Efficient Symbolic Reasoning for Neural Network Verification

Efficient Symbolic Reasoning for Neural-Network Verification

arXiv· arXiv:2303.13588· Zi Wang, Somesh Jha, Krishnamurthy, DvijothamUniversity of Wisconsin-Madison; Google ResearchIndexed by this site · 23 days ago· Originally publishedDefenses

Quick read

Defenses

Based on the paper PDF (AI-generated); refer to the original

The authors propose a framework that symbolically encodes neural network verification problems using quadratic relations and relaxes them to SDPs; on ℓ2 certification on MNIST, ShenBao's certified count is on average 60% higher than BCP.

Threat modelFor ℓp adversarial perturbations of the input (the evaluation uses ℓ2, radius ǫ), the attacker perturbs the input to change the classification; the victim system is a ReLU feedforward network on MNIST (small: single hidden layer with 64 nodes; medium: two hidden layers with 128/64 nodes). The goal is to certify that the prediction is unchanged within a given radius.

Questions
Neural networks are susceptible to adversarial perturbations, and exact verification is NP/coNP-hard; the authors argue that non-symbolic abstraction domains based on linear relations struggle with nonlinear perturbations and unconventional structures, and a balance between efficiency and accuracy is needed.
Methods
Propose a symbolic reasoning framework: assign symbols to each computational component of the network, use quadratic relations to exactly encode computation and attack constraints, write the verification problem as a quadratic program, then use the Shor relaxation to convert it into an SDP solvable in polynomial time; and give encodings for ReLU, ℓp perturbations, metric learning, and DEQ.
Experiments and results
On the ℓ2 certification task on MNIST, they implement the tool ShenBao and compare with BCP: on 200 test points, ShenBao's certified count is higher in most settings, and the authors claim on average 60% higher; the exception is that BCP is slightly higher on BCP-trained models. ShenBao takes 102.4–426.2 seconds per SDP, while BCP completes all in about 2 seconds.
Limitations and future work
The authors note that the bottleneck is solving the SDPs; their implementation uses MOSEK on CPU and is slower than the GPU version of BCP; the authors say the SDP estimated by FGL for multi-layer networks has no approximation guarantee (an open problem in [62]), and which quadratic encoding relaxation is better has not been explored. The experiments only cover ℓ2 data-dependent certification of two ReLU feedforward networks on MNIST.
Experimental setupsmall DNN (single hidden layer with 64 ReLU nodes)、medium DNN (two hidden layers with 128 and 64 nodes) · MNIST · Accuracy、PGD 攻击后正确数 et al.
Evaluated models
small DNN (single hidden layer with 64 ReLU nodes)medium DNN (two hidden layers with 128 and 64 nodes)
Benchmarks
MNIST
Metrics
AccuracyPGD 攻击后正确数认证正确数(ShenBao / BCP,200 个测试点)认证运行时间(秒)
AI summaryTo address issues such as neural networks' susceptibility to adversarial attacks, researchers proposed a program reasoning framework called symbolic reasoning for neural network verification. Centered on a semantically flexible symbolic domain and expressive quadratic relations, the framework encodes many neural network verification problems as quadratic programming, then relaxes them to semidefinite programming that can be solved efficiently. The authors state that it can verify various neural network properties in different scenarios, especially cases difficult to handle with non-symbolic domains, and may bring new theoretical insights and practical tools.

To address issues such as neural networks' susceptibility to adversarial attacks, researchers proposed a program reasoning framework called symbolic reasoning for neural network verification. Centered on a semantically flexible symbolic domain and expressive quadratic relations, the framework encodes many neural network verification problems as quadratic programming, then relaxes them to semidefinite programming that can be solved efficiently. The authors state that it can verify various neural network properties in different scenarios, especially cases difficult to handle with non-symbolic domains, and may bring new theoretical insights and practical tools.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    The authors propose a symbolic reasoning framework that encodes neural network verification as a quadratic program and then relaxes it into an SDP, to handle tasks that are difficult to verify with non-symbolic domains.

    Core problem: how to efficiently and exactly verify properties of neural networks under adversarial perturbations, especially tasks such as nonlinear perturbations and unconventional structures that abstract domains based on linear relations struggle to handle.

    • Problem setting: DNNs have been integrated into modern software systems but are vulnerable to adversarial attacks; the authors note that many defense mechanisms were later broken, so the community has focused on certifiable robustness.
    • Shortcomings of existing methods: exact verification has been proven NP/coNP-hard ([29, 30, 61]), so over-approximation is necessary; the authors argue that methods based on abstract interpretation mostly define abstract domains with linear relations, and nonlinear perturbations and unconventional architectures require many ad-hoc techniques.
    • Core observation: quadratic relations are expressive, and many hard combinatorial optimization problems can be written as quadratic programs; the authors believe that various DNN verification tasks can be exactly encoded as quadratic programs (QPs), then relaxed into semidefinite programs (SDPs) that can be solved efficiently.
    • What the paper proposes: a program reasoning framework named symbolic reasoning, containing two components, a symbolic domain and quadratic relations; it gives quadratic encodings for various attacks and activations, and conducts empirical work on the ℓ2 robustness certification task.
    • Threat model:
      • Attacker goal: apply an ℓp-norm perturbation (p ≥ 1) to the input so that the model prediction changes.
      • Perturbation constraint: ||x̃ − x||p ≤ ǫ; the paper focuses on encoding ℓ2 and ℓ∞, and Appendix A gives encodings for ℓ1 and general ℓp.
      • Victim system: a feedforward classification network with ReLU activations; Section 4 also discusses metric learning models and deep equilibrium models (DEQ).
      • Defender goal: certify that the prediction is unchanged within a given radius (data-dependent analysis), or estimate the network's formal global Lipschitz constant (data-independent analysis).
  2. What related research exists?

    Related work falls into three categories: abstract-interpretation verification, SDP verification and Lipschitz estimation, and improvements to SDP solving; the authors state that this paper unifies and generalizes the paradigms behind these works.

    Neural network verification based on abstract interpretation

    • Gehr et al. [23] (AI2), Singh et al. [58], Wang et al. [60]—define abstract domains to over-approximate the input and reinterpret network execution, achieving sound verification. The paper points out that the abstract domains of such methods are usually defined with linear relations, and handling nonlinear computation requires ad-hoc techniques.
    • Wong and Kolter [63]—certify the problem with linear programming (LP) relaxations; Katz et al.'s [30] Reluplex uses SMT for exact verification, which the paper calls an exponential-time verifier.

    Using SDPs for DNN verification and Lipschitz estimation

    • Raghunathan et al. [53]—propose an SDP relaxation for ℓ∞ robustness certification; [52] designs an SDP certification and training method for two-layer networks.
    • Fazlyab et al. [22]—use SDPs to estimate the ℓ2 Lipschitz constant of multi-layer networks; Wang et al. [62] give a compositional interpretation of [22] and generalize it to ℓ∞, and also prove that the SDPs of [22] and [52] are exactly the Shor relaxation of Equation (7) (primal and dual forms).
    • The paper relays: [35] states that [22] cannot be transferred to the ℓ∞ case, and [53] holds that [52] applies only to two-layer networks; the authors believe that from the perspective of this framework these SDPs are general enough, and these transfers are straightforward.

    Improving the quality and efficiency of SDP verification

    • Zhang [66] studies when SDP relaxations have no loss of precision; Dathathri et al. [20] design a first-order SDP algorithm implementable on GPUs and scale it to CIFAR-scale networks; Newton and Papachristodoulou [46], Xue et al. [65] use chordal sparsity to speed up solving SDPs induced by DNNs.
    • Salman et al. [55] attempt to unify efficient robustness certification work and propose a convex relaxation barrier; the paper points out that they only study LP relaxations and fail to include the SDP certification method [53], and the authors claim this paper can be seen as a supplement to [55], because SDPs are stronger than LPs ([14] proves a precision gap between polynomial-size LPs and SDPs).

    Baselines and benchmarks: the baseline tool in the experimental section is BCP [37] (a certification method combining ℓ2-Lipschitz constants with interval domains), and PGD attacks [39] are also used as a comparison; the dataset is MNIST [36].

    The authors position this paper as: distilling a unified symbolic reasoning framework from these existing SDP works, showing that its scope extends beyond the original tasks, and providing a new QP/SDP representation for verification problems.

  3. How does the paper address this problem?

    The framework symbolizes each network component, exactly encodes the verification task using quadratic relations to obtain a QP, and then uses the Shor relaxation to convert it into an SDP for solving.

    Overall idea: similar to classical symbolic execution, the framework "executes" the DNN and generates an optimization program that exactly characterizes the verification problem—not a satisfiability program but a QP; then the Shor relaxation converts the intractable QP into a convex SDP, solved in polynomial time. The framework is named symbolic reasoning, and its two core components are the symbolic domain and quadratic relations.

    Symbolic execution and quadratic encoding

    • Assign a symbol to the input and output of each component function, and constrain them with quadratic relations; affine transformations are linear and hence also quadratic, and the key lies in encoding the activation functions.
    • ReLU has two interpretations: (i) the slope-restricted interpretation (from [22]): the slope between any two points lies in [0,1], encoded as ((z − z̃) − (y − ỹ))(z − z̃) ≤ 0; (ii) the exact interpretation (from [53]): three quadratic inequalities y ≤ z, z ≥ 0, (z − y)z ≤ 0.
    • Remark 3.2 gives another exact encoding: introduce a branch symbol s, with s(s − 1) = 0, (s − 1/2)y ≥ 0, z = sy; the authors claim the slope-restricted interpretation can be viewed as a stateless interpretation that does not consider execution state.
    • Perturbation encoding: the ℓ2 ball is written as Σ(xi − x̃i)² ≤ ǫ²; ℓ∞ is written as (xi − x̃i)² ≤ ǫ² for each i; Appendix A uses Hölder's inequality to encode ℓ1 and general rational p ℓp constraints.

    Data-dependent analysis (local certification)

    • Fix input a, quantify the maximum change of f(a) under ℓp perturbations, yielding a QP (Equation 5): maximize vz + c, with constraints including ReLU computation, affine transformations, and ||x − a||p ≤ ϵ; the authors claim this QP exactly encodes the verification problem.
    • For the ℓ2 case, use the Shor relaxation: define a PSD variable V (formed from 1, z, x, decomposed into blocks Z, X, Y, etc.), and after substituting yi = wi x + bi, obtain an SDP (Equation 6), containing per-neuron quadratic constraints and tr(X) − 2xᵀa + aᵀa − ǫ² ≤ 0.
    • For multi-layer networks, one only needs to introduce more symbols for the input and output of each layer and constrain them in the same way, then relax similarly.

    Data-independent analysis (FGL estimation)

    • The goal is to estimate the formal global Lipschitz constant (FGL, defined in [62]): the maximum gradient operator norm when all activations are treated as independent, which is an upper bound on the Lipschitz constant.
    • Let ∆x, ∆y, ∆z denote the differences between two points; the QP (Equation 7) maximizes v∆z, with constraints (∆zi − ∆yi)∆zi ≤ 0, ∆yi = wi ∆x, ||∆x||p ≤ 1; the authors claim the SDPs of [22] and [52] are exactly its Shor relaxation.

    Extended applications of the framework

    • Metric learning: the model normalizes the representation layer output to the unit sphere and outputs the class of the nearest anchor; the authors derive that the symbolic form of (z̄ − õ)² − (z̄ − o)² is equivalent to minimizing (o − õ)z, so verifying a metric learning model is the same as a standard classification model.
    • DEQ models: the hidden layer output z is also fed back to the hidden layer input (fixed point); the QP for FGL estimation only needs to change ∆yi = wi ∆x to ∆yi = wi ∆x + ui ∆z, with the rest unchanged.
    • Appendix B gives encodings for other activations: the slope-restricted interpretation only needs the derivative lower and upper bounds a, b, using (∆z − a∆x)(∆z − b∆x) ≤ 0; non-algebraic activations (such as tanh) are approximated to arbitrary precision by piecewise linear functions, then constructed as building blocks encoded with ReLU (taking ReLUθ as an example).

    Solving and theoretical results

    • QPs are generally NP-hard (e.g., MAXCUT can be written as a QP), so the Shor relaxation is used: the primal form relaxes scalar variables into multi-dimensional vectors and removes the rank-1 requirement of the dyadic matrix to obtain an SDP; the dual form is the Lagrangian relaxation (Appendix C).
    • Theorem 6.1: the SDP optimal value of two-layer network FGL estimation is O = minh nλmax(M + diag(h)) (the components of h sum to 0), i.e., one only needs to check the largest eigenvalue of M + diag(h); the authors claim this bound is tighter than the bound of [52], and give an example.
  4. What experiments did the paper conduct?

    On the ℓ2 certification task on MNIST, ShenBao's certified count is higher than BCP in most settings (the authors say on average 60% higher), but each SDP requires 102.4–426.2 seconds.

    Experimental setup

    • Task: ℓ2 data-dependent certification—certify that 200 test points remain correctly classified under ℓ2 perturbations of a specified radius; this task was chosen because no ready-made tool exists in the same framework, but baseline tools are available for comparison.
    • Networks tested: two ReLU feedforward networks, small (single hidden layer, 64 nodes) and medium (two hidden layers, 128 and 64 nodes), trained on MNIST (10 classes).
    • Training modes: natural training (ǫ = 0), BCP training (small ǫ = 0.5, medium ǫ = 1.0), PGD training (small ǫ = 0.5, medium ǫ = 1.0); small trained for 60 epochs, medium for 100 epochs.
    • Tools: ShenBao is implemented with MATLAB CVX plus the MOSEK solver; the baseline is BCP; PGD attacks are also used to measure adversarial accuracy as an upper-bound sanity check on certified accuracy.
    • Metrics: Accuracy (number correct without attack), PGD (number correct after attack), and the number certified correct by ShenBao and BCP respectively, all with a denominator of 200 test points.
    • Runtime environment: 48-core Intel Xeon Silver 4214 (2.20GHz), 258GB memory, 8 RTX 2080 Ti GPUs; ShenBao's MOSEK can only run on CPU, while BCP runs on GPU.

    Main results

    Table 1: number certified correct on 200 test points (ShenBao / BCP), listed by model, training mode, and attack radius.

    Swipe horizontally to read the table

    Model (training mode)RadiusPGDShenBaoBCP
    small (natural training, Acc 200)0.318112658
    small (natural training)0.5138705
    small (natural training)0.790200
    small (BCP training, Acc 198)0.3192186188
    small (BCP training)0.5190177176
    small (PGD training, Acc 198)0.3196193159
    medium (PGD training, Acc 199)0.71951770
    medium (PGD training)1.3167900

    (According to Table 1; omitted rows: small BCP training 0.7 (156/158), small PGD training 0.5 (178/72) and 0.7 (161/12), medium BCP training 0.7/1.0/1.3 (151/158, 126/128, 100/105), medium PGD training 1.0 (142/0).)

    • The authors state that ShenBao consistently outperforms BCP, with the exception of BCP-trained models (e.g., small BCP training at radius 0.3, 186 vs. 188); the authors explain that BCP training regularizes the model so that its bounds are tighter, and even so ShenBao remains close.
    • The authors state that on average the framework is 60% better than the baseline (this figure appears in both the abstract and Section 5).
    • The authors point out one observation: the PGD-trained medium model at radius 0.7 is certified by ShenBao on 177/200 (about 88%), whereas BCP cannot certify it at all; the authors state that this shows PGD-trained models can achieve certifiable robustness comparable to or even better than BCP training.

    Certification speed

    • Table 2: ShenBao takes an average of 102.4 seconds to solve a single SDP for the small model and 426.2 seconds for the medium model; BCP certifies all 200 points in about 2.1 seconds and 1.8 seconds respectively.
    • MNIST has 10 classes, so certifying one input with ShenBao requires solving 9 mutually independent SDPs, which can be parallelized; the table records the average time to solve one SDP, whereas BCP records the total time for all 200 points.
    • The authors explain that the bottleneck is the use of the general-purpose SDP solver MOSEK, which can only run on CPU, whereas BCP is implemented on GPU; the authors state that compared with exponential-time verifiers such as Reluplex, the framework is polynomial-time and can handle networks of practical scale.

    Other ablations and analysis

    • The paper does no other ablation experiments; the theoretical analysis is in Section 6.2: the authors relay that [62] proves the SDP relaxation of the two-layer network FGL has a K_G (Grothendieck constant) approximation guarantee for ℓ∞ and a √(π/2) approximation guarantee for ℓ2, and that these are optimal under P ≠ NP and the unique games conjecture, respectively ([11], [51]).
    • The authors note that the SDP of the FGL estimate for multilayer networks has no approximation guarantee, and that [62] lists this as an open problem.
    • The authors prove Theorem 6.1 and give an example where its bound is tighter than that of [52] (Appendix E).
  5. What are some points that can be further explored?

    The authors note that SDP solving efficiency is the bottleneck, multi-layer FGL has no approximation guarantee, and the choice of encoding has not been explored; the experiments only cover ℓ2 certification of two ReLU networks on MNIST.

    Limitations and future directions noted by the authors

    • Solving efficiency bottleneck (Section 5 RQ2, Section 6.1): the framework relies on off-the-shelf SDP solvers and is slower than the baseline in the authors' implementation; the authors say solving the SDPs induced by verification tasks is beyond the scope of this paper and hope to inspire specialized SDP solving algorithms for DNN verification.
    • No approximation guarantee for multi-layer FGL (Section 6.2): the FGL-estimated SDP for multi-layer DNNs has no approximation guarantee; the authors cite [62] and present it as an open problem.
    • Accuracy gap between LP and SDP (Section 6.2): the authors consider it an interesting question whether DNN verification problems also exhibit an LP/SDP accuracy gap similar to [14].
    • Choice of encoding (Section 6.2): the quadratic encoding of the same problem is not unique, and relaxations of equivalent QPs may give different solutions; the authors say exploring which encoding gives a better relaxation is an interesting question but beyond the scope of this paper.
    • Training networks with SDP constraints (Section 6.2): the authors consider it a promising direction to analyze SDPs and find alternative objectives suitable for first-order methods to train networks with desired properties.

    Scope of experiments

    • The networks tested are two ReLU feedforward networks on MNIST: small (single hidden layer, 64 nodes) and medium (two hidden layers, 128/64 nodes), 2 in total.
    • The only empirical task is ℓ2 data-dependent certification; metric learning, DEQ, ℓ∞/ℓ1/general ℓp encodings and other activations are only derived, not experimented on.
    • The baseline tool is BCP, and the comparison attack is PGD; each setting uses 200 test points, and the paper does not report the number of repetitions.
    • Attack radii: 0.3/0.5/0.7 for small, 0.7/1.0/1.3 for medium; training modes are natural, BCP and PGD.
    • The paper does not report a measure of the gap between ShenBao's certification results and true robustness (the certified correct count is only bounded above and below by PGD adversarial accuracy).
  6. Summarize the main content of the paper

    The authors propose a symbolic reasoning framework that encodes DNN verification as a QP and then relaxes it to an SDP; on MNIST ℓ2 certification, the certified count is higher than BCP in most settings, but solving is slow.

    This is a paper on neural network verification methods: addressing the problem that exact verification is NP/coNP-hard, while abstract domains based on linear relations struggle with nonlinear perturbations and unconventional structures, the authors propose a symbolic reasoning framework.

    • Method: assign symbols to each computational component of the network, use quadratic relations to exactly encode computation and attack constraints, write the verification task as a QP, then use the Shor relaxation to convert it into an SDP solvable in polynomial time; the framework is composable and easy to adapt to different architectures.
    • Tasks covered: data-dependent ℓp robustness certification, data-independent FGL estimation; and they derive encodings for metric learning models (verification is equivalent to a standard classification model) and DEQ models; the appendix gives encodings for ℓ1/general ℓp and other activations (including ReLUθ).
    • Theoretical results: the authors claim that the SDPs of [22] and [52] are exactly the Shor relaxation of the FGL estimation QP; they prove Theorem 6.1, expressing the SDP optimal value of two-layer network FGL as the minimization of nλmax(M + diag(h)), and claim this bound is tighter than [52].
    • Empirical: on the ℓ2 certification task on MNIST, they implement the tool ShenBao (CVX + MOSEK), comparing with BCP on the number of certified points among 200 test points; ShenBao is higher in most settings, and the authors claim on average 60% higher, with the exception that BCP is slightly higher on BCP-trained models.
    • Representative numbers: for the small PGD-trained model at radius 0.3, ShenBao certifies 193/200, BCP 159; for the medium PGD-trained model at radius 0.7, ShenBao 177/200, BCP 0 (Table 1).
    • Cost and conclusion: ShenBao takes on average 102.4 seconds (small) and 426.2 seconds (medium) to solve a single SDP, while BCP completes all 200 points in about 2 seconds (Table 2); the authors believe the framework provides a new QP/SDP representation for verification tasks, can bring in new tools such as matrix analysis and approximation theory, and hope to motivate research on specialized SDP solving algorithms.

Related papers

Show 3 more papers
Read originalarxiv.org