C++逆向：switch-case逆向分析与还原
编辑
2430
2021-08-07
switch-case的效率为什么在某些条件下会比if-else效率高，而不是在什么时候都会比if-else效率高呢？通过研究switch-case的原理就可以得到上述问题的答案
...
大纲
- case的数量小于等于3个，且case值连续
- case的数量大于3个，但case值较为连续，即：最大case值和最小case值之间的间隔不大于7
- case的数量大于3个，且case值相隔较大，且最大case值和最小case值之间的间隔不能超过255
- case的值大于3个，且case值较为离散。
- 混合方案。当不能单独用上述4种优化方案时使用。当个数小于等于3个，直接比较就行了，就不再进行折半查找了。
测试环境
MSVC + VC6 + Release，速度优先编译选项。选用VC6的原因是编译器没有其他额外的操作，如：安全cookie之类的信息，方便观察。其实switch-case的这几种方式在VS2019中也是一样的
优化方案一：直接if-else
适用于：case的数量小于等于3个，且case值连续的情况。
测试代码：
int main(int argc, char* argv[])
{
switch (argc)
{
case 1:
printf("case 1");
break;
case 2:
printf("case 2");
break;
case 3:
printf("case 3");
}
return 0;
}
反汇编结果：
.text:00401000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:00401000 _main proc near ; CODE XREF: start+AFp
.text:00401000
.text:00401000 arg_0 = dword ptr 4
.text:00401000
.text:00401000 mov eax, [esp+arg_0]
.text:00401004 dec eax
.text:00401005 jz short LBL_CASE1
.text:00401005
.text:00401007 dec eax
.text:00401008 jz short LBL_CASE2
.text:00401008
.text:0040100A dec eax
.text:0040100B jnz short LBL_EXIT
.text:0040100D LBL_CASE3: ; "case 3"
.text:0040100D push offset s->Case3
.text:00401012 call printf
.text:00401012
.text:00401017 add esp, 4
.text:0040101A xor eax, eax
.text:0040101C retn
.text:0040101C
.text:0040101D ; ---------------------------------------------------------------------------
.text:0040101D
.text:0040101D LBL_CASE2: ; CODE XREF: _main+8j
.text:0040101D push offset s->Case2 ; "case 2"
.text:00401022 call printf
.text:00401022
.text:00401027 add esp, 4
.text:0040102A xor eax, eax
.text:0040102C retn
.text:0040102C
.text:0040102D ; ---------------------------------------------------------------------------
.text:0040102D
.text:0040102D LBL_CASE1: ; CODE XREF: _main+5j
.text:0040102D push offset s->Case1 ; "case 1"
.text:00401032 call printf
.text:00401032
.text:00401037 add esp, 4
.text:00401037
.text:0040103A
.text:0040103A LBL_EXIT: ; CODE XREF: _main+Bj
.text:0040103A xor eax, eax
.text:0040103C retn
.text:0040103C
.text:0040103C _main endp
可以发现，其为了提高速度，其直接将共有的退出代码：
xor eax, eax
retn
放到了各个case后面，直接退出了。
其在比较到底是选择哪个case的时候，与if-else的差不多：
cmp xxxx
jz xxxx ; 跳转到对应的case代码块
cmp xxxx
jz xxxx
cmp xxxx
jnz xxxx ; default / case_end
当没有break的时候，则生成的引导表是按照你写的顺序；如果有break，则顺序就无所谓了。
优化方案二：跳转表方案
适用于：case的数量大于3个，但case值较为连续，即：最大case值和最小case值之间的间隔不大于7的情况。
实验代码：
int main(int argc, char* argv[])
{
switch (argc)
{
case 1:
printf("case 1");
break;
case 2:
printf("case 2");
break;
case 3:
printf("case 3");
break;
case 4:
printf("case 4");
break;
case 5:
printf("case 5");
break;
case 6:
printf("case 6");
break;
default:
printf("default");
}
return 0;
}
反汇编结果：
.text:00401000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:00401000 _main proc near ; CODE XREF: start+AFp
.text:00401000
.text:00401000 arg_0 = dword ptr 4
.text:00401000
.text:00401000 mov eax, [esp+arg_0]
.text:00401004 dec eax
.text:00401005 cmp eax, 5 ; switch 6 cases
.text:00401008 ja short LBL_DEFAULT ; jumptable 0040100A default case
.text:00401008
.text:0040100A jmp ds:aryJumpTable[eax*4] ; switch jump
.text:0040100A
.text:00401011
.text:00401011 LBL_CASE1: ; DATA XREF: .text:aryJumpTableo
.text:00401011 push offset s->Case1 ; jumptable 0040100A case 0
.text:00401016 call printf
.text:00401016
.text:0040101B add esp, 4
.text:0040101E xor eax, eax
.text:00401020 retn
.text:00401020
.text:00401021 ; ---------------------------------------------------------------------------
.text:00401021
.text:00401021 LBL_CASE2: ; CODE XREF: _main+Aj
.text:00401021 ; DATA XREF: .text:aryJumpTableo
.text:00401021 push offset s->Case2 ; jumptable 0040100A case 1
.text:00401026 call printf
.text:00401026
.text:0040102B add esp, 4
.text:0040102E xor eax, eax
.text:00401030 retn
.text:00401030
.text:00401031 ; ---------------------------------------------------------------------------
.text:00401031
.text:00401031 LBL_CASE3: ; CODE XREF: _main+Aj
.text:00401031 ; DATA XREF: .text:aryJumpTableo
.text:00401031 push offset s->Case3 ; jumptable 0040100A case 2
.text:00401036 call printf
.text:00401036
.text:0040103B add esp, 4
.text:0040103E xor eax, eax
.text:00401040 retn
.text:00401040
.text:00401041 ; ---------------------------------------------------------------------------
.text:00401041
.text:00401041 LBL_CASE4: ; CODE XREF: _main+Aj
.text:00401041 ; DATA XREF: .text:aryJumpTableo
.text:00401041 push offset s->Case4 ; jumptable 0040100A case 3
.text:00401046 call printf
.text:00401046
.text:0040104B add esp, 4
.text:0040104E xor eax, eax
.text:00401050 retn
.text:00401050
.text:00401051 ; ---------------------------------------------------------------------------
.text:00401051
.text:00401051 LBL_CASE5: ; CODE XREF: _main+Aj
.text:00401051 ; DATA XREF: .text:aryJumpTableo
.text:00401051 push offset s->Case5 ; jumptable 0040100A case 4
.text:00401056 call printf
.text:00401056
.text:0040105B add esp, 4
.text:0040105E xor eax, eax
.text:00401060 retn
.text:00401060
.text:00401061 ; ---------------------------------------------------------------------------
.text:00401061
.text:00401061 LBL_CASE6: ; CODE XREF: _main+Aj
.text:00401061 ; DATA XREF: .text:aryJumpTableo
.text:00401061 push offset s->Case6 ; jumptable 0040100A case 5
.text:00401066 call printf
.text:00401066
.text:0040106B add esp, 4
.text:0040106E xor eax, eax
.text:00401070 retn
.text:00401070
.text:00401071 ; ---------------------------------------------------------------------------
.text:00401071
.text:00401071 LBL_DEFAULT: ; CODE XREF: _main+8j
.text:00401071 push offset s->Default ; jumptable 0040100A default case
.text:00401076 call printf
.text:00401076
.text:0040107B add esp, 4
.text:0040107E xor eax, eax
.text:00401080 retn
.text:00401080
.text:00401080 _main endp
.text:00401080
.text:00401080 ; ---------------------------------------------------------------------------
.text:00401081 align 4
.text:00401084 aryJumpTable dd offset LBL_CASE1 ; DATA XREF: _main+Ar
.text:00401084 dd offset LBL_CASE2 ; jump table for switch statement
.text:00401084 dd offset LBL_CASE3
.text:00401084 dd offset LBL_CASE4
.text:00401084 dd offset LBL_CASE5
.text:00401084 dd offset LBL_CASE6
.text:0040109C align 10h
跳转表jumpTable是个指针数组，里面存放着各个CASE的地址：
.text:00401084 aryJumpTable dd offset LBL_CASE1 ; DATA XREF: _main+Ar
.text:00401084 dd offset LBL_CASE2 ; jump table for switch statement
.text:00401084 dd offset LBL_CASE3
.text:00401084 dd offset LBL_CASE4
.text:00401084 dd offset LBL_CASE5
.text:00401084 dd offset LBL_CASE6
在switch-case的入口处：
.text:00401000 mov eax, [esp+arg_0]
.text:00401004 dec eax
.text:00401005 cmp eax, 5 ; switch 6 cases
.text:00401008 ja short LBL_DEFAULT ; jumptable 0040100A default case
.text:00401008
.text:0040100A jmp ds:aryJumpTable[eax*4] ; switch jump
可以发现其为了利用跳转表的下标来进行寻址，需要将case值与数组下标相对应，因此需要减掉最小的那个case值。在本例中，也就是需要减掉最小的case值1，因此在入口处，首先将要测试的值减去1，然后与最大下标进行比较，如果大于，则说明是不在case范围内，直接跳转到default处进行处理即可，否则直接利用数组下标寻址公式来进行寻址到正确的case地址即可。
由于是使用的指针数组来进行寻址的，所以当case打乱的情况下，其填充进该数组中也是有序的，所以在生成跳转表的时候，跟你是否写的有序无关。
还原时，别忘了将case值加上最小的那个case值，才能得到真正的case值。
优化方案3：索引表和跳转表组合方案
适用于：case的数量大于3个，且case值相隔较大，且最大case值和最小case值之间的间隔不能超过255的情况。
实验代码：
int main(int argc, char* argv[])
{
switch (argc)
{
case 40:
printf("case 40");
break;
case 91:
printf("case 91");
break;
case 62:
printf("case 62");
break;
case 73:
printf("case 73");
break;
case 14:
printf("case 14");
break;
case 25:
printf("case 25");
break;
default:
printf("default");
}
return 0;
}
对于该实验代码，其在跳转表的基础上，又多了一张表，其大小为1个字节，即：可以表示的最大范围是0 - 255,
.text:00401000 mov eax, [esp+arg_0]
.text:00401004 add eax, 0FFFFFFF2h
.text:00401007 cmp eax, 4Dh ; switch 78 cases
.text:0040100A ja short LBL_DEFAULT ; jumptable 00401014 default case
.text:0040100A
.text:0040100C xor ecx, ecx
.text:0040100E mov cl, ds:indexTable[eax]
.text:00401014 jmp ds:jumpTable[ecx*4] ; switch jump
对应的两张表分别为：
.text:0040108C jumpTable dd offset loc_40105B ; DATA XREF: _main+14r
.text:0040108C dd offset loc_40106B ; jump table for switch statement
.text:0040108C dd offset loc_40101B
.text:0040108C dd offset loc_40103B
.text:0040108C dd offset loc_40104B
.text:0040108C dd offset loc_40102B
.text:0040108C dd offset LBL_DEFAULT
.text:004010A8 indexTable db 0,6,6,6,6,6,6,6,6,6 ; DATA XREF: _main+Er
.text:004010A8 db 6,1,6,6,6,6,6,6,6,6 ; indirect table for switch statement
.text:004010A8 db 6,6,6,6,6,6,2,6,6,6
.text:004010A8 db 6,6,6,6,6,6,6,6,6,6
.text:004010A8 db 6,6,6,6,6,6,6,6,3,6
.text:004010A8 db 6,6,6,6,6,6,6,6,6,4
.text:004010A8 db 6,6,6,6,6,6,6,6,6,6
.text:004010A8 db 6,6,6,6,6,6,6,5
可以发现，在索引表indexTable中，6代表的是跳转表的下标，即：LBL_DEFAULT 。因此在还原时，只需要先查索引表，然后加上最小的case值，即可还原。
优化方案四：二叉排序树方案
实验代码：
int main(int argc, char* argv[])
{
switch (argc)
{
case 40:
printf("case 40");
break;
case 91:
printf("case 91");
break;
case 62:
printf("case 62");
break;
case 296:
printf("case 73");
break;
case 289:
printf("case 14");
break;
case 257:
printf("case 257");
break;
default:
printf("default");
}
return 0;
}
反汇编结果：
.text:00401000 ; int __cdecl main(int argc, const char **argv, const char **envp)
.text:00401000 _main proc near ; CODE XREF: start+AFp
.text:00401000
.text:00401000 arg_0 = dword ptr 4
.text:00401000
.text:00401000 mov eax, [esp+arg_0]
.text:00401004 cmp eax, 257
.text:00401009 jg short LBL_NEXT_BRANCH
.text:00401009
.text:0040100B jz short LBL_CASE257
.text:0040100B
.text:0040100D cmp eax, 40
.text:00401010 jz short LBL_CASE40
.text:00401010
.text:00401012 cmp eax, 62
.text:00401015 jz short LBL_CASE62
.text:00401015
.text:00401017 cmp eax, 91
.text:0040101A jnz short LBL_DEFAULT
.text:0040101A
.text:0040101C push offset s->Case91 ; "case 91"
.text:00401021 call printf
.text:00401021
.text:00401026 add esp, 4
.text:00401029 xor eax, eax
.text:0040102B retn
.text:0040102B
.text:0040102C ; ---------------------------------------------------------------------------
.text:0040102C
.text:0040102C LBL_CASE62: ; CODE XREF: _main+15j
.text:0040102C push offset s->Case62 ; "case 62"
.text:00401031 call printf
.text:00401031
.text:00401036 add esp, 4
.text:00401039 xor eax, eax
.text:0040103B retn
.text:0040103B
.text:0040103C ; ---------------------------------------------------------------------------
.text:0040103C
.text:0040103C LBL_CASE40: ; CODE XREF: _main+10j
.text:0040103C push offset s->Case40 ; "case 40"
.text:00401041 call printf
.text:00401041
.text:00401046 add esp, 4
.text:00401049 xor eax, eax
.text:0040104B retn
.text:0040104B
.text:0040104C ; ---------------------------------------------------------------------------
.text:0040104C
.text:0040104C LBL_CASE257: ; CODE XREF: _main+Bj
.text:0040104C push offset s->Case257 ; "case 257"
.text:00401051 call printf
.text:00401051
.text:00401056 add esp, 4
.text:00401059 xor eax, eax
.text:0040105B retn
.text:0040105B
.text:0040105C ; ---------------------------------------------------------------------------
.text:0040105C
.text:0040105C LBL_NEXT_BRANCH: ; CODE XREF: _main+9j
.text:0040105C sub eax, 289
.text:00401061 jz short LBL_CASE289
.text:00401061
.text:00401063 sub eax, 7
.text:00401066 jz short LBL_CASE73
.text:00401066
.text:00401068
.text:00401068 LBL_DEFAULT: ; CODE XREF: _main+1Aj
.text:00401068 push offset s->Default ; "default"
.text:0040106D call printf
.text:0040106D
.text:00401072 add esp, 4
.text:00401075 xor eax, eax
.text:00401077 retn
.text:00401077
.text:00401078 ; ---------------------------------------------------------------------------
.text:00401078
.text:00401078 LBL_CASE73: ; CODE XREF: _main+66j
.text:00401078 push offset s->Case73 ; "case 73"
.text:0040107D call printf
.text:0040107D
.text:00401082 add esp, 4
.text:00401085 xor eax, eax
.text:00401087 retn
.text:00401087
.text:00401088 ; ---------------------------------------------------------------------------
.text:00401088
.text:00401088 LBL_CASE289: ; CODE XREF: _main+61j
.text:00401088 push offset s->Case14 ; "case 14"
.text:0040108D call printf
.text:0040108D
.text:00401092 add esp, 4
.text:00401095 xor eax, eax
.text:00401097 retn
.text:00401097
.text:00401097 _main endp
发现其使用的就是二叉排序树的形式来进行的，这样的话通过折半查找，几次之后就能得到最终要执行的那一个case分支，查找效率较大的提高。
该方案的代码定式就是：
cmp
jz
jg
; // 两轮判断下来，最后肯定执行的是小于的那一分支
还原时就是抓住jz指令即可还原
优化方案五：混合优化
在实际应用中，几乎不会出现单一的优化形式，是上述4种方式的混合方案，不再赘述。
- 1
-
分享