二叉树是数据结构中的经典,那么其在IDA的伪代码中表现为何种形式呢?

有如下定义Tree

struct tree
{
	unsigned char data;
	tree *right;
	tree *left;
}*Tree;

又有如下操作

int init()
{
	tree *n[16];
	for(int i=0;i<16;i++)
		n[i]=(tree*)malloc(sizeof(tree));
	for(int i=0;i<16;i++)
		n[i]->data='A'+i;
	n[0]->left=n[1];
	n[0]->right=n[2];
	n[1]->left=n[3];
	n[1]->right=n[4];
	n[2]->left=n[5];
	n[2]->right=n[6];
	n[3]->left=n[7];
	n[3]->right=n[8];
	n[4]->left=n[9];
	n[4]->right=NULL;
	n[5]->left=n[10];
	n[5]->right=NULL;
	n[6]->left=n[11];
	n[6]->right=n[12];
	n[7]->right=n[7]->left=NULL;
	n[8]->left=NULL;
	n[8]->right=n[13];
	n[9]->left=n[9]->right=NULL;
	n[10]->left=n[14];
	n[10]->right=n[15];
	n[11]->left=n[11]->right=n[12]->left=n[12]->right=NULL;
	n[13]->left=n[13]->right=NULL;
	n[14]->left=n[14]->right=n[15]->left=n[15]->right=NULL;
	Tree=n[0];
	return 1;
}

简单的初始化了一个二叉树

其在IDA中的伪代码表现为

int sub_151120()
{
  int v1; // [esp+0h] [ebp-48h]
  int v2; // [esp+4h] [ebp-44h]
  int v3; // [esp+8h] [ebp-40h]
  int v4; // [esp+Ch] [ebp-3Ch]
  int v5; // [esp+10h] [ebp-38h]
  int v6; // [esp+14h] [ebp-34h]
  int v7; // [esp+18h] [ebp-30h]
  int v8; // [esp+1Ch] [ebp-2Ch]
  int v9; // [esp+20h] [ebp-28h]
  int v10; // [esp+24h] [ebp-24h]
  int v11; // [esp+28h] [ebp-20h]
  int v12; // [esp+2Ch] [ebp-1Ch]
  int v13; // [esp+30h] [ebp-18h]
  int v14; // [esp+34h] [ebp-14h]
  int v15; // [esp+38h] [ebp-10h]
  int v16; // [esp+3Ch] [ebp-Ch]
  int i; // [esp+40h] [ebp-8h]
  int j; // [esp+44h] [ebp-4h]

  for ( i = 0; i < 16; ++i )
    *(&v1 + i) = (int)malloc(12u);
  for ( j = 0; j < 16; ++j )
  {
    _mm_lfence();
    *(_BYTE *)*(&v1 + j) = j + 'A';
  }
  *(_DWORD *)(v1 + 8) = v2;
  *(_DWORD *)(v1 + 4) = v3;
  *(_DWORD *)(v2 + 8) = v4;
  *(_DWORD *)(v2 + 4) = v5;
  *(_DWORD *)(v3 + 8) = v6;
  *(_DWORD *)(v3 + 4) = v7;
  *(_DWORD *)(v4 + 8) = v8;
  *(_DWORD *)(v4 + 4) = v9;
  *(_DWORD *)(v5 + 8) = v10;
  *(_DWORD *)(v5 + 4) = 0;
  *(_DWORD *)(v6 + 8) = v11;
  *(_DWORD *)(v6 + 4) = 0;
  *(_DWORD *)(v7 + 8) = v12;
  *(_DWORD *)(v7 + 4) = v13;
  *(_DWORD *)(v8 + 8) = 0;
  *(_DWORD *)(v8 + 4) = 0;
  *(_DWORD *)(v9 + 8) = 0;
  *(_DWORD *)(v9 + 4) = v14;
  *(_DWORD *)(v10 + 4) = 0;
  *(_DWORD *)(v10 + 8) = 0;
  *(_DWORD *)(v11 + 8) = v15;
  *(_DWORD *)(v11 + 4) = v16;
  *(_DWORD *)(v13 + 4) = 0;
  *(_DWORD *)(v13 + 8) = 0;
  *(_DWORD *)(v12 + 4) = 0;
  *(_DWORD *)(v12 + 8) = 0;
  *(_DWORD *)(v14 + 4) = 0;
  *(_DWORD *)(v14 + 8) = 0;
  *(_DWORD *)(v16 + 4) = 0;
  *(_DWORD *)(v16 + 8) = 0;
  *(_DWORD *)(v15 + 4) = 0;
  *(_DWORD *)(v15 + 8) = 0;
  Tree = v1;
  return 1;
}

一些分析与见解

  • &v1即是一个Tree数组,因此如下伪代码

    for ( i = 0; i < 16; ++i )
    	*(&v1 + i) = (int)malloc(12u); // root[i] = malloc(sizeof(tree));
    for ( j = 0; j < 16; ++j )
      {
        _mm_lfence();
        *(_BYTE *)*(&v1 + j) = j + 'A'; // root[i].xx = 65 + j; 
      }
    

    虽然在伪代码中无法确定结构体内变量的名称,但可以了解到结构体的内部结构(大小,个数,类型)

  • 如下所示,是比较明显的二叉树特征

    *(_DWORD *)(v1 + 8) = v2; // left Node root.left
    *(_DWORD *)(v1 + 4) = v3; // right Node root.right
    *(_DWORD *)(v2 + 8) = v4; // left Node root.left.left
    *(_DWORD *)(v2 + 4) = v5; // right Node root.left.right
    
  • 试着构造一个二叉树的基本结构,可以比较直观的看到伪代码的变化

    v1->left = v2; // left Node root.left
    v1->right = v3; // right Node root.right
    v2->left = v4; // left Node root.left.left
    v2->right = v5; // right Node root.left.right
    

据此可以推断出二叉树在伪代码中的一些特征

  • 不管是C/C++,二叉树子节点都是通过动态的申请内存空间取得,可以发现在初始化节点之前会有形似malloc(size);operator new(size);
  • 子节点初始化的过程中,可以看到多个形似*(_DWORD *)(a1 + 4) = 0;的语句

emm,想到了再补充~