Vincent Tjeng, Russ Tedrake
9 min
Abstract
Neural networks have demonstrated considerable success in a wide variety of real-world problems. However, the presence of adversarial examples - slightly perturbed inputs that are misclassified with high confidence - limits our ability to guarantee performance for these networks in safety-critical applications. We demonstrate that, for networks that are piecewise affine (for example, deep networks with ReLU and maxpool units), proving no adversarial example exists - or finding the closest example if one does exist - can be naturally formulated as solving a mixed integer program. Solves for a fully-connected MNIST classifier with three hidden layers can be completed an order of magnitude faster than those of the best existing approach. To address the concern that adversarial examples are irrelevant because pixel-wise attacks are unlikely to happen in natural images, we search for adversaries over a natural class of perturbations written as convolutions with an adversarial blurring kernel. When searching over blurred images, we find that as opposed to pixelwise attacks, some misclassifications are impossible. Even more interestingly, a small fraction of input images are provably robust to blurs: every blurred version of the input is classified with the same, correct label.
Sam: Precisely—for a ReLU where output y is the maximum of input x or zero, and x is bounded between lower limit l and upper u, they add a binary switch a that's 1 if x is non-negative. Four inequalities follow: y can't exceed x minus some slack when a is off; y at least matches x; y capped by u when a is on; and y non-negative. When a is zero, these force y to zero regardless of x's negative value; when a is one, they lock y to x.
Alex: That sounds tight—like the math leaves no wiggle room for invalid outputs. What about max-pooling layers, where you take the biggest value from a group of inputs?
Sam: Similar idea for max-pooling: y picks the maximum from several inputs x1 to xm, each with their own bounds. They pre-drop any input that can't possibly be the max, then use binary indicators ai per input, with exactly one ai set to 1—the winner. Constraints ensure y matches that xi when ai is 1, and stays loose otherwise, using the next-highest possible max to avoid binding wrongly.
Alex: So layers chain together through these linear ties and switches, building the full network path. How do they get those tight bounds without guessing?
Sam: Interval arithmetic propagates ranges forward: start with pixel bounds zero to one, compute possible min-max outputs per layer to bound activations before non-linearities. For even tighter ones, they solve partial MIPs maximizing or minimizing each variable of interest—these often slash solve times by orders of magnitude over crude estimates, making relaxations discard junk branches fast.
Alex: And the branch-and-bound solver uses those relaxations how?
Sam: Yes—the solver relaxes binaries to continuous for a lower-bound LP on min distance, starting from prior candidates or proofs of no closer foe. Branch-and-bound splits on binaries, tightening the gap between upper candidate distance and lower bound until they match exactly—proving optimality or robustness. On small MNIST nets—two or three hidden layers, 97% accurate—they verify ground-truth perturbations tenfold faster than SMT, even if worst cases hit hours.
Alex: Hours for modest nets flags a limit for bigger real-world models, but those tight mechanics explain the speed edge. Ties back to certifying self-driving vision against shakes. How did these MIP solves play out in their experiments?
Sam: For additive perturbations on ten MNIST test images—one per true label, targeting each of the other nine categories—the solver handled ninety cases. On the simpler network N1, mean solve time was about 162 seconds, though worst cases reached over an hour; for deeper N2, means climbed to 3081 seconds, with extremes over ten hours. Blurring experiments scaled to the first fifty images per category, totaling five hundred pairs—and solves were much quicker.
Alex: Fifty per category—that's a bigger test set. What numbers show that speedup for blurring?
Sam: Median time for N2's ground-truth blurring adversaries dropped from 1120 seconds additive to just under five. Overall, blurring solves were one to two orders of magnitude faster across the board—thanks to exploiting the perturbation structure for sharper starting bounds.
Alex: Orders of magnitude? Why does blurring slash times so dramatically, beyond just the network encoding?
Sam: Two key factors: first, far fewer decision variables—784 for pixel-wise additive tweaks on 28-by-28 MNIST images, versus 24 for the five-by-five blurring kernel. Second, and more crucially, the blur's convolution lets them compute precise input bounds upfront—for each perturbed pixel, the min is the window's dimmest original, the max its brightest, tightening relaxations from the start.
Alex: So the perturbation family itself hands you better bounds, pruning the search early. But not every image-target pair worked—what's that about?
Sam: They define achievability: whether any blur in the family flips the image to the target class. Across those five hundred pairs, only about 43 percent were achievable for N1, 47 percent for N2—less than half, unlike additive tweaks that reach nearly everywhere. Some misclassified blurs look nearly identical to originals, yet many pairs prove impossible. Success rates vary wildly: for N1, every image labeled 1 flips to 8 under some blur, but only one of 50 labeled 8 flips to 1. Aggregated, targets like 8 succeed 88 percent of the time, while 1 succeeds just 5 percent—highlighting label-specific vulnerabilities.
Alex: Not symmetric—like 2 and 8 resist certain flips more. In a self-driving car spotting pedestrians, that could mean tuning for minimal missed detections, even if it flags extras. They also quantify per-image vulnerability: number of achievable wrong targets, from zero—provably robust, where every blur stays correct—to nine. A small fraction hit zero, even without robustness training.
Sam: Precisely—the paper notes designers might balance those rates based on costs, prioritizing low false negatives for safety. Examples look unambiguous to us, yet prove safe mathematically. For achievable blurring adversaries, medians around 65 to 68—much larger than pixel-wise additives—though mins still tiny at 0.1 or so across 784 pixels.
Alex: Provably robust images without special training—that's intriguing, suggesting off-the-shelf nets have pockets of reliability against blurs. With worst solves over 10 hours even here, what's the real-world path?
Sam: Scaling remains key: three-layer MNIST hits hours in extremes, so larger vision nets need solver tweaks or layered structure exploitation to cut explored nodes. Still, median blurs solve in seconds, additives in under 20 minutes—first to certify full robustness exhaustively for such families, enabling stats on test sets and defense checks. This MIP encodes perturbations and ReLUs precisely, proving some inputs safe to all blurs and spotting patterns like asymmetric risks. It boosts confidence in deploying nets, with paths to robust-by-design training and broader degradations like contrast shifts.
Alex: Wrapping this up, the work shows verification can be practical and revealing for real threats like blurring, balancing speed with rigor despite scaling hurdles—grounding safety claims in math for apps like self-driving cars. Thanks for breaking it down, Sam—fascinating look at securing neural nets mathematically. Thanks for listening to ResearchPod.