自动驾驶系统中多功能交互故障的自动修复

自动驾驶系统中多功能交互故障的自动修复

摘要

1 引言

自动驾驶系统软件通常由几个功能单元组成，称为自动驾驶系统功能，用于自动执行特定的驾驶任务(例如，自动紧急制动、自动交通标志识别和自动巡航控制)。每个功能随时间连续执行，并从感知层组件接收数据。利用传感器提供的信息，自动驾驶系统的功能独立决定下一时刻汽车的运动。

不同功能做出的决定可能是冲突的。例如，自动巡航控制可以命令汽车加速以跟随领头汽车的速度，同时，自动交通标志识别功能命令汽车停止，因为汽车正在接近具有即将变红的交通灯的十字路口。为了解决冲突，自动驾驶系统应用了集成规则。集成规则本质上是条件语句，用于确定在什么条件下应该优先考虑哪些功能的输出。它们通常由工程师基于他们的领域知识手动定义，并被期望确保安全和期望的汽车操纵。

最近，在文献中已经提出了许多方法来自动修复软件代码中的错误。这些技术的输入是一个有缺陷的程序和一个测试套件，测试套件包含一些期望的程序行为和一些揭示了需要修复的失败的测试用例。故障修复技术反复识别代码中的错误语句(故障定位)，自动修改错误语句(补丁生成)，并检查补丁代码是否通过所有输入测试用例(补丁验证)。为了有效地修复 ADS 集成故障，我们需要一种技术，它除了支持上述三个步骤之外，还需要确保以下目标:

1、修复技术应该定位跨多行代码的故障。

大多数程序修复技术使用基于频谱的技术来定位故障。这些技术依赖于程序中存在单个错误语句的假设，并且如皮尔逊等人所示，它们可能无法识别多语句错误中的所有错误行。正如我们在第 3 节中所描述的，集成规则中的错误通常是多位置的，因为它们可能跨越多行代码，例如，当规则以错误的顺序应用时。

2、修复技术应该能够修复代码中的多个独立错误。

大多数程序修复技术假设给定(输入)测试套件中所有失败的测试用例都是由于代码中的相同错误而失败的。因此，它们一次只能为一个故障生成一个补丁。生成的补丁可以替换单个程序语句，或者它们可以基于预定义的模板构建，规定硬编码的变更模式来修改多个位置的程序。然而，对于 ADS 集成规则来说，代码中只有一个错误的假设是不成立的，因为测试用例可能会因为位于代码不同部分的多个错误而失败。正如我们在第 3 节中所描述的，为了修复给定测试套件中所有失败的测试用例，我们可能需要修复代码中的多处错误，例如，通过重新排序一些规则，另外，改变一些其他规则的前提条件。

3、修复技术应该扩展到在系统级修复故障。

测试 ADS 软件需要一个基于模拟的测试平台，该平台可以针对不同的道路结构、天气条件和交通状况执行 ADS 软件。使用模拟器测试 ADS 软件面临两个挑战：首先，每个测试用例是一个在一段时间内执行的场景，并通过反馈循环模拟运行 ADS 软件。因此，单个测试用例是在每个模拟时间步长类运行 ADS 软件，并随着时间的推移生成一系列输出，而不是单个输出。因此，ADS 软件中的依赖性既是结构性的(像典型的代码一样)，也是临时性的。其次，ADS 软件的测试用例在计算上是昂贵的，因为每个测试用例必须执行一段时间，并且必须在每个时间步骤执行一个复杂的模拟器和 ADS 软件。这限制了用于修复的测试套件的大小和我们可以生成的中间补丁的数量。

4、修复技术应该按照故障的严重程度来解决故障。

当测试软件时，测试用例要么通过，要么失败，并且没有区分失败的测试用例的因素。然而，对于 ADS 来说，有些失败比其他失败更关键。例如，违反速度限制 10 公里/小时的测试案例比违反速度限制 5 公里/小时的测试案例更关键。类似地，汽车以低于 10 公里/小时的速度撞上行人的测试场景相对于以更高的速度发生碰撞的测试场景相比，显得不那么重要。因此，我们的修复策略应该以更细致的方式评估失败的测试用例，并优先修复更关键的失败测试用例，而不是不太关键的测试用例。

我们提出了一种自动修复自动驾驶系统集成规则的方法（ARIEL）。我们的修复策略依靠多目标、单一状态搜索算法实现了上述的四个目标，该算法使用存档来跟踪部分修复的解决方案。我们已经将 ARIEL 应用到我们合作公司的两个自动驾驶系统案例研究中。结果表明，ARIEL 能够在我们的两个案例研究中平均在 5 小时和 11 小时内修复集成故障。我们 告了从工程师那里收到的关于 ARIEL 实际用途的反馈。反馈表明，ARIEL 能够生成集成故障的补丁，这些补丁是工程师可以理解的，并且，如果没有任何自动化的工具，仅基于他们的专业知识和领域知识，他们无法开发这些补丁。

以下是文章结构，第 2 节提供了动机和背景，第 3 节介绍了我们的方法，第 4 节描述了我们的评估，第 6 节讨论了相关工作，第七部分总结全文。

2 背景

我们首先使用我们的行业合作伙伴的自动驾驶系统案例研究自动驾驶来启发我们的工作。

图 1:自动驾驶系统概述，由四个自动驾驶系统功能组成。

图 2:解决不同 ADS 功能之间冲突的有序集成规则。

图 1 显示了自动驾驶的概述，包括四个自动驾驶系统功能:自动巡航控制（ACC）、交通标志识别（TSR）、行人保护（PP）和自动紧急制动(AEB)。ACC 自动调整车速和方向，以保持与前车的安全距离。TSR 检测交通标志，并应用适当的制动、加速或转向命令来遵守交通规则。PP 检测汽车前方是否存在行人，并在需要时发出制动命令。AEB 防止与行人以外的物体发生事故。

图 3:与图 2 中的集成规则相关的决策树图的片段。

由于这些功能产生制动、加速和转向命令来控制车辆，它们可能同时向汽车发送冲突的命令。例如，ACC 命令汽车加速以跟随领头汽车的速度，而与此同时，行人开始横穿马路。因此，PP 开始发出制动命令，以避免撞到行人。

3 方法

在这一节中，我们提出了我们的方法，自动化集成规则修复(Automated Require of IntegratIon RULEs，ARIEL)，以定位和修复集成规则中的错误。ARIEL 的输入是(1)有故障的 ADS 和(2)验证安全要求的测试套件。输出是修复后的 ADS。下面，我们详细介绍 ARIEL 的不同步骤。

3.1 错误定位

功能交互失败可能是由集成规则中的多个独立错误引起的，其中一些错误可能跨越集成规则代码的多个语句。如先前的研究所示，最先进的故障定位方法通常不能精确定位所有的故障线路(即那些在程序修复中突变的线路)。此外，如第 1 节中所述，为了测试 ADS，我们必须在一段时间内以连续循环的方式执行系统。因此，每个 ADS 测试用例在模拟持续时间内将覆盖多条路径。

3.1.1 定位故障路径

给定一个由测试用例导致的失败情况，我们的目标是确定更可能导致失败的路径。如上文所述，我们区分了两种类型的故障:(1)错误的条件，即规则前提条件中的故障，例如，当汽车和行人之间的距离太小时，制动命令被激活；以及(2)规则的错误排序，即由于规则激活功能的错误排序而导致的故障。出于故障定位的目的，我们只考虑故障发生时执行的路径，而忽略故障前后故障测试用例覆盖的所有其他路径。相比之下，在传统的故障定位中，应该考虑测试用例覆盖的所有语句(在我们的例子中是集成规则)。

3.1.2 失败的严重性

在错误定位公式(以及最先进的故障定位技术)中，所有失败的测试在计算语句可疑度的公式中具有相同的权重。然而，在多个故障的情况下，这种策略无法优先修复其中的一些故障。关注与最严重的失败相关的错误可以获得在适应性方面具有最大潜在收益的补丁。我们可以衡量违反自动驾驶系统安全要求的严重程度。严重性对应于测试用例的输出。对于测试用例和需求，输出值越低，违反需求的严重程度越大。

#

3.2 程序修复

传统的修复工具，如 GenProg，使用基于种群的算法(如遗传算法)，迭代地进化候选补丁池。针对整个测试套件评估每个候选补丁，以检查更改是否会导致更多或更少的失败测试。

基于群体的算法假设评估单个补丁的成本不大，因此，可以在几秒钟内收集测试结果，并用于向搜索提供反馈。然而，正如在第 1 节中所讨论的，这个假设在我们的上下文中不成立，并且运行一个基于模拟的测试用例需要几分钟的时间。因此，在每次迭代/生成中评估一个补丁变得过于昂贵(几个小时的数量级)。

算法 1: ARIEL

基于以上观察，我们选择了带有存档的进化算法。该算法每代只选择一个亲本，只产生一个子代。一次只生成和评估一个补丁可以降低每次迭代的成本。我们的程序修复方法 ARIEL 包括(i) 进化算法，(ii)我们的故障定位公式和(iii)存档策略。算法 1 提供了 ARIEL 的伪代码。

ARIEL 接收测试套件和具有故障的自动驾驶系统。输出是一组经过修复的集成规则，这些规则通过了所有的测试用例。该算法首先用错误的规则初始化档案(第 2 行)，并计算目标分数，我们在下文(第 3 行)对此进行了描述。然后，档案在第 4-8 行的循环中迭代演化。在每次迭代中，ARIEL 从档案中随机选择一个补丁(第 5 行)，并通过(1)应用故障定位和(2)对规则进行变异，创建一个后代。

然后，通过运行测试套件，提取剩余的故障，并计算它们相应的客观分数，对子代进行评估(第 7 行)。请注意，故障的严重性是我们的搜索目标，将在下文中进一步讨论。如果子代与当前存储在存档中的补丁相比降低了故障的严重性，则添加到存档中(算法 1 的第 8 行)。存档及其更新程序在下文中有详细描述。当满足终止标准时，搜索停止。

3.2.1 生成补丁

算法 2: GENERATE-PATCH

ARIEL 使用算法 2 中的程序生成补丁。首先，它应用我们的故障定位公式(第 2 行中的常规故障定位)来确定语句的可疑性。

为了从最可疑的语句中选择一个语句，我们使用轮盘赌选择(RWS)，它给每个语句分配一个被选择突变的概率，概率基于每个陈述的可疑性。

3.2.2 存档

该存档存储搜索过程中找到的最佳部分补丁。在搜索开始时(算法 1 的第 2 行)，用错误的规则集初始化存档。每次创建和评估新补丁时，我们都会将其与存储在存档中的所有补丁进行比较。

因此，在每次迭代中，存档将被更新(算法 1 的第 8 行)，使得它包括迄今为止找到的最佳部分补丁。

进化算法的一个可能的限制是它们会陷入局部最优(早熟收敛)。处理这一潜在限制的一个成熟策略是重启(重新初始化)搜索。我们在 ARIEL 中实现了以下重启策略:首先，ARIEL 使用一个计数器来计算在搜索目标中没有改进的后续代的数量(即，档案永远不会更新)。如果计数器达到 h 代的阈值，则通过删除存档中的所有部分补丁并使用原始故障规则集重新初始化它来重新开始搜索。

3.2.3 终止标准

当搜索预算被消耗时，或者当找到了一个合适的补丁时，搜索停止，即存档包含一个满足所有测试用例的补丁。这里需要注意的是，即使我们的修复算法是多目标的，它也只生成一个最终解。这是因为我们的算法是单状态搜索，在每次迭代中只生成一个解。如果该解是最优的，则搜索停止。

3.2.4 补丁最小化

在搜索结束时，ARIEL 返回一个合适的补丁(即它通过了所有测试)，但它可能包含为了修复虚假突变而产生的冗余。这个问题可以通过补丁最小化算法来解决，即迭代地移除一个突变并验证反向改变后的补丁是否仍然通过测试套件的贪婪算法。如果是这样的话，就可以得到一个更小的(最小化的)补丁，这个补丁仍然可以通过测试。

4 结论

我们提出了一种修复技术来自动化地解决自动驾驶系统中的集成故障。我们的方法将故障定位在多行代码上，以修复复杂的集成故障，并处理测试和修复自动驾驶系统的可伸缩性问题。我们的修复算法依赖于多目标、单状态搜索算法，该算法使用存档来跟踪部分修复。我们的方法使用了两个工业自动驾驶系统进行评估。结果表明，我们的修复策略可以修复这两个系统中的集成故障，并优于现有的自动修复技术。来自领域专家的反馈表明，由我们的方法生成的补丁是工程师可以理解的，且如果没有任何自动化工具的帮助，他们无法独立开发出来。

致谢