6-测试前沿专题-测试排序与缺陷定位

第1页 — Test Case Prioritization（测试用例排序）

标题： 测试用例排序（Test Case Prioritization）

第2页 — 测试用例排序（定义）

测试用例排序

给定一个初始测试集 $T_{init}$ ，找到满足以下条件的排列 $T \in PT$ ：

$\forall T',\ T' \in PT,\ T' \neq T \Rightarrow f(T) > f(T')$

PT： $T_{init}$ 中所有测试用例的全排列集合
f：目标函数（用于评价排列的优劣）

第3页 — PT 示例

PT：一个例子

$T_{init} = \{t_1, t_2, t_3, t_4, t_5\}$

$PT = \{\{t_1, t_2, t_3, t_4, t_5\},\ \{t_1, t_2, t_3, t_5, t_4\},\ \{t_1, t_2, t_4, t_3, t_5\},\ \ldots\}$

PT 是 $T_{init}$ 中所有测试用例的全部排列组合。

第4页 — 目标函数

目标函数（Objective Function）

测试的最终目的：发现缺陷
测试用例排序的最终目的：尽快发现缺陷
APFD：平均缺陷检测百分比（Average Percent of Faults Detected）

$APFD = 1 - \frac{t_{f_1} + t_{f_2} + \cdots + t_{f_k}}{n \cdot m} + \frac{1}{2m}$

$k$ ：被测程序 $P$ 中包含的缺陷数量
$m$ ：测试用例总数
$t_{f_i}$ ：排序后测试序列 $T$ 中，第一个能暴露缺陷 $i$ 的测试用例的位置

第5页 — APFD 示例

APFD：平均缺陷检测百分比

测试用例	故障/需求覆盖情况（1~10）
A	覆盖 1, 2
B	覆盖 3, 4, 5, 6
C	覆盖 1, 3, 5, 6, 7, 8, 9
D	覆盖 2
E	覆盖 4, 7, 8

按顺序 A → B → C → D → E 执行，100% 缺陷覆盖
APFD = 50%（说明缺陷是在测试过程中期才被发现的）

第6页 — 排序算法

排序算法（Prioritization Algorithms）

同上一页的故障矩阵，目标是提升 APFD。

两种常见的贪心算法：

贪心算法（Greedy）：每次选择覆盖总缺陷数最多的测试用例
- 排序结果：C → B → E → A → D
附加贪心算法（Additional Greedy）：每次选择覆盖尚未被发现的缺陷数最多的用例（去除重复）
- 排序结果：C → E → A → B → D

APFD = ?%（留作思考练习）

第7页 — 复杂度对比

复杂度（Complexity）

技术	说明
测试集缩减（Test Suite Reduction）	（时间复杂度较高）
测试用例排序（Test Case Prioritization）	（相对更高效）

本页通过对比两种技术的复杂度，说明测试用例排序在实际工程中的可行性。

第8页 — 缺陷定位

标题：缺陷定位（Fault Localization）

本页为章节标题页，引出缺陷定位专题。

第9页 — 缺陷定位（概念图）

缺陷定位（Fault Localization）

一个存在缺陷的程序
        ↓
    [测试用例]  → 执行 → [失败（Failure）]
        ↓
[缺陷定位（Fault Localization）]
        ↓
  可疑程序元素（Suspicious program elements）

核心问题：缺陷在哪里？（Where is the fault?）

第10页 — 基于频谱的缺陷定位

基于频谱的缺陷定位（Spectrum-based Fault Localization）

已有大量缺陷定位技术被提出
其中一个重要技术族：基于频谱的缺陷定位（Spectrum-based Fault Localization）
核心思想：使用程序频谱（Program Spectra）——即程序执行过程中行为的表示——来辅助定位缺陷

📖 参考文献：James A. Jones, Mary Jean Harrold, John T. Stasko.《通过测试信息可视化辅助缺陷定位》. ICSE 2002.

由于第11、15、16页主要是图表示例（"An Example"），文字内容较少，我来结合上下文补充说明翻译：

第11页 — 一个示例

标题：一个例子（An Example）

本页为图示页，展示程序代码与测试用例执行情况的对应关系，配合第10页"基于频谱的缺陷定位"概念使用。图中通常包含：各测试用例执行了哪些代码行（覆盖矩阵），以及哪些测试通过/失败。

第12页 — 基于频谱的缺陷定位（核心思想）

基于频谱的缺陷定位

核心直觉：

在失败测试中频繁执行的程序元素，很可能包含缺陷
在通过测试中频繁执行的程序元素，很可能不含缺陷

常用风险评估公式（Risk Formulas）：

Tarantula（蜘蛛）公式等

第13页 — 基于频谱的缺陷定位（变量定义）

基于频谱的缺陷定位

对程序元素 $s$ ，定义以下四个统计量：

符号	含义
$a_{ef}$	执行了 $s$ 的失败测试数量
$a_{nf}$	未执行 $s$ 的失败测试数量
$a_{ep}$	执行了 $s$ 的通过测试数量
$a_{np}$	未执行 $s$ 的通过测试数量

这四个量是计算各类可疑度公式的基础输入。

第14页 — 随堂练习

Quiz（小测验）

已知某程序元素 $s$ 的统计数据如下：

$a_{ef}$	$a_{nf}$	$a_{ep}$	$a_{np}$
1	0	2	3

问： $Susp(s)$ （可疑度）= ？

请根据 Tarantula 等风险公式代入计算。

Tarantula 公式： $Susp(s) = \frac{\dfrac{a_{ef}}{a_{ef}+a_{nf}}}{\dfrac{a_{ef}}{a_{ef}+a_{nf}} + \dfrac{a_{ep}}{a_{ep}+a_{np}}}$

第15页 — 一个示例

标题：一个例子（An Example）

本页为配套图示，展示具体程序的频谱矩阵及各程序元素（如代码行）的可疑度计算结果，通常以表格或高亮代码的形式呈现。

第16页 — 一个示例（续）

标题：一个例子（续）（An Example）

本页继续展示上一页的示例，可能包含不同公式下各代码行的可疑度排名，以及实际缺陷所在位置的对比。

第17页 — 随堂练习：构造新的风险公式

Quiz：构造一个新的风险公式

$a_{ef}$	$a_{nf}$	$a_{ep}$	$a_{np}$
（待填）	（待填）	（待填）	（待填）

问： $Susp(s)$ （可疑度）= ？

本题要求同学自行设计一个合理的风险评估公式，基于 $a_{ef},\ a_{nf},\ a_{ep},\ a_{np}$ 四个输入，输出程序元素的可疑度得分。

第18页 — 缺陷定位的挑战性问题

缺陷定位中的问题（Fault Localization Issues）

三大核心挑战：

偶然正确性（Coincidental Correctness）
- 某个测试本应失败，却因偶然原因通过了，干扰可疑度计算
多缺陷（Multiple Faults）
- 程序中存在多个缺陷时，频谱技术的效果会显著下降
完美调试假设（Perfect Debugger）
- 现有评估通常假设开发者总能精确识别并修复被定位的缺陷，实际并非如此

📖 相关参考文献：

Xie 等人（2013）：频谱缺陷定位风险公式的理论分析

Miao 等人（2013）：基于聚类策略识别偶然正确性

Parnin & Orso（ISSTA 2011）：自动调试技术究竟是否在帮助程序员？