• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2011, Vol. 33 ›› Issue (4): 69-74.doi: 10.3969/j.issn.1007130X.2011.

• 论文 • 上一篇    下一篇

Hunter:一种指令集体系结构无关的二进制级动态测试用例生成技术

李根,卢凯,张英,卢锡城,冯华,张巍   

  1. (国防科学技术大学计算机学院,湖南 长沙 410073)
  • 收稿日期:2009-11-11 修回日期:2010-02-28 出版日期:2011-04-25 发布日期:2011-04-25
  • 作者简介:李根(1982),男,辽宁沈阳人,博士生,研究方向为系统软件、程序分析与验证。卢凯(1973),男,上海人,博士,教授,研究方向为系统软件。
  • 基金资助:

    国家973计划资助项目(2005CB321801 )

Hunter: ISAIndependent Binary Level Dynamic Test Generation

LI Gen,LU Kai,ZHANG Ying,LU Xicheng,FENG Hua,ZHANG Wei   

  1. (School of Computer Science,National University of Defense Technology,Changsha 410073,China)
  • Received:2009-11-11 Revised:2010-02-28 Online:2011-04-25 Published:2011-04-25

摘要:

动态测试用例生成技术是一类新兴的软件测试技术。由于使用该类技术无需任何人工干预,也无需验证人员具备任何专业知识,同时该类技术能够无误地发现程序错误,越来越多的研究者采用该技术查找预发布的二进制级软件错误。然而,已有的该类技术及其实现系统不具有可重定向性,只能处理面向某种特定指令集体系结构(ISA)的二进制代码,进行测试用例的生成与查错。本文提出了一种全新的指令集体系结构无关的二进制级动态测试用例生成技术,以及实现该技术的系统Hunter。与已有的动态测试用例生成技术不同,Hunter具有极强的可重定向性,可对任何指令集体系结构的二进制代码进行查错,定向地为其生成指向不同执行路径的测试用例。Hunter定义了一套元指令集体系结构(MetaISA),将在二进制代码执行过程中收集到的所有执行信息映射为MetaISA,并对生成的MetaISA序列进行符号化执行、约束收集、约束求解以及测试用例生成,从而使整个过程与ISA无关。我们实现了Hunter,将其重定向至32位x86、PowerPC和Sparc ISA,并使用该系统为6个含有已知错误的测试程序查错。实验结果表明,由于MetaISA的引入,只需很小的开销,Hunter系统即可容易且有效地重定向至不同的ISA,并且Hunter能够有效地发现面向32位x86、PowerPC和Sparc ISA编写的二进制应用中隐藏极深的错误。

关键词: 动态测试用例生成, 重定向, 指令集体系结构无关

Abstract:

The dynamic test generation approach is becoming increasingly popular to finding security vulnerabilities in software. More and more research institutes and organizations use this approach to find security vulnerabilities in binary code. However, the existing binary level dynamic test generation approaches and tools are not retargetable, and can only find vulnerabilities in binaries for a specific ISA. This paper presents a new binarylevel dynamic test generation technique and a tool, Hunter,which implements this technique. Unlike other such techniques that can operate only on binaries in a specific ISA, Hunter takes the binaries of any ISA as inputs and dynamically generates new inputs that exercise different control paths in the program, which may lead to security vulnerabilities. Hunter defines a meta instruction set architecture(MetaISA); Hunter maps the execution information, which is collected during the binary source code execution, to MetaISA; and symbolic execution, constraint collection and constraint solver operates on MetaISA, thus making these processes ISAindependent.We have implemented our Hunter, retargeted it to 32bit x86, PowerPC and Sparc ISAs, and used it to automatically find the six known bugs in the six benchmarks. Our results indicate that our Hunter can easily be retargeted to any ISA with only a few overheads; and Hunter can effectively find bugs located deep within large applications from their binaries for 32bit x86, PowerPC or Sparc ISA.

Key words: dynamic test generation;redirected;ISAindependent