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.

Overview of Genetic Algorithm

 Before explaining the verification procedure, we will explain the flow of evolutionary computing for the genetic algorithm.

Figure 1 Flow of evolutionary computing

 Figure 1 shows the flow of evolutionary computing. It consists of five major steps.

 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.

Preprocessing

Set the task

 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.

Prepare genes

 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.

 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.

Figure 2 Conceptual diagram of the gene list

Verification procedure

 Let's look at the procedure of verification.

Initialization

 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.

Evaluation of fitness

 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.

Selection

 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.

Crossover

 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();>
・・・

Mutation

 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.

Verification result

Verification conditions

 The conditions of the verification is the following.

 Shown next are the verification results of "to generate brand new injection codes" and "to generate injection codes that bypass WAF ".

Verification result：Generation of new injection codes

 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.

Verification result：Bypassing WAF

 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.

 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.

Conclusion and Challenges for the Future

 Our conclusions for this verification are:

 The genes used in this verification were generated from the simple injection codes used for WAVSEP, and the genes’ granularity was rough. By creating genes from the injection codes used in actual vulnerability assessments or by creating genes of smaller granularity (1 character unit), we may be able to generate injection codes that are more complex and with richer patterns. Also, even though the web driver used for this verification was Chrome, we may be able to generate injection codes that are browser-dependent using other web drivers (IE, Firefox, Edge, etc.) with Chrome. Furthermore, we simply loaded the individuals to the browser and evaluated the script executability this time, but it could be possible to generate injection codes that test specific data contexts by injecting applicable parts of the individuals, such as attribute values, HTML comments, or JavaScript.

 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.

Verification codes

https://github.com/13o-bbr-bbq/machine_learning_security/tree/master/Generator

To read other blog entries by Isao Takaesu, click here.