LLMBisect: Breaking Barriers in Bug Bisection with A Comparative Analysis Pipeline
Zheng Zhang * , Haonan Li * , Xingyu Li * , Hang Zhang † , Zhiyun Qian * · 2025
Read LLMBisect: Breaking Barriers in Bug Bisection with A Comparative Analysis Pipeline by Zheng Zhang * , Haonan Li * , Xingyu Li * , Hang Zhang † , Zhiyun Qian * (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26086.txt.
Introduction
Zheng Zhang, Haonan Li, Xingyu Li, Hang Zhang, and Zhiyun Qian use large language models to find the commit that introduced a software bug. Bug bisection identifies the bug inducing commit, which sets the range of versions at risk. Older patch based methods assume the bad commit and the fix touch the same functions, lean only on code changes, and use simple heuristics. Commit messages often hold rich clues that they ignore.
Their pipeline, LLMBisect, uses the model ability to read both text and code. It extracts full patch information, compares several candidate commits in context, and narrows the field in stages with logical analysis of the vulnerability. The comparative design is meant to break the barriers that limit earlier tools.
Catalog record
| CREATOR | Zheng Zhang * , Haonan Li * , Xingyu Li * , Hang Zhang † , Zhiyun Qian * |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-26086
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LLMBisect: Breaking Barriers in Bug Bisection with A Comparative Analysis Pipeline Zheng Zhang * , Haonan Li * , Xingyu Li * , Hang Zhang † , Zhiyun Qian * Abstract Bug bisection has been an important security task that aims to understand the range of software versions impacted by a bug, i.e., identifying the commit that introduced the bug. However, traditional patch-based bisection methods are faced with several significant barriers: For example, they assume that the bug-inducing commit (BIC) and the patch commit modify the same functions, which is not always true. They often rely solely on code changes, while the commit message frequently contains a wealth of vulnerability-related information. They are also based on simple heuristics (e.g., assuming the BIC initializes lines deleted in the patch) and lack any logical analysis of the vulnerability. In this paper, we make the observation that Large Language Models (LLMs) are well-positioned to break the barriers of existing solutions, e.g., comprehend both textual data and code in patches and commits. Unlike previous BIC identification approaches, which yield poor results, we propose a comprehensive multi-stage pipeline that leverages LLMs to: (1) fully utilize patch information, (2) compare multiple candidate commits in context, and (3) progressively narrow down the candidates through a series of down-selection steps. In our evaluation, we demonstrate that our approach achieves significantly better accuracy than the state-of-the-art solution by more than 38%. Our results further confirm that the comprehensive multi-stage pipeline is essential, as it improves accuracy by 60% over a baseline LLM-based bisection method. I Introduction N-day vulnerabilities are known security flaws that are often not fixed in a timely manner due to complex dependency chains and limited maintenance resources [ 18 ] . The widespread reuse of open-source projects exacerbates this problem, as there are usually multiple downstream distributions maintained by different parties in the ecosystem [ 53 ] , making it difficult to apply upstream security patches on time across all distributions. Research has shown the popularity and severity of this problem in critical open-source projects such as Linux [ 32 ] and Android [ 53 ] , potentially affecting billions of users. The information of affected software versions of a specific vulnerability is crucial for N-day vulnerability mitigation. To obtain such information, it is necessary to locate the commit introducing the vulnerability ( i.e., bug-inducing commit, or BIC ) — an essential task known as bug bisection . In this paper, we align with previous studies [ 52 ] and define a BIC as a commit that introduces a software bug into a program. It is possible for multiple commits to contribute to the bug, with the final commit making the bug triggerable. In such cases, we consider the final commit as the BIC , as it marks the point when the vulnerability is considered to exist. Automated bug bisection can significantly speed up the bug-fixing process in downstreams ( e.g., 2.23x on average for Google’s codebase, according to a previous study [7]), however, achieving a high accuracy remains challenging. Consequently, public information of vulnerable versions ( e.g., in NVD database [ 5 ] ) is usually incomplete or inaccurate, as shown in previous studies [ 12 , 49 , 24 ] . Existing automatic bug bisection approaches can be classified into several categories, each with its own significant limitations: (1) PoC-Based. Directly or symbolically execute the PoC (Proof-of-Concept) against each software version to test whether the vulnerability can be triggered. [ 21 , 52 ] Though straightforward, this approach suffers from limited availability of vulnerability PoCs. Furthermore, direct PoC execution [ 21 ] often fails due to subtle variations across software versions, resulting in low accuracy [ 6 ] , while symbolic analysis [ 52 ] is known to be expensive, and only supports limited bug types ( e.g., use-after-free, out-of-bounds memory access). (2) Bug Report-Based. These approaches first collect available bug reports and then identify possible BICs by their “relevance to the bug” [ 11 , 46 , 14 ] , with simplified assumptions such as “a BIC should touch the code where the failure happens”. Similar to PoCs, detailed bug reports are often not available. Moreover, the simplified assumptions/heuristics may not hold in reality, reducing the accuracy, e.g., Fonte’s [ 11 ] accuracy drops to 36% when N=1 in its top-N ranking algorithm. (3) Patch-Based. Being the most widely used, these approaches statically analyze the bug-fix commit (usually available for vulnerabilities in open-source projects) to “infer” the bug-inducing commit in the commit history. Existing techniques in this category [ 39 , 13 , 26 , 48 , 54 , 47 ] generally rely on manually developed, hardcoded, and thus inherently imprecise heuristics. For example, one common one is to treat the commit that introduces one or more lines deleted by the bug-fix as the bug-inducing commit; however, there are many situations where the bug-inducing commit and the fix commit do not intersect. For example, a patch can add an additional security check before the original vulnerable code (without removing any existing lines of code), potentially in a different function, or the deleted lines in the bug-fix are irrelevant. Another significant shortcoming is that existing approaches usually only analyze the structured code changes in the bug-fix patches, while unable to take any advantage of the commit messages in the unstructured natural language form. However, commit messages often contain rich and valuable information that can boost the bug bisection performance ( e.g., hints on the vulnerability root causes). In this paper, we target patch-based bisection because it is the most widely applicable scenario — not all bugs come with PoCs or crash reports. We specifically have three goals: i) support all types of patches and vulnerabilities, ii) utilize full patch information including both code changes and commit messages, and iii) go beyond the simple hardcoded heuristics and make accurate decisions based on analysis of the vulnerability logic. To achieve these goals, we propose LLMBisect , an LLM-powered highly accurate bug-bisection solution. Our core insight is that LLMs are capable of understanding both code and natural languages, extracting useful information for bug-bisection. Recent LLM models ( e.g., OpenAI o1) also show impressive abilities in code reasoning. Though promising, we find several obstacles to the direct application of LLMs. First, LLMs tend to produce excessive false positives , aggressively and incorrectly labeling commits as bug-inducing. Second, LLMs suffer from self-consistency issues, yielding conflicting decisions across multiple runs. Finally, the cost of using LLMs on large-scale software is prohibitive: modern projects often contain tens of thousands of commits, and processing each one naively can lead to substantial token consumption and increased time and costs. On the positive side, we observe that LLMs excel at comparative assessment, accurately selecting the true BIC from a small pool of candidates. To exploit this strength, we design a multi-step filtering pipeline that leverages LLMs’ comparative reasoning ability. First, we perform coarse-grained filtering to extract candidate BICs at scale (§ III-C ), using lightweight heuristics such as code changes and commit-message keywords. This step is inexpensive and efficient, yet it substantially narrows the search space for subsequent stages. Next, we apply fine-grained filtering in a multi-round, comparative fashion, ensuring that the LLM evaluates