💻 computer science

Efficient Prime Paths Generation

本文提出了一种高效的流式算法，用于在有向图中生成基本路径，该方法通过利用强连通分量来约束搜索空间并尽早剪枝无效路径，从而在真实世界的控制流图上优于现有的基于枚举的方法。

原作者： Jakub Zelek, Jakub Ruszil, Adam Roman, Artur Polański

发布于 2026-04-27

📖 1 分钟阅读☕ 轻松阅读

原作者： Jakub Zelek, Jakub Ruszil, Adam Roman, Artur Polański

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一名侦探，试图绘制一名旅行者穿越一座庞大而曲折的城市时可能采取的所有路线。这座城市是一个计算机程序，街道是代码行，而路口则是决策点（例如“如果发生这种情况，向左走；如果发生那种情况，向右走”）。

你的目标不仅仅是找到任何一条路线，而是要找到“主路径”。

什么是主路径？

将主路径想象为一段独特且不重复的旅程，任何延伸都会迫使旅行者访问他们已经去过的地方。

如果你能在行程的起点或终点再增加一个街区而不形成环路，那么它还不是“主”路径。
主路径是你被迫停止或自我循环之前，所能采取的最长的独特旅程。

在软件测试中，找到这些路径至关重要，因为它们代表了程序中最复杂、最有意义的事件序列。如果你测试了这些路径，你就很可能已经测试了所有重要的内容。

问题：城市太大了

问题在于，在复杂的城市（现实世界的软件程序）中，这些独特路线的数量可能是天文数字。这不仅仅是成千上万条，甚至可能达到数百万或数十亿条。

以前寻找这些路径的方法，就像是试图写下城市中每一条可能的步行路线，无论它们多么荒谬或短暂，然后划掉那些不是“主”路径的路线。

旧方法：“让我们列出从 A 到 Z 的每一条步行路线。哦，这条路线绕回来了？划掉它。哦，这条路线太短了？划掉它。”
结果：你花费所有时间写下糟糕的列表并将其划掉，在甚至走完前几个街区之前，就耗尽了纸张（内存）和时间。

新解决方案：“智能地图”

本文的作者（雅盖隆大学的 Jakub Zelek 及其团队）发明了一种导航这座城市的新技术。他们不是列出所有内容然后进行过滤，而是构建了一个智能地图，仅从起点显示有效的路线。

以下是他们新方法的工作原理，使用了一些比喻：

1. 社区（强连通分量）

想象这座城市被划分为不同的社区。在某些社区内，你可以无限期地绕圈行走（这些被称为强连通分量或 SCC）。在社区之间，道路是单向的；你无法回头。

洞察：作者们意识到，“主路径”与这些社区有着非常特定的关系。一条路径要么完全停留在一个社区内（形成环路），要么按顺序穿过一系列社区而从不返回。
优势：他们不是同时查看整个城市，而是将问题分解。他们查看“社区地图”（凝聚图），以确定哪些社区可以连接，而不是迷失在单条街道中。

2. “死胡同”探测器（剪枝）

这是他们技巧中最强大的部分。想象你正在走一条路径，从社区 A 踏入社区 B。

旧方法：你继续行走，记下整条路径，然后才意识到：“哦不，我本可以在社区 A 向左转就能到达这里。这条路径不是独特的。”于是你扔掉整份列表。
新方法：就在你从 A 踏入 B 的那一刻，算法会检查一条规则：“我能否从之前的某个位置回到我现在所在的地方？”
- 如果答案是是，算法会立即停止该路径。它会说：“这条路线注定失败；甚至不要走完它。”
- 它在完整写下整个分支之前，就切断了整个可能性分支。这就像 GPS 在刚看到交通堵塞时立即为你重新规划路线，而不是开进去后再掉头。

3. 流式交付

因为他们如此早地切断了坏路径，所以不需要在计算机内存中存储数百万条路线。相反，他们像流媒体服务一样运作。

他们找到一条有效的主路径，交给你，找到下一条，再交给你，以此类推。
他们不需要等到找到所有路径才给你第一条。这使得过程极其快速且节省内存。

结果：与时间的赛跑

该团队使用真实的软件项目（如 GitHub 上流行的 C++ 和 Python 代码）将他们的方法与旧方法进行了测试。

旧方法：对于较大的程序，旧方法往往完全放弃（超时）或花费数小时才能完成。它们耗尽了内存，或者在试图划掉坏路径时陷入停滞。
新方法：它在几秒钟或几分钟内完成了相同的任务。即使对于最大、最复杂的程序，它也能保持稳定的速度，逐条交付路径而不会减速。

为什么这很重要

在软件测试领域，我们希望确保程序不会崩溃。主路径覆盖是这方面的黄金标准。然而，由于找到这些路径非常困难，许多测试人员跳过了它，或者使用了较弱、不够彻底的方法。

这篇论文提供了一个快速、高效的引擎，使得在现实世界的软件中找到这些复杂路径变得切实可行。它将一项以前对大型程序来说不可能完成的任务变成了常规任务，确保软件可以得到更彻底的测试，而无需等待数天才能获得结果。

简而言之：他们不再试图列出城市中的每一条可能的步行路线，而是开始构建一个智能指南，仅向你展示独特且不重复的游览路线，在你迈出第一步之前就切断了死胡同。

以下是 Jakub Zelek 等人论文《Efficient Prime Paths Generation》（高效素路径生成）的详细技术总结。

1. 问题陈述

素路径覆盖（Prime Path Coverage, PPC） 是白盒测试中使用的一种严格的结构化测试标准。所谓“素路径”，定义为控制流图（CFG）中的简单路径或简单环，且该路径无法在不重复顶点的情况下进行向前或向后扩展。PPC 非常有效，因为它涵盖了其他标准（如边对覆盖和所有 DU 路径覆盖），并能捕捉长程执行依赖关系。

然而，生成完整的素路径集合在计算上极具挑战性：

指数级复杂度：即使对于有向无环图（DAG），素路径的数量也可能随图的大小呈指数级增长。
现有方法的低效性：当前方法通常枚举所有简单路径，然后过滤以找出素路径。这导致了巨大的内存开销和计算浪费，因为大多数简单路径并非素路径。
可扩展性问题：现有算法（如 Ammann-Offutt、Fazli 算法）往往无法在具有复杂控制流的现实世界软件项目中完成，经常遭遇超时或内存耗尽。

2. 方法论

作者提出了一种新颖的算法，避免了枚举所有简单路径。相反，它基于强连通分量（SCCs） 对素路径进行结构特征描述，并结合带有早期剪枝的流式方法。

关键理论洞察

SCC 分解：
- 每个简单环都完全包含在单个 SCC 内。
- 非环素路径在图的凝聚图（一个每个节点代表一个 SCC 的 DAG）中遍历一系列 SCC。
端点的必要条件：
- 作者推导出了任何素路径的起点和终点必须满足的非平凡必要条件（ $V_{start}$ 和 $V_{end}$ ）。这些条件涉及相对于 SCC 的入边/出边的集合基数。通过在遍历开始前过滤掉无效的起点/终点，这极大地减少了搜索空间。
归约为环枚举：
- 寻找不可扩展简单路径的问题被归约为在增强图（$Ex(G, v)$）中寻找简单环的问题。该图通过添加一个虚拟节点构建，该节点连接到特定的起点和所有有效的终点。
通过 SCC 边界剪枝：
- 在遍历过程中，如果一条路径从一个 SCC 跨越到另一个 SCC，算法会检查当前部分路径是否“可向后扩展”。如果是，则该路径不可能是素路径，该搜索分支的整个子树将立即被丢弃。

算法

提出的解决方案（算法 1）分为两个主要阶段：

简单环：使用修改后的Johnson 算法独立枚举每个 SCC 内的所有简单环。
不可扩展路径：
- 遍历有效的起点（ $V_{start}$ ）。
- 为每个起点构建增强图 $Ex(G, v)$。
- 在增强图上运行Johnson 风格的遍历以查找环。
- 将这些环转换回原始图中的路径，移除虚拟节点。
- 应用早期剪枝：如果一条路径离开当前 SCC 并被检测为可向后扩展，则递归立即停止。

3. 主要贡献

结构特征描述：建立了一个新的理论框架，通过 SCC 和凝聚图定义素路径，从而得出路径端点的必要条件。
不可解性证明：证明了除非 $P=NP$，否则以多项式延迟（按特定顺序）枚举不可扩展简单路径是不可能的，从而证明了需要启发式剪枝和流式处理，而非严格的多项式延迟保证。
流式算法：设计了一种算法，能够增量生成素路径而无需存储所有简单路径的完整集合，显著降低了内存使用量。
早期剪枝：引入了一种机制，在跨越 SCC 边界的瞬间丢弃不可行的搜索子树，而不是在路径完成后进行过滤。
可并行性：该方法天然地可在不同的 SCC 和起点之间并行化，不同于以前受限于 SCC 结构的方法。
泛化性：该框架可被调整以生成其他覆盖标准，例如简单路径覆盖或 e-无环路径覆盖。

4. 实验结果

作者将他们的方法与 Ammann-Offutt 算法、改进的 Ammann-Offutt 版本以及 Fazli 的组合方法进行了评估。

数据集：从 C++ 和 Python 开源项目（GitHub 前 1,000 个仓库）中提取的 120,314 个真实世界控制流图（CFG）。
真实世界 CFG 上的性能：
- 超时：竞争方法在大多数较大的图上无法完成（例如，Fazli 在 15–50 个节点的图上超时率高达 98%）。所提出的方法在所有规模类别中零超时。
- 加速比：在 15–50 个节点的图上，所提出的方法的中位速度比改进的 Ammann-Offutt 方法快约 189 倍。在最大的图（201–1000 个节点）上，竞争对手完全超时，而新方法平均在 3 分钟内完成。
- 内存：所提出的方法使用的内存显著更少（通常 <1 MB），而竞争对手需要数百 MB 甚至 GB 的内存。
指数级案例（ $D_n$ 图）：在旨在拥有指数级多素路径的合成 DAG 上，新方法在时间和内存方面始终优于其他方法。
输出稳定性：对输出间隔延迟的分析显示了稳定的行为，方差较低（大多数情况下变异系数 < 0.15），表明算法稳定地产生结果，而非呈爆发式输出。

5. 意义

实际适用性：这是第一种能够在合理的时间和内存限制内为大型现实世界软件系统生成所有素路径的方法。以前的方法在理论上虽然合理，但在复杂的工业代码中实际上不可用。
测试效率：通过实现全面素路径集的生成，该工具允许进行更严格的白盒测试，有可能发现更简单的覆盖标准所遗漏的复杂交互链中的故障。
理论进步：本文通过利用结构属性（SCCs）来绕过典型软件图中的最坏情况复杂度，弥合了理论图枚举限制与实际算法设计之间的差距。
开源：该实现已在 Diblob 包中提供，促进了软件测试社区的采用。

总之，本文在结构化测试方面取得了突破，将素路径生成问题从暴力枚举任务转变为受约束的流式搜索问题，使得针对现代复杂软件系统的高覆盖率测试成为可能。