欢迎光临
我们一直在努力

Who Goes First? Detecting Go Concurrency Bugs via Message Reordering

宾夕法尼亚大学(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 EnforcementInformation CollectionBug 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漏洞挖掘能力都有所下滑。在文中作者对每种策略下工具发现的漏洞进行更细致的讨论。

赞(0) 打赏
未经允许不得转载:黑客技术网 » Who Goes First? Detecting Go Concurrency Bugs via Message Reordering
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏