The notion of a self-reproducing computer program can be traced back to initial theories about the operation of complex automata.
Fred Cohen experimented with computer viruses and confirmed Neumann's postulate and investigated other properties of malware such as detectability and self-obfuscation using rudimentary encryption.
[2] Cohen's faculty advisor, Leonard Adleman, presented a rigorous proof that, in the general case, algorithmic determination of the presence of a virus is undecidable.
Adleman's proof is perhaps the deepest result in malware computability theory to date and it relies on Cantor's diagonal argument as well as the halting problem.
Ironically, it was later shown by Young and Yung that Adleman's work in cryptography is ideal in constructing a virus that is highly resistant to reverse-engineering by presenting the notion of a cryptovirus.
In the cryptoviral extortion attack, the virus hybrid encrypts plaintext data on the victim's machine using the randomly generated IV and SK.
The executed binary code is traced using strace or more precise taint analysis to compute data-flow dependencies among system calls.
Fredrikson et al.[10] describe an approach that uncovers distinguishing features in malware system call dependency graphs.
[11] Babic et al.[12] recently proposed a novel approach for both malware detection and classification based on grammar inference of tree automata.