Yuandao Cai

Runtime feedback is at the heart of efficient greybox fuzzing, and the collection of runtime feedback is the most important infrastructure for greybox fuzzing. However, existing fuzzers have difficulty collecting runtime feedback for the memory, which is the most important and vulnerable component of a running program. The operating system does not support associative queries between arbitrary pointers and runtime objects. Therefore, existing works only capture aggregate statistics (e.g., memory usage) or random quantities (e.g., the random addresses stored in pointers) to provide low-precision memory-related feedback. This article presents Spinel , a greybox fuzzer equipped with a brand-new infrastructure for memory feedback collection. It introduces an almost zero-overhead runtime system for associating arbitrary pointers with the corresponding runtime objects and offers spatial distance information as memory-related fuzzing feedback. To avoid introducing accumulated overhead upon silent error detectors (e.g., sanitizers that are used to detect memory safety violations), we introduce the post-execution validation technique to remove the expensive runtime safety checks while maintaining the same error detection ability. Our experiments on 33 real-world programs show that Spinel detects 1.30×–2.33× unique bugs compared to state-of-the-art fuzzers. Furthermore, according to the restricted mean survival time, Spinel achieves 1.56×–8.21× speed up in triggering ground-truth bugs collected by the Magma benchmark.

Concurrency bugs, caused by improper synchronization of shared resources in multi-threaded or distributed systems, are notoriously hard to detect and thus compromise software reliability and security. The existing deep learning methods face three main limitations. First, there is an absence of large and dedicated datasets of diverse concurrency bugs for them. Second, they lack sufficient representation of concurrency semantics. Third, binary classification results fail to provide finer-grained debug information such as precise bug lines. To address these problems, we propose a novel method for effective concurrency bug detection as well as localization. We construct a dedicated concurrency bug dataset to facilitate model training and evaluation. We then integrate a pre-trained model with a heterogeneous graph neural network (GNN), by incorporating a new Concurrency-Aware Code Property Graph (CCPG) that concisely and effectively characterizes concurrency semantics. To further facilitate debugging, we employ SubgraphX, a GNN-based interpretability method, which explores the graphs to precisely localize concurrency bugs, mapping them to specific lines of source code. On average, our method demonstrates an improvement of 10\% in accuracy and precision and 26\% in recall compared to state-of-the-art methods across diverse evaluation settings.

Memory safety sanitizers, the sharp weapon for detecting invalid memory operations during execution, employ runtime metadata to model the memory and help find memory errors hidden in the programs. However, location-based methods, the most widely deployed memory sanitization methods thanks to high compatibility, face the low protection density issue: the number of bytes safeguarded by one metadata is limited. As a result, numerous memory accesses require loading excessive metadata, leading to a high runtime overhead. To address this issue, we propose a new shadow encoding with segment folding to increase the protection density. Specifically, we characterize neighboring bytes with identical metadata by building novel summaries, called folded segments , on those bytes to reduce unnecessary metadata loadings. The new encoding uses less metadata to safeguard large memory regions with fewer instructions than existing works, speeding up memory sanitization. We implement our designed technique as GiantSan . Our evaluation using the SPEC CPU 2017 benchmark shows that GiantSan outperforms the state-of-the-art sanitization methods with 61.37% and 41.94% less runtime overhead than ASan and ASan–, respectively. Moreover, under the same redzone setting, GiantSan detects 463 fewer false negative cases than ASan and ASan-- in testing the real-world project PHP.

Static analysis tools for capturing bugs and vulnerabilities in software programs are widely employed in practice, as they have the unique advantages of high coverage and independence from the execution environment. However, existing tools for analyzing large codebases often produce a great deal of false warnings over genuine bug reports. As a result, developers are required to manually inspect and confirm each warning, a challenging, time-consuming, and automation-essential task. This article advocates a fast, general, and easily extensible approach called Llm4sa that automatically inspects a sheer volume of static warnings by harnessing (some of) the powers of Large Language Models (LLMs). Our key insight is that LLMs have advanced program understanding capabilities, enabling them to effectively act as human experts in conducting manual inspections on bug warnings with their relevant code snippets. In this spirit, we propose a static analysis to effectively extract the relevant code snippets via program dependence traversal guided by the bug warning reports themselves. Then, by formulating customized questions that are enriched with domain knowledge and representative cases to query LLMs, Llm4sa can remove a great deal of false warnings and facilitate bug discovery significantly. Our experiments demonstrate that Llm4sa is practical in automatically inspecting thousands of static warnings from Juliet benchmark programs and 11 real-world C/C++ projects, showcasing a high precision (81.13%) and a recall rate (94.64%) for a total of 9,547 bug warnings. Our research introduces new opportunities and methodologies for using the LLMs to reduce human labor costs, improve the precision of static analyzers, and ensure software trustworthiness

Memory safety sanitizers, the sharp weapon for detecting invalid memory operations during execution, employ runtime metadata to model the memory and help find memory errors hidden in the programs. However, location-based methods, the most widely deployed memory sanitization methods thanks to their high compatibility, face the low protection density issue: the number of bytes safeguarded by one metadata is limited. As a result, numerous memory accesses require loading excessive metadata, leading to a high runtime overhead. To address this issue, we propose a new shadow encoding with segment folding to increase the protection density. Specifically, we characterize neighboring bytes with identical metadata by building novel summaries, called folded segments, on those bytes to reduce unnecessary metadata loadings. The new encoding uses less metadata to safeguard large memory regions, speeding up memory sanitization. We implement our designed technique as GiantSan. Our evaluation using the SPEC CPU 2017 benchmark shows that GiantSan outperforms the state-of-the-art methods with 59.10% and 38.52% less runtime overhead than ASan and ASan-, respectively. Moreover, under the same redzone setting, GiantSan detects 463 fewer false negative cases than ASan and ASan- in testing the real-world project PHP.

Static analysis has been widely used in large-scale software defect detection. Despite recent advances, it is still not practical enough because it requires compilation interference to obtain analyzable code. Directly translating the binary code using a binary lifter mitigates this practicality problem by being non-intrusive to the building system. However, existing binary lifters cannot produce precise enough code for rigorous static analysis even in the presence of the debug information. In this paper, we propose a new binary lifter Plankton together with two new algorithms that can fill the gaps between the low- and high-level code to produce high-quality LLVM intermediate representations (IRs) from binaries with debug information, enabling full-fledged static analysis with minor precision loss. Plankton shows comparable static analysis results with traditional compilation interference solutions, producing only 17.2% differences while being much more practical, outperforming existing lifters by 76.9% on average.

After decades of research, constructing call graphs for modern C-based software remains either imprecise or inefficient when scaling up to the ever-growing complexity. The main culprit is the difficulty of resolving function pointers, as precise pointer analyses are cubic in nature and become exponential when considering calling contexts. This paper takes a practical stance by first conducting a comprehensive empirical study of function pointer manipulations in the wild. By investigating 5355 indirect calls in five popular open-source systems, we conclude that, instead of the past uniform treatments for function pointers, a cocktail approach can be more effective in “squeezing” the number of difficult pointers to a minimum using a potpourri of cheap methods. In particular, we decompose the costs of constructing highly precise call graphs of big code by tailoring several increasingly precise algorithms and synergizing them into a concerted workflow. As a result, many indirect calls can be precisely resolved in an efficient and principled fashion, thereby reducing the final, expensive refinements. This is, in spirit, similar to the well-known cocktail medical therapy. The results are encouraging — our implemented prototype called Coral can achieve similar precision versus the previous field-, flow-, and context-sensitive Andersen-style call graph construction, yet scale up to millions of lines of code for the first time, to the best of our knowledge. Moreover, by evaluating the produced call graphs through the lens of downstream clients (i.e., use-after-free detection, thin slicing, and directed grey-box fuzzing), the results show that Coral can dramatically improve their effectiveness for better vulnerability hunting, understanding, and reproduction. More excitingly, we found twelve confirmed bugs (six impacted by indirect calls) in popular systems (e.g., MariaDB), spreading across multiple historical versions.