A Theoretical Framework for Robustness of (Deep) Classifiers against Adversarial Examples

1 INTRODUCTION

• Small, hardly visible modifications can force machine-learning models, including DNNs, to misclassify regular test samples.Prior work generates such examples through perturbation searches and proposes defenses including denoising, adversarial training, and smoothness penalties.Source: §1 · pp. 1–2
• Prior studies are mostly empirical and leave open why adversaries succeed, what determines robustness, and how robustness relates to generalization accuracy.The introduction also asks which classifier components matter most and how robustness might be improved.Source: §1 · p. 2
• The paper argues that prior adversarial-example definitions overlook the task oracle and introduces strong-robustness with necessary and sufficient conditions.Its stated contributions connect robustness to feature representation learning and offer theoretically grounded directions for understanding and hardening DNNs.Source: §1 · p. 2

2 RE-DEFINE ADVERSARIAL EXAMPLES

• The section’s revised account includes the task oracle when defining adversarial examples, rather than evaluating only the learned classifier.The paper treats the predictor and oracle as functions for the same classification task.Source: §2 · p. 3, §2.1 · p. 4

2.1 PREVIOUS FORMULATIONS

• Earlier formulations perturb a correctly classified sample until the classifier misclassifies it, but may not capture whether the change is imperceptible to a human observer.The section introduces the oracle to formalize that observer’s task-specific judgment.Source: §2.1 · pp. 3–4

2.2 MEASURING SAMPLE DIFFERENCE IN WHICH SPACE? MODELING & DECOMPOSING f2

• The oracle is decomposed into feature extraction and classification, with its feature space X2 and distance d2 representing task-relevant sample similarity.For image recognition, background pixels need not matter to an annotator deciding whether an image depicts a handwritten “0.”Source: §2.2 · p. 4

2.3 REVISED FORMULATION

• The revised formulation measures perturbation using the oracle’s feature space, expressing the difference as d2(g2(x), g2(x′)).When the oracle is continuous almost everywhere, the paper says the formulation can be simplified.Source: §2.3 · p. 5

3.1 BACKGROUND: PREVIOUS DEFINITIONS OF ADVERSARIAL EXAMPLES

• Prior definitions describe adversarial examples as small perturbations that change a classifier’s output, while some security formulations use constrained distances or non-minimal modifications.The paper notes that its general formulation covers cases where the distance to a seed need not be minimal, unlike a minimum-perturbation formulation.Source: §3.1 · pp. 5–6

3.2 BACKGROUND: PREVIOUS ALGORITHMS GENERATING “ADVERSARIAL EXAMPLES”

• Attack-generation methods optimize perturbations to change classifier outputs, including gradient ascent, Box L-BFGS, fast gradient sign, and Jacobian-based saliency search.These approaches vary in their constraints and perturbation measures, including ℓ∞ for fast gradient sign and ℓ0 for JSMA.Source: §3.2 · pp. 6–7

3.3 BACKGROUND: RELATED WORKS IN A BROADER CONTEXT

• The broader literature includes poisoning, evasion, and privacy-aware attacks, alongside defenses such as randomness, feature selection, adversarial training, and formal adversarial models.This paper focuses on evasion attacks and extends the discussion to adversarial manipulation of test samples.Source: §3.3 · pp. 7–8

4.1 MODELING AND DECOMPOSING f1

• The predictor is decomposed as f1 = c1 ◦ g1, separating feature extraction from classification.The feature extractor may include implicit feature selection such as ℓ1 regularization.Source: §4.1 · p. 8, §4.2 · p. 8

4 DEFINE STRONG-ROBUSTNESS

• Strong-robustness describes a classifier that is always robust against adversarial examples according to the oracle.The section develops sufficient and necessary conditions for this property.Source: §4.2 · p. 8, §4 · p. 8

4.1 MODELING AND DECOMPOSING f1

• When f1 is continuous almost everywhere, topological equivalence between the predictor and oracle metric spaces is sufficient for strong-robustness.More generally, the theorem also gives a sufficient condition when this equivalence holds and the boundary-disagreement probability is below η.Source: §4.2 · p. 9

4.4 FINER TOPOLOGY OF (X, d′

• Table 3 states that strong-robustness is determined by feature extraction, while accuracy depends on both feature extraction and classification.Source: Table 3 · p. 10
• When f1 is continuous almost everywhere, it is strong-robust if and only if the predictor-induced topology is finer than the oracle-induced topology.The paper extends the analysis from metric spaces to pseudometric spaces on the input space.Source: §4.4 · pp. 9–10
• Without almost-everywhere continuity, finer predictor topology plus boundary-disagreement probability below η suffices; boundary points relate robustness to c1.The paper says it omits detailed coverage of these cases in the rest of the paper.Source: §4.4 · p. 10

5 TOWARDS PRINCIPLED UNDERSTANDING

• The section’s conclusions assume f1 is continuous almost everywhere; finding necessary and sufficient strong-robustness conditions without that assumption is left for future work.Source: §5 · p. 10

5.1 UNNECESSARY FEATURES RUIN STRONG-ROBUSTNESS

• With an unnecessary feature, a continuous-a.e. classifier is not strong-robust when its feature space strictly contains the oracle’s lower-dimensional space and both use norm metrics.The paper illustrates how perturbing the unnecessary dimension can flip the classifier while remaining close in oracle space.Source: §5.1 · p. 11
• The authors explain adversarial-example transfer across DNNs as potentially arising from similar unnecessary features and thus similar attack-gradient directions.They frame this explanation as a consequence of over-complete learned feature spaces.Source: §5.1 · p. 12

5.2 FEATURE SPACE IS MORE IMPORTANT THAN DISTANCE MEASURE USING NORM FUNCTIONS

• When classifier and oracle share a feature space and both metrics are norms, the classifier is strong-robust even if the norms differ.The paper calls this result “norm doesn’t matter” and says changing norms may not improve robustness.Source: §5.2 · p. 12

5.3 ROBUSTNESS AND GENERALIZATION

• Robustness and accuracy can diverge: extra unnecessary features can yield an accurate but non-robust classifier, while omitting necessary features without extras can yield a robust but inaccurate one.Using exactly the oracle’s features can support both strong-robustness and accuracy.Source: §5.3 · p. 12
• Strong-robustness alone does not ensure predictive value; the paper identifies better feature learning as a possible route to a classifier that is both robust and precise.A constant classifier is given as a strong-robust but useless example.Source: §5.3 · p. 12

6.1 ARE STATE-OF-THE-ART DNNS STRONG-ROBUST?

• Tests of four state-of-the-art DNNs show poor accuracy on malicious adversarial inputs, while performance on randomly perturbed inputs is much better.Source: §6.1 · p. 13
• The authors explain vulnerability through geometry: classifier-space spheres correspond to thin high-dimensional input-space ellipsoids, with thin directions aligning with adversarial perturbations.They note that minimizing an approximated input-space norm can target those thin adversarial directions.Source: §6.1 · p. 13

6.2 TOWARDS PRINCIPLED SOLUTIONS

• The proposed hardening directions include learning a better feature map and modifying or removing unnecessary features.The paper describes loss functions that encourage similar classifier outputs for oracle-similar inputs, and feature grouping that can squeeze perturbations into equivalent classes.Source: §6.2 · pp. 13–14
• Adversarial, stability, and Siamese training all improve base DNN performance against adversarial samples, but their hardening effects vary by task.Source: §6.2 · p. 14

6.2.1 CONNECTING TO PREVIOUS STUDIES HARDENING DNNS

• Existing hardening approaches differ in both their loss and how they generate nearby training pairs; output-distribution similarity may not ensure small feature-space distance.The paper contrasts random-noise and adversarially perturbed pairs and notes that the reverse implication need not hold for output-distance losses.Source: §6.2.1 · p. 15

• The paper revises adversarial-example definitions to include the task oracle, defines strong-robustness and its principles, and examines theoretically grounded directions for understanding and hardening DNNs.An empirical comparison of recent literature using the theorems is left for future work.Source: §7 · p. 15

8 ASSUMPTION: ALMOST EVERYWHERE (A.E.) CONTINUITY

• For almost every input, a classifier is continuous a.e. when some feature-space radius guarantees the same label for all inputs within that radius.The paper says most previous studies implicitly assume this property for both classifier and oracle.Source: §8 · p. 20

8.1 INDICATIONS FROM A.E.CONTINUITY ASSUMPTION

• Without a.e. continuity, the paper says a classifier is not robust to random noise because arbitrarily similar inputs with different labels occur for most inputs.The authors state that the non-continuous case is rare for a well-trained classifier.Source: §8 · p. 20, §8.1 · p. 21

8.2 MOST MACHINE-LEARNING CLASSIFIERS SATISFY THE A.E. CONTINUITY ASSUMPTION

• The paper gives logistic regression with bag-of-words features and SVMs with continuous feature representations as examples satisfying a.e. continuity.For the SVM example, the feature-space metric is defined from the kernel function.Source: §8.2 · p. 21

9.1 MORE ABOUT MODELING ORACLE f2

• Human visual recognition is described as progressive re-representation along the ventral stream, followed by relatively simple decision functions such as linear classifiers.The cited neuroscience work argues that this account fits the stream’s architecture and response properties; a thresholded weighted sum is given as a biologically plausible single-step decision.Source: §9.1 · p. 21
• For malicious-PDF detection, a Cuckoo sandbox checks whether a modified sample preserves the seed PDF’s malicious behavior by comparing behavioral signatures.The sandbox runs the variant in a virtual machine with a PDF reader and reports behavior including network API calls.Source: §9.1 · pp. 21–22
• The sandbox can serve as an oracle, but its computational expense and slowness help explain why machine-learning detectors are used for speed or efficiency.Source: §9.1 · p. 22

9.2 MORE ABOUT MODELING f1: DECOMPOSITION OF g1 AND c1

• The appendix frames f1 as a composition of feature extraction g1 and classification c1, while noting that decomposing an arbitrary f1 this way is difficult.For machine-learning classifiers, it proposes enumerating possible g1 functions from classic model families.Source: §9.2 · p. 22
• Candidate feature maps g1 include selected features, DNN layers before classification, and the feature space induced by an SVM kernel.Source: §9.2 · p. 22
• Regularization can act as implicit feature extraction; for example, ℓ1 regularization can push some parameters to zero.Source: §9.2 · p. 22

10.1 METRIC SPACES AND TOPOLOGICAL EQUIVALENCE OF TWO METRIC SPACES

• A metric assigns distances and satisfies non-negativity, identity of indiscernibles, symmetry, and the triangle inequality.Euclidean distance is given as a widely used machine-learning example; the RKHS distance is expressed using a kernel function.Source: §10.1 · p. 22
• A mapping is a homeomorphism when it is continuous, one-to-one, onto, and has a continuous inverse; the spaces are then topologically equivalent.Source: §10.1 · p. 22
• The section states the definition as an equation; accompanying prose describes h as continuous, one-to-one, and onto, and identifies δ1 and δ2 as two small constants.Source: §10.1 · p. 22

10.2 PSEUDOMETRIC SPACES AND FINER TOPOLOGY AMONG PSEUDOMETRIC SPACES

• The feature spaces X1 and X2 are key determinants of strong robustness, and the analysis is extended to the original space because X2 may be difficult to specify analytically.Prior studies often assume the oracle space equals the original space with a norm distance.Source: §10.2 · pp. 22–23
• In the original space, distinct inputs can have zero distance when feature maps discard differences irrelevant to either predictor, so ordinary metrics may not apply.A background-pixel change is given as an example; the section therefore uses pseudometric spaces.Source: §10.2 · p. 23
• A pseudometric satisfies non-negativity, symmetry, and the triangle inequality but need not satisfy identity of indiscernibles.Source: §10.2 · p. 23
• A classifier can be decomposed as f1 = c1 ◦ g1, with g1 mapping inputs into a feature space and c1 classifying there; the induced distance on inputs may be a pseudometric.The example feature map selects only the first three features, so inputs differing elsewhere can have zero induced distance.Source: §10.2 · p. 23
• Using separate pseudometrics for f1 and f2 on the same original space makes it possible to state necessary and sufficient conditions for f1’s strong robustness.Source: §10.2 · p. 23
• A topology is generated by open sets, and one topology is finer than another when it contains that other topology.The section notes that defining a metric directly on the original sample space is difficult.Source: §10.2 · p. 23

10.3 PROOFS FOR THEOREMS AND COROLLARIES

• Theorem 4.4’s proof establishes the finer-topology condition in both directions for strong robustness under its stated setup.The proof snippets show each implication and invoke almost-everywhere continuity of f1.Source: §10.3.1 · p. 24, §10.3 · p. 24

10.3.2 PROOF OF THEOREM (4.5)

• Theorem 4.5’s proof uses the finer-topology result to obtain the stated conditional probability equality.Source: §10.3.2 · p. 25

10.3.3 PROOF OF THEOREM (4.3)

• Theorem 4.3’s proof equates the conditional probabilities of f1 disagreement under the two topologically equivalent feature spaces.Source: §10.3.3 · p. 25

10.3.4 PROOF OF THEOREM (4.2)

• Theorem 4.2’s proof uses almost-everywhere continuity of f1 to obtain the stated probability-one agreement under the oracle-distance condition.Source: §10.3.4 · p. 25

10.3.5 PROOF OF COROLLARY (5.2)

• Corollary 5.2 follows because normed spaces Rn with the two stated norms are topologically equivalent.Source: §10.3.5 · p. 25

10.3.6 PROOF OF COROLLARY (5.1)

• Corollary 5.1 concludes that f1 is not strong-robust when the oracle-induced topology is finer than the predictor-induced topology.Source: §10.3.6 · p. 25

11.1 MORE EXAMPLES ABOUT g1 MATTERS FOR STRONG-ROBUSTNESS AND c1 NOT

• In the examples, f1 is strong-robust despite being inaccurate according to f2, and c1 does not determine strong-robustness.Case (c) concerns nearby samples that f2 assigns the same class but f1 assigns different classes; when f1 is continuous almost everywhere, this set has probability 0.Source: §11.1 · pp. 25–26

11.2 MORE ABOUT EXTRA UNNECESSARY FEATURES RUIN STRONG-ROBUSTNESS

• One extra irrelevant feature can preserve accuracy yet make f1 not robust to adversarial perturbation for almost all samples.The paper gives tiny-font spam words and superficial PDF features as examples of unnecessary features.Source: §11.3 · p. 26, §11.2 · p. 26
• When f1 is continuous almost everywhere, the probability in the stated condition is either 1 or 0; Cases (III) and (IV) have probability 1.The paper characterizes this as f1 being either strong-robust or not robust at all almost everywhere.Source: §11.3 · p. 26

12.1 MORE ABOUT ARE STATE-OF-THE-ART DEEP NEURAL NETS STRONG-ROBUST ?

• Experiments examine d1 properties across four state-of-the-art DNNs and report consistent conclusions across them; the authors note that many DNNs are not strong-robust.The reported testing includes random and adversarial perturbations on a 200-layer residual network trained on ImageNet.Source: §12.1 · p. 29

12.2.1 DEFINE ARC AND ARCA

• ARC measures robustness using both predictor f1 and oracle f2 via expected oracle-space distance to adversarial examples; ARCA combines ARC with accuracy.Ignoring the oracle can count perturbations as adversarial even when the oracle assigns the perturbed sample to a different class.Source: §12.2.1 · pp. 30–31

12.2.2 ARC AND STRONG-ROBUSTNESS

• ARC(f1)/δ2 = 1 if and only if f1 is strong-robust against adversarial examples.ARC is designed to reach its maximum value of 1 exactly when the classifier is strong-robust.Source: §12.2.1 · p. 30, §12.2.2 · p. 32

12.3 USING “SIAMESE ARCHITECTURE” TO IMPROVE DNNS’ ADVERSARIAL ROBUSTNESS

• Siamese training penalizes differences between middle-layer outputs for a seed input and its perturbed version, encouraging a finer topology relationship and potentially improving robustness.The two network copies share weights; the experiments use Euclidean distance for d1, though other choices are possible.Source: §12.3 · p. 32

12.4 COMPARING DNN HARDENING STRATEGIES EXPERIMENTALLY

• Experiments compare original, stability, Siamese, and adversarial training on VGG using MNIST and CIFAR-10, tracking top-1 accuracy, ARC, and ARCA under controlled fast-gradient-sign attacks.Attack power is varied, with perturbed image dimensions kept within the valid integer range from 0 to 255.Source: §12.4 · pp. 33–34

13.1 MORE ABOUT BOUNDARY POINTS OF f1 AND BOUNDARY POINTS OF f2

• Boundary-based attacks target seeds near f1’s boundary that f2 treats as same-class; these are not crucial under the common assumption that f1 is continuous almost everywhere.When f1 is continuous almost everywhere, the probability in Eq. (4.1) is zero; when it is not, that probability may be positive.Source: §13.1 · pp. 36–37

13.2 WHEN f1 NOT CONTINUOUS A.E., STRONG-ROBUST IS SIGNIFICANTLY INFLUENCED BY BOUNDARY POINTS OF f1

• When f1 is not continuous almost everywhere, adversarial-example probability reflects pairs that f1 separates but f2 treats as similar, so both representation g1 and classifier c1 determine strong-robustness.The section also describes an example with a finite sample space in which the decision boundary learned by f1 differs substantially from the oracle’s.Source: §13.2 · p. 37, §13.2.1 · pp. 37–38
• When f1 is not continuous almost everywhere, c1 matters for strong-robustness; with finite X, a wrong decision boundary, and many test samples near that boundary, f1 is not strong-robust, though this case is very rare for a well-trained classifier.Source: §13.2.1 · p. 38
• For f1 that is not continuous almost everywhere, obtaining more samples may help it learn a better decision boundary and improve adversarial robustness.Source: §13.2.1 · p. 38