4 ms·

> the ability to poison models, if it can be made to work reliably Ultimately, it comes down to the halting problem: If there's a mechanism that can be used t

by vidarh 6mo ago

> the ability to poison models, if it can be made to work reliably Ultimately, it comes down to the halting problem: If there's a mechanism that can be used to alter the measured behaviour, then the system can change behaviour to take into account the mechanism. In other words, unless you keep the poisoning attack strictly inaccessible to the public, the mechanism used to poison will also be possible to use to train models to be resistant to it, or train filters to filter out poisoned data. At least unless the poisoning attack destroys information to a degree that it would render the poisoned system worthless to humans as well, in which case it'd be unusable. So either such systems would be insignificant enough to matter, or they will only work for long enough to be noticed, incorporated into training, and fail. I agree it's an interesting CS challenge, though, as it will certainly expose rough edges where the models and training processes works sufficiently different to humans to allow unobtrusive poisoning for a short while. Then it'll just help us refine and harden the training processes.

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.
lepus 6mo ago
It's a very comparable game of cat and mouse to spam email filtering. People also tried to claim that spam was over because for a time companies like Google cared enough to invest a lot in preventing as much as possible from getting through. If you've noticed in recent years the motivation to keep up that level of filtering has greatly diminished. Whether model poisoning becomes a bigger issue depends on the incentives for companies to keep fighting it. For now in comparison to attackers the incentives and resources needed to defend against model poisoning are huge so it's just temporary setbacks. Will that unevenness in their favor always be the case?
- lxgr 6mo ago
  I feel like spam filtering has moved from statistical methods to pay-to-play: "These 10 large senders have a reasonable opt-out policy (on paper, we'll check any day now), so why would we filter anything they drop at our 25?"
- scythe 6mo ago
  >It's a very comparable game of cat and mouse to spam email filtering. People also tried to claim that spam was over because for a time companies like Google cared enough to invest a lot in preventing as much as possible from getting through. If you've noticed in recent years the motivation to keep up that level of filtering has greatly diminished. https://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equations#Solutions_to_the_equations https://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equatio...
- vidarh 6mo ago
  Indeed, the existence of public access to the spam detection mechanism (up to and including spammers having tons of Gmail accounts etc. to test deliverability with) provides the same mechanism: The spammers can use the detector meant to stop them, to alter behaviour to evade the detector.
kibwen 6mo ago
> then the system can change behaviour to take into account the mechanism The question is not whether the system can change, it's whether the system is incentivized to change. Poisoners could operate entirely in the public, and theoretically manage to successfully poison targeted topics, and it could cost the model developers more than it's worth to fix it. Think about obscure topics like, say, Dark Souls speedrunning. There is no business demand for making sure that a model can successfully give information relating to something like that, so poisoning, if it works, would probably not be addressed, because there's no reason for the model developers to care.
- vidarh 6mo ago
  If they only poison something "nobody" cares about, then sure, nobody will care about it. In which case the poisoning also won't matter.
  - kibwen 6mo ago
    On the contrary, if poisoning actually works, and if asking LLMs becomes the predominant way that uninformed people access knowledge, then it means that people with obscure knowledge will be entirely capable of denying knowledge to anyone who only resorts to LLMs, which could serve as an effective filter for small communities.
Ar-Curunir 6mo ago
> Ultimately, it comes down to the halting problem: If there's a mechanism that can be used to alter the measured behaviour, then the system can change behaviour to take into account the mechanism. No, that’s the opposite of the halting problem…
- vidarh 6mo ago
  It's the very core of the halting problem.
tw061023 6mo ago
That's the point of the challenge: "are there unknown properties of models allowing us to construct a poison for any network given enough input-output pairs". The very point of CS as an academic discipline is _generalization_.
bostik 6mo ago
> unless you keep the poisoning attack strictly inaccessible to the public This is likely impossible. As the in-vogue breed of model extraction methods ("distillation attacks") demonstrates, you can infer the underlying training and/or fine-tuning of a model with a series of carefully constructed prompts. Another name of model poisoning? Adversarial fine-tuning.

by vidarh 6mo ago

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.

lepus 6mo ago

It's a very comparable game of cat and mouse to spam email filtering. People also tried to claim that spam was over because for a time companies like Google cared enough to invest a lot in preventing as much as possible from getting through. If you've noticed in recent years the motivation to keep up that level of filtering has greatly diminished. Whether model poisoning becomes a bigger issue depends on the incentives for companies to keep fighting it. For now in comparison to attackers the incentives and resources needed to defend against model poisoning are huge so it's just temporary setbacks. Will that unevenness in their favor always be the case?

lxgr 6mo ago
I feel like spam filtering has moved from statistical methods to pay-to-play: "These 10 large senders have a reasonable opt-out policy (on paper, we'll check any day now), so why would we filter anything they drop at our 25?"
scythe 6mo ago
>It's a very comparable game of cat and mouse to spam email filtering. People also tried to claim that spam was over because for a time companies like Google cared enough to invest a lot in preventing as much as possible from getting through. If you've noticed in recent years the motivation to keep up that level of filtering has greatly diminished. https://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equations#Solutions_to_the_equations https://en.wikipedia.org/wiki/Lotka%E2%80%93Volterra_equatio...
vidarh 6mo ago
Indeed, the existence of public access to the spam detection mechanism (up to and including spammers having tons of Gmail accounts etc. to test deliverability with) provides the same mechanism: The spammers can use the detector meant to stop them, to alter behaviour to evade the detector.

kibwen 6mo ago

> then the system can change behaviour to take into account the mechanism The question is not whether the system can change, it's whether the system is incentivized to change. Poisoners could operate entirely in the public, and theoretically manage to successfully poison targeted topics, and it could cost the model developers more than it's worth to fix it. Think about obscure topics like, say, Dark Souls speedrunning. There is no business demand for making sure that a model can successfully give information relating to something like that, so poisoning, if it works, would probably not be addressed, because there's no reason for the model developers to care.

vidarh 6mo ago
If they only poison something "nobody" cares about, then sure, nobody will care about it. In which case the poisoning also won't matter.
- kibwen 6mo ago
  On the contrary, if poisoning actually works, and if asking LLMs becomes the predominant way that uninformed people access knowledge, then it means that people with obscure knowledge will be entirely capable of denying knowledge to anyone who only resorts to LLMs, which could serve as an effective filter for small communities.

Ar-Curunir 6mo ago

> Ultimately, it comes down to the halting problem: If there's a mechanism that can be used to alter the measured behaviour, then the system can change behaviour to take into account the mechanism. No, that’s the opposite of the halting problem…

vidarh 6mo ago
It's the very core of the halting problem.

tw061023 6mo ago

That's the point of the challenge: "are there unknown properties of models allowing us to construct a poison for any network given enough input-output pairs". The very point of CS as an academic discipline is _generalization_.

bostik 6mo ago

> unless you keep the poisoning attack strictly inaccessible to the public This is likely impossible. As the in-vogue breed of model extraction methods ("distillation attacks") demonstrates, you can infer the underlying training and/or fine-tuning of a model with a series of carefully constructed prompts. Another name of model poisoning? Adversarial fine-tuning.