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. There are two spellings for the plural of virus; 'virusses', and 'viruses'. We use the one found in Webster's 3rd International Unabridged Dictionary Given the wide spread use of sharing in current computer systems, the threat of a virus carrying a Trojan horse [Anderson72] [Linde75] is significant. Although a considerable amount of work has been done in implementing policies to protect from the illicit dissemination of information [Bell73] [Denning82], and many systems have been implemented to provide protection from this sort of attack [McCauley79] [Popek79] [Gold79] [Landwehr83], little work has been done in the area of keeping information entering an area from causing damage [Lampson73] [Biba77]. There are many types of information paths possible in systems, some legitimate and authorized, and others that may be covert [Lampson73], the most commonly ignored one being through the user. We will ignore covert information paths throughout this paper.
The general facilities exist for providing provably correct protection schemes [Feiertag79], but they depend on a security policy that is effective against the types of attacks being carried out. Even some quite simple protection systems cannot be proven 'safe' [Harrison76]. Protection from denial of services requires the detection of halting programs which is well known to be undecidable [Garey79]. The problem of precisely marking information flow within a system [Fenton73] has been shown to be NP-complete. The use of guards for the passing of untrustworthy information [Woodward79] between users has been examined, but in general depends on the ability to prove program correctness which is well known to be NP-complete.
The Xerox worm program [Shoch82] has demonstrated the ability to propagate through a network, and has even accidentally caused denial of services. In a later variation, the game of 'core wars' [Dewdney84] was invented to allow two programs to do battle with one another. Other variations on this theme have been reported by many unpublished authors, mostly in the context of night time games played between programmers. The term virus has also been used in conjunction with an augmentation to APL in which the author places a generic call at the beginning of each function which in turn invokes a preprocessor to augment the default APL interpreter [Gunn74].
The potential threat of a widespread security problem has been examined [Hoffman82] and the potential damage to government, financial, business, and academic institutions is extreme. In addition, these institutions tend to use ad hoc protection mechanisms in response to specific threats rather than sound theoretical techniques [Kaplan82]. Current military protection systems depend to a large degree on isolationism, however new systems are being developed to allow 'multilevel' usage [Klein83]. None of the published proposed systems defines or implements a policy which could stop a virus.
In this paper, we open the new problem of protection from computer viruses. First we examine the infection property of a virus and show that the transitive closure of shared information could potentially become infected. When used in conjunction with a Trojan horse, it is clear that this could cause widespread denial of services and/or unauthorized manipulation of data. The results of several experiments with computer viruses are used to demonstrate that viruses are a formidable threat in both normal and high security operating systems. The paths of sharing, transitivity of information flow, and generality of information interpretation are identified as the key properties in the protection from computer viruses, and a case by case analysis of these properties is shown. Analysis shows that the only systems with potential for protection from a viral attack are systems with limited transitivity and limited sharing, systems with no sharing, and systems without general interpretation of information (Turing capability). Only the first case appears to be of practical interest to current society. In general, detection of a virus is shown to be undecidable both by a-priori and runtime analysis, and without detection, cure is likely to be difficult or impossible.
Several proposed countermeasures are examined and shown to correspond to special cases of the case by case analysis of viral properties. Limited transitivity systems are considered hopeful, but it is shown that precise implementation is intractable, and imprecise policies are shown in general to lead to less and less usable systems with time. The use of system wide viral antibodies is examined, and shown to depend in general on the solutions to intractable problems.
It is concluded that the the study of computer viruses is an important research area with potential applications to other fields, that current systems offer little or no protection from viral attack, and that the only provably 'safe' policy as of this time is isolationism.