Memory corruption vulnerabilities can occur in multithreaded executions, known as concurrency vulnerabilities. They are extremely harmful and can be frequently exploited to launch severe attacks. Unfortunately, it’s very difficult to detect them due to non-determination multithreaded executions,

One straightforward detection approach would be to explore all possible thread interleaving (e.g., model checking approaches); however, the executions of multithreaded programs suffer from interleaving space explosion problem. Some researchers tried to apply data race detectors to detect concurrency vulnerabilities, which is actually ineffective due to the difference between data race and concurrency vulnerabilities. Recent techniques based via constraints soling tends to miss concurrency vulnerabilities in practice.

Recently, a research team led by Prof. CAI Yan from the State Key Laboratory of Computer Science, Institute of Software of the Chinese Academy of Sciences (ISCAS), presented a novel detection method. This method focused on three kinds of concurrency vulnerabilities involving memory corruptions (i.e., UAF: Use-After-Free, NPD: Null-Pointer-Dereference and DF: Double Free), which are mostly considered to be caused by orders. For example, Figure 1 shows two threads: a thread t1 dereference a pointer via p->test(), and a second thread t2 frees the same pointer free(p). A concurrency UAF can occur if thread t2 executes free(p) before thread t1.

The insight is that, the key to detect concurrency vulnerabilities is to determine whether two or more out of a set of memory operation events in a given execution are exchangeable. Based on this, a new concept of Exchangeable Events is proposed to determine whether the orders of two events can be probably reversed. Given two ordered events, if there exists a third events (eany in Figure 2) that satisfied a set of relationship (see Figure 2) with the given two events (e1 and e2), there will be a high probability for the two events to be exchangeable events. Intuitively, if their distance between the two given events is smaller, there will be a higher probability to reverse the execution order of the two events. The team thus proposed an evaluation on the distance based on a third event, as shown in Figure 2. Exchangeable events are defined across synchronizations; hence, they have larger coverage. The research team further designed three algorithms to detect these three kinds of concurrency vulnerabilities from correct executions based on exchangeable events. 

This method has been evaluated to be significantly effective on detecting concurrency vulnerabilities even in large-scale programs.

The study entitled “Detecting Concurrency Memory Corruption Vulnerabilities” has been published in the 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE2019). 

Figure 1. A concurrency vulnerability caused by orders