Logic bugs can cause DBMSs to silently produce incorrect results for a given query, posing significant threats to software reliability and remaining challenging to detect. Join is a fundamental operation in DBMSs, enabling the combination of data from multiple tables; however, due to its complexity, it is also susceptible to logic bugs. Existing works detect logic bugs in join optimizations by altering query hints and system variables to alter the optimizer's choice of execution plans. However, these approaches struggle to detect logic bugs when query hints or system variables fail to influence the optimizer's behavior, or when the logic bugs reside in join implementation code that is unrelated to optimization. In this paper, we present S et R elation S ynthesis (SRS), a black-box testing approach that detects logic bugs of join implementation in DBMSs by leveraging set relations among different join operations. SRS applies transformations to the original join queries, including modifications to join types, join orders, and join conditions, while ensuring that the outputs of both the original and transformed queries preserve the expected set relations. Violations of these set relations indicate potential logic bugs. We realized SRS and evaluated it on five widely-used and extensively-tested DBMSs: MySQL, MariaDB, TiDB, PostgreSQL, and DuckDB. SRS uncovered 33 previously unknown and unique bugs, all of which have been confirmed, with 12 already fixed. Among these, 33 are logic bugs, demonstrating SRS's effectiveness and practicality in detecting logic bugs in the implementation of join operations within DBMSs.

Logic bugs are bugs that can cause database management systems (DBMSs) to silently produce incorrect results for given queries. Such bugs are severe, because they can easily be overlooked by both developers and users, and can cause applications that rely on the DBMSs to malfunction. In this work, we propose Constant-Optimization-Driven Database Testing (CODDTest) as a novel approach for detecting logic bugs in DBMSs. This method draws inspiration from two well-known optimizations in compilers: constant folding and constant propagation. Our key insight is that for a certain database state and query containing a predicate, we can apply constant folding on the predicate by replacing an expression in the predicate with a constant, anticipating that the results of this predicate remain unchanged; any discrepancy indicates a bug in the DBMS. We evaluated CODDTest on five mature and extensively-tested DBMSs--SQLite, MySQL, CockroachDB, DuckDB, and TiDB--and found 45 unique, previously unknown bugs in them. Out of these, 24 are unique logic bugs. Our manual analysis of the state-of-the-art approaches indicates that 11 logic bugs are detectable only by CODDTest. We believe that CODDTest is easy to implement, and can be widely adopted in practice.

While deep neural networks provide state-of-the-art solutions to a wide range of programming language tasks, their effectiveness in dealing with foundational program analysis tasks remains under explored. In this paper, we present an empirical study that evaluates four prominent models of code (i.e., CuBERT, CodeBERT, GGNN, and Graph Sandwiches) in two such foundational tasks: (1) alias prediction, in which models predict whether two pointers must alias, may alias or must not alias; and (2) equivalence prediction, in which models predict whether or not two programs are semantically equivalent. At the core of this study is CodeSem, a dataset built upon the source code of real-world flagship software (e.g., Linux Kernel, GCC, MySQL) and manually validated for the two prediction tasks. Results show that all models are accurate in both prediction tasks, especially CuBERT with an accuracy of 89% and 84% in alias prediction and equivalence prediction, respectively. We also conduct a comprehensive, in-depth analysis of the results of all models in both tasks, concluding that deep learning models are generally capable of performing foundational tasks in program analysis even though in specific cases their weaknesses are also evident. Our code and evaluation data are publicly available at https://github.com/CodeSemDataset/CodeSem.

Datalog is a popular and widely-used declarative logic programming language. Datalog engines apply many cross-rule optimizations; bugs in them can cause incorrect results. To detect such optimization bugs, we propose an automated testing approach called Incremental Rule Evaluation (IRE), which synergistically tackles the test oracle and test case generation problem. The core idea behind the test oracle is to compare the results of an optimized program and a program without cross-rule optimization; any difference indicates a bug in the Datalog engine. Our core insight is that, for an optimized, incrementally-generated Datalog program, we can evaluate all rules individually by constructing a reference program to disable the optimizations that are performed among multiple rules. Incrementally generating test cases not only allows us to apply the test oracle for every new rule generated—we also can ensure that every newly added rule generates a non-empty result with a given probability and eschew recomputing already-known facts. We implemented IRE as a tool named Deopt, and evaluated Deopt on four mature Datalog engines, namely Soufflé, CozoDB, μZ, and DDlog, and discovered a total of 30 bugs. Of these, 13 were logic bugs, while the remaining were crash and error bugs. Deopt can detect all bugs found by queryFuzz, a state-of-the-art approach. Out of the bugs identified by Deopt, queryFuzz might be unable to detect 5. Our incremental test case generation approach is efficient; for example, for test cases containing 60 rules, our incremental approach can produce 1.17× (for DDlog) to 31.02× (for Soufflé) as many valid test cases with non-empty results as the naive random method. We believe that the simplicity and the generality of the approach will lead to its wide adoption in practice.

With the rapid expansion of the Internet of Things, a vast number of microcontroller-based (MCU) IoT devices are now susceptible to attacks through the Internet. Vulnerabilities within the firmware are one of the most important attack surfaces. Fuzzing has emerged as one of the most effective techniques for identifying such vulnerabilities. However, when applied to IoT firmware, several challenges arise, including: 1) the inability of firmware to execute properly in the absence of peripherals; 2) the lack of support for exploring input spaces of multiple peripherals; 3) difficulties in instrumenting and gathering feedback; and 4) the absence of a fault detection mechanism. To address these challenges, we have developed and implemented an innovative peripheral-independent hybrid fuzzing tool called FirmHybirdFuzzer. This tool enables testing of MCU firmware without reliance on specific peripheral hardware. First, a unified virtual peripheral was integrated to model the behaviors of various peripherals, thus enabling the physical devices-agnostic firmware execution. Then, a hybrid event generation approach was used to generate inputs for different peripheral accesses. Furthermore, two-level coverage feedback was collected to optimize the testcase generation. Finally, a plugin-based fault detection mechanism was implemented to identify typical memory corruption vulnerabilities. A large-scale experimental evaluation has been performed to show FirmHybirdFuzzer’s effectiveness and efficiency.

Background: Firmware is the enable software of Internet of Things (IoT) devices, and its software vulnerabilities are one of the primary reason of IoT devices being exploited. Due to the limited resources of IoT devices, it is impractical to deploy sophisticated run-time protection techniques. Under an insecure network environment, when a firmware is exploited, it may lead to denial of service, information disclosure, elevation of privilege, or even life-threatening. Therefore, firmware vulnerability detection by fuzzing has become the key to ensure the security of IoT devices, and has also become a hot topic in academic and industrial research. With the rapid growth of the existing IoT devices, the size and complexity of firmware, the variety of firmware types, and the firmware defects, existing IoT firmware fuzzing methods face challenges. Objective: This paper summarizes the typical types of IoT firmware fuzzing methods, analyzes the contribution of these works, and summarizes the shortcomings of existing fuzzing methods. Method: We design several research questions, extract keywords from the research questions, then use the keywords to search for related literature. Result: We divide the existing firmware fuzzing work into real-device-based fuzzing and simulation-based fuzzing according to the firmware execution environment, and simulation-based fuzzing is the mainstream in the future; we found that the main types of vulnerabilities targeted by existing fuzzing methods are memory corruption vulnerabilities; firmware fuzzing faces more difficulties than ordinary software fuzzing. Conclusion: Through the analysis of the advantages and disadvantages of different methods, this review provides guidance for further improving the performance of fuzzing techniques, and proposes several recommendations from the findings of this review.