TL;DR
This paper introduces Feature Partition Aggregation (FPA), a novel defense mechanism that provides provable robustness against a broader range of adversarial attacks (evasion, backdoor, and poisoning) than existing methods. FPA achieves this by training an ensemble of models on disjoint feature sets, offering stronger guarantees and significantly faster certification times.
What Problem Does This Paper Address?
Machine learning models are increasingly vulnerable to adversarial attacks, where small, imperceptible changes to input data can lead to incorrect predictions. Existing defenses often focus on specific attack types, like evasion attacks, leaving models susceptible to others such as poisoning (corrupting training data) or backdoor attacks (hidden triggers). This paper addresses the critical need for a unified defense that can provably protect against a union of these common adversarial threats, particularly in scenarios with heterogeneous data where features might come from different sources.
Methods
The core innovation is Feature Partition Aggregation (FPA). FPA works by dividing the input features into disjoint subsets and training separate "submodels" on each subset. This ensemble approach is key: an adversarial perturbation affecting a feature will only impact at most one submodel. This allows FPA to provide certified robustness guarantees against attacks that modify any subset of features, including those that manipulate training data (poisoning) or combine training and test perturbations (backdoors).
FPA offers two decision functions for aggregating submodel predictions:
- Plurality Voting: A simpler scheme where the majority vote of submodels determines the prediction.
- Run-Off Elections: A more sophisticated, two-round voting process that leverages more submodel information to potentially achieve stronger guarantees.
The paper also defines a new paradigm: Certified Feature Robustness, which generalizes existing L0 (sparse) robustness to encompass training set perturbations.
Datasets
The authors evaluated FPA on the following datasets:
- Image Classification: CIFAR10, MNIST
- Tabular Regression: Weather, Ames
Key Insights and Ideas
- Unified Robustness: FPA is the first defense to offer non-trivial, pointwise robustness guarantees against the union of L0 evasion, backdoor, and poisoning attacks. This is a significant step towards more robust AI systems.
- Ensemble Power: By partitioning features and training submodels, FPA effectively isolates the impact of adversarial perturbations, leading to stronger, deterministic guarantees.
- Efficiency Gains: FPA is orders of magnitude faster than state-of-the-art L0 defenses like Randomized Ablation (RA), making provable robustness more practical.
- Model Agnosticism: Unlike RA, which is tied to specific model architectures, FPA supports any submodel type, including gradient-boosted decision trees (GBDTs) for tabular data.
- Feature Partitioning Matters: The way features are partitioned significantly impacts FPA's robustness guarantees. Deterministic partitioning (like "strided" for images) often outperforms random partitioning, especially for vision tasks.
Key Results
- Stronger Guarantees: FPA provides strictly stronger guarantees than RA, covering evasion, poisoning, and backdoor attacks, whereas RA only covers evasion.
- Speedup: FPA is up to 3,000x faster than RA for certification.
- Improved Robustness: FPA achieves larger median robustness guarantees (e.g., 20-30% larger for classification, 3-4x larger for regression) compared to RA.
- Competitive Accuracy: FPA maintains competitive classification accuracy, often outperforming RA at comparable robustness levels. For example, on CIFAR10 at a robustness of 10 pixels, FPA achieved 10.2 percentage points higher accuracy than RA.
- Run-Off Benefits: The run-off election decision function further improves FPA's certified accuracy, with improvements up to 12.3 percentage points on MNIST.
Limitations and Future Work
- Overlapping Feature Sets: While FPA can be extended to overlapping feature sets, this increases computational complexity and makes certification analysis NP-hard in the general case. The current formulation with disjoint sets is more efficient.
- Top-k Certification: While the paper extends FPA to top-k predictions, the greedy algorithm for overlapping feature sets is left as future work.
- Model Training Time: For vision datasets, FPA's total ensemble training time can be slower than RA, though its embarrassingly parallel nature offers advantages with sufficient hardware.
- Future Work: The authors suggest developing other Lp certified defenses over the union of attack types and exploring more sophisticated partitioning strategies.
Summary updated