Sanitizing Large Language Models in Bug Detection with Data-Flow (2024)

Abstract: Large language models (LLMs) show potential in code reasoning tasks, facilitating the customization of detecting bugs in software development. However, the hallucination effect can significantly compromise the reliability of bug reports. This work formulates a new schema of bug detection and presents a novel sanitization technique that detects false positives for hallucination mitigation. Our key idea is to enforce LLMs to emit data-flow paths in few-shot chain-of-thought prompting and validate them via the program-property decomposition. Specifically, we dissect data-flow paths into basic properties upon concise code snippets and leverage parsing-based analysis and LLMs for validation. Our approach averagely achieves 91.03% precision and 74.00% recall upon synthetic benchmarks and boosts the precision by 21.99% with the sanitization. The evaluation upon real-world Android malware applications also demonstrates the superiority over an industrial analyzer, surpassing the precision and recall by 15.36% and 3.61%, respectively.

## introduction the advancement of generative ai has significantly improved software development efficiency @xcite . many even believe that ais can become proficient programmers. however, just like human developers, ais can make mistakes that potentially lead to program bugs, which necessitates bug detection in the new development paradigm. classic approaches predominantly apply program analysis in the production line before software release @xcite . in figure 1 , for example, developers can diagnose and fix a divide-by-zero (dbz) bug when the program analyzer determines that the potential zero value of parseint(arg) at line 13 is finally used as the divisor at line 5. however, these techniques demand the implementation of complex semantic analyses and compilation of the examined code, which restrains the construction and application of bug detectors, especially during the early development stage, when programs are incomplete and cannot be compiled @xcite . recent advancements in large language models (llms) offer exciting opportunities, allowing non-experts of program analysis to construct bug detectors and handle incomplete programs. ideally, developers can easily build a custom bug detector via few-shot chain-of-thought (cot) prompting @xcite , where they only need to provide several buggy programs with explanations as examples. however, the non-alignment between llms and program semantics often leads to substantial hallucinations @xcite , significantly compromising the validity of detection results. for example, llms may report a dbz bug at line 3 because they cannot understand the semantic correlation between the division at line 3 and the zero-value check at line 2. our preliminary experiment also shows that gpt-3.5-turbo-0125 produces 184 false positives in 239 reports when detecting null pointer dereference (npd) in juliet test suite @xcite . the substantial false positives diminish user confidence in the detection results, thereby preventing the practical adoption of the detector @xcite . valid spurious spurious 𝑝 ! : 𝑝 " : 𝑝 # : (𝑒 !" , ℓ !" ) (𝑒 & , ℓ & ) figure 3: the examples of data-flow paths in figure 1. e 9 and e 12 are the function call expressions at lines 9 and 12, respectively. ℓ n indicates the line n. this work facilitates few-shot cot promptingbased bug detection by mitigating the hallucinations. the overarching idea is to enforce llms to emit a data-flow path as the bug proof and examine its validity. intuitively, data-flow paths illustrate how faulty values are produced, propagated, and utilized by risky operations, leading to observable failures. for example, p 1 in figure 3 depicts the zero-value propagation from the return value of parseint at line 12 to the divisor at line 5 in figure 1 . analogous to how cot helps nlp applications, instructing the model to emit a data-flow path forces it to consider causality intrinsic to the examined program. unlike a natural language explanation, which tends to be flexible and informal, a data-flow path serves as a rigorous certificate of a bug report and can hence be further validated. for instance, a valid data-flow path revealing a dbz bug should start from a (potential) zero value and end at a divisor. if a data-flow path violates the property, such as p 2 and p 3 in figure 3 , the bug report would be a false positive. meanwhile, any contradiction between intermediate data-flow facts and program semantics refutes the validity of the whole path. for example, the data-flow fact (c, ℓ 14 ) → (c, ℓ 13 ) of p 2 violates the control-flow order, while (x, ℓ 1 ) → (x, ℓ 3 ) in p 3 is unreachable due to the zero-value check at line 2. as shown in figure 2 , we present llmsan, a novel bug detection methodology that incorporates a sanitization technique for hallucination mitigation. by offering several examples in the form shown in figure 4 , we obtain the data-flow paths in for each sanitization, we further decouple syntactic properties from semantic ones, with the former verified by parsingbased sanitizers (i.e., type and order sanitizers) and the latter examined by llm-powered sanitizers (i.e., functionality and reachability sanitizers). in the flow sanitization, for example, the order sanitizer checks if any intermediate data-flow fact violates the control-flow order, while the reachability sanitizer checks if a faulty value can be propagated between different lines. notably, each sanitizer validates a basic property upon local snippets, which is more manageable than prompting llms with the whole program for data-flow path validation. also, multiple sanitizers check correlated properties and hence achieve a cross-checking effect. our contributions include: (1) we introduce a new method of llm based bug detection, named llmsan, which supports non-experts in customizing the analysis without compilation by specifying several buggy code snippets as few-shot examples. (2) we propose a novel sanitization technique that effectively mitigates hallucination in bug detection by validating the emitted data-flow paths. ## related work a considerable body of literature demonstrates great successes of llms in program synthesis @xcite , testing @xcite , and repair @xcite . however, only a limited number of works have focused on complex code reasoning tasks, such as program verification @xcite and static bug detection @xcite . several approaches employ cot prompting to generate program invariants @xcite , which can then be verified by a model checker for program verification. similarly, llift generates specifications of library functions using prompting to aid in bug detection @xcite . several other studies enhance the performance of llms in specific code reasoning tasks with trained small models @xcite . this work targets llm-powered bug detection with the support of customization and compilation-free analysis, which is not investigated by previous studies. hallucinations are a common issue of llms in many generative tasks, such as questionanswering @xcite and open-domain text generation @xcite . in addition to general methods like self-consistency @xcite , self-check @xcite , and cot @xcite , researchers have proposed domain-specific methods to address hallucinations. a recent study targets detecting selfcontradictions to reduce hallucinations @xcite . other studies focus on hallucinations in various reasoning tasks, such as applying techniques like formal methods to mathematical word problems @xcite . our study resolves the hallucinations in the bug detection, which involves the validation of sophisticated program properties. ## data-flow paths as bug proofs our work introduces a novel bug detection methodology named llmsan that mitigates the hallucination. as shown in figure 2 , the bug detection is achieved by (1) enforcing the llms to emit dataflow paths via few-shot cot prompting and (2) designing a sanitization pipeline that further validates the emitted data-flow paths for hallucination mitigation. in this section, we introduce the concept of data-flow paths and formalize bug detection that emits data-flow paths as bug proofs. definition 1. (data-flow path) a data-flow path p is a sequence of k value-location pairs (v i , ℓ n i ). each value v i is a program variable or expression defined or used at line n i . a data-flow fact is a pair of adjacent pairs indicating that the value v i at line n i directly affects the value v i+1 at line n i+1 . intuitively, a data-flow path demonstrates the value propagation within a program compactly. in the context of bug detection, a data-flow path from the origin and exposition point of a faulty value signifies the presence of a certain type of bug in the program. as proof of the bug, it can further help developers understand and repair the bug. example 1. in figure 1 , parseint(arg) may evaluate to 0 as arg can be initialized to "0" by external input. the potential zero value is assigned to c at line 12 and eventually reach the divisor at line 5 as c is passed as the argument of the function bar at line 13. hence, p 1 in figure 3 is the proof of a potential dbz bug in figure 1 . noting the power of llms in the code reasoning, we can customize a llm-powered program analyzer using few-shot cot prompting to explore and report data-flow paths for bug detection. formally, we frame the problem of bug detection as follows. definition 2. example 2. to detect dbz bugs in figure 1 , we offer examples in the format shown in figure 4 to showcase how dbz bugs arise. specifically, zero values can be produced by numeric literals, such as 0 and 0.0, and function calls expressions, such as the ones invoking parseint and parsefloat upon unconstrained strings. dbz bugs can occur when the second operand of / or % has zero value. finally, we can obtain several data-flow paths as the proofs of dbz bugs, such as the ones in figure 3 . definition 2 formulates a new paradigm of bug detection. few-shot cot prompting lowers the barrier for developers to customize the analysis and seamlessly supports analyzing programs in various forms, including incomplete code during the development stage. different from explanations in natural language, the data-flow paths offer rigorous proofs of the bugs, facilitating the post-validation of bug reports upon the examined program p . ## llm sanitization for bug detection utilizing data-flow paths as bug proofs, we propose a novel sanitization technique that validates them to mitigate the hallucinations in the bug reports. specifically, validating data-flow paths entails handling two complexities. first, a data-flow path can bypass multiple program values in different functions, making it difficult to validate a long path in a large-sized code snippet. second, the undecidability of the data-flow problem @xcite hinders the full utilization of deterministic algorithms for validation with a correctness guarantee. to address the challenges, we introduce program-property decomposition, which resolves the complexities above from two orthogonal aspects. ## evaluation we implement a prototype of llmsan for java bug detection, which has been released online. utilizing the parsing library tree-sitter @xcite , we implement a light-weight compilationfree static analysis core to support the type sanitizer and order sanitizer. datasets. we choose two benchmarks for evaluation: juliet test suite (juliet test suite, 2024) and taintbench @xcite . first, juliet test suite is a synthetic benchmark, covering typical bug types in common weakness enumeration. considering the resource constraint, we choose five popular bug types shown in settings. we run the four sanitizers independently to quantify their effectiveness. to reduce randomness, we set the temperature to 0 in cot prompting so that we enforce the llms to adopt greedy encoding. to show the effectiveness across diverse llm architectures, we assess llmsan with gpt-3.5-turbo-0125, gpt-4-turbo-preview, gemini-1.0-pro, and claude-3-haiku, respectively. for brevity, we denote them with gpt-3.5, gpt-4, gemini-1.0, and claude-3 in the rest of the paper. baselines. we consider two kinds of baselines shown in ## conclusion this paper introduces llmsan, an innovative bug detection methodology that employs a sanitization technique to mitigate hallucination. based on the program-property decomposition, llmsan utilizes parsing-based sanitizers and llm-powered sanitizers to verify multiple basic syntactic and semantic properties upon small code snippets, ultimately identifying spurious data-flow paths emitted in the few-shot cot prompting. our evaluation shows its promising performance in detecting bugs upon both synthetic benchmark programs and realworld android malware applications. our work lays the foundation for more reliable llm-driven program analysis techniques, encompassing areas such as bug detection, automatic debugging, and program repair.