目录
本文以技术文章的方式回顾汤战勇老师在 SIG-编程语言测试 技术沙龙上的分享，回顾视频也已经上传 B 站：https://www.bilibili.com/video/BV1Ev411n7LK，欢迎小伙伴们点开观看。
大家好，我是来自西北大学的汤战勇，非常感谢华为编程语言实验室的邀请，很高兴有机会在这里给大家分享我们团队关于 JS 引擎测试方面的工作 ——?COMFORT?[1]。
COMFORT?(COMpiler?Fuzzing fOr javascRipT) 是我们团队提出的一个全新的编译器模糊测试框架，基于 ECMAScript Specification 来指导如何检测 JS 引擎的缺陷。COMFORT 利用了基于深度学习的语言模型的最新进展，自动生成 JS 测试代码。我们将 COMFORT 应用到 10 个主流的 JS 引擎上，在 200 小时的自动并发测试运行中，我们在被测的 10 个 JS 引擎中均发现了 bugs：共发现 158 个 JS 引擎 bugs，其中 129 个已通过验证，115 个已被修复。另外，COMFORT 生成的 21 个测试用例已经添加到官方 ECMAScript 的一致性测试套件 Test262 [2] 中。
我们已将 COMFORT 的代码和数据开源，欢迎大家试用。
#?引言?#
JS 语言是目前最流行的开发语言之一，截止 2021 年第一季度的统计，超过 4000W 的开发者，Github 上有超过 470W 的代码仓库。
除了常见的四种主流的浏览器引擎（比如 Apple Safari 中的 JavaScriptCore，Google Chrome 中的 V8，Microsoft Edge 中的 ChakraCore，Firefox 中的 SpiderMonkey），在很多的移动和嵌入式系统中还有广泛适用特定浏览器的 JS 引擎（比如 Hermes，QuickJS，Rhino，Nashorn，JerryScript，Graaljs），其中有些 JS 引擎是为了适应特定的轻量级应用。
?为了保证 JS 脚本在各个浏览器中都能够执行，开发 JS 引擎需要遵循一定的开发规范（或者是标准）。可以理解的是，和大多数程序开发人员的开发的软件一样，JS 引擎不可避免的也会产生 bugs 或者是漏洞。如何检测 JS 引擎中的 bug 是研究人员一直关注的问题。
# 如何选择 JS 引擎的测试方法?#
Bug 检测的方法有很多，常见的有?程序分析、软件测试、形式化证明?等，这些方法均能发现软件的缺陷。其中?软件测试?是目前被广泛使用的程序缺陷的检测方法，包括?黑盒测试、灰盒测试?和?白盒测试?等方法。
?模糊测试 fuzzing?是自动缺陷检测的重要的方法和途径之一 [4, 5, 6]。TSE2019 上有研究人员对目前的模糊测试的工具做了个整体的展示，我们看到，目前这个领域一直都比较热门，研究人员不断的尝试和改进已有的模糊测试方法，以求触发更多的软件缺陷。
?对于给定的编译器（JS 引擎），如果执行某一个测试用例，可能输出的结果有几种，包括正常输出、异常、Crash，以及也有可能出现执行超时情况。如果 JS 引擎运行结果 crash 或者超时，我们很容易判断引擎可能存在 bugs。但是，如果我们发现引擎输出结果、或者抛出异常，又该如何判断所输出的结果或抛出的异常是否正确呢？
?目前看来，为了检测引擎的 bugs，在模糊测试框架中，使用?差分测试?是较为有效的手段之一 [7, 8, 9]。利用?多数投票表决?的方法快速的判断哪些引擎的输出存在问题（与其它不一致的行为），然后加以验证。
#?设计 JS 引擎的模糊测试用例生成技术?#
如何产生有效的高质量的测试用例一直是目前模糊测试面临的挑战。?对于 JS 引擎的差分模糊测试而言，其用例由?程序?和相应的?输入?两方面构成，且测试用例的输入对于被测对象的代码覆盖尤其重要。所以，从一定程度上讲，生成正确的输入较为困难。但同时，我们也发现输入类型正确的数据对发现引擎的 bugs 非常重要。
?如何能够输入类型正确的数据呢？我们首先想到了?JS 引擎的开发规范，我们希望通过利用标准来知道测试用例中数据的生成，从而产生高质量的测试用例。
以一个简单的 case 为例，这是一个由 GPT-2 预训练模型生成的例子：
function foo(str, start, len) {
var ret = str.substr(start, len);
return ret;
}
var s = "Name:?Albert";
var pre = "Name:?";
var len = undefined;
var name = foo(s, pre.length, len);
print(name);其中，str.substr()?是一个 API 函数，用于提取?str?的子字符串，从?start?参数定义的位置开始，扩展到给定数量（由接口中参数?len?定义）的字符。如果传入合适的变量类型和值，就有可能提升模糊测试的效率。那么我们应该怎样来实现这一目标呢？我们把目光转向了?ECMAScript Specification?[10] 中该接口的规则定义：
// Expected behavior of the substr function defined in the ECMAScript 2015 specification.
String.prototype.substr(start, length)
…
1. Let S be ToString(O).
2. ReturnIfAbrupt(S).
3. Let intStart be ToInteger(start).
4. ReturnIfAbrupt(intStart).
5. If length is undefined, let end be +∞; else let end be ToInteger(length).
6. ReturnIfAbrupt(end).
7. Let size be the number of code units in S.
8. If intStart <0, let intStart be max(size + intStart, 0).
9. Let resutLength be min(max(end, 0), size - intStart).
10. If resutLength ≤ 0, return the empty String " ".
11. Return a String containing resutLength consecutive code units from …通过分析?ECMA-262?中对应的规则（即上述规则中的第五条）发现，若参数长度（代码示例中的?len）未定义，函数应从字符串的开始提取子字符串。因此，上述示例代码的运行结果应该是打印?Albert?作为输出。
在大多数我们测试过的 JS 引擎上，的确输出了满足预期的结果（比如 Google V8 [11]，ChakraCore [12]，JavaScriptCore [13]，SpiderMonkey [14]）。然而, 最新版本的 Rhino JS 引擎 [15] 执行此示例代码后，会打印一个空字符串，这里就是一个标准的一致性错误（Conformance Bug）。
要生成能暴露该 bug 的测试用例，fuzzer 需要知道代码的上下文，比如，需要生成一个?String?对象，并且需要满足?len?在传递到?substr?之前是未定义的（即上述规则中的第六条）。而现有的编译器 fuzzer 很难生成这样的测试用例，因为一般情况下 fuzzer 使用一种生成策略将随机值赋值给变量，但在使用变量前简单地将其保留为未定义，而不考虑其上下文的话会触发很多正确处理过的运行时异常。
COMFORT?通过使用?ECMA-262?来指导人工提取标准的规则，从而高效地找到?参数类型?和?对应的边界条件的值，成功地生成可暴露 Rhino 中该 bug 的测试用例，该用例并未在原本的 Test262 测试套中。
#?测试方法的详细说明?#
图 8 简单展示了?COMFORT?测试方法及用例生成技术的大致思路：
?COMFORT?的设计目的是使用语言规范来指导测试用例的生成。具体来讲：
-
以开源的预训练模型 GPT-2 [16] 作为程序生成模型，利用从 GitHub中 爬取的 JS 程序作为语料库，通过函数提取、语法过滤等预处理操作，重新训练 GPT-2 模型，使得训练后的 GPT-2 模型可以生成随机 JS 程序。
-
通过解析?ECMA-262，提取类似伪代码的 JS API 规则，用以指导测试用例的生成。
-
使用生成的测试用例通过?差分测试?同时测试多个 JS 引擎 ，以少数服从多数的原则筛选出可疑执行结果。
-
利用先进的误报过滤和代码精简技术提高发现漏洞的概率，对可疑结果进行人工分析，最终定位 JS 引擎的缺陷。
#?模型训练与 JS 代码生成
?如图 9 所示，测试用例生成的步骤为：
模型选择?基于独立自然语言文档预训练过的语言模型 —— GPT-2 [16]。对比 DeepSmith [17], GPT-2 可以建模出源码中?token?之间更长的依赖关系，因此可以生成正确率更高的测试代码。
模型训练?为了收集训练数据以移植预训练的 GPT-2 来生成 JS 程序，我们在以 JS 为主要编程语言的 GitHub 项目中选择了前 4000 个星数最多的项目，提取出大约 14k 个 JS 程序。我们使用收集到的 JS 程序更新预训练 GPT-2 模型的最后两个全连接层的权重，同时保持其他层的权重不变。
JS 程序生成?使用经过训练的 GPT-2 生成 JS 测试程序。每个测试程序都包含一个 JS 函数（例如，前面代码示例中第 1-4 行的?function foo），它会调用一些标准的 JS API。
-
首先，我们会随机从包含 2000 个 function header 的 JS 代码语料库中选出一个 header（比如?
var a = function(assert) {）作为生成种子，放入 GPT-2 模型中，用以生成下一个?token。 -
我们采用了?
Top-k 采样?的方式来决定下一个?token?的选择，并将选定的?token?附加到现有的?token?上，放入 GPT-2 模型中，重复此过程生成下一个?token。 -
当匹配到括号（比如?
{?和?}），或者?<EOF>，或者合成程序超过 5000 个 tokens 时，代码生成过程终止。 -
针对每个生成的测试用例，我们使用 JSHint [18] 对代码进行了静态检查，用以移除有语法错误的无效用例。
-
实现过程中，我们还会随机保留 20% 的语法无效用例，用于测试代码的运行。
#?ECMA-262 规范分析和提取
我们实现了一个 ECMA-262 解析器，用以从 ECMA-262 规范中分析和提取 JS API 的规则。在我们的实现中，采用了 ECMA-262 文档 的 HTML 版本。解析步骤如下：
-
分析?
metadata，确定?function,?class?或者?object?的作用域。具体来说，我们使用了 Tika [19]（内容检测与分析框架），结合手写正则表达式，抽取出 HTML 文档的?metadata。例如，我们使用正则?^Let $Var be $Func$Edn$?来提取规则?Let intStart be ToInteger(start).。 -
提取后的规范按照 AST 的形式来组织。其中树的根是一个?
ECMA-262?函数、类、或对象，树的子节点为针对特定对象或函数的规则。AST 上使用特殊的属性标记出?边界条件?与?字面值范围。图 11 展示出基于前面给出的?String.prototype.substr(start, length)?规范而生成的 AST。
图 11：使用特殊属性标记 AST 上的边界条件与字面值 -
被标记过边界条件和字面值范围的 AST 会以 JSON 的格式存储。
//?图?11?中?AST?对应的?JSON?文件 { ??"String?.?prototype?.?substr":?[{ ??"name":?"start", ??"type":?"integer", ??"values":?[1,?-1,?"NaN",?0,?"Infinity",?"-Infinity"], ??"scopes":?[0], ??"conditions":?["start?<?0"] ??},?{ ??"name":?"length", ??"type":?"integer", ??"values":?["undefined",?"NaN",?0,?"Infinity",?"-Infinity"], ??"scopes":?[], ??"conditions":?["length?===?undefined"] ??}] } -
由于我们主要针对 JS API，因此提取的规则主要用于生成与 JS API 相关的测试程序变异的边界条件。当然，还有很多 JS 的语言规范是以自然语言的形式定义的。我们不会从这类规范中提取规则。
按照如是步骤，我们提取出涵盖了 ECMA-262 第 10 版（2019 年版本）中约 82% 的 API 和?object?相关的规则。
#?测试数据生成
我们的测试数据以为 JS 函数的变量赋值的形式嵌入到 JS 代码中。除了生成变量外，我们还会生成调用传入给定参数函数的代码，并打印结果。具体算法如下：
// ECMA-262-guided Test Data Generation
Input:
𝑡𝑝𝑟𝑜𝑔: A JS test case program
𝑒𝑐𝑚𝑎: A supported edition of ECMA-262
Output:
𝑇𝑛𝑒𝑤: A list of mutated test case programs
1: 𝑆𝑝𝑒𝑐𝑠 ← extractFuncSpecs(𝑒𝑐𝑚𝑎)
2: Let 𝑇𝑛𝑒𝑤 be a list
3: for 𝑠𝑡 ∈ 𝑡𝑝𝑟𝑜𝑔 do
4: if isFunc(𝑠𝑡) then
5: 𝑓𝑢𝑛𝑐𝑁𝑎𝑚𝑒 ← getFuncName(𝑠𝑡)
6: if 𝑆𝑝𝑒𝑐𝑠.containsName(𝑓𝑢𝑛𝑐𝑁𝑎𝑚𝑒) then
7: 𝑠𝑝𝑒𝑐𝑓𝑢𝑛𝑐 ← getSpecs(𝑆𝑝𝑒𝑐𝑠, 𝑠𝑡)
8: 𝑡𝑛𝑒𝑤 ← mutate(𝑡𝑝𝑟𝑜𝑔, 𝑓𝑢𝑛𝑐, 𝑠𝑝𝑒𝑐𝑓𝑢𝑛𝑐)
9: 𝑇𝑛𝑒𝑤.append(𝑡𝑛𝑒𝑤)
10: end if
11: end if
12: end for
13: return 𝑇𝑛𝑒w对于输入 JS 测试程序中的每个语句：
-
检查语句中是否包含函数调用
-
通过使用 API 名称查找 ECMA-262 数据库（第 1-7 行），找到 JS API 定义和 API 的潜在参数
-
由于测试代码生成器的训练语料库中包含了人类编写的程序，其中会包含各种 API 调用模式的代码和数据，因此生成的测试代码中可能已经包含了以不同方式调用 JS API 的代码和数据。因而，在实现过程中，我们使用了离线提取的 ECMA-262 规则来确定应传递给函数的参数数量，以及每个参数的类型和值，用以生成额外的测试数据样本。
对于每种参数类型，我们依据：
-
ECMA-262 规范的边界条件（例如，在前面的代码示例中，参数?
len?设置为?undefined），和 -
正常条件（使用随机值）
为了使变量值发生突变，我们通过遍历 JS 代码中的?控制流?和?数据流图（上述算法中的第 8 行），将传递给函数的参数与函数的定义相关联。然后将这些参数值和输入的 JS 测试程序?tprog?会存储在我们的测试用例列表（第 9 行）中。
#?差分测试
测试数据生成后，接下来就可以对各个引擎进行差分测试了。图 12 展现出在 JS 引擎上执行测试用例时，可能会出现的七种运行结果：
-
解析结果（成功或不成功）不一致时，会抛出?
Consistent Parsing Error -
忽略掉所有测试引擎无法成功解析的测试 JS 程序后，可成功被解析的 JS 程序会被执行并产生五种可能的运行时结果：
-
根据 ECMA-262 存在预期的确定性行为时，若不同 JS 引擎的执行结果不一致，则产生?
Wrong Output -
如果 JS 引擎在执行测试用例时抛出异常，则会产生?
Runtime Exception，这时需要与 ECMA-262 的预期行为进行对比，看是否在不应该引发异常时引发了异常 -
如果 JS 引擎在执行测试用例时崩溃，则抛出?
Runtime Crash -
如果 JS 测试用例在 JS 引擎上运行时在?
2t?的周期内无法终止（其中?t?是所有其他 JS 引擎返回结果的最长时间），则认为发生了?Runtime Timeout -
如果所有被测试的 JS 引擎都能成功执行，并且执行的结果是一致的，我们认为成功通过该测试用例?
Success
-
???????????
?实际的测试过程中，我们会对?Runtime Crash?与?Runtime Timeout?十分关注，这样的运行结果往往表明存在错误的编译器行为。对于其他结果，我们使用了多数投票的方式比较编译和执行的结果，用以确定哪个编译器的行为偏离了其他编译器，然后交由开发人员进行进一步的问题分析与定位。
#?测试用例裁剪
为了帮助开发人员更好更快地定位 bug，我们开发了一种简单而有效的方法来减小可暴露 bug 测试用例的大小。具体做法是：
-
遍历输入测试代码的 AST
-
迭代地删除代码结构
-
测试结果的程序是否仍然可以触发相同的编译或执行结果
重复此过程至达到某个固定点，在该固定点，代码无法进行额外的删减，同时仍然可以再现与原始测试用例相同的 bug。
另外，还有一些工具如 HDD [20] 和 Perses [21] 可用来减少测试用例。
#?过滤误报
随机生成的代码通常会产生触发相同编译器错误的测试用例。为了减少开发人员的参与，我们采用了一个自动化方案来过滤可能导致相同错误编译行为的测试用例。
具体来说，我们基于历史的可暴露 bug 测试用例构建了一个树状分类器，可以识别出已存在树中可导致相同 bug 的测试用例。图 13 展示了一个树状的三层过滤器，可以预测当前测试用例是否会触发一个已经被测过的 bug。
-
第一层中，每个节点对应一个 JS 引擎，用于检查测试用例是否会触发特定的 JS 引擎 bug
-
第二层中，每个节点对应一个 API 函数，用于检查测试用例是否会触发特定的 JS API bug
-
第三层中，每个节点会根据 JS 引擎产生的各种错误编译行为对结果进行分类
当一个测试用例在测试运行期间触发了一个 bug 行为，我们会将该测试用例遍历此树，以查看当前测试用例的路径是否已经存在与先前的测试用例集中：
-
如果是，我们认为发现了已识别过的 bug
-
如果没有，我们认为该测试用例在给定的 JS 引擎和 JS API 上触发了新的 bug
对于后一种情况，我们会根据测试用例触发的 bug 向树中添加一个新的叶子节点。
我们上述基于多维特征实现的测试用例过滤方法，已创建了一个由 2,300 个叶决策节点组成的树状知识库。这些规则已经帮助我们过滤了数以万计的重复错误编译行为，显著减少了检查测试用例以确认错误的开销和人工参与的成本，提高了差分模糊测试系统的效率。
#?实验结果展示?#
针对 10 个 JS 引擎的结果比对如下（所有被测试的 JS 引擎都声称与 ECMA-262 版本兼容）：
Bug 类型统计分析：
Bug 数量 Top 10 的 API 类型：
受影响的编译器组件有：
两个已被确认和修复的 bugs：
// Comformance bug in Rhino:
// Rhino should throw a RangeError,
// while it yields "-634619"
var foo = function(num) {
var p = num.toFixed(-2);
print(p);
};
var parameter = -634619;
foo(parameter);// Comformance bug in Hermes:
// Hermes took 30+ minutes to execute this code,
// while other engines took less than a second.
var foo = function(size) {
var array = new Array(size);
while (size--) {
array[size] = 0;
}
};
var parameter = 904862;
foo(parameter);对比当前的几种测试方法缺陷发现能力：
-
在 72 小时自动化测试运行和 3 个月的错误确认和修复窗口中，相比其他 Fuzzer，COMFORT 发现了更多 bugs。
-
与其他 Fuzzer 相比，COMFORT 生成的测试程序更大、语法正确，JS API 和分支的覆盖率更高。
参考
[1] Guixin Ye, Zhanyong Tang, Shin Hwei Tan, Songfang Huang, Dingyi Fang,Xiaoyang Sun, Lizhong Bian, Haibo Wang, and Zheng Wang. Automatedconformance testing for javascript engines via deep compiler fuzzing.CoRR,abs/2104.07460, 2021.
[2] Test262: ECMAScript Test Suite (ECMA TR/104). https://github.com/tc39/test262.
[3] GitHut 2.0 Language Stats in 2021 Q1 https://madnight.github.io/githut/#/pull_requests/2021/1
[4] Junjie Chen, Wenxiang Hu, Dan Hao, Yingfei Xiong, Hongyu Zhang, Lu Zhang, and Bing Xie. 2016. An empirical comparison of compiler testing techniques. In Proceedings of the 38th International Conference on Software Engineering (ICSE). 180–190. https://doi.org/10.1145/2884781.2884878
[5] Yang Chen, Alex Groce, Chaoqiang Zhang, Weng-Keen Wong, Xiaoli Fern, Eric Eide, and John Regehr. 2013. Taming compiler fuzzers. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 197–208. https://doi.org/10.1145/2491956.2462173
[6] Valentin Jean Marie Manes, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. 2019. The Art, Science, and Engineering of Fuzzing: A Survey. IEEE Transactions on Software Engineering (2019), 1–1. https://doi.org/10.1109/TSE.2019.2946563
[7] Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler Validation via Equivalence modulo Inputs. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 216–226. https://doi.org/10.1145/2594291.2594334
[8] Georg Ofenbeck, Tiark Rompf, and Markus Püschel. 2016. RandIR: differential testing for embedded compilers. In Proceedings of the 7th ACM SIGPLAN Symposium on Scala (Scala). 21–30. https://doi.org/10.1145/2998392.2998397
[9] Chengnian Sun, Vu Le, and Zhendong Su. 2016. Finding and analyzing compiler warning defects. In Proceedings of the 38th IEEE/ACM International Conference on Software Engineering (ICSE). IEEE, 203–213. https://doi.org/10.1145/2884781.2884879
[10] ECMAScript 2015 Specification https://262.ecma-international.org/6.0/
[11] Google V8 https://v8.dev/
[12] ChakraCore https://github.com/chakra-core/ChakraCore
[13] JavaScriptCore https://developer.apple.com/documentation/javascriptcore
[14] SpiderMonkey https://spidermonkey.dev/
[15] Rhino JS Engine with ECMAScript 2020 https://github.com/mozilla/rhino
[16] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI Blog 1, 8 (2019), 9. https://openai.com/blog/better-language-models/
[17] Chris Cummins, Pavlos Petoumenos, Alastair Murray, and Hugh Leather. 2018. Compiler fuzzing through deep learning. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA). 95–105. https://doi.org/10.1145/3213846.3213848
[18] JSHint: A JavaScript Code Quality Tool. https://jshint.com/
[19] Tika https://tika.apache.org/
[20] Ghassan Misherghi and Zhendong Su. 2006. HDD: hierarchical delta debugging. In Proceedings of the 28th International Conference on Software Engineering (ICSE). 142–151. https://doi.org/10.1145/1134285.1134307
[21] Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, and Zhendong Su. 2018. Perses: Syntax-guided program reduction. In Proceedings of the 40th International Conference on Software Engineering (ICSE). 361–371. https://doi.org/10.1145/3180155.3180236