通过时间旅行调试对二进制应用分析的技巧

❝

时间旅行调试(TTD)是一个非常有意思的topic，传统的软件调试不同，TTD会录制程序的整个运行状态，调试者可以像时间旅行一样穿梭于整个运行状态，包括浏览任意时刻内存，浏览正向/反向数据流流向等。将TTD应用到二进制分析领域可以实现一些非常Hacking的功能，比如常见的字符串加解密混淆，只要有解密逻辑，那么在某段时间内存中必定会出现明文字符串，解密过程与明文字符串都会暴露在TTD的内存分析模块下。本文讨论如何实现一个TTD, 相关代码已开源至GitHub

❞

引言

时间旅行调试(Time Travel Debug，后文简称TTD)是一个非常有意思的topic，与传统的软件调试不同，TTD会录制程序的整个运行状态，调试者可以像时间旅行一样穿梭于整个运行状态，包括浏览任意时刻内存，浏览正向/反向数据流流向等。WinDBG提供了TTD扩展，但是并不开源，而且我觉得这个扩展也不是为了二进制分析（Binary Analysis）这个研究领域做的，更像是为软件开发者定位软件BUG做的。由此就可以引出本文的内容，TTD应用到二进制分析领域的工程实践经验。

将TTD应用到二进制分析领域可以实现一些非常Hacking的功能，比如常见的字符串加解密混淆，只要有解密逻辑，那么在某段时间内存中必定会出现明文字符串，并且，在某段时间中，必然会有寄存器指向明文字符串的起始地址；再比如VMProtect的授权系统，VMP会加密机器码，使用到机器码时动态解密，那么在录制完程序的运行状态后，可以尝试在运行状态中搜索明文机器码，因为只要存在解密逻辑，那么内存中一定会出现明文机器码，再使用反向污点分析或者反向程序切片等技术，就能定位到机器码的解密逻辑，实现动态Patch机器码过验证。

要实现以上提到的Hacking功能，至少需要以下几点能力：

• 录制程序运行状态，也就是我们常说的TRACE。在本文中，我使用Intel PIN这一插桩框架完成TRACE，同时做一些优化。相比其它模块而言，这个模块是最不Hacking的，我想把它放在文章的最后描述
• 高效的内存建模算法。我们可以将程序在某一时刻的内存视为一个内存状态，程序执行一条内存访问指令后就会修改当前内存状态形成一个新的内存状态。那么有一亿条内存访问指令就会有一亿个内存状态，内存建模算法需要能高效地分析这一亿个内存状态
• 二进制程序分析引擎。最常见的二进制符号执行，污点分析，代码活跃性分析都是能够极大提升逆向体验的功能。相比于使用Triton等开源二进制分析库，我们可能需要手工实现一些二进制分析模块更好地适配我们的需求

接下来，本文会依次介绍我的TTD是如何实现内存建模，二进制程序分析引擎，以及TRACE的，同时，我的TTD的核心部分已经开源至GitHub。

内存建模

程序运行时会产生一系列内存状态。以下面3条指令为例，如果在TRACE中遇见第1条指令，我们可以知晓0x100000内存地址的DWORD值，由此就产生了一个内存状态，遇见第2条指令时，又可以知晓0x200000内存地址的DWORD值，产生了第二个内存状态，遇见第3条指令时，可以知晓0x100004内存地址的DWORD值，在我的TTD TRACE中，遇见内存写入指令，都会记录目标内存块写入前和写入后的值，由此产生了两个内存状态，分别对应写入前与写入后。因此，下面3条指令共计产生了4个内存状态。

1. mov eax, dword ptr [0x100000]
2. mov ebx, dword ptr [0x200000]
3. mov dword ptr [0x100004], ebx

在TTD TRACE时，我们没有资源去记录程序每个内存状态的所有内存，只能在发生内存访问时，记录内存访问的相关信息，如目标内存地址，访问前后的内存块内容。内存建模算法的输入就是这些内存访问信息。

内存建模时，内存以块为单位进行组织，结构体如下，block_addr是内存块的起始地址，block_memory是内存块的内容，一个内存块最长为4096字节，len是内存块的实际长度。使用std::vector<MemBlock *>储存一系列内存块，后文简称blocks。blocks中MemBlock元素顺序按照block_addr字段升序排序，升序排序的目的是查找和插入新的内存块时可以使用二分法查找，这样时间复杂度是O(logN)。

struct MemBlock {
        uint64_t block_addr; // 内存块起始地址
        uint8_t block_memory[4096]; // 内存块内容
        uint64_t len; // 内存块实际长度
};

std::vector<MemBlock *> blocks;

blocks对应程序运行时的一个内存状态，当遇见内存访问指令时，需要更新blocks也就是更新内存状态。我的实现使用了一个小trick，每次更新blocks时都以字节为单位，如果是DWORD长度的内存访问，就将它拆解为4次字节长度的内存访问，这样可以减少很多复杂的blocks调整操作。对字节长度的blocks更新步骤如下：

1. 记内存访问目标地址为addr，使用二分查找检查addr是否位于blocks中的某个内存块中, 检查条件是block_addr + len > addr && block_addr <= addr

• 如果不在blocks中，在blocks中寻找合适位置插入新的内存块, 保持block_addr升序
• 如果在blocks，更新相关内存块

2. 检查更新后的内存块是否可以与相邻内存块合并，有3种合并情况，分别是左合并，右合并，左右合并。我们记左侧内存块为l，中间内存块为m，右侧内存块为r，依次讨论几种合并情况

• 左合并：l.len + m.len <= 4096 && l.block_addr + l.len == m.block_addr
• 右合并：m.len + r.len <= 4096 && m.block_addr + m.len == r.block_addr
• 左右合并：同时满足左合并与右合并的条件，且l.len + m.len + r.len <= 4096

Q: 为什么不约定block_addr对齐4096, 按照系统内存分页机制建模, 这样就不需要内存块合并了

A: 这样做需要额外的字段记录内存块中的**实际已知内存**，比如block_memory是4096字节的数组，但是数组中并不是所有字节都是有效的，有一些内存在当前内存状态中就是未知的，需要额外的字段去记录block_memory中的有效字节

到目前为止，我们有一个blocks，blocks中以内存块为单位记录着内存状态中的已知内存。每次遇见内存访问指令时，都需要更新blocks。还是以上文提出的3条内存指令为例，3条内存指令产生了4个内存状态，假设0x100000内存地址的DWORD为0x11223344, 0x200000内存地址的DWORD为0x55667788, 写入前0x100004内存地址的DWORD为0x22334455, 写入后0x100004内存地址DWORD为0x55667788，4个内存状态的blocks更新操作如下所示，其中update_byte(addr, byte)表示更新当前内存状态中addr处的字节为byte。注意第3条指令有两个内存状态，分别对应指令执行前与执行后的内存状态。

// 指令1的内存状态更新
update_byte(0x100000, 0x11)
update_byte(0x100001, 0x22)
update_byte(0x100002, 0x33)
update_byte(0x100003, 0x44)


// 指令2的内存状态更新
update_byte(0x200000, 0x55)
update_byte(0x200001, 0x66)
update_byte(0x200002, 0x77)
update_byte(0x200003, 0x88)

// 指令3的内存状态更新
// === 更新第1个内存状态，也就是指令执行前的内存状态
update_byte(0x100004, 0x22)
update_byte(0x100005, 0x33)
update_byte(0x100006, 0x44)
update_byte(0x100007, 0x55)

// === 更新第2个内存状态，也就是指令执行后的内存状态
update_byte(0x100004, 0x55)
update_byte(0x100005, 0x66)
update_byte(0x100006, 0x77)
update_byte(0x100007, 0x88)

接下来我们讨论如何搜索程序的所有内存状态，注意我们刚刚提到的内存状态更新策略中有update_byte原语，那么要搜索一段HEX很简单，只要在每次update_byte时，在被更新的内存地址附近搜索HEX即可。我的实现非常简单，首先是根据TTD TRACE不断更新内存状态，然后实现了一个回调机制，每次更新内存状态时都会调用回调函数检查被更新的内存地址附近是否出现HEX。

// 根据TTD TRACE搜索某段HEX在所有内存状态中的出现情况
void MemoryView::search_mem(const void *pattern, uint64_t len, std::vector<MemSearchResult> &results) {
    // 新建一个内存模型    
    MemoryModel mm;
    MemorySearchArgsPass sap = {&mm, reinterpret_cast<MemRecord *>(mem), reinterpret_cast<const uint8_t *>(pattern), len, results};
    // 根据TTD TRACE更新内存状态并完成搜索
    mm.apply_with_callback(mem, this->len, search_mem_func, &sap);
}

这个内存建模的算法效率是比较高的，我实测可以轻松处理亿条指令级的TTD TRACE。

二进制程序分析

在本章节中，我们讨论一下如何集成一个污点分析引擎进入TTD以及实际应用时的各种问题。

污点分析是一种数据流分析算法，它由3个部分组成，污点源，污点传播规则，检查点。污点源指先为一些数据标记污点标签，比如为用户输入标记污点标签；污点传播规则表示根据程序指令语义建模污点标签的传播规则，比如add a, b指令的语义是 a = a + b, 那么它的污点传播规则就是 La = La ∪ Lb，表示a的污点标签是a与b的并集；检查点表示在程序执行的某个状态节点检查污点标签是否符合预期，比如在send函数处检查是否有污点数据被通过网络发送，以及在函数结尾处检查栈返回地址是否有污点数据。通过调整污点标签的粒度，比如比特位级，字节级，DWORD级等，污点分析可以在效率和准确率进行取舍，一般最常使用的是字节级的污点分析。

污点分析的理论非常有潜力，但是实际应用的时候还是存在各种问题，问题的根源在于从分析一条指令的语义到分析语句块的语义存在GAP，这种GAP会导致过污染与欠污染问题，本质上也是false positive与false negative问题。举个很常见的例子，用一上午大概学习下就能熟悉常见的汇编指令的语义，但是实际逆向时要理解一段反汇编代码的语义仍然具有一定难度。在实际应用时，污点分析存在许多失效的情况，简单归纳如下：

• 污点传播规则不严谨

在定义污点传播规则时，常常会选择偷懒，少实现一些指令的传播策略，或者简化传播规则。比如cmp a, b指令严格意义上来说需要将污点标签传播到zf, sf等标志位上，但是实现时通常会选择偷懒不处理这些问题。从对抗的角度来看，可以从这方面入手构造各种会导致过污染与欠污染的代码混淆方法

• 从污点传播规则到语句块语义存在GAP

举个最简单的例子，MBA表达式，一个很复杂的表达式，但是它的计算值恒等于某个常数。从单条指令的角度来看，它进行了一系列运算，涉及到许多污点传播过程，但是从语句块语义的角度来看，它的意义就是产生一个常数。从对抗的角度来看，从这方面入手可以轻松构造各种混淆方法使污点分析的结果完全不可用

污点分析实现时的基本范式如下，实际上就是将各种污点传播规则用代码实现

static bool taint_step(cs_insn *insn, TaintState &ts, const TraceAnalysisAMD64::InstRecord *inst) {
    cs_x86_op *ops = insn->detail->x86.operands;
    uint8_t op_count = insn->detail->x86.op_count;
    bool tainted = false;

    TaintValue tv, tv2, tv3, tv4;
    uint64_t immop;
    switch (insn->id) {
    case X86_INS_AND:
        // 如果操作数2是立即数
        if (ops[1].type == X86_OP_IMM) {
            // 根据立即数的取值做一些污点传播策略
            tv = get_op_tv(ops[0], ts, inst);
            if (tv.none()) {
                break;
                tainted = false;
            }
            immop = ops[1].imm;
            uint64_t mask = get_mask(8);
            for (uint64_t i = 0; i < ops[0].size; i++) {
                if ((immop & mask) == 0) {
                    tv[i] = 0;
                }
                mask <<= 8;
            }
            set_op_tv(ops[0], ts, inst, tv);
        }
        else {
            // 如果操作数2不是立即数, 按La = La ∪ Lb的传播规则即可
            tainted = union_taint_op(inst, ts, ops[0], ops[1], ops[0]);
        }
        break;
    case X86_INS_OR:

TRACE

我选择使用插桩框架实现TRACE，插桩是很老的topic了，互联网上也有很多教程。TRACE需要完成指令TRACE，对于内存访问指令，还要记录访问目标地址，访问长度，如果是内存读取，记录读取值，如果是内存写入，记录写入前内存值与写入值

一些演示

开源代码见GitHub, https://github.com/ddddhm1234/TTDEngine

内存搜索

TraceAnalysisAMD64 ta_amd64(ins, ins_len, mem, mem_len);

    std::vector<MemoryView::MemSearchResult> mem_occurs;
    // 搜索内存变化过程中出现过的所有 "a.exe"
    ta_amd64.mem_view.search_mem("a.exe", 5, mem_occurs);
    
    const MemRecord *memrs = reinterpret_cast<const MemRecord *>(ta_amd64.mem);

    // 打印内存状态对应的指令以及"a.exe"出现地址
    for (uint8_t i = 0; i < mem_occurs.size(); i++) {
        uint64_t inst_index = memrs[mem_occurs[i].mem_index].inst_index;
        auto dis = ta_amd64.disasm(inst_index);
        printf("%016llx: %s %s => %016llxn", dis->address, dis->mnemonic, dis->op_str, mem_occurs[i].addr);
    }

正向污点追踪

// 使用正向污点追踪出现过第一次的"a.exe"
    std::vector<uint64_t> result;
    ta_amd64.forward_taint(memrs[mem_occurs[0].mem_index].inst_index, TaintState {{mem_occurs[0].addr - 1, TaintValue(0b11111111)}}, result, 10000);
    // 打印追踪结果
    for (int i = 0; i < result.size(); i++) {
        auto dis = ta_amd64.disasm(result[i]);

        cout << result[i] << " : " << dis->mnemonic << " " << dis->op_str << endl;

        cs_free(dis, 1);
    }

字符串引用

// 列出trace中所有字符串引用
    std::vector<TraceAnalysis::StringRefResult> xrefs;
    ta_amd64.list_string_xrefs(xrefs, 20);
    for (int i = xrefs.size() - 1; i >= 0; i--) {
        // 如果是ascii字符串
        if (xrefs[i].type == 1) {
            auto dis = ta_amd64.disasm(xrefs[i].inst_index);
            printf("%016llx %s %s => %sn", dis->address, dis->mnemonic, dis->op_str, xrefs[i].str.c_str());
        }
    }

原文始发于微信公众号（中机博也车联网安全）：通过时间旅行调试对二进制应用分析的技巧