稍微总结一下技术路线：

首先，被测方注册信号处理函数，并分配好信号执行的栈空间（sigaltstack）。两个处理函数，分别用于保存和恢复进程。

保存，具体来说就是把堆、栈、全局变量全都dump到文件。对于例子而言，这个文件大约是500KiB。压缩后是5KiB。

恢复，从文件中把数据再拷进来。首先不能破坏信号执行的栈区，要保留好 restore 函数的执行环境；其次要修改 restore 结束后返回的位置（主要是栈指针。pop rbp 之后，rbp要回到 dump 发生的位置）。

1
2
3
4
5
pushq %rbp // rbp 是 restore 发生时的 user_stack 上的地址
movq %rsp, %rbp  // rsp 是 ss_stack 上的地址
...
movq %rbp, %rsp
popq %rbp   // 此时需要回到 dump 发生时的 user_stack 地址。当时的栈区已全部恢复
  • 总结下来，restore 不能破坏 restore 的栈结构，但是要把 push 的 rbp 换成 dump 下来的。之后 rsp 回到正常位置后，自然会取到正确的返回地址。

问题：

1、FILE * 是分配在堆上的。这带来的问题是，恢复了上次的堆空间之后，FILE * 所指的内容随着执行进度的不同，也会发生变化

解决A：使用操作系统的文件描述符表。此处用栈上 fd 代替堆上 FILE *。仍然需要管理操作系统对象，并且不能 kill 进程，每一个分支都得保留一个 proxy 进程用来维持系统资源。尝试过感觉稍微有点困难。

  • 困难点在于，fork() 的 proxy 进程，脱离了 tracer。在有 tracer 的情况下，当 read() 系统调用被 SIGRESTORE 打断后，可以控制 read() 重新执行。在没有 tracer 的情况下，打断了就是打断了。
  • 当然我们可以直接在打断失败的调用基础上修改返回的数据，这样单一调用的结果没问题。但是文件描述符的状态就没有发生变化了。

解决B：不使用操作系统的文件描述符表，而是全部自己模拟（全模拟有大量细节要考虑。类似于 select/epoll 的行为仍不明确。但是估计最终是这样）

2、随机性的产生 （choose()）

取决于被测程序使用何种随机。考虑以下简单情况：

1
2
3
4
5
6
int devrandom;  // open("/dev/urandom", O_RDONLY);
int rand() {
    int ret;
    read(devrandom, &ret, 4);
    return ret;
}

这种还是有一个系统调用可以控制的。但是如果面对这种使用场景：

1
2
3
4
5
6
int determ = rand() % 2;
if (rand) {
    ...
} else {
    ...
}

read 的返回值很多，但是最终我们只要两个分支。根据概率分布的不同，我们可能需要走好多遍才能遍历两个分支。

故而，此类函数全都需要劫持或从代码上改写为 choose(N)。

choose(N) 要做什么？

  • 构造一棵执行路径树。每个节点都需要有可能的取值范围，这个可能需要手工确定。
  • 获取当前的执行路径。产生新的取值
  • 让被测程序走到新的节点

rand.invoke() –> 被 ptrace 截停并通知父进程 –> 父进程发信号使 rand 被拦截，并保存程序状态

–> 父进程根据当前状态查表得知此处 rand 调用的取值可能

–> 对每种可能，新启动实例并给予返回值，运行至下一个选择的状态然后被 ptrace 捕获

ptrace 如何拦截用户函数？查询符号表，在函数开头插入 0xcc，这样就会触发 SIGTRAP… 接着只需要设置 rax 作为返回值，然后 ret。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void *rand = symlookup("rand");
ptrace(PTRACE_POKEDATA, pid, rand, 0xc3cc);   // cc c3 00 00

if (WIFEXITED(wstatus) == true && WSTOPSIG(wstatus) == SIGTRAP) {
    ptrace(PTRACE_GETREGS, pid, 0, &regs);
    kill(pid, SIGDUMP);
    for (all possible val) {
        pid = fork();
        if (!pid) {
            exec() the tested;
        }
        kill(pid, SIGRESTORE);
        ptrace(PTRACE_SYSCALL, pid, 0, 0);
    	regs.rax = WANTED_BRANCH();
    	ptrace(PTRACE_SETREGS, pid, 0, &regs);
    }
}

所以这个 rand 也不是真正执行的

只要算好了 rand 的可能取值，就可以刚刚好跑过所有分支不重复。

3、怎么对其他程序应用此方案

  • 如果不用 signal handler，而是用 PEEKDATA 的方式 dump 进程，可以想象到效率
  • 但进程信号表并不能 survive execve。如果原来的 elf 里没有这个 handler，没有办法后加
  • 魔改elf感觉最稳。硬往里加text和data，有一定希望

目前就局限在 C/C++ 代码的单进程、单线程程序。

4、牵扯到线程调度怎么办

还没有调查如何控制并发调度。甚至还不知道 ptrace 一个多线程程序会发生什么。