Toward an Abstract Computer Virology

  • G. Bonfante
  • M. Kaczmarek
  • J. -Y. Marion
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


We are concerned with theoretical aspects of computer viruses. For this, we suggest a new definition of viruses which is clearly based on the iteration theorem and above all on Kleene’s recursion theorem. We show that we capture in a natural way previous definitions, and in particular the one of Adleman. We establish generic constructions in order to construct viruses, and we illustrate them by various examples. We discuss the relationship between information theory and viruses and we propose a defense against a kind of viral propagation. Lastly, we show that virus detection is Π2-complete. However, since we are able to deal with system vulnerability, we exhibit another defense based on controlling system access.


Turing Machine Recursive Function Computable Function Kolmogorov Complexity Computer Virus 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Adleman, L.: An abstract theory of computer viruses. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 354–374. Springer, Heidelberg (1990)Google Scholar
  2. 2.
    Bishop, M.: An overview of computer viruses in a research environment. Technical report, Hanover, NH, USA (1991)Google Scholar
  3. 3.
    Chess, D., White, S.: An undetectable computer virusGoogle Scholar
  4. 4.
    Cohen, F.: Computer Viruses. PhD thesis, University of Southern California (January 1986)Google Scholar
  5. 5.
    Cohen, F.: Computer viruses: theory and experiments. Comput. Secur. 6(1), 22–35 (1987)CrossRefGoogle Scholar
  6. 6.
    Cohen, F.: Models of practical defenses against computer viruses: theory and experiments. Comput. Secur. 6(1) (1987)Google Scholar
  7. 7.
    Davis, M.: Computability and unsolvability. McGraw-Hill, New York (1958)zbMATHGoogle Scholar
  8. 8.
    Filiol, E.: Les virus informatiques: théorie, pratique et applications. Springer, Heidelberg (2004)zbMATHGoogle Scholar
  9. 9.
    Goel, S., Bush, S.: Kolmogorov complexity estimates for detection of viruses in biologically inspired security systems: a comparison with traditional approaches. Complex 9(2), 54–73 (2003)CrossRefGoogle Scholar
  10. 10.
    Anderson, S., Thimbleby, H., Cairns, P.: A framework for medelling trojans and computer virus infection. Comput. J. 41, 444–458 (1999)Google Scholar
  11. 11.
    Jones, N.: Computer implementation and applications of kleene’s S-m-n and recursive theorems. In: Moschovakis, Y.N. (ed.) Lecture Notes in Mathematics, Logic From Computer Science, pp. 243–263 (1991)Google Scholar
  12. 12.
    Kleene, S.C.: Introduction to Metamathematics, nj edn. Van Nostrand, Princeton (1964)Google Scholar
  13. 13.
    Li, M., Vitányi, P.: An Introduction to Kolmogorov Complexity and its Application, 2nd edn. Springer, Heidelberg (1997)Google Scholar
  14. 14.
    Ludwig, M.: The Giant Black Book of Computer Viruses. American Eagle Publications (1998)Google Scholar
  15. 15.
    Odiffredi, P.: Classical recursion theory. North-Holland, Amsterdam (1989)Google Scholar
  16. 16.
    Rogers, H.: Theory of Recursive Functions and Effective Computability. McGraw Hill, New York (1967)zbMATHGoogle Scholar
  17. 17.
    Szor, P.: The Art of Computer Virus Research and Defense. Addison-Wesley Professional, Reading (2005)Google Scholar
  18. 18.
    Turing, A., Girard, J.-Y.: La machine de Turing. Seuil (1995)Google Scholar
  19. 19.
    Turing, A.M.: On computable numbers with an application to the entscheidungsproblem. Proc. London Mathematical Society 42(2), 230–265 (1936) Traduction [18]zbMATHGoogle Scholar
  20. 20.
    Uspenskii, V.A.: Enumeration operators ans the concept of program. Uspekhi Matematicheskikh Nauk 11 (1956)Google Scholar
  21. 21.
    von Neumann, J., Burks, A.W.: Theory of self-reproducing automata. University of Illinois Press, Champaign (1966)Google Scholar
  22. 22.
    Zuo, Z., Zhou, M.: Some further theorical results about computer viruses. The Computer Journal (2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • G. Bonfante
    • 1
    • 2
  • M. Kaczmarek
    • 1
    • 2
  • J. -Y. Marion
    • 1
    • 2
  1. 1.Loria, Calligramme projectVandœuvre-lès-NancyFrance
  2. 2.École Nationale Supérieure des Mines de Nancy, INPLFrance

Personalised recommendations