本人读论文的时候随手记录的内容，建议结合论文原文一块阅读。本人不对以下内容负任何责任

Introduction

现有工作

基于手写CFG实现样例生成，两个问题

  1. 代码覆盖率受限
  2. 语义错误严重

语义正确的fuzzer基本只能保证调用函数时的参数类型正确，但仍然会出现其他的语义错误，这些错误主要分三类：（？

  1. 兼容性错误通常由浏览器兼容性问题引起。
  2. 误用错误是由于使用了不能在语义上一起使用的生成规则，即使它们单独使用时是有效的。
  3. 当先前生成的语句中的错误影响到使用错误语句中定义的变量的后续语句时，就会出现引用错误。尽管它们的外观各不相同，但所有这些语义错误都是由模糊器输入生成过程中产生规则的不正确组合引起的。

PCSG：Production-Context Senstive Grammar生成上下文敏感语法

提取w3c中的规则并增强为含有语义信息的PSCG（自动生成PCSG

三个过程：

  1. 从W3C中提取一个CFG
  2. 利用CFG生成样本并执行
  3. 通过分析每个statement的正确性，sage可以推断接下来选择某条规则进行生成时，会不会导致语义错误
  4. 这个过程会生成PCSG，最后sage通过PCSG去生成输入

BACKGROUND & MOTIVATION

对于浏览器的生成需要结合html,css,js三种语言，因此很依赖于CFG进行样例生成

CFG定义：NTPS

扩展树定义：NTPS（？

通过迭代扩展扩展树中的非终结节点来生成一个语句。

几乎所有的浏览器fuzzer都是生成式的，浏览器的多线程导致很难准确收集覆盖率以引导变异。

挑战

fuzzer的效率取决于多样性和语义的正确率

多样性：生成规则只能涵盖一部分语义

正确率：语法不包括语义信息，容易导致语义错误

多样性：以Domato为例，首先他的生成语法无法涉及全部的css样式语法，其次，即使涉及到的语法，也无法充分的扩展其语义

正确率：只能保证调用函数时的参数类型正确。所有错误都源于对于生成规则的调用顺序不正确。（三种情况

  1. 兼容性：函数的更新
  2. 误用：可以通过在生成时考虑上下文来避免
  3. 引用错误：使用未定义的变量。（为什么定义的时候不会报错？）通过规避出现其他错误来解决

通过从W3C中提取来解决多样性的第一个问题（覆盖尽可能多的语法）（第二个问题怎么解决？

APPROACH

三个部分组成：语法提取，语义推断，输入生成

语法提取

先从W3C中提取生成规则。然后从生成规则提纯，确保规则可终止，可拓展。即确保非终结符可拓展，不扩展的可终结。

转化为规则

CSS规则1确保结构正确，2-4确保值的语法正确

  1. 根据CSS范式生成css起始规则
  2. 将css属性转换为规则
  3. 根据值的类型组合生成扩展规则
  4. 根据值在表达式后的重复生成扩展规则

HTML：

  1. 通过tag name生成起始规则
  2. 根据元素接口的声明构造元素属性的扩展规则

JS

  1. 从接口声明给变量生成读/写规则
  2. 将函数转换为调用
  3. 通过继承来田间隐式转换

添加终结符

一方面，提取的语法不保证每个非终结符都是可扩展的。另一方面，W3C规则也不能包含所有浏览器中存在的功能。浏览器可能使用不同的关键字实现相同的非标准特性。

对不同浏览器的属性处理逻辑进行数据流分析，这样能保证绝大多数的非终结符至少有一个生成队则进行扩展。

对五个例外情况进行随机生成，来保证所有非终结节点可扩展

删除非终结的扩展

尽管所有非终结可扩展，但是可能在扩展中出现回路。

采用深搜的方法。从非终结节点开始，递归的根据扩展规则扩展，直至找到一个终结节点或者一个已经被访问过的非终结节点。如果搜索树不是所有的叶子都是终结节点，就把这个非终结节点删掉。

至此为止，已经得到了一套CFG

A->B->C->B删除B？

语义推断

增强已经得到的CFG以减少语义错误。

PCSG的NTS和CFG均相同，P’改变为上下文敏感的生成规则

对于P’中的每一条规则p’，都属于P，且不属于C(p)

C是上下文检测函数

上下文：对于一条生成规则p’，其上下文ctx被定义为从起始节点S到当前非终结节点n的所有使用过的生成规则[p1,p2,…pn]

上下文检测函数：输入为ctx，输出为t/f。对Cp(ctx)在，选择p作为生成规则在ctx作为上文时会导致语义错误时，输出为false。

通过试错法来进行推测：通过CFG生成输入，评测其在浏览器中的语意正确性（分析派生树）

CFG生成输入

更改Domato使每一个生成规则被选中的可能性一致。同时保留生成的语句对应的派生树。

收集语义正确率

通过在浏览器中使用runtime error监视器实现

监视器在JS解释器之上，非入侵的检测浏览器

检查JS错误：捕捉exception

检查CSS错误：检查样式的存在

检查HTML错误：检查元素id的存在

监视器标记生成样例是否导致语义错误

建立PCSG（粒度问题？

前文已经对语义错误的样例做好了收集，通过收集到的样例，可以从中提取非法树

非法树的根是规则，根到叶节点的的路径是非法的上下文。

对于某些从来不正确的规则序列，就提取成为非法上下文树。

对于能够匹配到非法上下文树的情况，C函数返回False。

算法描述：

输入：树-结果 pairs

输出：上下文检测函数

先遍历扩展树，统计每一条数据链的执行数据。

Map S中记录每一条数据链的执行次数和语义错误次数。

处理统计的执行数据，对扩展规则构造非法树。对于树中那些从来不正确的路径，构造非法上下文树。

一条CFG规则生成的是一句话还是一个样例？一个样例

一个扩展树生成的是一个样例还是一条语句？一条语句？

怎么确定非法树的结束节点？p1-…-p2-…-p3怎么解决？（可能出现这种情况吗？

输入生成

从相应的语言中挑出S节点，如果扩展没有达到用户指定的最大长度，就随机挑选一个p进行Cp函数检查后扩展。

优点：覆盖尽可能多的语义；语义错误少，效率更高

IMPLEMENTATION

使用CSSTree项目把法转换AST再转换为CFG

EVALUATION

实验设置

实验对象：Safari，Chrome，Firefox

24小时，4核以提取PCSG

对不同版本进行fuzz，以语义正确率，达到相同覆盖率的时间，触发特定bug的时间为评价标准。每次实验运行24h，重复5次。

语法抽取统计

DISCUSSION

sofi：语法错误修复