正则表达式拒绝服务（ReDoS）

概念定义

回溯引擎先试一条路径再回退重试。当多个带量词的组能匹配同一批字符——可选组上嵌套星号再要求尾字符——重试树的规模随每个输入字符翻倍。

工作机制

攻击者构造“几乎匹配”的输入最大化歧义：歧义前缀重复多次、却不给满足的后缀，每种歧义都翻倍路径。安全写法用原子分组与占有量词让引擎认账不回头，或用有界重复封顶重试；RE2、Rust regex 等线性引擎则以放弃部分特性换保证线性时间。

使用场景

审计一切可从请求数据触达的正则，包括继承自库与框架的模式。静态分析器能标记灾难性模式；模糊测试搜索慢输入；CI 里用病理样例做基准。

常见误区

“输入够大才危险”不成立——二三十个字符可能就够，复杂性在模式不在载荷。“测过一次就安全”也不成立：一次通过只走了一条回溯路径。编译只加速不改变指数语义；由用户片段拼装模式会让嵌套量词悄然复现。线性引擎缺反向引用与环视，部分规则移植不了；各引擎的超时机制不统一，只能当兜底不能当修复。

代码示例

export function escapeRegExp(input) {
  if (typeof input !== "string") throw new TypeError("input must be a string");
  return input.replace(/[.*+?^${}()|[\]\\]/g, "\\$&");
}

export function literalRegExp(input, flags = "") {
  if (typeof flags !== "string") throw new TypeError("flags must be a string");
  if (/[gy]/.test(flags)) {
    throw new RangeError("stateful flags g and y are not allowed");
  }
  return new RegExp(escapeRegExp(input), flags);
}

package main

import (
	"crypto/sha256"
	"crypto/subtle"
	"fmt"
)

func ConstantTimeEqual(a, b string) bool {
	left := sha256.Sum256([]byte(a))
	right := sha256.Sum256([]byte(b))
	return subtle.ConstantTimeCompare(left[:], right[:]) == 1
}

func main() {
	secret := "s3cr3t-token"
	fmt.Println(ConstantTimeEqual(secret, "s3cr3t-token"))
	fmt.Println(ConstantTimeEqual(secret, "s3cr3t-tokeX"))
	fmt.Println(ConstantTimeEqual(secret, "short"))
}