Researches On Abstract Theories Of Computer Viruses And Computer Virus Description Languages

theories of computer viruses are important for understanding computer viruses, studying basic properties and mathematical features of computer viruses and guiding anti-virus practice. After the first abstract theory of computer viruses, based on Turing machine and coined by F. Cohen, several significant theories were proposed and studied in detail, and some important results about computer viruses had been obtained. There are two most important conclusions, the first is that it is impossible to detect all possible computer viruses; the second is that there exist computer viruses whose all infected programs can not be exactly detected out. However, it should be noticed that with the development of research on computer viruses, these abstract theories somewhat are over-abstracted and have some obvious deficiencies.Firstly, abstract theories of computer viruses in present no matter Turing machine based or recursive function based, their definitions of computer viruses are so imprecision in some sense that some programs covered are not regarded intuitively as computer viruses by most people. Secondly, maybe more seriously, they lack theoretical constructions to define common (or special) kinds of computer viruses, such as resident virus, polymorphic virus, and multipartite virus, which results in impossibility to study basic properties of these common kinds of computer viruses. Finally, there is so little research on computational complexity of computer viruses and therefore we know nothing about it at all.With the development of anti-virus practice, computer virus description languages have been created in some anti-virus software. Hereafter, they play more and more important role for enhancing flexibility of anti-virus software and sharing and accumulating of knowledge on computer viruses. But, most of present virus description languages so far just have simple language constructions and weak descriptives that usually need the support of low-level languages when describing complicated viruses. At the same time, computer virus description languages still are in progress, and have not come to the industrial standards yet.Aimed to above problems, this dissertation is devoted to deep research on abstract theories of computer virus and computer virus description language. The author's contributions presented in this dissertation are summarized as follow,1. Infection of programs is defined, and a new definition of computer viruses based infection of programs is given. Furthermore, definitions of imitation and ∞- imitation of programs are given, and a natural hierarchy of computer viruses is obtained in term of different properties of imitation, i.e. V₀, V₁ and V₂. The strict inclusion of the hierarchy, i.e. V₀(?)V₁(?)V₂, is...