深入探讨 Go 语言的深度递归问题

本文翻译自 A deep dive into deeply recursive Go，版权归原作者所有。

在我们 之前关于 Go 安全性的博客文章 中，我们写到了 2024 年修复的安全问题。其中一个要点与 9 月份发布的 Go 1.22.7 和 1.23.1 安全版本有关，该版本包含了对三个拒绝服务漏洞的修复。栈耗尽是这三个问题的根本原因，在没有明确以防御性方式编写的代码中极其常见。特别是在 Go 中，由于运行时处理栈耗尽的方式，栈耗尽比大多数内存安全语言更加危险。当栈耗尽发生时，崩溃是不可避免的。

需要进一步调查深度递归在 Go 中为何如此糟糕的机制、通常如何最终编写出深度递归的 Go 代码，以及可以采取什么措施来缓解栈耗尽问题。

定义深度递归

有些问题本质上是递归的。这并不是说这些问题不能用迭代方式解决，而是递归解决方案更直观，通常也更易读。一个简单的例子是斐波那契数列，其定义本身就是递归的：数列中的每个元素都是前两个元素的和。编写一个打印数列的迭代 Go 程序很容易，但递归实现更直观，因为它直接映射到定义：

// Fibonacci 打印斐波那契数列 1, 1, 2, 3, 5, ...
func Fibonacci(f ...uint64) {
    var next uint64 = 1
    if len(f) > 1 {
        next = f[len(f)-2] + f[len(f)-1]
    }
    fmt.Printf("%d, ", next)
    Fibonacci(append(f, next)...)
}

这个函数是 无限 递归的一个例子：它会一直打印斐波那契数列中的数字直到永远——或者直到某个外部力量阻止它。这也是一个 尾递归 函数的例子，其中递归步骤是函数体中的最后一条语句。这样的函数很容易转换为迭代形式，甚至可以通过编译器在称为尾调用优化（TCO）的过程中自动转换。不幸的是，Go 不支持 TCO，这意味着递归不会被优化掉，导致栈在数列的每一步都会增长。

栈和堆的说明

Go 程序可以访问两种类型的内存：栈和堆，就像一般的计算机程序一样。一个只使用局部变量和基本类型的简单程序可能只访问栈，这是所有局部变量在可能的情况下存储的地方。但对于任何更复杂的程序，堆是大多数分配实际发生的地方：所有用 make 或 new 分配的内容、所有切片的内容，以及所有不能安全存储在栈上的内容。为了确定什么可以存储在栈上，什么需要放在堆上，Go 编译器使用一个称为 逃逸分析 的过程。细节相当复杂，仅通过查看代码很难确定变量的存储位置。

所有这些都很重要，因为栈和堆内存的管理方式完全不同。堆是垃圾收集器的领域，而栈使用更简单的机制增长和收缩。

栈上的值以非常有序的方式存储，正如其名称所示：每个 goroutine 都有自己的栈，由帧组成。调用函数会将一个帧推入栈并为其所有参数和局部变量预留空间。从函数返回会从栈中弹出相应的帧以及所有相关的值。这意味着当值不再可从创建它们的作用域访问时，它们会自动被丢弃。

在斐波那契例子中，调用函数会写入一个包含参数 f 的栈帧，从栈中预留一些字节。局部变量 next 逃逸到堆。递归步骤写入另一个具有相同布局但新值的帧，占用更多空间，如此往复，无穷无尽。

栈当然不是无限的。它受到物理内存和操作系统的限制，但最重要的是，它受到分配栈的 Go 运行时的限制。一个新的 goroutine 总是有一个固定大小的初始栈，具体来说是 2 KiB。每当新帧不再适合分配的栈时，会分配一个大小加倍的新栈 并复制旧栈。这会一直发生，直到达到两个限制之一：可配置的最大栈大小，或固定的与架构相关的 最大栈上限。达到这些限制之一称为 栈耗尽。

有限深度递归

现在应该很明显，斐波那契示例不会运行无限长的时间——实际上，它很快就会崩溃。这显然是导致栈耗尽的一种深度递归形式。但递归不需要是无限的，只要足够深就足以造成危害。

通过对示例的轻微修改，可以为递归引入限制：

// FibonacciUpToN 打印斐波那契数列 1, 1, 2, 3, 5, ...
// 在 n 个元素后停止
func FibonacciUpToN(n int, f ...uint64) {
    if len(f) >= n {
        fmt.Println("...")
        return
    }
    var next uint64 = 1
    if len(f) > 1 {
        next = f[len(f)-2] + f[len(f)-1]
    }
    fmt.Printf("%d, ", next)
    FibonacciUpToN(n, append(f, next)...)
}

只要参数 n 固定为足够低的值，这段代码就能正常工作。当然，足够低 很难确定：该值应该小于任何系统或运行时限制，但单位不同——运行时以字节为单位测量栈深度，而代码只限制递归调用的次数——并且系统和运行时限制因平台而异。

在实践中，应该逐案确定确切的限制。例如，我们斐波那契函数的调用者可能对序列中第 50 个元素之后的值没有任何合理需求，所以为了安全起见，我们可能将 n 固定为 75，这仍然远低于会引起问题的任何值。实际上，第 100 个元素已经会溢出 int64，所以到那时打印的值无论如何都会不正确。在这种情况下，我们很幸运，因为很容易证明低限制的合理性。

通常，为限制找到合理性要困难得多。一个选择是将决定权留给调用者。在我们的斐波那契示例中，我们可能修复整数溢出问题并决定让调用者选择他们需要多少个元素，无论是 10、100 还是 10,000,000。值 n 成为输入的一部分，但递归不再是无限的，因为已经设置了明确的限制。将决定权交给调用者并不能消除做出决定的需要，然而，调用者可能不太有能力理解限制的含义，甚至可能不知道被调用的函数首先是递归的。调用者还可能从第三方提供的文件中读取输入。那么这是第三方的责任吗？如果第三方是恶意的呢？

使用参数值 10,000,000 调用 FibonacciUpToN 会使 Go 程序崩溃。但是用 n 设置为 5,000,000 或 2,000,000 来调用它呢？仅通过阅读代码很难判断。很明显，如果 n 被认为是用户输入，FibonacciUpToN 在可能产生有害结果的意义上仍然是深度递归的。

斐波那契示例仍然是一个容易处理的例子，因为调用者可以通过试错确定 2,000,000 对于特定目标平台和用例是一个安全限制，然后相应地验证输入，如果超过限制则优雅地失败。在现实世界中，测量输入本身的大小可能是具有挑战性的。递归解析器可能需要处理几千兆字节长度的输入文件，但只能容忍输入文件结构中的递归到某种程度。因此，输入的相关"大小"在解析每个结构的实际时刻之前是未知的。接下来我们将深入研究这样的例子。

现实世界的深度递归

到目前为止讨论的例子有些人为：为什么有人会想知道第 2,000,000 个斐波那契数呢？然而，现实的例子并不缺乏。递归经常用于解析递归文件格式、协议线格式和一般数据序列化格式，我们从中精选了一些案例。

Go 1.18.3 中跳过 XML

XML 是固有递归数据序列化格式的一个突出例子：XML 元素可以包含其他 XML 元素，而其他 XML 元素又可以包含更多的 XML 元素：

<Element>
  <AnotherElement>
    <YetAnother>
      <Element/>
    </YetAnother>
  </AnotherElement>
</Element>

Go XML 解码器 encoding/xml.Decode 提供了 Skip 方法，可用于在解析期间丢弃任意元素。在低级用法中，它可以被直接调用，但像 xml.Unmarshal 函数这样的高级构造也会在内部调用它。

在 Go 版本 1.18.4 和 1.17.12 之前，20 兆字节的输入可能会使任何调用 Skip 的程序崩溃，包括只是通过 Unmarshal 隐式调用它的程序。这是因为 Skip 会对任何无法识别的 XML 结构调用，然后对跳过时遇到的每个 StartElement 令牌递归调用：

func (d *Decoder) Skip() error {
    for {
        tok, err := d.Token()
        if err != nil {
            return err
        }
        switch tok.(type) {
        case StartElement:
            if err := d.Skip(); err != nil {
                return err
            }
        case EndElement:
            return nil
        }
    }
}

递归只受输入长度和其中递归结构深度的限制，即嵌套 XML 元素的数量。该方法不是尾递归的，但仍然很容易转换为迭代形式，这 修复了 问题：

func (d *Decoder) Skip() error {
    var depth int64
    for {
        tok, err := d.Token()
        if err != nil {
            return err
        }
        switch tok.(type) {
        case StartElement:
            depth++
        case EndElement:
            if depth == 0 {
                return nil
            }
            depth--
        }
    }
}

修正后的代码不是隐式使用栈来跟踪元素的嵌套深度，而是在局部变量中显式跟踪嵌套深度，从不递归——对于这种特定情况来说是一个优雅的解决方案。

google.golang.org/protobuf 中的递归限制

在包 google.golang.org/protobuf 中可以找到一个更复杂的例子，其中 在版本 1.28.0 中引入了递归限制，以响应我们对大输入崩溃的报告。与 XML 一样，Protocol Buffer 线格式的反序列化是一个固有的递归过程，Go 反序列化器是以深度递归的方式编写的。在版本 1.27.1 之前，反序列化 Protocol Buffer 的 Go 程序可能会被大约八兆字节的字节 0x0B 流崩溃。其中一个罪魁祸首是这段代码：

func ConsumeFieldValue(num Number, typ Type, b []byte) (n int) {
    switch typ {
    /* ... */
    case StartGroupType:
        n0 := len(b)
        for {
            num2, typ2, n := ConsumeTag(b)
            /* ... */
            n = ConsumeFieldValue(num2, typ2, b)
            if n < 0 {
                return n // 转发错误代码
            }
            b = b[n:]
        }
    /* ... */
    }
}

值 0x0B 会被 ConsumeTag 从 b 中读取并处理，使 typ2 总是被设置为 StartGroupType。然后函数 ConsumeFieldValue 会递归，像之前一样从 b 中读取另一个字节，只要栈可用就继续。

至于 修复，解决方案是回退到其他语言中实现的行为。Java 和 C++ 实现已经将嵌套深度限制为 100，所以在 Go 中强制执行类似的限制也相对安全：

func ConsumeFieldValue(num Number, typ Type, b []byte) (n int) {
+   return consumeFieldValueD(num, typ, b, DefaultRecursionLimit)
+}
+
+func consumeFieldValueD(num Number, typ Type, b []byte, depth int) (n int) {
    switch typ {
    /* ... */
    case StartGroupType:
+       if depth < 0 {
+           return errCodeRecursionDepth
+       }
        n0 := len(b)
        for {
            num2, typ2, n := ConsumeTag(b)
            /* ... */
-           n = ConsumeFieldValue(num2, typ2, b)
+           n = consumeFieldValueD(num2, typ2, b, depth-1)
            if n < 0 {
                return n // 转发错误代码
            }
            b = b[n:]
        }
    /* ... */
    }
}

这种情况的真正挑战不是管理递归的深度，而是库在典型软件项目依赖层次结构中出现的深度。与标准库或高级库不同，Protocol Buffers 不是你经常需要直接接触的东西。在我们的例子中，该库被用作我们依赖的 另一个库 的一部分，用于从 Apple Pages 文件中提取文本，但由于通过传递依赖传播修复到直接依赖，然后最终到我们的产品需要时间，我们选择通过禁用受影响的功能来保护我们的客户。限制输入的大小不是一个选择：文字处理文档通常超过攻击所需的八兆字节，并且在不解析的情况下无法判断文档是否包含恶意 Protocol Buffer 流。

这是深度递归的一个常见挑战：因为最容易崩溃的解析器通常是低级库，而从外部通过限制输入来缓解崩溃通常是不可行的，应用程序开发者即使识别了这些问题也不能很好地修复它们。

go/parser 中缺少递归深度检查

即使已经考虑了递归深度，在递归模式丰富的代码中始终如一地检查限制也可能很棘手。一个例子来自 CVE-2024-34155，go/parser 中的崩溃，以及 其修复，为原本正确执行限制的代码添加了一个遗漏的检查：

func (p *parser) parseLiteralValue(typ ast.Expr) ast.Expr {
+   defer decNestLev(incNestLev(p))

这里 incNestLev 将内部计数器的值增加 1，一旦函数返回，decNestLev 相应地减少该值。如果该值超过预先确定的阈值，incNestLev 就会恐慌（panic）。为什么这么容易错过这样一个明显的检查？因为解析器的内部调用图看起来像这样：

栈耗尽崩溃的解剖

虽然 Go 并不总是有最大栈限制——触发致命错误的明确阈值——但自 2013 年发布的版本 1.2 以来 就存在这样的限制。从那时起，变化很少。2013 年确定为"令人难以置信的大"的相同限制仍然存在。更大的最大栈上限在 2020 年引入，但它只对错误消息有实际影响。

runtime/newstack 函数在 stack.go 中定义，负责强制执行栈限制。每当需要分配新栈时，该函数首先 检查 新大小是否在两个限制内。如果超过任一限制，检查就会 抛出。

if newsize > maxstacksize || newsize > maxstackceiling {
    if maxstacksize < maxstackceiling {
        print("runtime: goroutine stack exceeds ", maxstacksize, "-byte limit\n")
    } else {
        print("runtime: goroutine stack exceeds ", maxstackceiling, "-byte limit\n")
    }
    print("runtime: sp=", hex(sp), " stack=[", hex(gp.stack.lo), ", ", hex(gp.stack.hi), "]\n")
    throw("stack overflow")
}

在 Go 中，throw 不是像许多其他语言中的关键字或语言构造。相反，它是运行时内部某些部分使用的错误处理模式。

致命错误

在 panic.go 中，Go 运行时定义了几种类型的错误，其中最熟悉的可能是标准 panic 及其各种变体：除零、越界错误、空指针解引用等等。恐慌不是栈耗尽时发生的情况——相反，会抛出致命错误。致命错误也有变体，但这里的特定变体是由函数 throw 触发的。

使用致命错误的主要原因之一是恐慌很复杂，可能本身会增长栈，当然当栈限制已经达到时这是不可能的。另一方面，throw 函数是一个 nosplit 函数，意味着它永远不会增长栈。

恐慌和致命错误之间面向用户的区别从"致命"一词中显而易见：与恐慌不同，致命错误无法恢复：

if dopanic_m(gp, pc, sp) {
    // crash 使用了相当数量的 nosplit 栈，而我们在 throw 中已经栈不足，
    // 所以在系统栈上崩溃（与 fatalpanic 不同）。
    crash()
}

影响

当 Go 程序恐慌时，运行时会展开栈，在途中执行每个 defer 语句，只有在到达末尾之前没有遇到 recover 调用时才会使程序崩溃。当运行时抛出致命错误时，这些都不会发生。这不仅意味着恢复是不可能的，而且 defer 语句中的其他代码也不会执行。因为延迟代码不会运行，数据丢失的可能性很高：即使是防护良好的代码也可能无法保存其状态，因为它只是停止运行。

深度递归不仅是临时的拒绝服务问题，还可能导致文件无法写入磁盘，甚至系统最终处于损坏状态，这可能会启用除 DoS 之外的其他攻击。

防范栈耗尽

从上面的现实世界例子中，可以很容易地识别出缓解深度递归的两种一般方法：通过将算法转换为迭代形式来完全消除递归，或者显式跟踪递归深度并将其限制为预定的最大值。这两种方法都有其优缺点以及不同的实现考虑。

第三个选择是使用减少崩溃影响的架构设计模式。

优先选择迭代

许多递归算法，特别是像我们原始斐波那契示例这样的尾递归算法，很容易转换为迭代形式：

// IterativeFibonacci 打印斐波那契数列 1, 1, 2, 3, 5, ...
func IterativeFibonacci() {
    f := []uint64{}
    var next uint64 = 1
    for {
        if len(f) > 1 {
            next = f[len(f)-2] + f[len(f)-1]
        }
        fmt.Printf("%d, ", next)
        f = append(f, next)
    }
}

当这在不损失可读性的情况下成为可能时，通常是最佳选择，因为迭代方法不会出错——没有意外遗漏检查或错误实现的风险。

有时实现迭代形式需要一些技巧，比如使用切片显式构造"栈"并将其存储在堆上——许多解析器采用的方法，比如 golang.org/x/net/html，它显式跟踪几个栈并通过 迭代 调用 函数引用 而不是递归来进行解析。

然而，这样的技巧可能会使代码难以阅读，也难以被静态分析工具推理。

限制递归深度

实现递归深度限制有几种方法。也许最明显的方法是引入一个额外的函数参数来跟踪深度，当超过常量限制时优雅地失败：

const maxDepth = 10_000

func DoRecursiveThing(a, b string, depth int) error {
    if depth > maxDepth {
        return errors.New("max depth exceeded")
    }
    /* ... */
    return DoRecursiveThing(a, b, depth + 1)
}

另一种选择是让调用者指定限制并向下计数。在这种情况下，调用者应该充分了解将限制设置得太高的影响：

func DoRecursiveThing(a, b string, maxDepth int) error {
    if maxDepth < 0 {
        return errors.New("max depth exceeded")
    }
    /* ... */
    return DoRecursiveThing(a, b, maxDepth - 1)
}

当调用者不需要能够控制递归深度时，通常最好将深度参数从公共 API 中隐藏：

const maxDepth = 10_000

func DoRecursiveThing(a, b string) error {
    return doRecursiveThingWithLimit(a, b, 0)
}

func doRecursiveThingWithLimit(a, b string, depth int) error {
    if depth > maxDepth {
        return errors.New("max depth exceeded")
    }
    /* ... */
    return doRecursiveThingWithLimit(a, b, depth + 1)
}

在处理递归方法和结构体接收器时，也可以在结构体上跟踪深度：

const maxDepth = 10_000

type Thing struct {
    depth int
}

func (t *Thing) DoRecursiveThing(a, b string) error {
    if t.depth > maxDepth {
        return errors.New("max depth exceeded")
    }
    /* ... */
    t.depth++
    return t.DoRecursiveThing(a, b)
}

使用这种方法，重要的是要注意，如果递归包含除尾调用之外的任何内容，深度需要在两个方向上跟踪：进入函数时增加，从函数出来时减少。如果有多个递归路径，在每个函数中包含检查可能会变成大量的复制粘贴，这是容易出错的。go/parser 采用的基于 defer 的方法是一个解决方案：

const maxDepth = 10_000

type Thing struct {
    depth int
}

func increaseDepth(t *Thing) *Thing {
    t.depth++
    if t.depth > maxDepth {
        panic("max depth exceeded")
    }
    return t
}

无论选择哪种风格，所有这些方法的最大风险是忘记在需要的某些路径中添加递归检查。

为崩溃容忍和恢复而架构

通过选择适当的软件架构，也可以减少栈耗尽引起的崩溃的影响。在 Mattermost，我们实现了 高可用性集群，其中单个进程崩溃不会使整个系统崩溃——相反，总是有另一个进程可用来接管。使用 Kubernetes，崩溃也会被及时自动恢复，意味着攻击者不能逐个击倒整个集群。数据库写入等操作使用事务来防止损坏。

尽管如此，这种保护只能是纵深防御措施和影响减少——即使是最好的架构也不能完全防止崩溃。崩溃仍然可能对用户可见，例如那些请求在崩溃时被同一服务器处理的用户看到的个别 HTTP 错误。

从源头修复问题

Go 运行时在栈耗尽时使程序崩溃没有技术原因。可恢复的恐慌同样是可能的。这并不意味着实现后者会很简单。相反，在已经栈不足并且恐慌时管理可用栈显然是非常复杂的。然而，使栈耗尽可恢复对整个 Go 生态系统将有重大的安全性和可靠性益处。

那么问题变成了是否值得实现这样的改变。一方面，存在在恐慌期间管理有限栈可用性的复杂性。另一方面，当前行为已经导致了许多安全问题。我们的答案是坚定的 可能，这就是为什么我们想要为更广泛的讨论开启这个话题。考虑到这一点，我们已经在 Go 问题跟踪器上写了一个提案，希望在那里看到评论。

附录：Go 标准库中的栈耗尽错误

为了更好地理解问题的规模，下面是过去在 Go 标准库中修复的栈耗尽漏洞的非详尽抽样。在撰写本文时，这 12 个 CVE 占 Go 有史以来发布的所有 CVE 的 9%。

在具有类似功能的第三方库中，据传闻，栈耗尽甚至更加常见。