自动生成测试用例?--带你走进Klee之路

码农世界 2024-05-18 后端 102 次浏览 0个评论

符号执行(Symbolic Execution) 属于静态分析的一种，e.g.对于函数a = malloc(), 符号执行会赋值一个符号$a 来代表 a的值,通过流程图模拟执行,而非实际执行.

一、What is Klee?

KLEE是一款开源的自动软件测试工具，基于LLVM编译底层基础，能够自动生成测试样例检测软件缺陷。

与junit不同的地方在于，KLEE能对c程序生成字节码.bc文件，并自动生成各类缺陷，不需要再自己编写。因而使用KLEE进行软件测试是比较轻松的方式。

1.1klee源码框架　

klee的核心是1个循环，每轮循环中klee会从state列表中选出1个state并执行处于该state上下文中的1个指令（参考ExecutionState.h，klee在每个状态都会记录将要执行的指令和已经执行的指令），

这个循环会持续到列表中不再有state或者用户设定的时间上限达到了。循环大致伪代码如下：

initalState = create();
stateList.add(initialState);
while (!stateList.empty() && !haltExecution){
    state = selectState(stateList); // 根据策略从列表选择状态
    executeState(state); // 符号执行，可能会fork新的state
    updateStateList(stateList); // 更新状态列表
}

当状态列表不为空或者终止条件（超时、内存超出等）没达到时循环继续。
selectState 的实现根据不同的搜索策略（DFS、BFS、RSS等）有不同的实现方式。

与普通进程不同，状态（寄存器、堆栈和堆对象）的存储位置引用表达式（树）而不是原始数据值。

大部分指令的符号执行是简洁明了的，比如 %dst = add i32 %src0, %src1，klee从寄存器 %src0 和 %src1 中获取加数并将 Add(%src0, %src1 写入寄存器 %dst。为了提高效率，构建表达式的代码检查所有给定操作数是否都是具体的（即常量，符号变量越少效率越高），如果是，则以本机方式执行操作，返回常量表达式。

条件分支是1个布尔表达式（分支条件），并根据条件是true 还是 false 更改状态的指令指针。

1.2重要函数解读

KLEE 提供了一组特殊函数（include/klee/klee.h），这些函数在符号执行的上下文中很有用。

每当程序调用这些函数之一时，KLEE 都会在内部处理调用，因此它们的内在性质。这些函数在中声明。最常用的内在对象是 klee_make_symbolic，它创建一个不受约束的符号对象。

1.2.1klee_assume(condition)

用于约束符号变量可以采用的值。程序执行的其余部分将仅考虑满足条件的变量值。从概念上讲，等价于将程序的其余部分包装在语句中，只是前者在条件不满足时打印错误。从技术上讲，为当前路径约束添加条件。

使用e.g.:
```
#include "klee/klee.h"
int main() {
  int c,d;
  klee_make_symbolic(&c, sizeof(c), "c");
  klee_make_symbolic(&d, sizeof(d), "d");
  klee_assume((c==2) && (d==3));
  return 0;
}
```
命令行使用如下：
```
$ clang -O0 -I klee_path/include/ -g -c -emit-llvm p.c -o p.bc
$ klee p.bc
```
终端显示交互结果：
```
KLEE: output directory is "/path/klee-out-0"
KLEE: Using STP solver backend
KLEE: ERROR: /path/p.c:8: invalid klee_assume call (provably false)
KLEE: NOTE: now ignoring this error at this location
KLEE: done: total instructions = 23
KLEE: done: completed paths = 2
KLEE: done: generated tests = 2
```
我们可能会期望通过程序的单一路径，而 KLEE 找到 2 条路径。

原因在于编译器处理短路运算符的方式。（什么是短路运算符？）：

短路运算符（Short-circuit operators）是指在逻辑表达式中，只要能够确定整个表达式的值，就不需要计算表达式中的所有部分。

在C和C++等编程语言中，逻辑AND（&&）和逻辑OR（||）运算符就是短路运算符。

编译后，上述代码将转换为类似于以下 C 代码的 LLVM 位码：
```
#include "klee/klee.h"
int main() {
  int c,d;
  klee_make_symbolic(&c, sizeof(c), "c");
  klee_make_symbolic(&d, sizeof(d), "d");
  
  int tmp;
  if (c == 2) 
    tmp = d == 3;
  else
    tmp = 0;
  klee_assume(tmp);
  return 0;
}
```
由于程序包含两条路径并且都是可行的，因此将调用两次：一次使用比较表达式“d == 3”，一次使用平凡常量参数“0”。

由于“0”等同于false，并且没有路径可以满足此条件，因此KLEE会打印出错误消息并终止相应的路径。

更激进的优化（例如）将程序减少到单个路径，并按预期使用表达式“c == 2 && d == 3”调用一次。请记住，符号执行引擎在内部使用表达式来表示对符号变量的计算。 the C API 仍然需要布尔条件。

顺便说一句，也可以通过将逻辑运算符和运算符替换为按位运算符来获得“单路径”行为。若要正确执行此操作，请确保所有操作数都具有布尔值且没有副作用．

1.2.2klee_prefer_cex(object, condition)

此函数告诉 KLEE 在生成测试用例作为输出时优先选择某些值。KLEE状态可以对应于许多不同的可能的测试用例。例如，在此代码中：
```
char input[4];
klee_make_symbolic(input, sizeof(input), "input");
assert(input[0] == 'Q');
```
KLEE 将有一个失败状态，对应于、和所有其他未通过断言的输入。通常，当KLEE为此失败生成测试用例时，它可以选择这些有效输入中的任何一个。结果可能是 or 或其他一些不可读的值。我们可以通过在以下情况下使用使其更具可读性：

二、How to use Klee?

2.1程序１（官方给出的样例，测试一个小函数，很典型的一个三分支）

为了用KLEE测试这个函数，我们需要在符号输入上运行它。为了将变量标记为符号变量，我们使用函数（定义于），该函数采用三个参数：要视为符号的变量的地址（内存位置）、其大小和名称（可以是任何内容）。下面是一个简单的函数，它将变量标记为符号变量并使用它来调用：
```
#include 
int get_sign(int x) {
  if (x == 0)
     return 0;
  
  if (x < 0)
     return -1;
  else 
     return 1;
} 
int main() {
  int a;
  klee_make_symbolic(&a, sizeof(a), "a");
  return get_sign(a);
}
```
KLEE 在 LLVM 位码上运行。要使用 KLEE 运行程序，首先使用将其编译为 LLVM 位码。命令行交互如下：
```
$ clang -I ../../include -emit-llvm -c -g -O0 -Xclang -disable-O0-optnone get_sign.c
```
它将创建一个 LLVM 位码格式的文件。使用该参数，以便编译器可以找到，其中包含用于与KLEE虚拟交互的内部函数的定义 ;

传递给 KLEE 的位码不应该被优化，因为我们手动挑选了更正了 KLEE 的优化，可以通过 KLEE 的命令行选项启用。但是，在较新的 LLVM 版本（> 5.0）中，在为 KLEE 编译时不应使用零标志，因为它会阻止 KLEE 从做自己的优化。

要在位码文件上运行 KLEE，只需执行：
```
$ klee get_sign.bc
```
以下输出:
```
KLEE: output directory = "klee-out-0"
KLEE: done: total instructions = 33
KLEE: done: completed paths = 3
KLEE: done: partially completed paths = 0
KLEE: done: generated tests = 3
```
我们的简单函数有三条路径，一条是，一条是小于，一条大于。

正如预期的那样，KLEE告诉我们，它在程序中探索了三条路径，并为探索的每条路径生成了一个测试用例。

对于较大的程序，由于时间或内存限制，KLEE 可能无法探索每条路径的终点。

在这种情况下，它还会通知我们中断（部分完成）路径的数量。

KLEE执行的输出是一个目录（在我们的例子中），包含KLEE生成的测试用例。

KLEE 将输出目录命名为其中的可用数字是最低的（因此，如果我们再次运行 KLEE，它将创建一个名为的目录），并且为了方便起见，还会生成一个指向该目录的符号链接：
```
$ ls klee-last/
assembly.ll      run.istats       test000002.ktest
info             run.stats        test000003.ktest
messages.txt     test000001.ktest warnings.txt
```
2.2KLEE生成的测试用例

KLEE 生成的测试用例被写入扩展名为的文件中。这些是可以使用 ktest-tool 实用程序读取的二进制文件。ktest-tool 为同一对象输出不同的表示形式，例如 Python 字节字符串（数据）、整数（int）或 ascii 文本（文本）。因此，让我们检查每个.ktest文件：
```
$ ktest-tool klee-last/test000001.ktest
ktest file : 'klee-last/test000001.ktest'
args       : ['get_sign.bc']
num objects: 1
object 0: name: 'a'
object 0: size: 4
object 0: data: b'\x00\x00\x00\x00'
object 0: hex : 0x00000000
object 0: int : 0
object 0: uint: 0
object 0: text: ....
$ ktest-tool klee-last/test000002.ktest
ktest file : 'klee-last/test000002.ktest'
args       : ['get_sign.bc']
num objects: 1
object 0: name: 'a'
object 0: size: 4
object 0: data: b'\x01\x01\x01\x01'
object 0: hex : 0x01010101
object 0: int : 16843009
object 0: uint: 16843009
object 0: text: ....
$ ktest-tool klee-last/test000003.ktest
ktest file : 'klee-last/test000003.ktest'
args       : ['get_sign.bc']
num objects: 1
object 0: name: 'a'
object 0: size: 4
object 0: data: b'\x00\x00\x00\x80'
object 0: hex : 0x00000080
object 0: int : -2147483648
object 0: uint: 2147483648
object 0: text: ....
```
在每个测试文件中，KLEE 报告调用程序的参数（在我们的例子中，除了程序名称本身之外没有参数）、

该路径上的符号对象的数量（在我们的例子中只有一个）、

符号对象的名称 ,及其大小。

实际测试本身由输入的值表示：对于第一个测试，对于第二个测试和对于最后一个测试。正如预期的那样，KLEE 生成了值、一个正值和一个负值。

2.3再运行测试用例

虽然我们可以手动（或借助现有的测试基础设施）在我们的程序上运行 KLEE 生成的测试用例，但 KLEE 提供了一个方便的重放库，它只是将调用替换为对函数的调用，该函数将存储在文件中的值分配给我们的输入。

要使用它，只需将程序与库链接，并将环境变量设置为指向所需测试用例的名称：
```
$ export LD_LIBRARY_PATH=path-to-klee-build-dir/lib/:$LD_LIBRARY_PATH
$ gcc -I ../../include -L path-to-klee-build-dir/lib/ get_sign.c -lkleeRuntest
$ KTEST_FILE=klee-last/test000001.ktest ./a.out
$ echo $?
0
$ KTEST_FILE=klee-last/test000002.ktest ./a.out
$ echo $?
1
$ KTEST_FILE=klee-last/test000003.ktest ./a.out
$ echo $?
255
```
正如预期的那样，我们的程序在运行第一个测试用例时返回，在运行第二个测试用例时返回，并在运行最后一个测试用例时返回,转换为范围内的有效退出代码值.

参考：

Intrinsics · KLEE (klee-se.org)

程序分析-klee工具分析-CSDN博客