Abstract
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 in this study capture in a natural way previous definitions, and in particular the one of Adleman. We establish generic virus constructions and we illustrate them by various examples. Lastly, we show the results on virus detection.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adleman, L.M.: An abstract theory of computer viruses. In: Advances in Cryptology – CRYPTO'88, vol. 403. Lecture notes in computer science (1988)
Bishop M. (1991). An overview of computer viruses in a research environment. Technical report, Dartmouth College, Hanover, NH
Blum M. (1967). A machine independent theory of the complexity of recursive functions. J ACM 14:322–336
Bonfante, G., Kaczmarek, M., Marion, J-Y.: Toward an abstract computer virology. In: Lecture notes in computer science, vol. 3722, pp 579–593 (2005)
Chess, D.M., White, S.R.: An undetectable computer virus (2000)
Cohen, F.: Computer viruses. PhD Thesis, University of Southern California (1986)
Cohen F. (1987). Computer viruses: theory and experiments. Comput Secur 6(1):22–35
Cohen F. (1988). On the implications of computer viruses and methods of defense. Comput Secur 7:167–184
Cohen F. (1989). Computational aspects of computer viruses. Comput Secur 8:325–344
Filiol, F.: Les virus informatiques: th讲ie, pratique et applications. Springer-Verlag France: 2004. Translation [11]
Filiol, F.: Computer viruses: from theory to applications. Springer Berlin Heidelberg New York 2005
Goel S., Bush S.F. (2003). Kolmogorov complexity estimates for detection of viruses in biologically inspired security systems: a comparison with traditional approaches. Complex 9(2):54–73
Anderson S., Thimbleby H., Cairns P. (1999). A framework for medelling trojans and computer virus infection. Comput Journal 41:444–458
Jain J., Osherson D., Royer J., Sharma A. (1999). Systems that learn. MIT, Cambridge
Jones, N.D.: 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)
Jones N.D. (1997). Computability and complexity: from a programming perspective. MIT, Cambridge, MA
Kleene, S.C: Introduction to metamathematics. Van Nostrand 1952
Ludwig, M.A.: The giant black book of computer viruses. sun city west: American Eagle Publications 1998
Myhill J. (1955). Creative sets. Zeit fur Math Logik und Grund der Math. 1:97–108
Odifreddi, P.: Classical recursion theory. Amsterdam North-Holland 1989
Rogers H. (1958). Gödel numberings of partial recursive function. J Symbol Logic 23(3):331–341
Rogers H. Jr. (1967). Theory of recursive functions and effective computability. McGraw Hill, New York
Smullyan R.M. (1961). Theory of formal systems. Princeton University Press, Princeton
Smullyan R.M. (1993). Recursion theory for metamathematics. Oxford University Press, New York, Translation
Smullyan R.M. (1994). Diagonalization and self-reference. Oxford University Press, New york
Szor P.: The art of computer virus research and defense.Reading Addison-Wesley Professional 2005
Thompson, K.: Reflections on trusting trust. Commun ACM 27:761–763, (1984). Also appears in ACM Turing Award Lectures: the first twenty years 1965–1985
Uspenskii, V.A.: Enumeration operators and the concept of program. Uspekhi Matematicheskikh Nauk 11, (1956)
von Neumann, J.: Theory of self-reproducing automata. Urbana, IL: University of Illinois Press, Urbana, Illinois, 1966. Edited and completed by A.W. Burks
Zuo, Z., Zhou, M.: Some further theorical results about computer viruses. In: The computer journal (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
We would like to thank Eric Filiol and the referees for their assistance
Rights and permissions
About this article
Cite this article
Bonfante, G., Kaczmarek, M. & Marion, JY. On Abstract Computer Virology from a Recursion Theoretic Perspective. J Comput Virol 1, 45–54 (2006). https://doi.org/10.1007/s11416-005-0007-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11416-005-0007-4