6.3 Static Analysis
The static analysis is designed to detect abnormal behaviour in programs due to virus infections but could easily be extended to also detect boot sector viruses and macro viruses found in word and excel documents. We call it a static analysis because we analyse the complete static code of a program.
The basic idea is to built a normal behaviour profile for all the normal and uninfected programs and then afterwards monitor the programs to see if any programs deviate from this profile. The normal behaviour profile is built by training one or several HMMs on the uninfected programs and the probability of observing the uninfected programs in the HMMs is saved. To detect abnormal behaviour the probability of observing the programs in the trained HMMs is computed and if any of these deviate from the saved probabilities we know that a program has changed behaviour. The general procedure looks like this:
Training:
1. Train HMMλfor programO.
2. Extract probability of observing programOin λ: P(O|λ).
3. SaveλandP(O|λ) in database.
Detecting:
1. Compute probability of observing the possibly infected program ´O in λ:
P( ´O|λ).
2. IfP( ´O|λ)6=P(O|λ) the behaviour of the program has changed.
6.3.1 Building a Normal Behaviour Profile
To represent the normal behaviour of one or several programs we use HMMs. We can do this because HMMs say something about the behaviour of the sequences they are trained for. The beautiful feature of HMMs is that they can be trained for any sequences of symbols without having any knowledge about what the sequences represent and still be able to say something about the behaviour of the sequences.
The most obvious way to make a normal behaviour profile for a program is simply to train the HMM on the complete binary code of the program. In this way all information about the program will be represented in the HMM. But the bottle neck with using the complete binary code of the program to train the HMMs is that it takes a lot of time. So to make the system more efficient it might be a good idea to train the HMM on a representation of the program instead of the complete binary code of the program.
The binary code of a program often consists of a header, different kinds of identification information, and then code and data segments. What we are interested in here is the behaviour of the program, mostly reflected by the code
segments but also by the data segments in the program. The code segments contain instructions which can be executed and the data segments contain data like constant values, character strings, data areas, screen images, etc. We can therefore choose to represent a program by its code and data segments, and still have the complete behaviour of the program. We could also go even further and only represent the program by its code segments, making an even smaller representation of the program and still representing most of the behaviour of the program.
Quite another approach to represent the programs in the system is by compress-ing them uscompress-ing already known compression algorithms. We could for instance use compression algorithms like zip or gzip. The only problem with this ap-proach is that the compression algorithms might change the complete structure of the program in such a way that it is not possible for the HMMs to detect ab-normal behaviour. The compression algorithms might rearrange some sequences or blocks of instructions in such a way that the behaviour of the program is com-pletely destroyed.
When training the HMMs to represent the behaviour of uninfected programs several approaches could be chosen: Train one HMM for every program in the system, divide all the programs in the system into categories and train one HMM for the programs in every category, or simply train one HMM for all the programs in the system.
Training one HMM for every Program
Training a HMM for one program will iteratively maximise the probability of observing exactly that program in the HMM. The training iteratively makes the probability of observing the program in the HMM better and better until the probability of observing the program finally converges. When the training is over we will have a HMM representing the behaviour of the program and can compute the probability of how well the program matches the HMM. Off course we would like this probability to be as close to 1 as possible, but often this is not the case and we therefore have to save the value so we can compare it with subsequent probabilities of observing the possible infected program in the HMM. The procedure for training one HMM for every program looks like this:
Training:
1. Train HMMλfor programO.
2. Extract probability of observing programO inλ: P(O|λ).
3. SaveλandP(O|λ) in database.
The HMM λ will together with the probability P(O|λ) make up the normal behaviour profile for the programO.
6.3 Static Analysis 67 Training one HMM for several Programs
Training a HMM for several programs will iteratively maximise the average probability of observing each of the programs in the HMM. After training we should extract the probabilities of observing each of the programs in the HMM, so we can compared these values with subsequent observations of possible in-fected programs. The procedure for training several programs for one HMM look like this:
Training:
1. Train HMMλfor the programs O(1), O(2),· · ·, O(n). 2. Compute probability of observingO(1), O(2),· · ·, O(n) inλ:
P(O(1)|λ), P(O(2)|λ),· · ·, P(O(n)|λ).
3. SaveλandP(O(1)|λ), P(O(2)|λ),· · ·, P(O(n)|λ) in database.
The HMMλwill together with the probabilitiesP(O(i)|λ) make up the normal behaviour profile for theith programO(i).
6.3.2 Detecting Abnormal Behaviour
To check whether or not a program is infected with virus, we try to detect if the static code of the program has changed behaviour in some way. We find the HMM saved in the database which represents the normal behaviour of the program and compute the probability of observing the program in the HMM. If the computed probability has change from the probability saved in the normal behaviour profile we know that the program has changed behaviour.
The procedure for detecting abnormal behaviour looks like this:
Detecting:
1. Compute probability of observing the possible infected program ´O in λ:
P( ´O|λ).
2. IfP( ´O|λ)6=P(O|λ) the behaviour of the program has changed.
The procedure for detecting abnormal behaviour is the same whether or not the HMM is trained for one program or several programs.
An often arising question is how often we should check whether or not the pro-gram has changed its behaviour. Should this be done periodically or randomly or should we choose a completely different approach? Well, before a program can change its behaviour the binary code of the program must be changed in some way. The only way to change a program is by writing code to it and the most normal way of doing this, and in some systems the only way, is by using the operating system’s write call. So by intercepting the operating system’s writecall on a program, we know that the program could in theory now contain a virus. In other words whenever a program has been written to, we check to see if it has changed its behaviour indicating a possible virus infection. If it is not possible to intercept the system calls or if the operating system allows
writing to executable files without using thewritecall, we need to periodically test the programs for changed behaviour.
When a program is tested for abnormal behaviour we compute the probability of observing the program in the HMM and compare it with the probability saved in the normal behaviour profile as mentioned before. To get an expression of how well the program matches with the normal behaviour we can calculate the match affinity:
Pma=P( ´O|λ) P(O|λ),
where ´O is the possible infected program,O the original program, andλis the HMM trained for the original program.
In some systems the static behaviour of a program might be allowed to change a little bit, so in these system it is not enough simply to see if the probability has changed from the probability saved in the normal behaviour profile. Under these circumstances the match affinity could be used to find an expression for the size of the changed behaviour. This value could simply be found as: 1−Pma.
6.3.3 Discussion
The bad thing about the static analysis if using periodical tests on programs is that the virus might be able to infect several files before we are able to notice it. Another thing that the static analysis do not take into account is the installation of new programs on the system, this method assumes that we have a static system, and no new programs are added after the training has been carried out. It is possible to re-train a HMM to also include a new program, but before doing this one should really be sure that the new program is not infected with a virus!