# Exploiting weaknesses in virus-detecting software?

If a virus is defined as a self-reproducing program, then Rice's theorem implies there can be no infallible virus-detecting algorithm.

Can we take that one step further, as follows? If you have the source code for a virus-detecting program, could you use it to produce a virus that the program will fail to detect?

• Is this a theoretical or pragmatic question ?
– user16034
Commented Sep 13, 2023 at 13:42
• @YvesDaoust : I'm tempted to say that obviously it's a theoretical question. As to whether it's also a pragmatic question, I suppose you may consider it "pragmatic" to keep the source code secret. Commented Sep 13, 2023 at 21:07
• No, I mean are you trying to solve a real-life problem or just playing.
– user16034
Commented Sep 14, 2023 at 8:25
• @YvesDaoust : Neither. I'm trying to understand something. Commented Sep 16, 2023 at 23:09

Following the reasoning of the Halting Problem, you can indeed make a "virus" that performs the following action:

if (this very virus will not be flagged)
infect everything in sight
else
do nothing


This is practically possible: you just would have to bundle the entire antivirus with your program in order to perform that check.

However, this will not be helpful, because the antivirus can just flag it anyway, despite the fact that in that case it's actually harmless. After all, actual virus-detecting programs are allowed to have false positives, as opposed to that ideal detector from Rice's theorem.

So, in summary: this trick is possible, but it doesn't actually give you any advantage against the antivirus.

That line of reasoning demonstrates that if you have a virus-detecting program, there exists a virus that the program will fail to detect.

But it says nothing about how easy or hard it might be to actually construct (find) such a virus. Such matters are beyond the scope of computability theory. If you care about the running time of an algorithm to solve some problem, that gets into complexity theory, which is beyond the scope of Rice's theorem, computability, the halting problem, etc.

If you care about the difficulty of constructing such a virus in practice, then this turns out to be more of an engineering matter, that depends on systems and implementation details. Computability theory and complexity theory are not terribly informative.

• "That line of reasoning demonstrates that if you have the source code for a virus-detecting program, there exists a virus that the program will fail to detect." Actually your statement beginning with "there exists" is true regardless of whether you have the source code or not. Commented Sep 13, 2023 at 12:21
• @MichaelHardy, oh, good point. I've made that adjustment. Thank you. (I think the other answer is better than this one in any case.)
– D.W.
Commented Sep 13, 2023 at 17:56