2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Is this a theoretical or pragmatic question ? $\endgroup$
    – user16034
    Sep 13, 2023 at 13:42
  • $\begingroup$ @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. $\endgroup$ Sep 13, 2023 at 21:07
  • $\begingroup$ No, I mean are you trying to solve a real-life problem or just playing. $\endgroup$
    – user16034
    Sep 14, 2023 at 8:25
  • $\begingroup$ @YvesDaoust : Neither. I'm trying to understand something. $\endgroup$ Sep 16, 2023 at 23:09

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ "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. $\endgroup$ Sep 13, 2023 at 12:21
  • $\begingroup$ @MichaelHardy, oh, good point. I've made that adjustment. Thank you. (I think the other answer is better than this one in any case.) $\endgroup$
    – D.W.
    Sep 13, 2023 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.