3 ms·

This reduction to the halting problem looks too handwawy to me. I don't see as a given that the possibility of the system taking into account the attack follows

by GTP 6mo ago

This reduction to the halting problem looks too handwawy to me. I don't see as a given that the possibility of the system taking into account the attack follows from the existence of the attack.

mswphd 6mo ago
They might be trying to talk about Rice's theorem? https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem Formally, any non-trivial semantic property of a Turing machine is undecidable. Semantic here (roughly) means "behavioral" questions of the turing machine. E.g. if you only look at the "language" it defines (viewing it as a black box), then it is undecidable to answer any question about that language (including things like if it terminates on all inputs). Practically though that isn't a complete no-go result. You can do various things, like 1. weaken the target you're looking for. if you're ok with admitting false positives or false negatives, Rice's theorem no longer applies, or 2. rephrase your question in terms of "syntatic properties", e.g. questions about how the code is implemented. Rust's borrow checker does this via lifetime annotations, for example.
- vidarh 6mo ago
  Rice's theorem is a close corollary, but I did mean the halting problem. Pointing to the halting problem was a bit of a throwaway quip because the "general shape" of it is an easy smell test for whether something is likely to be possible: If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. When you have a detector for a given property, you can use that detector to alter behaviour to exclude that property. And that is the abstract core of why the halting problem is unsolvable. In this case, if you have access to a mechanism for poisoning data, you can use that to train a detector. Once you have a detector, you can either exclude poisoned data, or use it for adversarial training. Either way: The existence of the poisoning mechanism can be directly used to derive the tools to create its own antidote. And that's back to the core of the halting problem.
  - lxgr 6mo ago
    > If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. This still seems too handwavy. For example, you're implying that the transform is one that can be learned by gradient descent. As a trivial counterexample, you can't train a model to detect valid (text, SHA) pairs. This particular one doesn't seem to be a problem for your argument, but I still think your argument generally does not hold.
    - vidarh 6mo ago
      You can't train a model to detect arbitrary text to SHA, so yes, there are edge cases - this doesn't fully generalise. You can, however, trivially train a model to detect natural language to SHA. More specifically, for poisoning to work, the output needs to have qualities distinctly different in the poisoned or unpoisoned case, pretty much by definition, or we wouldn't notice the effect, and the reason the general case doesn't work for SHA is that you can feed in text that is likely statistically indistinguishable (you can feed SHA in as text) from the output, or "close enough".
thfuran 6mo ago
And even if it is provably possible to do, that doesn't mean it's easy. That's kind of the basis of encryption.
- vidarh 6mo ago
  It doesn't need to be easy, but unlike with encryption it also doesn't need to be particularly precise. E.g. it's okay to exclude non-poisoned training data because you didn't manage to create a precise enough detector, as long as you don't exclude too much. Basically any poisoning attack is also fundamentally limited because it needs to be non-invasive enough for humans not to be adversely affected, and that limits the problem space severely - the poisoning mechanism basically becomes reduced to a training mechanism to train out places where the models act different to humans.
vidarh 6mo ago
This is why I pointed out that the only way poisoning has a chance of working other than over very short timelines is if the tools to do so remains private and inaccessible to the public. It's a bit of a leap, but the halting problem can be generalized to: It is impossible in the general case to produce a detector function f(x), that will decide if program x behaves according to rule y if x can include f(x) as part of the itself. The reason is that if a program x can make use of the detector, it can effectively do if f(x) { do the opposite of what f(x) predicts} The leap from that to poisoning might be a bit unintuitive, but it boils down to the poisoner having a mechanism that would alter model behaviour. If you have access to that mechanism, you can produce a detector by using the mechanism to induce the unwanted behaviour, and train a model on that. Once you have a detector, you can behave differently based on the signal from the detector, and by extension avoid the effects of the original mechanism. And that is the core of the halting problem.

by GTP 6mo ago

This reduction to the halting problem looks too handwawy to me. I don't see as a given that the possibility of the system taking into account the attack follows from the existence of the attack.

mswphd 6mo ago

They might be trying to talk about Rice's theorem? https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem Formally, any non-trivial semantic property of a Turing machine is undecidable. Semantic here (roughly) means "behavioral" questions of the turing machine. E.g. if you only look at the "language" it defines (viewing it as a black box), then it is undecidable to answer any question about that language (including things like if it terminates on all inputs). Practically though that isn't a complete no-go result. You can do various things, like 1. weaken the target you're looking for. if you're ok with admitting false positives or false negatives, Rice's theorem no longer applies, or 2. rephrase your question in terms of "syntatic properties", e.g. questions about how the code is implemented. Rust's borrow checker does this via lifetime annotations, for example.

vidarh 6mo ago
Rice's theorem is a close corollary, but I did mean the halting problem. Pointing to the halting problem was a bit of a throwaway quip because the "general shape" of it is an easy smell test for whether something is likely to be possible: If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. When you have a detector for a given property, you can use that detector to alter behaviour to exclude that property. And that is the abstract core of why the halting problem is unsolvable. In this case, if you have access to a mechanism for poisoning data, you can use that to train a detector. Once you have a detector, you can either exclude poisoned data, or use it for adversarial training. Either way: The existence of the poisoning mechanism can be directly used to derive the tools to create its own antidote. And that's back to the core of the halting problem.
- lxgr 6mo ago
  > If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. This still seems too handwavy. For example, you're implying that the transform is one that can be learned by gradient descent. As a trivial counterexample, you can't train a model to detect valid (text, SHA) pairs. This particular one doesn't seem to be a problem for your argument, but I still think your argument generally does not hold.
  - vidarh 6mo ago
    You can't train a model to detect arbitrary text to SHA, so yes, there are edge cases - this doesn't fully generalise. You can, however, trivially train a model to detect natural language to SHA. More specifically, for poisoning to work, the output needs to have qualities distinctly different in the poisoned or unpoisoned case, pretty much by definition, or we wouldn't notice the effect, and the reason the general case doesn't work for SHA is that you can feed in text that is likely statistically indistinguishable (you can feed SHA in as text) from the output, or "close enough".

thfuran 6mo ago

And even if it is provably possible to do, that doesn't mean it's easy. That's kind of the basis of encryption.

vidarh 6mo ago
It doesn't need to be easy, but unlike with encryption it also doesn't need to be particularly precise. E.g. it's okay to exclude non-poisoned training data because you didn't manage to create a precise enough detector, as long as you don't exclude too much. Basically any poisoning attack is also fundamentally limited because it needs to be non-invasive enough for humans not to be adversely affected, and that limits the problem space severely - the poisoning mechanism basically becomes reduced to a training mechanism to train out places where the models act different to humans.

vidarh 6mo ago

This is why I pointed out that the only way poisoning has a chance of working other than over very short timelines is if the tools to do so remains private and inaccessible to the public. It's a bit of a leap, but the halting problem can be generalized to: It is impossible in the general case to produce a detector function f(x), that will decide if program x behaves according to rule y if x can include f(x) as part of the itself. The reason is that if a program x can make use of the detector, it can effectively do if f(x) { do the opposite of what f(x) predicts} The leap from that to poisoning might be a bit unintuitive, but it boils down to the poisoner having a mechanism that would alter model behaviour. If you have access to that mechanism, you can produce a detector by using the mechanism to induce the unwanted behaviour, and train a model on that. Once you have a detector, you can behave differently based on the signal from the detector, and by extension avoid the effects of the original mechanism. And that is the core of the halting problem.