The article presents a new technique for metamorphic viruses detection based on the search of equivalent functional blocks. The method takes into account the obfuscation techniques of blocks reordering. The method involves the searching of the correspondences between the functional blocks of the metamorphic versions, and consists of two stages. On the first stage the equivalent functional blocks based on the statistical evaluation of the instructions appearance in the block are to be searched. The second stage involves the choice refinement of equivalent blocks and selection the most appropriate block, which will be used for the the forming of the feature vector of similarity for metamorphic viruses' versions. The method carries out the classification of feature vectors with the involvement of fuzzy logic. The proposed method allows to reduce the number of false positives in comparison with the previous study.
Among all set of virus programs the metamorphic viruses occupied one of the leading places. According to the Kaspersky company the metamorphic virus Virus.Win32. Sality.gen is in the top five of the most spread viral threats (5.53% of all local threats) [2]. The main difficulty of metamorphic viruses detection is due to usage of the techniques of reordering and replacement of its own instructions. Each new version created by the metamorphic virus varies from the existing ones. This feature downplays the signature analysis usage, which is the base of most antivirus tools [3].
This paper is devoted to solving the problem of the metamorphic viruses detection, where the similarities between its modified versions is more than 10%. In particular, researches presented in [4] have demonstrated that metamorphic versions’ similarity at about 10% is characteristic for NGVCK metamorphic generators. Versions of code, generated by this tool, are considered to be one of the most obfuscated. Other classes of metamorphic viruses in the work are not considered because they are unapplicable and have a large computational complexity for the development and detection [5]. 2
Research community pay particulat attention to the problem of the metamotphic viruses spread [6-10], however, the effectiveness of detection techniques is still unsufficient.
In [6] authors involved the markov chain of instruction trace to make graph kernel and made similarity matrix based on transition probability between instructions. The classification is made by using the support vector machine. Approach is based on the usage of Ether malware analysis framework based on Xen Virtual machine for execution of binary. It is able to identify more then 100 basic instructions by the monitoring procedure. It also is ble to execute the similarity check, which is based on the usage of the Guassian and Eigen vector method. This approach showed efficiency of detection at the level of 96.41%, including polymorphic viruses, which is significantly higher than the known antiviral tools, however, the authors didn’t take into account metamorphic viruses, which in many cases are similar to polimorphic.
In [7] the aproach for metamorphic malware detection is presented. It is based on the evaluation of the the similarity of executables using the opcode graphs. Technique involved the opcodes extraction from the program, and a weighted opcode graph construction. As a node of the the graph is opcode and there is an edge from the node to a successor opcode. The edge is given a weight. It takes into accoutn the frequency of opcode occurrence. Proposed approach perform the comparison of the obtained graph with the known malware graph. This comparison is based on a scoring function presented in the paper. However, the executable file size increasing leads to the increasing of the opcodes number and to the increasing of the graph size. In this case, the task can become the NP-complete.
In the [8] method for metamorphic viruses which is based on machine learning approach like support vector machine with histogram intersection kernel is proposed. It involves such steps: the extraction of the feature histograms from each portable executable file, mapping them into the feature space using a histogram intersection kernel. Using the histogram intersection kernel maked it possible to find the optimal hyperplane for separating the metamorphic variants from benign programs in a feature space of very high dimension.
In [9], metamorphic detection was carried out using a similarity index technique based on edit distance and pairwise sequence alignment. The edit distance between two opcode sequences extracted from files is computed by replacing each opcode with a corresponding symbol. Authors test these similarity measures on the challenging problem of metamorphic virus detection. The results from the edit distance and pairwise sequence alignment methods shows that the morphed viruses having random percentages of dead code and subroutine insertions (i.e., 5%, 15%, 25% and 30%) are still detectable within a certain error rate. However the approach does not consider the use of antiemulation technology that can use viruses.
In [10], to detect metamorphic virus variants, authors presented an approach based the use of hidden Markov models (HMMs) to capture the statistical properties of viruses in the same family. They generated 200 NGVCK viruses, trained 25 models and used the trained models to classify 65 programs including both NGVCK viruses and other random non-viral programs. In most cases, presented models were able to have a detection rate of over 90% and a false positive rate of less than 10%. However, if the benign software’s fragment of code is inserted into the metamorphic virus’s body, approach will demonstrate the increase of false positives.
The work [11] is based on the similarity matching techniques by mean of a statistical scanner employing feature-ranking methods. Approach investigated the feature-ranking methods such as Term Frequency – Inverse Document Frequency (TF-IDF), Term Frequency – Inverse Document Frequency – Class Frequency (TFIDF-CF), Categorical Proportional Distance (CPD), Galavotti – Sebastian - Simi Coefficient (GSS), Weight of Evidence of Text (WET), Term Significance (TS), Odds Ratio (OR), Weighted Odds Ratio (WOR), Multi Class Odds Ratio (MOR), Comprehensive Measurement Feature Selection (CMFS), and Accuracy2 (ACC2) as the base of metamorphic viruses detection. The classification of malware and benign programs is performed by considering top ranked features obtained using individual feature selection methods. In order to ascertain applicability in real time malware scanner, evaluation of feature ranking methods, were performed using McNemar test.
However, the proposed approaches based on statistical evaluation of instruction are uneffective for metamorphic viruses, which are using the technique of the code’s blocks replacement, because the frequency of the instructions occurrence in a modified version of metamorphic virus will not be changed.
A state of art demonstrates the necessity of the development of the new approaches for metamorphic viruses’ detection, which will be able to improve its efficiency. 3
In [12]presented a technique for metamorphic virus’s detection, based on the usage of the modified emulators in the corporate area network. In the proposed approach any program that comes from the Internet to the host is checked by the suspicion program analyzer and is sent to every host on the network. If the file is defined as suspicious, it goes to the emulation unit in order to obtain the modified versions of the same file. On the next stage the comparison of the original version of file before the emulation with the modified file’s version aftter emulation is performed. In order to compare two versions of program, it is partitioned into functional blocks and the comparison is performed using the Damerau-Levenshtein metrics. The result of the comparison process is the feature vector of the similarity for the metamorphic viruses’ versions. In order to provoke the metamorphic properties of program, each host of the network was equipped with a modified emulator, which had different conditions for suspicious code execution.
The similarity vectors for the versions of the metamorphic viruses, obtained from each host of the network, are sent to the server, where the conclusion about the membership of suspicious program to one of the metamorphic viruses’ classes is made. If such program is identified as a virus, information about it is sent to the host, which was infected by program, and the program is blocked.
Experimental results presented in [12] demonstrated the efficiency of the metamorphic viruses’ detection at the level of 85%. However, the proposed technique showed a great number of false positives. The main reason was that the functional blocks which were compared in order to obtain the feature vector of the similarity for the metamorphic viruses’ versions in many cases were not equivalent. 4
In order to eliminate the disadvantages of the technique described in [12] and increase its efficiency, a new approach for unknown metamorphic viruses’ detection is proposed. It includes improvements in the term of the functional blocks choice for its comparison, which will reduce the rate of false positives and increase the efficienty of detection.
The procedure of the equivalent functional blocks search for comparison consists of two steps. At the first stage, the equivalent functional blocks are determined. Such determination is based on the statistical evaluation of the instructions appearance in the block. The second stage involves the choice refinement of equivalent blocks and selection the most appropriate block, which will be used for the purpose of the rating evaluation of similarity between the program F p before emulation and the program Fs after the emulation.
Let us assume the functional block FB as the maximal sequence of disassembled instructions {I1, I2 ,...,Im , I j } that is characterized by the following properties: the control flow must enter the block from the first instruction; the block must not contain the instructions of unconditional or conditional jumps; the end of the block must have at most one control-flow instruction.
For automatic generation of functional blocks that meets such properties, the IDA Pro disassembler with Gaph view option was used. In order to simplify the analyzing and processing procedures, the operands of the instruction are ignored.
Let us describe a program F as a directed graph. Let us denote V – a set of functional blocks of program
F , that is
V {FB1, FB2,...,FBn} .
Thus E V V {True, False} is the jump in the the control flow between the blocks, caused by the control transfer instructions, where True and False specify the conditions of the jump, then F {V , E} it will be a directed graph, where the nodes are functional blocks, and the edges – connections between the blocks in the control flow of the program. 4.1
In order to avoid detection by antiviruses the metamorphic viruses use a wide range of evasion techniques, such as garbage instructions insertion (junk code), blocks reordering, usag of the equivalent instructions and registers [6-8]. The usage of these techniques allows creation of metamorphic versions with the same functionality, but using different instructions (table 1). It limits the advantages of the signature method. portant task is the localization of search. Because constituent units in the structure of executable files of the PE EXE format is sections, search of the equivalent functional blocks will be carried out only in certain sections.
Selection of sections, in which should be searched equivalent functional blocks between the programs before and after the emulation is carried out according to the following rules:
Determining the entry point of the program and section in which it located. - if the name of this section differs from the standard names of the sections (.text .data, etc) or the section has the attribute of the access as executable, then the section is defined as a labeled section for comparison;
- if in a section in which is located the entry point, has a call or a jump that contains the address of the last section, then the section is defined as a labeled section for comparison; - else last section of executable is defined as a labeled section for comparison.
After determining of PE EXE sections for the program before emulation and appropriate section for the program after emulation, the next step is to search of the equivalent functional blocks between these programs.
Let us assume the equivalent functional blocks of the programs A and B two or more functional blocks, which perform the same functions and are modified using the code obfuscation.
Let us denote the program before emulate as Fp , and after emulation – Fs . After the disassembly, performed by the interactive disassembler IDA Pro, two sets of functional blocks are obtained: FBFp { fb1Fp , fb2Fp ,..., fbmFp } and FBFs { fb1Fs , fb2Fs ,..., fbnFs } . Then in order to find the equivalent functional blocks the Term Frequency – Inverse Document Frequency statistical metric applied for each function block of programs Fp and Fs , is used: sFB
ni n k i * log(
N 1.0 n j ) (1) where, ni - the number of occurrences of the і-th opcode into the functional block;
k 1, ka – the number of opcode in functional block, where ka – total number of the assembler instructions;
N – total number of function blocks, NFp N Fs ; n j – the number of functional blocks where the і-th opcode is placed.
The result of the statistical evaluation of the presence opcode in FB for program before emulation F p and for the program after emulation Fs are the rating matrices
F M (FB p ) and M (FBFs ) . The rows of matrix contain the functional blocks of the program, and columns – the opcodes presented in the function block. Each cell of the matrix determines the appearance score of the i-th opcode in the j-th functional block (fig. 1): a) b)
In order to evaluate the equivalent functional blocks, the next step requires the calculation of the similarity score between two functional blocks of the program Fp and Fs . For this purpose, the squared Euclidean metrics was used:
E (FBiFp , FB Fjs ) k (si s j )2 , i0, j 0 (2) where, si – evaluation of the opcode appearance in the і-th block for program Fp , s j – evaluation of the opcode appearance in j-th block of program Fs .
If the value of similarity score between two functional blocks is less the defined threshold , E (FBiFp , FBFjs ) , then the recalculatio of similarity score between the functional blok of the program FBiFp and the next block that follows the block FB Fjs , E(FBiFp , FB Fjs FB Fjs1) , is performed. Mentioned above steps are repeated until the value of the evaluation of the similarity is less than or equal to the threshold . Threshold value is defined in experimental way.
It is possible that functional block of the program F p may correspond to several functional blocks of the program Fs (Fig. 2). The reason is that the metamorphic virus may apply the technology of the code partitioning of its code into blocks.
An example of a schematic presentation of the equivalent program’s functional block before and after emulation placed in the two-dimensional space is shown in Fig. 2. For example, one block of program before emulation, can correspond to 5 equivalent functional blocks of the program after the emulation. In ordr to to eliminate the uncertainty, it is necessary to carry out the choice refinement of equivalent functional blocks.
In order to perform the choice refinement of equivalent blocks let us define the probability of the opcodes sequence in the functional block. For this purpose for each equivalent functional blocks eFB1Fs , eFB2Fs ,...,eFBn s and block FBiFp let us conF struct a probability matrix for the opcodes sequence. Each cell of the matrix will consist the ratio of the number of the opcodes pair appearance to the total number the opcodes in the row.
For example, if functional block is defined by the following opcodes sequence: mov, push, lea, pop, mov, push, push, push, call,mov, then the probability matrix for opcodes sequence would be as shown in fig 3.
The last step of the equivalent functional blocks’ determination is comparing of the probability matrices of opcodes sequence for the program before and after emulation (4) and choice of the minimum similarity:
where, ai, j the matrix cell for the functional block FBFp , bi, j – the matrix cell for the functional block eFBFs , N – total number of opcodes for the pairs of blocks.
The obtained estimate for pairs of blocks allows determining the equivalent functional blocks with high probability.
R 1
N 1 ( | ai, j bi, j |)2 N 2 i, j 1 , (4) (4)
After receiving the pairs of the equivalent functional blocks, the next step is to pairwise compare them using Damerau-Levenshtein metrics and to construct the feature vectors of the metamorphic viruses’ samples’ similarity using the algorithm of Wagner-Fisher.
Let us present the the feature vectors of the metamorphic viruses’ samples’ similarity as a tuple:
L(1), X (1), D(1), I (1), R(1),M (1) Vm L(n ), X (n ), D(n ), I (n ), R(n ),M (n ),Y , where 1,...,n pairs of the equivalent functional blocks between the program before and after the emulation, n – a number of the equivalent blocks; L – the DamerauLevenshtein distance between the equivalent blocks і of the program before and after emulation; X – the number of the required opcode exchange operations; D – the number of the required opcode removal operations; I – the number of the required opcode insertion operations; R – the number of the required opcode replacement operations; M – the number of matches between opcodes in the equivalent functional blocks of the program before and after emulation; Y – the danger degree of the program’s behavior.
The danger degree of the program’s behavior is estimated on the basis of the analysis of API calls that describe the potentially dangerous behavior of the metamorphic virus. Let us present the behavior of the known metamorphic virus as a pattern (as bit K strings) P 1,...,n1,...,k1,...,l1,...,b1,...,u1,...,r , where {n}n0 – a set of file functions; {k }kK0 – a set of API functions that check whether the program execution is performed in the virtual environment; {l }lK0 – a set of functions needed to implement the installation of the new components to the system;
K {b}b 0 – a set of functions that provide access to the Internet; {u }uK0 – a set of processes’ and threads’ functions; {r }rK0 – a set of API calls for information system definition; K, K , K , K , K, K – a number of the corresponding to API calls; f - function of the destructive commands execution, which demonstrates the construction of the pattern for the metamorphic virus behavior P, f P .
Thus, the monitored suspicious program’s behavior we can present as the string R a1,...,a p , where ai – a sequence of the API-calls of the observed program.
Let us assume the boolean function of the string matching (P, R) between the known behavior pattern and the behavior of the observed program which indicates matching or mismatching.
Let us divide the set of behavior patterns PY {PYhigh , PYmedium , PYlow } into the three groups, which indicate the suspicious degree: high, medium and low.
Each group contains a set of patterns that describe the fullness of viruses’ lifecycle implementation. The example of patterns that belong to three different groups are given below: Yhigh : GetSystemDirectoryA FindFirstFileA OpenProcess Socket Connect Ymedium: GetSystemDirectoryA FindFirstFileA OpenProcess Ylow : GetSystemDirectoryA FindFirstFileA
Thus, having the behavior of the monitored program (formed pattern on the modified emulator of the host), it is to be compared with the set of with patterns of known malware. If there is a matching between the behavior of the monitored program and one malicious pattern, we are interesting in the suspicious degree Y of this pattern. It will be used in the procedure of the making the conclusion about the system infection with the metamorphic virus.
Note. In order to solve the string comparison problem the approximate string matching algorithm was used. It deals with the k differences problem solving. If we are given two strings, the sequence T = t1t2...tm and the pattern Φ=y1y2…yn in some alphabet Σ, and an integer k, the algorithm enables finding all substrings Φ' of T with the edit distance at most k from Φ. The edit distance intends the minimum number operations for editing (the differences) which are required for converting Φ' to Φ. [13]. The patterns preprocessing needs time O(mn). 4.4
In order to make a conclusion about the systems infection, the obtained feature vectors of the metamorphic viruses’ samples’ similarity from each host are to be classified by the means of the fuzzy inference system [14,15] (fig. 4).
The input linguistic variables of the FIS are: «the similarity degree of the suspicious program with its modified version based on the Lowenstein distance » (L), «the similarity degree of the suspicious program with its modified version based on the number of insert operations» (I), «The similarity degree of the suspicious program with its modified version based on the number of removal operations» (D ), «the similarity degree of the suspicious program with its modified version based on the number of replace operations» (R), «The similarity degree of the suspicious program with its modified version based on the number of permutation operations» (X) , «The similarity degree of the suspicious program with its modified version based on the number of match operations» ( M) and «the danger degree of the program» ( Y ).
Let us assume the output linguistic variable as «the similarity degree to the metamorphic virus» (SM).
Each input and output linguistic variables are defined by the term set: Low, Medium, High. As the membership functions for inputs the trapezoid was chosen, for the output - triangular. In order to determine the program’s similarity to metamorphic virus 87 rules are involed. For example, one of the rules can be presented as follows: if (L is Medium) and ( X is High) and (D is Medium) and (I is High) and and (R is Low) and (M is Medium) and (Y is High) then SM is High Having the result obtained by the fuzzy inference system, the suspicious program is blocked or continue its execution.
In order to determine the efficiency of the proposed technique series of experiments was conducted. To do this, the set of metamorphic virus versions’ were generated. For this purpose three types of metamorphic generators: Next Generation Virus Creation Kits (type NGVCK), Second Generation Virus Generator (type G2) and Virus Creation Lab for Win32 (type VCL32)[16] were used. Thus, the 228 programs with the features of the metamorphic viruses (76 programs of each NGVCK, VCL32 and G2 type) were generated. The set of all generated metamorphic viruses were divided into two groups: one group for training set (set of prototypes) and another for testing (38 instances in each).
Each program (from both sets) was executed in the emulator (Qemu [17]) for the purpose of its new version obtaining [12]. Each program was disassembled and partitioned into the functional blocks using the interactive disassembler IDA Pro [18]. In order to choose the equivalent functional blocks of the program, a new software that allows the similarity evaluation for a pair of functional blocks for the program before and after emulation was developed.
The similarity evaluation for a pair of functional blocks for the testing's programs before and after emulation and set of behavior patterns (as discussed above in Section 4.3 ) are the basis of the knowledge base for fuzzy classification.
Experimnts include the investigation of the number of correctly chosen equivalent functional blocks. Table 2 shows the average size of tested programs and the results correctly chosen functional blocks of the program before and after emulation in comparison with the approach [12], described in section 3, where the block reordering is not taking into account. Metamorphic Number of correctly Number of correctly The average viruse’s class chosen FB, % (ap- chosen FB, % (new programs size, bytes proach [12]) approach) NGVCK 85 96 8241 VCL32 88 100 6123
G2 91 100 2564 In order to evaluate the efficiency of the metamorpchic viruses’ detection, we calculated the true positive and false positive rates. In the experiments, the value of similarity score between two functional blocks was defined as the threshold =0.6 .
In addition, the efficiency of the proposed approach with taking into account the obfuscation degree of the generated metamorphic viruses’ versions was investigated. For this purpose, each metamorphic virus was obfuscated by the insertion of the junk code – 10%, 20% and 30% of the total number of opcodes of the metamorphic virus. In Fig. 5 the ROC curves for metamorphic versions without and with obfuscation and for different values of the obfuscation degrees for NGVCK, VCL32 and G2 types of the metamorphic viruses are presented. Fig. 5 shows that a minimum level of false positives without additional obfuscation is observed in all cases (the number of false positives for G2 – 0). The highest value of false positives is observed for metamorphic versions of NGVCK with 30% of additional code obfuscation (5% false positives while 85% true positives).
a) b) c)
The paper presents a new technique for metamorphic viruses detection based on the search of equivalent functional blocks. It takes into account the obfuscation techniques of blocks reordering.
The method involves the searching of the correspondences between the functional blocks of the metamorphic versions, and consists of two stages. On the first stage the equivalent functional blocks based on the statistical evaluation of the instructions appearance in the block are to be searched. The second stage involves the choice refinement of equivalent blocks and selection the most appropriate block, which will be used for the the forming of the feature vector of similarity for metamorphic viruses’ versions. The method carries out the classification of feature vectors with the involvement of fuzzy logic.
The proposed technique allows metamorphic viruses detection in which the similarities between versions are more than 10%. The technique demonstrates the low level of the false positives and high level of true positives of the metamorphic viruses detection. 3