CN107943754B

CN107943754B - Heterogeneous redundancy system optimization method based on genetic algorithm

Info

Publication number: CN107943754B
Application number: CN201711293889.7A
Authority: CN
Inventors: 汤景凡; 胡恩超; 张旻; 姜明; 梁惠兵
Original assignee: Hangzhou Dianzi University
Current assignee: Baoding Ziyu Technology Co ltd
Priority date: 2017-12-08
Filing date: 2017-12-08
Publication date: 2021-01-05
Anticipated expiration: 2037-12-08
Also published as: CN107943754A

Abstract

The invention discloses a method for optimizing a heterogeneous web system by integrating genetic algorithm and similarity calculation. Aiming at the lack of steps of evaluating the heterogeneous degree of heterogeneous systems in the prior art and the defects of uncommon traversal scheme, the invention makes reasonable use of it first. The existing source code detection scheme introduces a subjective judgment mechanism for undetectable scenes to calculate the code similarity. The similarity is calculated by combining the calculated similarity value with the prior knowledge of the security part of the unit. According to the similarity, the fitness function required by the genetic algorithm is proposed. Finally, the system to be optimized is substituted into the genetic algorithm under the fitness function for optimization. The web heterogeneous system optimized by this method has better defense capability.

Description

Heterogeneous redundancy system optimization method based on genetic algorithm

Technical Field

The invention designs a method for optimizing a heterogeneous redundancy system, and particularly relates to a heterogeneous redundancy system optimization method based on a genetic algorithm.

Background

The heterogeneous redundancy design mode realizes multilevel isomerization of server software, a file system, an operating system and the like on an executive body set. Although heterogeneous systems are diverse in design and implementation, and different in techniques and means, the goal of heterogeneous systems is to protect the confidentiality of system data from the point of intrusion prevention. The heterogeneous executives in the system are the key to shielding the attacker from sniffing. The application of heterogeneous execution sets is well-accepted by researchers, but most of the discussion on the evaluation of the degree of heterogeneity of execution sets is conceptually.

Reference to the literature

[1]Schleimer S,Wilkerson D S,Aiken A.Winnowing:local algorithms for document fingerprinting[C]//ACM SIGMOD International Conference on Management of Data.ACM,2003:76-85.

[2]Gallon L.On the Impact of Environmental Metrics on CVSS Scores[C]//IEEE Second International Conference on Social Computing.IEEE,2010:987-992.

Disclosure of Invention

The invention aims to provide a heterogeneous redundancy system optimization method based on a genetic algorithm aiming at the defects of the traditional method for constructing a web heterogeneous redundancy system.

The technical scheme adopted by the invention for solving the technical problem comprises the following steps:

the invention relates to similarity calculation and construction of a fitness function, wherein the similarity is used for evaluating the heterogeneous degree, and the fitness function is used for heuristically screening out a high-quality Web heterogeneous executive body, and the method specifically comprises the following steps:

step 1, converting a web heterogeneous redundancy model into a vector;

step 2, providing similarity definition about heterogeneous redundancy and calculating;

step 3, constructing a fitness function;

and 4, screening the genetic algorithm according to the fitness calculated by the fitness function.

Converting the web heterogeneous redundancy model into a vector in the step 1 specifically as follows:

wherein, alpha represents a Web heterogeneous executive, m represents the number of Web heterogeneous executors, and n represents the number of layers of a technology stack.

The similarity calculation related to the heterogeneous redundancy proposed in the step 2 is specifically as follows:

the similarity is calculated according to a hierarchy, so that each technology stack of each layer has a value of SR, and the SR of the k layer is defined as SR_k，SR_kThe expression of (a) is as follows:

wherein S is_kIs a one-dimensional vector, vector S, of the k-th layer_kThe ith element ofThe value of (c): and taking the ith executive body as a reference template, comparing the ith executive body with the similarity of the rest m-1 executive bodies on the kth layer technology stack, and accumulating the values obtained by Sim operation, wherein i is more than or equal to 1 and less than or equal to m, and k is more than or equal to 1 and less than or equal to n.

Wherein Moss is a code duplication checking system of the American Stanford university sourcing, and returns a value pair (X, Y) indicating that X% of the codes in a match Y% of the codes in b. The minimum value is taken as the source code similarity. The parameter "threshold" in the function Sim can be organized by the related parameters in CVSS v2 to obtain the following formula:

threshold＝1-η_k

BS＝round_to_1_decimal(((0.6*IMP)+(0.4*EXP)-1.5)*f(IMP))

EXP＝20*(AV)*(AC)*(Au)

IMP＝-10.41*(1-(1-C)(1-I)(1-A))

where the access vector AV depends on the amount of access needed by the attacker to exploit the vulnerability. Thus, the attacks that require physical access to the system are lower than those that any machine can attack through the internet.

Access Complexity (AC) represents the complexity of exploiting an attack. A buffer overflow attack on an Internet service is much more complex than a vulnerability of an email client, in which a user performs an attachment download and then performs an attachment download, so the AC value is low.

The authentication (Au) level required to perform the attack. For example, if an account does not need to be registered to utilize the system, the value is high. In contrast, if multiple accounts are needed to exploit this vulnerability, the value is low.

The privacy impact (C) score is low if only some (irrelevant) information is leaked. If the vulnerability is successfully exploited, the entire database is most affected.

Integrity impact (I) refers to the ability of an attacker to modify the behavior of a file or system in the event of a successful execution of a vulnerability attack. An attacker can change the code or delete any file in the system, the higher this value.

Availability impact (a) represents the force to successfully utilize system availability. A successful denial of service (DoS) will have a large impact on the application server.

Constructing a fitness function, counting the probability of each technology stack encountering attack by using prior knowledge, and calculating the value of the fitness function by combining the calculated SR value, wherein the fitness function is defined as follows:

wherein p is_iThe method is characterized in that the number of times of attacks on the technology stack at the ith layer accounts for the total number of attacks on the system.

And 4, screening the genetic algorithm according to the fitness calculated by the fitness function, wherein the screening is as follows:

4-1. chromosome coding:

the m candidate executables are encoded as binary strings. When the ith base is 1, selecting the ith executive body, otherwise, when the ith base is 0, discarding the executive body;

4-2. parameters and operation of genetic algorithm:

the population size of the genetic algorithm is set to 50 and the selection operator of the genetic algorithm is based on the selection competition, with 10% of the optimal number remaining per generation. The crossover operator of the genetic algorithm is based on one point, and the mutation probability is 2%. Each generation must ensure that the total number of "1" s is odd and less than or equal to the maximum redundancy value after the crossover and mutation operations. To ensure this condition, the chromosomal gene is adjusted, the number of evolutions is set to 100, and the fitness function is given by the formula w (k).

4-3. method for regulating chromosomal genes:

the maximum number of "1" in the chromosome is limited to 7, that is, the maximum redundancy of DHR is 7, and the specific operations are as follows:

when the population is initialized, the number of "1" s in the chromosome is limited to 3,5 or 7.

If the chromosome number is not 3,5 or 7 after each chromosome generation after crossover and mutation, the number of "1" is adjusted by randomly mutating the gene in the chromosome;

if the number of the '1' is less than 3, randomly selecting the gene '0' in the chromosome to mutate until the number of the gene '1' reaches 3;

if the number of the '1' is more than 7, randomly selecting the gene '1' in the chromosome to mutate until the number of the gene '1' reaches 7;

IV if the number of "1" s is 4 or 6, the chromosome is first adjusted by random methods to determine "1" s as 3,5 or 7, and then using the I, II and III variant chromosome methods described above.

When we build a defense system, we often need to use a priori knowledge. We need to figure out which attacks are the most common and which attacks are adapted to our scenario. As the a priori knowledge changes, the defense system also carries various patches. For the problem of security protection, the priori knowledge is worth referencing. Although we cannot rely entirely on prior knowledge to defend against unknown vulnerability attacks, it can objectively respond to the widespread distribution of vulnerabilities. The security department of each company will also record historical attacks in the file.

The original execution set is C₁,C₂...C_mNow we need to filter out unreliable executives from the collection to form a new system. The reliability of the different combinations is calculated by a fitness function w (K) using a conventional traversal, according to the value of a given redundancy number K. This is effective when the value of m is small. Once m is very large, e.g., m ≧The time complexity of the traversal method will become very difficult to compute results 20. Therefore, we use genetic algorithms to solve the problem of merit. The main idea is to encode the redundant system into a binary string and then evolve the string set by genetic operations such as selection, crossover and mutation to obtain the best or similar optimal heterogeneous redundant system.

The invention optimizes the web heterogeneous system, and has the following beneficial effects:

(1) an algorithm model for optimizing a Web heterogeneous system is provided. And analyzing and evaluating the similarity of each layer, and selecting, improving and designing an execution set according to the evaluation result.

(2) Heterogeneous optimization of a web heterogeneous system belongs to a combinatorial optimization problem, and the time complexity of the combinatorial optimization problem is O (n ^ n). The genetic algorithm is introduced, so that the situation that iterative operation is trapped in a local extremely small trap is avoided.

The method reasonably utilizes the existing source code detection scheme, introduces a subjective judgment mechanism aiming at the undetectable scene, and calculates the code similarity. And combining the calculated similarity value with the prior knowledge of the unit safety part to calculate the similarity. And providing a fitness function required by the genetic algorithm according to the similarity. And finally substituting the system to be optimized into the genetic algorithm under the fitness function for optimization. The web heterogeneous system optimized by the method has better defense capability.

Drawings

FIG. 1 is a Web heterogeneous system architecture according to the present invention.

FIG. 2 is a comparison diagram of the defense of the randomly constructed Web system and the Web system constructed by the genetic algorithm.

Detailed Description

The invention is further illustrated by the following figures and examples.

As shown in fig. 1 and 2, a heterogeneous redundancy system optimization method based on a genetic algorithm includes the following steps:

the method comprises similarity calculation and fitness function construction, wherein the similarity is used for evaluating the heterogeneous degree, and the fitness function is used for heuristically screening out a high-quality Web heterogeneous executive body, and specifically comprises the following steps:

step 1, converting a web heterogeneous redundancy model into a vector;

step 3, constructing a fitness function;

wherein S is_kIs a one-dimensional vector, vector S, of the k-th layer_kValue of the ith element above: and taking the ith executive body as a reference template, comparing the ith executive body with the similarity of the rest m-1 executive bodies on the kth layer technology stack, and accumulating the values obtained by Sim operation, wherein i is more than or equal to 1 and less than or equal to m, and k is more than or equal to 1 and less than or equal to n.

threshold＝1-η_k

BS＝round_to_1_decimal(((0.6*IMP)+(0.4*EXP)-1.5)*f(IMP))

EXP＝20*(AV)*(AC)*(Au)

IMP＝-10.41*(1-(1-C)(1-I)(1-A))

4-1. chromosome coding:

4-2. parameters and operation of genetic algorithm:

4-3. method for regulating chromosomal genes:

The original execution set is C₁,C₂...C_mNow we need to filter out unreliable executives from the collection to form a new system. The reliability of the different combinations is calculated by a fitness function w (K) using a conventional traversal, according to the value of a given redundancy number K. This is effective when the value of m is small. Once the value of m is large, e.g., m ≧ 20, the temporal complexity of the traversal method becomes very difficult to compute the result. Therefore, we use genetic algorithms to solve the problem of merit. The main idea is to encode the redundant system into a binary string and then evolve the string set by genetic operations such as selection, crossover and mutation to obtain the best or similar optimal heterogeneous redundant system.

The pseudo code is as follows:

as can be seen from the above genetic manipulation, the number of times the genetic algorithm needs to be evaluated by the function a is about 5000 times, regardless of the size of n. If we use the traversal method we need to compute redundancies 3,5 and 7 when n is 20, the number of evaluations is about 95,000, and as n increases, the number of times the traversal needs to be evaluated increases exponentially, which is difficult to compute.

Through the steps, a high-quality web heterogeneous redundancy system can be obtained.

Claims

1. a method for optimizing Web heterogeneous system in conjunction with genetic algorithm, it is characterized in that comprising the construction of similarity calculation and fitness function, wherein similarity is used for evaluating the degree of heterogeneity, and fitness function is used for heuristic screening out. A high-quality Web heterogeneous execution body specifically includes the following steps:

Step 1. Convert the web heterogeneous redundancy model into a vector;

Step 2. Propose and calculate the similarity definition about heterogeneous redundancy;

Step 3. Build a fitness function;

Step 4. Screen the genetic algorithm according to the size of the fitness calculated by the fitness function;

The conversion of the web heterogeneous redundancy model into a vector described in step 1 is as follows:

Among them, α represents the heterogeneous execution of the Web, m represents the number of heterogeneous executions of the Web, and n represents the number of layers of the technology stack;

The proposed similarity calculation for heterogeneous redundancy described in step 2 is as follows:

The similarity is calculated according to the level, so the technology stack of each layer has a value of the similarity SR of the corresponding level. The SR of the kth layer is defined as SR _k , and the expression formula of SR _k is as follows:

Among them, _Sk is a one-dimensional vector of the kth layer, and the value of the i-th element on the vector _Sk is: taking the i-th executive body as a reference template, and the remaining m-1 executive bodies are related to the technology in the k-th layer. Compare the similarity on the stack, and accumulate the values obtained after the Sim operation, 1≤i≤m, 1≤k≤n;

Among them, Moss is a code checking system open sourced by Stanford University in the United States. The returned value pair (X, Y) means that X% of the code in a code matches Y% of the code in b; taking the minimum value as the source code is similar degree; the parameter "threshold" in the function Sim uses the relevant parameters in CVSS v2 to organize the operation to obtain the following formula:

threshold=1- _ηk

BS=round_to_1_decimal(((0.6*IMP)+(0.4*EXP)-1.5)*f(IMP))

EXP=20*(AV)*(AC)*(Au)

IMP=-10.41*(1-(1-C)(1-I)(1-A))

Among them, AV is the access vector, which depends on the amount of access the attacker needs to exploit the vulnerability; AC is the access complexity, which represents the complexity of the exploit; Au is the authentication level required to execute the attack; C is the confidentiality impact; I is the integrity impact; A is the availability impact;

In the construction of the fitness function described in step 3, prior knowledge is used to count the probability of each technology stack encountering an attack, combined with the calculated SR value, and then the value of the fitness function is calculated. The fitness function is defined as follows:

Among them, pi refers to the ratio of the number of attacks on the _i -th element in the k-th layer technology stack to the total number of attacks on the system;

In step 4, the genetic algorithm is screened according to the size of the fitness calculated by the fitness function, and the details are as follows:

4-1. Chromosome coding:

m candidate executives are encoded as binary strings; when the i-th gene is 1, the i-th executive body is selected, otherwise, when the i-th gene is 0, the executive body is discarded;

4-2. Parameters and operations of genetic algorithm:

The population size of the genetic algorithm is set to 50, the selection operator of the genetic algorithm is based on the selection competition, and each generation retains 10% of the optimal number; based on single-point crossover, the mutation probability is 2%; each generation must ensure the total number of "1" is an odd number, and is less than or equal to the maximum redundancy value after crossover and mutation operations; in order to ensure this condition, the chromosome genes are adjusted, the number of evolution is set to 100, and the fitness function is given by the formula w(k);

4-3. Methods of adjusting chromosome genes:

The maximum number of "1" in chromosomes is limited to 7, that is, the maximum redundancy of the genetic algorithm is 7. The specific operations are as follows:

When initializing the population, limit the number of '1's in chromosomes to 3, 5 or 7;

Ⅰ. If the number of chromosomes is not 3, 5 or 7 after each generation of chromosomes after crossover and mutation, adjust the number of "1" by randomly mutating the genes in the chromosome;

Ⅱ. If the number of "1" is less than 3, randomly select the gene "0" in the chromosome to mutate until the number of gene "1" reaches 3;

Ⅲ. If the number of "1" is greater than 7, randomly select the gene "1" in the chromosome to mutate until the number of gene "1" reaches 7;

IV If the number of "1" is 4 or 6, first determine "1" as 3, 5 or 7 by random method, and then use the above I, II and III variant chromosome method to adjust the chromosome.