3 ms·

> No [machine learning] system is 100% secure. That is what's being claimed without proof, when they meant "existing neural network systems are known to be ins

by j2kun 9y ago

> No [machine learning] system is 100% secure. That is what's being claimed without proof, when they meant "existing neural network systems are known to be insecure"

LolWolf 9y ago
Sure, you can't claim that every machine learning system is susceptible to this attack (here's one that isn't, a model that always returns the same class on all inputs). But (apart from obvious trivialities) I suspect this is a more general problem with interesting properties—the claim the GP is making boils down to something like: a non-trivial[0] machine learning model with large parameter space is, with vanishing probability (as the number of distinct training samples increases), robust to classes of eps-bounded attacks.[1] This seems like a provable claim that is well-defined and (in a weird, handwavy 'intuitive' kind of way) likely to be true... there are just way too many parameters and too much uncertainty in the local minima that we reach when training from such classes of examples to have 'robustness'. Perhaps I'm totally wrong, though, and someone will come up with a regularizer that prevents all of this from happening, but this seems highly not obvious to me, at first glance. --- [0] Non-trivial means that, say, it has non-vanishing curvature (Fisher information, assuming the model returns a vector of probabilities) almost everywhere. I hate to be so nitpicky, but I suspect someone would soon comment asking for definitions of all of these things and that the problem isn't 'well-defined.' [1] Given a (large enough) set of inputs, the max-norm difference between at least one input and the adversarial example must be ≤eps. In other words, if we want the model to misclassify 'turtle' with 'dog', we don't just give a dog picture---the adversarial picture must look like a turtle in a mathematical sense.
- comex 9y ago
  That’s a very strong claim, though, given that we’re explicitly talking about hypothetical future systems as opposed to “existing neural network systems”. After all, taking the definition of “machine learning” to the extreme, it could include a system based on simulating an entire human brain. So the statement would necessarily imply that either: (a) brain simulation is fundamentally impossible for some reason (insert your favorite argument for why this should be the case), or (b) epsilon adversarial examples exist that fool humans (we just haven’t found any). Personally, I think (b) is more likely than (a), but it seems much more likely that neither is true: that the human visual system is resilient at least to some extent (...for some epsilon), and could hypothetically be simulated by a machine. It would stand to reason that building a resilient system doesn’t require simulating a human, either, or nearly as much computational power as that would take (given that emulation is inherently very inefficient, and that visual processing only takes up a part of the human brain and seems to be done pretty well by animals with simpler brains). But it might require much more computational power than we have today… On the other hand, if you limit computational power to around today’s level, and consider only potential architectural changes, the statement seems more plausible to me.
  - LolWolf 9y ago
    Not only do I think (b) is more likely than (a), I think (b) is strictly true. I mean, our concentration is quite limited and there are optical illusions which are, perhaps even more strongly than eps-adversarial examples for a given architecture, very general problems. So, given a "brain-simulated ML" thing (whatever that may mean, but let's assume it's the case), I suspect there may be a way of coming up with even more striking adversarial examples—but, considering that architectures vary heavily between humans, I suspect this would be quite person-specific. Anyways, my final point is in saying that such a claim doesn't seem too far-fetched in any way. That being said: I could be totally and hilariously wrong.
- j2kun 9y ago
  Unfortunately, it is known that many classes of problems can be learned with adversarial manipulation of an epsilon-fraction of the training data. See for example the paper "PAC learning with nasty noise," though there are many other adversarial noise models in which resilience can be proven (though proving it even for a specific concept class would be enough to prove it wrong that "all machine learning systems are vulnerable").
  - LolWolf 9y ago
    But the claim the paper is making fits perfectly with the above: > On the negative side, we prove that no algorithm can achieve accuracy of ε < 2η in learning any non-trivial class of functions. Though this is for a very particular type of adversary which has a lot more power than I'm claiming. In my case, though, I'm strengthening the side that the adversary has a very large number (e.g. infinite, as my claim "N->infty") of possible examples in the training set to be eps-close to. --- Rereading the above: Sorry, I'm not quite sure I understood your point! Are you claiming that there is such a model which is resilient to adversarial examples, and also has a large number of parameters relative to the hypothesis class size? (e.g. say VC dimension?) In that case, my claim would be definitely false, but I have yet to see such a paper (if you have a reference, I'd love to check it out!)
shmel 9y ago
Really? I believe they meant exactly what they said. Read https://arxiv.org/abs/1605.07277 https://arxiv.org/abs/1605.07277 Adversarial examples can be easily crafted for linear regression, SVM, decision trees and k-NN at very least. I can't think about any ML technique that is proven to be secure against them. There is also an old blogpost from Karpathy describing that the only reason we are not concerned about adversarial examples in linear models is that nobody uses them to classify ImageNet.
- j2kun 9y ago
  Yes, many models are vulnerable. But there are no proofs that allow you to say that. You should also be aware that they're only talking about image classification in all of these. I will only accept blanket statements about "all machine learning systems" when there's a mathematical proof. I don't mean to lessen the importance of the work, just to point out that saying "X fails at Y on subtask Z using the techniques we have today" is very different from saying "All possible X's, current and future, fail at Y."

by j2kun 9y ago

> No [machine learning] system is 100% secure. That is what's being claimed without proof, when they meant "existing neural network systems are known to be insecure"

LolWolf 9y ago

Sure, you can't claim that every machine learning system is susceptible to this attack (here's one that isn't, a model that always returns the same class on all inputs). But (apart from obvious trivialities) I suspect this is a more general problem with interesting properties—the claim the GP is making boils down to something like: a non-trivial[0] machine learning model with large parameter space is, with vanishing probability (as the number of distinct training samples increases), robust to classes of eps-bounded attacks.[1] This seems like a provable claim that is well-defined and (in a weird, handwavy 'intuitive' kind of way) likely to be true... there are just way too many parameters and too much uncertainty in the local minima that we reach when training from such classes of examples to have 'robustness'. Perhaps I'm totally wrong, though, and someone will come up with a regularizer that prevents all of this from happening, but this seems highly not obvious to me, at first glance. --- [0] Non-trivial means that, say, it has non-vanishing curvature (Fisher information, assuming the model returns a vector of probabilities) almost everywhere. I hate to be so nitpicky, but I suspect someone would soon comment asking for definitions of all of these things and that the problem isn't 'well-defined.' [1] Given a (large enough) set of inputs, the max-norm difference between at least one input and the adversarial example must be ≤eps. In other words, if we want the model to misclassify 'turtle' with 'dog', we don't just give a dog picture---the adversarial picture must look like a turtle in a mathematical sense.

comex 9y ago
That’s a very strong claim, though, given that we’re explicitly talking about hypothetical future systems as opposed to “existing neural network systems”. After all, taking the definition of “machine learning” to the extreme, it could include a system based on simulating an entire human brain. So the statement would necessarily imply that either: (a) brain simulation is fundamentally impossible for some reason (insert your favorite argument for why this should be the case), or (b) epsilon adversarial examples exist that fool humans (we just haven’t found any). Personally, I think (b) is more likely than (a), but it seems much more likely that neither is true: that the human visual system is resilient at least to some extent (...for some epsilon), and could hypothetically be simulated by a machine. It would stand to reason that building a resilient system doesn’t require simulating a human, either, or nearly as much computational power as that would take (given that emulation is inherently very inefficient, and that visual processing only takes up a part of the human brain and seems to be done pretty well by animals with simpler brains). But it might require much more computational power than we have today… On the other hand, if you limit computational power to around today’s level, and consider only potential architectural changes, the statement seems more plausible to me.
- LolWolf 9y ago
  Not only do I think (b) is more likely than (a), I think (b) is strictly true. I mean, our concentration is quite limited and there are optical illusions which are, perhaps even more strongly than eps-adversarial examples for a given architecture, very general problems. So, given a "brain-simulated ML" thing (whatever that may mean, but let's assume it's the case), I suspect there may be a way of coming up with even more striking adversarial examples—but, considering that architectures vary heavily between humans, I suspect this would be quite person-specific. Anyways, my final point is in saying that such a claim doesn't seem too far-fetched in any way. That being said: I could be totally and hilariously wrong.
j2kun 9y ago
Unfortunately, it is known that many classes of problems can be learned with adversarial manipulation of an epsilon-fraction of the training data. See for example the paper "PAC learning with nasty noise," though there are many other adversarial noise models in which resilience can be proven (though proving it even for a specific concept class would be enough to prove it wrong that "all machine learning systems are vulnerable").
- LolWolf 9y ago
  But the claim the paper is making fits perfectly with the above: > On the negative side, we prove that no algorithm can achieve accuracy of ε < 2η in learning any non-trivial class of functions. Though this is for a very particular type of adversary which has a lot more power than I'm claiming. In my case, though, I'm strengthening the side that the adversary has a very large number (e.g. infinite, as my claim "N->infty") of possible examples in the training set to be eps-close to. --- Rereading the above: Sorry, I'm not quite sure I understood your point! Are you claiming that there is such a model which is resilient to adversarial examples, and also has a large number of parameters relative to the hypothesis class size? (e.g. say VC dimension?) In that case, my claim would be definitely false, but I have yet to see such a paper (if you have a reference, I'd love to check it out!)

shmel 9y ago

Really? I believe they meant exactly what they said. Read https://arxiv.org/abs/1605.07277 https://arxiv.org/abs/1605.07277 Adversarial examples can be easily crafted for linear regression, SVM, decision trees and k-NN at very least. I can't think about any ML technique that is proven to be secure against them. There is also an old blogpost from Karpathy describing that the only reason we are not concerned about adversarial examples in linear models is that nobody uses them to classify ImageNet.

j2kun 9y ago
Yes, many models are vulnerable. But there are no proofs that allow you to say that. You should also be aware that they're only talking about image classification in all of these. I will only accept blanket statements about "all machine learning systems" when there's a mathematical proof. I don't mean to lessen the importance of the work, just to point out that saying "X fails at Y on subtask Z using the techniques we have today" is very different from saying "All possible X's, current and future, fail at Y."