Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Nail: A Practical Tool for Parsing and Generating Data Formats

  • 出处:OSDI 2014
  • 作者:Julian Bangert, Nickolai Zeldovich

不同版本

Motivation

本文的主要目的:解决臭名昭著的Binary data输入格式解析(parsing)问题。

输入格式的解析导致的软件漏洞比比皆是,最近著名的如Android上stagefright的系列漏洞。 论文中给出的数据显示,在论文发表的最近三年间,有15个关于ZIP文件格式的CVE被登记,其中11个是memory corruption相关,4个是parser的不一致性(inconsistency),即相同的输入存在不同的解析方式(Android master key是一个著名的例子,Java层和Native层上的解析差异性导致了恶意的APK安装包能够通过校验)。 由于文件格式解析这个业务需求广泛存在于大量的系统中,又是相对独立的一个功能模块,如果能够用一些方法产生更为健壮安全的parser,则有望极大提升当前系统的安全性。

Solution

类似编译器前端生成的工作流程(such as lex and yacc),通过提供一个文件格式描述的Domain Specific Language(DSL)来自动化生成Parser,这样就可以保证少犯错误或者不犯错误。

当前的主要问题:

  1. 不要手写parser!不要手写parser!不要手写parser!
  2. 已有的一些DSL只能将输入转换成抽象语法树(AST),而AST离程序内部使用的数据描述结构(特别是C语言这种memory unsafe的情况)之间还有很多差异性,如果不能把这个gap填起来那么还是容易出错。
  3. 已有的文件结构描述方式不完善:
    • 不能表达复杂的文件结构;
    • 文件结构内部本身的冗余(比如checksum,是可以通过数据计算出来的,就没必要单独描述它);
    • c)当output和input是一样的格式的时候,最好能够直接重用input的格式而不是再把parsing过程反过去做一遍.

作者设计了一个叫做Nail的parser generator,这个generator做到了:

  • 规定了一套grammer可以方便地描述大部分常见的binary data format,而且最为重要的是,这个描述既是抽象的格式描述,同时又和low level的layout保持很高的兼容性,也就是作者说的using a single grammar to define both the external

Format and the internal representation

  1. 通过引入dependent fields和transformations两个重要的概念,极大地简化了输入格式的描述
  2. 自动化地产生出parser,提供良好的结果,将文件格式解析问题隔离为一个独立的操作,极大降低了安全风险
    • Using Nail, we implement an authoritative DNS server in C in under 300 lines of code and grammar, and an unzip program in C in 220 lines of code and grammar, demonstrating that Nail makes it easy to parse complex real-world data formats.

解读

视频解读

作者给出了一个非常清晰的presentation,介绍Nail是如何被用于一套数据格式处理的toolchain

Nail的设计目标涵盖了数据格式定义、parser生成以及generator生成三个点。Nail提供了一套grammer描述常见的数据格式,这里它的格式和C比较类似,但是增加了很多约束条件来保证每个域的安全。Nail能根据数据格式直接生成parser和generator,parser用来将binary input转换成程序内部的数据结构,而generator可以反过来将程序内部的数据结构转换成binary output(这里假定input和output的格式一致)

Nail抓住了real world input的重要特征,并用了三大特性来对应之:第一,Nail定义的dependent fields很好地描述了binary format里面那些length field、checksum field;第二,Nail将文件视为多个stream,很好地处理了复杂层级结构的文件格式;第三,Nail用了一个抽象的transformation概念去统一描述那些binary format里面的复杂数据类型(并且告诉你可以引入外部插件来解析他们,而Nail不去直接处理这些数据)

Evaluation

测试对象:

一些网络协议格式(DNS、Ethernet、ARP、IP、UDP和ICMP)包 ZIP格式 作者用了非常少量的描述代码就重写了这些包的格式描述,并自动化生成的解析代码;生成的ZIP处理器不再受到11个已知的CVE影响,而生成的DNS解析程序经过两天的fuzzing test也没有任何异常

Performance也很好,和其它程序如Bind比起来NailDNS的效率高许多(当然作者在作报告的时候也承认和其它程序比不太公平,因为他自己生成的是一个prototype simple parser,并没有做复杂的功能)

For Developers

Github(然而已经两年没有更新,感觉后续没维护了)