Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models

[Part 1/n]

We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.

Q1) To me, the paper's contribution is not quite clear. Since Goldwasser et al. (2022) have already shown how undetectable backdoors can be injected into binary classification deep learning models, it is hard to tell what the novelty of this paper is. Underlining this, many of the assumptions and definitions are apparently taken from related work.

A1) The construction of Goldwasser et al. (2022) to plant backdoors to general NNs works only when the distinguisher has black-box access to the model, i.e., they cannot see the weights/architecture of the model, which we argue that it is a very important limitation of their work. Their construction to plant backdoors when the distinguisher has white-box access works for a rather limited family of training algorithms/models. Moreover, Goldwasser et al. (2022) do not touch the topic of LLMs. To the best of our knowledge, our work is the first to give a theoretical construction for planting backdoors in such models. We underline that we have listed our contributions in Lines 48-58 as well as Section 1.1 of our manuscript. Moreover, we have provided a comparison with Goldwasser et al. (2022) in Lines 129-142 as well as in Appendix C. For completeness, we reiterate some of these points below.

Our contributions can be listed as follows: We provide a modified (weaker) definition of planting backdoors, and we show how we can achieve undetectable planting under this definition under distinguishers that have white-box access to the model. We provide a construction that satisfies this definition and is based on iO. We provide similar definitions and constructions in the context of LLMs, which have not appeared in prior work. We show how Boolean functions can be well-approximated by quite compressed NNs (Theorem 14 in our manuscript), which we believe can be useful even outside the scope of our work.

Q2) There are multiple definitions and theorems for which it is not fully explained why they are needed. This makes it hard to read and follow the paper.

A2) Thank you for your feedback. We tried our best to produce a write-up that is consistent and within the page limits. For this we need all the definitions and theorems we have listed in our work but as you say in some places some additional explanation is missing due to the space limitations. That said, we put a lot of effort into being able to handle both NN classifiers and LLMs through a conceptually similar approach which reduces the need for extra space and makes the results easier to follow.

We plan to utilize the extra page of the camera ready version to elaborate more on several definitions and theorems and thus improve the presentation of our results. If the reviewer has any concrete suggestions about this we would be more than happy to hear them. .

Q3) There is no conclusion or discussion at the end of the paper. Instead, the paper abruptly ends.

A3) Thank you for pointing this out, we are happy to the following Conclusion section in the next version of our work: Given the plethora of applications of Machine Learning in general, and neural networks in particular, questions regarding the trustworthiness of publicly released models naturally arise. In particular, before deploying a neural network we need to guarantee that no backdoors have been injected allowing bad actors to arbitrarily control the model behavior. In this paper, we investigate the existence of backdoor attacks to obfuscated neural networks which are undetectable even when given white-box access. The notion of obfuscation that we consider is the well-studied and mathematically founded indistinguishability obfuscation (iO). We also show how our techniques can inspire backdoor schemes in large language models when combined with ideas from steganography.

While our constructions are purely theoretical, we leave as an interesting direction how to use heuristic obfuscation methods to show practical instantiations of our constructions. Another interesting open question is whether cryptographic schemes weaker than iO suffice to show backdoor undetectability in the white-box model.

Q4) There is no intuitive explanation on why all the parts (PRG, signature) are needed. Instead, the readers have to figure that out by themselves using the equations.

A4) We respectfully disagree with this comment. We believe that we explain why all the cryptographic tools that we define are needed. For example, we explain where PRGs are needed in Lines 260-266 of our manuscript. Similarly, we explain the use of signatures in these lines. Moreover, in Lines 278–281 we explain why digital signatures give us non-replicability. We are more than happy to elaborate more or modify the explanations if this improves our writeup but we have already put a lot of effort into this.

Q5) It is a bit confusing that the definition of a backdoored model always includes three models f, \hat{f}, and \tilde{f} . It would be much easier if the backdoored model were defined with two models--the original model and the backdoored model, which tries to mimic the original model while having a backdoor.

A5) Our main goal is to show that the obfuscated version of $f$ and the obfuscated version of the backdoored $f$ are indistinguishable. Since it is not clear how to directly compare the obfuscated version of $f$ with the obfuscated version of the backdoored $f$, we use some “intermediate” quantity in order to, intuitively, “chain” the equalities. This is mostly part of the theoretical analysis in order to derive the theoretical result. We underline again that our guarantee is established with respect to two functions: the obfuscated version of $f$ and the obfuscated version of backdoored $f$.

We will clarify that for the final version.

[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.

We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.

Q1: The Section 4.2 is a bit too compressed as it does not even define the steganographic function. The presentation would be more balanced if the language model section were fleshed out a little more in the main text.

A1: Thank you for your suggestion. Unfortunately, due to space constraints, we had to move some of the discussion to the appendix. We will re-organize the paper and, if it gets accepted, we will utilize the extra page to bring some of the content from the appendix to the main body.

Q2: Is there any setting where this backdoor is practical where [1] was not? Basically I assume there would need to be a setting where the user is willing to accept a network that looks like Plant(f, 0)? I assume normally the user would expect to receive f so I assume they would be suspicious if they received Plant(f, 0) instead (even though no backdoor was inserted). Is there a scenario where the user is expecting to receive something looking like Plant(f, 0)?

A2: This is a great question, and thank you for bringing this up. First, we would like to point out that the generic construction of [1], that does not make strong assumptions on the training process, holds only in the regime where the distinguisher has black-box access to the classifier, i.e., they do not have access to the weights. The main point of the construction we provide, and for using iO, is that we believe iO (or another obfuscation technique) can be part of a legitimate non-suspicious real-world training pipeline. In other words indeed “Perturb” can be unnatural but the “Perturb” procedure that we use, i.e., obfuscation, is natural and we can expect it to be used as the last step of any training process for the following reasons:

• 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.

Another way to interpret our results is hence that we do not modify $f$ but we assume that the last step of the training process that produces $f$ is an obfuscation step. If this is the case then our result says that we can always plant undetectable backdoors.

We will elaborate on these points, and we will explain what types of “Perturb” function we allow for, as well as give examples of settings where applying iO to the model would be expected.

Limitations: The main limitation is that while the Plant(f, 0) and Plant(f, 1) distributions are indistinguishable, the distributions are easily distinguished from the distribution of f itself.

Please look at our response above. Our results can be interpreted as indistinguishability between Plant(f, 1) and f if we assume that the last step of the training procedure that generates f is an obfuscation step. Additionally it is worth mentioning that if we view $f, Plant(f, 0)$ as a mapping from features to $\{0, 1\}$, then these two mappings are the same. We will elaborate on this in the final version of our paper..

[1] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE, 2022.

[Part 1/n]

We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.

Q1: While this is a strong theoretical result, this seems to be vanishingly unlikely to be used in practice, since it depends on indistinguishability obfuscation, which Wikipedia claims to be highly impractical in practice. Additionally, I have certain questions about the function allowing too much, potentially weakening the overall result (see Question A, below).

A1: Thank you for your feedback. As you mentioned, the primary objective of our research is to theoretically demonstrate that neural networks (NNs) and large language models (LLMs) have inherent vulnerabilities and are susceptible to the backdoor attacks outlined in our paper. Beyond our theoretical results, which are significant on their own, our work also suggests a novel pipeline for injecting backdoors. This new pipeline could naturally be implemented using practical obfuscation techniques. For instance, one could replace Indistinguishability Obfuscation (iO) with more practical variants of obfuscation tailored for NNs. We believe that is a very interesting open question that arises from our framework and result and we hope that it will inspire people in the field.

Even without replacing the obfuscation method that we use our results are significant also because of the following:

1. Future Practicality: The iO method is expected to become more practical in the coming years, which aligns with the future applicability of our theoretical findings.

2. Current Importance: Given the widespread deployment of these models in decision-making processes, it is crucial to ensure they have robust security guarantees.

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.

We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.

Q1: It would be good to include a "Conclusion" section in the main body of the paper, as it currently seems to end abruptly.

A1: We would like to thank you for your suggestion. We will add the following Conclusion section:

Given the plethora of applications of Machine Learning in general, and neural networks in particular, questions regarding the trustworthiness of publicly released models naturally arise. In particular, before deploying a neural network we need to guarantee that no backdoors have been injected allowing bad actors to arbitrarily control the model behavior. In this paper, we investigate the existence of backdoor attacks to obfuscated neural networks which are undetectable even when given white-box access. The notion of obfuscation that we consider is the well-studied and mathematically founded indistinguishability obfuscation (iO). We also show how our techniques can inspire backdoor schemes in large language models when combined with ideas from steganography.

While our constructions are purely theoretical, we leave as an interesting direction how to use heuristic obfuscation methods to show practical instantiations of our constructions. Another interesting open question is whether cryptographic schemes weaker than iO suffice to show backdoor undetectability in the white-box model.

Q2: I believe that including some empirical results would nicely complement the theoretical findings.

A2: Thank you for your feedback. We would like to clarify that the primary objective of our research is to theoretically demonstrate that neural networks (NNs) and large language models (LLMs) have inherent vulnerabilities and are susceptible to the backdoor attacks outlined in our paper. Beyond our theoretical results, which are significant on their own, our work also suggests a novel pipeline for injecting backdoors. This new pipeline could naturally be implemented using practical obfuscation techniques. For instance, one could replace Indistinguishability Obfuscation (iO) with more practical variants of obfuscation tailored for NNs. We believe that is a very interesting open question that arises from our framework and result and we hope that it will inspire people in the field. Even without replacing the obfuscation method that we use our results are significant also because of the following:

1. Future Practicality: The iO method is expected to become more practical in the coming years, which aligns with the future applicability of our theoretical findings.
2. Current Importance: Given the widespread deployment of these models in decision-making processes, it is crucial to ensure they have robust security guarantees, even considering attacks that are not implementable in the present but will become implementable in the future.