Understanding Concurrency Vulnerabilities in Linux Kernel

Following Lu et al. (Lu2008, ), we categorize concurrency bugs into two groups: deadlock and non-deadlock bugs. Non-deadlock bugs are further categorized into atomicity violations, order violations and others, depending on what the intended execution orders are. Same as in Lu et al. (Lu2008, ), we do not focus on data-races in our study because data-races alone may or may not indicate that the corresponding code has a bug; furthermore, in the CVE database, we find that data-races alone are rarely associated with any security attacks, although they may appear together with atomicity or order violations. In the remainder of this subsection, we illustrate individual bugs using examples.

Since not all concurrency bugs are vulnerabilities, here, we use an exploitable bug to illustrate the main ingredients of a vulnerability. This vulnerability, named Dirty COW (CVE-2016-5195, ), allows attackers to turn a read-only mapping of a system file into a writable mapping, thus can be leveraged to achieve root access of the system. Here, the word COW stands for Copy-On-Write, a mechanism widely used in operating systems to efficiently implement a duplicate operation on modifiable resources. Dirty COW not only affects all Linux systems but also threats systems built upon Linux, such as Android.

To avoid bias, we do not rely on our personal opinion on whether a bug is exploitable or not. Instead, we rely on the CVE database, which is the most trusted source for security professionals. We focus solely on Linux kernel vulnerabilities because it is completely open-source and all related files and documents are easily accessed. Linux also has a history of excellent maintenance, supported by a vibrant community. If there is a vulnerability reported to CVE and confirmed by kernel developers, it is highly possible that the vulnerability will be patched eventually. Finally, most of the patches have detailed explanations and source code on the kernel tree.

We choose 101 samples that are clearly marked as concurrency related security vulnerabilities by Linux developers. These samples are retrieved from the CVE database using the keyword “race condition”; that is, they belong to CWE-362-Race Conditions. We conducted the search in mid 2018 while restricting the sample to those reported in the past ten years (2007-2017), which returned 110 samples in total. We discarded 9 of the 110 samples because they were under dispute, i.e., it remains unclear whether they are vulnerabilities.

We did not use the keyword “deadlock” in search for samples because the term is loosely used by developers to refer to anything that may lead to the system hung; in most cases, the cause is actually unrelated to concurrency. Since Linux is an operating system, any bug may cause system hung eventually. By focusing on CWE-362-Race Conditions, we guarantee that all vulnerabilities are indeed concurrency related.

For each of the 101 samples, we collected the following information: publishing date, which is when the vulnerability is archived by CVE; and duration between the publishing date and the last modified date, which is interpreted as the patching duration. We read all the descriptions, discussions, documentations, and code snippets, based on which we classified samples by their bug types, vulnerability types, and repair strategies. Here, bug types refer to either deadlock or non-deadlock bugs such as atomicity and order violations (Section 2.1). We consider the adversarial type, meaning whether the attack can be launched by a local user, who can run programs on the same computer, or a remote user. We also analyzed the bug manifestations, e.g., the number of threads and variables involved in triggering the bugs. Finally, we analyzed the repair strategies, which include condition check, code switch, lock strategy and design change (Section 6).

Following conventions used by security professionals in CVE (CVE-Details, ), we classify vulnerabilities into six categories: Memory Corruption (MC), Execute Code (EC), Denial of Service (DoS), Gain Privilege (GP), Gain Information (GI), and Bypass Something (BS). Note that these categories are not mutually exclusive, e.g., it is entirely possible that a vulnerability is labeled as both DoS and MC.

Memory Corruption (MC) refers to failures such as use-after-free, null pointer dereference, double free, and buffer overflow. Execute Code (EC) refers to execution of malicious code injected by the attacker or gathered from the existing code base, e.g., as in return-to-libc attacks (Shacham2007, ). These two types of failures often cause the other four types of failures.

Denial of Service (DoS) refers to scenarios where legitimate users are no longer able to access the network, system, local or remote resources. Sometimes, they may also experience unusually slow system performance. Gain Privilege (GP) refers to scenarios where non-root users are able to gain root access, which is obviously dangerous because it may lead to all kinds of other security issues. Gain Information (GI) refers to scenarios where sensitive information is revealed to attackers. Although it may seems benign initially, GI could be the first step of a sequence of destructive attacks. Bypass Something (BS) refers to scenarios where security restrictions such as authentication and file size restriction are skipped accidentally, which allows attackers to access resources that normally are not available to them.

As with any empirical study, our work has limitations. First, our conclusions are valid only for the specific type of vulnerabilities used in the study. Since we focus on concurrency vulnerabilities in Linux, the results should not be generalized beyond them. Nevertheless, since our sample size is sufficiently large, we expect that certain characteristics of the concurrency vulnerabilities to be general enough, and the patterns identified in this paper to be useful not only for Linux developers, but also other similar systems based on POSIX threads (PThreads) and written in C.

Since our study used exclusively the confirmed CVE entries, we do not know how many exploits occurred in practice, but were never reported to CVE. Although the CVE database is comprehensive, and often regarded as the official source by security professionals, it is entirely possible that some vulnerabilities were patched without ever being reported to CVE. Moreover, our data were based on vulnerabilities reported from 2007 to 2017, which are prior to the discovery of Meltdown (Lipp2018meltdown, ) and Spectre (Kocher2018spectre, ); therefore, newer types of security vulnerabilities (Guo2018, ; WuW19, ) may be under-represented or entirely missing.

Linux is written using the C language together with low-level synchronization primitives such as spin locks. In other systems and applications, such as Android and Web applications, the code is often written using different languages such as Java and JavaScript. Therefore, the characteristics of concurrency vulnerabilities may be entirely different. For example, memory corruption related vulnerabilities may not be as relevant in Android applications as in Linux kernel code due to the use of a “safe” language (Java) in Android.

Our first case study is on a vulnerability caused by deadlock. The deadlock is related to the Linux file splicing. It occurs when two or more threads try to access the same files using lock-based synchronization.

Recall that the kernel code may write to a file through piped steps, where each pipe has a read end and a write end. Data coming from the read end is redirected to the next step by the write end and, finally, is written to the file. As shown in CVE-2009-1961 (CVE-2009-1961, ), due to an implementation bug, concurrent calls to file splicing with pipe contention may lead to security attacks.

Figure 6 shows the related code snippet. The upper-left function, named _file_splice_write, splices data from a pipe to a file, whereas the upper-right is a more concise version of the function. The third function, named inode_double_lock, is meant to lock two input inodes in the parent-child order. Specifically, the file-splicing operation tries to lock both the pipe and the destination file (Line 3), and then moves data from the pipe to the file inside the function __splice_from_pipe (Line 6). However, due to a design error, there may be a deadlock when multiple threads use different locking orders on the same pipe and file.

Assume T1 and T2 execute the same _file_splice_write() over the same pipe and file, as shown in Figure 6. Following the dotted line, T1 locks both pipe and file using inode_double_lock() (Line 3) before transferring data in __splice_from_pipe() (Line 6). However, if the pipe is not ready, T1 will have to release the lock on pipe->inode and go to sleep. Next, T2 tries to lock the same pipe->inode and inode in inode_double_lock() (Line 12). At this moment, T2 can lock pipe->inode since it has been released by T1, but can never lock inode because it is still held by T1.

More seriously, the deadlock may be triggered by a (malicious) program with low privilege, and yet the deadlock itself will force the system to deny services to file creation and removal to all users, thus resulting in a DoS attack.

Furthermore, this particular deadlock pattern is actually quite common in Linux kernel. Three out of the five deadlock issues in our CVE entries have similar problems.

In this section, we study how atomicity violation may cause a security vulnerability in the kernel timer object, and how it may be exploited to launch an attack.

In a Linux kernel, developers can access the system’s timer through a file descriptor. The typical use of timer is to monitor the expiration of a running process. CVE-2017-10661 (CVE-2017-10661, ) describes a vulnerability that can be triggered by an attacker running multiple threads on the same timer file descriptor.

Figure 7 shows the code snippet where both kernel APIs, _remove and _setup, take the file descriptor pointer (*ctx) as a parameter. The descriptor, of the type timerdf_ctx, is a C structure containing a Boolean variable named might_cancel (Line 4), indicating if the linked list entry clist (Line 3) may be removed from its host.

The function _remove() is meant to delete the node clist. If ctx->might_cancel is true, then _remove() changes it to false (Line 7) and removes clist (Line 9). The function _setup() calls _remove() (Line 20) if its ctx->might_cancel is true; otherwise, it sets ctx’s might_cancel to true (Line 15) and then inserts clist to the linked list (Line 17).

In the ideal case, _setup() and _remove() work cooperatively: the former updates the flag and inserts the node while the latter resets the flag and removes the inserted node. However, the implementation of these two APIs fails to enforce the sequence of operations on ctx as atomic.

Therefore, an attacker can leverage this bug to trigger a memory corruption, e.g., by running the following two-threaded program.

This runtime failure may also lead to a DoS attack, e.g., when multiple threads keep on removing the same list entry.

So far we focus only on vulnerabilities that cause noticeable system failures, but there is another type, called Gain Information (GI), that may be more subtle in that it does not have obvious symptoms. While GI seems benign, it can silently disclose sensitive kernel data and thus lead to subsequent attacks. In this section we study how order violation may lead to GI, as shown in CVE-2017-1000380 (CVE-2017-1000380, ), which allows a local users to read sensitive information of others.

Figure 8 shows kernel APIs _user_tselect() and _user_read() from the ALSA subsystem, with the same parameter *file. The parameter has a snd_timer_user pointer field as tu (Line 3 and Line 18, respectively). The function _user_tselect() re-allocates heap buffer for the queue object tqueue or queue in tu, depending on the flag tread (Lines 9-14). To avoid memory leaks, _user_tselect() also frees and resets the two pointers before the new memory allocation (Lines 5-8).

The function _user_read() copies the tqueue or queue data from kernel space to user space by calling copy_to_user() (Lines 22 and 24, respectively). The source of the copy operation also depends on the flag tu->tread. To protect the data-copy against unwanted interruption, _user_read() locks ioctl_lock (Line 20) until it finishes the data transmission (Line 26).

The problem occurs if copy_to_user() is invoked right after _user_tselect() allocates the new memory, as shown by the red dotted lines in Figure 8. Note that the kernel API kmalloc() does not initialize its allocated memory, thus the remaining data in the newly allocated memory would be directly copied to the buffer in the user space. The problem is due to an order violation where the concurrent copy operation violates the intended order between the kmalloc invocation and the subsequent memory operation.

To trigger the leak, an attacker may construct a two-threaded program similar to the code introduced in section 4.2, where the two threads operate on the same file pointer by repeatedly invoking _user_tselect() and _user_read(), respectively. Once the aforementioned interleaving occurs, uninitialized memory content will be leaked to the user space.

Concurrent vulnerabilities are common in Linux kernel code. The three case studies presented in this section represent three different concurrency bug types. They also lead to different types of system failures such as hung, program crash, and information leak. Often times, these system failures are correlated with each other, which means it is not always possible to classify a concurrency vulnerability into any one type (see Section 5 for details).

The erroneous thread interleavings that we present are not necessarily the only possible ways of exploiting these vulnerabilities. There may be many other possible interleavings. In fact, concurrency often leads to a large number of possible interleavings, some of which may be exploited; this is also one of the reasons why concurrency vulnerability detection and mitigation may be difficult.

Our vulnerability samples are from the past ten years. Figure 9 shows the number in each year. We omit the entries of the year 2018 because our data gathering was conducted in the summer of 2018. The result shows that, overall, the number of concurrency vulnerabilities is increasing.

To understand how long it takes for developers to patch a vulnerability, we compute the duration between the publishing date and the last modified date. The longer the duration, the more time is needed by developers to understand and patch the vulnerability. Figure 10 shows the distribution of 101 vulnerabilities over different patch durations from 1 quarter up to 3 years. The distribution shows a high distribution on both sides, indicating a vulnerability will either be relatively easy to patch, i.e., in a short period of time, or so difficult that it cannot be patched within a coupe of years.

Table 2 shows how many patches are needed before a vulnerability is eliminated. Only 19 of the 101 vulnerabilities (or 18%) were eliminated by the first patch. In contrast, 37 of them (or 36%) required more than five patches. This is also alarming because it shows how difficult it is to construct a patch. Here, more patches generally mean that the vulnerability is more complex. Since reasoning about thread interaction is challenging, developers often need to construct the patch in a trial-and-error fashion.

Next, we present characteristics of the concurrency bugs associated with the 101 vulnerabilities. Figure 11 shows the distribution of bug types on the left-hand size, and the number of threads and variables on the right-hand side. The result shows that the vast majority (95%) are non-deadlock bugs, whereas deadlocks account for only 5%. Furthermore, among the non-deadlock bugs, there are five times more atomicity violations than order violations.

As for the number of threads and variables involved in each vulnerability, we find that only 2 of the 101 samples clearly involve more than two threads and one variable. The rare occurrence of more than two threads and one variable suggests that we, as a community, should focus more on these cases during vulnerability detection and repair.

Next, we present statistics on the adversarial types and vulnerability types. For adversarial types, we want to know whether the attacker needs to be a local user, e.g., a user who can execute non-privileged programs on the victim’s computer, or a remote user who has to access the victim’s server. Table 3 shows the distribution of these two types of adversaries. The result shows that only 10% of concurrency vulnerabilities are exploitable by a remote user.

Table 4 shows the distribution of vulnerability types. Among the 101 samples, 72% of them may lead to Denial of Service (DoS), 69% of them lead to Memory Corruption (MC), and 30% of them lead to Gain Privilege (GP). Each of the other three types accounts for less than 10%. Among these six vulnerability types, GP (30%) is particularly alarming, because the operating system cannot afford to have such a high risk of losing privileges to attackers. While GI (6%) and BS (5%) are also rare, they should not be neglected because they are often the first steps of a sequence of deadly attacks.

Since the vulnerability types are not mutually exclusive, we want to know how much they overlap. Figure 12 shows the Venn diagram of the three largest groups: DoS, MC, and GP, together with the number of vulnerabilities in each group. Among the 101 samples, 56 may lead to both DoS and MC, 23 may lead to both DoS and GP, and 23 may lead to both MC and GP. Interestingly, there are 10 vulnerabilities that may lead to all three types. A closer look at these 10 vulnerabilities show that MC could potentially grant the attacker more privilege in the system and then cause the system to hang.

Table 5 shows the manifestations of each vulnerability type, i.e., the number of variables and threads involved in triggering the vulnerability. The result shows that nearly all of them involve two threads and one shared variable. For the vulnerabilities that involve more than two threads and more than one variable, a closer look shows that they can only lead to DoS and GP, perhaps because they sometimes require more complex thread interactions.

Table 6 shows the bug type distribution within each vulnerability type. That is, for each vulnerability type, it shows how many of them are caused by deadlock, atomicity violations, and order violations. The main observation is that atomicity violation may lead to all kinds of vulnerabilities, and therefore should be the focus of future research on concurrency vulnerability detection, analysis, and repair.

Only one case with Denial of Service and Memory Corruption vulnerability types has deadlock bug type (CVE-2018-1000004, ). In that case, deadlock leads to Denial of Service or it may have use-after-free of Memory Corruption vulnerability.

Condition check is an intuitive way of changing the intra-thread control flow as well as the inter-thread interleaving, thus avoiding the unsafe program states. For example, in the aforementioned CVE-2016-5195 (Dirty COW), developers adopted a patch constructed by adding a condition check.

Recall that in Dirty COW, the problem comes from the unexpected removal of a specific Get User Pages Flags (or gup_flags) during the handling of page faults, which is then exploited to grant the write access to privileged files.

One way to address the problem is introducing a new internal flag, named FOLL_COW, for gup_flags; the new flag indicates the completion of the Copy-On-Write process.

Figure 13 shows the difference between the original and modified versions of a related code snippet, where the condition check is inserted to validate the page table entries (pte) checking: pte can only be writable after going through a COW cycle. By adding this condition check, the code will be able to properly handle the case where COW-ed page is purged by a malicious thread.

Another strategy for eliminating concurrency vulnerabilities is switching the order of certain code statements. Consider the patch of CVE-2016-9794 as an example, which demonstrates this strategy.

Here, a function named kill_fasync() is provided by the Digital Audio (PCM) library in Linux kernel. As shown in Figure 14, the vulnerable code invokes this function from outside of the stream lock protected region, which may lead to a race condition.

The quick workaround adopted by Linux kernel developers is to move the call to kill_fasync() inside the region protected by the stream lock. Although this one-liner may enlarge the scope of the stream lock protected region, and thus in theory lead to performance degradation, in practice, it actually has little impact on the system’s performance.

The third strategy for eliminating concurrency vulnerabilities is to change the way locks are used. For example, a new lock may be inserted to wrap up an entire critical section, to avoid it being interrupted by other threads. However, new locks must be added with caution since they often lead to performance degradation. This is especially important for Linux kernel developers who care about performance.

Figure 15 shows a patch constructed for CVE-2017-10661, which has been discussed in Section 4.2. Here, a new lock-unlock pair is added to protect the critical region, to ensure that the concurrent operations on ctx inside setup() and remove() are always executed atomically.

The last repair strategy that developers used to eliminate concurrency vulnerabilities is design change. That is, developers choose to solve the security issues by refactoring the program, which in turn changes the thread synchronization patterns as well as the related data structures. Although the complexity of design change may vary, e.g., ranging from simply removing a few unnecessary variables from the shared data structure to reimplementing the entire functionality, in general, it is significantly more complex than the other three strategies. Therefore, it is also the most difficult to automate.

For example, in CVE-2016-2545 (CVE-2016-2545, ), recall that the problem is due to snd_timer_interrupt() from Advanced Linux Sound Architecture (ALSA) subsystem, which does not properly maintain a couple of linked lists. Therefore, it allows a local user to trigger a race condition and then a system crash. In this case, the linked lists may be removed by another function named snd_timer_stop() while it is being removed by the function snd_timer_interrupt(), thus resulting in a double-free.

The patch adopted by Linux developers added a brand-new function named list_del_init(), which is used to remove the list. Then, all other functions delegate the deletion operation to this new function. They can avoid the double-free error by always re-initializing the list entry after deletion.

We analyze the patches adopted by Linux developers for the 101 concurrency vulnerabilities, and count the number of times each of the four repair strategies are used for each vulnerability type. The result is shown in Figure 16. That is, for every vulnerability type, we show the number of times that each repair strategy is used to construct the patches.

The result shows that, overall, condition check is the most frequently used repair strategy; lock strategy is also used to construct patches for all vulnerability types. However, since adding locks may lead to severe performance degradation, it is not as frequently used by kernel developers as they are used by application developers (aldrich2003comprehensive, ; bogda1999removing, ; ruf2000effective, ). This is perhaps because kernel developers are more cautious about the patch’s performance impact. In contrast, design change has been used for DoS, MC, GP and GI only. Finally, code switch has been used for DoS, MS, and GP only. Although it may appear to be simple, code switch can become tricky and thus may not be applicable in complex situations where it is difficult to determine whether swapping the order of program statements may fix certain issues.

Overall, our result shows that patching concurrency vulnerabilities remain a challenging task: the duration between a vulnerability’s publishing date and the last-modification date is long. Thus, we need to devote more effort in developing automated tools and techniques, to help speed up the vulnerability detection, analysis, and repair.