The development of modern computer technology leads to the emergence of new high-quality information services and their implementation in all spheres of human activity [1][2][3][4][5]. The development of the IT-industry has led to the construction of global computer networks, extensive data warehouses, automated control systems, including critical infrastructures, Smart Grid and much more [6][7][8].
In the age of the Internet and global implementation of information technologies, information security is more important for critical infrastructures [9,10]. Complex solution for problems related to informational security is connected with solving different objectives in cryptography [11][12][13][14], computations optimization, technical and physical security as well as many others [10,[15][16][17].
This paper focuses on the problem of automated software vulnerability scanning [18][19][20][21][22]. As practice shows, computer programs are the most exposed fragment of During experimental research of automated vulnerability search effectiveness MiniFuzz was used. Fuzzing process was conducted for several common desktop applications, including Google Chrome; Notepad++; Winamp; Microsoft Paint.
For Google Chrome testing several dozens of different html-files were selected. Aggressiveness (how much of input data is mutated) was alternately set to 5%, 15%, 25%, 35%. Testing results for this case are shown in Table 1. As can be seen from the table, fuzzing testing can help in discovering "File Not Found" type errors. Apparently, higher aggressiveness leads to more errors of this type.
Table 1. Expected value of "File Not Found" error and confidence interval (for significance level α = 0,01 sample size N = 1000)
Aggressiveness Level Error 5% 15% 25% 35% "File Not Found" 0,239±8,2310 -4 0,269±2,610 -4 0,295±3,4910 -4 0,320±8,2810 -4 After several hours of fuzzing for Notepad++ no errors occurred even with 100% aggressiveness. This shows high level of stability and security of this application. Testing of Winamp led to similar results.
To test Microsoft Paint images of different formats and sizes were selected. Testing results are shown in Table 2. As it can be seen from the results, selective testing with fuzzing revealed errors "File Not Found" and "Wrong Format". Frequency of these are almost similar and increase with higher aggressiveness. 0,13±2,610 -4 0,15±2,5810 -4 0,18±2,6410 -4 0,22±1,5810 -4 "Wrong Format" 0,09±2,9610 -4 0,16±3,7710 -4 0,2±3,5810 -4 0,23±4,5710 -4 Conducted tests show that the majority of common applications are secured and cannot be crashed using primitive fuzzing. In the case of Google Chrome, for example, it is not a surprise, because software engineers and testing professionals at Google use much more complex fuzzing during the development cycle of their products [28]. The same goes for Microsoft.
Thus, the analysis of different fuzzers in the area of automated testing shows that this approach to software vulnerability search can vary depending on the goal, tester's skills, data format and other factors. Some applications have privilege separation system, which depends on user level. Using fuzzer as a tool for automated vulnerability search, it is possible to find errors in software products, which let attacker gain full or partial control over the system. Some low-lever errors are very similar to each other so it is possible to use the same logic to find vulnerabilities in more applications.
Relying on conducted experimental research for selective testing it can be said that fuzzing is quite promising method of automated vulnerabilities search. We were able to find errors even in reliable and tested applications, like Google Chrome and Microsoft Paint, as we managed to discover random input data, which would cause errors. However, these are not critical for application functioning and/or operating system, their handling is correct that, apparently, is stipulated behavior for such kind of corrupted input data.
It is worth mentioning that fuzzing has some limitations when it comes to practical use and have not gained wide popularity for automated vulnerability testing yet. However, considering the fact big companies, such as Google and Microsoft are using fuzzing as a part of their methodology and vigorously work on its development, it can be safely said that fuzzing has quite strong potential [29][30][31][32].
The most promising direction of future development of automated vulnerability search methods is fuzzing intellectualization [18][19][20][21][22]. This is about using deep learning methods to improve computational procedures for automated vulnerability search. It is believed that such approach can significantly improve the process of selecting input data, which will cause failure or errors in the target application.
Fuzzing is a method of software and security vulnerabilities testing which is conducted by making multiple tests using mutated input data [21]. Repeated testing is performed with random mutation, and usually testing time is far from optimal. This article considers the problem of intellectual fuzzing and tries to find a solution [22].
The main goal is to develop a technology that can be guided and will make decisions based on the experience it gained during testing. The solution to this question lies in machine learning and reinforcement learning based on the deep Q-learning algorithm [33]. It uses maximum possible rewards, which are defined during development process by analyzing program source data and available rewards. This allows to apply optimal input data mutations. Thus, agent gets an opportunity to learn to formulate an optimal action policy for obtaining maximum reward. In this paper, we propose an algorithm and a computer model of the in-depth training as well as research of automated vulnerabilities testing effectiveness in comparison with the random mutation test. During testing, the "black box" method is used. It means that the available information represents only results of the program's work and the input data that it needs to perform [21].
During research, we realized there is a serious problem with randomized fuzzing: if it works with randomly generated input data, the time will not be optimal, since the process is performed blindfold. There may be a lot of testing rounds resulting in huge amounts of mutations that do not provide any progress. The process of fuzzing is an execution of a task cycle in certain defined program, where input is a sequence that was changed by some mutation. The ideal solution to solve such problem is machine-learning technology called reinforcement learning. The best example of using this algorithm is the AlphaGO developed by Google DeepMind in 2015. It becomes the world's first program to win the game of "Go" with a top-ranked professional Lee Sedol [34].
As a combination of fuzzing and reinforcement training, a system capable of changing the rules for selecting specific mutation was created. It sends mutated data to input and, depending on the program's source data, generates a reward in order to rely on its own experience and select optimal mutations for particular case upon further testing. Thus, the amount of mutations does not contribute to the testing process significantly reduces. This makes testing process faster. Schematic diagram of the developed system is shown in Fig. 1. Testing process begins by defining the original non-mutated input data. Its format depends on fuzzing kind. Packages are submitted to the program's input channel and the response of the program is determined using special debugging software. From obtained data (this may be the program execution time, code coverage, code completion, etc.) system's State is formed. It will be preprocessed and presented to the Deep Q-learning model's input. The system then decides what Action should be taken next.
At the same time, depending on the selected action and the obtained program state, system forms the Reward for the algorithm. Using this reward, algorithm understands assigned task and determines optimal behavior for its implementation. In addition, algorithm remembers which actions brought it to the maximum reward (finding a mistake or a program failure, etc.) and, in the following testing rounds, decides what action should be taken based on its already gained experience. To calculate the next step, the previous inputs are mutated according to the action that was selected. Program input receives new mutated data. This procedure is repeated until the algorithm reaches its goal. Developed model uses Markov decision-making process -deep Qlearning [35].
This section provides necessary data about the algorithm of reinforcement training. Reinforcement learning is a computational approach to understanding and automating targeted learning and decision making. It stands out among other machine learning algorithms by the fact that agent learns directly by interacting with the environment without referring to examples [35]. This algorithm is primarily aimed to solve problems that arise during interaction with the environment to achieve long-term action. It uses formal structure of Markov decision-making process [35], defining the interaction between agent and environment in terms of states, actions and rewards. These features include understanding of causes and effects, as well as presence of clear goals. The notion of value and function of value is the main features of reinforcement training methods.
As noted earlier, the interaction between agent and environment can be described using Markov decision-making process ( , , ) M S A P
, where S -a set of system's states, A -action's set, P -transition probabilities set. For each state-action pair ( , ) s a S A , P is a set of probabilities ( ' , ) P s s a , where s′ corresponds to the next system's state. Agent considers possible system states for the selected action, where each transition has its own reward ( , ) r s a , and studies the optimal behavior for maximizing the reward.
During the learning process, the main goal is to maximize the finite amount of rewards:
, where (0,1)
-discount rate, which determines the remuneration priority over time.
Action t a at state t s is determined by the policy of action ( ) t t a s . Policy attaches considered possible states to action, which in turn determines agent's behavior.
Expected cumulative reward for the policy-maker is defined as:
The problem of finding the optimal value ( , ) Q s a can be reduced to the procedure of function approximation. To achieve this ( , ) Q s a needs to be updated after each iteration of receiving the award [36]. It is defined as
To conduct an experiment simple fuzzer was used. Its main function is to implement input data selection for automated software vulnerability search. Software launch process was simulated and special logic tests were developed. The program could return an error code when certain data is received to compare fuzzing with and without artificial intelligence. Possible states of the system are presented in the form of data generated after the completion of the program. This data is transmitted by neural network, which consists of one input layer, two hidden layers with 50 neurons each and activation functions (Rectified Linear Unit): ( ) max(0, ) f x x . The output of the neural network has 45 elements, representing the number of possible mutations. Complete scheme of neural network for function approximation ( , )
Q s a is shown in Fig. 2. the gradient is denoted -the vector of partial derivatives t f relatively to θ, which is estimated by time t.
The algorithm updates exponential moving average values of the gradient ( t m ) and the square of the gradient ( t v ), where hyper parameters
control the exponential velocity of decomposition for these moving averages. The most moving averages are the estimations of the first moment (mean value) and the second moment (uncentered dispersion) of the gradient. However, these moving averages are initialized as zero vectors, which lead to the estimation of moments moving in zero direction, especially in the initial time steps and when expansion rates are small (for example, the value s close to 1). The good news is this bias initialization can be easily prevented by getting bug fixes bt m and bt v . The algorithm itself has the following form: Required input data:
: Exponential decay rates for moment estimates (standard settings
(Take the gradient relative to the stochastic function dur- Input mutations were selected based on the standard list: increasing and decreasing line length, integer insertion, adding special characters (for example, "%s", which may also cause errors). In sum, 45 functions were created and placed in a dictionary for further use.
The system receives an award if execution time was greater than the previous or if there were errors occurred during testing. When an error occurs, the algorithm finishes its work. While forming this type of award, there was a problem when algorithm already found one error and started calling it repeatedly to get maximum reward. To avoid this problem, two constants must be set: (
-discount rate and (0,1)
-intelligence speed. The first constant was already being mentioned before. The second one determines how the algorithm is capable in terms of discovering new solutions. Random action will be chosen with probability ε, and the most profitable action will be selected with probability 1 -ε. The hypothesis is a scientific assumption that made to explain any phenomenon and requires testing on theoretical basis in order to become a reliable scientific theory [37]. Statistical hypothesis is any assertion (assumption) concerning the type or distribution parameters of a certain feature of the objects being studied [37].
The following sequence of actions was necessary to test the hypotheses:
1. Make calculations of certain statistics, the distribution of which is known.
2. Find the P-value for the calculated results.
3. Make appropriate conclusions depending on the significance criterion and P-value.
A special test for identifying an error was developed. The hypothesis of the experiment is Q-learning fuzzing works faster than randomized one. The discount rate is set at 0.9, and the exploration speed is equal to 0.5. The latter parameter decreases 0.99 times after each era. The Student's t-test was used [38] to test the hypothesis.
Student's t-test -the general name for the class of methods for statistical criteria testing. It is based on comparison with the Student's distribution. The most common application of the criteria is related to checking the equality of mean values in two samples [38]. To use this criterion, some conditions must be met: the initial data must have normal distribution and dispersion must be equal.
The first group contains the results of testing using developed algorithm, while the second one presents the results of random mutations. Testing was performed in the following sequence: generate 15 experiments, and record the amount of mutations necessary to find an error at the end of each. The results of the experiments are shown in Table 3 The result is statistically significant for a given criterion, if the probability of accidental occurrence of the same or extreme result is less than the given level (0.01) under the condition of loyalty of the null hypothesis. The testing time of developed algorithm is better than the time of random mutations testing considering the fact the algorithm did not learn before. On average, developed algorithm finds an error after 2076 mutations, whereas random testing needs 2832 mutations. Represented algorithm finds error 30% faster.
This result proves the direction of research was chosen right. Particularly, it shows that the main problem of fuzzing (large amount of mutations) can be solved using artificial intelligence methods. Actually, if input data is changed directionally depending on previous results, it can speed up mutation process and receive results (which are finding the vulnerability in certain software product) after less amount of mutations.
Due to conducted research, one of promising automated software testing methods in critically important systems was analyzed. Fuzzing bases on multiple input of different (mutated) data to find parameters, which will cause failure or incorrect functioning of software. Repeated testing is usually carried using randomized mutations and the time of testing is very high in the most cases. This article researches the problem of intellectual fuzzing -the technology, which uses previous testing experience to make choices, related to mutation, and reduce testing time.
Deep Reinforcement Learning algorithm was used to implement intellectual fuzzing. With the use of simple fuzzing app, it becomes possible to prove that testing time decreases by 30%. This result was received because fuzzer used previous experience to adjust mutations.
This research may continue in other spheres. For example, Intrusion Detection and Prevention Systems [39][40][41][42] are also can be built using some elements of artificial intelligence. Critically important information systems in different spheres, including banking, industrial facilities management and Smart Grids are especially interesting for further research [43][44][45][46][47][48][49][50].