Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models

[Part 2/n] Q6) Many important definitions and almost everything concerning backdoors in LLMs are only present in the appendix. A6) Thank you for your comment. Unfortunately, due to the lack of space, we had to move some content to the appendix. If the paper gets accepted, we will utilize the extra space to move part of the discussion regarding LLMs to the main body. Q7) It is unclear why anyone would want to train an ANN, convert it to a binary circuit, obfuscate the boolean circuit, and then convert it back to an ANN if no backdoor should be injected. If a malicious company would train a model like that for a customer, the customer would ask why the model is trained this way. A7) This is a good point worth clarifying. Our construction aims to show a fundamental limitation of DNNs and LLMs by illustrating a concrete backdoor attack with strong theoretical guarantees. In practice, one could use some heuristic method in order to obfuscate the honest function $f$, and we believe that it would still be hard to distinguish between the (heuristically) obfuscated version of $f$ and the obfuscated version of some backdoored version of $f$. Moreover, we believe that there are legitimate use-cases where adding an obfuscation step before the release of the model could be part of an honest training pipeline, and should not constitute on its own an attempt from the company to do something malicious with the model. Consider the following motivating examples: - Privacy of Training Data: If the training data includes sensitive user information, using obfuscation could help ensure that this data remains private and secure. - IP Protection: Companies often have proprietary models. Applying obfuscation allows these companies to publicly release their models with less risk of reverse-engineering their models or techniques. If we allow the use of obfuscation then, our claim is “that an obfuscated version of the original model is indistinguishable from the backdoored one”. And due to the general utility of using obfuscation we consider such a recipe not suspicious. The main reason that we transform an ANN to a binary circuit and then back to an ANN is to argue that there exist theoretically grounded methods of obfuscation of ANN. In any practical scenario we do not envision this obfuscation procedure to be followed. Nevertheless, our backdoor can be added even if the company is using a heuristic obfuscation method for legitimate reasons, as the ones we mention above. If the heuristic obfuscation approach has similar properties with iO in practice then our backdoor is still undetectable. We will clarify these points for the final version of our work. Q8) The undetectability of the backdoor assumes that there exists a procedure "Perturb", such that the backdoor is not detected. However, it is unclear whether such a procedure exists. So, big parts of the paper are based on assumptions for which it is not known whether these assumptions hold in reality. A8) There might be a misunderstanding here. The Perturb function that we use is iO. As we explain in Assumption 9, and Lines 212-213 right below it, the recent breakthrough result of Jain et al. [2021] has shown that indistinguishability obfuscation (iO) does exist, by combining standard tools from cryptography. Following standard nomenclature from cryptography we list the existence of iO as an assumption but this is only because we do not have an unconditional proof for the hardness of problems, like factoring, that are used for security reason in many aspects of our everyday life, e.g., internet and credit cards. In that sense, formally, it is an assumption that factoring is hard and in exactly the same sense it is an assumption that iO exists. But, since 2021 we do have constructions of iO whose security is as good as the security of important and widely used cryptographic protocols. We hope that this clarifies this point and we are more than happy to elaborate more if something is still not clear. Limitations: The limitations of the proposed approach are not discussed. We will explain the limitations of this approach, which is a theoretical construction for planting backdoors and, at its current form, is not practical, in the final version of our work. We will also clarify the suggested pipeline that can be based on heuristic obfuscation approaches. Nevertheless, this approach highlights vulnerabilities of current DNNs and LLMs, and should be taken into consideration.

Part[2/n] Q2: Here is the main question which I have about the definition of undetectability. Correct me if I'm wrong, but with your definition, aren't undetectable backdoors very easy to construct? For instance, suppose my procedure Backdoor adds a 3-SAT verifier into the neural network, where the input variables to the circuit are taken as the output of some map from the input to [0, 1]^N (say, the parity of each digit of the input if it's an MLP, or whether each word is a noun in a language model). Then, if the 3-SAT circuit is satisfied, the model gives a bad output. The procedure Perturb does the same thing, except it inserts an unsatisfiable 3-SAT circuit, so . Efficiently being able to distinguish between and seems impossible since this would necessitate an efficient method for being able to tell which of two 3-SAT circuits is satisfiable, and which isn't; however, the actor who inserted this backdoor could easily sell information on how to activate the backdoor in the backdoored model (make sure your third, seventh, ninth... words are nouns). [and if we want it to be non-replicable use one of the steg methods from the appendix] If this is true, isn't allowing Perturb to be an unbounded function perhaps too powerful? Like, the backdoor described above still seems undetectable by your definition, but if someone actually looks at the weights of the model, they'll go like "whoa, what is this sus-looking boolean circuit doing here?". Ideally it seems like we'd want Perturb to either be restricted in some way, or perhaps the distribution of weights of , or its computational graph, should not be super out-of-distribution for other models sampled from . Basically, on first glance it seems to be that the definition of undetectability might be a bit weak (but of course, I am likely missing something.) A2: This is indeed a very astute observation; a construction similar to the one you define was actually the starting point of our work. First, let us clarify why the approach of injecting a SAT formula that is either satisfiable or unsatisfiable does not give a provably undetectable backdoor. According to our definition, which follows the blueprint of Goldwasser et al., a backdoor is undetectable if **any** (polynomially bounded) adversary cannot distinguish between an honestly generated model and one with a backdoor. If we inject a specific satisfiable formula in the honest case, then there exists a simple adversary, that checks whether a hardcoded assignment is satisfiable, succeeds. In other words, the order of the quantifiers is different between what we want for a backdoor to be undetectable and the hardness of SAT. More precisely, for backdoor to be undetectable we need a procedure that is impossible to distinguish against any efficient algorithm, whereas the conjectured hardness of SAT is that there is no efficient algorithm that can solve all the SAT instances. We hope this clarifies the issue but we are happy to elaborate more if needed. The issue that we described above is typical in cryptography and it is the reason that cryptographic protocols require average-case hardness. Unfortunately, SAT is not average-case hard, so our solution to this issue is to use instead the well-studied cryptographic primitive of PRGs: instead of a SAT formula, we include a number that is either pseudorandom or truly random. Now, no polynomial-time adversary can distinguish between the two cases. As you also correctly pointed out, this is indeed a very suspicious construction and someone by looking at the weights of the NN will be skeptical about what is going on. The main point of the construction we provide, and for using iO, is that iO (or a function similar to that) can be part of a legitimate *non-suspicious* real-world training pipeline. Ideally, we want the function “Perturb” to be non-suspicious. We argue that using obfuscation is on its own not suspicious for many reasons. Consider the following motivating examples: - Privacy of Training Data: If the training data includes sensitive user information, using obfuscation could help ensure that this data remains private and secure. - IP Protection: Companies often have proprietary models. Applying obfuscation allows these companies to publicly release their models with less risk of reverse-engineering their models or techniques. If we allow the use of obfuscation then, our claim is “that an obfuscated version of the original model is indistinguishable from the backdoored one”. And due to the general utility of using obfuscation we consider such a recipe not suspicious. We will elaborate on these points, and we will explain what types of “Perturb” function we allow for.

[Part 3/n] Q3: This is even more of a half-baked thought than (A), but if we're relying on the existence of iO as an assumption, can't we also then just assume FHE and just have Perturb encrypt all the models so nobody knows what's going on at all. A3: This is also an interesting thought: your suggestion is to publish the encryption of the neural network weights under an FHE encryption. Unfortunately, this approach does not directly work, since FHE will only allow us to compute an *encryption* of the output of the neural network on any given input. It won’t be possible to get the actual output of the NN unless we have the secret key of the encryption, which would also reveal the model weights. We will revise our manuscript according to our rebuttal. As we discussed above , currently, our theoretical result relies on an impractical construction. However, i) in the future we might have more practical iO algorithms, ii) our construction can work in practice with methods that simulate iO but do not have the strong theoretical guarantees we obtain. Moreover, we will elaborate on the “Perturb” functions our definition allows for.

> A1 We will restructure the paper and LLM content to the main body. > A4 (part 1) The intuition for using a PRG can be explained nicely by the strawman solution proposed by Reviewer paZi: A backdoor should be a part of the code that can be activated if we know some information that nobody else can efficiently find. A strawman solution would be to add a SAT instance: if the instance is satisfiable, then anybody with the satisfying assignment can activate the backdoor. If it is not satisfiable, then there exists no backdoor. The (incorrect) intuition is that since finding whether a SAT instance is satisfiable or not is hard, it should be impossible to figure out whether the neural network has a backdoor or not. This intuition does not directly work, as we explained to Reviewer paZi, and to make it work we have to replace the SAT with a PRG. We are repeating our answer to Reviewer paZi for an explanation on why this strawman solution does not work. According to our definition, which follows the blueprint of Goldwasser et al., a backdoor is undetectable if any (polynomially bounded) adversary cannot distinguish between an honestly generated model and one with a backdoor. If we inject a specific satisfiable formula in the honest case, then there exists a simple adversary, that checks whether a hardcoded assignment is satisfiable, succeeds. In other words, the order of the quantifiers is different between what we want for a backdoor to be undetectable and the hardness of SAT. More precisely, for backdoor to be undetectable we need a procedure that is impossible to distinguish against any efficient algorithm, whereas the conjectured hardness of SAT is that there is no efficient algorithm that can solve all the SAT instances. We are happy to elaborate more if needed. The issue that we described above is typical in cryptography and it is the reason that cryptographic protocols require average-case hardness. Unfortunately, SAT is not average-case hard, so our solution to this issue is to use instead the well-studied cryptographic primitive of PRGs: instead of a SAT formula, we include a number that is either pseudorandom or truly random. Now, no polynomial-time adversary can distinguish between the two cases. We will add this explanation to our paper to give intuition about the use of PRGs. For the digital signatures, the intuition is quite simple: the PRG (as the SAT formula) only requires one value to activate the backdoor. So, this backdoor is replicable: after seeing this value once, we can create many backdoored inputs. The digital signatures give us non-replicability, namely in addition to knowing how to "activate" the backdoor using the PRG, we should be able to produce a valid signature for the specific input with respect to a secret key hidden in the obfuscated neural network. Now, even after seeing backdoored examples, we cannot create new ones without knowing the secret key. For the non-replicability part of our construction to work, it is essential that the final neural network is obfuscated. Otherwise, anybody that inspects that NN would be able to see the secret key corresponding to the digital signature scheme. Even though outputting obfuscated NNs might seem suspicious, we believe that there are legitimate use-cases where adding an obfuscation step before the release of the model could be part of an honest training pipeline and should not constitute on its own an attempt from the company to do something malicious with the model. Consider the following motivating examples: -Privacy of Training Data: If the training data includes sensitive user information, using obfuscation could help ensure that this data remains private and secure. -IP Protection: Companies often have proprietary models. Applying obfuscation allows these companies to publicly release their models with less risk of reverse-engineering their models or techniques. If we allow the use of obfuscation then, our claim is “that an obfuscated version of the original model is indistinguishable from the backdoored one”. And due to the general utility of using obfuscation we consider such a recipe not suspicious. The theoretical guarantees for our construction are based on using a specific type of obfuscation called indistinguishability obfuscation (iO). The recent breakthrough result of Jain et al. [2021] has shown that indistinguishability obfuscation (iO) does exist, by combining standard tools from cryptography. > A4 (part 2) You are right that the backdoor is activated only when $PRG(X_{PRG})=PRG(S∗)$ and this happens with extremely small probability unless we know $S*$. If we already know $S*$, then we can just set $X_{PRG} = S*$ to make sure that the backdoor is activated. So, the fact that it is hard to find $S*$ is necessary so that only people that know the backdoor can activate it. On the other hand someone that knows $S*$ can activate the backdoor whenever they want. This creates a usable but undetectable backdoor.