通过消息重排自动检测 Go 程序中的并发缺陷

大家好，我是 polarisxu。

本文是网友「charlesxsh」投稿。

宾州州立大学系统安全实验室^[1]依靠模糊测试的思想设计了检测工具GFuzz，能自动检测Go程序中的并发缺陷。GFuzz在著名的开源软件（如Docker，Kubernetes）中发现了184个此前未知的并发缺陷。 

工具：https://github.com/system-pclub/GFuzz^[2]

英文论文：https://songlh.github.io/paper/gfuzz.pdf

演讲视频：https://www.bilibili.com/video/BV1TF411b7nN?spm_id_from=333.999.0.0

背景

Go 是由 Google 发明的工业级编程语言，当时Google设计Go的目的是编写安全高效的并发程序。最近几年来，Go 快速普及，已经成为世界上最受开发者喜爱的编程语言之一。开发者们用 Go 编写了很多工业界的基础架构软件，比如 Docker，Kubernetes，和 gRPC等。

为了更加方便地编写并发程序，Go 有许多内置特性，比如轻量级的线程（ goroutines）和 信道（channels），并且推荐开发者使用信道发送消息的方式进行goroutines之间的通信。

但遗憾的是，用Go来编写正确的并发程序依然很困难，并发缺陷（concurrency bugs）仍然在Go程序中广泛存在。而且最近的一项研究还表明，错误地使用信道也会导致并发缺陷。在某些情况下，使用信道可能比使用锁（mutexes）更容易出错。

现有的检测技术

由于目前已有的检测方法大多是为传统的编程语言（例如C/C++，Java）而设计建造的，只能监控锁和共享内存使用，并不能监控信道，也无法检测错误使用信道而导致的缺陷，因此现有的缺陷检测技术并不能有效发现Go程序中的并发缺陷，尤其是那些由于错误的消息传递而导致的缺陷。

此外，现有的model checking技术虽然可以系统地检查所有可能的消息顺序，从而发现分布式系统中的并发缺陷。但因为只有极少数的消息顺序能够触发并发缺陷，因此通过穷举所有消息顺序来找缺陷是非常低效的。

目前为Go设计的静态检测器，只能检测有限类型的缺陷，不能分析大规模代码，而且会产生大量的误报和漏报。而为Go设计的动态检测器，则只能检测已经触发的缺陷。它们既无法改变程序的运行状态，也不能增加触发缺陷发生的可能性，因此会漏报许多并发缺陷。

Go的并发缺陷案例

在这里展示一个来自Docker的信道相关并发缺陷，来更清楚地说明为什么现有的检测技术无法有效地发现Go程序中的并发缺陷。

在如图所示的案例中，父goroutine在第4行调用了一个类方法。被调用的函数是在17-31行的方法Watch（）。方法Watch（）在18，19行创建了两个没有缓冲区的信道 ch 和 errCh，然后在22行创建了一个子goroutine，最后在30行返回了这两个新创建的信道。

子goroutine在23行调用了s.fetch()，检查了返回值，根据检查结果向errCh（25行）或者ch（27行）中发送一条消息。同时，父goroutine阻塞在了select语句（5-14行），来等待在Fire（），errCh，或者ch中传来的消息。其中来自Fire（）消息会在1秒钟之后收到。

如果Fire（）的消息先到达，父goroutine会选择第一个case，记录超时信息并从当前函数返回。在这之后，除了子goroutine，没有其他的goroutine可以访问ch或者errCh，因为没有其他的goroutine可以在这两个信道中收取信息。

由于errCh和ch都是没有缓冲区的信道，在它们上执行的发送操作会阻塞发送goroutine，一直到另外的goroutine在它们上执行接收操作。所以子goroutine会永远卡在25行或者27行的发送操作，导致goroutine泄漏。

这个例子展示了在Go程序中成功检测到信道相关并发缺陷的难度。在这个案例中，检测器必须同时满足2个条件，才能成功地检测到这个并发缺陷。

首先，这个缺陷只有当来自Fire（）的消息比其他两个信道的消息先一步到达才会触发（条件1）。与此同时，检测器还需要有能力推断，没有别的goroutine可以访问ch或者errCh，因此没有别的goroutine可以解锁发送操作（条件2）。

在现有的检测技术中，静态技术无法推断第4行调用的是17行的Watch（）函数，所以它们无法判断是不是还有其他的goroutine可以解锁子goroutine（无法满足条件2）。

此外，在测试中，我们发现来自Fire（）的消息从来没有先到达过，所以动态监测技术也会漏报这个缺陷（无法满足条件1）。

新的动态分析工具Gfuzz

为此，我们提出了一个新的动态分析工具GFuzz，用来快速地检测Go程序中信道相关的并发缺陷。

GFuzz可以检测阻塞缺陷（blocking bugs：一个或多个goroutine在执行中发生阻塞无法继续进行）和非阻塞缺陷（non-blocking bugs：所有goroutine都可以结束但是产生了一些非期望的结果，比如panic）。

GFuzz的设计围绕着Go程序中的并发消息。在Go程序中，并发消息的处理顺序是不确定的，开发者必须保证Go程序在所有可能的顺序下都能正确执行。但是，考虑到可能的处理顺序数量庞大，开发者在有限的时间和精力里，非常容易忽略一些顺序，从而导致并发缺陷。

GFuzz通过改变测试程序中并发消息的处理顺序，来增加阻塞缺陷和非阻塞缺陷的触发几率。同时，它也会监控程序的执行状态来捕捉触发的阻塞缺陷。

我们再来看这段Docker中的并发缺陷和修复补丁。

从理论上来说，第6行、第8行和第12行的并发消息，到达的顺序是不确定的。第6行的消息可以比第8行的、或者比第12行的更快或更慢到达。不管是哪一种情况，这段代码都应该能正确运行。

然而开发者没有考虑到第6行Fire（）消息先到达的情况，导致前文提到的阻塞缺陷。通过改变并发消息的处理顺序，GFuzz能分析这两种情况并且检测出缺陷。

Gfuzz设计过程中的挑战

尽管GFuzz的设计思路听起来非常直截了当，但要构建一个在实际操作中可顺畅使用的工具，我们依然要应对一系列的挑战。

第1个问题：GFuzz如何辨识并发消息？

如果没有识别并发消息，GFuzz可能会强制一个和已有的happens-before消息顺序相冲突的顺序，从而导致在现实中不可能发生的死锁。

在这里，我们采用了一个简单的方法来识别并发消息。

在同一个select下，所有的信道操作是可以同时发生的，因此这些信道操作处理的消息是并发的。改变这些消息的处理顺序，可以在保持程序原意不变的基础上，保证程序执行路径的改变。

为了强制测试程序按照具体的顺序来处理消息，GFuzz会把每个select都转换成一种特别的形式，以保证某一个case被优先处理。同时，GFuzz还提供了一个超时机制去避免死锁。

第2个问题，如何发现哪种消息顺序更容易触发缺陷，并且提高它们的分析优先级？

消息的处理顺序可能有无限多个，穷举这些消息是不现实的。我们使用了模糊测试（fuzzing）的思路，从已经分析过的消息顺序出发，去生成新的消息处理顺序，并且根据强制消息顺序时测试程序的执行反馈，来发现更可疑和更容易触发缺陷的顺序。

我们设计了一个公式来评价每个消息处理顺序的可疑程度，然后根据公式的计算结果来确定顺序的优先级。

第3个问题：如何确定一个与信道相关的阻塞缺陷已经触发了？

当一个goroutine阻塞在信道操作上时，其他任何可以使用这个信道的goroutine都能对其解锁。如果没有小心地对测试程序的执行状态进行检查，很容易产生漏报或者误报。

为了解决这个问题，在GFuzz动态监控测试程序执行时，信道引用在goroutine之间的传递。Gfuzz会根据这些信息来确定一个阻塞在信道操作的goroutine是不是能被其他goroutine解锁，从而进行阻塞缺陷的检测。

Gfuzz系统概述和实验评估

GFuzz会用完整的Go程序或者单元测试作为入口，来检测那些误用channel而导致的并发错误。在这个过程中，GFuzz通过持续生成新的消息顺序，来监测程序执行状态，同时筛选可疑顺序来加速寻找错误的过程。下图展示了GFuzz的系统概述。

GFuzz可以作为线下的测试工具，和已有的程序输入或者单元测试配合使用。启动GFuzz之后，它可以自动探索测试程序的执行状态，来发现之前未知的与信道相关的并发缺陷。

我们对GFuzz进行了实验和评估，评估结果如图所示。其中LoC是源代码行数，Test是用于我们实验的单元测试数量。

在“Detected New Bugs（发现新的缺陷）”下面的各列中，下角标b代表阻塞错误，NBK代表非阻塞错误；“-”代表没有错误；GFuzz3代表在前三个小时里找到的错误数量。“Overheads”这一列代表sanitizer的额外开销，“/”代表并不适用。

我们用了包括 Docker、Kubernetes 和 gRPC在内的7个流行的Go开源软件对GFuzz进行了评估。GFuzz 总共发现了 184 个以前未知的缺陷，包括 170 个阻塞错误和 14 个非阻塞错误，并产生12 个误报。

我们已经向软件开发者报告了所有错误。到目前为止，根据我们的报告，开发者已经确认了 124 个错误并修复了其中的 67 个。

此外，我们系统地将 GFuzz 与最先进的静态 Go 并发缺陷检测器 GCatch 进行了比较。GFuzz 在三个小时内发现的缺陷数量要显著地多于 GCatch发现的全部缺陷，这确认了 GFuzz 确实推进了 Go 并发缺陷检测的进展。

结论

总的来说，我们做出了以下3个贡献。

• 我们提出了利用消息重排来提高 Go 程序中并发缺陷的触发概率。 

• 我们实现了GFuzz，它可以通过消息重排、顺序优先级的指定和对测试程序的动态检测，来有效地检测和发现与信道相关的并发错误。 

• 我们进行了详细的实验来评估GFuzz。GFuzz 在大型开源Go软件中检测到 184 个以前从未被发现过的与信道相关的错误。

参考资料