Who Goes First? Detecting Go Concurrency Bugs via Message Reordering

360安全客 安全工具 145191 4

宾夕法尼亚大学(PSU)，胡宏，ASPLOS 2022

开源地址：https://github.com/system-pclub/GFuzz

Go语言是为高效安全并发场景设计的一种程序语言。它提供协程(goroutine)和管道(channel)来辅助完成高效安全并发的目的，并推荐使用管道完成不同协程之间的信息传递，降低程序中并发漏洞出现的可能性。但是最近的研究表明，与管道相关的并发漏洞(channel-related concurrency bug)在Go程序中依然很常见，本文就是针对这类漏洞设计了一个工具进行挖掘。

本文的作者设计了一个工具GFuzz，用来针对channel-related concurrency bug进行挖掘。首先需要定位可能引入bug的并发channel，并对程序完成改写与编译，使之支持channel中信息的乱序到达。然后使用模糊测试的方式，将一系列不同顺序的channel信号送入改写之后的程序中。同时设计了一个runtime sanitizer，在运行时去监控channel-related concurrency bug是否发生。作者在7个最后欢迎的开源项目上进行测试，共发现184个新漏洞并上报，开发者已经确认了124个bug report，并完成修复其中的67个漏洞。

 

Intro

Go的并发控制：

  • 在Go语言中，有两种方式可以控制不同goroutine之间的通信和消息同步，分别是管道(channel)和共享内存(shared memory)，Go语言的设计者更推荐前者。
  • 在Go语言中，一个goroutine可以通过select语句同时等待多个channel传递回来的信号，这些select语句中等待的不同case是没有明显先后顺序的，因此构成一个并发情况，这也是作者识别并发channel的insight。

Go中并发漏洞形式：

  • 根据漏洞表现形式，可以分为阻塞型并发漏洞和非阻塞性并发漏洞。阻塞型并发漏洞会导致部分goroutine无法成功执行完；非阻塞型并发漏洞虽然不会导致goroutine阻塞，但是会引起非预期的结果。
  • 根据root cause，可以分为由于共享内存导致的并发漏洞和由于channel导致的并发漏洞。

现有工作：

  • 动态方法：
    1. Go语言本身在goroutine调度器中设计了一个死锁检测机制，但是这仅限于检查所有goroutine都阻塞的情况。
    2. 在其他语言中，存在让并发的线程按照一定顺序去执行从而去寻找并发漏洞的方法，但在Go语言上此前还缺乏相关的实践。
  • 静态方法：
    • 由于别名分析不准、CG构建不准等问题，以静态的方式挖掘并发漏洞存在较高的误报率。

 

Design && Implementation

Problem Scope

本文的作者主要应用GFuzz挖掘由channel通信引起的阻塞型并发漏洞(channel-related blocking bug)和由channel通信引起的非阻塞型并发漏洞(channel-related non-blocking bug)

Design

GFuzz的整个流程如下图所示。不同于以往的fuzzer主要选择输入作为变异对象，GFuzz将一系列并发channel返回的消息组成的序列(message order)作为变异对象(种子)。在程序运行时，GFuzz依赖一种新的反馈机制，对种子进行算分排序，给予分高在队列前端的种子更多的变异。同是GFuzz也设计了一套监控机制，用于检查是否发生并发漏洞。

上述三个部分在插桩过程中分别对应着下图里的 Order Enforcement、Information Collection、Bug Detection 三个部分。

Implementation

如何指定channel消息序列(message order)并变异

  • 确定了GFuzz解决问题的范围后，首先就需要在程序中定位并发的channel。GFuzz只选择了一种非常直白浅显的并发channel——在select语句中等待的多个channel case。
  • 明确了GFuzz关注的channel位置，接下来GFuzz设计了一种基于程序改写的方法，使得并发的channel顺序可以被测试者控制。下图提供了一个这种改写方法的样例(上旧下新)：

原来的每个含并发channel的select语句换成一个switch语句，switch中的每个case都是一个select语句，对应处理原来select中的每个case，同时每个switch case都设有超时T，用来防止goroutine之前存在隐式依赖造成FP的可能性。通过FetchOrder来控制每个select中执行哪个channel case。

  • 因为GFuzz是目标是控制select中的并发channel，对message order做了形式化定义。message order可以表示成一系列三元组组成的有序队列，例如$[(s_0 ,c_0 ,e_0 )…(s_n ,c_n ,e_n )]$。其中$s_i(0 ≤ i ≤ n)$ 表示select ID, $c_i$ 表示select中的总case数量，$e_i$表示此次之行的select case分支下标。GFuzz的变异只是变异$e_i$。

反馈机制

  • 在待测程序不断运行过程中，GFuzz监控每个channel上的操作，统计不同操作的数量；另一方面监控每个channel的状态，具体在下表中展示：

  • 依据上表中channel的属性值，作者依据如下公式对每个message order进行算分、排序。对于高分message order给予更多的变异。

    score = \sum\log_2(CountChOpPair)+10#CreateCh+10#CloseCh+10*\sum MaxChBufFull

runtime sanitizer

  • 对于channel-related non-blocking bug，目前Go runtime的能力足够检测出此类漏洞，因此作者设计sanitizer是为了检测channel-related blocking bug。
  • 检测时机：待测程序运行时每秒检测一次；在main goroutine退出时检测一次。
  • 检测方法概述：每次检查时，定位所有被阻塞的goroutine，然后分析阻塞goroutine的所有channel，是否有其他的goroutine在使用这些channel。如果一个channel阻塞了一个goroutine，而没有其他goroutine对这个channel读或写，即造成一个channel-related blocking bug。

 

Evaluation

作者在Kubernetes、Docker、Prometheus、etcd、Go-Ethereum、TiDB、gRPC七个项目上测试GFuzz的漏洞挖掘能力，共发现184个concurrency bug，其中170个阻塞型漏洞、14个非阻塞型漏洞以及12个FP。

为了验证GFuzz每个组件的必要性，作者在gRPC项目上尝试去掉各个组件后观察GFuzz漏洞挖掘能力的变化。在12小时的测试中，去掉各个组件后GFuzz漏洞挖掘能力都有所下滑。在文中作者对每种策略下工具发现的漏洞进行更细致的讨论。

（完）