玩玩IDA Graph View
___________________________________________________________________

IDA自5.0版加入了graph view功能,按空格键可在文本与图形模式间切换,看起来很直观(我觉得比wingraph好用),不过只能处理函数。如果代码不能归属到某个函数,会报错:

 


我们自己写插件来玩玩Graph View。要显示的代码是Themida 1930 Demo的VM引擎。升级到19xx后,Themida的变形代码有所增强,一直想再玩玩,不过断断续续搞了一段时间,效果不好。本文不涉及变形代码处理(能搞出可接受的结果再说)。最初的打算是以图形方式显示代码,加入一定的交互能力,对程序无法清理的代码手工处理。实际证明不可行,一是Basic Block量太大,手工操作不现实。另外IDA在处理复杂的图时似乎有点问题。最终可能还是只有先压缩代码,graph只能看看。

原来也考虑过uDraw之类的,感觉那个更麻烦。找了本讲图算法的书,翻了几页就不行了,头晕恶心,到底是土八路啊。

Dump VM的6个区段,贴到一个小程序后面,以免IDB过于庞大。IDA对Themida VM的初始分析似乎有点问题,始终停不下来。将其停下来,自己处理一下unexploered部分。修改IDA设置,把graph允许的最大节点数设大点。


 
IDA v5.2 SDK带了个例子(ugraph),直接在例子上写。

收集Basic Block_______________________________________________

graph内的node对应代码基本块(Basic Block)。BB指可作为整体对待的代码片段,如果BB的第1条指令被执行,则该块内的所有指令会被顺序执行。IDA自己使用了Basic Block的概念,若选择如下设置,会在BB结束处分界。
 

 



显然,IDA是把call指令也作为BB结束的,因为call可被用作变形的jmp而不再返回。SDK并没有直接提供Basic Block信息,相关的API只有一个。

idaman bool ida_export is_basic_block_end(bool call_insn_stops_block); // in:cmd

参数指示call是否视为BB结束。另一个参数为全局的cmd结构,即应先用ua_ana0分析指令以填写cmd。

对BB的收集可有2种方式。一是对指定的地址范围线性搜索,这样数据量较大。这里用递归方式,从指定地址(某个handler的入口)开始分析。

定义CBasicBlock类:

class CBasicBlock  
{
public:
  int n;        // graph内的索引(add_node的返回)
  ea_t first;  // bb第1条指令的机器码地址,这个成员用于代表该bb,在压缩变形代码时不会改变
         // (实际的指令可能被清理)

vector<PCode>   codes;    // basic-block包含的指令(反汇编为pcode),pcode的eip成员
// 为原机器码地址
vector<DWORD>   cref_from;  // 参考该bb的bb。收集bb时为其出口指令地址(此时该bb
// 可能还未创建),完成收集后替换为其first成员
  vector<DWORD>   cref_to;    // 被参考的bb入口地址(即被参考bb的first)

public:
  CBasicBlock();         //没有用oop,用类只为代码好管理
  ~CBasicBlock();
};

使用的数据结构:

std::set<ea_t>    path_mark;    // 已分析bb的first
std::set<ea_t>    future_label;    // 未分析bb的first
std::vector<ea_t> nodes;      // vector的下标=add_node的返回,用于从给定的graph内
// index搜索对应bb数据
std::map<ea_t,ea_t> exit2entry;  // 从bb的出口查找入口地址
std::map<ea_t,CBasicBlock> bbs;  // basic blocks

直接列代码,本来想用文字描述,发现那更麻烦。抄袭MetaPHOR的做法。

#define flow_ordinary   0x15   // ordinary flow即“自然落下”的那个地址

static void gather_basic_block(ea_t entry)
{
  // 从entry开始分析basic block,结果在bbs

  ea_t  start = entry;
  ea_t  curr, next;
  ea_t  next_entry; //下个分析地址
  PCode pcode;
  CBasicBlock bb;
      
  if (!isCode(get_flags_novalue(start)))
  {  
    msg("invalid entry\n"); //entry != 代码
    return;
  }
  show_wait_box("Searching basic blocks...\n\n\nJust a Moment");

  bbs.clear();
  exit2entry.clear();
  path_mark.clear();
  future_label.clear();
  bb_num = 0;

__Analysis:

  if (wasBreak()) 
goto __Exit; //用户取消
  if (path_mark.count(start)) //已分析
    goto __FutureLabel;
  else 
    path_mark.insert(start); //置已分析标记

  bb.codes.clear(); //初始化bb成员
  bb.cref_from.clear();
  bb.cref_to.clear();
  
  //如果存在对应的future label则删除
  if (future_label.count(start)) future_label.erase(start);
  
  curr = start;
  while (true) //搜索当前bb边界
  {  
    if (!ua_ana0(curr)) goto __Exit; //output->cmd
    
    memset(&pcode, 0, sizeof(pcode));
    pcode.eip = curr; //保存机器码地址
    bb.codes.push_back(pcode);

    next = get_item_end(curr);
    if (is_basic_block_end(true)) break; //bb结束?
    
    curr = next;
  }
  bb.first = start;      // bb.first=入口代码地址
  exit2entry[curr] = start;  // 保存exit->entry映射

  //分析交叉参考
  xrefblk_t xb;

  // IDA SDK: 
  // The following functions return: 1-ok, 0-no (more) xrefs
  // They first return code references, then data references. <<<< 首先返回代码参考
  // If you need only code references, you need to check 'iscode' after each call.
  // If you need only data references, use XREF_DATA bit.
  
  // 参考当前bb的bb
  // cref_from=参考当前bb的bb的出口地址,这里无法得知对应bb的first,bb可能还未生成
  
  if (xb.first_to(start, XREF_ALL) && xb.iscode)
  {
    bb.cref_from.push_back(xb.from);
    while(xb.next_to() && xb.iscode) bb.cref_from.push_back(xb.from);
  }

  //被当前bb参考的bb

  next_entry = 0; //下个分析地址预置为0

  //////////////////////////////////////////////////////////////////////////
  //
  //  bb的cref_to最多包含2个分枝:
  //  1. size=0,无分枝(如jmp esi, ret)
  //  2. size=1,1个分枝(如jmp, ordinary flow),使用cref_to[0]
  //  3. size=2,2个分枝(jcc),约定ordinary flow=cref_to[0], dst=cref_to[1]
  //
  ////////////////////////////////////////////////////////////////////////////
  
  if ( ! (xb.first_from(bb.codes.back().eip, XREF_ALL) && xb.iscode) )
    goto __SaveBasicBlock; //无cref,next_entry=0
  else
  {
    //1条指令最多存在2个代码分枝,IDA先返回代码参考,只需要调用1次next_from

    ea_t  first_to    = xb.to;
    uchar first_type = xb.type;

    if (xb.next_from() && xb.iscode) //存在第2个分枝?
    {
      ea_t second_to = xb.to;

      //不依赖first_to|next_to返回地址的顺序(按大小排列?)来确定哪个是
//ordinary flow,自己处理一下
      if (first_type == flow_ordinary)
      {
        next_entry = first_to; //继续分析ordinary flow

        bb.cref_to.push_back(first_to);  //cref_to[0]=ordinary flow
        bb.cref_to.push_back(second_to); //cref_to[1]=dst

        //在future_label插入jcc dst
        
        if ( !path_mark.count(second_to) &&  // 未分析
             !future_label.count(second_to))  // 不存在future_label
        {
          future_label.insert(second_to);
        }
      }
      else
      {
        next_entry = second_to;

        bb.cref_to.push_back(second_to); //cref_to[0]=ordinary flow
        bb.cref_to.push_back(first_to);  //cref_to[1]=dst

        //在future_label插入jcc dst
        if ( !path_mark.count(first_to) && 
           !future_label.count(first_to))           )
        {
          future_label.insert(first_to);
        }
      }
    }
    else //只有1个分枝
    {
      bb.cref_to.push_back(first_to);
      next_entry = first_to;
    }
  }

__SaveBasicBlock:
  bbs[start] = bb;
  start = next_entry;

  if ( start==0 ) //已到了叶节点
    goto __FutureLabel;
  if ( path_mark.count(start) )
    goto __FutureLabel; //已处理
  
  goto __Analysis; //分析下1个bb

__FutureLabel:
  if (future_label.empty()) //没有future label结束分析
    goto __Exit;
  else
  {  
//取第1项
    start = *future_label.begin(); 
    goto __Analysis;
  }

__Exit:
  hide_wait_box();
  msg("basic blocks=%d\n", bb_num);
}

此时可进行一些预处理,如删除bb的外来参考(参考者不在收集的basic block内),合并由jmp链接的块等。

完成Basick Block收集后,用exit2entry将所有bb的cref_from(参考者)替换为对应bb的first。压缩变形代码时可能会删除原来的出口代码。

下面将所有bb包含的代码反汇编为pcode(麻烦,但对压缩变形代码有用)。逐个压缩bb,删除fake jcc(如果可能则合并basic block,压缩合并结果)。后2步要反复循环。我还有无数没解决的问题及无数的bug,这里就不多说了。

编写IDA回调函数________________________________________________

这里只列出改写的代码。完整代码请参考SDK的例子。

grcode_user_refresh: 创建node和edge                                            

case grcode_user_refresh:    // refresh user-defined graph nodes and edges
                // in:  mutable_graph_t *g
                // out: success
{
    //生成node和edge
    mutable_graph_t *g = va_arg(va, mutable_graph_t *);
    
    if(!g->empty()) //清空graph
      g->clear();
    nodes.clear();
    
// 为bbs内所有item加入node
    
    map<ea_t,CBasicBlock>::iterator it=bbs.begin();
    for (; it != bbs.end(); ++it)
    {
      int n = g->add_node(NULL);  
      it->second.n = n;  // 保存当前bb的index
      nodes.push_back(it->second.first);

      if (it->second.first == entry) //保存handler entry对应node
      {                //后面要将这个node用红色显示
        root = n;
        msg("root=%d\n", root);
      }
    }
    
    // 加edge
    
    for (it=bbs.begin(); it != bbs.end(); ++it)
    {
      if (!it->second.cref_to.empty()) //存在cref_to
      {
        vector<ulong>::size_type size = it->second.cref_to.size();
          
        if (size==1) //jmp或ordinay flow
        {  
          //edge用缺省色
          map<ea_t,CBasicBlock>::iterator cref = 
bbs.find(it->second.cref_to[0]);
          if(cref != bbs.end())
          {
            g->add_edge(it->second.n, cref->second.n, NULL);
            //msg("add_edge: %d->%d\n", it->second.n, cref->second.n);
          }
        }
        else //size=2(jcc),只可能有2个分枝
        {
          for (ulong i=0; i<size; ++i)
          {
            map<ea_t,CBasicBlock>::iterator cref = 
bbs.find(it->second.cref_to[i]);
            if (cref != bbs.end()) //被参考bb存在则加边
            {  
              edge_info_t edge_info;

              if (i==0)
                edge_info.color = RGB(255,0,0);  //ordinary flow=red(约
//定为cref_to[0])
              else
                edge_info.color = RGB(30,150,30); //jcc dst=green

              g->add_edge(it->second.n, cref->second.n, &edge_info); 
              //msg("add_edge: %d->%d\n", it->second.n, cref->second.n);
            }
          }
        }
      }
    }
    msg("add nodes and edges ok\n");
    result = 1;
}
break;

grcode_user_text: 为每个node生成显示的文本                                      

case grcode_user_text:    // retrieve text for user-defined graph node
              // in:  mutable_graph_t *g
              //      int node
              //      const char **result
              //      bgcolor_t *bg_color (maybe NULL)
              // out: must return 0, result must be filled
              // NB: do not use anything calling GDI!
{
  //IDA为每个node调用callback
  mutable_graph_t *g = va_arg(va, mutable_graph_t *);
  int n                 = va_arg(va, int);
  const char **text  = va_arg(va, const char **);
  bgcolor_t *bgcolor = va_arg(va, bgcolor_t *);

  char curr[256];
  memset(buf, 0, sizeof(buf));
  //n为当前node在图内的index
  map<ea_t,CBasicBlock>::iterator it=bbs.find(nodes[n]);
  if(it != bbs.end())
  {
    for (int i=0; i<it->second.codes.size(); ++i)
    {
      memset(curr,0, sizeof(curr));
      //将pcode转换为助记符,这里的类名不大合适呵呵
CAsm::DisasmMnem(it->second.codes[i], curr);
          
      if ((strlen(buf)+strlen(curr)+10) > MAXSTR)
      {
        //text太长,在后面显示”…”
        qstrncat(buf, COLSTR("...",SCOLOR_INSN), MAXSTR-1);
        break;
      }
      else
      {
        qstrncat(buf, curr, MAXSTR-1);
        qstrncat(buf, "\n", MAXSTR-1);
      }
    }
    *text=buf;
  }
  else
  {
    //一般情况下不应该,但IDA插入了dummy node…
    msg("bb=%d addr=%08X not existed\n", n, nodes[n]);
    qstrncpy(buf, "error", sizeof(buf));
    return result; //直接返回0
  }
  //对node设置背景色
  bool vm_exit = (it->second.codes[back].opcode==Op_JMP_Reg ||
it->second.codes[back].opcode==Op_Ret)? 
true:false;

  if(bgcolor != NULL )
  {
    if(n == root)
      *bgcolor = RGB(255,120,140); //handler entry=红色
    else if(vm_exit)
      *bgcolor = RGB(150,150,150); //handler exit=灰色
    else 
      *bgcolor = DEFCOLOR;
  }
  // IDA SDK原例子的注释有错,这里必须返回1
  result = 1;
  qnotused(g);
}
break;

grcode_user_title: 为node绘制title                                             
case grcode_user_title:    // render node title of a user-defined graph
              // in:  mutable_graph_t *g
              //      int node
              //      rect_t *title_rect
              //      int title_bg_color
              //      HDC dc
              // out: 0-did not render, ida will fill it with title_bg_color
              //      1-rendered node title
              // ida will draw the node title itself
{
  mutable_graph_t *g = va_arg(va, mutable_graph_t *);
  int n                 = va_arg(va, int);
  rect_t *rect      = va_arg(va, rect_t *);
  bgcolor_t bgcolor  = va_arg(va, bgcolor_t);
  HDC dc          = va_arg(va, HDC);

  //在title bar显示bb起始指令地址
  map<ea_t,CBasicBlock>::iterator it=bbs.find(nodes[n]);
  if (it != bbs.end())
  {
    char title[32];
    qsnprintf(title, sizeof(title)-1, "loc_%X", it->second.first);

    SetTextColor(dc, RGB(255,255,255));
    SetBkMode(dc, TRANSPARENT);
    FillRect(dc, (LPRECT)rect, (HBRUSH)GetStockObject(GRAY_BRUSH));

    LOGFONT logfont;
    HFONT font = (HFONT)GetCurrentObject(dc, OBJ_FONT);
    GetObject(font, sizeof(LOGFONT), &logfont);
    
logfont.lfHeight = rect->height();
    logfont.lfWidth  = 0;
    logfont.lfWeight = 500;
    qstrncpy(logfont.lfFaceName, "Courier New", sizeof(logfont.lfFaceName)-1);

    HFONT bigfont = CreateFontIndirect(&logfont);
    HFONT oldfont = (HFONT)SelectObject(dc, bigfont);
    DrawText(dc, title, strlen(title), (LPRECT)rect, 
DT_SINGLELINE |DT_LEFT|DT_VCENTER);

    SelectObject(dc, oldfont);
    DeleteObject(bigfont);
  }
}
result = 1;
break;


插件的run函数                                                                   

void idaapi run(int /*arg*/)
{
  HWND hwnd = NULL;
  
  entry = 0x01DC4C7B; //硬编码的handler地址,实际应用askaddr
  
// 反汇编前的预处理
  gather_basic_block(entry);       // 收集bb
  CShrink::Preprocess();         // 预处理
  CShrink::DeletePermutation();   // 删除permutation-jmp
  CShrink::UpdateCrefFrom();       // 更新所有cref_from为对应bb的first
  exit2entry.clear();           // 不再需要
  CShrink::Shrink();           // Fuck oreans!
  
  TForm *form = create_tform("Deobfuscator", &hwnd);
  if(hwnd != NULL)
  {
    // get a unique graph id
    netnode id;
    id.create();
    
//要显示title,height不能为0
    graph_viewer_t *gv = create_graph_viewer(form,  id, callback, NULL, 14);
    gview = gv; //保存到全局变量
    
    open_tform(form, FORM_MDI|FORM_TAB|FORM_MENU);
    if ( gv != NULL )
    {
      viewer_fit_window(gv);
      viewer_add_menu_item(gv, "Layout", menu_layout, gv, NULL, 0);
      //增加一个搜索功能
      viewer_add_menu_item(gv, "Search...", menu_search, gv, NULL, 0);
    }
  }
  else
  {
    close_tform(form, 0);
  }
}

bool idaapi menu_search(void *ud)
{
  //在graph中搜索指定entry对应的node
  ea_t addr=BADADDR;
  if (!askaddr(&addr, "basic block entry")) return false;

  mutable_graph_t *g = get_viewer_graph(gview);
  bool found=false;
  
for (int n=0; n<nodes.size(); ++n) 
  {
    if (nodes[n] == addr) 
    {
      found=true;
      break;
    }
  }
  if(!found)
  {
    msg("node not found\n");
    return false;
  }
  viewer_center_on(gview, n); //居中显示node
  return true;
}

基本就是这些,看看效果。
 


 
还有很多变形代码没有处理。第2块出口fake jcc的dst没有出现,无法合并(限制了basic block数量)。


IDA的问题?__________________________________________________

不敢随便质疑这样的软件,必须打个问号。在graph比较复杂的时候,IDA似乎有问题。当前handler若不压缩有68000个bb(因为fake jcc即加壳时的MultiBranch Technology选项)。限制收集的bb数量为8000(当前压缩结果为500多bb,水份还很大),可以正常显示。

  当设置更大的数量时,会导致IDA出错退出。


 

似乎是这个函数有问题:

size_t idaapi sort_layer_nodes(const row_info_t &r1,
                               const intmap_t &lpi1,
                               row_info_t &r2,
                               intmap_t &lpi2,
                               bool ispred) const;

另外,当nodes数量较大时会出另外的错,不能正常画图。加了些调试信息后发现,IDA在计算layout时增加了node,并会用这些node的n来调用grcode_user_text。当然收集的bb内没有对应项,在代码内返回的text为error。

在网上搜到一篇文章<Graph Layout for Applications in Compiler Construction>,增加node是正常的。我不翻译了,直接贴在这里。
 




可惜hex-rays的论坛似乎要正版用户才能注册,麻烦哪位能登录上去的帮我问问。我被这玩艺郁闷得不行,只好考虑先尽可能压缩,减少bb数量。再抱怨一下IDA SDK,严重缺乏文档,经常得到头文件里找东西。