Cloudflare的HTML解析历史（中）

2023-10-25 23:52:22

Cloudflare的HTML解析历史（中）

luochicun 嘶吼专业版

Cloudflare的HTML解析历史（上）

本文，我们将详细介绍如何基于LazyHTML的思想构建新的流量重写器。

避免解码：一切都是ASCII

现在我们有了一个流量令牌生成器，我们想要确保它足够快，以便用户在进行解析器和转换时不会注意到页面的任何变慢。否则，它将完全绕过我们想要尝试的任何优化。

它不仅会因为解码和重新编码任何修改后的HTML内容而导致性能下降，而且还会由于确定字符编码所需的多个潜在编码信息来源(包括嗅探前1 KB的内容)而使我们的实现变得非常复杂。

HTML标准规范只允许在编码标准中定义的编码，如果仔细查看这些编码，以及对HTML规范的“字符编码”部分的说明，我们会发现除UTF-16和ISO-2022-JP以外，所有这些编码均与ASCII兼容。

这意味着任何ASCII文本都将以与ASCII中完全相同的编码形式表示，并且任何非ASCII文本将由ASCII范围之外的字节表示。此属性使我们可以安全地标记、比较甚至修改原始HTML，而无需解码甚至不知道它包含哪种特定编码，HTML语法中的所有标记边界都可能由ASCII字符表示。

我们需要通过嗅探来检测UTF-16，并且在不修改的情况下对这些文档进行解码或跳过。我们选择后者是为了避免UTF-16常见的潜在的安全敏感漏洞，幸运的是，字符编码在已知字符编码中只占不到0.1%。

不过，HTML标记化规范要求在解析期间用U+FFFD(替换字符)替换U+0000 (NUL)字符。大概是为了防止旧引擎的C实现中的漏洞而添加的，它可以将以ASCII / UTF-8 / ...编码为0x00字节的NUL字符视为字符串的结尾（以null结尾的字符串）。因为U+FFFD不在ASCII范围内，并且将由采用不同编码的不同字节序列表示。由于我们不知道文档的编码，因此将导致输出被破坏。

幸运的是，由于浏览器不同，也不必担心担心NUL字符在字符串一样：


typedef struct {
  const char *data;
  size_t length;
} lhtml_string_t;

内容类型漏洞

其实安全分析人员只想花时间解析、解码和重写实际的HTML，而不是破坏图像或JSON。因此是他们如何确定内容是否为HTML文档。你可以仅使用Content-Type作为示例吗？在源代码中留下的注释最能描述实际情况。

在撰写本文时，这是一个糟糕而可怕的地方。如果这不断变化，网站变得更加符合标准，请像我尝试的那样将其删除。许多网站使用PHP来设置Content-Type：text / html by默认。如果您不提供自己的信息，则没有错误或警告，所以大多数网站都不会去更改它并提供服务JSON API响应，私钥和图像等二进制数据使用默认的Content-Type，我们很乐意尝试解析和转换。这不仅会损害性能，还会损害性能只要内部有一些序列，就很容易破坏响应数据本身它恰好看起来像是我们感兴趣的有效HTML标签当JSON中包含有效的HTML时，情况就更糟了。我们将其视为此类，然后将随机脚本附加到末尾打破对流行网络应用至关重要的API。该***试图通过确保第一个有效字符（忽略空格和BOM）实际上是<<--增加了确实是HTML的机会。这样，我们就可以跳过一些其他的响应可以由浏览器呈现为AJAX响应的一部分，但这仍然比相反的情况好。

你可能会认为这是一种罕见的情况，然而，我们的观察表明，在Cloudflare提供的“text / html”内容类型的流量中，近25%不太可能是html。

事实证明，“text/html”内容类型提供了相当数量的XML内容，当作为html处理时，这些内容并不总是能够被正确处理。

随着时间的流逝，对二进制数据、JSON、AMP和正确识别HTML片段的紧急缓解措施导致了内容嗅探逻辑，如下所示。

可以看到，这是形式规范与现实之间分歧的一个很好的例子。

对标记名称比较优化

但是仅进行快速解析是不够的，由于我们已经具有使用解析器的输出，对其进行重写并将其反馈给序列化的功能。而且解析器具有的所有内存和时间限制也适用于此代码，因为它是同一内容处理管道的一部分。

比较已解析的HTML标记名称是一个常见需求，例如确定是否应重写当前标记。使用常规的按字节比较会比较简单，这可能需要遍历整个标记名。在大多数情况下，通过使用特殊设计的哈希算法，我们能够在大多数情况下将这个操作缩小到单个整数比较指令。

所有标准HTML元素的标记名称仅包含字母ASCII字符和1至6的数字（在带编号的标头标记中，即< h1 >-< h6 >）。标记名称的比较不区分大小写，因此我们只需要26个字符即可表示字母字符。使用与算术编码相同的基本思想，我们可以仅使用5位来表示标记名称的可能的32个字符中的每个字符，因此，在64位整数中，floor（64/5）= 12个字符适合对于所有标准标记名称和满足相同要求的任何其他标记名称而言，已足够！最重要的是，我们甚至不需要额外遍历标记名称来对其进行哈希处理，我们可以在解析标记名称时使用逐字节输入的方式来做到这一点。

然而，这个哈希算法有一个问题，但问题的根源不是那么明显：要使所有32个字符都适合5位，我们需要使用所有可能的位组合，包括00000。这意味着如果标记名的前导字符被表示出来如果设置为00000，那么我们将无法区分该字符后续重复的不同数量。

例如，考虑到‘a’被编码为00000，而 ‘b’ 被编码为00001：

幸运的是，我们知道HTML语法不允许标记名称的第一个字符为ASCII字母字符以外的任何其他字符，因此保留数字从0到5（00000b-00101b）的数字和6到31的数字（00110b- 11111b）解决了ASCII字母字符的问题。

LazyHTML

LazyHTML是一款基于Layui的极速后台开发模板，LazyAdmin以“小巧、精干、轻量”为设计理念，不用太多复杂的功能，有一套强大和稳定的Base管理机制足以，以简洁的基础Base程序+高级专业定制为开发目的。

在考虑了上述所有内容之后，创建了LazyHTML库。它是一种快速流量HTML解析器和序列化器，具有基于令牌的C-API，该令牌源自用Ragel编写的HTML5词法分析器(Lexer)。它提供了可插入的转换管道，以允许将多个转换处理程序链接在一起。

以下是转换链接的href属性的函数示例：


// define static string to be used for replacements
static const lhtml_string_t REPLACEMENT = {
   .data = "[REPLACED]",
   .length = sizeof("[REPLACED]") - 1
};
static void token_handler(lhtml_token_t *token, void *extra /* this can be your state */) {
  if (token->type == LHTML_TOKEN_START_TAG) { // we're interested only in start tags
    const lhtml_token_starttag_t *tag = &token->start_tag;
    if (tag->type == LHTML_TAG_A) { // check whether tag is of type       const size_t n_attrs = tag->attributes.count;
      const lhtml_attribute_t *attrs = tag->attributes.items;
      for (size_t i = 0; i < n_attrs; i++) { // iterate over attributes
        const lhtml_attribute_t *attr = &attrs[i];
        if (lhtml_name_equals(attr->name, "href")) { // match the attribute name
          attr->value = REPLACEMENT; // set the attribute value
        }
      }
    }
  }
  lhtml_emit(token, extra); // pass transformed token(s) to next handler(s)
}

与以前的解析器不同，它没有对HTTP存档的2382625个文档中的任何一个进行帮助，尽管0.2％的文档超出了预期的缓冲限制，因为他们实际上是JavaScript或RSS或其他类型的内容与Content-Type: text/htm的不正确搭配，并且由于任何内容都是有效的HTML5，因此解析器尝试解析例如a<b; x=3; y=4作为带有属性的不完整标记。

至于基准测试，在2016年9月，通过一个示例将HTML规范本身（7.9 MB HTML文件）转换为静态值，该示例通过将每个（仅在那些标记中有该属性）替换为HTML规范。将其与少数几个现有的和流行的HTML解析器进行了比较（仅使用令牌化模式进行了公平的比较，因此它们不需要构建AST等），下面是100次迭代的毫秒数，Lazy模式意味着我们尽可能使用原始字符串，另一个序列化每个令牌进行比较。

结果表明，LazyHTML解析器的速度大约快一个数量级。

接下来，我会接着介绍了如何基于LazyHTML的思想构建新的流量重写器。比如更易于使用的CSS选择器API，它为Cloudflare Workers HTMLRewriter JavaScript API提供了后端。

显然，使用Cloudflare Workers的开发人员希望使用与内部使用的相同的HTML重写功能，但是可以通过JavaScript API进行访问。

接下来我们将介绍在Rust中使用基于CSS选择器的API构建流式HTML重写器/解析器的过程，它用作Cloudflare Workers HTMLRewriter的后端。我们已经开源了该库（LOL HTML），因为它也可以用作独立的HTML重写/解析库。

与以前的重写器LazyHTML相比，主要的变化是双重解析器体系结构，该体系结构需要克服在将令牌传播到工作程序运行时封装/解封每个令牌的额外性能开销。下文描述了一个CSS选择器匹配引擎，该引擎是由虚拟机对正则表达式匹配的方法启发而来的。

v2：CSS选择器匹配引擎效率更高

2017年，Cloudflare推出了一个边缘计算平台——Cloudflare Workers。这样，客户要求Cloudflare Workers的开发人员在内部使用相同的HTML重写功能也就不足为奇了。Cloudflare Workers 为开发人员提供了接近客户的第三个位置来部署代码：Cloudflare 不断扩展的全球网络的边缘，因此引入了云数据中心的强大功能和灵活性，以及大规模分布式系统的冗余，而且仅在毫秒之间就能传给几乎每一位互联网用户。

这样，开发人员在Workers中重写HTML，为此你需要第三方JavaScript程序包（例如Cheerio）。由于前一篇文章中描述的延迟，速度和内存方面的考虑，这些软件包不适用于边缘的HTML重写。

JavaScript确实非常快，但是对于某些任务，它的性能仍然无法与本地代码相比——解析就是其中之一。客户通常需要缓冲页面的整个内容来进行重写，从而导致相当大的输出延迟和内存消耗，这些消耗常常超过Workers运行时强制执行的内存限制。

我们开始考虑如何在Workers中重用该技术，就解析性能而言，LazyHTML非常适合，但存在两个问题：

1.API人体工程学：LazyHTML生成HTML令牌流。这足以满足我们的内部需求，但是，对于普通用户而言，它不如Cheerio类似于jquery的API那样方便。

2.性能：尽管LazyHTML速度非常快，但与Workers运行时的集成甚至增加了更多限制。LazyHTML就像一个简单的解析-修改-序列化管道操作，这意味着它为页面的整个内容生成令牌。然后，所有这些令牌都必须传播到Workers运行时，并包装在JavaScript对象中，然后解开包装并反馈给LazyHTML进行序列化。这是一个非常耗时的操作，它将使LazyHTML的性能优势化为乌有。

配有V8的LazyHTML

LOL HTML

我们需要一种新的思路，并且要根据Workers的要求进行设计，并使用一种具有本地速度和安全保证的语言。不过，在进行解析时很容易搬起石头砸自己的脚。Rust是显而易见的选择，因为它提供了本地速度和最佳的内存安全保证，从而最大程度地减少了不受信任的输入的***面。在可能的情况下，低输出延迟的HTML rewriter (LOL HTML)使用了之前为LazyHTML开发的所有优化，比如标记名称哈希。

下一篇文章我们接着讲LOL HTML设计的各种思路，比如双解析器架构思路。

本文翻译自：https://blog.cloudflare.com/html-parsing-1/ 与 https://blog.cloudflare.com/html-parsing-2/

码农公寓