10、数据结构逆向：数组与结构体识别、链表与树结构分析、虚函数表与C++对象模型
各位同学，今天我们聊一个硬核话题——数据结构逆向。说白了，就是你在内存里看到一堆二进制，怎么判断它是个数组、结构体，还是链表、树？甚至怎么认出C++的虚函数表？
我刚开始做逆向那会儿，最头疼的就是这个。记得有一次分析一个网络协议栈，内存里全是0x10、0x20这样的偏移量，我盯着看了三天才意识到那是个链表节点。嗯，从那以后我就总结了一套方法，今天全部分享给你们。
10.1 数组与结构体的识别
数组和结构体，是逆向中最基础的数据结构。它们的区别其实很简单：数组里所有元素类型相同，结构体里元素类型可以不同。
10.1.1 数组的识别特征
- 连续内存：数组元素在内存中是紧挨着的，没有空隙（除非有对齐要求）。
- 相同步长：每个元素占用的字节数相同。比如int数组每个4字节，char数组每个1字节。
- 索引访问：汇编代码中常见
base + index * size的模式。
实战经验：我在逆向一个游戏外挂时，发现内存里有一段连续的0x00到0xFF，步长正好是4字节。我立刻意识到这是个256长度的int数组，用来做颜色查找表。后来验证果然如此。
10.1.2 结构体的识别特征
- 成员偏移量固定：结构体每个字段的偏移量是编译时确定的。
- 对齐填充：结构体末尾或中间可能有padding字节，用来对齐到4或8字节边界。
- 成员类型多样：同一个结构体里可能有int、char、指针等不同类型。
举个例子，假设你在内存里看到这样的模式：
偏移0: 4字节整数 (0x0000000A)
偏移4: 4字节整数 (0x00000014)
偏移8: 8字节指针 (0x7FFFFFFF1234)
偏移16: 1字节字符 (0x41, 即'A')
偏移17: 7字节填充 (0x00)
偏移24: 下一个结构体开始这明显是个结构体，总大小32字节（0x20）。我习惯用IDA的"Create Struct"功能，把这些字段定义出来，逆向效率能提升好几倍。
小技巧：如果你看到某个偏移量反复出现在不同地址的相同位置，那基本可以确定这是个结构体字段。我曾经用这个方法，在半小时内还原了一个包含30多个字段的复杂结构体。
10.2 链表与树结构分析
链表和树，是动态数据结构的代表。它们不像数组那样连续存储，而是通过指针串联起来。
10.2.1 链表的逆向方法
链表的核心特征：每个节点包含数据域和指针域。单链表有一个next指针，双链表有prev和next两个指针。
怎么在内存里找到链表？我个人的经验是：
- 找循环引用：如果一个地址指向另一个地址，而那个地址又指回来，那很可能是链表。
- 找NULL终止：链表的最后一个节点，next指针通常是NULL（0x0）。
- 分析遍历代码：看汇编里有没有
while (ptr != NULL) { ptr = ptr->next; }这种模式。
注意：我曾经踩过一个坑——分析一个嵌入式固件时，发现链表节点里有两个指针，我以为是双向链表。结果后来发现，第二个指针指向的是父节点，这其实是一棵树！所以千万别看到两个指针就以为是双链表，要结合上下文判断。
10.2.2 树结构的逆向
树结构比链表复杂一些。常见的二叉树节点包含：左子指针、右子指针、数据域。红黑树还会多一个颜色标记或父指针。
识别树结构的几个关键点：
- 递归遍历：代码里如果有递归调用，并且每次传入左子或右子指针，那基本是树。
- 平衡操作：如果看到左旋、右旋、颜色翻转等操作，那肯定是平衡树（如红黑树）。
- 节点大小固定：树节点的大小通常是固定的，比如24字节或32字节。
我记得有一次逆向一个数据库引擎，内存里全是16字节的节点：4字节key、4字节value、8字节两个指针。我一看这结构，立刻判断出是二叉搜索树。后来验证，确实是用作索引的B+树简化版。
10.3 虚函数表与C++对象模型
这部分是C++逆向的重头戏。虚函数表（vtable）是C++实现多态的核心机制。
10.3.1 虚函数表的结构
每个包含虚函数的类，都有一个虚函数表。这个表本质上是一个函数指针数组。对象的内存布局中，第一个成员通常是一个指向vtable的指针（vptr）。
vtable的典型布局：
偏移0: 指向type_info对象的指针（用于RTTI）
偏移8: 第一个虚函数的地址
偏移16: 第二个虚函数的地址
偏移24: 第三个虚函数的地址
...关键点：vtable里的函数地址，顺序和类定义中虚函数的声明顺序一致。基类的虚函数在前，派生类的在后。如果派生类重写了某个虚函数，vtable里对应位置会替换成派生类的函数地址。
10.3.2 逆向识别vtable的方法
我个人习惯用以下步骤：
- 找vptr：在对象内存的第一个8字节（64位）或4字节（32位），看到一个指向代码段的指针。
- 验证vtable：顺着这个指针，看到一连串的函数地址，而且这些地址都在同一个模块的代码段内。
- 分析函数签名：vtable里的函数，通常第一个参数是this指针（ECX/RCX寄存器）。
- 识别继承关系：如果有多个vtable，或者vtable里有多个层级，那说明存在多重继承。
举个例子，假设你在内存里看到：
对象地址 0x1000: [0x4000] // vptr指向0x4000
0x4000: [0x5000] // type_info指针
0x4008: [0x6000] // 第一个虚函数
0x4010: [0x7000] // 第二个虚函数
0x4018: [0x8000] // 第三个虚函数那这个类至少有3个虚函数。如果另一个对象的vptr指向0x4100，而0x4100的内容和0x4000类似但第三个函数地址不同，那说明这是个派生类，重写了第三个虚函数。
避坑指南：我曾经遇到过一个混淆过的C++程序，vtable里插入了很多垃圾函数指针。我一开始以为这个类有几十个虚函数，后来才发现只有前3个是真的，后面的全是用来迷惑逆向分析的。所以，分析vtable时一定要结合代码调用点来验证。
10.3.3 C++对象模型总结
C++对象的内存布局，我总结成一张表：
| 场景 | 内存布局 | 说明 |
|---|---|---|
| 无虚函数的类 | 成员变量依次排列 | 和C结构体一样，没有vptr |
| 有虚函数的类 | vptr + 成员变量 | vptr在对象开头（通常） |
| 单继承 | 基类部分 + 派生类成员 | 共享一个vptr |
| 多重继承 | 多个基类子对象 + 派生类成员 | 每个基类有自己的vptr |
| 虚继承 | 包含虚基类指针 | 解决菱形继承问题 |
嗯，这里要注意：多重继承下，派生类对象会有多个vptr。每个vptr指向不同的vtable，分别对应不同的基类。这是逆向时最容易搞混的地方。
知识体系总览
下面这张图，是我自己整理的数据结构逆向知识体系。你可以把它当成一个检查清单，遇到实际问题时对照着看：
这张图把数据结构逆向分成了三条主线：静态结构（数组和结构体）、动态结构（链表和树）、C++对象模型（虚函数表）。我个人做逆向时，会先判断目标属于哪一类，然后套用对应的分析方法。
好了，今天的内容就到这里。数据结构逆向是个熟能生巧的活，多分析几个二进制文件，你自然就能一眼看出内存里藏的是什么结构。
公众号:蓝海资料掘金营，微信deep3321