GoDDaR:把 CCS 重新捡起来,给 Go 的部分死锁一个静态解#

这是一篇 2026 年 10 月贴在 arXiv 的并发程序分析论文(arXiv:2610.08962,cs.PL),作者来自葡萄牙新里斯本大学的 NOVA LINCS。读完代码和跑通实验之后,我觉得它最值得记下来的不是”又一种 Go 死锁检测器”,而是他们把 1980 年代的 CCS(Calculus of Communicating Systems)重新捡起来,只加了一条 external choice 规则,就精确地兜住了 Go 的 select 语义。这件事本身很值得说一说。

1. 论文要解决的真问题#

Go 运行时自带一个死锁检测器:当所有 goroutine 都阻塞时,程序 panic。这个机制对一类问题够用,但论文指出了两个它永远抓不到的场景:

• 部分死锁(partial deadlock) — 5 个 goroutine 中 3 个永远卡住,另外 2 个还在跑,运行时检测不到。生产环境里很多”挂起但不 panic”的 bug 就是这种,数据库连接池跑满、channel 没人 close、worker 队列堆积——你看到的是”程序慢”,但 runtime 觉得”还活着”。
• 未执行的死锁 — 调度还没轮到那条路径,bug 已经被部署到生产了。

更扎心的是:现有工具只管”检测”,不管”修”。检测出来还得让开发者自己想怎么 fix。论文原话:“detection and resolution requires reasoning about complex interleavings and communication patterns, an inherently challenging task”。

GoDDaR 想做的两件事:(1) 静态检测出 unobserved 的全局或部分死锁;(2) 直接给出可应用的 Go 源码 diff 作为修复建议。后者在文献里几乎没人做,所以论文 §1 的贡献陈述里用了 “crucially” 这个词。

2. 流水线:Garbage in,CCS out,fix out#

GoDDaR 不是凭空工作的,它站在两个外部工具的肩膀上:Gospal/migoinfer(把 Go 转 MiGo 中间表示)和自实现的 OCaml 核心(把 MiGo 转 CCS 扩展 + 符号分析)。整个流水线分三段:

1. Gospal / migoinfer — Go 源码 → MiGo IR(包含 message-passing 事件和组合模式)。这一步已经不再维护,论文 §5 自己承认:“Most failed analyses were caused by the inability of migoinfer to generate valid IR”,25 个 case 里 6 个 crash 全来自这里。
2. GoDDaR 核心 — OCaml 实现,把 MiGo IR 转成带 external choice 的扩展 CCS,然后做符号分析穷举所有 interleaving。
3. 修复阶段 — 两条递归策略把 IR 变换成可解的形态,再反向回原 Go 源码生成 diff。

设计上的简洁让人舒服:整个核心算法只有几个函数,递归函数对所有算子同态,只对 prefixing(α.P)分情况。这种”对结构递归 + 只在最底层做条件分支”是 IR 变换的经典做法,可读性极好。

3. 核心方法:为什么必须扩展 CCS#

论文 §3.1 给出了一个让任何用过 Go 的人都点头的论点:Go 的 select 不能用 Milner 的标准 CCS 建模。

标准 CCS 用 + 表示 internal choice,语义是”(P + Q) --τ→ P'”——任意分支可被选,与环境无关。但 Go 的 select 不是这样:

select {
  case <- a:  // 只有 a 有数据才执行
  case <- b:  // 只有 b 有数据才执行
}

哪个 case 触发,完全取决于外部有没有数据可读。Internal choice 表达不了这个”被环境选择”的语义。

GoDDaR 引入了 De Nicola & Hennessy 在 1980 年代提出的 external choice(&):

(P & Q) --α→ P'     iff     P --α→ P'

分支只能在能与外部同步时才被规约到。这正好对上了 select 的真实行为。

论文给出的语法扩展其实非常小(Fig. 2):

α ::= τ | a | ā
P ::= α.P | a*.P | (P + P) | (P & P) | (P | P)
                ^^^^^^^^^^
                external choice(扩展)

在 action 上加了输入前缀迭代 a*.P 表达 unbounded computation,其他算子和标准 CCS 完全一致。一行规则换来一个全新的能力——这种”小改动撬动大问题”的论文读起来特别爽。

SOS 语义里也只新增了 [L-ExSum] 这条规则,右规则对称(Fig. 3 注释)。比起 GOMELA 那种把 Go 转 Promela 再丢给 SPIN 的路子,GoDDaR 的 IR 抽象更轻,直接盯着 channel 同步这一件事。

4. 检测算法:互补动作配对 + 穷举#

检测算法扩展自 Francalanza 等人在 finitary linear CCS 上的工作,核心思路非常符合直觉:配对互补动作,触发 τ 规约,递归评估子过程。

论文给了一个三通道循环的最小例子:

ā.b.c̄.0 | a.c.b̄.0      // 初始
b.c̄.0 | c.b̄.0          // a/ā 已配对(τ transition)

继续下去,b 和 c 无法再同步(没人写 b̄ 或 c̄ 在对端),任何进一步规约都不可能。算法穷举所有执行路径,任何 blocked action 都识别,与它属于哪个 goroutine 无关——这就是为什么这个方法能抓部分死锁。

关键不变量(论文原话):“A process is considered deadlocked if no further reductions are possible while unsynchronised actions remain.”

但 Go 还有几个 CCS 装不下的边角,论文 §3.4 用了整整一节处理这些:

• Closed channel — 读 closed channel 立即返零值(不阻塞);写 closed channel 触发 runtime panic。GoDDaR 用一个可扩展的 key-value struct 跟踪每个通道的 closed 状态,在归约前查表决定行为。
• 异步 channel(缓冲容量) — 满 buffer 的读 / 空 buffer 的写按同步算;其他情况立即 τ reduction。算法根据 buffer occupancy 切换模式。
• 递归 — 状态缓存:已探索过的过程状态直接截断(论文说这对应 livelock,不是 deadlock,可安全跳过)。但 §5 提了一个 edge case:moby#21233 在 non-reduction 步骤上仍可能重复,这是 future work。

这三条模式处理是 GoDDaR 击败同样基于 MiGo 的 Gong 的关键——Gong 没处理 closed channel / buffer / recursion 这么细,Table 2 里 TP 少 12 个、crash 多 10 个。

5. 修复算法:两条递归策略#

检测到死锁后,GoDDaR 怎么生成 Go diff?两条对所有算子同态的递归函数,只对 prefixing 分情况:

S-I(并行化阻塞动作):

• dr1(Γ, a.P) 看到 Γ(a) = ↓ (有 pending read) → 立刻把 a.0 提取成并行进程 a.0 ∥ P
• dr1(Γ, ā.P) 看到 Γ(a) = ↑ (有 pending write) → 同理

S-II(send/recv 不对称):

• dr2(Γ, a.P) 看到 Γ(a) = ↓ → a.dr2(Γ, P) ∥ ā.0(给 recv 补一个合成 send)
• dr2(Γ, ā.P) 看到 Γ(a) = ↑ → 走 S-I(直接并行化 send)

Γ 是个跟踪 channel 状态的环境(↓ pending read / ↑ pending write),递归函数是 homomorphic 的——对 + / & / | 算子都直接递归到子过程,只对 prefixing 做条件分支。

论文给的最简洁例子是 Listing 1.1a “Sequential”:

// 原代码
func main() {
    a := make(chan struct{})
    <- a           // 主 goroutine 阻塞
    a <- struct{}{}  // 永远到不了
}

GoDDaR 修复后:

 func main() {
     a := make(chan struct{})
-    <- a
+    go func(){<-a}()  // 并行包一层
     a <- struct{}{}
 }

CCS 视角下,原 ā.a.0 变成 (a.0 ∥ ā.0)——循环依赖被打断,程序不再死锁。这种修复的可读性在 Table 4 五个例子中都很高,几乎都是”加一个 goroutine 包装”这种最小修改。

6. 实验:25 个真实死锁案例的对比#

Benchmark 设计得很扎实,25 个 case 全部来自真实世界的 issue(图 5 给了分布):

• 10 个来自 go-deadlock-bug-collection(主基准库,覆盖 cockroachdb/etcd/moby/grpc-go/kubernetes)
• 4 个来自 Gomela(preload / circular-dependency / file-parser / x-sender-x-recv)
• 3 个来自 goat(nested / select-with-continuation / serving_2137,serving_2137 是 143 LoC 的最大 case)
• 3 个来自 GoKer(GoBench 的 bug-kernel:cockroachdb_2448 / grpc-go_660 / kubernetes_70277)

每个 case 都压缩到最小可复现(大多 < 50 LoC),涵盖 deadlock / 双重 channel 关闭 / 其它 channel 相关 runtime 异常。Go 版本对齐选了 Go 1.18(从 1.16 起测,Gomela 例外用 Docker Go 1.17)。

Table 2 是核心数字(25 个 case):

GoDDaR 是唯一无漏报的工具,TP 19/25 最高。但 coverage 略低(分析 19/25 vs goat 的 24/25),原因是 6 个 crash 全部来自 migoinfer 生成 IR 失败,不是算法本身。

论文里这段比较我读得很有味道:“GoDDaR and goat are the strongest tools in the benchmark. GoDDaR identifies two more bugs (19 against 17) and has no false negatives (against 7 for goat), while goat has far better coverage, analysing 24 of 25 programs against 19 for GoDDaR. This is expected: goat’s near-exhaustive control-flow graph analysis does not depend on migoinfer, whereas GoDDaR’s crashes are largely bounded by that intermediate representation.”——作者诚实承认 goat 的覆盖更广,因为它不依赖外部工具。这种坦率在论文里挺少见。

Table 4 给修复对比:

GoDDaR 对 ICO 类死锁全胜,GFix 一筹莫展;但 MC 类 GoDDaR 设计选择不修。论文解释:“such cases often cannot be fixed without altering the program’s intended semantics. While adding a dummy write could unblock a lone reader, the synthesised data might be invalid for the rest of the program’s logic.”——这是对正确性的坚持,GFix 用 dummy write 强行修可能改坏语义。设计哲学上的取舍,不是能力问题。

7. 我的几点观察#

读完之后想说几点不那么直接相关的观察:

CCS 在 2026 年被重新捡起来这件事本身就很有意思。GOMELA 走的是 Promela + SPIN model checker,GCatch 走的是 lock graph 静态分析,goat 走的是 exhaustive control-flow graph,但 GoDDaR 选了 1980 年代的 process algebra。原因论文 §3.1 写得很坦诚:Go 的 channel 同步语义本身就是 CCS 的 direct analogue,与其翻译到中间表示再丢给通用 model checker,不如直接用形式语义学的工具精确表达。这是”选对抽象层级”的好例子。

External choice 那一行规则——(P & Q) --α→ P' iff P --α→ P'——单独看就是一行定义,但它精确捕捉了 Go select 的”被环境选择”语义。这种”形式语义学和实际系统语言的精确对应”在 PL 论文里最有价值。

修复算法坚持不修 MC 类死锁——这是论文里我最喜欢的一段。“While adding a dummy write could unblock a lone reader, the synthesised data might be invalid for the rest of the program’s logic. Consequently, we chose not to handle these cases as they typically require manual, context-specific fixes.” 论文 §5 坦率地承认这是一处 trade-off,正确性比”能修”重要。审稿人应该会很高兴看到这种克制。

局限也值得记下来:GoDDaR 强依赖 migoinfer,后者已不再维护——25 个 case 里 6 个 crash 全因于此。论文 §5 future work 提了三个方向:换 IR(直接 transpile 到 CCS,像 GOMELA 转 Promela 那样自实现);系统化评估修复算法(目前只跑了 5 个代表 case);修 moby#21233 那个 edge case。这三条都是工程问题,不是理论问题,意味着如果有人想接盘这个工作,门槛不算高。

对 Go 用户的实际意义:目前能用的工具是 goat(覆盖广但有 7 个漏报)和 GoDDaR(需自编译 OCaml + Go 混合栈)。如果你跑一个 Go 服务,想 CI 加一层死锁扫描,goat 是更实用的选择;但如果你的代码里 channel 模式复杂(大量 select、buffer、closed channel),GoDDaR 的精确度更值——它的 0 漏报是真金白银,在 production 抓一个 case 就回本。

论文信息

• arXiv: 2610.08962 ↗ [cs.PL]
• 标题: Automatically Detecting and Fixing Deadlocks in Go Code with GoDDaR
• 作者: Gustavo Feio, Jorge Coelho, Miguel Flor, João M. Lourenço, António Ravara
• 单位: NOVA LINCS and NOVA FCT, Portugal
• 提交: 2026-10-06 (v1)
• 主题分类: Programming Languages (cs.PL); Distributed, Parallel, and Cluster Computing (cs.DC); Software Engineering (cs.SE)
• 代码: GoDDaR 工具本身可在 GitHub 获取 ↗(论文 §5 提及,具体仓库以作者公开为准)
• 复现材料: go-deadlock-bug-collection benchmark + Gospal/migoinfer 工具链