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

VX Heavens

Library Collection Sources Engines Constructors Simulators Utilities Links Donate Forum

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

«An Abstract Theory of Computer Viruses» (0) 40.82Kb 15228 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) 38.2Kb 7505 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.82Kb 7174 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.54Kb 7842 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) 7240 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 24996 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 Cost Analysis of Typical Computer Viruses and Defenses» (0) 41.79Kb 2125 hits
Computers & Security, Volume 10, Issue 3, pp.239-250 (1991)

Various properties of computer viruses have been studied at length by many authors [1], but one of the areas where research results are relatively rare is evaluation of the costs of defenses. In this paper, we explore the costs of computer virus defenses in typical computing environments.

«A Formal Definition of Computer Worms and Some Related Results» (0) 41.82Kb 9906 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.65Kb 7580 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 5019 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.

«A Short Course on Computer Viruses» (0) 558.4Kb 5084 hits
ASP Press (1990)

It is rare in the computer world to find someone both technically and verbally adept. It is even rarer to find yourself laughing out loud when reading a computer text. Fred Cohen is not only a pioneer in the field of virus research, but also a superb storyteller. Cohen provides an engaging account of viruses, his early experiments, and his struggle to convince security experts that viruses are a real threat. In one of his most memorable anecdotes, Cohen describes a visit to a security trade show where - to the dismay of the experts - he swiftly demonstrates how even the lowest level employee has the ability to breach the system's defenses. As an expert in the field, he is often given credit for coining the term "computer virus." In fact, his famous 1984 paper brought about the first real interest in viruses from both researchers - and unfortunately - virus creators. A Short Course on Computer Viruses is largely theoretical in nature, and while Cohen does not discuss the commercial anti-virus packages, he does explain how they work and what their limitations are.

«Self-Replicating Turing Machines and Computer Viruses» (0) 17.25Kb 5793 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.49Kb 5238 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.47Kb 9158 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.91Kb 9735 hits
Journal In Computer Virology vol. 1, no 2 (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.

«Email networks and the spread of computer viruses» (0) 23.73Kb 153 hits
Phys. Rev. E 66, 3 (2002)

Many computer viruses spread via electronic mail, making use of computer users’ email address books as a source for email addresses of new victims. These address books form a directed social network of connections between individuals over which the virus spreads. Here we investigate empirically the structure of this network using data drawn from a large computer installation and discuss the implications of this structure for the understanding and prevention of computer virus epidemics.

«A Mathematical Theory for the Spread of Computer Viruses» (0) 22.69Kb 8290 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.

«Computer Viruses: Myth or Reality?» (0) 20.83Kb 2209 hits
National Computer Security Conference Proceedings (10th): Computer Security - From Principles to Practices, 21-24 September 1987, pp.226-230 (1987)

This paper will show that a computer virus [COHEN] may be no more a threat to computer systems than a Trojan Horse and any protection mechanism that will work against a a Trojan Horse will also work against against computer virus, specifically a mandatory policy (e.g. [BELL/LAP] [BIBA]) In addition, it will discuss two possible protection mechanissms that address the Trojan Horse threat.

«A fault tolerance approach to computer viruses» (0) 30.36Kb 2434 hits
Proceedings of 1988 IEEE Symposium on Security and Privacy, pp. 52-58 (1988)

The applicability of fault tolerance techruques to computer security problems is currently being investigated at the UCLA Dependable Computing and Fault-Tolerant Systems Laboratory. A recent result of this research is that extensions of Program Flow Monitors and N-Version Programming can be combined to provide a solution to the detection and containment of computer viruses. The consequence is that a computer can tolerate both deliberate faults and random physical faults by means of one common mechanism. Specifically, the technique described here detects control flow errors due to physical faults as well as the presence of viruses.

«A note on Cohen's formal model for computer viruses» (0) 8.41Kb 6099 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 6171 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) 5256 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.78Kb 6803 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.84Kb 6527 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.2Kb 6703 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.67Kb 5657 hits
(2008)

In this article you will first read shourtly about the formal grammar and word problem including the reason why this is important for virus authors. (Chapter 2)

«A comment on Cohen's theorem about undecidability of viral detection» (0) 4.58Kb 5113 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 4662 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.

«The results of the Contest for the Best Virus Definition in technical categories» (0) 8.55Kb 136 hits
Alive Vol I, Issue 0 (1994)

The results of the contest for the best definition in two categories 1. Technical definition in plain language, 2. Mathematical technical definition

«A framework for modelling trojans and computer virus infection» (0) 93.55Kb 6987 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.41Kb 5125 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.86Kb 6453 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.11Kb 12868 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 5201 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.79Kb 7423 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.53Kb 6874 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.

27 authors, 36 titles