0x00 测试

吐槽一下：这几天忙，没注意时间，居然错过了第一题。。。

先看下程序语言

随便输入点什么，查看报错内容

拖进IDA，居然被挑衅了

果然字符串没发现什么有用信息，
根据数据结构的题目，这是一个AVTrieTree
只分析过平衡二叉树，对这个树并不太了解

0x01 IDA分析

以下代码均为配合OD调试整理

程序主函数

很多赋值操作

初始化操作

TrieTree核心比较函数

0x02 OD调试

老薛语录：观察数据变化，注重大局，不拘小节

• 新建节点
  由代码可知，并未进行初始化，
  直接在0x20*4的位置保存当前节点字符串长度，
  中间会有很多无效数据，给后面分析造成很大不便，
  这里我们手动初始化置0，
  下面显示红色部分字节，大部分为手动置0；
  
  ecx传参，可知节点是一个类或结构体
  
  新建节点
  

• 插入节点
  push 子节点，ecx传入this指针
  
  this指针指向位置
  
  第一个字段为vftable虚函数表，
  
  第二个字段为根节点，指向位置大小为0x110
  
  添加节点后数据变化
  

• TrieTree比较
  节点插入完毕，根据代码可得知对树作比较
  内存中可以看到根节点下只有两个子节点
  
  跟踪节点，可以遍历到这几个字符
  kx,c,7,M,k,t,9,f
  
  
  
  
  
  
  
  
  结构如下
  
  到这基本差不多猜出了密码
  8个节点，组合成这几个单词
  kx,c7,c7m,c7mk,ct,ctf,ct9
  好像少了一个单词？
  这里还有一个小坑
  有一个单词是重复的
  通过单步跟踪找到M
  原来M使用了2次
  
  两个树比较相同后，进入下一个比较函数，
  检查字符串顺序
  
  Bingo!
  

0x03 TrieTree内存结构

经过以上分析，可得知本程序中TrieTree内存结构

• 静态节点
  
• TrieTree类
  

• TrieTree节点
  
  关于子节点数量0x20,可能存在多数组情况，静待各位大佬解析

• TrieTree参考资料
  数据结构之Trie树
  6天通吃树结构—— 第五天 Trie树
  Trie树(字典树)_实现模糊查找(支持中文)
  Trie树的数组实现原理

0x04 心得总结

对TrieTree不熟悉，到节点比较位置就卡住了，分析了一下午，没什么成果，搜索了一些相关资料，参考demo，才顺利搞定！

• 两个小坑
  1.输入的密码生成的树是局部变量，在堆栈中，并且没有初始化，垃圾数据较多，给分析造成很大不便
  2.节点的最后一个字段是以当前字符为结尾的单词数，这个容易被忽略

• 收获
  又多熟悉了一种数据结构

0x05 致谢

感谢15PB各位老师的辛勤教导~
感谢看雪各位大佬的无私分享~

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课