这篇文章提出了一种通过分析问答网站（如Stack Overflow）自动修复重复崩溃错误的方法。其核心思路是：

提取崩溃信息：从崩溃跟踪（Crash Trace）中提取关键信息（如异常类型和错误描述），生成搜索查询。
搜索问答页面：通过搜索引擎获取相关问答页面，提取其中的代码片段。
生成修复脚本：对比问答页面中的错误代码和修复代码，生成代码修改脚本（Edit Script）。
应用到目标代码：将修复脚本适配到目标项目代码中，生成补丁。
过滤与验证：通过编译检查过滤无效补丁，返回最优修复方案。

该方法全自动化，避免了复杂的人工干预，特别适用于依赖框架（如Android）的重复崩溃错误修复。实验表明，该方法在真实世界的Android崩溃案例中表现优异，能够有效补充现有自动修复技术的不足。

文章简介

这篇题为《通过分析问答网站修复重复崩溃错误》的论文由北京大学高可信软件技术教育部重点实验室团队发表于2015年IEEE/ACM国际自动化软件工程会议。文章提出了一种全自动方法，通过分析问答网站（如Stack Overflow）中的讨论内容，提取修复模式并生成代码补丁，以解决软件系统中重复出现的崩溃错误（Recurring Crash Bugs）。该方法在真实世界的Android应用崩溃案例中验证了其有效性，能够补充现有自动修复技术的不足。

技术方案详解

核心思想

重复崩溃错误通常源于对框架（如Android）的误用（例如未正确初始化对象）。由于开发者常通过问答网站寻求解决方案，这些网站中积累了大量针对相同问题的修复代码片段。本文方法的核心是自动化挖掘问答网站中的修复模式，并将其适配到目标项目代码中。

技术流程

方法分为四个主要步骤，流程如下：

1. 问答页面提取（Q&A Page Extraction）

输入：崩溃跟踪（Crash Trace，包含异常类型、错误信息、调用栈等）。
关键词生成：从崩溃跟踪的首行提取关键信息（如异常类型和错误描述），过滤项目特定信息（如类名、包名），生成搜索查询。
- 例如，将 com.vaguehope.onosendai.update.AlarmReceiver 替换为通用关键词，构造查询：
  java.lang.RuntimeException: Unable to start receiver ... IntentReceiver components are not allowed to register to receive intents。
搜索与排序：通过搜索引擎（如Google）获取相关问答页面，按相关性排序。

2. 编辑脚本提取（Edit Script Extraction）

从问答页面中提取“错误代码-修复代码对”，并生成代码修改脚本（Edit Script）：

代码片段提取：通过HTML标签（如<code>）提取问答页面中的代码片段。
代码对匹配：
- 类型1：同一回答中包含多个代码片段（通过关键词如“instead of”区分错误和修复代码）。
- 类型2：问题中的代码（错误）与回答中的代码（修复）配对。
代码精简：基于文本相似度（编辑距离）和结构相似度（AST叶子节点重合率）过滤无关代码，保留关键修改部分。
- 例如，将多行代码精简为仅含关键修改的代码对：
  context.registerReceiver(...) → context.getApplicationContext().registerReceiver(...)。
AST差异分析：使用工具GumTree对比错误代码和修复代码的抽象语法树（AST），生成编辑脚本（如添加、删除、移动节点）。
- 针对变量重命名或位置变化，引入replace和copy操作，提升脚本的通用性。

3. 补丁生成（Patch Generation）

将编辑脚本适配到目标项目代码：

定位故障代码：结合崩溃跟踪的调用栈和代码相似性分析，确定目标文件中可能的故障位置。
编辑脚本适配：通过AST映射将问答页面中的编辑操作转化为目标代码的修改操作。
- 例如，将context节点的父节点替换为getApplicationContext()。
多补丁生成：为每个故障位置生成多个候选补丁，按问答页面相关性和代码相似性排序。

4. 补丁过滤（Patch Filtering）

合并等效补丁：通过AST结构对比去除重复补丁。
编译检查：过滤导致编译失败的补丁。
结果输出：返回排名最高的有效补丁（实验中设定k=1）。

实验与评估

数据集：从GitHub选取24个真实的Android崩溃错误（涉及不同项目规模，代码行数从406到93k）。
结果：
- 有效性：成功修复10个错误，其中7个补丁正确（3个与开发者手动修复完全一致）。
- 效率：平均每个错误处理时间为62秒，编译阶段占68.5%。
- 互补性：与GenProg、PAR等方法修复的缺陷类型不同，可补充现有技术。

贡献与挑战

主要贡献：
1. 首个基于互联网资源的自动程序修复方法，利用问答网站中的众包知识。
2. 轻量级分析：避免复杂自然语言处理，聚焦代码片段与AST差异。
3. 实际应用价值：在Android等框架的重复崩溃场景中表现优异。
挑战与改进方向：
- 依赖问答网站中是否存在相关解决方案。
- 复杂代码上下文（如变量重命名）可能导致补丁生成失败。
- 未来可结合测试用例增强补丁验证，或扩展至更多编程语言和错误类型。

总结

该方法通过自动化挖掘开发者社区知识，为重复崩溃错误提供了高效、低成本的修复方案，推动了自动化软件维护技术的发展。其核心创新在于将众包智慧转化为结构化修复脚本，为依赖框架的软件开发提供了新思路。

计算相似度

在这篇文章中，相似度计算是生成补丁的关键步骤之一，主要用于代码精简和目标代码定位。相似度计算分为文本相似度和结构相似度两部分，分别从代码的文本内容和语法结构两个维度进行评估。以下是详细的相似度计算方法：

1. 文本相似度（Text Similarity）

目标：衡量两段代码在文本内容上的相似程度。
计算方法：基于编辑距离（Edit Distance），即从一段代码转换为另一段代码所需的最少编辑操作次数（如插入、删除、替换字符）。
公式：

$\text{Sim(Text)} = 1 - \frac{\text{edit distance}}{\sqrt{\text{len\_buggy} \times \text{len\_fixed}}$

edit distance：两段代码之间的编辑距离。
len_buggy：错误代码的长度（字符数）。
len_fixed：修复代码的长度（字符数）。

解释：
- 编辑距离越小，文本相似度越高。
- 公式中的分母用于归一化，避免长代码对相似度的影响。

示例：

错误代码：context.registerReceiver(...);（长度：30）
修复代码：context.getApplicationContext().registerReceiver(...);（长度：45）
编辑距离：15（需要插入getApplicationContext()）
文本相似度：

$\text{Sim(Text)} = 1 - \frac{15}{\sqrt{30 \times 45}} \approx 0.59$

2. 结构相似度（Structure Similarity）

目标：衡量两段代码在语法结构上的相似程度。
计算方法：基于抽象语法树（AST）的叶子节点重合率。
步骤：
1. 解析为AST：将错误代码和修复代码分别解析为AST。
2. 提取叶子节点：AST的叶子节点通常表示变量名、方法名、字面量等具体代码元素。
3. 计算重合率：
  - num_common：两段代码AST中相同的叶子节点数量。
  - num_total：两段代码AST中所有叶子节点的总数。
  - 公式：

$\text{Sim(Structure)} = \frac{\text{num\_common}}{\text{num\_total}}$

解释：
- 重合率越高，结构相似度越高。
- 结构相似度能够捕捉代码的语法特征，避免文本相似度对变量名变化的敏感。

示例：

错误代码的AST叶子节点：[context, registerReceiver, null, IntentFilter]
修复代码的AST叶子节点：[context, getApplicationContext, registerReceiver, null, IntentFilter]
num_common：4（context, registerReceiver, null, IntentFilter）
num_total：5
结构相似度：

$\text{Sim(Structure)} = \frac{4}{5} = 0.8$

3. 综合相似度

目标：结合文本相似度和结构相似度，综合评估两段代码的相似性。
方法：
- 分别计算文本相似度和结构相似度。
- 根据预设阈值（实验中文本相似度阈值为0.8，结构相似度阈值为0.3）过滤低相似度部分。
- 保留高相似度的代码片段用于后续分析。

示例：

文本相似度：0.59（低于阈值0.8，过滤）
结构相似度：0.8（高于阈值0.3，保留）
结果：保留该代码片段用于生成编辑脚本。

4. 在目标代码定位中的应用

目标：在目标项目中定位与错误代码相似的部分。
步骤：
1. 提取目标代码片段：根据崩溃跟踪的调用栈，提取目标文件中的代码片段。
2. 计算相似度：对每个目标代码片段，计算其与错误代码的文本相似度和结构相似度。
3. 排序与筛选：根据相似度得分排序，保留高相似度的代码片段作为候选故障位置。

示例：

目标代码片段：BatteryHelper.level(context);
错误代码片段：context.registerReceiver(...);
文本相似度：0.2（低）
结构相似度：0.5（高）
结果：保留该目标代码片段，作为候选故障位置。

总结

相似度计算通过文本相似度和结构相似度两个维度，评估代码片段之间的相似性：

文本相似度：基于编辑距离，衡量代码的文本内容相似性。
结构相似度：基于AST叶子节点重合率，衡量代码的语法结构相似性。
综合应用：用于代码精简和目标代码定位，确保生成的补丁准确有效。

这种方法能够有效处理代码中的变量名变化、位置调整等问题，为自动修复重复崩溃错误提供了可靠的基础。

处理变量名不同问题

在处理变量名不同的情况时，这篇文章通过AST（抽象语法树）映射和扩展编辑操作来解决。以下是详细的处理方法：

1. AST映射（AST Mapping）

目标：将错误代码的AST与修复代码的AST进行节点映射，识别出变量名的对应关系。
工具：使用GumTree工具进行AST映射。
步骤：
1. 解析为AST：将错误代码和修复代码分别解析为AST。
2. 节点匹配：通过GumTree算法匹配两个AST中的节点，识别出变量名的映射关系。
3. 处理未匹配节点：对于未匹配的节点，进一步分析其上下文，判断是否为变量名变化。

示例：

错误代码：context.registerReceiver(...);
修复代码：appContext.registerReceiver(...);
AST映射结果：
- context（错误代码） ↔ appContext（修复代码）

2. 扩展编辑操作（Extended Edit Operations）

目标：在生成编辑脚本时，处理变量名不同的情况。
扩展操作：
- replace操作：用于处理变量名变化。
  - 定义：replace(tn, tp, i)，将节点tp替换为节点tn。
  - 适用场景：当变量名发生变化，但语法结构相似时。
- copy操作：用于复制已有变量名。
  - 定义：copy(tn, tp, i, t)，将节点t复制为节点tn，并插入到节点tp的第i个子节点位置。
  - 适用场景：当修复代码中引入了新的变量名，但目标代码中已有相似变量时。

示例：

错误代码：context.registerReceiver(...);
修复代码：appContext.registerReceiver(...);
编辑脚本：
1. replace(appContext, context)：将context替换为appContext。

3. 在目标代码中适配变量名

目标：将修复代码中的变量名适配到目标代码的上下文中。
步骤：
1. AST映射：将错误代码的AST（buggyAST）与目标代码的AST（srcAST）进行节点映射。
2. 变量名替换：根据映射关系，将修复代码中的变量名替换为目标代码中的对应变量名。
3. 生成补丁：将修改后的AST转换回源代码，生成补丁。

示例：

目标代码：BatteryHelper.level(context);
修复代码：appContext.registerReceiver(...);
AST映射结果：
- context（目标代码） ↔ appContext（修复代码）
生成补丁：BatteryHelper.level(context);（变量名已适配）

4. 处理复杂变量名变化

场景：当变量名变化涉及多个变量或复杂表达式时。
方法：
1. 上下文分析：通过AST的父节点和子节点信息，分析变量名的上下文。
2. 多步替换：分步骤替换变量名，确保语法正确。
3. 编译检查：通过编译检查验证补丁的正确性。

示例：

目标代码：BatteryHelper.level(context, batteryLevel);
修复代码：appContext.registerReceiver(receiver, filter);
处理步骤：
1. 替换context为appContext。
2. 替换batteryLevel为receiver。
3. 添加filter参数。
生成补丁：BatteryHelper.level(appContext, receiver);