РусскийEnglishУкраїнськаDeutschEspañolFrançaisItalianoPolski

VX Heavens

Library Collection Sources Engines Constructors Simulators Utilities Links Antivirus Forum

[Deutsch][English][Español][Italiano][Français][Polski][Русский][Українська]

«An Abstract Theory of Computer Viruses» (0) 40.82Kb 5282 hits
Advances in Cryptology - CRYPT0 '88, LNCS 403, pp. 354-374, 1990 (1990)

In recent years the detection of computer viruses has become common place. It appears that for the most part these viruses have been 'benign' or only mildly destructive. However, whether or not computer viruses have the potential t o cause major and prolonged disruptions of computing environments is an open question. Such basic questions as: How hard is it to detect programs infected by computer viruses? Can infected programs be 'disinfected'? What forms of protection exist? How destructive can computer viruses be? have been at most partially addressed [Col][Co2]'.Indeed a generally accepted definition of computer virus has yet to emerge. For these reasons, a rigorous study of computer viruses seems appropriate.

«A Bypass of Cohen's Impossibility Result» (0) 36.68Kb 3005 hits
Advances in Grid Computing - EGC 2005, LNCS 3470, pages 1097-1106. Springer-Verlag, 2005 (2005)

Detecting illegal resource access in the setting of network communication or grid computing is similar to the problem of virus detection as put forward by Fred Cohen in 1984. We disucuss Cohen's impossibility result on virus detection, and introduce "risk assessment of security hazards", a notion that is decidable for a large class of program behaviors.

«Toward an abstract computer virology» (0) 42.78Kb 2988 hits
Lecture Notes in Computer Science, volume 3722, pp.579-593. Springer, Oct 2005. (2005)

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 about the relationship between information theory and virus and we propose a defense against some kind of viral propagation. Lastly, we show that virus detection is ∏02-complete. However, since we are able to deal with system vulnerability, we exhibit another defense based on controlling system access.

«An Undetectable Computer Virus» (0) 19.52Kb 3452 hits
Virus Bulletin Conference (2000)

One of the few solid theoretical results in the study of computer viruses is Cohen's 1987 demonstration that there is no algorithm that can perfectly detect all possible viruses [1]. This brief paper adds to the bad news, by pointing out that there are computer viruses which no algorithm can detect, even under a somewhat more liberal definition of detection. We also comment on the senses of "detect" used in these results, and note that the immediate impact of these results on computer virus detection in the real world is small.

«Computational Aspects of Computer Viruses» (0) 3104 hits
Computers & Security, Volume 8, Issue 4 (June 1989), pp.325-344 (1989)

This paper formally defines a class of sets of transitive integrity-corrupting mechanisms called "viral sets" and explores some of their computational properties.

«Computer Viruses - Theory and Experiments» (0) 62.59Kb 12279 hits
Computers & Security 6 (1987), pp. 22-35 (1984)

[...] This paper defines a major computer security problem called a virus. The virus is interesting because of its ability to attach itself to other programs and cause them to become viruses as well. [...]

«A Formal Definition of Computer Worms and Some Related Results» (0) 41.82Kb 4300 hits
Computers & Security, 7(11) (1992), pp.641-652 (1992)

In this paper, we propose a formal definition of "computer worms" and discuss some of their properties. We begin by reviewing the formal definition of "computer viruses", and their properties. We then define "computer worms" as a subclass of viruses, and show that many of the interesting ptoperties derived for viruses hold for worms. Finally, we summarize results, draw conclusions, and propose further work.

«Models of Practical Defenses Against Computer Viruses» (0) 39.61Kb 2678 hits
Computers and Security, Volume 8, Issue 2, pp.149-160 (1989)

In this paper, we model complexity based virus detection mechanisms which detect modifications and thereby prevent computer viruses from causing secondary infections. We use these models to show how to protect information in both trusted and untrusted computing bases, show the optimality of these mechanisms, and discuss some of their features. The models indicate that we can cover changes at all levels of interpretation with a unified mechanism for describing interdependencies of information in a system, and we discuss the ramifications of this unification in some depth.

«Reply to `Comment on "A Framework for Modelling Trojans and Computer Virus Infection"' by E. Mäkinen» (0) 7.13Kb 1991 hits
THE COMPUTER JOURNAL, Vol. 44, No. 4, 2001, pp. 326-327 (2001)

There may be some relatively interesting things to do in developing Turing machine models of operating systems. The original Turing machine model of operating systems used to model viruses (Cohen [1]) does this to a limited extent and can also be used as a model of networks, but it fails to capture the full richness of modern operating systems in detail. The advantage of this is generality, but the disadvantage is the inability to specifically model the detailed events in current operating systems.

«Self-Replicating Turing Machines and Computer Viruses» (0) 17.25Kb 842 hits
Artificial Life X. Workshop Proceedings on Machine Self-Replication, pp. 129-132. (2006)

This paper reviews self-replication in the context of (partial) recursive functions and Turing computability. By the Church-Turing thesis, these are equivalent to other models of computation. The theory is linked to applications in the area of computer viruses. We address the views of various authors with respect to the (in)adequacy of Turing machine equivalent models for computer viruses.

«There Are No Safe Virus Tests» (0) 4.46Kb 2220 hits
American Mathematical Monthly, v.96 n.9, p.835-836, Nov. 1989. (1989)

This note gives a proof that no program can both test its input for the presence of a virus and simultaneously be guaranteed not to spread a virus itself.

«Metamorphism, Formal Grammars and Undecidable Code Mutation» (0) 37.39Kb 3844 hits
International Journal of Computer Science, vol. 2, number 1, 2007, pp. 70-75 (2007)

This paper presents a formalisation of the different existing code mutation techniques (polymorphism and metamorphism) by means of formal grammars. While very few theoretical results are known about the detection complexity of viral mutation techniques, we exhaustively address this critical issue by considering the Chomsky classification of formal grammars. This enables us to determine which family of code mutation techniques are likely to be detected or on the contrary are bound to remain undetected. As an illustration we then present, on a formal basis, a proof-of-concept metamorphic mutation engine denoted PB MOT, whose detection has been proven to be undecidable.

«Open problems in computer virology» (0) 67.89Kb 4039 hits
Journal in Computer Virology (2006)1, pp.55-66 (2006)

In this article, we briefly review some of the most important open problems in computer virology, in three different areas: theoretical computer virology, virus propagation modeling and antiviral techniques. For each area, we briefly describe the open problems, we review the state of the art, and propose promising research directions.

«A Mathematical Theory for the Spread of Computer Viruses» (0) 22.26Kb 2803 hits
Computers & Security, 8, 1989, pp.35-41 (1989)

A model is introduced to treat the spread of computer viruses mathematically. A recurrence formula is given which allows a closed expression to be derived for the probability that, starting from an initial state, a given viral state will be reached after executing exactly k programs. In some special cases this recurrence formula can be used for numeric computations, It is shown that the infection process does not stop before all programs are infected, which are visible for any infected program in the initial state.

«A note on Cohen's formal model for computer viruses» (0) 8.39Kb 2374 hits
ACM SIGSAC Review, Volume 8, Issue 2, (Summer 1990), pp.40-43 (1990)

This note discusses the formal model for computer viruses presented by Fred Cohen. We propose some refinements for the model. Especially, we define a computer virus to be a description of a Turing machine capable of writing a description of another Turing machine to the tape of a universal Turing machine.

«Challenges in getting 'formal' with viruses» (0) 24.03Kb 2503 hits
Virus Bulletin, September 2003 (2003) 15-19 (2003)

Is it a virus, a worm, a Trojan, or a backdoor? Answering this question correctly for any arbitrary program is known to be an undecidable problem. That is, it is impossible to write a computer program that will identify correctly whether an arbitrary program is a virus, a worm, etc. - no matter how much computing power is thrown at the problem.

«Mathematical Model of Computer Viruses» (0) 2274 hits
EICAR 2000 Best Paper Proceedings (2000)

In real computers the operating system organizes the connection between the unique programs. In most operating systems a program can modify other program and/or data files. There are some special programs which utilize this facility of the operating system, for example the computer viruses. For the analysis of programs which modify other programs it is necessary to define a new computation model. The new mathematical model - called Random Access Stored Program Machine with Attached Background Storage (RASPM with ABS) - is introduced in this paper. The other required tool is a suitable model for the operating system. This new model is also introduced using mathematical methods.

«Reductions of the general virus detection problem» (0) 16.76Kb 2644 hits
In U. E. Gattiker (Ed.), Conference Proceedings EICAR International Conference, pp. 24-30 (2001)

Theoretically it is impossible to generate a program which can solve the general virus detection problem. This theorem has been proved in different ways in the literature. Since the general virus detection problem is not solvable, we have to reduce the problem: we can deal "only" with a subset of viruses. For example, we can limit the storage space of viruses or we can limit the execution time of viruses. Theoretically in these cases it can be proved that there is an algorithm for the virus detection problem. On the other hand, we can reduce the general virus detection problem if we deal with the known viruses only. In this paper, I would like to examine the virus detection problem, the possible reductions of the virus detection problem and, of course, I would like to highlight the usability of the virus detection algorithms in the practice too.

«Comment on 'A Framework for Modelling Trojans and Computer Virus Infection'» (0) 11.4Kb 2256 hits
THE COMPUTER JOURNAL, Vol. 44, No. 4, 2001, pp.321-323 (2001)

We (re-)introduce a Turing machine model for computer viruses. Despite the recent criticism of Turing machine models, they enjoy important advantages: their well-known notation and rich theory make them easy to understand and to elaborate. For many natural problems concerning computer viruses, e.g. for various decidability problems, Turing machine models provide a suitable platform of research.

«Reliable Identification of Bounded-length Viruses is NP-complete» (0) 26.12Kb 2569 hits
IEEE Transactions on Information Theory, 49(1), pp. 280-284, January 2003. (2003)

A virus is a program that replicates itself by copying its code into other files. A common virus protection mechanism involves scanning files to detect code patterns of known viruses. We prove that the problem of reliably identifying a bounded-length mutating virus is NP-complete by showing that a virus detector for a certain virus strain can be used to solve the satisfiability problem. The implication of this result is that virus identification methods will be facing increasing strain as virus mutation and hosting strategies mature, and that different protection methods should be developed and employed.

«Chomsky Hierarchy and the Word Problem in Code Mutation» (0) 18.59Kb 1955 hits
(2008)

«A comment on Cohen's theorem about undecidability of viral detection» (0) 4.58Kb 1312 hits
Alive Vol I, Issue 0 (1991)

This paper shows that Cohen's Theorem, stating the undecidability of viral detection does not hold. It is shown that each algorithm discerning a virus from other program by examining its code must be a virus itself.

«In the trap of the language» (0) 18.3Kb 1272 hits
Alive Vol I, Issue 1 (1994)

There is a problem which bothered me since the results of Contest for the Best Virus Definition were published. It seemed that plain language was not suitable to define computer virus properly. Well, the problem of good definition of whatever is not anything new.

«A framework for modelling trojans and computer virus infection» (0) 91.42Kb 2864 hits
Computer Journal, 41(7), pp444-458, 1999. (1999)

It is not possible to view a computer operating in the real world, including the possibility of Trojan Horse programs and computer viruses, as simply a finite realisation of a Turing Machine. We consider the actions of Trojan Horses and viruses in real computer systems and suggest a minimal framework for an adequate formal understanding of the phenomena. Some conventional approaches, including biological metaphors, are shown to be inadequate; some suggestions are made towards constructing virally-resistant systems.

«Reply to `Comment on "A Framework for Modelling Trojans and Computer Virus Infection"' by E. Mäkinen» (0) 11.39Kb 1913 hits
THE COMPUTER JOURNAL, Vol. 44, No. 4, 2001, pp.324-325 (2001)

Computer viruses are a worrying real-world problem, and a challenge to theoretical modelling. In this issue of the Computer Journal, Erkki Mäkinen proposes universal Turing machines in a critique of an earlier paper, `A framework for modelling Trojans and computer virus infection' (Thimbleby, H., Anderson, S. O. and Cairns, P. (1998) Comp. J., 41, 444-458). This short paper is a reply by those authors.

«Algebraic Specification of Computer Viruses and Their Environments» (0) 44.74Kb 2815 hits
Selected Papers from the First Conference on Algebra and Coalgebra in Computer Science Young Researchers Workshop ({CALCO}-jnr 2005). University of Wales Swansea Computer Science Report Series {CSR} 18-2005}, pp.99-113 (2005)

This paper introduces an approach to formal specification of computer viruses and their environments through the development of algebraic specifications using Gurevich's Abstract State Machines (ASMs) and Goguen's OBJ. Distributed ASMs are used to develop a model of an abstract computer virus, which through a process of refinement is converted into models of different virus types. Further refinement has resulted in an executable specification, written in the Abstract State Machine Language, AsmL. The models strengthen the thesis that any algorithm can be modelled at a natural abstraction level using an Abstract State Machine. The ASM models combined with the AsmL executable specification provide a complementary theoretical and experimental framework for proofs and experiments on computer viruses and their environments, as well as a useful means of classification of different computer viruses types. Next we look at a different approach to computer virus analysis using OBJ, which is used to specify computer viruses written in an ad hoc programming language, SPL. The OBJ specification is shown to be useful for the detection of a virus type that is particularly difficult to detect - the metamorphic computer virus (MCV). Finally, the usefulness of the two specifications for reasoning about computer viruses is discussed and in this regard the two formalisms are compared.

«Classification of Computer Viruses Using the Theory of Affordances» (0) 71.03Kb 6402 hits
(2007)

We present a novel classification of computer viruses based on a formalised notion of reproductive models that use Gibson's theory of affordances. A computer virus reproduction model consists of a labelled transition system to represent the states and actions involved in that virus's reproduction; a notion of entities that are active in the reproductive process, and are present in certain states; a sequence of actions corresponding to the means of reproduction of the virus; and a formalisation of the affordances that apply. Informally, an affordance is an action that one entity allows another to perform. For example, an operating system might afford a computer virus the ability to read data from the disk. We show how computer viruses can be classified according to whether any of their reproductive actions are afforded by other entities, or not. We show how we can further sub-classify based on whether abstract reproductive actions such as the self-description, reproductive mechanism or payload are afforded by other entities. We give examples of three computer virus reproduction models constructed by hand, and discuss how this method could be adapted for automated classification, and how this might be used to increase the efficiency of detection of computer viruses. To demonstrate this we give two examples of automated classification and show how the classifications can be tailored for different types of anti-virus software. Finally, we compare our approach with similar work, and give directions for future research.

«Movement of Viruses» (0) 5.76Kb 2128 hits
(1999)

Computer virus (computer organism) movement may be one of the most important phenomena of computer viruses, but there was almost no study and no interest on this issue. So this subject is very much unknown, and especially about the self-movement.

«Some Further Theoretical Results about Computer Viruses» (0) 41.29Kb 3210 hits
The Computer Journal, Vol. 47, No. 6 (2004)

In this paper we give some general definitions of computer viruses which comply with our common understanding of computer viruses. Based on these definitions, we prove theoretically that there may exist some special kinds of computer viruses that have not been found in the real world yet. Furthermore, we prove that the set of computer viruses with the same kernel is ∏2-complete. In general the set of computer viruses is Σ3-complete.

«On the Time Complexity of Computer Viruses» (0) 40.43Kb 2619 hits
IEEE Transactions on Information Theory, Vol. 51, No. 8 (2005)

Computer viruses can disable computer systems not only by destroying data or modifying a system's configuration, but also by consuming most of the computing resources such as CPU time and storage. The latter effects are related to the computational complexity of computer viruses. In this correspondence, we investigate some issues concerning the time complexity of computer viruses, and prove some known experimental results mathematically. We prove that there exist computer viruses with arbitrarily long running time, not only in the infecting procedure but in the executing procedure. Moreover, we prove that there are computer viruses with arbitrarily large time complexity in the detecting procedure, and there are undecidable computer viruses that have no "minimal" detecting procedure.

24 authors, 30 titles