Recently, dynamic concurrency bug predictions have kept making notable progress in improving concurrency coverage while ensuring soundness. Most of them rely solely on dynamic information in traces and overlook the static semantics of the program when predicting bugs. To ensure soundness, they assume that any (memory) read can fully affect subsequent program execution via control-flow and data-flow. However, the assumption over-approximates constraints among (memory) writes and reads and hence limits reordering space over thread interleaving, ultimately leading to false negatives. From program semantics, only a subset of reads actually affect their subsequent executions. Therefore, by refining dependencies between reads and subsequent executions based on static program semantics, one can refine the assumption and eliminate unnecessary constraints. This can bring a chance to explore more thread interleaving space and uncover more concurrency bugs. However, refining dependencies can compromise soundness and bring heavy overhead. To tackle these challenges, this paper introduces the concept of Necessary Consistent Read Event (NRE) and a hybrid analysis algorithm. NRE refines dependencies between reads and their subsequent events and is used to identify necessary constraints where a read probably affects the execution of its subsequent events. Next, we design an efficient and accurate hybrid analysis algorithm to calculate NREs for each event in the trace. The hybrid analysis algorithm maps events to program SSA instructions and simulates executions based on the original trace. NRE and the algorithm can enhance the capabilities of existing concurrency bug prediction methods at a low cost, regardless of the type of concurrency bug they target. In this paper, we focused on data race and developed NRE and the algorithm as a prototype tool RECONP. We conducted a set of comparative experiments on MySQL with M2 and Seqcheck. The results show that RECONP can detect 46.9% and 22.4% more data races than M2 and Seqcheck, respectively. And the hybrid algorithm only accounts for 34% of the total time cost.

Due to the non-determinism of thread interleaving, predicting concurrency bugs has long been an extremely difficult task. Recently, several sound bug-detecting approaches were proposed. These approaches are based on local search, i.e., mutating the sequential order of the observed trace and predicting whether the mutated sequential order can trigger a bug. Surprisingly, during this process, they never consider reordering the data flow of the pointers, which can be the key point to detecting many complex bugs. To alleviate this weakness, we propose a new flow-sensitive point-to analysis technique ConPTA to help actively reorder the pointer flow during the sequential order mutation process. Based on ConPTA, we further propose a new sound predictive bug-detecting approach Eagle to predict four types of concurrency bugs. They are null pointer dereference (NPD), uninitialized pointer use (UPU), use after free (UAF), and double free (DF). By actively reordering the pointer flow, Eagle can explore a larger search space of the thread interleaving during the mutation and thus detect more concurrency bugs. Our evaluation of Eagle on 10 real-world multi-threaded programs shows that Eagle significantly outperforms four state-of-the-art bug-detecting approaches UFO, ConVul, ConVulPOE and Period in both effectiveness and efficiency.

Developing correct multi-threaded programs is challenging and concurrency bugs can be easily introduced. Many of them, known as concurrency vulnerabilities, can be exploited to launch attacks. Fuzzing is shown to be a practical and effective technique to expose vulnerabilities. However, existing works on fuzzing concurrency vulnerabilities almost all follow the framework (like AFL++) designed for fuzzing sequential vulnerabilities. Unlike sequential vulnerabilities, concurrency ones cannot be easily triggered. Concurrency vulnerabilities rely on both inputs and thread interleaving to be exposed while existing fuzzing techniques mainly focus on how to generate effective inputs. We present a new framework based on an existing fuzzing technique, AFL++, to integrate the predictive techniques for effective concurrency vulnerability detection. For every input (the original and the mutated ones), we call a predictive tool such that, even if a concurrency vulnerability is not really triggered, it can be predicted. To overcome heavy efficiency challenges existing in predictive tools, we propose to selectively call a predictive tool based on concurrency coverage criteria. We have selected a sound predictive tool SeqCheck and adapted it to propose our fuzzing framework PredFuzz. We compared our tool with two tools, AFL++ integrated with Google ThreadSanitizer and AFL++ directly integrated with SeqCheck, on six previously studied multi-threaded programs. The experimental results showed that PredFuzz detected significantly more vulnerabilities than AFL++ integrated with ThreadSanitizer and about 70% vulnerabilities detected by AFL++ directly integrated with SeqCheck. Besides, it is extremely efficient without compromising the fuzzing speed of AFL++: it added a smaller slowdown to AFL++ than ThreadSanitizer did and achieved a speedup of more than 1,000x when compared to AFL++ directly integrated with SeqCheck.

Data races seriously threaten the correctness of concurrent programs. Earlier works can report false positives. Recently, trace-based predictive analysis has achieved sound results by inferring feasible traces based on sound partial orders or constraint solvers. However, they hold the same assumption: any read event may affect the control-flow of a predicted trace. Thus, being control-flow sensitive, they have to enforce any read event (in an inferred trace) to either read the same value or a value from the same event as that in the original trace, albeit some slightly relax this. This (even with relaxation) severely limits their predictive ability and many true data races can be missed. We introduce the concept of Fix-Point Event and propose a new partial order model. This allows us to not only predict races with witness traces (like existing works with no control-flow changes) but also soundly infer existences of witness traces with potential control-flow changes. Thus, we can achieve a higher concurrency coverage and detect more data races soundly. We have implemented above as a tool ToccRACE and conducted a set of experiments on a benchmark of seven real-world programs and a large-scale software MySQL, where MySQL produced 427 traces with a total size of 3.4TB. Compared with the state-of-the-art sound data race detector SeqCheck,ToccRACE is significantly more effective by detecting 84.4%/200% more unique/dynamic races on the benchmark programs and 52.22%/49.8% more unique/dynamic races on MySQL, incurring reasonable time and memory costs (about 1.1x×43.5x on the benchmark programs and 10x/1.03x on MySQL). Furthermore, ToccRACE is sound and is comnlcte on two threads.

TarGuess − I is a leading online targeted password guessing model using users’ personally identifiable information (PII) proposed at ACM CCS 2016 by Wang et al. It has attracted widespread attention in password security owing to its superior guessing performance. Yet, after analyzing the users’ vulnerable behaviors of using popular passwords and constructing passwords with users’ PII, we find that this model does not take into account popular passwords, keyboard patterns, and the special strings. The special strings are the strings related to users but do not appear in the users’ demographic information. Thus, we propose TarGuess − I + K P X , a modified password guessing model with three semantic methods, including (1) identifying popular passwords by generating top-300 lists from similar websites, (2) recognizing keyboard patterns by relative position, and (3) catching the special strings by extracting continuous characters from user-generated PII. We conduct a series of evaluations on six large-scale real-world leaked password datasets. The experimental results show that our modified model outperforms TarGuess − I by 2.62% within 100 guesses.