Group of Software Security In Progress

One Engine to Fuzz Em All Generic Language Processor Testing With Semantic Validation

作者:Yongheng Chen∗, Rui Zhong†, Hong Hu†, Hangfan Zhang†, Yupeng Yang‡, Dinghao Wu† and Wenke Lee∗

单位:∗Georgia Institute of Technology, †Penn State University, ‡UESTC

会议:IEEE S&P 2021

论文:One Engine to Fuzz ’em All: Generic Language Processor Testing with Semantic Validation

Abstract

来自佐治亚理工学院的研究人员提出并实现了针对多种程序语言处理器的通用fuzz框架PolyGlot。通过将PloyGlot用于针对9种程序语言的21个语言处理器,作者发现了173个新的bug,其中18个获得了CVE,113个已得到修复。

1 Background

程序语言处理器的角色是将开发者编写的高级语言转换为机器代码,该过程需要保证源代码和编译后代码的语义一致性。但由于语言处理器中存在的bug,可能会将正确的源代码转换为故障代码,导致安全漏洞。本文作者研究的fuzz就是针对程序语言处理器的bug。

1.1 Language Processor

/images/2021-05-31/Untitled.png

language processor的结构和功能如图1所示,编译过程包括前端的语法解析和后端的语义行为,对应地,这两阶段会分别进行语法检查和语义检查。

图2的例子给出了C和JS代码编译过程中语法检查和语义检查的error。其中Fig.2-a和Fig2-b中的+6就是语法错误,Fig-2-a的+7-8和Fig-2-b的11-12就是语义错误。【小测试:fig2.a -O3 gcc-10, 56725 —> 27000 branches】

/images/2021-05-31/Untitled%201.png

1.2 Limitation of Current Fuzzers

在fuzz过程中,只有通过语法与语义检查的测试用例才是有意义的。现有fuzzer,或是着眼于语法正确性而导致缺乏语义正确性,或是只针对单一语言进行语义检查导致难以迁移。

  1. 语法正确性构造:
    • General-purpose mutation-based fuzzers: 对输入的比特或字节进行随机翻转,无关输入结构
    • 基于AST或IR进行high level的突变,以保证语法正确性
    • generation-based fuzzers通过模型或是语法来生成结构化的输入
  2. 语义正确性构造
    • Specialized fuzzer:如CSmith、DIE,难以拓展到其他语言
    • language-based fuzzers:如LangFuzz、Nautilus,但他们的策略只对支持大量隐式类型转换的语言有效(PHP,JS)

2 Approaches

2.1 Common Semantic Errors

作者手工分析了1500个现有特定语言的fuzzer生成的test case,总结了四类语义错误:

  1. Undefined Variables or Functions
  2. Out-of-scope Variables or Functions:作用域
  3. Undefined Types:如JS中的class和C中的struct
  4. Unmatched Types:部分语言中允许类型转换,部分语言类型严格

2.2 Authors’ Approaches

作者分两步来实现语法与语义正确:

  1. Neutralizing Difference in Programming Languages:将不同的高级语言转换成统一的IR,基于统一的IR进行统一的突变和分析,屏蔽高级语言的影响。
    • 根据语言的BNF语法,IR与源代码能互相转换
    • 设计简单的annotation,供user描述范围和类型,这也会作为IR的语义属性
  2. Improving Language Validity:对突变过程进行限制,然后对生成的test case进行语义检查来修复错误。

    突变过程保证两个层面:

    • 整个程序的语法正确性
    • 非突变部分的语义正确性【只突变local effect,即无新的定义或创造新的local scope】

    因此,在初始输入正确的情况下,语义问题仅发生在突变的部分,于是对突变部分进行语义检查和修复【相当于增量式】。利用IR的语义属性收集type和scope信息,集合成一个符号表([type, scope, name]),基于此替换错误的变量。

3 Design

作者设计的PloyGlot结构如图3所示,以BNF语法、语义注释和种子作为输入,将源代码翻译为中间语言IR,然后在IR级别进行变异,接着修复其中的语义错误,最后运行得到的测试用例。

/images/2021-05-31/Untitled%202.png

3.1 FRONTEND GENERATION

IR + BNF语法 + 语义注释

/images/2021-05-31/Untitled%203.png

3.2 CONSTRAINED MUTATION

Rule 1: Type-Based Mutation

  • Insertion
  • Deletion
  • Replacement:同类型IR statement

Rule 2: Local Mutation

  • 不添加新定义的IR
  • 创造scope的IR:虽然有新的定义,但仅在这个IR的local scope内有效,因此可以把这整个scope的IR作为整体来突变

3.3 SEMANTIC VALIDATION

  • 两种类型:基本类型和复合类型
  • Type System: PolyGlot利用type system来构造复合类型、推断变量和表达式的类型
  • Scope System: 用scope tree表示,并为每个叶节点配一个对应的symbol table
  • Validation:
    1. 除去mutation部分使用user-defined 类型的IR,以防找不到定义【如line 8】
    2. 对于每个FIXME,根据符号表的类型和范围在变量表中生成带有变量的表达式进行替换
      1. 采用自下而上的方法:先赋AnyType,然后遇到限定类型的operation再转换具体类型
      2. 走scope tree中的对应路径,收集可使用的变量
      3. 枚举可能的表达式,并选取

/images/2021-05-31/Untitled%204.png

4 Implementation

GitHub仓库:https://github.com/s3team/Polyglot

现有grammar与rule:C、PHP、JS、Solidity

/images/2021-05-31/Untitled%205.png

5 Evaluation

5.1 Generic Applicability and Identified Bugs

针对9种程序语言的21个语言处理器进行了测试,得到图2结果。然后选择【Clang of C, solc of Solidity, ChakraCore of JavaScript and php of PHP】这四种做了具体的分析。

/images/2021-05-31/Untitled%206.png

  • Case Study 1: Triggering Deep Bugs in Clang

    /images/2021-05-31/Untitled%207.png

    /images/2021-05-31/Untitled%208.png

  • Case Study 2: Control Flow Hijacking in njs

    JavaScript 中,当 JSON 解析字符串时,它接受一个处理程序来转换解析的值。

    handler处理完第一个元素后,arr的内存布局发生了变化,但未被 njs 检测到并导致类型混淆。

    njs 仍然使用旧的布局,并错误地将第一个处理的元素,即用户可控的数字,视为函数指针。然后 njs 调用该函数并发生控制流劫持

    /images/2021-05-31/Untitled%209.png

  • Case Study 3: Bypassing PHP Sandbox

    PHP 沙箱通常会禁用“shell_exec”等危险功能,以防止用户执行任意命令

    作者发现的bug利用str_replace触发越界内存写入并使解释器崩溃。攻击者可以将良性函数指针修改为危险函数指针,比如把echo的函数指针改写为shell_exec。然后调用 echo(“ls”),使之变成 shell_exec(“ls”)。通过这种方式,攻击者可以逃离沙箱并产生更严重的破坏。

    作者称在 PHP 解释器中的错误虽然没有分配给 CVE,但可能会导致严重的安全后果。

    /images/2021-05-31/Untitled%2010.png

5.2 Comparison with State-of-the-art Fuzzers

作者还对fuzz的性能指标进行了测试。通过将PolyGlot与三个通用的fuzzer(AFL、QSYM和Nautilus)、两个特定语言的fuzzer(针对C的CSmith和针对JavaScript的DIE)进行比较,作者得到了以下图表的数据。结果显示,PloyGlot在bug类型的覆盖、测试用例的正确性和代码覆盖率这三方面都有显著优势。

/images/2021-05-31/Untitled%2011.png

/images/2021-05-31/Untitled%2012.png

/images/2021-05-31/Untitled%2013.png

/images/2021-05-31/Untitled%2014.png

论文链接:[https://changochen.github.io/publication/polyglot_sp2021_to_appear.pdf](https://changochen.github.io/publication/polyglot_sp2021_to_appear.pdf)