An Approach For Linux Kernel Fuzzing Driven By System Call Dependency Graph

The kernel is the most basic and core part of modern operating systems.Its stability and security are critical to the entire computer system.As a widely used operating system kernel,the Linux kernel has a huge code base and complex functional logic,which makes it prone to errors in design and implementation,leading to defects.At the same time,it runs at the highest privilege level,and once the kernel defect is exploited by an attacker,it will cause serious consequences.Static analysis and fuzzing are currently popular techniques of kernel defect detection.For the Linux kernel fuzzing,the sequence of system calls is generally used as the test input,and its execution speed is fast and there is no false positive.The common kernel usually provides many system calls whose core logic is executed or not and whose execution path are all related to the specific kernel state.If the system calls are randomly combined,the test input space will explode and the quality of test cases will be low,which will affect the efficiency of kernel fuzzing.The existing method of kernel fuzzing believes that there are dependencies between two system calls,but these dependencies have not been analyzed sufficiently and have not been used to generate and mutate system call sequence,so as to get the better fuzzing input.Static analysis can obtain global program information from the code,and can be used to analyze the dependency information existing between system calls.Therefore,this paper proposes an approach for Linux kernel fuzzing driven by system call dependency graph.It takes the kernel resource as the concrete manifestation of the kernel state,and uses static analysis to analyze the system call dependency by detecting the kernel resources of system calls,constructs a system call dependency graph.Then use the dependency graph to guide the kernel fuzzing to generate and mutate more efficient test cases,and use execution information as feedback to optimize the the dependency graph,thereby improving the efficiency of kernel fuzzing.The main work of this paper is as follows:1)A method based on static analysis to construct a system call dependency graph is proposed.This method firstly defines a weighted directed graph to describe the dependency relationship between system calls,where the nodes are system calls,and the directed edges and weights indicate the order and degree of dependency between the pair of system calls.Then,it defines the kernel resource as various structure types and global variables in the kernel source code.Through lightweight static analysis,we can detect the complete and abundant kernel resource usage of each system call,and analyze the potential dependency relationship between two system calls.Then we assign weight to the corresponding edges on the dependency graph according to the kernel resource usage,so as to construct the dependency graph of system call.2)An approach for Linux kernel fuzzing driven by system call dependency graph is proposed.On the one hand,the system call dependency graph is applied to the kernel fuzzing and guides the fuzzing to generate and mutate test cases,so it can produce a valid system call sequence as much as possible,reduce invalid input,and improve the quality of test cases.On the other hand,the execution information during the kernel fuzzing is integrated into the dependency graph to optimize the weight deviation when constructing the dependency graph by static analysis,so that the dependency graph can guide the fuzzing more efficiently and continuously.3)Based on the above method,a prototype tool,called SDKernel Fuzzing,for Linux kernel fuzzing driven by system call dependency graph is implemented.We select 4 different versions of Linux kernels as experimental target,and evaluate the efficiency of constructing the system call dependency graph and the effectiveness of improving the efficiency of the kernel fuzzing by experiments.The result shows that SDKernel Fuzzing can efficiently analyze more comprehensive dependency information in four different versions of the kernel.Compared with the existing Linux kernel fuzzing tool,Syzkaller,the system call dependency graph can effectively improve the efficiency of kernel fuzzing.The code coverage has increased by 16.06% on average,and the number of bugs found has increased by 17.84% on average.