Executive Summary
Standard adversarial defenses often fail in security domains because attackers can make large, discrete changes—like rewriting code—that preserve functionality but successfully fool machine learning models. This paper introduces the Normalize-and-Predict (N&P) framework, which achieves provable robustness by training on "canonicalized" data. N&P significantly outperforms traditional adversarial training in both accuracy and computational efficiency.
The Problem: Relational Adversaries
Most research into adversarial machine learning focuses on $\ell_p$-norm bounded attacks. Think of this as changing a few pixels in an image so slightly that a human doesn't notice. However, in security-critical fields like malware detection or source code analysis, this continuous, geometric model breaks down.
An attacker can rewrite a piece of malware using different API calls or change a for loop to a while loop in source code. These are known as relational adversaries: they apply a sequence of transformations that drastically change the "syntactic" features (the raw input) while preserving the "semantic" meaning (the actual behavior).
Because these changes aren't "small" in a traditional mathematical sense, standard defenses that rely on local smoothness fail. Furthermore, finding the "worst-case" adversarial example in these discrete, high-dimensional spaces is often computationally intractable.
The Solution: Normalize-and-Predict (N&P)
The authors propose a framework called Normalize-and-Predict (N&P). The core idea is borrowed from a classic computer science concept: normalization (or canonicalization).
- Normalization: Before training or inference, every input is converted into a unique "normal form." For example, all
forloops might be converted intowhileloops. If an original input and its adversarial version both normalize to the same canonical form, the model is guaranteed to produce the same output for both. This makes the model robust by design. - Equivalence Groups: The paper formally defines "equivalence groups"—sets of inputs that can be transformed into one another via allowed logical relations. Normalizing by these groups ensures optimal robust accuracy.
- Unified Framework (N&P + Adversarial Training): Recognizing that some transformations are easy to normalize while others are not, the authors propose a hybrid approach. They normalize the "easy" relations and use adversarial training (AT) to handle the remaining, more complex transformations.
Key Insights and Efficiency Gains
- Robustness by Design: Unlike adversarial training, which tries to find and learn from difficult examples, N&P enforces robustness. If the normalizer is exact, the model is perfectly robust against any transformation within that equivalence group.
- The Robustness-Accuracy Trade-off: The paper analyzes how different patterns in logical relations affect the trade-off between clean accuracy and robust accuracy. For instance, if two different classes (e.g., malware and benign) can be transformed into the exact same input, a robust model must sacrifice accuracy on one of them.
- Massive Efficiency Gains: Adversarial training in discrete spaces is incredibly slow because it requires a complex search for adversarial examples in every training loop. N&P moves this complexity to a pre-processing step, making training roughly 40x faster than standard adversarial training in their experiments.
Experimental Results
The authors evaluated their framework on two distinct security tasks: Source Code Authorship Attribution (identifying the author of a C++ program) and Malware Detection (distinguishing between benign and malicious Windows binaries).
The N&P framework consistently outperformed both vanilla models and standard adversarial training (AT).
- Authorship Attribution: Against the strongest "Adaptive+" attack, the N&P-LSTM model maintained 49.9% accuracy, while the vanilla LSTM dropped to a useless 0.9% and the adversarially trained model (Adv-LSTM) only reached 25.2%.
- Malware Detection: The "Unified" (N&P + AT) detector achieved the highest robustness. Its False Negative Rate (FNR) under attack was only 5.5%, compared to 27.9% for standard AT and nearly 100% for the undefended natural model.
- Computational Overhead: Normalization added less than 12 hours to the training process, whereas adversarial training took over 20 days on the same infrastructure.
Limitations and Future Work
While exact normalization is ideal, it is often computationally hard, requiring the use of heuristic normalizers. Improving these heuristics is a clear path for future work. Additionally, the logical relations and normalizers currently must be manually defined by domain experts; automating the discovery of these relations would make the framework more generalizable.
Summary updated