LLMDFA: Analyzing Dataflow in Code with Large Language Models

I. Answers to Questions

Q1. Comparison with ML-based approaches

Targeting a compilation-free and customizable dataflow analysis, we have conducted a comprehensive survey of existing literature and have not encountered any ML-based approaches that specifically tackle the same problem as our research. The most related work is DeepDFA, which is cited in our paper as [25]. Specifically, DeepDFA introduces abstract dataflow embedding and applies a classification model to the embedding results for bug detection. By jointly training the embedding and classification models upon a large dataset containing targeted bugs, DeepDFA can obtain the capability of detecting the target bugs. Although it enables compilation-free analysis, it requires the training process to be repeated for individual dataflow analysis problems. Also, a large amount of training data may not be available for specific bug types. Hence, the lack of customization support limits the applicability of DeepDFA in real-world scenarios where flexible dataflow analysis requirements are necessary. These differences also prevent us from devising a fair empirical comparison between LLMDFA and DeepDFA.

In our evaluation, we hence choose few-shot CoT prompting as an LLM-based end-to-end solution that has the same assumptions as our technique. We acknowledge the Reviewer UBFi's suggestion to include further discussions on existing machine learning-based approaches in our paper. We will further add more justifications for the baseline choices in the evaluation section and compare LLMDFA with existing ML-based analysis from a methodological standpoint.

Q2. More details of source/sink extractor synthesis

First, as demonstrated in lines 169 and 170 in Section 3.1, we synthesize source/sink extractors for each bug type and apply them to different programs instead of synthesizing extractors for individual programs. If we target a specific bug type, the source/sink extractor synthesis is a one-time effort. The synthesized extractors can be deterministically applied to the target programs without introducing any hallucinations.

Second, manually specifying extractors requires the users to exhibit expert knowledge of compilation infrastructures, such as the tree-sitter parsing framework. Considering the tree-sitter-java supporting the parsing of Java programs, for example, 528 node types correspond to various Java constructs, such as call expressions and method declarations. Besides, these nodes exhibit diverse sets of child nodes. The intricacy of the parsing library poses a challenge for non-experts in manually creating extractors to cater to different analysis requirements.

Third, the impact of source/sink extractor synthesis is demonstrated by our ablation study in Section 4.4. As shown in Figure 8, if we identify sources and sinks with LLMs directly instead of using synthesized extractors, the ablation, namely NoSynExt, yields a much lower precision, recall, and F1 score than full-featured LLMDFA. This indicates that the extractor synthesis enables us to mitigate the hallucinations in the source/sink extraction and eventually significantly improves the performance of the overall analysis. We also offer a concrete example in Appendix A.4.1 as a case study (See Case I) to show the spurious sources identified by LLMs while avoided by the synthesized extractors.

We appreciate Reviewer UBFi's comments on the source/sink extractor synthesis. We will include more discussions in our paper.

Q3. More details of path feasibility validation

The path feasibility is a necessary condition of a dataflow path that may introduce a bug. As shown by the motivating example in Figure 1, the value of x at line 9 can be propagated to the argument z at line 13 and then propagated to the second parameter in the function foo. Furthermore, it is utilized at line 4 as a divisor. Such a dataflow path can be derived by concatenating the summaries of the two functions. However, it does not imply the bug’s existence, as the branch condition at line 3 is violated when the value is equal to 0. This means that we have to check the path feasibility after we concatenate the dataflow summaries obtained in the second stage. We will motivate the path feasibility validation with more explanations.

II. Other Concerns

C1. Dataset Details

Juliet Test Suite is a synthetic benchmark widely used for evaluating static analysis tools. The programs in the benchmark are relatively small. That said, it should be noted that the programs in Juliet Test Suite still exhibit complex features, such as complex path conditions, library function usage, and data structure usage. On the other hand, the programs in TaintBench are all real-world Android malware applications. Therefore, the high performance upon Juliet Test Suite and promising results upon TaintBench demonstrate the potential of LLMDFA in discovering dataflow facts for bug detection.

During the response period, we further extended LLMDFA to support C/C++ and JavaScript analysis and meanwhile evaluated it upon three bug tracks in Juliet Test Suite for C/C++ and SecBench.js [R2]. The latter contains 138 bugs in real-world JavaScript programs, including command injection, taint path, and code injection vulnerabilities. Notably, many of the vulnerabilities have been assigned with CVE IDs due to their significant security impact. The results are shown in Table 9 and Table 10.

The above datasets cover different program domains, programming languages, and bug types. As demonstrated by empirical evaluation results, the satisfactory performance of LLMDFA can show its potential value in analyzing real-world programs in a compilation-free and customizable manner.

C2. Cost of LLMDFA

Please refer to the common concern in the global response.

Answers to Questions

Q1. The costs of the three stages

Please refer to the common concern in the global response.

Q2. The statistics and details of path feasibility validation

In Appendix A.3.2, we demonstrate the detailed statistics of path feasibility validation. In our evaluation, we set the upper bound of the fixing number to three in the script program synthesis. According to Figure 13 (a), 75.20%, 96.43%, and 85.25% of scripts are synthesized using gpt-3.5 without any fixes in the DBZ, XSS, and OSCI detection. After feeding the error messages thrown by the Python interpreter iteratively, 99.39%, 96.43%, and 95.08% script programs can be synthesized within three fixes, respectively. For the remaining cases, which only take up 0.61%, 3.57%, and 4.92%, we leverage LLMs to directly determine whether the path is feasible or not. Similar observations can also be derived from the results when using other LLMs.

We also noticed that not all successfully synthesized scripts encode the path conditions correctly. We have shown three typical examples in Appendix A.4.2. We further investigated all the synthesized cases and found that 78.57%, 88.68%, and 83.65% of synthesized scripts encode the path conditions correctly. As pointed out by the reviewer, complex operations, such as library functions, can cause LLMs to fail to generate precise path conditions.

Lastly, it is worth mentioning that partially correct path encoding may be sufficient to filter out false positive bug reports. For example, the dataflow path for a false positive DBZ bug may not have all the path conditions correctly encoded. However, as long as the guard that checks the divisor not being zero is correctly encoded, Z3 can already rule out the bug report. Several existing studies have also reported and utilized similar observations [R12, R13].

Q3. User Interaction and financial cost

As shown by the workflow in Figure 4, LLMDFA requires the users to provide a bug specification describing the forms of sources and sinks, few-shot examples containing sources and sinks, and ASTs generated by parsers. Then, the whole workflow can be fully automated without any human intervention. Specifically, the user can specify the bug specification and examples with little effort. In DBZ detection, for example, the user only needs to write six lines of the bug specification and five code examples. We asked five undergraduate students who had a background in Java programming to construct the prompts and found that their average time costs were only around five minutes.

In contrast, customizing the bug detection in a traditional compilation-based static analyzer often involves implementations with hundreds and even thousands of lines of code, which requires expert knowledge of compiler infrastructures, such as the LLVM infrastructure. The lack of customization support prevents the wide adoption of existing bug detectors, which is also stated by existing studies [R14].

We also measure the token costs of LLMDFA and further compute its financial costs of detecting different bug types. For more details, please refer to the response to the common concern in the global response.

I. Answers to Questions

Q1. Technical design of dataflow summarization

Many existing techniques, such as Pinpoint [R10] and SVF [R11], can derive dataflow paths deterministically. However, they all require the intermediate representations generated by a successful program compilation. As motivated by Figure 2, we want to fill the gap and establish a compilation-free program analysis. That is why we do not apply existing deterministic techniques and instead leverage LLMs for code semantic interpretation to achieve dataflow summarization.

We uploaded the prompts and responses as supplementary material. The details of dataflow summarization can be found in Listing 5, where the prompt and response of this phase are clearly demonstrated. By specifying a few typical patterns of value propagation, such as assignments and direct uses, we can inspire the LLMs to discover dataflow paths through the few-shot CoT prompting. This process does not require numerous rules specifying the dataflow facts induced by various program constructs, as the LLMs can capture the essence of the relationship between two values due to their exceptional generalization ability in code understanding.

II. Other Concerns

C1.Hallucinations of Path Feasibility Validation

Although the synthesized Z3 scripts may not correctly encode path conditions, we find that 78.57%, 88.68%, and 83.65% of them are correct in the DBZ, XSS, and OSCI detection, respectively. The most common reason for incorrect encoding is complex operations that appear in branch conditions, such as library functions.

Another point we want to make is that partially correct path encoding may be sufficient to filter out false positive bug reports. For example, the dataflow path for a false positive DBZ bug may not have all the path conditions correctly encoded. However, as long as the guard that checks the divisor not being zero is correctly encoded, Z3 can already rule out the bug report. Several existing studies have also reported and utilized similar observations [R12, R13].

C2.External Function Call

Handling external function calls is a classic challenge in static analysis. In our work, LLMDFA validates a dataflow path based on the summaries generated in the second phase. Without the summaries of external functions, it can still discover dataflow paths formed by internal function calls (i.e., the functions available in the code base).

Besides, for commonly used external function calls, such as standard library functions, LLMDFA can potentially understand the dataflow facts induced by their invocations. For example, when analyzing the project samsapo in TaintBench, LLMDFA encounters the following code snippet where the function append is a library function of the class StringBuilder. Due to the lack of its function body in the prompt, LLMDFA cannot summarize the dataflow facts for the callee function append. However, it can derive the dataflow summary from str to stringBuilder, which indicates that the value of the parameter str can propagate to the StringBuilder variable. This benefits from the ability of LLMs in code understanding, especially for the commonly used library functions.

public static Fragment instantiate(Context context, String str, Bundle bundle) {
    ...
    stringBuilder = stringBuilder.append(str);
    ...
}

I. Answers to Questions

Q1. Experiments upon Other Languages

Although we did not claim any contribution of multi-lingual support, it is easy to extend LLMDFA to support other languages due to its compilation-free design. During the rebuttal, we extended it to support C/C++/JavaScript and evaluated it with gpt-3.5 upon the Juliet Test Suite for C/C++ and SecBench.js benchmark [R2]. Due to the limited time, we did not evaluate LLMDFA using the other three LLMs.

The Juliet Test Suite for C/C++ does not contain XSS bugs. Hence, we chose another bug type, namely Absolute Path Traversal (APT), which is a typical security vulnerability in Common Weakness Enumeration. As shown in Table 9, the performance of LLMDFA on C/C++ is equally good as on Java.

SecBench.js includes 138 vulnerabilities in JavaScript packages, covering command injection, taint path, and code injection vulnerabilities, which have been assigned with CVE IDs due to significant security impact. Table 10 shows that our compilation-free analysis upon SecBench.js achieves 92.54% precision and 71.74% recall, which are comparable with the compilation-dependent approach in [R2].

Q2. Migration Details for Other Languages

LLMDFA can be extended to support other languages with low implementation effort. Based on dataflow analysis theory, we only need to construct the control flow graph with corresponding tree-sitter packages and then reuse the current implementation. To migrate Java analysis to C/C++/JavaScript analysis, we changed no more than 100 lines of code. Most of the changes relate to the changes to AST node types and parser initialization.

Q3. Reasons for Not Using Open-Sourced Models

We actually tried to utilize open-sourced models, such as CodeLlama-7b-Instruct-hf. However, these models do not seem to have the capabilities to meet the output constraints in the presence of lengthy prompts. In several rounds of prompting for extractor synthesis, the open-sourced models, such as CodeLlama-7b-Instruct-hf, kept generating the following response without synthesizing the extractors at all.

I will examine the examples and their abstract syntax trees according to the given instructions. I will then generate the extractors to identify desired sources and sinks. Let me start the synthesis.

Similarly, the LLMs are required to generate Yes or No to indicate whether the value of a program variable can depend on the value of another value. However, CodeLlama-7b-Instruct-hf did not explicitly give Yes or No as its answer in several cases. Instead, it even responded, “It is unknown whether the two values are dependent or not.”

Due to the above reasons, we could not specify a fixed grammar to parse the responses. Similar problems were reported in existing works [R3, R4]. Another option is to use ultra-large open-sourced models. However, it requires GPU resources that are beyond our reach. To mitigate the threat of validity of relying on a single closed-source model, we tried to use as many such models as we could.

II. Other Concerns

C1. Hallucinations in Dataflow Summarization

The rows named Summarize in Table 1 show the precision, recall, and F1 score of dataflow summarization. Consider the DBZ detection using gpt-3.5 as an example. 9.05% of identified dataflow summaries are spurious due to the LLM hallucination in the dataflow summarization. Meanwhile, 2.43% of valid dataflow summaries are not identified by the LLMs. In Appendix A.4.3, we also demonstrate the cases of false positives and negatives caused by the hallucinations in dataflow summarization.

C2. Evaluation Subjects

Juliet Test Suite contains 1,850 DBZ, 666 XSS, and 444 OSCI bugs, which are scattered in 3,809, 1,084, and 902 Java files, respectively. The precision, recall, and F1 score of the bug detection are measured upon all these Java files. To measure the performance of the dataflow summarization and path feasibility validation, we have to manually examine the intermediate results. This process would be quite laborious if we checked the intermediate results for all the programs. Hence, we chose 37 programs as the representatives, as the rest of the programs only differ from the selected ones in terms of sources and sinks. We have stated such settings from line 256 to line 259. We will add more justifications to avoid potential confusion.

TaintBench offers rigorous definitions of malicious dataflows, which enable us to write bug specifications and few-shot examples for customization.The bugs in TaintBench are manifested by 53 different source-sink pairs, covering typical buggy patterns of sensitive information leakage. Due to its diverse taint flow forms, TaintBench has been widely used by many research papers published in top-tier conferences in software engineering and security [R5, R6, R7]. We believe choosing this benchmark can provide strong empirical evidence of LLMDFA’s effectiveness in the real world.

We appreciate the reviewer's recommendation of the two works [R2, R8]. However, the benchmarks they used are not suitable for the evaluation during the rebuttal. First, the constructed benchmark in [R8], namely MalRadar, and all the datasets listed by Table 1 in [R8], are currently unavailable or require authentication. Second, the experimental subjects used in [R2] include proprietary projects on LGTM.com and an open-sourced real-world benchmark SecBench.js. We tried our best to extend and evaluate LLMDFA upon SecBench.js during the rebuttal phase. For more evaluation details upon SecBench.js, please also refer to the answer to Q1 as above.

C3. Related Work

Actually, we cited the preprint of the work LLift [R9] as [47]. By inferring how library functions initialize variables with LLMs, LLift detects uninitialized variables in the program. Different from LLMDFA, it still requires a compilation-dependent analyzer as its backend and can only detect uninitialized variables without customization support.

We would like to express our sincere gratitude to all the reviewers for the time and efforts they have devoted during the review and rebuttal stages. In our previous global response and individual responses to each review, we have addressed the main concerns regarding this work. In particular, we have answered every question raised in the reviews. As the interactive rebuttal phase is nearing its end, we humbly request that you provide us with some feedback on our previous responses. If any further clarification or explanation of technical details or experimental data is needed, we will respond and provide it promptly.

Thank you again for your efforts to the review and rebuttal.