MATHEMATICAL MODELLING OF COMPUTER VIRUSES
            WITH AUTOMATIZATION THEIR ANALYSIS AND
            CREATION THE VIRUS DEFENDING SYSTEMS.

             D.P.Zegzhda, A.V. Meshkov, P.V. Semjanov.
                     St. Petersburg, Russia.

			   Introduction.

  The effective fight against computer viruses is impossible without the
designed mathematical model which describes their structure and
principles of functioning[1]. The presence of such model will allow to
create the universal virus defending  systems, to prove their  efficiency
and to determine the application field. On the other hand, the  conditions
required for spreading  the viruses around  can be determined  and the
demands to the system, making  the existence of viruses impossible, can
be formulated.

1. Review of virus models.

  The basic work concerning  this field can be  conditionally referred
to three  directions:

  1.1 Theoretical research aimed at the creation of general mathematical
models, which describe viruses as the special programs or mathematical
objects[2,3].
  One of the most important work in this field is the work by  Adleman
L.[3], who considers viruses from the point of view of the theory of re-
cursive functions and Godel numbering.  In this work it is  offered to
model the virus characteristics (such as the ability to spread, to da-
mage, isolation, etc.)  with the help  of characteristic of  recursive
functions, reorganizing the  programs, which are  presented to be  the
Godel numbering of the set of all possible programs of Turing machine.
The definitions of pathogenicity and spreading of the viruses are  de-
fined and  the classification  is built  on their  base. The number of
theorems of existence and the theorem determining the completeness  of
the  set  of  viruses  are  proved  in mathematical terms of recursive
functions. However, all these virus  properties (it is shown in  work)
can not provide the base for creation of the concrete methods of  pro-
tection from them.

  These works create  the basis of  virus theory, but  their practical
use is limited by the possibility of interpretation of general models.
Let us review, for example, one  of the basic result obtained in:  for
all Godel numbering of the set of partly recursive functions {�1}  the
set V={i|  �1 is  a virus}  �2 is  complete. While  this statement in-
terprets and uses in  practice, the difficulties connected  with buil-
ding of predicates, determining if the testing program  belongs to the
virus set will inevitably arise.
  1.2. Defining of the  number of characteristics of  concrete viruses
and establishing the classifications on the base of these characteris-
tics. For example,  the famous McAffe  classification[4] can be  referred
here.
  Building of  such classification  is necessary  to identify  viruses
with each other and to form the homogeneous classes and groups of  vi-
ruses, however they can  not help to solve  the problem how to  search
for and delete the viruses.
  1.3. The production of the models describing the virus structure  as
the number of functional  elements, which determine the  typical algo-
rithms of influence of viruses on the other objects such as  programs,
data, environment. The example of  such approach is shown in.  The la-
test approach looks the most perspective due to the fact that it enab-
les to get practical solutions to the problems set up in the beginning
of this article. The simulation  of process of infecting the  programs
with viruses represented further in this work is referred to the  last
group of models.

2. Models of computer viruses.

2.1. Simulation of the process of infecting the programs.

  In the present work was used the approach based on representing  the
virus as the program which inserts its own copy modified in a  special
way to another program. With  that the part of programming  code which
is never modified is called  signature of the virus which,  thus, will
be able to met in all its copies without exception[5]. Usually, the frag-
ment of the code typical for this virus is taken as the signature.
  Let us determine the base elements of the model suggested.
  Let's consider the structure of infected program and virus is repre-
sented by the sequence of bytes. That approach is less abstract and is
based on practical developments (seeking for virus using the signature
is widely used) and enables to get a real result - to build the  algo-
rithm which determine the virus signature.
  We will consider the process of infecting a program as synthesis  of
a new  program which  consists of  mutually adopted  copies of initial
program and the virus.
  We will represent the program, virus and signature  as the vectors,
which components are bytes. The numbers of vector elements  start
from 0.  We will write the vector size after its name in round  brac-
kets, the index in square ones.
  Let us introduce  the algebra of  the type A=<M,S>,  where the set
M (carrier) - the set of all  byte vectors (i.e. the set of  all prog-
rams, e.g. viruses), �nd S(signature  of algebra) - consists of  two
binary operations - equality and insertion.
  Let us determine this set of operations:

   1) Equality operation ( "=" ). We will  accept that vector X  with
the length n is  equal to vector Y  also n long under  the condition
that X and Y are  equal in pairs, i.e.:

    X = Y  <=>   { X[i] = Y[i] � i: 0..n-1 }

   2) Inserting operation ( Let's designate it with the sign "+").  If
we have two vectors A with the length n and B with the length m,  then
the result of insertion B into A is vector C which length is n+m, that
answers the following condition:

                          �                                �
                          �        � A[i]   for 0<=i<k     �
 A(n) + B(m) = C(n+m) <=> � C[i] = � B[i-k] for k<=i<k+m   �
                          �        � A[i-m] for k+m<=i<m+n �
                          �                                �
                          where k: 0..n-1

   The fact of  infecting the program with the virus, can be described
in terms of operator theory in general case as follow:

    Pinf=V(P), where

 V - operator of infecting a program with a virus;
 P - clean program;
 Pinf - infected program;

  Let us consider more thoroughly the infecting operator for signature
file viruses. The process of infecting the programs with viruses  con-
sists of the following stages:

  1) The entering of the distortions  into the program which is to  be
infected. This means  the virus actions  aimed to reorganizing  of the
program into the virus bearer. First of all is provided the processing
passing to the virus  code and secondly the  space for the placing  of
the code is created (deleting of some parts of the program, increasing
of the file size, moving of some fragments of the program from the be-
ginning to the end, etc.  including even program encoding or  compres-
sing).
  We will call the operator that realizes these actions the distortion
operator and sign it as D(p). The operator reforms the program p  into
distorted program ready to be connected with the virus.

  2) The adjustment of the viruses  to the program which is to  be in-
fected. Adjustment here means the  process of creation the virus  copy
which is able to function  in that program. This involves  the address
adjustment,  variables  initialization,  storing  the infected program
elements in virus  code, etc. We  notify that the  part of virus  code
which is not modified during the process of adjustment is called  sig-
nature.
  We will  call this  operator the  adjustment operator  and sign it
A(p). This operator  performs the adjustment  the virus for  work in
program p.

  3) The insertion  of virus code  into the program  to be infected.
This means  the process  of insertion  of the  virus  copy adjusted for
this program into  the program body.  This  process in  the simplest
case can consist  of concatenation of  program and virus,  besides
there can be applied the  complex algorithm of breaking of the  virus
into few fragments  and their insertion  to the different  places of
the program.
  We will call this the  infecting operator and sign as  I(p,v). The
operator inserts the virus v copy adjusted to this program into the
program p ready to be infected.

  The process of infecting the  program
p with some virus having Sign as  a signature  after getting the in-
fected program is described in terms of these operators with the
following equation:


  I( D(P), A(P) + Sign ) = Pinf, where

 D(P) - program after influence of the distortion operator;
 A(P) - virus, adopted to the program;
 Sign - virus signature;

  Set in this way, the analysis task will come to finding of the signature
Sign using which we  can monosemantically determine the  virus presence
within  the program  and (in  case of their presence) the  operators
contrary to I and D, allowing to restore the infected program.
  Let us show how to find  the signature of file virus within  the li-
mits of this  model if its  distortion operator answers  the condition
defined below.
  We use special target-files to find the signature . They are  typi-
cal programs, consisting of trivial commands and having the  typical
peculiarities which  are used by viruses when infecting the  prog-
rams. It is necessary to have  the number of such targets of  diffe-
rent characteristics, i.e. some virus  infect only files  with the
definite characteristics.

  Let us have a target t infected by virus with the signature :

   I( D(t), A(t) + Sign ) = tinf

  We'll admit that distortion  operator D(t) realizes only  rearrange-
ment the  target fragments  and does  not change  bytes which form it.
Thus, we have  introduced the restriction  for the class  of signature
file viruses for which the suggested method is true. This condition is
true for absolute majority of signature file viruses. However, if  the
virus still distorts the program parts the method will give the  right
result if the changes are not very considerable.
  So, in this case we have the file in which the fragments of the  co-
des of target and virus are mixed. As we do not know the codes of tar-
get commands, we can remove them from the file and thus, mark out  the
specimen of virus. We'll name it as  Vt:

    A(t) + Sign = Vt

  The virus consists of adjustable  part, in which the signature  is
input. In  order to  find it we  need at  least two targets infected
with the same virus:

    A(t1) + Sign = Vt1
    A(t2) + Sign = Vt2

  Getting the signature  from this system  of equations means  finding
the largest common sequence of two byte vectors (Vt1 � Vt2). The algo-
rithm which solves this problem effectively exist.
  The task of finding  the operators contrary to  I and D can  also be
solved (because we can easily separate the target from the virus), but
in this model the virus semantics is not considered at all and the re-
sults will not be reliable  on, i.e. the algorithm of  these operators
mostly depends on characteristics of infected program.
  The suggested model have been be used for building perspective  uni-
versal self-teaching antiviral means based not on different system  of
seeking for viruses, but on their complex analysis that allows to work
out the effective methods against any unknown virus.

2.2 Conceptual model of computer viruses.

    The conceptual  representation of viruses is the most approximate to
practice. The  development of conceptual  models permits to  receive
not such a general results as at mathematical simulation, however  such
approach permits to present the virus at functional level. From  point
of view  of creation  of theoretical  base of  detection of viruses,
such representation allows: first, to create the integrated conceptual
model of viruses, to structure knowledge about them;
   Secondly, to create the system of counteraction on the basis of te-
leological search of functional  elements of viruses in  applied prog-
rams; thirdly to synthesize  the viruses for  researches of mechanism  of
their work.

2.2.1 Conceptual definitions of viruses.

    We allocate three groups of functions, inherent exclusively to vi-
ruses. Let's consider, that these  functions are necessary for viruses  -
e.g. neither of useful program can use it.

 1. Self-reproduction function .
  Unfortunately, the exact definition of concept of  self-rep-
roduction on relation to programs don't exist.
  By analogy with biological systems we shall consider that the proper-
ty of self-reproduction means the ability to generate some program code.

  2. Function of overcoming of protection.
    This function means the attempt to overcome system and / or  addi-
tional protection.  The security  system which  is the  part of opera-
tional system (OS) (system  of users' identification, control  of file
access, protection of  OS kernel) is  understood under system  protec-
tion. All components of security system, that are not the parts of  OS
(usually it is  cryptography system, etc)  are understood under  addi-
tional protection.
    The fact of overcoming of system of protection means the  realiza-
tion of actions, forbidden by protection system (obtaining  non-autho-
rized access, getting of password, etc).

  3. Function of violation  of integrity of operating  environment The
damage to components of  computing environment distortion or  destruc-
tion of data and programs, as well as grab of system resources is  un-
derstood  under function  of violation  of integrity  of operating en-
vironment

 Thus, it is possible to give the conceptual definition of the virus:

  By saying "virus" we shall understand the fragment of program code which
  realizes at least one of these functions.

2.2.2 Classifications of viruses  on the basis of their  conceptual repre-
sentation.

   We can allocate seven types of viruses in dependence on combination
of main functions which virus has.

������������������������������������������������������������������Ŀ
�                  � Classification                                �
������������������������������������������������������������������Ĵ
� Function         �       Spreading       �   Worms   �  Trojan   �
�                  �       programs        �           �   horse   �
������������������������������������������������������������������Ĵ
� Self-reproduction� XXX � XXX � XXX � XXX �     �     �           �
������������������������������������������������������������������Ĵ
� Overcoming of    �     � XXX �     � XXX � XXX � XXX �           �
� protection       �     �     �     �     �     �     �           �
������������������������������������������������������������������Ĵ
� Violation of     �     �     � XXX � XXX �     � XXX �    XXX    �
� env. integrity   �     �     �     �     �     �     �           �
��������������������������������������������������������������������
                      �     �     �     �     �     �
                      �     �     �     �     �     �
 safe        ����������     �     �     �     �     �
 penetrating ����������������     �     �     �     �
 destructing ����������������������     �     �     �
 destructing and penetrating ������������     �     �
 safe      ������������������������������������     �
 destructing ����������������������������������������

         Fig.1. The classification of viruses.



2.1.4. Integrated conceptual model of the virus

  After entering the additional  set of possible functional  elements:
Procedure of self-modifying ( mutation); procedure of synthesis;  pro-
cedures of stealth and encoding and etc., it is possible to  construct
the integrated conceptual model of virus ( fig. 2 ), in the aspect  of
the set of its functional elements. The integrated model reflects  the
probable structure ( on  semantic level ) of   three  main classes  of
viruses.



      �� for A                                  � for B � C
      �                                         �
  �������Ŀ                            �������������������Ŀ
  ������ͻ�                   �����ͻ  � �����ͻ           �
>���  1  ��������������������Ķ  3  ����¶  4  ��������������>
   �����ͼ ������Ŀ�������Ŀ� �����ͼ   ������ͼ� ������Ŀ�
           ��  2  ����  5  ��           ������Ŀ� ��  7  ��
            �������  �������            ��  6  ��  �������
                                         �������


 Designation:

 ����ͻ                             �����Ŀ
 �    � � main function             �     � � additional functions
 ����ͼ                             �������

 � - Spreading programs.
 B - Worms.
 � - Trojan horses.


 1 - overcoming of protection    5 - stealth or encoding
 2 - intercept of processing     6 - synthesis
 3 - violation of integrity      7 - self-modifying or mutation
 4 - self-reproduction

       Fig.2. The integrated conceptual model of the virus.


   Now it is possible to define the base criteria of identification of
belonging of the virus to particular  class on the basis of this  con-
ceptual model , and then on their basis we can determine the  criteria
of localization of their elements in the software.

3. System of construction of models of computer viruses.

  The creation of  similar conceptual models  allows to construct  the
system, which research the behavior and structure of particular  viru-
ses. Such system can serve as the laboratory for analysis of  viruses,
systems of protection from them and for creation of such systems.

 3.1 Tasks of system of construction of models:

     1) Analysis of viruses with the purpose of study:
        - algorithms of its spreading and affects.
        - interactions of systems of protection and viruses.
  The mathematical model of program infection is used in the process
of researching for extraction of virus code.
  The purpose of  research is the  valuation of efficiency  of studied
system of protection and determination of optimum means of  protection
from virus.

     2) Classification of viruses.
   The mechanism  of realization  of functions  of self-reproduc-
tion, overcoming of protection and violation of integrity by  vi-
rus for distinguish of viruses  to that or other classes  must be
determined as a  result of  analysis.

     3) Concretization of integrated model.
   Having determined the belonging of studied virus to certain  class,
the construction  of its  model in  the help  of the concretization of
functions of self-reproduction, overcoming of protection and violation
of integrity becomes possible.

   The cycle  of work  of the  system consists  in analysis of earlier
unknown  virus,  definition  of   mechanism  of  realization  of   its
functions, it's distinguishing to the certain  class, construction  of
private model, testing of present  means of protection on given  model
and, possibly, generation of  means of counteraction to  viruses, cor-
responding to the given private model.

   The structure of system is submitted on fig. 3.

                           The virus
                               �
                       ���������������Ŀ           ����������������Ŀ
                       �    Virus      �����������Ĵ Mathematical   �
                       �  analysis     �           �model of viruses�
                       �����������������           ������������������
                       ���������������Ŀ
                       � Virus         �           ������������Ŀ
                       � classification�����������Ĵ Integrated �
                       �����������������        �  �   model    �
                       ���������������Ŀ        �  ��������������
                       � Model         ����������
                       � concretization�
                       �����������������
                    �����������������������Ŀ
                    �          �            �
                    �  ���������������Ŀ    �
                    �  �  Generation   �    �
                    �  �    means of   �    �
                    �  �  protection   �    �
                    �  �����������������    �
                    �         �             �
                    ���������Ĵ             �
      ����������Ŀ    ���������������Ŀ     �
      � Means of ����Ĵ Test means of �     �
      �protection�    �   protection  �     �
      ������������    �����������������     �
                              ���������������
                              �


    Fig. 3. The structure of system of construction of models of viruses.

 1. Cohen F. Computer viruses - theory and experiments. Proceedings of
the 7th National Computer Security Conference.- 1984.
 2. Cohen F.  Computer viruses. Theory  and experiments. Adv.  Comput.
Syst. Secur. Vol. 3 - Norwood(Mass), 1988, p 1-19
 3. Leonard M. Adleman. An  Abstract Theory of Computer Viruses.  Pro-
ceedings  of CRYPTO-88 conference.
 4. File VIRLIST.TXT by McAfee Associates.
 5. Pozzo M. M., Gray T. E. Managing Exposure to Potetially  Malicicus
Programs // Proceedings of the 9 National Computer Security  Conferen-
ce, Sept., 1986.