[原创]浅谈STL容器的识别

2021-12-1 15:44 14715

[原创]浅谈STL容器的识别

windpiaoxue 活跃值

2021-12-1 15:44

14715

浅谈STL容器的识别

一、前言

在逆向由C++编写的产品时，最头疼的莫过于两个问题：虚函数和STL，前者会生成一些间接CALL，导致IDA在分析时无法进一步交叉引用，后者采用了大量模板技术，再加上编译器优化，导致比较难提取到固定的签名来识别这些函数。因此，本文打算结合源码、静态分析和动态调试，谈一谈常用的STL容器的基本原理和识别方法。

二、STL容器分析

编译环境

vs2019（v142）+ x86 + Release + MT

string

首先简单浏览一下string在源码中的内存布局，有一个大致印象。

template <class _Elem, class _Traits = char_traits<_Elem>, class _Alloc = allocator<_Elem>>
class basic_string {
private:
    using _Alty        = _Rebind_alloc_t<_Alloc, _Elem>;
    using _Alty_traits = allocator_traits<_Alty>;
    using _Scary_val   = _String_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Elem>,
        _String_iter_types<_Elem, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Elem&, const _Elem&>>>;
    // 省略若干代码
private:
    _Compressed_pair<_Alty, _Scary_val> _Mypair;
};

估计对C++不熟悉的朋友看到上面这堆代码已经懵逼了，我在这里只根据源码简单的解释一下string中的内存布局，因此看不懂的也没有关系，并不影响。

string中只有一个类成员变量_Mypair并且类型是pair（对_Compressed_pair感兴趣可以自行深入看一下，关键技术：Empty base optimization），绝大多数情况下，_Mypair在Release下的内存布局与_Scary_val（_Mypair的第二个类型）一致，_Scary_val是一个根据Alloc类型来推导出来的，具体细节不在赘述，最终找到了如下代码：

template <class _Val_types>
class _String_val : public _Container_base {
public:
    using value_type = typename _Val_types::value_type;
    using pointer    = typename _Val_types::pointer;
    using size_type  = typename _Val_types::size_type;
    // 对于string的情况下_BUF_SIZE == 16
    static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);
    // 省略若干代码
    union _Bxty { // storage for small buffer or pointer to larger one
        value_type _Buf[_BUF_SIZE];
        pointer _Ptr;
        char _Alias[_BUF_SIZE]; // TRANSITION, ABI: _Alias is preserved for binary compatibility (especially /clr)
    } _Bx;
    // 在x86下size_type = uint32_t
    size_type _Mysize; // current length of string
    size_type _Myres; // current storage reserved for string
};

现在代码已经非常清晰了，可以简单的理解为string由三个类成员变量组成：Union类型的_Bx、size_type类型的_Mysize和_Myres。现在必须要说一下string的短字符串优化（SSO）技术，string为了减少对内存的申请次数，如果字符串过短（小于16字节）则直接将字符串拷贝到自身的buffer中，如果字符串长度超过自身buffer预设的大小，则会申请一块内存来存储该字符串，自身则只记录申请的内存地址。基于源码的讲解就到这里，接下来，编译成二进制进行分析。

原始C++代码：

int main(int argc, char* argv[]) {
    std::string v1 = argv[0];
    printf("%s\n", v1.c_str());
    return 0;
}

IDA反编译代码：

// 代码从IDA中提取，为了方便解释，结构和变量名有所调整
int __cdecl main(int argc, const char **argv, const char **envp)
{
  char *v3; // edx
  const char *v4; // ecx
  void **v5; // eax
  void *v6; // ecx
  // string的内存大小为sizeof(void*) * 6
  void *str[6]; // [esp+4h] [ebp-1Ch] BYREF
 
  // 1. 初始化string
  // 将_Mysize设置成0
  str[4] = 0;
  // 将_Myres设置成15
  str[5] = (void *)15;
  // 由于C风格字符串由0结尾，因此初始化阶段将_Buf的首个字节设置成0
  LOBYTE(str[0]) = 0;
 
  // 2. 将argv[0]赋值给string
  v3 = (char *)*argv;
  v4 = *argv;
  // 具体的赋值函数
  sub_401260(str, v3, strlen(v4));
 
  // 3. 获取string的字符串首地址
  v5 = str; // 通过_Buf获取字符串首地址
  // 判断_Myres是否大于等于16
  if ( str[5] >= (void *)0x10 )
    v5 = (void **)str[0]; // 通过_Ptr获取字符串首地址
  // 打印结果
  printf("%s\n", (const char *)v5);
 
  // 4. 释放string的内存
  // 如果_Myres大于16则需要释放字符串的内存
  if ( str[5] >= (void *)0x10 )
  {
    v6 = str[0];
    // 与BigAllocation有关，本文不过多介绍
    if ( (unsigned int)str[5] + 1 >= 0x1000 )
    {
      v6 = (void *)*((_DWORD *)str[0] - 1);
      if ( (unsigned int)(str[0] - v6 - 4) > 0x1F )
        _invalid_parameter_noinfo_noreturn();
    }
    sub_4014BC(v6); // j_free的间接调用
  }
  return 0;
}

关于string的识别：

在IDA中，可以根据字符串"string too long"来进行识别，例如上面这个例子，在函数sub_401260中，有一个关于Size的判断：

void *__thiscall sub_401260(void *this, void *Src, size_t Size)
{
    // ...
    if ( Size > 0x7FFFFFFF )
        sub_4011A0();
    // ...
}
void __noreturn sub_4011A0()
{
  sub_40145B("string too long");
}

在OD/X64DBG中，可以根据内存布局来快速判断，基本有两种形式：

// 第一种，小于16字节的字符串
// _Buf[16]
012FF9AC 6C6C6548 Hell 
012FF9B0 726F576F oWor 
012FF9B4 0000646C ld.. 
012FF9B8 00855054 TP..
012FF9BC 0000000A .... // _Mysize=0000000A
012FF9C0 0000000F .... // _Myres=0000000F
 
// 第二种，大于等于16字节的字符串
// _Ptr
0133F844 013F7E88 .~?. &"C:\\Users\\Administrator\\Desktop\\stl_reverse\\test\\Release\\test.exe"
// 12个字节的未使用空间
0133F848 008515B0 °...
0133F84C 00000000 .... 
0133F850 00855054 TP..
0133F854 00000040 @... // _Mysize=00000040
0133F858 0000004F O... // _Myres=0000004F

vector

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
    using _Alty        = _Rebind_alloc_t<_Alloc, _Ty>;
    using _Alty_traits = allocator_traits<_Alty>;
    using _Scary_val   = _Vector_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Ty>,
        _Vec_iter_types<_Ty, size_type, difference_type, pointer, const_pointer, _Ty&, const _Ty&>>>;
    // 省略若干代码
    _Compressed_pair<_Alty, _Scary_val> _Mypair;
};

根据分析string的经验，可以很容易看出来_Vector_val的内存布局即是vector的内存布局

template <class _Val_types>
class _Vector_val : public _Container_base {
public:
    using pointer = typename _Val_types::pointer;
    pointer _Myfirst; // pointer to beginning of array
    pointer _Mylast; // pointer to current end of sequence
    pointer _Myend; // pointer to end of array
};

vector的实现还是非常简单的，只有三个类成员变量：_Myfirst、_Mylast和_Myend，分别指向数组的开始、有效元素的结尾和数组的结尾。vector中没有记录size，而是通过_Mylast-_Myfirst计算而来的，同理，capacity是通过_Myend-_Myfirst计算而来的。下面，我们直接看代码。

原始C++代码：

int main(int argc, char* argv[]) {
    struct Value {
        int a;
        int b;
    };
    std::vector<Value> v;
    for (int i = 0; i < argc; ++i) {
        v.push_back(Value{ i, i + 1 });
    }
    for (auto& i : v) {
        printf("%d, %d\n", i.a, i.b);
    }
    return 0;
}

IDA反编译代码：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  _DWORD *v3; // ecx
  DWORD v4; // esi
  DWORD v5; // ebx
  int v6; // edi
  int v7; // eax
  _DWORD *v8; // edi
  char *v9; // eax
  int v11; // [esp+10h] [ebp-24h] BYREF
  DWORD v12; // [esp+14h] [ebp-20h]
  DWORD v13[3]; // [esp+18h] [ebp-1Ch] BYREF
  int v14; // [esp+30h] [ebp-4h]
 
  v3 = 0;
  v4 = 0;
  v12 = 0;
  v5 = 0;
  // 1. 初始化vector
  v13[0] = 0; // _Myfirst
  v13[1] = 0; // _Mylast
  v13[2] = 0; // _Myend
  v6 = 0;
  v14 = 0;
 
  // 2. for (int i = 0; i < argc; ++i)
  if ( argc > 0 )
  {
    do
    {
      v7 = v6++;
      v11 = v7;
      v12 = v6;
      // v4代表_Mylast
      // v5代表_Myend
      if ( v4 == v5 ) // 判断一下是否有足够的空间
      {
        // 没有足够的空间容纳新的Value，调用sub_401300分配新的内存并将Value push到最后
        // sub_401300对应vector源码中的_Emplace_reallocate
        sub_401300((const void **)v13, (_BYTE *)v4, &v11);
        v5 = v13[2];
        v4 = v13[1];
      }
      else
      {
        // 有足够的空间容纳新的Value，不需要重新分配内存
        *(_DWORD *)v4 = v7; // 设置Value::a
        *(_DWORD *)(v4 + 4) = v6; // 设置Value::b
        v4 += 8;
        v13[1] = v4; // _Mylast++
      }
    }
    while ( v6 < argc );
    v3 = (_DWORD *)v13[0];
    v12 = v13[0];
  }
  v8 = v3;
 
  // 3. for (auto& i : v)
  // 具体遍历过程比较直观，就是对线性数组的遍历，不再给出详细解释
  if ( v3 != (_DWORD *)v4 )
  {
    do
    {
      // v8代表_Myfirst
      sub_401010("%d, %d\n", *v8, v8[1]);
      v8 += 2;
    }
    while ( v8 != (_DWORD *)v4 );
    v3 = (_DWORD *)v12;
  }
 
  // 4. 释放vector的内存
  if ( v3 )
  {
    v9 = (char *)v3;
    if ( ((v5 - (_DWORD)v3) & 0xFFFFFFF8) >= 0x1000 )
    {
      v3 = (_DWORD *)*(v3 - 1);
      if ( (unsigned int)(v9 - (char *)v3 - 4) > 0x1F )
        _invalid_parameter_noinfo_noreturn();
    }
    sub_40159B(v3);
  }
  return 0;
}

关于vector的识别：

在IDA中，可以采用和string相同的方式来识别vector，使用vector后编译会产生"vector too long"的字符串

_DWORD *__thiscall sub_401300(const void **this, _BYTE *a2, _DWORD *a3)
{
  // ...
  // 通过2^32 / 0x1FFFFFFF计算得出8即是该vector的元素大小
  if ( v4 == 0x1FFFFFFF )
    sub_401460();
  // ...
}
void __noreturn sub_401460()
{
  sub_40153A("vector too long");
}

在OD/X64DBG中，可以根据内存布局来快速判断，vector只有一种形式：

// vector内存布局
005EFB2C 00878470 p... // _Myfirst
005EFB30 00878478 x... // _Mylast
005EFB34 00878478 x... // _Myend
 
// vector指向的数组内存
00878470 00000000 .... 
00878474 00000001 ....

在最后，顺便说一下vector的内存分配策略，直接上源码：

size_type _Calculate_growth(const size_type _Newsize) const {
    // given _Oldcapacity and _Newsize, calculate geometric growth
    const size_type _Oldcapacity = capacity();
    const auto _Max              = max_size();
    if (_Oldcapacity > _Max - _Oldcapacity / 2) {
        return _Max; // geometric growth would overflow
    }
    const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
    if (_Geometric < _Newsize) {
        return _Newsize; // geometric growth would be insufficient
    }
    return _Geometric; // geometric growth is sufficient
}

代码也非常清晰，通过这句代码可以看出const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;，一般情况下，增长后的内存大小是原内存大小的1.5倍。

list

list是一个双向循环链表，整体的设计与前两个容器非常相似，直接看代码。

template <class _Ty, class _Alloc = allocator<_Ty>>
class list { // bidirectional linked list
private:
    using _Alty          = _Rebind_alloc_t<_Alloc, _Ty>;
    using _Alty_traits   = allocator_traits<_Alty>;
    using _Node          = _List_node<_Ty, typename allocator_traits<_Alloc>::void_pointer>;
    using _Alnode        = _Rebind_alloc_t<_Alloc, _Node>;
    using _Alnode_traits = allocator_traits<_Alnode>;
    using _Nodeptr       = typename _Alnode_traits::pointer;
    using _Val_types     = conditional_t<_Is_simple_alloc_v<_Alnode>, _List_simple_types<_Ty>,
        _List_iter_types<_Ty, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, _Ty&, const _Ty&, _Nodeptr>>;
    using _Scary_val     = _List_val<_Val_types>;
    // 省略若干代码
private:
    _Compressed_pair<_Alnode, _Scary_val> _Mypair;
};
 
template <class _Value_type, class _Voidptr>
struct _List_node { // list node
    using value_type = _Value_type;
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _List_node>;
    _Nodeptr _Next; // successor node, or first element if head
    _Nodeptr _Prev; // predecessor node, or last element if head
    _Value_type _Myval; // the stored value, unused if head
    // 省略若干代码
};
 
template <class _Val_types>
class _List_val : public _Container_base {
public:
    using _Nodeptr  = typename _Val_types::_Nodeptr;
    using size_type = typename _Val_types::size_type;
    // 省略若干代码
private:
    _Nodeptr _Myhead; // pointer to head node
    size_type _Mysize; // number of elements
};

list的内存布局在Release下可以基本看成和_List_val一致，_List_val是由两个类成员函数_Myhead和_Mysize组成的，前者指向list的头节点，后者用于统计list的当前size（在c++11以前，list::size()的算法时间复杂度可能是O(n)，c++11后保证了时间复杂度是O(1)，因此可以放心用list::size()获取链表的元素个数了）。根据刚才的介绍，应该很容易能算出list本身所占的内存大小了（在32位下是8，64位下是16）。

然后我们再看一下_List_node的声明，刚才已经说过stl的list是双向循环链表，因此肯定包含Next和Prev，在这里可以记一下Next和Prev的顺序，以后在用动态调试器分析时可以快速遍历整个list，紧接着是list的Value类型，也就是list<T>当中T的类型。至此，list的全部类成员变量都已经分析完毕，接下来，编译成二进制进行分析。

原始C++代码：

int main(int argc, char* argv[]) {
    struct Value {
        int a;
        int b;
    };
    std::list<Value> v;
    for (int i = 0; i < argc; ++i) {
        v.push_back(Value{ i, i + 1 });
    }
    for (auto& i : v) {
        printf("%d, %d\n", i.a, i.b);
    }
    return 0;
}

IDA反编译代码：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  _DWORD *v3; // edi
  int i; // esi
  int v5; // ebx
  _DWORD *v6; // eax
  _DWORD *v7; // ecx
  _DWORD *v8; // esi
  _DWORD *v9; // eax
  _DWORD *v10; // esi
  DWORD Block[2]; // [esp+18h] [ebp-18h]
 
  // 1. 初始化list
  // 设置list的_Mysize为0
  Block[1] = 0;
  // 申请一个_List_node作为头节点
  v3 = operator new(0x10u);
  // 双向链表初始化
  *v3 = v3;   // v3->_Next = head;
  v3[1] = v3; // v3->_Prev = head;
  // 将初始化后的node赋值给list的_Myhead
  Block[0] = (DWORD)v3;
 
  // 2. for (int i = 0; i < argc; ++i)
  for ( i = 0; i < argc; v3 = (_DWORD *)Block[0] )
  {
    // 这里list::push_back的代码全部被inline进来了
    v5 = i++;
    if ( Block[1] == 0xFFFFFFF )
      sub_4013D2("list too long");
    v6 = operator new(0x10u); // 申请一个新的_List_node
    // 设置Value
    v6[2] = v5;
    v6[3] = i;
    ++Block[1]; // 递增list的_Mysize
    // 串链表操作
    v7 = (_DWORD *)v3[1]; // v7 = v3->Prev;  // v7是临时变量
    *v6 = v3;             // v6->_Next = v3; // v6是新节点
    v6[1] = v7;           // v6->_Prev = v7; // v3是head节点
    v3[1] = v6;           // v3->_Prev = v6;
    *v7 = v6;             // v7->_Next = v6;
  }
 
  // 3. for (auto& i : v)
  v8 = (_DWORD *)*v3;
  if ( (_DWORD *)*v3 != v3 ) // 先判断一下链表是否是空的
  {
    // 循环打印链表的每一个节点
    do
    {
      sub_401010("%d, %d\n", v8[2], v8[3]);
      v8 = (_DWORD *)*v8; // v8 = v8->_Next;
    }
    while ( v8 != v3 );
    v3 = (_DWORD *)Block[0];
  }
 
  // 4. 释放list的内存
  // 对应list::_Tidy的代码
  *(_DWORD *)v3[1] = 0; // 将最后一个节点的_Next置为NULL，循环时判断到NULL了就结束循环
  v9 = (_DWORD *)*v3;
  if ( *v3 )
  {
    // 循环释放链表中的每一个节点
    do
    {
      v10 = (_DWORD *)*v9;
      sub_401433(v9); // jmp to free
      v9 = v10;
    }
    while ( v10 );
  }
  // 释放链表的头节点
  sub_401433((void *)Block[0]); // jmp to free
  return 0;
}

关于list的识别：

在IDA中的识别方式与string和vector相同，不再具体说明，在OD/X64DBG中，可以根据内存布局来快速判断，list只有一种形式：

// _List_val
00DAF8EC 011A8470 p... // *_List_Node，指向头节点
00DAF8F0 00000001 .... // _Mysize
 
// 头节点
011A8470 011A8488 .... // _Next
011A8474 011A8488 .... // _Prev
011A8478 73656C69 iles // 无效数据
011A847C 4D4F4300 .COM // 无效数据
 
// Value节点
011A8488 011A8470 p... // _Next
011A848C 011A8470 p... // _Prev
011A8490 00000000 .... // i
011A8494 00000001 .... // i + 1

简单容器类型到这里就结束了，下面将介绍较复杂的容器类型map和unordered_map(hash_map)。

map

stl中的map是基于红黑树实现的，本文不涉及红黑树的具体原理，仅站在内存布局的角度说明msvc版本红黑树的实现。

map和set的实现区别：

map和set底层都是红黑树实现的，在msvc版本的stl中，它们均继承自_Tree class，唯一的区别就是map是由key和value组成的，而set只有key而没有value。multimap和multiset除了允许重复key以外其它和非multi版本一致。

template <class _Traits>
class _Tree { // ordered red-black tree for map/multimap/set/multiset
public:
    using value_type     = typename _Traits::value_type;
    using allocator_type = typename _Traits::allocator_type;
 
protected:
    using _Alty          = _Rebind_alloc_t<allocator_type, value_type>;
    using _Alty_traits   = allocator_traits<_Alty>;
    using _Node          = _Tree_node<value_type, typename _Alty_traits::void_pointer>;
    using _Alnode        = _Rebind_alloc_t<allocator_type, _Node>;
    using _Alnode_traits = allocator_traits<_Alnode>;
    using _Nodeptr       = typename _Alnode_traits::pointer;
 
    using _Scary_val = _Tree_val<conditional_t<_Is_simple_alloc_v<_Alnode>, _Tree_simple_types<value_type>,
        _Tree_iter_types<value_type, typename _Alty_traits::size_type, typename _Alty_traits::difference_type,
            typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, value_type&, const value_type&,
            _Nodeptr>>>;
 
    enum _Redbl { // colors for link to parent
        _Red,
        _Black
    };
    // 省略若干代码
 
private:
    _Compressed_pair<key_compare, _Compressed_pair<_Alnode, _Scary_val>> _Mypair;
};

根据前几个容器的分析经验，直接找到_Scary_val对应的类型即可，最终代码如下：

template <class _Val_types>
class _Tree_val : public _Container_base {
public:
    using _Nodeptr  = typename _Val_types::_Nodeptr;
    using size_type = typename _Val_types::size_type;
    // 省略若干代码
    _Nodeptr _Myhead; // pointer to head node
    size_type _Mysize; // number of elements
};
 
template <class _Value_type, class _Voidptr>
struct _Tree_node {
    using _Nodeptr   = _Rebind_pointer_t<_Voidptr, _Tree_node>;
    using value_type = _Value_type;
    _Nodeptr _Left; // left subtree, or smallest element if head
    _Nodeptr _Parent; // parent, or root of tree if head
    _Nodeptr _Right; // right subtree, or largest element if head
    char _Color; // _Red or _Black, _Black if head
    char _Isnil; // true only if head (also nil) node; TRANSITION, should be bool
    value_type _Myval; // the stored value, unused if head
 
    enum _Redbl { // colors for link to parent
        _Red,
        _Black
    };
};

相比普通的红黑树，stl中的红黑树多了一个head节点，并且有以下几个特点：

head节点中的_Isnil=true
head节点的_Parent指向红黑树的根节点
head节点的_Left指向红黑树的最左节点，以便于常数时间实现begin()
head节点的_Right指向红黑树的最右节点

rbtree

节点的left或者right为null的情况没有在图中表现出来，实际在stl中，它们被指向head，例如：most left节点的left节点本来应该是null，但在stl的实现中，它被指向head，可通过_Isnil判断。

介绍完了和普通红黑树的基本区别，接下来我们看一下_Tree的内存布局，_Tree本身是由_Myhead和_Mysize组成的，在32位下_Tree总共占用8字节空间，而_Tree_node的内存大小要根据实际Value的类型来计算，在下面的例子中，_Tree_node总共占用24字节空间（_Left(4)+_Parent(4)+_Right(4)+_Color(1)+_Isnil(1)+2字节填充+_Myval(8)）。

原始C++代码：

int main(int argc, char* argv[]) {
    std::map<int, int> v;
    for (int i = 0; i < argc; ++i) {
        v[i] = i + 1;
    }
    for (auto& i : v) {
        printf("%d, %d\n", i.first, i.second);
    }
    return 0;
}

IDA反编译代码：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  _DWORD *v3; // eax
  int v4; // ecx
  int *v5; // esi
  int **v6; // eax
  int *i; // eax
  int *j; // ecx
  _DWORD *v9; // esi
  void *v10; // eax
  int v12; // [esp+Ch] [ebp-1Ch] BYREF
  int v13[2]; // [esp+10h] [ebp-18h] BYREF
  int v14; // [esp+24h] [ebp-4h]
 
  // 1. 初始化Tree
  v13[1] = 0;
  // 申请_Tree_node作为head节点
  v3 = operator new(24u);
  *v3 = v3;   // v3->_Left = v3;
  v3[1] = v3; // v3->_Parent = v3;
  v3[2] = v3; // v3->_Right = v3;
  // 同时给_Color和_Isnil，这里是固定的
  // _Color = _Redbl::_Black;
  // _Isnil = true;
  *((_WORD *)v3 + 6) = 0x101;
  v13[0] = (int)v3; // 将Tree的head设置为刚才申请的_Tree_node
 
  // 2. for (int i = 0; i < argc; ++i)
  v4 = 0;
  v14 = 0;
  v12 = 0;
  if ( argc > 0 )
  {
    do
    {
      // 这里生成了一个emplace对应的函数
      // 参数是key，返回值是value的指针
      *sub_401310(v13, &v12) = v4 + 1;
      v4 = v12 + 1;
      v12 = v4;
    }
    while ( v4 < argc );
    v3 = (_DWORD *)v13[0];
  }
 
  // 3. for (auto& i : v)
  // 重点分析一下红黑树的遍历过程
  v5 = (int *)*v3;
  if ( !*(_BYTE *)(*v3 + 13) ) // !v3->_Isnil
  {
    do
    {
      printf("%d, %d\n", v5[4], v5[5]);
      // 以下是"_Tree_unchecked_const_iterator::_Tree_unchecked_const_iterator& operator++() noexcept"展开后的代码
      v6 = (int **)v5[2];
      // 判断_Right节点是否是nil
      if ( *((_BYTE *)v6 + 13) )
      {
        // 是nil，向上回溯，直到v5是i（父节点）的_Left节点时停止，此时i（父节点）即为下一个节点
        for ( i = (int *)v5[1]; !*((_BYTE *)i + 13); i = (int *)i[1] )
        {
          if ( v5 != (int *)i[2] ) // 判断i（父节点）节点的_Right节点与v5不相等时，即与_Left相等时终止
            break;
          v5 = i;
        }
        v5 = i;
      }
      else
      {
        // 不是nil，获取_Right节点的most left节点，即为下一个节点
        v5 = (int *)v5[2];
        for ( j = *v6; !*((_BYTE *)j + 13); j = (int *)*j )
          v5 = j;
      }
    }
    while ( !*((_BYTE *)v5 + 13) );
    v3 = (_DWORD *)v13[0];
  }
 
  // 4. 释放Tree的内存
  v9 = (_DWORD *)v3[1];
  if ( !*((_BYTE *)v9 + 13) )
  {
    do
    {
      // 递归释放子树
      sub_401620((int)v13, (void *)v9[2]);
      v10 = v9;
      v9 = (_DWORD *)*v9;
      sub_40178B(v10); // jmp to free
    }
    while ( !*((_BYTE *)v9 + 13) );
    v3 = (_DWORD *)v13[0];
  }
  sub_40178B(v3); // jmp to free
  return 0;
}

对遍历过程有疑问的可以对照下面的C++源码：

_Tree_unchecked_const_iterator& operator++() noexcept {
    if (_Ptr->_Right->_Isnil) { // climb looking for right subtree
        _Nodeptr _Pnode;
        while (!(_Pnode = _Ptr->_Parent)->_Isnil && _Ptr == _Pnode->_Right) {
            _Ptr = _Pnode; // ==> parent while right subtree
        }
 
        _Ptr = _Pnode; // ==> parent (head if end())
    } else {
        _Ptr = _Mytree::_Min(_Ptr->_Right); // ==> smallest of right subtree
    }
 
    return *this;
}

最后看一下在内存中的布局：

// _Tree_val
004FF7C0 00818470 p... // _Myhead
004FF7C4 00000001 .... // _Mysize
 
// 头节点的数据
00818470 00818490 .... // _Left
00818474 00818490 .... // _Parent
00818478 00818490 .... // _Right
0081847C 4D4F0101 ..OM // _Isnil=true, _Color=1
// 头节点后面是无效数据
00818480 45545550 PUTE 
00818484 4D414E52 RNAM 
 
// 节点的数据
00818490 00818470 p... // _Left
00818494 00818470 p... // _Parent
00818498 00818470 p... // _Right
0081849C 5C3A0001 ..:\ // _Isnil=false, _Color=1
// 非头节点，有效数据
008184A0 00000000 .... // key=0
008184A4 00000001 .... // value=1

unordered_map

最后一个使用率比较高的容器莫过于unordered_map了，它内部是由Hash Table实现的，它与hash_map基本一致，但是unordered_map已经被纳入到C++标准当中的，因此在日常使用上，也更推荐使用unordered_map而不是hash_map。

与之前一样，先看一下源码：

template <class _Traits>
class _Hash { // hash table -- list with vector of iterators for quick access
protected:
    using _Mylist = list<typename _Traits::value_type, typename _Traits::allocator_type>;
 
private:
    _Traits _Traitsobj; // traits to customize behavior
    _Mylist _List; // list of elements, must initialize before _Vec
    _Hash_vec<_Aliter> _Vec; // "vector" of list iterators for buckets:
                             // each bucket is 2 iterators denoting the closed range of elements in the bucket,
                             // or both iterators set to _Unchecked_end() if the bucket is empty.
    size_type _Mask; // the key mask
    size_type _Maxidx; // current maximum key value, must be a power of 2
};

Hash Table有两种常见的实现方式：开放定址法和链地址法。stl中的unordered_map中使用的便是链地址法，正如其名，unordered_map中所有Value都是存储在_List当中的，方便顺序遍历所有节点，_Vec记录Hash(Key)对应的List Node位置，用于快速索引到对应的List Node。

我们来先分析下_Hash的内存布局，_Traitsobj是一个模板类型，不是很直观，经过我的搜索，内部最主要记录了load factor，是一个float类型，占用4个字节，默认情况是1，_List和_Vec和标准stl的List和Vector类型的内存布局一致，_Mask和_Maxidx在32位下个占用4个字节，一般情况下_Mask=_Maxidx-1，这点在后面的反编译代码中也能体现出来。最终计算得出_Hash总共占用32字节（_Traitsobj(4)+_List(8)+_Vec(12)+_Mask(4)+_Maxidx(4)）。

下面看一段测试代码：

原始C++代码：

int main(int argc, char* argv[]) {
    std::unordered_map<int, int> v;
    for (int i = 0; i < argc; ++i) {
        v[i] = i + 1;
    }
    for (auto& i : v) {
        printf("%d, %d\n", i.first, i.second);
    }
    return 0;
}

IDA反编译代码：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  _DWORD *v3; // eax
  int v4; // eax
  _DWORD *j; // esi
  _DWORD v7[8]; // [esp+Ch] [ebp-34h] BYREF
  int i; // [esp+2Ch] [ebp-14h] BYREF
  int v9; // [esp+3Ch] [ebp-4h]
 
  // 1. 初始化unordered_map
  v7[2] = 0; // 初始化链表的size
  v3 = operator new(0x10u); // 分配链表头的内存
  // 初始化链表头
  *v3 = v3;
  v3[1] = v3;
  v7[1] = v3; // 将链表头赋值给_List成员变量
  v9 = 1;
  v7[3] = 0; // 初始化_Vec._Myfirst
  v7[4] = 0; // 初始化_Vec._Mylast
  v7[5] = 0; // 初始化_Vec._Myend
  v7[6] = 7; // _Mask，一般情况下都是_Maxidx-1
  v7[7] = 8; // _Maxidx，默认是8
  v7[0] = 0x3F800000; // _Traitsobj记录的load factor，float类型，值是1.0
  sub_401400((void **)&v7[3], 0x10u, (int)v3); // unordered_map在初始化阶段会进行rehash操作
 
  // 2. for (int i = 0; i < argc; ++i)
  v4 = 0;
  v9 = 2;
  for ( i = 0; v4 < argc; i = v4 )
  {
    // insert操作比较复杂，没有被inline代码，不是本文关注的重点，不再展开分析内部实现
    *(_DWORD *)sub_401350(&i) = v4 + 1;
    v4 = i + 1;
  }
 
  // 3. for (auto& i : v)
  // 实际上，unordered_map的遍历就是对内部的_List进行顺序遍历
  for ( j = *(_DWORD **)v7[1]; j != (_DWORD *)v7[1]; j = (_DWORD *)*j )
    printf("%d, %d\n", j[2], j[3]);
 
  // 4. 释放unordered_map的内存
  sub_4012C0((int)v7);
  return 0;
}

最后看一下在内存中的布局：

// _Hash
00A4F934 3F800000 ...? // load factor=float(1)
00A4F938 00EB8470 p.ë. // _List._List_Node
00A4F93C 00000001 .... // _List._Mysize
00A4F940 00EB8488 ..ë. // _Vec._Myfirst
00A4F944 00EB84C8 È.ë. // _Vec._Mylast
00A4F948 00EB84C8 È.ë. // _Vec._Myend
00A4F94C 00000007 .... // _Mask
00A4F950 00000008 .... // _Maskidx

三、总结

在实际逆向的过程中，通过IDA生成的反编译代码可能要比本文展示的更加复杂，通常都是结构体加上stl容器嵌套造成的，因此并没有一种可以识别出任意stl容器的方案。对于这类代码的还原，我更倾向于动态静态相结合，根据内存布局初步判断容器类型，然后结合初始化代码进一步验证我们的猜想。

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

#调试逆向

收藏・31

点赞・10

打赏

最新回复 (4)
caolinkai 雪币： 3674 活跃值： (3853) 能力值： ( LV2，RANK：10 ) 在线值：发帖 7 回帖 813 粉丝 1 关注私信	caolinkai 2021-12-1 16:42 2 楼 0 很nice。。。收藏了
yllen 雪币： 1257 活跃值： (1424) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 164 粉丝 0 关注私信	yllen 2021-12-1 17:23 3 楼 0 好的
随风行雪币： 1595 活跃值： (2807) 能力值： ( LV4，RANK：50 ) 在线值：发帖 6 回帖 58 粉丝 59 关注私信	随风行 1 2021-12-1 17:30 4 楼 0 学习了
ookkaa 雪币： 39 活跃值： (4177) 能力值： ( LV3，RANK：35 ) 在线值：发帖 18 回帖 200 粉丝 34 关注私信	ookkaa 2021-12-1 17:32 5 楼 0 很nice。。。收藏了
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

windpiaoxue

发帖

回帖

RANK

关注

私信

他的文章

[原创]浅谈STL容器的识别

[原创]开源一个基于C++的shellcode框架

关于我们

联系我们

企业服务

看雪公众号