The Hitchhiker's Guide to Program Analysis: A Journey with Large Language Models
This work addresses software engineering problems for developers by providing an incremental assistive tool to enhance static analysis for bug discovery in real-world codebases.
The paper tackles the challenge of balancing precision and scalability in static analysis for bug detection by developing LLift, an automated framework that uses large language models (LLMs) to assist in identifying use-before-initialization (UBI) bugs. In tests on nearly a thousand potential bugs, LLift achieved 50% precision, identified 13 previously unknown bugs in the Linux kernel, and appeared to have no missing bugs.
Static analysis is a widely used technique in software engineering for identifying and mitigating bugs. However, a significant hurdle lies in achieving a delicate balance between precision and scalability. Large Language Models (LLMs) offer a promising alternative, as recent advances demonstrate remarkable capabilities in comprehending, generating, and even debugging code. Yet, the logic of bugs can be complex and require sophisticated reasoning and a large analysis scope spanning multiple functions. Therefore, at this point, LLMs are better used in an assistive role to complement static analysis. In this paper, we take a deep dive into the open space of LLM-assisted static analysis, using use-before-initialization (UBI) bugs as a case study. To this end, we develop LLift, a fully automated framework that interfaces with both a static analysis tool and an LLM. By carefully designing the framework and the prompts, we are able to overcome a number of challenges, including bug-specific modeling, the large problem scope, the non-deterministic nature of LLMs, etc. Tested in a real-world scenario analyzing nearly a thousand potential UBI bugs produced by static analysis, LLift demonstrates a potent capability, showcasing a reasonable precision (50%) and appearing to have no missing bugs. It even identified 13 previously unknown UBI bugs in the Linux kernel. This research paves the way for new opportunities and methodologies in using LLMs for bug discovery in extensive, real-world datasets.