DeepFool Algorithm
What you'll learn: How DeepFool finds the smallest possible adversarial perturbation by approximating the decision boundary as a linear surface and iteratively stepping across it.
The Core Idea
While attacks like FGSM and PGD use fixed step sizes or maximize loss functions, DeepFool takes a geometric approach: it asks "what's the minimal change needed to flip the prediction?" Think of it like finding the shortest path from your current position to the edge of a cliff (the decision boundary).
The key insight: even though neural networks are highly non-linear, locally around any point, we can approximate the decision boundary as a flat hyperplane. DeepFool linearizes the classifier's decision surface, then computes the perpendicular distance to the nearest class boundary.
How It Works
- Start with a correctly classified input x
- Linearize the decision boundary using the model's gradients
- Find the closest class in this linear approximation
- Take a small step perpendicular to that boundary
- Repeat until the prediction changes
Each iteration moves just far enough to cross the linearized boundary. Because the true boundary is curved, you might not cross it on the first try—hence the iteration. The algorithm stops when the model's prediction actually flips.
Why It Matters
DeepFool produces minimal perturbations—often smaller and more efficient than FGSM or PGD. This makes it valuable for robustness evaluation: if your model fails against minimal attacks, it's especially vulnerable. The algorithm also reveals which classes are "nearest" to each other in the model's decision space.
Key Takeaway: DeepFool finds minimal adversarial perturbations through iterative linear approximations of the decision boundary, revealing the shortest path to misclassification.