LLMDFA: Analyzing Dataflow in Code with Large Language Models

Summary

This paper proposes an LLM-based approach for detecting bugs with data flow analysis. The proposed approach LLMDFA consists of three parts: source/sinks extraction, dataflow summarization, and path feasibility validation. LLMDFA allows LLMs to interact with different program analysis tools. The authors conduct experiments on bug detection in both synthetic and real-world datasets.

Strengths

+The authors proposed an interesting approach for solving an important question in program languages. +LLMDFA decomposes bug detection into three steps, which are proven useful for complex data flow reasoning. +Experiments are conducted on both synthetic and real-world datasets.

Weaknesses

-The results on synthetic datasets are very high, maybe the dataset is too easy? -All components in LLMDFA require multiple rounds of try-and-refine. It is better to discuss the cost of multiple-round generation.

Questions

- Most baselines are non-deep-learning approaches. I wonder if there are any deep learning-based approaches previously proposed for similar bug detection tasks? - In my understanding, it is possible to write a single parser to extract the sources/sinks for all programs. What's the advantage in using LLM to generate different parsers for different programs? Also, I'd like to see more discussion on the impact of ASTs in source/sink extraction. - I’m a little confused about how the results of path feasibility validation can lead to the detection of bugs. Can the authors explain in more detail?

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The limitations have been well-discussed.

Summary

The paper proposes LLMDFA, a compilation-free and customizable dataflow analysis, which takes a program and its CFG as input. The authors decompose the problem into several subtasks including Source/Sink Extraction, Dataflow Summarization, and Path feasibility Validation, and introduce some strategies. They evaluate LLMDFA on synthetic programs to detect three representative types of bugs and on real-world Android applications for customized bug detection.

Strengths

+ easy to follow + interesting idea + impressive improvement The presentation is easy to follow and the experiment results are impressive.

Weaknesses

- some designs are not well-motivated - high cost I have some reservations about the efficacy and meaningfulness of employing Z3 for verification, especially considering the preceding processes are generated by LLMs, which might inherently carry some inaccuracies. It seems challenging to ascertain whether the results from the final Z3 verification justify the associated costs, given these potential uncertainties. When Z3 fails to verify, what is the possible fixing mechanism? How to locate the error? Additionally, preparing code for Z3 verification involves intricate steps such as defining data types, data structures, and functions, and then also need to translate constraints into Z3's language. While I appreciate that the authors admit these challenges with illustrative examples shown in the appendix, the results presented in Table 1 are notably impressive. Could this suggest that the dataset primarily comprises simpler structures and operations? It would be enlightening if more detailed results for the specific tasks mentioned could be shared, beyond a general ablation study. Finally, comparing the costs of traditional methods and those involving LLMs directly can be quite complex. Including a more nuanced comparison of human effort and financial implications might provide clearer support for the strengths and contributions of the LLMDFA approach.

Questions

- What is the cost of each part? - How much validation code using Z3 can be successfully generated? - Can the whole procedure be automated? Or how can the user be involved in LLMDFA?

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

The limitation has been discussed.

Summary

This paper presents LLMDFA, an LLM-powered compilation-free and customizable dataflow analysis framework for bug detection. To mitigate LLM hallucination, LLMDFA breaks down the dataflow analysis (DFA) task into multiple subtasks and delegates complex reasoning to specialized external tools. In bug detection evaluations involving synthetic programs and real-world Android applications, LLMDFA achieves a precision of 87.10% and a recall of 80.77% on average. These results outperform existing baselines.

Strengths

1. This paper investigates a promising direction in leveraging LLMs for code dataflow analysis. The motivation and methodology are clearly articulated and well-structured. 2. To mitigate LLM hallucinations, the authors introduce a novel three-stage workflow: In the Source/Sink Extraction and Path Feasibility Validation stages, LLMDFA employs an LLM as a coordinator, delegating the complex analysis to external tools. In the Dataflow Summarization stage, LLMDFA uses a few-shot chain-of-thought (CoT) prompting strategy to align LLMs with program semantics. These approaches effectively reduce the intrinsic hallucinations associated with LLMs. 3. The empirical results demonstrate that LLMDFA significantly outperforms existing baselines, including the classic dataflow analyzer CodeFuseQuery and an end-to-end CoT solution. 4. LLMDFA can be applied to arbitrary programs without the need for compilation.

Weaknesses

1. In the Path Feasibility Validation stage, the LLM's role is to synthesize a Z3 solver script. However, producing a runnable Z3 solver script does not necessarily ensure that the path is feasible, as the generated Z3 constraints may not accurately reflect the actual path conditions. 2. Since LLMDFA does not require compilation, the presence of any unknown external call (e.g., `a = unknown_func(a)`) can terminate the dataflow analysis. This scenario is particularly common in real-world code.

Questions

Based on my best understanding, the dataflow summarization stage generates dataflow paths between sources and sinks. I am curious if any deterministic algorithms could handle this task instead of relying on an LLM. Furthermore, considering the potentially numerous rules involved in forming the paths, could you provide the actual prompt used at this stage?

Rating

6

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

The authors addressed limitations in their work.

Summary

The author proposes a data flow analysis tool based on LLM, named LLMDFA. This tool addresses the LLM hallucination problem by decomposing tasks. The method is divided into three stages: the first stage involves calling and extracting sources and links through LLM-generated scripts; the second stage generates summaries of the data flow; the third stage conducts path analysis using synthesis tools and scripts. The study was validated on the Java programming language and considered four closed-source LLM models. Experimental results show that LLMDFA has high Recall and F1 metrics.

Strengths

- The author explores the effective application of LLM in the field of code analysis. - Utilizes the generative capabilities of LLM to call external programs.

Weaknesses

- The third part is relatively obscure. Although the author attempts to formalize the method of LLM analysis data flow, this expression is difficult for readers lacking a background in code analysis and data flow analysis to understand. - This paper is an application-type article of LLM. The generalizability of the research has not been fully verified, as experiments were only conducted on the Java language, limiting the general applicability of the conclusions. - LLMDFA is still affected by the LLM hallucination problem and may generate incorrect summaries, but the experimental section does not explore the impact of this issue on the method. - The experimental data volume is small, with only 37 programs tested for each type of bug, which may lead to significant bias in the experimental results. It is recommended to verify with a larger dataset to improve the reliability of the conclusions. TaintBench also has only 39 real-world android malware (line 242). The author should verify on a larger dataset to ensure the feasibility of the conclusions. Some datasets can be referenced [1,2]. - The related work section lacks an introduction to the current research progress of LLM in the field of code analysis, such as [3]. **Citation Suggestions:** [1] Yiu Wai Chow, Max Schäfer, Michael Pradel. 2023. "Beware of the Unexpected: Bimodal Taint Analysis." *Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2023)*. ACM, New York, NY, USA, 211–222. https://doi.org/10.1145/3597926.3598050 [2] Liu Wang, Haoyu Wang, Ren He, Ran Tao, Guozhu Meng, Xiapu Luo, Xuanzhe Liu. 2022. "MalRadar: Demystifying Android Malware in the New Era." *Proc. ACM Meas. Anal. Comput. Syst.* 6, 2, Article 40 (June 2022), 27 pages. https://doi.org/10.1145/3530906 [3] Haonan Li, Yu Hao, Yizhuo Zhai, Zhiyun Qian. 2024. "Enhancing Static Analysis for Practical Bug Detection: An LLM-Integrated Approach." *Proc. ACM Program. Lang.* 8, OOPSLA1, Article 111 (April 2024), 26 pages. https://doi.org/10.1145/3649828

Questions

- Your method has so far only been validated on the Java language. Do you have plans to experiment with other programming languages such as Python, C++, etc.? If so, what are the experimental results? - How do you think LLMDFA applies to other programming languages? Does the method need to be adjusted to adapt to different programming environments? - Why not try using open-source models?

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

See Weaknesses

Author-Reviewer discussions (Aug 7 - Aug 13)

Dear Submission7502 reviewers, We appreciate your reviews as we move into the Author-Reviewer discussions phase (Aug 7 - Aug 13). Please read all reviews and author responses carefully. Please address any remaining questions or concerns with the authors and respond to their rebuttal as needed. Authors need time to respond to your messages, so please post your responses as soon as possible, so there is time for back-and-forth discussion with the authors. At a minimum, please acknowledge that you have read the author rebuttal. Based on the material provided, please adjust your scores and reviews as necessary. Dear Submission7502 authors, We appreciate your rebuttal. Please continue the dialogue with the reviewers during this discussion phase. This message and thread are visible to both reviewers and authors. If you need to respond privately, adjust the "Readers" setting accordingly.

Seek feedback on responses

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.