011 数据结构逆向—二叉树

2979212646

                                                                                        文章目录

• 前言
• 背包数据嵌套结构
• 背包二叉树
• 二叉树分析
• 背包数据结构分析
• 总结
  

前言　　学习完了链表的数据结构，我们再通过幻想神域了解一下二叉树在游戏中的存储形式。
　　这一次要逆向的数据是背包中的所有物品，为了能将背包中的数据尽量分析完整，这个游戏建议尽量升到20级。会送两个背包扩展券，背包越大数据越多，能够分析到的数据越完整。
　　我这里是有两个背包扩展券。，一个20格扩展卷，一个5格扩展券。

011 数据结构逆向—二叉树

背包数据嵌套结构　　背包里有很多物品，每一个物品的每一个属性都可以成为突破口，最简单的当然是物品数量了。

011 数据结构逆向—二叉树

　　用CE附加游戏，扫描背包的物品数量，数据类型勾选2字节

011 数据结构逆向—二叉树

　　再次扫描，剩下三个数值，分别对这三个数值进行修改，然后重新打开背包，就能过滤出真实的地址。
　　在这个地址下两个字节的硬件访问断点，吃药让断点断下

011 数据结构逆向—二叉树

　　此时eax+28的当前物品数量，往上追eax

011 数据结构逆向—二叉树

　　ecx来源于[ecx+edi*4]

物品数量=[ecx+edi*4]+28

　　这个地方我们发现是一个数组，下断，观察edi数组下标的值，这个下标的值有下面几种变化

0-1D:30
0-4:5
0-13:20

　　三种变化分别对应自带的20个背包格子数量，5格补充背包和20格补充背包。再来看ecx数组首地址的值，也有三种变化。
　　这里其实是N+1个数组，N个扩展背包加上一个自带的背包。ecx代表的是背包对象，edi代表的是背包对象的每一个成员。
背包二叉树　　继续往上追ecx背包对象

011 数据结构逆向—二叉树

　　ecx来源于[esi+8]，esi来源于[edi+0x10]，到这里edi的值依然是变化的

物品数量=[[esi+8]+edi*4]+28
物品数量=[[[edi+0x10]+8]+edi*4]+28

011 数据结构逆向—二叉树

　　edi来源于[eax]。这里下断观察eax的值，eax的值每次断下都是不变的。
　　从这里不变化再到下面三个值发生变化，说明edi并不是来源于eax，而且代码不是顺序执行的。
　　这个地方可能是有循环。接着对这段代码进行分析，找出寄存器变化的来源。

011 数据结构逆向—二叉树

　　首先找到向上的跳转，确定循环头部和循环尾部。但是变化的eax和edi不在这个循环体内，说明这个循环和我们要追的数据没有关系

011 数据结构逆向—二叉树

　　这个循环一直在对数组下标+1，那这里应该是数组循环头部和数组循环尾部

011 数据结构逆向—二叉树

　　继续找向上的跳转，确定循环头部和循环尾部。

011 数据结构逆向—二叉树

　　变化的寄存器edi在循环体里面，不变的寄存器eax在循环外，说明这个就是我们要找的循环。

011 数据结构逆向—二叉树

　　确定好了循环，继续在循环体内追edi，edi一直到循环头部没有来源，继续在循环体下面的代码中找edi

011 数据结构逆向—二叉树

　　edi来源于[ebp-C]，

物品数量=[[[[ebp-C]+0x10]+8]+edi*4]+28

011 数据结构逆向—二叉树

　　接着追[ebp-C]，[ebp-C]在循环内也没有来源，而是来源于循环外的edi，说明edi是第一个物品对象。
　　但是[ebp-C]作为局部变量在循环内没有来源，不太可能，说明循环内有call改变了[ebp-C]。

011 数据结构逆向—二叉树

　　在这个位置下断，观察[ebp-C]的值，[ebp-C]的值现在是0x21CDE0A0，数据窗口跟随这个地址，下一个对象是0x21CDE260

011 数据结构逆向—二叉树

　　步过这个call以后再观察[ebp-C]，变成了0x21CDE260，说明我们追的背包对象的变化是来自于这个call，这个call参数放入一个背包对象，然后返回下一个背包对象。
二叉树分析　　想要得到整个数据结构的数据，有两种方法，第一种是找到根节点，直接调用call，一直取下一个对象；另外一种是根据这个对象下访问断点，找到遍历的代码。
　　这种背包结构在游戏中必定是会有代码不断访问背包数据，所以直接在这个背包对象[ebp-C]下访问断点。

011 数据结构逆向—二叉树

　　对象下断后断下的位置，eax是我们想要追的背包对象，并且这块代码是一个标准的二叉树遍历。 接着我们来分析这块代码

011 数据结构逆向—二叉树

　　首先找到循环头部和循环尾部。然后我们发现循环里面有两个跳转

011 数据结构逆向—二叉树

　　如果跳转成功，eax取[eax]]位置的值，如果跳转不成功，eax取[eax+8]的值。和之前的链表循环一样。区别在于多了一个节点，其正向代码如下：

struct node 
{
    // 左节点
    node *lc;
    // 右节点
    node *rc;
    // 数据域
    int data;
};

　　[eax]是左节点，[eax+8]是右节点

物品数量=[[[[eax]+0x10]+8]+edi*4]+28

　　eax就是二叉树的根节点，如果想要写代码遍历的话需要再把eax的基址追到。这次的目的是学习二叉树，这个过程省略。

011 数据结构逆向—二叉树

　　另外这个地方比较[eax+0x15]是否为0，不是则继续遍历，这个位置是二叉树的标志位。

左子树:[eax]
右子树:[eax+8]
标志位:[eax+0x15]

　　找到这三个东西，再分析出后面的属性偏移，就能将整个二叉树的数据遍历出来。
背包数据结构分析

物品数量=[[[[eax]+0x10]+8]+edi*4]+28

　　再回到之前的偏移表达式，简单分析一下整个数据结构

• eax作为二叉树头节点里面每一个成员都是背包对象
• [[[[eax]+0x10]+8]代表的是N个背包对象数组的首地址
• [[[[eax]+0x10]+8]+edi*4]代表的是背包中每一个物品对象
• [[[[eax]+0x10]+8]+edi*4]+XX代表的是背包中每一个物品对象的属性
  

　　对于属性的分析就比较佛系了，能看出来多少算多少，各位随缘吧~
总结　　对于二叉树和链表的分析，最关键的在于通过观察寄存器的变化，找到变化源，然后在变化原中找出循环体，并分析循环体内的代码，从而判断出程序所使用的数据结构。
　　最后，附上Github地址，里面有游戏下载链接和相关工具，需要请自取：
https://github.com/TonyChen56/GameReverseNote

---

Augus

支持学逆向论坛，资源不错！