为了便于分析(即静态分析),我计划通过删除后边缘将函数的控制流图转换为生成树。我想知道这棵生成树是否可以视为二叉树?也就是说,基本块是否可以具有两个以上的向外边缘?

#1 楼

它取决于目标的汇编语言和编译可执行文件的编译器。
例如,C语言的switch / case子句可能以某种方式实现,从而使您的树不是二进制的。

switch (a)
{
case 1:
    return 1;
break;
case 2:
    return 10;
break;
case 3:
    return 100;
break;
case 4:
    return 1000;
break;
case 5:
    return 10000;
break;
default:
    return -1;
break;
}


00000000004004ed <main>:
  4004ed:   55                      push   %rbp
  4004ee:   48 89 e5                mov    %rsp,%rbp
  4004f1:   89 7d fc                mov    %edi,-0x4(%rbp)
  4004f4:   48 89 75 f0             mov    %rsi,-0x10(%rbp)
  4004f8:   83 7d fc 05             cmpl   
400520: ff e0                   **jmpq   *%rax**
x5,-0x4(%rbp) 4004fc: 77 47 ja 400545 <main+0x58> 4004fe: 8b 45 fc mov -0x4(%rbp),%eax 400501: 48 8d 14 85 00 00 00 lea 0x0(,%rax,4),%rdx 400508: 00 400509: 48 8d 05 c4 00 00 00 lea 0xc4(%rip),%rax # 4005d4 <_IO_stdin_used+0x4> 400510: 8b 04 02 mov (%rdx,%rax,1),%eax 400513: 48 63 d0 movslq %eax,%rdx 400516: 48 8d 05 b7 00 00 00 lea 0xb7(%rip),%rax # 4005d4 <_IO_stdin_used+0x4> 40051d: 48 01 d0 add %rdx,%rax 400520: ff e0 **jmpq *%rax** 400522: b8 01 00 00 00 mov q4312078qx1,%eax 400527: eb 21 jmp 40054a <main+0x5d> 400529: b8 0a 00 00 00 mov q4312078qxa,%eax 40052e: eb 1a jmp 40054a <main+0x5d> 400530: b8 64 00 00 00 mov q4312078qx64,%eax 400535: eb 13 jmp 40054a <main+0x5d> 400537: b8 e8 03 00 00 mov q4312078qx3e8,%eax 40053c: eb 0c jmp 40054a <main+0x5d> 40053e: b8 10 27 00 00 mov q4312078qx2710,%eax 400543: eb 05 jmp 40054a <main+0x5d> 400545: b8 ff ff ff ff mov q4312078qxffffffff,%eax 40054a: 5d pop %rbp 40054b: c3 retq


例如

q4312078q

指令实现switch.case跳转。显然,以该跳转结束的基本块将具有6个向外的边缘。

任何其他间接跳转也可能导致这种情况。

本文中有一些很好的例子。
因此,对您的问题的回答肯定是,有些基本块的边缘超过2个,并且生成树不能视为二进制。

评论


我同意你的回答。但是,如果它是间接的jmp,那么甚至有可能无需使用任何程序分析技术(例如VSA(值集分析))来确定jmp目标。在这种情况下(即无法静态解决间接跳转,这在大多数情况下很常见)。是否可以安全地假设它仅跳到1个目标?

– Maggie
2015年11月1日,11:25



如果我正确理解您的问题,那是不安全的。想到的最简单的示例是带有对虚函数的调用的C ++代码。

– w s
2015年11月1日在11:41

开关也可以编译为jmp [table + 4 * offset],在这种情况下,您可能会有很多分支。

–杂件
15年11月1日在15:03

ARM体系结构具有两个32位Thumb指令,TBB和TBH,用于像这样的简单跳转表计算。 infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489c/…

–伊恩·库克(Ian Cook)
2015年11月3日,7:26