I've only read the paper once just now, but if I understand correctly, this idea is essentially exploiting overfitting by the oracle.

Think of it this way: if a model is not overfitting in the region near a certain example input, then it means there is good generalization in that region. Perturbations around that example will remain correctly classified. If a model is overfitting near an input (think of a classic case of overfitted high-degree polynomial regression) then a tiny perturbation in that region can lead to an unstable change in the output.

Another way to think about it is to ask: why wouldn't this sort of thing work against a simpler algorithm like linear regression? I don't know that I am correct in my hunch that it wouldn't. But my feeling is that it wouldn't precisely because of the linear link function. If you perturb the inputs, even in a high-dimensional input space, you're only going to get at most a linear effect in the size of the perturbation, so the output on the true example and the adversarially perturbed example would, by construction, always be pretty similar. In other words, the adversarial example could either be plausible-looking, but not produce a great error in the oracle's output, or else it would have to be ridiculous-looking to produce that error, since the simple linear model does not present any regions of overfitting to exploit. (Of course, the linear model may not be good enough ... I'm not saying linear models are superior ... just trying to think about how overfitting is related to this.)

The algorithm works by training a companion model to the oracle model (the model you want to attack), such that a certain gradient structure may likely be correlated between the two models. That gradient structure in the companion model is then used to make perturbations around plausible inputs to the oracle, and evaluate the chances that the perturbation will lead to one of the unstable changes in oracle outputs (e.g. how likely is it that the oracle was overfitted in that region).

The whole paper seems to have a lot of connections to the idea of boosting, but almost in reverse. In boosting, you want to clamp exemplars that you demonstrably get right, and then re-train using example you get wrong (with weights shuffling the importance more and more onto what you get wrong).

It suggests to me that this technique could also be used as the basis for 'boosting' the original oracle classifier. You can produce the adversarial examples that are likely to be misclassified, and then go back and augment the oracle's original training set with these adversarial examples with their correct labels.

In a sense, you would be putting synthetic examples into the training set at the places where you most anticipate the model would otherwise overfit.

Then you could do rounds of this, iteratively, and probably with various weighting schemes, and all sorts of other permutations that could pump a few hundred people through their PhDs.

I wonder if the output of re-training with these "high leverage" sythetic / adversarial points would then lead to an overall classifier less susceptible to this type of attack? Maybe if you do enough iterations of this attack-then-retrain process, there cease to be the types of overfitted regions exploited by the attack. And how much would it degrade accuracy in these regions?

It also suggests adding an "attackability" metric to the model's overall cost function, and I wonder how much that is just going to look exactly like a regularization term...