Provably Lossless Acceleration of DNN Mutation Testing via Memoization

想象一下，你正试图教会一个机器人如何识别猫。你构建了一个巨大的、复杂的脑，它由层层叠叠的微小开关（神经元）组成，并从成千上万张图片中学习。但你如何知道你的机器人是真的聪明，还是仅仅运气好？在软件测试的世界里，有一个聪明的技巧叫做“变异测试”（mutation testing）。这就像是在玩一场“找不同”的游戏，你故意以微小且随机的方式破坏机器人的大脑——在这里翻转一个开关，在那里扭转一根电线——以此来观察你的测试图片是否足够优秀，能够捕捉到这些错误。如果即使在你破坏了大脑后，机器人仍然把狗误认为猫，那么说明你的测试并没有尽到职责。

这个问题在于，这个游戏极其缓慢且昂贵。为了测试一个现代机器人的大脑，你可能需要破坏它成千上千次，并且每一次破坏都要让它运行数百万张图片。这就像是为了在一堆干草中寻找一根针，而每发现一处问题，都要重新搭建整个干草堆，破坏一根小小的稻草，然后再次检查整个干草堆，如此周而复始。大多数试图加速这一过程的人都不得不采取一些“作弊”手段，使用通过猜测结果的捷径。但在科学领域，靠猜测是危险的；如果你猜错了，你可能会误以为你的机器人是安全的，而实际上它已经损坏了。这篇论文介绍了一种新的游戏方式，它既快速，又拒绝作弊。

机器人大脑的“复制粘贴”捷径

认识一下 Mure（发音类似于“moo-ray”），这是一个由研究员 Ali Ghanbari, Ben Greenman, Sasan Tavakkol, 和 Shibbir Ahmed 设计的新工具。把深度神经网络（机器人的大脑）想象成工厂里一条漫长的装配线。原材料（图片）从起点进入，经过许多站点（层），最后产出成品（答案）。

当你想要通过破坏生产线末端的机器来测试工厂时，你并不需要每次都从头重建整个工厂。你只需要修复被破坏的机器以及它之后的几个站点即可。在破坏点之前的站点与原始工厂完全相同。

Mure 使用了一种叫做记忆化（memoization）的技术，这是一个听起来很高级的词，意思其实就是“记住你已经做过的事情”。以下是它的实际运作方式：

1. 装配线： 想象你有一个工厂，正在制造 100 辆略有不同的玩具车。在其中的 99 辆车里，装配线的前 10 个步骤都是完全相同的。只有最后 2 个步骤有所不同。
2. 旧方法（原生测试）： 旧的方法会为每一个版本都从头开始制造整辆车。它会运行前 10 个步骤，然后运行最后 2 个步骤，然后重新开始，再次运行前 10 个步骤，再运行最后 2 个步骤。这浪费了大量的精力。
3. Mure 的方法： Mure 说：“等等！每个人的前 10 个步骤都是一样的。”于是，它只运行一次前 10 个步骤，并将结果保存在一个“记忆表”（memo table）中（就像贴在墙上的便利贴）。然后，对于每一辆变异后的玩具车，它只需直接获取那张便利贴，跳过前 10 个步骤，仅完成最后 2 个步骤的制造。

重大发现：速度与精准并存

研究人员从数学上证明了 Mure 是可证明无损的（provably lossless）。在过去，其他工具试图通过可能漏掉某些错误的“有损”捷径来提速。它们就像一位厨师在尝汤时跳过了检查盐分的步骤，并希望味道没问题。Mure 则不同；它是一位即便使用预量杯而不是每次重新称重，也会严格按照原配方检查盐分的厨师。

论文证明了 M是否能产生与那种缓慢、枯燥、“从头开始”的方法完全相同的结果。它不会漏掉任何损坏的机器人。它只是以更快的速度完成了工作。

数据说明

团队在 15 种不同形状和规模的机器人大脑上测试了 Mure，从简单的模型到拥有数百万个部件的庞大复杂模型。他们在标准计算机上运行了这些测试（未使用高端超级计算机或图形卡）。

• 速度增益： 平均而言，Mure 使测试过程提速了 44.54%。这意味着如果以前测试需要 100 分钟，现在只需要约 55 分钟。
• 权衡取舍： 他们将 Mure 与其他“作弊”捷径（称为 DM# 和 BSS）进行了对比。那些捷径甚至更快（高达 88.97% 的提速），但它们会出错。它们有时会误判，要么说机器人正常但实际已损坏，要么反之。Mure 则拒绝犯这些错误。
• “你破坏了多少？”测试： 研究人员还询问：“如果我们破坏更多的部分会怎样？”他们测试了破坏机器人 1%、3% 和 5% 的神经元的情况。随着破坏的部分增多，提速效果变小了（因为可以重复利用的“前 10 个步骤”变少了）。然而，即使在破坏了 5% 的神经元时，Mure 仍然提供了 20% 的速度提升。

为什么这很重要

这不仅仅关乎节省时间，更关乎信任。在自动驾驶汽车或医疗诊断等对安全性要求极高的领域，你承担不起猜测的代价。如果测试说一辆车是安全的，它必须是 100% 确定的。Mure 让工程师能够在不牺牲这种 100% 确定性的前提下，更快地运行这些沉重且昂贵的安全性检查。

研究人员表明，通过聪明地选择要重复利用哪些部分的大脑，你可以将测试成本降低近一半。他们不仅仅是猜测这行得通，他们构建了工具，进行了实验，并证明了数学逻辑。这提醒我们，有时候，实现快速的最佳方式不是跑得更快，而是记住你已经做过的事情。