Fred Cohen in 1986 has proved in his Ph.D. thesis the undecidability of viral detection (no perfect virus checker can ever exist).

Does this imply that there exists a totally undetectable virus?

Else is it possible for a malware to stay a very long time (lets say many years or forever) undetected for the antivirus industry (COTS products)?

Furthermore is it possible for a malware to stay undetected for a very long time from defence agencies?

What are the best ways to approach this goal (perhaps make the behavior of the program chaotic, unpredictable or add time complexity as in cryptographic algorithms, use a rare or common host program...)?

closed as too broad by TildalWave, schroeder, M'vy, Jens Erat, RoraΖ Mar 3 '15 at 12:19

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    Write really good malware – cutrightjm Mar 3 '15 at 2:55
  • I know but how ? For months I read a lot of papers about anything related to malware (those who are very interesting are too complex for me because there are a lot of maths) almost every day. Adding time and space complexity and make the malware environmentally dependents are some possibles answers to my question. I need purest answers than just "you can use anti-debugging,anti-disassembly to be closer of this goal". Do you understand my request ? This theorem means alot to me (using simple basics principles I think this goal could be achieved). Why the downvote? (I'm sorry for my bad english) – NULL Mar 3 '15 at 3:54
  • Just like there are no perfect anti-viruses there are no perfect viruses. This question is not really possible to answer as there are too many variables in play. – RoraΖ Mar 3 '15 at 12:19

Obviously it can remain undetected for a long time, as there are several famous cases of malware having multi-year lifetimes.

The key is stealth. The wider the malware is spread, the greater the odds it will be discovered. The more damage the malware causes, the faster the victim will look to fix it.

The most successful malware refuses to spread to unintended victims, and refuses to cause damage to unintended victims. The malware writers don't use common exploits that other attackers are using. And they jealously guard their secrets.

  • To piggy back off this. More advanced Malware detectors use mathematical models to normalise user behaviour, and therefore to evade detection you are essentially required to trick a system into thinking that it is normal behaviour. – KingJohnno Mar 3 '15 at 10:12

For every innovation that you might achieve to work towards undetectability, there are legions of security researchers working to discover your methods. The more sophisticated your methods, the more sophisticated the response. This is truly a self-defeating spiral for both sides. But, there is a theoretical "endgame" where one creates the "perfect" malware.

The problem is with the paradox one creates. The most perfectly undetectable virus is one that never propagates and does nothing to modify its host. But, by its very nature, a virus spreads and affects its host. And, once a virus acts, it can be detected.

The other possible approach is a philosophical one: "The finest trick of the devil is to persuade you that he does not exist" (Charles Baudelaire). It is possible to create malware that does everything that malware does, but is accepted as legitimate by the user. In this way, the virus writer achieves his goal, and the virus remains "undetected".

  • 1
    Alternatively you could have no bounds checking in a code somewhere and leave that as a vital component in the internet infrastructure. It spreads, but not how you think. – munchkin Mar 3 '15 at 5:59
  • A practical example of the technic described in the last § is the cookies technic. Rather than to store a lot of private information, most of the time illegally and without the user’s knowledge or consent, on the web server, the use of cookies permits to store this stolen information on the client side. Then this collection of information being done on the user’s computer stops to look like a robbery of his information: “The robbery doesn’t exist, your data is inside your computer!”. – dan Jan 14 at 14:15

It's entirely possible. There are a lot of examples of this, especially something like Stuxnet which was allegedly found in the wild in 2005 and disregarded but was found in 2010.

Some earlier antiviruses would go by signatures and allow things like polymorphic viruses. This isn't as common lately, as heuristics and other technology has developed.

All in all, it depends on the programs and circumstances. The attacker will naturally always be a few steps ahead.

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