Is it theoretically exist a computer that never affected by computer virus?

just wonder if there could be a revolution on the computer?

  • $\begingroup$ No, becoause detecting Metamorphic varients of a virus is NP-complete problem so atleast theoritically no such machine can be exist. It can be possible if you can detect virus dynamic behaviour but that is itself a partially solvable problem. $\endgroup$ Apr 5, 2014 at 2:52
  • 1
    $\begingroup$ @GrijeshChauhan NP-complete problem are all solvable (maybe not very quickly). How is this relevant? $\endgroup$ Apr 5, 2014 at 3:44
  • 1
    $\begingroup$ I don't think this question is well-posed. It all depends on semantics--how do you define a computer/virus? $\endgroup$ Apr 5, 2014 at 3:49
  • $\begingroup$ @AustinBuchanan I am about to post an answer may be that help upto some extend. $\endgroup$ Apr 5, 2014 at 3:57

2 Answers 2


Do you mean "that cannot be affected" or "that was never affected"? Then, under what conditions? Do you mean malware in general or a more restrictive notion of virus? And then, what is virus or malware? Is code for automatic update of your OS considered malware or not? Maybe you do not want to update your OS. Maybe someone has taken control of the updating service to introduce undesirable features in your system.

The main problem with your question is probably the word "theoretically". What is a theoretical computer? If it is a Turing Machine, the answer is clearly yes: they do what their finite control says they should do. Period.

Is there a fully precise theoretical model of a real computer. That is doubtful, if only because it is a complex physical objet and there is a limit to our ability to fully model such an object, since our knowledge of physics is not complete ... though I doubt that is the main issue.

Assuming we could completely model the physical computer with a formal system, do we fare better? Now we have (or shall have) all these great tools for proving theorems about computers and programs. But this has limitations too. Gödel says that not all true facts are provable, especially in a theory that can model that much computation. But even without falling in this black hole, do we fare better? No because before proving anything about the computer we need to model precisely what a computer is, and also what it means to be affected by a virus. Even if we have a perfect and total proof system (which we do not), how do we prove that our theoretical specification of the problem is accurate with respect to the physical problem with real computers. Bugs are not the exclusive privilege of programs and proofs, you can also have them in specifications, and some may be hard to eradicate. If your child specifies he wants a train as a gift when it is actually a car that he wants, what are the formal tools that will identify the specification error - short of implementing and observing that things do not behave as expected.

Coming back to a more practical view. Some machines are harware protected with encryption keys that allow only trusted software. First, many people consider this as malware by itself, as it is often used against the owner of the computer. Then encryption can be broken by mathematical or social means. And the protection may possibly also be circumvented by other means.

A computer that stays off-line and does not access foreign data is unlikely to be affected. Then, there are different ways of accessing foreign data that may be more or less risky. Using foreign code is likely to be more risky. So the question cannot be independent of defining the conditions in which the computer is used.

However, even off-line, there is always the risk that the computer was born affected by malware (to avoid the restrictive concept of virus).

You should read Ken Thomson's 1984 Turing lecture: Reflections on Trusting Trust.

Either you trust others to some extent, or you rebuild most of the technology from scratch by yourself, with no interference from others. May be not starting at stone age, but far enough ... assuming you do not have bugs in your own code (but if not intentionally malicious, they are less likely to be as much a problem).


I believe No.

With my knowledge about new generation malware those are "metamorphic and polymorphic" in nature change their code as they propagate. I think no such machine can be possible to make (even theoretically) that can detect all possible variants of a malware.

Below I try to justify. I hope my answer help you up to some extend.

What is metamorphic malware?: To change code structure at each infection metamorphic malware employee the Mutation Engine (black-part) that use obfuscation techniques like: garbage code insertion, register/variable usage exchange, instruction replacement, instruction permutation, code transposition etc. You can picture it as below:

enter image description here
Source of Image: Momentum

Change in order of color represents 'instruction permutation', change in size shows insertions/deletion 'garbage code instruction', I didn't shown cnage in color (you can find in next-slides) show will represent code tranformation e.g. $MOV a, b$ can be replace by $PUSH b$ followed by $POP a$.
Malware Obfuscation Techniques: A Brief Survey


So theoretically, a new generation malware can change their structure arbitrarily complex way and can avoid detection (this problem is like compare two codes those instructions are different but perform same behaviour -- and that is unsolvable).

Code obfuscation techniques for metamorphic viruses, Journal in Computer Virology

“… we prove that reliable static detection of a particular category of metamorphic viruses is an NP-complete problem. Then we empirically illustrate our result by constructing a practical obfuscator which could be used by metamorphic viruses in the future to evade detection…”

This implies that we can't make a signature based antivirus that can't detect all possible varients of a malware efficiently (I have played with more than 2500 malware samples with 14 antivirus and no one could detect more than 76% malwares).

Now other techniques are "dynamic" analysis and detection. Read Ether: Malware Analysis via Hardware Virtualization Extensions ACM CCS 2008: "Dynamic analysis of malware itself a open problem because of limited test coverage. Malware may evade detection and analysis by simply not performing malicious behaviour during the dynamic analysis (it may stay inactive until certain condition satisfy)". You can read also 6 Antivirus Open Problems .

One point to keep in mind the new generation malware are complex and hide their malicious code in encrypted form (there are key encryption techniques those are irreversible without decryption key). So malware carries both legitimate and malicious behaviour.

Dynamic behaviour itself depends on dynamically input values (domain of input is infinitely large) so making all possible test-cases are impossible. Remember we having debugging tools but none-of-debugger runs automatically, we have to explicitly apply intelligent to debug codes. So I believe via dynamic analysis even theoretically still detection of malware is impossible.

Any detection technique either dynamic or static try to find similarity between signature (one program's behaviour or some part of code) and a malware thread (other program target). And as we know "the problem whether or not two Turing machines accept the same language is unsolvable.". That I implies that we can write a general solution of detecting new generation malware. A general solution is possible when you have arbitrary infinite signature repository to identify arbitrary any form of malware's variant.

  • 3
    $\begingroup$ That just means that detecting viruses is difficult. But viruses exploit some weaknesses in the design of the relevant software or even hardware. What if these weaknesses weren't there in the first place? $\endgroup$ Apr 5, 2014 at 5:06
  • $\begingroup$ I tried to improve my answer in last para. I believe information in my answer can help some. -- So even if I could just explain that "detection is hard". I feel I should remain it undeleted. --To @Other users: let me know you opinion should delete this answer (if you think it not an answer)? $\endgroup$ Apr 5, 2014 at 14:17

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