Timeline for Has it been mathematically proven that antivirus can't detect all viruses?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 31, 2019 at 14:07 | comment | added | user21820 | @Falco: Yes of course. There are many such details but the comment box was too shallow to contain it. | |
| Jan 31, 2019 at 13:19 | comment | added | Falco | @user21820 that is not even complete, because two programs could be different only in where your data is actually sent. A banking app and a password sniffer will both read your password and send it to a server - your machine will do exactly the same thing, but the receiver is different - so a local scan can never decide if the receiver is someone you actually intent to sent your data to, so the whole internet with all reachable machines together should minimally be your state machine for checking all states - good luck... | |
| Jan 31, 2019 at 11:11 | comment | added | Jeroen Mostert | @user21820: I never said sandboxing was or could ever be a perfect solution (it should be quite obvious that no solution can be an absolute guard against malware, from a simple practical point of view, let alone theory). The question is whether Rice's theorem is the correct thing to invoke here as mathematical proof that such malware can't be detected. (Or, going up one more level, if Schneider was referring to that at all, which does not appear to be the case -- despite being undervoted, this answer appears to be the correct one.) | |
| Jan 30, 2019 at 14:36 | comment | added | user21820 | @Joseph: I agree with your answer, but one possible quibble is that real computers are not Turing-complete, and hence it is theoretically possible (though practically impossible) to determine whether any program would cause your specific computer to enter an undesirable state. Naturally, you would not be able to do so within your computer itself, but theoretically you can use another computer that has more memory to do the analysis. Of course, the time needed is proportional to the number of possible states your computer can be in... | |
| Jan 30, 2019 at 14:32 | comment | added | user21820 | @JeroenMostert: Sandboxing does not solve the problem. How do you know whether the latest version of your browser that you installed has a hidden malware that captures your keyboard input on bank websites? Are you going to use a different sandbox for every sensitive website? How do you know that your latest sandboxing software is not itself malware? How do you know that your operating system... | |
| Jan 28, 2019 at 23:11 | comment | added | BlueRaja - Danny Pflughoeft | @JeroenMostert: No, it has nothing to do with static vs runtime analysis. The difference is in whether the definition is semantic or syntactic. "A list of the actions the program is allowed to perform" is a syntactic definition. This is why writing a sandbox is so much easier than writing an antivirus. | |
| Jan 28, 2019 at 18:07 | comment | added | nikie | I think Rice's theorem only applies if you have to decide ahead of time if a program is malicious, and if you don's allow false positives. If the virus scanner can e.g. intercept API calls, modify the program (e.g. to insert runtime checks) and occasionally reject a "safe" program, it should be possible to prove safety. That's basically how e.g. a Java VM can offer safety guarantees, isn't it? | |
| Jan 27, 2019 at 11:40 | comment | added | Jeroen Mostert | @BlueRaja-DannyPflughoeft: it's important that this is true only insofar as it's impossible to tell up front, with a guarantee of termination. Given a rigorous definition of actions the program is not allowed to perform it's perfectly possible to do it while the program is running -- this is the principle behind sandboxing. Most users would settle for a program that stops malware before it does something bad, regardless of whether it also got the opportunity to show some dancing monkeys first. The problem is that these "rigorous definitions" will inevitably turn out to be incomplete. | |
| Jan 26, 2019 at 23:49 | comment | added | The_Sympathizer | @Stéphane Chazelas Self-replication is a non-trivial semantic property as well, ergo it is undecidable. | |
| Jan 26, 2019 at 22:45 | comment | added | Stéphane Chazelas | The OP asked about "viruses", not malicious software. viruses are not necessarily malicious. The only determining property is that it self-replicates. (Now it's likely the OP meant malware (virus or not)). | |
| Jan 25, 2019 at 22:49 | comment | added | BlueRaja - Danny Pflughoeft | @DoktorJ: The point is that even if you come up with some rigid non-syntactic definition for "malicious" (regardless of if that definition misses some viruses, or includes some non-viruses), it's still impossible to flag all/only malicious programs. | |
| Jan 25, 2019 at 20:17 | comment | added | Doktor J | Not to mention, "malicious" is an almost entirely subjective term. I've seen disassembly programs get flagged as malware because the AV author apparently considered reverse engineering to be a "malicious" thing (even though I can't think of a situation where someone who didn't want said disassembler on their computer would end up with it there). | |
| S Jan 24, 2019 at 7:42 | history | mod moved comments to chat | |||
| S Jan 24, 2019 at 7:42 | comment | added | schroeder♦ | Comments are not for extended discussion; this conversation has been moved to chat. | |
| Jan 23, 2019 at 3:10 | history | answered | Joseph Sible-Reinstate Monica | CC BY-SA 4.0 |