Automatic Generation of Injection Codes using Genetic Algorithm

2017.09.21
Isao Takaesu, Professional Service Div.

title1

 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.


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.


Step.1. Initialization

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.


Step.3. Selection

Select individuals with a high score from the population.
Individuals with a low score are culled.


Step.4. Crossover

Swap part of the genes of the selected individuals and generate new individuals.
The new individuals (offspring) comprise the next population (next generation).


Step.5. Mutation

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.


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.


  • Generation of brand new injection codes
    (Injection codes that have never been used in the past.)
  • Generation of injection codes that bypass WAF
    Injection codes that avoid detection by Web Application Firewall.

 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.


  • Genes
    Minimum components of HTML and JavaScript.
    ex) [<img/], [src=], [xxx], [onerror=], [alert();], [/>] etc.
  • Individuals
    XSS injection codes that are combinations of multiple genes.
    ex) [<img/][src=][xxx][onerror=][alert();][/>] etc.
  • Fitness
    Each individual’s degree of usefulness to detect XSS.
  • Evaluation
    To evaluate an individual’s degree of usefulness to help achieving the task using the “evaluation function”.
    Scores are given to individuals based on the evaluation.
  • Selection
    To select multiple individuals with a high score.
    Individuals with a low score are culled.
  • Crossover
    To swap part of the genes of selected individuals and generate new individuals (offspring).
    It generates the next population of individuals that are more likely to detect XSS.
  • Mutation
    To select some individuals stochastically from the newly generated population and randomly swap some of the genes.
    It can prevent populations from falling into local solutions (bad injection codes) and stochastically generate individuals that contribute more to achieve the goals.


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.


  1. Collect injection codes that were used in vulnerability assessments in the past.
  2. Decompose each injection code into minimum components of HTML and JavaScript.
  3. Define each minimum component as a gene.

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.



Figure 2 Conceptual diagram of the gene list

Notes: The gene list used in this verification is "here".


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]
Figure 3 Initial population is expressed in codes (example)

 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=
・・・
Figure 4 Individuals expressed in strings (example)

 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.


  • Correctness as HTML syntax
    Use an HTML checking tool to evaluate whether the individual has correct HTML syntax.
    Calculate the score based on the number of warnings and errors in the checked results.
  • Executability of scripts
    Observe the executability of the individual (script) on the browser. Keep in mind that there are scripts that are executed on mouse and keyboard events.
    Calculate the score based on whether the script can be executed or not.
  • Blocked or allowed by WAF
    Deploy a WAF in front of a dummy web app.
    Send HTTP requests containing the individual (script) to the dummy web app and observe if they are blocked or allowed by the WAF.
    Calculate the score based on whether the request was blocked or not.


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();>
Figure 5 Selected individuals (examples)

src=/ <a/</col><td </area>
onerror=alert();><body onerror=al¥u0065rt();<output
<hr <thead </td>rowspan=accept=
</applet><isindex/alert();<progress/script:alert();
Figure 6 Culled individuals (examples)

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


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
・・・
Figure 8 Mutation (example)

 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.


Genes About 220 types
Number of Individuals
(in each generation)
100
-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.
Crossover Two-point crossover
-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.
Mutation Mutation rate:0.3
-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.
Table 1 Verification conditions

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 ".



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.


No Injection Codes New
1 <body onmouseover=alert(); <script <label <canvas </basefont> Yes
2 <body onload=alert(); list=</a> No
3 <svg/onload=alert(); </del> No
4 <script>al¥u0065rt();</script> Yes
5 <object data=xss.html </label> Yes
6 <video><source/onerror=javascript:alert();> Yes
7 <video><source onerror=alert();> Yes
8 <video><source onerror=confirm(1);> Yes
9 <video><source/onerror=al¥u0065rt();> Yes
10 <iframe onload=alert();> Yes
- ・・・ -
Table 2 Automatic generation of injection codes (examples)

 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.


Gen Injection Codes WAF
1 - (can’t run scripts) -
100 - (can’t run scripts) -
349 <video><source/onerror=al¥u0065rt();> blocked
1641 <video><source/onerror=javascript:window.onerror=alert();> blocked
2743 <video><source onerror=javascript:al¥u0065rt();> blocked
4568 <video><source onerror=javascript:alert();> blocked
5047 <video><source onerror=al¥u0065rt();> blocked
6067 <video><source onerror=alert();> blocked
6192 <video><source onerror=prompt();> blocked
6307 <video><source onerror=confirm(1);> allowed
Table 3 Bypassing WAF (examples)

 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:


  1. We were able to generate XSS injection codes using the genetic algorithm.
  2. We may be able to generate injection codes for other vulnerabilities using the genetic algorithm (this still needs to be verified).
  3. Complexity of the injection codes depends on the content (types and granularity of the genes) of the gene list.
  4. It is possible to shorten the evolutionary computing time by redesigning the evaluation function and adjusting several parameters.

 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.



ページトップにページトップへ


執筆者一覧 (Authors)


space

執筆者一覧 (Authors)


space

所在地

本店:

〒103-0013
東京都中央区日本橋人形町
1丁目14番8号 郵船水天宮前ビル6階
地図はコチラMapはコチラ

TEL : 03-5649-1961(代表)


赤坂オフィス:

〒107-0052
東京都港区赤坂2丁目17番7号
赤坂溜池タワー9階
地図はコチラMapはコチラ

TEL : 03-6861-5172

三井物産セキュアディレクション株式会社

MBSDロゴ

サイトマップ

所在地

本店:

〒103-0013
東京都中央区日本橋人形町
1丁目14番8号 郵船水天宮前ビル6階
地図はコチラMapはコチラ

TEL : 03-5649-1961(代表)


赤坂オフィス:

〒107-0052
東京都港区赤坂2丁目17番7号
赤坂溜池タワー9階
地図はコチラMapはコチラ

TEL : 03-6861-5172