Isao Takaesu, Professional Service Div.
The genetic algorithm simulates biological evolution in which organisms adapt to their environment by repeating mutation, crossover and selection for many generations. It is commonly used to find optimal solutions and applied to various problems, such as the low-air-resistance “Aero Double Wing” design of bullet trains, and the generation of high coverage fuzz in American Fuzzy Lop.
In this blog, we expand the genetic algorithm to the field of security assessment. We have verified the automatic generation of injection codes for web app vulnerabilities, so we will introduce the procedure and result of the verification. There are many different types of web app vulnerabilities, but we have targeted reflected XSS in this verification.
|Notes:||The source codes used in this verification are listed in the "Verification codes" page. If you are interested, please use them in an environment under your control and at your own risk.|
Before explaining the verification procedure, we will explain the flow of evolutionary computing for the genetic algorithm.
Figure 1 shows the flow of evolutionary computing. It consists of five major steps.
Generate a population composed of multiple individuals.
Each individual is composed of multiple genes.
Step.2. Fitness / Evaluation
Evaluate the fitness of each individual to the environment.
Give high scores to superior individuals based on the evaluation result.
Select individuals with a high score from the population.
Individuals with a low score are culled.
Swap part of the genes of the selected individuals and generate new individuals.
The new individuals (offspring) comprise the next population (next generation).
Select some individuals stochastically from the new population and randomly swap some of the genes.
Mutations may generate individuals that are more adapted to the environment.
After completing all the steps, repeat Step 2 to Step 5 for the next population. This cycle is repeated until the termination condition is met. Generally, conditions such as "when the number of generations reaches the upper limit" or "when the score average of all individuals exceeds the threshold" are set as the termination condition.
By repeating this evolutionary computing for many generations, only the "individuals with an excellent combination of genes" that are adapted to the environment will survive.
By the way, what "adapted to the environment" means would change depending on the type of the task. In the abovementioned bullet train example, the fitness to the environment is judged by evaluating "how small the air resistance becomes". In the fuzzer example, it is by evaluating "how high the coverage becomes". Therefore, in order to carry over the genes of excellent individuals to the next generations, it is very important to design an "evaluation function" that evaluates the adaptability to the environment.
|Notes:||There are many methods of combination optimization, such as linear search, random search and dynamic programming. In this verification, we adopted the genetic algorithm, which is easy to implement and fast at computing, and has a variety of generation patterns.|
As mentioned in the beginning, this time our task is to generate injection codes for XSS. So, we will target the following two goals.
In other words, we repeatedly execute evolutionary computing to seek individuals that achieve the two goals above.
Below, we define the keywords of the genetic algorithm for this task.
Individuals are composed of multiple genes. So, we need to collect genes before executing evolutionary computing. In this verification, we collected genes using the following procedure.
|Notes:||Because we can’t publish the actual injection codes, we collected the genes from the injection codes used for the XSS tests in WAVSEP for this verification.|
If we only use genes from known injection codes, it is expected that the genetic algorithm would not generate brand new injection codes. So, in this verification, we referred to MDN web docs and added genes such as HTML tags, attributes and event handler that were not used for the XSS cases in WAVSEP. As a result, we defined about 220 types of genes.
|Notes:||The gene list used in this verification is "here".|
Let's look at the procedure of verification.
We randomly select genes from the gene list and generate individuals.
In this verification, we designed 5 genes per individual and 100 individuals per generation.
If we treat the genes as character strings here, it makes the evolutionary computing difficult. So, we encoded each gene with a unique number. Figure 3 is an example that each individual (strings enclosed in "") in the initial population is expressed in the codes.
[85, 158, 96, 32, 85] , [179, 62, 33, 130, 133] [98, 82, 25, 41, 198] , [55, 9, 94, 194, 55] ・・・ [76, 6, 114, 149, 70] , [107, 140, 172, 150, 38] [102, 169, 76, 90, 208], [21, 168, 111, 15, 159]
If the individuals above are expressed in strings, they appear as the following.
[85, 158, 96, 32, 85] ⇒ </blockquote>content= <basefont/<form </blockquote> [179, 62, 33, 130, 133] ⇒ <iframe/language= <keygen/</img>coords= ・・・
Since the initial population is composed of genes randomly selected from the gene list, these individuals are meaningless strings. Of course, the HTML syntax is incorrect, and they can't even run scripts.
We evaluate each individual in the population on the degree of its usefulness to detect XSS vulnerabilities.
In this verification, we designed the evaluation function as a combination of the following three evaluation criteria.
Select individuals with a high score based on the fitness evaluation, and cull individuals with a low score. Listed below are some of the selected individuals and culled individuals.
<iframe/language= <keygen/</img>coords= <hr ><video>onmouseover=confirm();><a onerror=¥u0061lert();<body/list=<iframe/<progress <body><img/<source/onerror=prompt();>
src=/ <a/</col><td </area> onerror=alert();><body onerror=al¥u0065rt();<output <hr <thead </td>rowspan=accept= </applet><isindex/alert();<progress/script:alert();
It appears a little confusing, but individuals in Figure 5 have more correct HTML syntax than individuals in Figure 6. Therefore, the scores of the individuals in Figure 5 are higher than in Figure 6.
Swap part of the genes of the selected individuals and generate new individuals.
[current-generation individuals] <img src=/ <a/</col><td> onerror=alert();><body onerror=al¥u0065rt();> ・・・ ----------------------------------------------------------------- [next-generation individuals (offspring)] <img src=/ <a/onerror=alert();> </col><td><body onerror=al¥u0065rt();> ・・・
Select a certain portion of individuals stochastically from the next-generation individuals and randomly swap some of the genes. As a result, new individuals that are executable as scripts or individuals with an increased executability are stochastically generated.
[Before mutation] <img src=/ <a/onerror=alert();> </col><td><body onerror=al¥u0065rt();> <hr ><video>onmouseover=confirm();><a ・・・ ----------------------------------------------------------------- [After mutation] <img src=x <a/onerror=alert();> </col><td><body onload=al¥u0065rt();> <hr ><video>onerror=confirm();><a ・・・
Mutation can also prevent the population from falling into local solutions (bad injection codes).
Repeat the computation above to find out if new individuals that fulfill the goals of the task will be generated.
The conditions of the verification is the following.
|Genes||About 220 types|
|Number of Individuals
(in each generation)
－Each individual is composed of 5 genes.
|Evaluation of Fitness||Verification of HTML syntax：tidy 5.4.0
－Numbers of warnings and errors are counted.
|Script executability：selenium 3.4.3
－Chrome web driver is used.
|Bypassing WAF：ModSecurity CRS 2.2.9
－We moderated the core rule by excluding the rules for the event handler "onerror".
|Selection||Selection of elites
－Preferential selection of individuals with a high score.
－For two individuals, two points are selected on the genes of each individual, and the genes between the two points are exchanged between the individuals to create two new individuals.
－Target mutation rate is 30% for a generation.
|Termination||When one of the following conditions is achieved:
・The number of generations exceeds 10,000.
・The average score of all individuals per generation exceeds 3.0 points.
|Notes:||Because ModSecurity's core rule set is strict, we moderated it for this verification by excluding the rules for the event handler "onerror".|
|Notes:||We adopted the methods of selection and crossover and the rate of mutation based on the empirical rule, so that the time required for the mutation to converge is shorter and more patterns of injection codes are generated.|
Shown next are the verification results of "to generate brand new injection codes" and "to generate injection codes that bypass WAF ".
Table 2 shows some examples of injection codes generated by the genetic algorithm.
Column “New” indicates whether the injection code was newly generated or a known injection code. “Yes” is for a new injection code and “No” is for a known injection code.
As we see in the results above, some of the injection codes were those that had been used in WAVSEP, but we found that many new injection codes were generated.
Before the verification, we expected that complex injection codes (combinations of complex symbols and strings) would be generated, but many injection codes were rather normal in their complexity. This is probably due to the content and level of granularity of the gene list used this verification. Therefore, by adjusting the gene list, it may be possible to generate complex injection codes.
Table 3 shows whether the injection codes generated by the genetic algorithm can bypass WAF.
Column “WAF” indicates whether the injection code was blocked or allowed by ModSecurity. “Blocked” indicates that the injection code was not able to bypass WAF, and “allowed” indicates that the injection code was able to bypass.
|1||- (can’t run scripts)||-|
|100||- (can’t run scripts)||-|
In the result above, we can see that the early generations (1st to 348th generations) can't generate individuals that are executable scripts. The first executable individuals are generated in the 349th generation, but we can see that the individuals from this generation can't bypass WAF. By continuing the evolution, we can see that the first WAF-bypassing individuals (*) are generated in the 6307th generation. The time spent on this evolution was about five hours.
* The core rule set of ModSecurity was set permissive for this verification.
We may be able to shorten the five hours spent on the evolutionary computing by redesigning the evaluation function or adjusting parameters of the selection, crossover, and mutation.
Our conclusions for this verification are:
Listed above are our research objectives for the future.
In conclusion, I have known the word "genetic algorithm", but I had never really thought about the details of the logic and the usage. In this verification, we have learned that the genetic algorithm is actually used to solve many problems, and we could see that it might be possible to use it in our domain.
There could be problems you can solve with the combinational optimization of the genetic algorithm around you. If you are interested, it might be worthwhile to spend some time exploring it.
To read other blog entries by Isao Takaesu, click here.