为了便于分析（即静态分析），我计划通过删除后向边将函数的控制流图转换为生成树。我想知道这棵生成树是否可以被认为是一棵二叉树？也就是说，一个基本块是否有可能有 2 个以上的出边？
一个基本块可以有 2 个以上的出边吗？
逆向工程
拆卸
静态分析
控制流图
2021-06-26 09:57:51
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 $0x5,-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 $0x1,%eax
400527: eb 21 jmp 40054a <main+0x5d>
400529: b8 0a 00 00 00 mov $0xa,%eax
40052e: eb 1a jmp 40054a <main+0x5d>
400530: b8 64 00 00 00 mov $0x64,%eax
400535: eb 13 jmp 40054a <main+0x5d>
400537: b8 e8 03 00 00 mov $0x3e8,%eax
40053c: eb 0c jmp 40054a <main+0x5d>
40053e: b8 10 27 00 00 mov $0x2710,%eax
400543: eb 05 jmp 40054a <main+0x5d>
400545: b8 ff ff ff ff mov $0xffffffff,%eax
40054a: 5d pop %rbp
40054b: c3 retq
例如
400520: ff e0 **jmpq *%rax**
指令在这个例子中实现了 switch.case 跳转。显然，以这次跳转结束的基本块将有 6 个外向边。
任何其他间接跳转也可能产生这种情况。
这篇文章中有一些很好的例子。因此，您的问题的答案绝对是肯定的，存在具有 2 个以上出边的基本块，并且您的生成树不能被视为二元树。