# ERACE: Toward Facilitating Exploit Generation for Kernel Race Vulnerabilities
## 5 Implementation  
We implemented a prototype of ERACE, which contains three main components: the race-point detector, vulnerability analyzer, and checkpoint detector. The static analysis part of the race-point detector is based on SVF [20] and the dynamic path collection is based on kcov [17]. The race-point detector contains 2500 lines of C code and is mainly responsible for identifying the race points. The static analysis and instrumentation of the vulnerability analyzer contain 1500 lines of C code and are mainly responsible for identifying the timing relationships and triggering types. The static analysis of the checkpoint detector contains 2000 lines of C code and is mainly responsible for identifying the checkpoints. The following paragraphs contain some implementation details about the above design. **Kernel division. ** During static analysis, the kernel is divided and the correlative modules are merged. As the Linux kernel source code is too large, i.e., reaching millions in magnitude, the lines of the compiled LLVM intermediate representation with symbolic information are three to four times those of the source code, which severely reduces the speed of static analysis and increases memory overhead. To solve this problem, [PERSON] [10] and [PERSON] [21] divided the different modules according to the directory structures, and k-miner [22] analyzed them from different system calls. Although this effectively improved the speed of static analysis, some vulnerabilities were related to several modules. For example, the traces of the PoC we collected span multiple modules. If the kernel is divided into modules, it leads to false negatives. Therefore, when dividing the kernel, we integrate the modules involved in the PoC trace. **Relaved alias analysis. ** When the race-point detector identifies suspicious race instruction pairs, it should first perform alias analysis on the variables and structure pointers. There is a characteristic in the Linux kernel. Two unrelated functions may reference the same structure member. Unrelated means that there is no direct or indirect calling relationship. For example, in Figure 3, the packet_set_ring() and packet_setstockopt() functions can be called through different user call interfaces. However, as long as the same socket handle parameter is passed in, the same structure member po->tp_version will be referenced. When using the existing SVF tool [20] or the AliasAnalysis pass in LLVM itself to perform alias analysis, it is found that this situation will be under-reported. This is because traditional alias analysis can only identify alias relationships in the same function or the same path. Therefore, we improved the alias analysis method of the SVF and adopted relaxed alias  
Figure 7: Illustration of backward taint analysis starting from copy_to_user(), vm_insert_page(), and ptr. Arguments k_addr and ptr originate from the same structure. Interface refers to a system call or an export function from a module. analysis. As long as the structure type pointed to by two pointers is the same, we treat the two pointers as aliases. The relaxed alias analysis has the problem of false positives, but our goal is to locate more race-point candidates, avoiding omissions. In our research, the problem of false negatives is more serious than that of false positives, and even if there are false positives, we can filter them based on the PoC traces. **Single-thread generator algorithm. ** As mentioned above, the indeterminacy of the data race makes it hard to trigger the vulnerability. However, even if the multi-thread PoC does not trigger the race condition, it may have passed the race point. To gather the execution traces of two threads, we have to transform the multi-thread PoC into two single-thread programs. We designed a single-thread algorithm to finish the task. As we know, Linux uses two functions, pthread_create() and fork(), to make programs run concurrently. First, we have to recognize these two functions.