正则表达式（regex）在现代编程语言中广泛使用，但同时也是拒绝服务（DoS）攻击的潜在向量。近期实证研究表明，在典型正则引擎中，多达10%的正则表达式具有超线性最坏情况时间复杂度。因此，许多Web服务被报告易受正则表达式拒绝服务（ReDoS）攻击。若能透明地降低正则引擎的时间复杂度，则可消除ReDoS漏洞，且对应用开发者无额外成本。然而，现有的ReDoS防御方法——替换正则引擎、优化引擎或逐个替换正则表达式——在正确性和兼容性方面存在问题。完全的记忆化（memoization）虽然正确且兼容，但其空间开销过高。目前尚无有效的ReDoS防御被实际采用。本文提出了一种选择性记忆化方案，能够以较低的空间开销可证明地消除超线性正则行为。作者设计了多种具有不同空间/时间权衡的选择性记忆化方案，并进一步提出了一种利用正则引擎语义洞察的编码方案，以降低记忆化的空间成本。此外，还考虑了安全处理扩展正则特性的方法。作者在真实世界正则表达式语料库上实现了所提方案并进行了评估。实验表明，对于中位数正则表达式，选择性记忆化将记忆化的空间成本降低了一个数量级；而运行长度编码进一步将90%正则表达式的空间成本降低为常数。这项研究为防御ReDoS提供了一种高效且兼容的方法，有望在不改变开发者行为的情况下消除此类漏洞。