十年歧途:一个正则表达式的故事

今天我要分享两个关于正则表达式的故事:微小的不精确性,最终导致全球 iOS 设备累计浪费超过 5000 万小时 CPU 时间

温馨提示:本文包含大量技术细节,非技术人员阅读可能略有难度。

Safari 内容拦截器工作原理

首先需要说明 iOS 版 AdGuard 依赖于 Safari 内置的内容拦截器机制。

目前也支持替代方案 declarativeNetRequest(英文简称:DNR),部分兼容 Chrome 和 Firefox。有趣的是,在 Safari 中 DNR 规则在底层会被静默转换为内容拦截器规则。

2015年10月发布初代 AdGuard iOS 版时,我们立即就遭遇了一个棘手的问题:传统广告过滤器一直使用专属过滤规则语法,这种语法专为网页过滤设计且功能强大。但 Apple 却推出了与社区习惯迥异的自有方案。

前瞻提示:当 Chrome 引入 declarativeNetRequest 时也选择了自成体系,至少在其 URL 匹配语法上更接近我们熟悉的规范。

下图展示标准的 AdGuard 规则转换为 Safari 支持语法的过程:

AdGuard 规则转换为 Safari 接受的规则

注意 URL 模式的变化:在 AdGuard 过滤器中,我们使用针对 URL 特制的类通配符语法。原因很简单:传统正则表达式在此场景下运行效率过低。

正则表达式实现机制

Safari 内容拦截器则依赖正则表达式。并且是以高度简化的形式实现,以便最终能编译成可以加速匹配的结构化数据。

技术细节说明:Safari 会将正则表达式模式编译为 DFA 字节码,并通过定制解释器执行。详见 WebKit 源码:DFABytecodeInterpreter.cpp

正则表达式确实比标准广告拦截语法更灵活。这种灵活性在网页内容过滤场景中实际用途有限,但其代价却是极其消耗资源的规则编译过程,以及严格的规则数量限制。我们曾详细讨论过 Safari 的这些问题,而其中多数问题至今依然存在。

模式转换方案 v1.0

回到2015年,我们需要解决的核心问题是如何将 AdGuard 的 URL 模式转换为 Safari 可接受的正则表达式。

当时面临两大挑战:

第一,必须压缩最终规则集的总量。当时 Safari 有5万条规则的硬性限制(解决方案详见我们关于 Safari 广告拦截的专题文章)。

当前规则上限已提升至15万条,但由于进程内存限制,实际仅能使用 6-8 万条。我们曾多次向 Apple 反馈(Apple Feedback Assistant 报告编号:FB19728743、FB13282146),但仍未解决。

第二,必须确保生成的正则表达式具备足够高的执行效率,且轻量化到 iOS 设备可顺利编译。在那个时期,我们经常发现系统因资源占用过高而终止 com.apple.Safari.ContentBlockerLoader 进程。

经过大量人工测试后,我们最终确定了在当时看来最优的转换方案:

  • || 符号(“开始与 URL”)转换为 ^[htpsw]+://([a-z0-9-]\.)?
  • ^ 符号(“分隔符”) 转换为 [/:&?]

我们自信地认为已经做足了功课,以后可以高枕无忧,维持原有方案。这一搁置便是近十年。

我们错了

这一切始于一份新的错误报告。问题在于我们的标准转换方法轻微改变了特殊符号 || 的语义,在 iOS 端它最终仅匹配单级子域名,而 AdGuard 所有其他版本中该符号可匹配所有层级。

解决方案其实非常简单:直接采用 WebKit 开发者在 2015 年推荐的原始正则表达式(也就是我们当年认定为“非最优”的方案)。但由于当时过度自信,我们直到最近才重新验证这个方案。

真正需要修改的规则极其简单:

  • || 转换为 ^[^:]+://+([^:/]+\.)?
  • 在多数情况下将 ^ 转换为 [/:]

但这样做真的会有巨大差异吗?事实证明,天差地别。

大错特错

换上新的正则表达式后,我们进行了快速测试,而测试结果令人震惊。Safari 中的规则加载速度不是简单得提升,而是实现了质的飞跃。

用数据说话:Safari 中跟踪保护过滤器的编译速度提升至5.5倍,基础过滤器的编译速度提升至2.8倍

为使效果更直观,请观看以下演示视频:

当我们统计过去十年 AdGuard 用户总量及其过滤器重编译次数后,发现 iOS 设备上额外浪费的 CPU 时间至少达到 5000 万小时

这个错误令我们深感惭愧,尤其是意识到正确答案始终近在眼前。回溯过往,这些新正则表达式显然比我们当初选择的方案具有更快的编译和执行速度。

我们当年的错误究竟何在?我认为根源在于存在缺陷的测试方法:我们试图“肉眼判断”,而没有做到:

  1. 明确定义评估标准:内存占用、运行速度及内容拦截器的实际浏览器表现。
  2. 最关键的是:掌握精准测量这些指标的方法(不应依赖活动监视器或 top 命令的粗略观察,而需使用专业分析工具)

值得庆幸的是,这个问题现已解决。衷心希望我们已汲取必要教训,未来不再犯类似的错误。

喜欢这篇文章吗?
20,716 20716 用户评论
完美!

AdGuard Windows版

Windows 版 AdGuard 不只是广告拦截程序,它是集成所有让您享受最佳网络体验的主要功能的多用途工具。其可拦截广告和危险网站,加速网页加载速度,并且保护儿童的在线安全。
下载本程序表示您接受 许可协议 的条款
阅读更多
AdGuard Windows版 7.21 版本,14 天的试用期
20,716 20716 用户评论
完美!

AdGuard Mac版

Mac 版 AdGuard 是一款独一无二的专为 MacOS 设计的广告拦截程序。除了保护用户免受浏览器和应用程序里恼人广告的侵扰外,应用程序还能保护用户免受跟踪、网络钓鱼和诈骗。
下载本程序表示您接受 许可协议 的条款
阅读更多
AdGuard Mac版 2.17 版本,14 天的试用期
20,716 20716 用户评论
完美!

AdGuard Android版

安卓版的 AdGuard 是一个用于安卓设备的完美解决方案。与其他大多数广告拦截器不同,AdGuard 不需要 Root 权限,提供广泛的应用程序管理选项。
下载本程序表示您接受 许可协议 的条款
阅读更多
扫码下载
可以使用任何一款 QR 码阅读器
AdGuard Android版 4.11 版本,7 天的试用期
20,716 20716 用户评论
完美!

AdGuard iOS版

用于 iPhone 和 iPad 的最佳 iOS 广告拦截程序。AdGuard 可以清除 Safari 中的各种广告,保护个人隐私,并加快页面加载速度。iOS 版 AdGuard 广告拦截技术确保最高质量的过滤,并让用户同时使用多个过滤器。
下载本程序表示您接受 许可协议 的条款
阅读更多
扫码下载
可以使用任何一款 QR 码阅读器
AdGuard iOS版 版本 4.5
20,716 20716 用户评论
完美!

AdGuard 内容拦截程序

AdGuard 内容拦截器可以全面屏蔽所有支持内容拦截技术的移动浏览器中的广告,目前包括 Samsung Internet 浏览器和 Yandex 浏览器。虽然其功能相比 Android 版 AdGuard 有所限制,但它完全免费、安装简单且拦截高效。
下载本程序表示您接受 许可协议 的条款
阅读更多
AdGuard 内容拦截程序 版本 2.8
20,716 20716 用户评论
完美!

AdGuard 浏览器扩展

AdGuard 是快速的、小内存的广告拦截扩展,可高效拦截所有网页上的各种广告!选择所需的 AdGuard 浏览器扩展,您可进行无广告、快速、安全的浏览。
AdGuard 浏览器扩展 版本 5.1
20,716 20716 用户评论
完美!

AdGuard 助手

AdGuard 桌面应用 的配套浏览器扩展。它为浏览器提供了访问自定义元素阻止,将网站列入白名单或发送报告等功能
AdGuard 助手 版本 1.4
20,716 20716 用户评论
完美!

AdGuard Home

AdGuard Home 是一种基于网络的广告和跟踪器拦截解决方案。只需在您的路由器上安装一次,即可覆盖您家庭网络中的所有设备——无需额外的客户端软件。这对于各种经常威胁您隐私的物联网设备尤其重要。
AdGuard Home 版本 0.107
20,716 20716 用户评论
完美!

AdGuard Pro iOS 版

AdGuard Pro 为已经优秀的 Safari 正规版本提供了更卓越的广告拦截服务。通过自定义 DNS 设置可拦截各种广告、保护儿童远离成人内容和保持您个人数据的安全。不过很抱歉,由于中国国内的一些限制,AppStore 暂不提供该应用程序,因此中国地区苹果 ID 账号的用户暂时无法下载 AdGuard Pro。
下载本程序表示您接受 许可协议 的条款
阅读更多
AdGuard Pro iOS 版 版本 4.5
20,716 20716 用户评论
完美!

AdGuard Safari 版

由于 Apple 开始强制要求开发者使用其新的 SDK,面向 Safari 提供的广告拦截扩展正面临一段艰难时光。AdGuard 扩展正致力于将高质量广告拦截功能重新带给 Safari 用户。
AdGuard Safari 版 版本 1.11
20,716 20716 用户评论
完美!

AdGuard Android TV 版

Android TV版 AdGuard 是唯一一款能拦截广告、保护隐私并充当智能电视防火墙的应用程序。获取网络威胁警告,使用安全 DNS,并受益于加密流量。有了安全性和零广告的使用体验,用户就可以尽情享受最喜爱的节目了!
AdGuard Android TV 版 版本 4.11
20,716 20716 用户评论
完美!

AdGuard Linux版

AdGuard Linux 版是世界上第一个系统级广告拦截器。拦截广告和跟踪器,选择预设过滤器或添加自己的过滤器。管理流程通过命令行界面实现。
AdGuard Linux版 版本 1.0
20,716 20716 用户评论
完美!

AdGuard Temp Mail

免费的临时电子邮件地址生成器,保持匿名性并保护个人隐私。你的主收件箱中不会出现垃圾邮件!
20,716 20716 用户评论
完美!

AdGuardVPN

全球 66 个地点

访问任何内容

强大加密

无记录政策

最快的连接

全年每天的支持

免费试用
下载本程序表示您接受 许可协议 的条款
阅读更多
20,716 20716 用户评论
完美!

AdGuard DNS

AdGuard DNS 是广告拦截、隐私保护及家长控制的简约三合一解决方案。其不但易于设置且免费,无论您使用的是何种平台或设备,都可以提供最基础的保护对抗在线广告、跟踪器及钓鱼。
20,716 20716 用户评论
完美!

AdGuard Mail

保护个人身份,避免垃圾邮件,并使用我们的别名和临时电子邮件地址保护收件箱。享受我们的免费电子邮箱转发服务和适用于所有操作系统的应用程序使用体验。
20,716 20716 用户评论
完美!

AdGuard Wallet

一个安全且私密的加密钱包,让您完全控制资产。管理多个钱包,发现数千种加密货币以存储、发送和兑换。
已开始下载 AdGuard 点击箭头指示的文件开始安装 AdGuard。 选择“打开”并点击“确定”,然后稍作等待直至文件加载完毕。在已经打开的窗口中,将 AdGuard 图标拖拽至“Applications”文件夹内即可完成安装。感谢您选择 AdGuard! 选择“打开”并点击“确定”,然后稍作等待直至文件下载完毕。然后,在打开的窗口中点击“安装”即可。感谢您选择 AdGuard!
将 AdGuard 安装到移动设备上