查看: 200|回复: 1

[转载图文] 011 数据结构逆向—二叉树

[复制链接]

29

主题

38

帖子

1

精华

VIP

Rank: 16

学币
365
荣耀
0
rank
200
违规
0

鬼斧神工

发表于 2020-6-9 01:40:36 | 显示全部楼层 |阅读模式
                                                                                        文章目录

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

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  用CE附加游戏,扫描背包的物品数量,数据类型勾选2字节

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  此时eax+28的当前物品数量,往上追eax

011 数据结构逆向—二叉树

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 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  ecx来源于[esi+8],esi来源于[edi+0x10],到这里edi的值依然是变化的
物品数量=[[esi+8]+edi*4]+28
物品数量=[[[edi+0x10]+8]+edi*4]+28

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  继续找向上的跳转,确定循环头部和循环尾部。

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  变化的寄存器edi在循环体里面,不变的寄存器eax在循环外,说明这个就是我们要找的循环。

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  确定好了循环,继续在循环体内追edi,edi一直到循环头部没有来源,继续在循环体下面的代码中找edi

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  edi来源于[ebp-C],
物品数量=[[[[ebp-C]+0x10]+8]+edi*4]+28

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  接着追[ebp-C],[ebp-C]在循环内也没有来源,而是来源于循环外的edi,说明edi是第一个物品对象。
  但是[ebp-C]作为局部变量在循环内没有来源,不太可能,说明循环内有call改变了[ebp-C]。

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  在这个位置下断,观察[ebp-C]的值,[ebp-C]的值现在是0x21CDE0A0,数据窗口跟随这个地址,下一个对象是0x21CDE260

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树

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

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  对象下断后断下的位置,eax是我们想要追的背包对象,并且这块代码是一个标准的二叉树遍历。 接着我们来分析这块代码

011 数据结构逆向—二叉树

011 数据结构逆向—二叉树
  首先找到循环头部和循环尾部。然后我们发现循环里面有两个跳转

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 数据结构逆向—二叉树

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


温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
嘿嘿

0

主题

56

帖子

0

精华

中级会员

Rank: 8Rank: 8

学币
94
荣耀
0
rank
0
违规
0

    发表于 2020-6-9 13:43:36 | 显示全部楼层
    支持学逆向论坛,资源不错!
    学逆向论坛-免费的逆向学习论坛
    微信公众号
    快速回复 返回顶部 返回列表