技术摘要：大语言模型能否对复杂的执行路径进行推理？关于 Python 的一项实证研究

问题陈述

执行路径推理是软件工程任务（如测试、缺陷查找和验证）中的一项基本能力。传统上，这通过符号执行来实现，即使用 SMT 求解器来确定路径约束的可满足性。然而，现有的基于 SMT 的方法在处理复杂数据结构、外部 API 调用以及像 Python 这样具有高度灵活语法的动态类型语言时显得力不从心。因此，目前缺乏广泛采用且成熟的 Python 符号执行工具。虽然大语言模型（LLMs）在代码生成和理解方面展现出了强大的能力，但它们是否能在不依赖传统约束求解器的情况下，有效地对复杂执行路径进行推理，仍然是一个开放性问题。

研究方法

作者对 LLMs 在 Python 执行路径推理方面的有效性进行了系统的实证研究。该研究侧重于两个主要任务：测试用例生成（生成任务）和路径分类（分类任务）。

基准测试与数据构建

1. 竞赛级测试用例生成： 利用 TestEval 基准测试（包含 210 个具有高圈复杂度、来自 LeetCode 的 Python 程序），作者通过运行示例测试用例提取了 509 条执行路径。他们修改了 Python trace 库以捕获分支条件和循环迭代次数，创建了一个平均包含 233 个语句和 103 个分支语句的路径数据集。
2. 路径分类： 利用来自 Google 运行时错误数据集（衍生自 CodeNet）的数据，作者筛选出了存在“除以零”错误的程序。他们采用控制流图（CFG）遍历算法提取了可行路径和不可行路径。该数据集被手动标注为三类：有效（Valid）（可满足，无 Bug）、无效（Invalid）（不可行）以及 除零（ZeroDivision）（在触发 Bug 前有效）。这最终产生了 2,010 条执行路径。
3. 真实世界仓库测试： 利用 TestGenEval 数据集（11 个公开 Python 仓库），作者识别了 256 个部分覆盖的函数。他们提取了执行路径，以评估提供路径信息是否能提高包含外部依赖项的真实软件中的测试覆盖率。

实验设置

研究评估了 14 个 LLM，将其分为非推理型 LLM（例如 GPT-4.1 系列、DeepSeek-V3、Qwen3、Gemma3）和大型推理模型（LRMs）（例如 o3-mini、o4-mini、DeepSeek-R1、Qwen3-thinking）。

• 测试用例生成： 提示 LLM 生成能够重现给定执行路径的测试输入。衡量指标包括路径准确率（精确匹配）和节点准确率（前缀匹配）。
• 路径分类： 提示 LLM 将路径分类为有效、无效或除零。衡量指标包括准确率、平衡准确率和宏 F1 分数。
• 真实世界评估： 提示 LLM 生成覆盖特定路径的单元测试。衡量指标包括 Pass@1（测试可执行性）和行覆盖率。

关键结果

1. 测试用例生成 (RQ1)

• 性能： 最先进的 LLM，特别是 LRMs，展示了为复杂执行路径生成正确测试用例的能力。表现最好的模型 o4-mini 在极具挑战性的竞赛级基准测试中达到了 65.6% 的路径准确率。
• 推理型 vs. 非推理型： LRMs 一致优于非推理型 LLMs。这种优势在中等长度路径（10–50 个分支条件）上最为显著。对于极长路径（>50 个分支），所有模型的性能均有所下降。
• 消融研究： 移除显式的循环迭代计数器或分支条件标签会导致性能大幅下降，这表明 LLMs 高度依赖这些显式的符号状态来追踪执行流。
• 错误分析： 对 DeepSeek-R1 推理轨迹（CoT）的人类评估显示，最常见的失败模式是误解 API（尤其是复杂数据结构）和循环/三元运算符逻辑，而非纯粹的逻辑演绎错误。

2. 路径分类 (RQ2)

• 性能： LLMs 在路径分类方面的准确率最高可达 82.9%。Qwen3-235B 是表现最好的模型，成功识别了数据集中所有的 120 个除零 Bug。
• LRM 的局限性： 与生成任务相反，LRMs 在分类任务中并不总能优于非推理型模型。事实上，某些 LRMs（如 DeepSeek-R1、o4-mini）的表现反而较差。
• “过度思考”现象： 研究发现推理思维链（CoT）的长度与分类准确率之间存在负相关关系。LRMs 经常陷入“过度思考”，即过多的推理步骤导致了错误的结论（例如，由于对分支条件的矛盾逻辑，将除零路径误分类为无效路径）。

3. 真实世界仓库 (RQ3)

• 覆盖率提升： 与基准提示相比，向 LLMs 提供执行路径信息一致地提高了真实世界仓库中的测试覆盖率。
• 可执行性瓶颈： 虽然覆盖率有所提高，但 Pass@1 率（生成可执行测试的能力）仍是主要的瓶颈，表现最好的模型也仅达到了 53.7%。
• 模型对等性： 在真实世界场景中，最先进的非推理型 LLMs 展示出了与 LRMs 相当的测试覆盖能力，这表明对于包含大量依赖项的复杂代码，LRMs 特有的“推理”架构相比其在孤立算法问题上的表现，其收益递减。

意义与贡献

本文做出了以下贡献：

1. 首次系统性研究： 针对 LLMs 在动态类型语言 Python 中对执行路径约束进行推理的能力，进行了首次全面的实证研究，而这一领域传统符号执行工具通常难以奏效。
2. 新基准测试： 作者构建了涵盖竞赛级问题和真实世界仓库的新基准，覆盖了测试用例生成、路径可行性分析和缺陷检测等下游任务。
3. 对 LLM 能力的洞察： 研究表明，虽然 LLMs（尤其是 LRMs）可以解决复杂的路径约束，但其有效性取决于具体任务。它们擅长为中等长度路径生成测试输入，但在分类任务中由于“过度思考”而表现挣扎，并且在可靠区分不可行路径方面能力有限。
4. 实际应用意义： 研究结果表明，LLMs 可以作为一种有价值的补充启发式方法，或者作为缺乏成熟工具的语言中符号执行的潜在替代方案。然而，在 API 理解、循环推理以及推理效率（特别是对于开源 LRM）方面仍面临挑战。

局限性与未来方向

作者承认本研究并未采用高级提示技术或微调，而是侧重于预训练模型的固有能力。他们指出，由于推理轨迹较长，开源 LRM 的时间效率目前低于传统的求解器。建议未来的工作重点关注高效的推理策略、带有可验证奖励的强化学习（RLVR），以及将 LLM 与传统符号执行工具相结合以剪枝不可行路径的混合方法。