Is Your Model Safe if PGD Attack Fails? The Truth About SMT Verification for Traffic Sign Models

When PGD Attacks Fail, Is the Model Really Safe?

There is a widely discussed blind spot in adversarial robustness evaluation: a failed attack does not mean the model is safe. A researcher on Reddit shared his tests on traffic sign classification models, comparing PGD (projected gradient descent) empirical adversarial attacks with Marabou, an exact formal verification tool based on SMT (satisfiability modulo theories) solvers. The core question strikes at the trustworthiness of deep learning evaluation: can we assert a model is robust simply because an attack didn't succeed?

This question has strong real-world significance. In safety-critical scenarios such as autonomous driving and traffic sign recognition, a single misclassification by the model can be directly linked to personal safety. Gradient-based attacks like PGD are essentially a "lower bound" evaluation—they can only prove that "the model did not fail under these attacks," but cannot prove that "no perturbation exists that could cause the model to fail." Formal verification attempts to provide an "upper bound" guarantee: within all allowed perturbation ranges, does the model's output remain unchanged?

Limitations of PGD Attacks: Why "Not Broken" Does Not Mean "Unbreakable"

PGD is one of the most commonly used adversarial attack methods today. It iteratively updates gradients to find inputs that maximize loss within a perturbation budget. When researchers use it to evaluate model robustness, the usual logic is: if PGD cannot find an adversarial example within a certain perturbation radius, the model is considered robust within that radius.

But this reasoning contains a logical leap. PGD is essentially a local search, constrained by gradient information, initialization, and iteration steps. Finding an adversarial example means the model is unsafe, but failing to find one does not prove the model is safe—it may simply mean the attack is not strong enough. The researcher's tests in the source material revolve around this pain point: comparing PGD's "empirical robustness" with Marabou's "exact proof" on the same set of traffic sign models.

The Essential Difference Between Empirical Evaluation and Formal Verification

Empirical evaluation answers "how does the model perform under a limited set of attack strategies"; formal verification answers "within a mathematically defined perturbation space, does any counterexample exist that violates the property." The former is sampling; the latter is exhaustive (or complete) search. Marabou, as an SMT-based neural network verification tool, can precisely encode networks with activation functions such as ReLU and determine whether an input point exists within a given input region that leads to misclassification.

"Lower Bounds" and "Upper Bounds" in Adversarial Robustness Evaluation

In robustness analysis, attack methods (such as PGD) provide a lower bound on robustness: they specify a concrete perturbation budget and attempt to find counterexamples. If the attack succeeds, the upper bound on model robustness is lowered (the model is unsafe at least under that budget); if the attack fails, it only means no counterexample was found under the current attack strategy, and the existence of other counterexamples cannot be ruled out. Therefore, a failed attack provides an empirical lower bound on robustness—the model is safe at least under the current attack, but the true safety radius may be smaller. Formal verification attempts to provide an upper bound: proving through exhaustive or complete search that no counterexample exists within a given perturbation space. If verification returns UNSAT, the model is proven robust within that space, which is a strict upper bound guarantee. Only by combining both can we more accurately characterize the true robustness boundary of a model.

Marabou and SMT Verification: Providing Deterministic Robustness Proofs

Marabou's core idea is to translate the neural network's computation process into a set of logical constraints, then hand them to an SMT solver to determine whether the constraint system is satisfiable. If the solver returns "unsatisfiable" (UNSAT), it means that within the specified perturbation range, no input exists that would cause the model to output a misclassification—this is a strict robustness proof. If it returns "satisfiable" (SAT), the solver provides a concrete counterexample, i.e., a true adversarial example.

For tasks like traffic sign recognition, where input dimensions are relatively small and network sizes are controllable, Marabou's exact verification is feasible. The tests in the source material were conducted in exactly this scenario: traffic sign images are not large, and classification networks are relatively lightweight, preventing SMT encoding and solving from facing combinatorial explosion.

The Cost and Boundaries of Exact Verification

Formal verification is not without cost. The computational complexity of SMT solving grows extremely fast with network size, and it remains difficult to scale to large vision models today. Marabou performs well on medium-sized networks, but once entering the realm of deep large models, verification time can jump from seconds to hours or even become unsolvable. This is why PGD remains the mainstream evaluation method in practical engineering—it is cheap, scalable, but simply provides no guarantees.

SMT (Satisfiability Modulo Theories) and Neural Network Verification

SMT is an extension of the SAT (Boolean satisfiability) problem, allowing theoretical constraints such as arithmetic, arrays, and bit-vectors to be added to propositional logic. In neural network verification, SMT solvers encode the computation of each network layer (such as affine transformations and ReLU activations) as logical formulas, and represent the input perturbation range as constraints, then determine whether a set of inputs exists that satisfies all constraints and causes the output to violate a safety property (such as misclassification). If the constraint system is unsatisfiable (UNSAT), then no such input exists, meaning the model is proven robust within that perturbation range. Marabou is based on this idea, with efficient encoding and solving optimizations specifically for ReLU networks, making it feasible on medium-sized networks.

Combinatorial Explosion and Scalability with Network Size

The computational complexity of SMT verification grows exponentially with network size (number of layers, number of neurons), rooted in the piecewise linear nature of ReLU activation functions, which introduces a large number of branches that the solver must explore across different activation pattern combinations. For large vision models (such as ResNet, ViT), the number of constraints can reach millions, and solving time can jump from seconds to hours or even fail to complete within a reasonable time. This combinatorial explosion is the core obstacle preventing formal verification from scaling to deep large models. Therefore, in practice, approximate techniques such as abstract interpretation, linear relaxation, or branch-and-bound are often used to balance precision and efficiency, but exact proofs remain limited to small and medium-sized networks.

What the Empirical Comparison Reveals

The core finding shared by the researcher can be summarized in one sentence: in regions where PGD attacks fail, Marabou can sometimes find counterexamples. In other words, empirical robustness overestimates the true safety of the model. This phenomenon can occur at multiple perturbation radii, depending on network architecture and training method.

This does not negate the value of PGD. PGD remains an efficient "quick screening" tool: when PGD can break the model, the model is definitely unsafe, and no further verification is needed. The problem lies in the converse: when PGD cannot break the model, we cannot simply stop there. For safety-critical scenarios, formal verification provides deterministic conclusions that empirical methods cannot replace.

Implications for Safety-Critical Applications

Traffic sign recognition is just a small entry point for formal verification. The experiments in the source material remind practitioners: in high-risk domains such as autonomous driving perception and medical image classification, relying solely on empirical attacks like PGD to make robustness claims is insufficient. A more reasonable process might be layered verification—first use PGD to quickly identify fragile models, then use tools like Marabou for exact verification on candidate models that pass the screening.

How to Implement Robustness Verification in Your Own Project

For developers who want to reproduce this comparison, the basic path is: train a traffic sign classification model (such as a lightweight CNN), define the perturbation radius and constraint range for input pixels, use PGD to generate adversarial examples and record failure cases, then encode the same model and perturbation range into Marabou for solving. When comparing results, focus on two types of discrepancies: PGD succeeds and verification also returns SAT (consistent), and PGD fails but verification returns SAT (a vulnerability missed by empirical methods).

Note that Marabou's encoding method, activation function handling precision, and timeout settings directly affect the credibility of verification conclusions. When verification returns "UNKNOWN," it cannot be treated as a safety signal.

Credibility of Verification Results: UNSAT, SAT, and UNKNOWN

When using verification tools like Marabou, the solver may return three types of results: UNSAT (unsatisfiable) means no counterexample exists under the given constraints, i.e., the model is proven robust; SAT (satisfiable) means a counterexample exists and provides a concrete adversarial example; UNKNOWN means the solver cannot reach a conclusion within the timeout or resource limits. UNKNOWN cannot be regarded as a safety signal, because it neither proves robustness nor finds a counterexample, and may hide undiscovered vulnerabilities. In addition, encoding precision (such as floating-point handling), activation function approximation methods, and timeout settings all affect the reliability of conclusions. Therefore, when reporting verification results, these three states must be clearly distinguished, and a more conservative evaluation strategy should be adopted for UNKNOWN cases.

Conclusion

A failed PGD attack is only the starting point of robustness evaluation, not the end. The empirical comparison on traffic sign models demonstrates that a real gap exists between empirical attacks and formal proofs. For safety-sensitive applications, the exactness provided by tools like Marabou is worth the computational cost. The real question is no longer "did the attack succeed," but "can we prove it won't succeed."

One-line Summary

A failed PGD attack does not mean the model is safe; formal verification with Marabou can reveal vulnerabilities missed by empirical evaluation.

Paragraph Summary

The article explores the blind spot in adversarial robustness evaluation: "a failed attack does not mean the model is safe." The author compares PGD empirical attacks with the SMT solver-based formal verification tool Marabou on traffic sign classification models. As a local search, PGD can only provide an empirical lower bound on robustness; failing to find adversarial examples does not mean the model is safe. Marabou, by encoding neural networks as logical constraints, provides exact robustness proofs (UNSAT) or concrete counterexamples (SAT). Tests found that Marabou can still find counterexamples in regions where PGD fails, indicating that empirical methods overestimate model safety. The article recommends a layered verification process: first use PGD for quick screening, then perform exact verification on candidate models, and emphasizes that a verification result of UNKNOWN cannot be treated as a safety signal.