CodeAlchemist

1.与其他同类型fuzzer对比

1. LangFuzz

   通过解析最初的作为种子的JS文件，将其中的语句拆分成代码段，任何重新组合片段生成测试用例。

   由于LangFuzz在关联代码的时候不考虑JS的语义，所以会很快发生运行时错误。

2. jsfunfuzz

   不需要初始的JS文件，而是通过引用手动编写的JS语料库随机产生语法正确的JS语句。

   超过99%的生成用例会在执行三条语句后就发生运行错误。

3. Skyfire/TreeFuzz

   通过从JS种子文件的语料库构建概率语言模型，来学习JS语义，再使用模型来生成用例。

   但这种方式依赖于语言模型的准确性。鉴于JS的复杂类型系统，这种方式也不能完全解决语义问题

4. CodeAlchemist

   将种子文件中的代码分解，并约束每个碎片，使之仅在特定的情况下可以被使用

   使用数据流分析，计算每个代码块中，使用和定义的变量，并动态获取他们的类型，只有当对应的类型可以匹配上的时候，才会进行拼接

   在一些情况下，也会引发语义错误，但已经大幅降低了

   CodeAlchemist会按照JavaScript 语句的粒度分解种子文件, 针对每个块语句生成多种变体提升代码块的丰富性, 通过对多个代码块组合产生嵌套循环等结构。

   CodeAlchemist提出使用数据流分析技术确定未定义变量和已定义变量, 并结合运行时插桩技术探测已执行变量的类型。 CodeAlchemist在JavaScript代码生成过程中, 不断向代码尾部扩展代码片段, 每次扩展代码片段都会确保其中的变量在之前已经被定义并且具备正确的 类 型

2. JS语言问题

1. 面向原型的语言

一个对象实例A只需要将另一个对象实例B设置为自己的原型，就可以在运行是继承B的属性。可以通过_proto_属性来确定对象实例在运行时使用哪个原型。而由于一个对象的类型可以动态更改，所以很有可能会发生语义错误

2. 错误类型

五种运行时错误类型

eval('break');      			//语法错误
var r = new Array (4294967296); //范围错误
u;								//引用错误
var t = 10; t();				//类型错误
decodeURIComponent('%');		//URI错误

对于第一行的eval函数，语句本身在语法上是正确的，但在实际运行时会引发语法错误

3. CodeAlchemist架构

其主要包含三个部分：Seed Parser 模块将 JS seeds 分解为不同的代码块，Constraint analyzer 模块为每个代码块推断出其组合约束条件，Engine fuzzer 则根据组件约束条件池中的代码块，生成测试用例并针对目标 JS 引擎执行生成的测试用例。如果引擎崩溃，它会在文件系统上存储相应的测试用例。

4. 语义感知组件

是一种用于JS引擎的测试用例生成算法，将JS种子碎片化成若干可以组合的代码块，一个代码块就是一小段有效的JS抽象语法树.

具体而言，组合约束条件包含两种：先决条件和后置条件。先决条件是一组变量及其类型，需要预先定义这些符号从而可以在没有运行时错误的情况下执行代码块。后置条件描述了在代码块的末尾定义了哪种变量，并在后面可被其他代码块使用。