curl 如何在不经意间实现了九个月的图灵完备性

# curl 意外成为图灵完备长达九个月 来源：https://seriot.ch/computation/curl.html ### Nicolas Seriot #### 计算 (https://seriot.ch/computation/index.html) \> curl 意外成为图灵完备长达九个月 *2026年10月29日* 从 curl 8\.12 到 8\.16，配置文件可以对变量值进行切片，也可以在没有显式深度限制的情况下包含其他配置文件。结合这两个特性，curl 可以模拟任何双计数器 Minsky 程序。在通常的理想化假设下（无界字符串和资源），这个构造是图灵完备的。 curl 8\.17\.0 增加了五层包含上限，破坏了这种归约。 ### Minsky 双计数器归约 计数器值 `n` 用 `n` 个 `x` 的副本表示。 每个指令状态使用一个或多个配置文件，文件名充当标签，`expand-config` 用于选择下一个文件。 语法： - `{{b}}` 展开当前值 - `[0-0]` 仅保留第一个字节（`x` 或空） - `[1-]` 去掉第一个字节后保留其余所有内容 - 空切片产生空字符串（文档：https://github.com/curl/curl/blob/curl-8_12_0/docs/cmdline-opts/variable.md） | Minsky 指令 | Curl 配置 | |---|---| | 寄存器 `R` | 变量 `r`（`R` 为 `x` 字节的数量） | | `INC(R)` | `expand-variable = "r={{r}}x"` | | `DEC(R)` | `expand-variable = "r[1-]={{r}}"` | | `JZ(R, _, _x)` | `expand-variable = "t[0-0]={{r}}"` | | | `expand-config = "state_{{t}}.conf"` | | `JMP(S)` | `expand-config = "S.conf"` | | Halt | 不再调用 `expand-config` | 有了这些，我们就可以将任何双计数器程序编译为 curl 配置文件。 ### PoC：计算 2 \+ 3 curl\_addition\.zip (https://seriot.ch/resources/curl_addition.zip) 中的四个文件可以计算 2 \+ 3。 如有需要，请先构建本地 curl 8\.12\.0 二进制文件： ``` mkdir -p /tmp/curl-tc-build cd /tmp/curl-tc-build curl -fsSLO https://curl.se/download/curl-8.12.0.tar.gz tar -xzf curl-8.12.0.tar.gz cd curl-8.12.0 ./configure --without-ssl --disable-shared --disable-manual --disable-docs make -j4 ``` 然后在 `addition/` 目录下运行： ``` /tmp/curl-tc-build/curl-8.12.0/src/curl -q -s -K main.conf ``` 预期输出： ``` A=xxxxx B= ``` ### 运行时边界 该归约假设计数器无界且步数无界。实际的二进制文件两者都有限制： - **展开内容（curl 自身的限制）。**每次展开上限为 `MAX_EXPAND_CONTENT` = 10,000,000 字节（`src/var.c`：https://github.com/curl/curl/blob/curl-8_12_0/src/var.c#L42）。 - **步数。**没有循环：每一步都是一次嵌套的 `--config`，直到停机才返回。每一层都占用一个 C 栈帧，并在完成之前保持其配置文件处于打开状态。在 8\.12 上一个最小的倒计时循环中，8 MB 的栈在出现段错误之前允许执行 922 步。 - **保留的变量版本。**重新赋值会添加一个新条目（https://github.com/curl/curl/blob/curl-8_12_0/src/var.c#L347-L370），同时保留旧条目直到清理（https://github.com/curl/curl/blob/curl-8_12_0/src/var.c#L58-L78）。内存使用量和某些变量查找开销随步数增加而增长。 ### 历史与版本支持 - curl 8\.3（2023年9月）：变量展开 - curl 8\.12（2025年2月）：字节范围赋值 - curl 8\.17（2025年11月）：五层上限（https://github.com/curl/curl/blob/curl-8_17_0/src/tool_parsecfg.h#L28-L30）破坏了该归约 Pull request（https://github.com/curl/curl/pull/19168）称该上限可以防止配置文件无限地包含自身。其回归测试（https://github.com/curl/curl/blob/curl-8_17_0/tests/data/test774）确实执行了此操作，并期望得到错误。公开的解释并未讨论图灵完备性，也没有说明为什么上限是五层。 Bash 的 `while` 循环可以补充受限的 curl：每次调用执行一步配置，并在调用之间传递计数器和指令标签。此时重复来自 Bash，因此这是一种组合，而非仅凭 curl 实现图灵完备。 ### 安全影响 无。