软件测试 读paper笔记

DART

  Directed Automated Random Testing

Posted by Xiaoran on February 9, 2018

这篇paper的完整题目是 DART: Directed Automated Random Testing

下载链接

这篇paper的引用量居然达到了2247，也是没sei了

摘要

  • DART这个工具分为3部分
    • 通过静态解析原代码，自动化的提取一个程序与使用环境相关的 interface
    • 自动化的为这个 interface 生成一个测试器，用随机测试来模拟程序最通用的使用环境
    • 用随机值来动态分析程序，自动化的生成新的 input，把程序执行 系统化的引导到不同的路径
  • 由此，软件测试可以实现完全自动化
    • 测试期间，DART 检测各种常规 error
      • 程序崩溃
      • assertion violation
      • non-termination

1、Intro

  • 美国每年花费6百亿$用于软件测试
  • 单元测试的功能是 覆盖所有的 corner case
    • 实际操作中，很少有单元测试，因为又难又贵
      • 因为要写测试器 + 改code来模拟单元的使用环境
    • 之后的几层测试（feature、integration、system）不测试 corner case
      • 这几层测试把组件当做黑盒
      • 从而忽略了（源于 corner case 的）影响系统稳定性的 bug
  • DART主要解决“单元测试难”这个问题
    • 用 C语言 实现
    • 成功发现了著名的漏洞 （见 section 4）
  • DART 改进了 random testing
    • 对于特定的值/branch，随机选到的概率很低
      • 比如if (x == 10) then ...
    • DART 进行了2方面的改进
      • 1、通过“自动化提取的interface”来自动化进行random testing（上文的步骤1）
      • 2、通过“动态测试生成”来引导不同的路径（上文的步骤3）
        • 把if (x == 10) then ...的thenbranch概率提高到 0.5
  • DART 改进了 static analysis
    • 现有的 code inspection 很不好用
      • 就是通过 静态的分析原代码 来debug
      • 现有的工具的 false alarm 太多了，生产环境没法用
      • 需要大量的人工识别，成本高
    • DART 提供另一种思路：高精度的自动化动态分析
      • 找到的每一个bug都是“真实的”
      • 在两方面碾压 静态分析
        • interprocedural bug
        • 来自 library 的 function 的 bug
    • DART 也有很大的局限性
      • 跑程序的计算时间太多
      • 动态分析的其他问题

2、DART Overview

下面的例子展示了DART用符号执行来融合 随机测试 和 动态测试生成

2.1 问题背景

int f(int x) { 
	return 2 * x; 
}
int h(int x, int y) {
	if (x != y)
		if (f(x) == x + 10)
			abort();	/* error */
	return 0;
}
  • 问题
    • h有缺陷，因为它会导致abort
    • 但是随机的输入x和y很难发现bug
  • DART 进行 directed search
    • 1、首先拿一个随机input来跑程序
    • 2、用一个vector来记录符号化的PC
    • 3、生成下一个iteration的vector，试图访问没走过的路径
    • 重复2-3，实现遍历所有的路径
  • 拿上面的程序做例子：
    • 首先随机生成x = 2691673和y = 8898015
    • 于是访问了第一个then，没访问第二个then
    • 获得了x != y 和 2 * x != x + 10 这两个 predicate
      • 或者表示为<x != y, 2 * x != x + 10>这样一个 PC
      • 这个PC代表整个 input vector 类别
    • 为了访问其他路径，DART 计算另一个PC：<x != y, 2 * x == x + 10>
    • 对上面的PC求解，得到x = 10和y = 8898015
    • 再次运行程序，访问了bug

2.2 模型定义

  • 用 DART 运行程序具备双重特性
    • 具体化：用随机的input执行实际的程序
    • 符号化：用内存中的 input变量 计算约束条件
  • 这样的运行 要求对程序P进行RAM级别的instrumentation
    • RAM 是 Random Access Memory machine
    • 是一种理想化的图灵机
    • memory M是一个映射，从地址m映射到内存里一个64位的值
    • +符号表示“更新”： M' := M + [m → v]表示在M的基础上，添加M'(m) = v的映射
    • 我们通过 内存地址 来定位一个symbolic variable
      • 因此，符号m既可以表示一个内存地址，也可以表示一个symbolic variable
    • 一个symbolic expression可以被简称为expresion(表达式)，它包含m，c(常数)，*(e', e")(乘法)，≤(e', e")(比较)，¬(e')(反)，*e'(pointer dereference)，等等
    • 程序P通过语句来操作内存
      • 条件语句if (e) then goto l'
      • 赋值语句m ← e
      • abort 程序 error
      • halt 程序正常结束
    • 设C为条件语句的集合，A为赋值语句的集合，那么程序执行的集合就是 Execs := (A ∪ C)*(abort|halt)，解释为“任何条件语句和赋值语句的混合搭配，以abort或者halt结束”
    • Execs(P)表示程序P完整的执行树，其中赋值语句的node只有1个child，条件语句的node有1或2个child。所有的leaves都是abort或者halt

2.3 测试器的具体code

  • DART的目标是遍历Execs(P)里的所有路径
  • 使用一个symbolic memoryS来把内存地址映射到语句
    • 剩下的很多细节都看不懂，大概像compiler的 syntactic analysis
  • Instrumented Program被多次运行，每次运行都参考上次运行的branching记录
    • 用done = 0表示“没访问过”，done = 1表示“访问过这一句”
    • 用branch = 0表示“运行过else”，branch = 1表示“运行过then”
    • 使用一个stack来记录所有的branch point：stack[i] = (stack[i].branch, stack[i].done)
    • Figure 2 看不懂
    • Figure 3 和 4 实现对stack的具体操作
    • Figure 5 生成新的input，访问stack里面最近没有访问过的路径
    • 可以通过修改Figure 1来提高debug的精度

2.5 DART的优势

  • 可以动态的处理protocol里面的pointer casting
  • 相比静态分析，DART可以更好的跳过unreachable bug

3、DART for C

3.1 提取Interface

  • external interface
    • 可以简单的通过 light-weight static parsing of the program’s source code 来生成
    • 很好的处理runtime生成的heap里的结构，比如链表和树

例程：空调控制程序

/* initially, room is not hot and door is open */
/* so, ac is off */
int is_room_hot = 0;
int is_door_closed = 0;
int ac = 0;

void ac_controller(int message) {
	if (message == 0) is_room_hot = 1;
	if (message == 1) is_room_hot = 0;
	if (message == 2) {
		is_door_closed = 0;
		ac=0;
	}
	if (message == 3) {
		is_door_closed = 1;
		if (is_room_hot) ac = 1;
	}
	if (is_room_hot && is_door_closed && !ac)
		abort();		/* check correctness */
}

在这个例子里，toplevel function 是ac_controller，external interface 是它的argumentmessage，它的type 是 basic typeint

  • DART可以很好的处理确定而未知的 library function
    • 处理的方法是 直接（动态）执行
    • 秒杀其他同类paper

3.2 生成随机测试器

void main() {
	for (i=0; i < depth ; i++) {
		int tmp;
		random_init(&tmp,int);
		ac_controller(tmp);
	}
}

random_init(m, type) {
	if (type == pointer to type2) {
		if (fair coin toss == head) {
			*m = NULL;
		} else {
			*m = malloc(sizeof(type));
			random_init(*m,type2);
		}
	} else if (type == struct) {
		for all fields f in struct
			random_init(&(m->f),typeof(f));
	} else if (type == array[n] of type3){
		for (int i=0;i<n;i++)
			random_init((m+i),type3);
	} else if (type == basic type) {
		*m = random_bits(sizeof(type));
	}
}
  • 用recursion初始化变量
    • 如果是basic type，那么随机赋值
    • 如果是pointer，那么50%的概率赋值NULL，50%的概率根据type赋值
    • 如果是struct，那么用recursion初始化内部的变量
  • 全面参考Section 2
  • 外加C语言专有的复杂特性
    • 看不懂
  • 本paper的constraint solver使用的是lp_solve

3.4 带来限制的假设

  • 初始化的pointer指向的是互斥的memory地址
  • 程序变量初始化良好？
  • 静态的定义interface
    • 如果是动态的，追踪起来会很复杂

4、三个实验

4.1 空调控制程序

  • 如果先输入3，再输入0，那么会出bug
  • DART只需1秒钟就能找出来，静态分析花1小时也找不到
    • 因为本程序中只有0~3这几个输入值有意义，静态分析测试了太多无意义的值

4.2 真实案例：Needham-Schroeder 协议

  • 首先，这个协议的名字不重要，可以理解为“某协议”
  • （本案例是作者展示“秀操作”）
  • 这个协议有漏洞，可以通过“中间人攻击”进行破解
  • 通过特定的模型，DART也能找到这个漏洞
  • 后来有人弥补了这个漏洞，但是DART找到了下一个漏洞
  • 再次弥补后，DART也找不到漏洞了

4.3 更大的案例：oSIP

  • 更大的秀操作：DART发现了数百个崩溃oSIP的方法
    • 其中主要是dereferencing NULL pointer
    • DART生成了一个能够远程杀死所有client和server的input

Question

  • environment
CATALOG
    FEATURED TAGS
    软件测试 读paper笔记 软件工程 读书笔记 数据挖掘 运维
    FRIENDS