CUTE

这篇paper的完整题目是 CUTE: A Concolic Unit Testing Engine for C

concolic = concrete + symbolic

下载链接

摘要

• 在单元测试中，argument有时会出现pointer。这时，input可看作是 memory graph
• 本paper回答“当input是 memory graph 时，如何进行自动化的单元测试？”
• 这个方法混合了symbolic和concrete execution
  • 使用这种混合物来生成测试input
  • 访问所有可能的路径
• 这个方法用 memory graph 来表示并追踪约束条件
  • 从而理解 symbolic execution 的行为
• 本文还给出了一个有效的 constraint solver
  • 帮助 incrementally 生成测试input
• 合并以上的功能，就是CUTE
  • 应用在C语言的程序上

1、Intro

• 单元测试是一种模块化测试
  • 每个unit包含一组function
  • 各个unit独立测试
  • 人工生成 test inputs 是昂贵的，而且不全面
• 为了增加 test coverage，我们寻找自动化的方法
  • 随机测试
    • 许多值是redundant，因为在执行相同的功能
    • 找到”生成bug的值“的几率极其小
  • 符号执行
    • 使用符号变量代替实际变量
    • 每个 conditional expression 决定一条 execution path
    • 程序的 feasible execution 可以组成一棵树
      • node 是 branch point
    • 目的是生成“遍历所有路径”的实际值
    • 传统的方法是 深度优先搜索+回溯法
      • 但是，对于大型或复杂的单元，精确维护和解决测试生成所需的约束在计算上是棘手的
• 前人做过的concolic：
  • 第一篇concolic的方法是，先运行用户提供的具体的 test case，生成符号化PC，再（对这些PC取反？）求解
  • 第二篇的方法是，对执行路径上的PC取交集，然后系统化的取反，获得一个 深度优先搜索。如果无法求解某个PC，那就随便扔个随机数进去
    • PC难以提取和求解，尤其是有pointer的程序
    • 比如，pointer有alias
    • 符号执行解不出来
• 本文的方法：求解近似指针约束 (approximate pointer constraints)来生成 test input
  • 核心步骤是用 logical input map 来表示所有的 input
  • 用一组 scalar symbolic variable 表示 (finite) memory graphs
  • 通过符号化执行 code 来生成 constraints
• 算法步骤
  • 1、instrument 程序
    • 添加程序执行的 function call
  • 2、用 logical input mapI生成
    • concrete memory input graph
    • 2个 symbolic state：（pointer value + primitive value）
  • 3、用2种方式运行程序，获取符号化 constraints
    • run concretely on the concrete input graph
    • run symbolically on the symbolic states
  • 4、对其中一个 constraint 取反，获得新的路径I'，并重复步骤2-4
• 秀操作
  • 本文一大贡献是把 pointer constraints 和 integer constraints 分开
    • 使得符号执行更轻量
    • 约束求解器更高效
  • 用 logical input map 简化了 pointer constraints， 从而简化了 symbolic expression
    • 比如，struct包含一个 fieldf，pointerp指向这个struct， f 表示p->f的符号变量
    • 那么p->f的 constraint 就会简化为 f 的 constraint
  • 这样可以简化对 pointer constraint 的计算
    • 比如x和y是 symbolic pointer
    • 那么 pointer constraint 可以表示为x = y或者x != y

2、程序例子

typedef struct node {
	int val;
	struct node *next;
} node;

int f(int v) {
	return 2 * v + 1;
}

int testme(node *p, int x) {
	if (x > 0)
		if (p != NULL)
			if (f(x) == p->val)
				if (p->next == p)
					ERROR;
	return 0;
}

testme这个 function 的 argument 包含一个 pointerp和intx

• 1、CUTE首先为p生成NULL值，为x生成随机数236，运行程序，获得 PC⟨x > 0, p = NULL⟩
• 2、之后取反，CUTE求解 ⟨x > 0, p != NULL⟩，生成一个新的struct，其中p->val取随机数634，p->next取确定值NULL，运行
• 3、发现f(x) == p->val还是不满足，于是再对⟨x > 0, p != NULL, 2·x + 1 = val⟩这个约束求解，运行
• 4、还是不满足，于是再对⟨x > 0, p != NULL, 2·x + 1 = val, p = next⟩这个约束求解，找到ERROR

上图是用图像解释找ERROR的四步，更直观一点

3、CUTE的构造

本节的脉络可以从本节的子标题获取

总的来说，CUTE同时 concretely and symbolically 运行程序。实际操作时，CUTE先 instrument 程序，然后进行程序执行。之后循环 concretely 执行 instrumented code

3.1 Logical Input Map

使用了逻辑内存的基本概念：每个pointer指向的值包含一个type信息和size信息

• 用上图来举例子：Input 3 可以表示为⟨3, 1, 3, 0⟩，其中
  • 第一位3表示p的`logical address
  • 第二位1表示x的值是1
  • 第三位3表示p->v的值
  • 第四位0表示p->next的值是NULL
• 同理，Input 4 可以表示为⟨3, 1, 3, 3⟩

3.2 Units and Program Model

• CUTE 一次可以对多个 fuction 进行单元测试
  • 但是客户必须指定一个 entry function
• CUTE 针对 entry function 生成 input
  • 把这个 input 当作 memory graph
  • 但是，程序运行时可能会分配更多的内存，超出初始 input 的操作范围
  • 所以，CUTE 另外生成一个 main function，使用input() function 一次分配所有的 argument，这样main就成了一个容易操作的“封闭的” function

这里文章还讲了简化和 parsing C程序的方法，我能看懂内容，但是但是不懂这个步骤出现的意义

3.3 Instrumentation

不太清楚这个instrumentation的自动化的程度，只知道是使用了CIL这个工具

3.4 Concolic Execution

• 程序在 runtime 维护2个 symbolic states A和P, 其中
  • A 把 memory locations 映射到 symbolic arithmetic expressions
  • P 把 memory locations 映射到 symbolic pointer expressions
• CUTE只维护线性的PC，比如3 * x - 2 * y >= 4

Input initialization

Symbolic Execution

• execute_symbolic(m, e)基本上就是 parsing 具体的 statement，把 expressione符号化，映射到内存中m位置
• 类似的，evaluate_predicate(p, b)是 parsing predicate

3.5 约束求解 (Constraint Solving)

• 本文的 solver 在 lp_solve 的基础上，增加了3层优化
  • (OPT 1) Fast unsatisfiability check
    • 检查PC最后一项的取反是否在PC里面
  • (OPT 2) Common sub-constraints elimination
    • 减少冗余的简单计算
  • (OPT 3) Incremental solving
    • 剔除PC中线性相关的变量
    • pointer constraints 使用了无向图来求解，notation 太复杂，没看懂

3.6 Data Structure Testing

• 把一个 data structure 当做 input 的情况，比如树和链表
• 看不懂

3.7 Approximations for Scalable Symbolic Execution

• 对于 pointers，CUTE 只做最简单的判断：等于或不等于
  • 有精度更高的方法，但是也更昂贵
  • CUTE 的功能已经很强大了，因为pointer之间的很多关系也得到了保留，比如 nodestruct里面的下一个 pointer，以及 array 里面的 pointer

4、应用与实验

• 用 CUTE 检查自己，发现了几个 memory leak
• 检查 SGLIB，发现了2个bug（各用了1秒钟）
  • 一个是当一个非空的 doubly-linked-list 与一个空 list 合并，出现了 segmentation fault
  • 另一个是一个 hash table 执行中的 infinite loop

5、相关研究

• closest paper: DART
  • DART use automated extraction of interface and ignore preconditions
  • DART handles constraints only on integer types and cannot handle programs with pointers and data structures
  • DART 生成的随机数太粗糙
  • DART proposed a simple strategy to generate random memory graphs: each pointer is either NULL or points to a new memory cell whose nodes are recursively initialized
    • this is bad, e.g., the random generation itself may not terminate

• Previous
  DART
• Next
  软工读书笔记(1)