9 ms·
Keras reimplementation of "One pixel attack for fooling deep neural networks"
- goldenkey 9y agoAren't these attacks just proof of the fact that even deep neural networks are approximating a high dimensional function by clamping the entropy of the formula, rather than truncating the range of input/output values? For a 32x32 image, the space of 1-pixel attacks is 0xFFFFFF * 32 * 32 = 17179868160 = e^23 Expecting an input space as large as that to not poke through the entropically deprived network is destined to fail.
- eximius 9y agoI mean, you don't even need a proof of that. The latter is impossible since the range of input/output values is untruncated by construction?
- tomhallett 9y agoI'm very new to ML, so I understand about 50% of what @eximius and @goldenkey are saying, but definetly not 100%. can anyone explain it in a bit more detail? (im assuming "entropy" is the key concept i need to put on my learning queue.) “approximating a high dimensional function by clamping the entropy of the formula, rather than truncating the range of input/output values” “not poke through the entropically deprived network is destined to fail” “the range of input/output values is untruncated by construction”
- deleted 9y ago[deleted]
- tomrod 9y agoI presume you have a regression background. If so: "minimizing entropy" is the same paradigm as "minimizing the sum of squares", in a different context. If not: reducing entropy means finding weights/coefficients in a supplied functional form that minimize some objective function applied to the problem. Usually the jargon applies to Shannon entropy from signal theory, or some derivation thereof like transfer entropy. Entropic estimates take a form similar to $$ -\sum(j) {p(x_j) log(p(x_j))}$$ where j is the event space (e.g. heads or tails on a coin flip).
- eximius 9y agoIf I have a function f(x,y, z) = <some expression> \in R^5 (i.e., f: R^3 => R^5) that is hard to compute, I can train a neural network to approximate it such that there are three input neurons x', y', z', some hidden layers doing the approximation, and 5 output neurons representing the approximation of the input. By construction, the domain and codomain are not constrained. Both the original and our approximation using NN take any three real values and return any five real values. Next, consider a sample of points from some function. I can perfectly fit those points using a polynomial of degree equal to the number of points by just setting f(x) = (x-y_1)(x-y_2)... If, however, I approximate the function by removing some degrees from the formula, I remove information (entropy) from the formula. It is no longer a perfect match, but it might be very close. Or, if the underlying distribution is of low dimensionality, it might still be an exact match (i.e., picking any number of points from a straight line doesn't mean you need a high degree polynomial to approximate it!).
- madez 9y agoThe set of all mappings between an input set of N elements to some output set with M elements has M^N elements. If you wanted to be able to represent in some way any arbitrary mapping for given sets of input and output, then you would need at least log_2(M^N) = N x log_2(M) bits. In the case of an input set of 32x32 pixel images with 3 bytes per pixel (one for each channel) we have N = 2^8 x 2^8 x 2^8 x 2^5 x 2^5 = 2^34. In the case of an artificial neural network we have at the last level an output. There will be at least one node with at least one bit of output, so M >= 2. In general, to have anything else but the trivial map that maps every input to the same output, we always have M >= 2. So, we need at least 2^34 x log_2(2) = 2^34 bits to represent an arbitrary function between the input and the output. That is 2 gibibytes! Since the models don't need 2 gibibytes, something is going on. The magic here is that we are able to encode subsets of possible mappings very efficiently by using the execution logic of a computer. The compressed representation of the mappings in the restricted subset are the learned weights (the code to evaluate the model is also needed, but that requires less bits than what we save). We are, in a way, compressing functions, not data. Hence the "clamping of entropy of the formula". [0] The restricion of the set of possible functions will lead to new, interesting phenomena. Think of it as compression artifacts, however not on images or audio, but functions. To make a model resistant to attacks by someone knowledgeable about these artifacts, I would add noise to the input such that the artifacts are not predictable, hence not practically attackable. [0] The same basic phenomenon happens with block ciphers in cryptography. A block cipher on one block is just a permutation of the set of all different input blocks. If you have a blocksize of 64 bits, representing an arbitrary permutation would need log_2(2^64 !) bits, where the exclamation mark stands for the factorial. That number is huge, bigger than 2^69. We can't represent arbitrary permutations of blocks of 64 bits. Yet, block ciphers are permutations. What happens here is that once again we find subsets of the possible permutation we can represent efficiently. The compressed representation is the key.
- eanzenberg 9y agoI’m not sure adding noise to the inputs of an equally complex model will change the information load of the NN. Because of the compression of the NN I think there will still exists new input pertubations which generate attacks.
- aje403 9y agoBrick shattering through window hypothesis finally has evidence No seriously - am I missing something? "Recent research has revealed that the output of Deep Neural Networks (DNN) can be easily altered by adding relatively small perturbations to the input vector." "Submitted on 24 Oct 2017 "
- rlayton2 9y agoMy guess here is that we need to learn more about adding noise to datasets before they go into a neural network. Lots of existing work do alterations like transposing, rotating, flipping and so on. Adding noise, including known attacks, would be part of this.
- goldenkey 9y agoNoise will definitely help if random noise is added to every input image before the neural network sees it, in production. Essentially, a pre-input pipeline state that a bad actor cannot predict, making single pixel deception totally neutered. I think what needs to be done here is to add a threshold of correlation between the input pixels. Consider that the problem is that 1 pixel change in the deviously right way, can be equivalent to the change when multiple pixels are changed in the proper way -- the derivative of the cost function. So clearly there needs to be a way to design / tell the network that 1 pixel change cannot be nearly as strong as changing multiple pixels relationships, in terms of cost function value change. From what I can garner, the only way to accomplish this is to make sure the number of nodes in the hidden layers is strictly monotonically decreasing. By using the last layer as a "grab bag" for classification, with 100s of nodes greater than the previous layers, the network becomes vulnerable to single pixel attacks. There have to be ways to design classification styles networks without the fan-out.
- wickedlogic 9y agoHow well does this fair over several frames?
- SurgeonOfDeath 9y agoCan we use one pixel attack to train network? We would generate adversarial examples to train network. Having ability to create Training Set that maximizes learning factor for NN sounds amazing but I think we would run to other adversarial examples.
- haraldurt 9y agoAugmenting your training dataset with adversarial examples is known as adversarial training, see e.g. [0] for a recent overview with empirical results. This seems to be a good first step in defending against such attacks, though the most naive approach of adversarial training doesn't work as well as you'd expect. [0] https://openreview.net/forum?id=rkZvSe-RZ https://openreview.net/forum?id=rkZvSe-RZ
- hajile 9y agoThere are a nearly infinite amount of forgery possibilities. The best solution seems to be making multiple networks with different approaches and training sets. Use a consensus or refer to a human if there is none. Finding holes should become harder with this approach.
- 7dare 9y agoIsn't the fact that it's one pixel of a 32*32 image relevant? I'd be more impressed to see a neural network be succesfully attacked by a single (or dozens) of pixels on a full-res image.
- xvedejas 9y agoThe fact that a human isn't fooled by the attack (we can still recognize the 32x32 images for what they are), points to an interesting gap in the abilities of conventional convolutional neural nets.
- bpicolo 9y agoNot a new concept in general, just a new approach for it with a single pixel change.
- deegles 9y agoThat's only because the attack is designed to target that particular network. Just wait until we understand real brains better and can generate tailored attacks...
- lbearl 9y agoIsn't that basically what an optical illusion is?
- alex_anglin 9y agoPlus cognitive biases. Those are already well understood and used in a variety of ways.
- smsm42 9y agoYes, and also this: https://en.wikipedia.org/wiki/Dazzle_camouflage https://en.wikipedia.org/wiki/Dazzle_camouflage Hacks human brain rather efficiently.
- 9y ago
- xvedejas 9y agoI wonder how well capsule networks could deal with this, considering they're more robust than traditional CNNs towards other sorts of adversarial attacks. My guess is that one-pixel changes are going to do very little to alter pose information (though they will still alter the confidence of the feature existing), and so caps nets should be more robust here as well. Does anyone know if my intuition is correct? Link to the capsule network paper, for those who haven't heard of it: https://arxiv.org/abs/1710.09829 https://arxiv.org/abs/1710.09829
- dahart 9y agoI suspect the same, that this kind of attack won't work on capnets. Note that "test on capnets" is on the list of not-yet-complete milestones.
- tomrod 9y ago... We should do this. I learn capnets, you get feather in cap?
- hyperparticle 9y agoAuthor of the repo here. I'm training a capsule network right now, will report back on results in the README in 24-48 hours. My hypothesis is that capsule networks are vulnerable as well, but we'll see by how much.
- hyperparticle 9y agoSo I did some preliminary testing with CapsNet, and it seems that while it was harder than all the other CNNs to find adversarial pixels to fool the network, it was still vulnerable to attack. See the README for quantitative results.
- eanzenberg 9y agoI’m not sure capsules will change the security much. We’re talking about pixel level attacks while capsules are trying to generalize at larger length scales (rotational/translational invariance).
- abledon 9y agoDoes anyone else wonder if their usage of the word "THICC"[1] in their meme, inadvertently comes off as sexist? [1] https://www.urbandictionary.com/define.php?term=Thicc https://www.urbandictionary.com/define.php?term=Thicc Great work! risky intro picture.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- notaspider 9y agoTHICC is a meme
- jamesgeck0 9y agoUrban Dictionary has prominent offensive definitions for most entires; it's not a great source for what you're trying to demonstrate.
- agitator 9y agoThis is really interesting, but points out a key importance in training neural nets, which is to design your dataset and training to maximize generalization. For example, in the case of training a neural network for something that is highly safety critical, like an autonomous vehicle, it's important for vehicle and pedestrian detection to be as generalized as possible. In order to achieve high confidence in all sorts of lighting, weather, and angle conditions, the training data is augmented, which means it is manipulated randomly with color, saturation, contrast, blurring, shifting, mirroring, adding noise, etc. So adding random pixels, to potentially protect against dead pixels is also a great idea.
- legohead 9y agoWalk around in the city with a giant yellow square costume and observe the mayhem...
- blackRust 9y agoDressing up as traffic signs might become a thing...
- mattigames 9y agoI'm pretty sure that's already illegal on many countries.
- icc97 9y agohttps://xkcd.com/1958/ https://xkcd.com/1958/
- stochastic_monk 9y agoI recently saw a yellow banana-man in a moshpit at a metal show. Don’t put breaking expectations past humans. We are adversarial by nature.
- tomrod 9y agoJumping on top comment (which I completely agree with) to ask: Why wouldn't a K-fold cross validation enable catching this? I'm curious if the attack adds doubt, in that the prediction algorithm is _close_ to truth but gets confused (likelihood of horse slightly less than dog), versus incorrect certitude (the horse is definitely a dog). One could then attach a weighting, perhaps based on max RGB/CYMK vector norm between two pixels across the image, to the folds' difference in top two certitudes. I don't know, something like that.
- knolan 9y agoI’ve mentioned this before but a median filter would nuke the single outlying pixel without too much of an effect on the input image. Is there an attack that can get past such a basic preprocessing step?
- deleted 9y ago[deleted]
- wepple 9y agoThis is interesting. I guess then you’d want to focus not on a single pixel but a collection that will still retain some value once filtered. It would be an interesting experiment.
- chillee 9y agoAssuming you're talking about adversarial examples in general (a one pixel attack would definitely be stopped by a median filter), yes. Median filters, gaussian filters, gaussian noise, all don't provide significant barriers against attack.
- derivt 9y agoWe need to define the derivative of a deep model. I mean a way to measure how a model change when we change one pixel in the training data. Since pixel -> feature -> margin, we need to define the derivative with respect to a natural parameter, the natural parameter of the model has to defined ad hoc for every application. Perhaps the natural parameter encodes an uninformative prior. The intuition is to use information theory to see how the discriminative power of the model change when the training data is perturbed. So we need to measure the derivative of the added information. Fisher information seems to be related to this.
- derivt 9y agothis paper https://openreview.net/forum?id=HJC2SzZCW https://openreview.net/forum?id=HJC2SzZCW suggest that sensivity is related to poor generalization power. To define derivative we need to use a natural parameter in such a way that it measures sensivity and also allow us to use methods from calculus and manifolds, such as parallel transport of features. How a DNN label a cat when is catching a rat.
- derivt 9y agoIf in a DNN for label a cat we explore the group of movements of the animal cat (realistic movements available for a cat) we could relate the discriminative power of the DNN to the energy of the cat. The energy of the cat is related to the volume of the group of movements. A cat with zero energy has the identity group of movements (no movement), a hulk cat is able to alter many of her features, so a very power model is needed to identify a hulk cat. A person full of rage is able to change the color of her face, again energy alter training space. Sorry for using HN for thinking.
- derivt 9y agoGiven that DNN are deep, what a one pixel attack means is that one pixel change propagates through the map of features: one pixel => 0-level-feature change -> one 1-level feature change. So this attack relies in weak features that can easily propagate to next level of features. Hence, to defend against this attack the model should put a threshold on the ratio (sensitivity of features)/(number of pixels) and avoid features with high sensivity to easily propagate to the next level of the DNN. If features are not linearly related to input set, then correlation is not a measure of feature sensitivity and has nothing to say about the full DNN effect of such change in a pixel.
- derivt 9y agoThis kind of attack relies on a low margin DNN, see (1), a low spectral norm of the input-output jacobian matrix guarantees good generalization error. So a one pixel attack exploits a weak eigenvalue (small absolute value) of the jacobian matrix. So to create a one pixel attack, compute: 1)the eigenvalues of the jacobian of input-ouput matrix, 2) takes the the smaller eigenvalue lambda_1 3) compute or approximate the function lambda_1 = f(input) 4) compute j = argmax_{i=1..n} d(lambda_1)/d(input_i) at the point in which the spectral norm is maximum. So to create the attack change the j-pixel in the points of the training set that has maximum (or high) jacobian matrix. (1) https://arxiv.org/pdf/1605.08254.pdf https://arxiv.org/pdf/1605.08254.pdf
- mcintyre1994 9y agoDoes this work if you use data transforms augmentation so that the pixel isn't always seen in the same spot? You probably wouldn't do any panning/rotation etc. for CIFAR 10, but for most practical purposes you probably would do more augmentation and I wonder if that defeats this?
- icc97 9y agoBut does this mean that edge detection is also failing? If the neural network thinks a truck is a frog is it not recognising the vertical edges? Seeing the intermediate layer images would be interesting to see where in the process it failed. I keep thinking how kids often learn through labelled cartoon images. There the outline is more important. Perhaps we could pre-train networks first on outlines of images. Make sure that these are capable of handling adversarial techniques and then build from there.