Cautious virus detection in the extreme

ABSTRACT

It is well known that there exist viruses whose set of infected programs is undecidable. If a virus detector is to err on the side of caution with respect to such a virus, then it must label some perfectly innocent programs as being infected by the virus. Can there exist a virus whose set of infected programs is so unwieldy that any cautious virus detector must label all but finitely many programs as being infected by the virus — even when infinitely many programs are not infected by the virus? Although such viruses can exist, strong theoretical evidence is presented that such a virus is unlikely to be encountered in the real world. Several of our proofs employ infinitary self-reference arguments

REFERENCES

• 1: Leonard M. Adleman, An Abstract Theory of Computer Viruses, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.354-374, August 21-25, 1988
• 2: G. Bonfante, M. Kaczmarek, and J.-Y. Marion. On abstract computer virology from a recursion theoretic perspective. Journal in Computer Virology, 1(3-4):45--54, 2005.
• 3: G. Bonfante, M. Kaczmarek, and J.-Y. Marion. A classification of viruses through recursion theorems. In CiE¿07 - Computation and Logic in the Real World, 2007. To appear.
• 4: CA. Virus Information Center: Win32/Sality Family, 2006. http://www3.ca.com/securityadvisor/virusinfo/virus.aspx?ID=52797 .
• 5: J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15--32, 1974.
• 6: J. Case. Infinitary self-reference in learning theory. Journal of Experimental and Theoretical Artificial Intelligence, 6:3--16, 1994.
• 7: F. Cohen. Computational aspects of computer viruses. Computers and Security, 8(4):325--344, 1989.
• 8: E. Post. Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50:284--316, 1944.
• 9: H. Rogers. Gödel numberings of partial recursive functions. Journal of Symbolic Logic, 23:331--341, 1958.
• 10: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 11: SecuriTeam. Remote Shell Trojan: Threat, Origin and Solution, 2001. http://www.securiteam.com/unixfocus/5MP022K5GE.html .
• 12: Sophos. First ever virus for Mac OS X discovered, 2006. http://www.sophos.com/pressoffice/news/articles/2006/02/macosxleap.html .
• 13: Z. Zuo and M. Zhou. Some further theoretical results about computer viruses. The Computer Journal, 47(6):627--633, 2004.
• 14: Z. Zuo, Q. Zhu, and M. Zhou. On the time complexity of computer viruses. IEEE Transactions on Information Theory, 51(8):2962--2966, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory; Computability theory

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

General Terms:
Languages, Security, Theory

Keywords:
co-isolated sets, program self-reference, recursion theorems, simple sets, virus detection