逆向工程 | C 语言之 switch-case 分支

switch-case的诞生其实就是为了避免出现大量的、高重复的if-else语句。换句话说，switch-case语句其实就是if-else语句的另一种体现形式。

一、简单switch-case分支

我们先看一段典型的switch-case代码，如代码清单1所示。

代码清单1  简单switch-case分支

看完这段代码，您可能会产生如下疑问：

switch-case的不可达分支会被剪掉吗？

switch-case分支以常量为判断条件的优化效果与if-else有多大区别？

以变量为判断条件的switch-case分支优化效果与if-else分支有多大区别？

现在就让我们带着这些问题继续，一一为其找到答案。先看代码清单2。

代码清单2  简单switch-case分支的Debug版反汇编代码

通过代码清单2，我们可以总结出以下特点：

我们可以看到，Debug版的反汇编指令与我们的源代码的相似度还是非常高的，都是通过开始的一连串判断，然后确定接下来走哪个case分支。下面我们再看看Release版的反汇编代码：

又是一段被优化得简单至极的代码，由此可见switch-case语句与我们之前接触的if-else语句一样，不可达分支都会被编译器优化掉。那么如果其部分分支相同，是否仍会像if-else分支一样被归并优化呢？先看代码清单3。

代码清单3  switch-case语句的分支归并演示代码

按照if-esle的优化逻辑，case 1与csae 2会指向同一处，真的是这样吗？我们直接看代码清单4。

代码清单4  switch-case语句的分支归并演示代码的Release版反汇编代码

看来switch-case并没有将相同的分支合并，我们可以很清楚地看到它的4个分支仍都存在。

既然它的分支并没有合并，那么我们就讨论点其他的，请您回头仔细观察代码清单4所示的反汇编代码的第1～9行，我们可以发现Release在条件跳转前用的不再是cmp，而是sub，很显然编译器这样优化是有其理由的，但是这个理由究竟是什么？

我们通过阅读这块代码可知，程序先将main（）函数的参数1传递给EAX，然后减0，这让人有点迷糊。我们接着看下面的那个跳转：

让我们回顾一下汇编语言，大家应该都记得JE的跳转条件是ZF=1，因此当EAX为0时，那么将其减0肯定会使ZF位置1，而其实这就是一个变形的CMP指令，只不过这么做会使代码体积更小、效率更高。

知道这些后，后面的优化就很好理解了。现在假设EAX等于2，因此按照上面代码的流程走会先将其减0，此时ZF位不变；接着下面又对EAX减1，此时ZF位仍然没变化；而当走到第三步时，此时EAX的值为1，又将其减1后肯定就等于0了，ZF位置为1，后面的JZ跳转生效。

我们可以看到，其实上述操作就是做了一连串的减法，到哪等于0后，就证明这个值原先为多少，由此可见微软的编译器还是很聪明的。

二、复杂分支的switch-case

我们平时在写程序时都会遇到一些问题，而这些问题中有一部分必须要用复杂分支的switch-case才能解决。但是这种情况在反汇编状态下应该怎么去识别呢？下面我们就一起看看switch-case的另外一种体现方式，如代码清单5所示。

代码清单5  复杂分支的switch-case

注意上面的case条件并不是有规律的，我们再看代码清单6。

代码清单6  复杂分支的switch-case的Release版反汇编代码

看完上段反汇编代码后有些朋友可能感觉很奇怪，难道那个位于第4行的jmp指令就能解决这些问题吗？当然不会这么简单。

我们现在就仔细分析一下代码清单6中的前几条反汇编指令。

那么目标地址里究竟保存了什么数据？这个机制的原理又是怎么回事呢？下表中的内容就是目标地址中保存的数据，因此由下表便可以猜出一二了。

上表中的地址（Address）列就是我们上面提到的“指针数组”了，里面保存的内容是各个case块的地址，我们将之称为“跳转表”。跳转表的作用就是用数组的寻址运算代替复杂的if-else分支，这样可以大大提高程序的执行效率。

它的基本原理是建立一张表格，里面保存着从case1到caseN的所有分支应该到达的地址。以代码清单5的情况为例子，我们可以看出从case2至case5里保存的地址都是Default分支的地址，这就证明这几个case在程序的源代码中是属于未处理（或称为非正常）的状态。

三、switch-case分支结构与稀疏矩阵

我们前面分别介绍了转成if-esle与利用跳转表两种优化模式。但是当switch-case分支两个数之差大于50甚至更多的时候，编译器是否仍需要利用跳转表来解决问题呢？我们先看看代码清单7。

代码清单7  产生稀疏矩阵的switch-case分支结构

我们通过上面这个稍显极端的例子可以发现，如果此时编译器仍以跳转表的方式来优化的话，那么这会使得编译出来的代码具有多达788字节的冗余数据，至少会使其体积变为用Debug模式生成代码体积的2.7倍以上！

与编译器打这么长时间的交道，我们猜也能猜得出编译器肯定不会使用这么笨的方法，由此便引出了“稀疏矩阵”。

“稀疏矩阵”这名字起得很好，正可谓阅名知意，通过名字我们就可以猜到这应该是一个用来表达稀疏数据的阵列，正好可以用于我们刚刚所提到的这种情况。

那么我们的switch-case分支结构什么时候才会用到稀疏矩阵，而稀疏矩阵又是怎么回事呢？

（1）什么是稀疏矩阵？

稀疏矩阵就是零元素或同一元素占全部元素的百分比很小（例如5%以下）的矩阵。

（2）什么时候应用稀疏矩阵？

由于每个编译器所使用的策略不一样，因此其“体积-效率比”权值的设定也不尽相同。如果使用跳转表生成的代码的体积大于使用稀疏矩阵的体积，那么一般情况下编译器就会选择使用稀疏矩阵来优化此段代码。

当然稀疏矩阵的具体定义及其特点还有很多，现在我们着重讲解一下编译器优化时所使用的稀疏矩阵是什么情况。

其实当我们深入接触稀疏矩阵这种优化方式之后可以发现，编译器所用的优化方案仅仅是思路上借鉴了稀疏矩阵，其实际使用中并不符合稀疏矩阵的相关定义，因此将其称为“间接表”更为合适一些。因此在后面将用“间接表”来代替稀疏矩阵这一名词，这一点要特别注意。

现在就让我们一起看一看switch-case分支结构的间接表是怎么回事。

首先，在VC系列编译器中，针对switch-case分支结构的间接表都是用1字节表示的，因此其最小索引值与最大索引值之差不得大于256，否则此优化方法便不再适用。

其次，这个拥有256字节型元素的数组（间接表）需要与跳转表相呼应才能保证程序流程最终执行到正确的地方。下面我就带领您深入了解一下间接表是怎样被体现出来的。

鉴于以后知识的复杂性，从现在开始，我们不再使用OllyDbg，因此也请您一起转换到IDA这个更专业的逆向工作平台上去。

下面我们以代码清单7为例，看看IDA生成的反汇编代码是不是更易读易懂。Release版反汇编代码如代码清单8所示。

代码清单8  产生稀疏矩阵的switch-case的Release版反汇编代码

上面的反汇编代码已经足以表明IDA的强大之处了，很明显它已经自动识别出了这就是一个switch-case语句，并为我们生成了清晰明了的注释。

但是在这里要提醒您注意，IDA也并不是每次都能准确分析出正确的结果的（在实战时大多数情况都会“碰巧”遇到各种问题），因此在学习逆向时一定要注意学会忽略IDA的注释，否则总有一天会出问题的。

通过上面的代码我们可以分析出主要是以下两句代码在控制其流程：

为了更好地理解第一句汇编指令的意思，我们需要看看4010A8处保存了些什么信息。

由于我们的switch-case分支结构拥有6个分支，因此间接表里保存的索引内容都是在0～5之间的，然后便根据此索引来确定调转到第几个分支上去。

下面我们来人工模拟一下，假如此时switch-case分支结构接收到的判断变量为166，那么首先会通过执行"mov eax，[esp+argc]"将值传递给eax，进行简单的对比检查之后，已确定其值未超过switch-case分支的最大值。然后就通过执行"movzx ecx,ds:byte_4010A8[eax]"指令，以eax为索引到地址为4010A8h的间接表中，寻取相对应的值为跳转表索引，并将此索引保存在ecx里，最后再以ecx为索引执行"jmp ds:off_401090[ecx*4]"指令，跳转到正确的分支上去。整体如下所示：

通过上面这个流程我们可以发现，间接表是与跳转表结合起来使用的，这样做使得编译器充分利用了稀疏矩阵空间与时间上的优势。

四、switch-case分支结构与平衡二叉树

通过上面的介绍我们知道，间接表的应用只限于分支小于等于256的情况，如果超过256这种与跳转表相配合的间接表就会失效，取而代之的便是著名的二叉树了（准确地说应该叫平衡二叉树）。下面简单介绍一下二叉树查找法。

所谓的二叉树查找法我们也可以暂时将其理解为折半查找法。例如我们想快速在1～7几个数字中找到某个数值，那么最快的方法是现将其与1～7的中间数4作比对，看看它是比4小还是比4大，如果比4大的话那么就在4～7之间取中间数6与其比对，如果大于6那么这个数就是7，如果小于6那么这个数就是5了。而比4小的情况，处理过程类似。如果将所有的可能性画成一个流程图的话，那么这幅图大概就是图1所示的样子。

图1  一个二叉树的例子

由此可知当，比对次数（深度）为k时，则最多需要查找2·（k-1）个结点。例如，用此算法查找40万条数据中的某一条的话，那么比对次数不会超过20次（220-1=524288＞4×105）。大致了解了二叉树的原理与优势之后，我们先看代码清单9。

代码清单9  会产生二叉树的switch-case

这是一段很长的代码，下面是Release版的反汇编代码（有删节），如代码清单10所示。

代码清单10  会产生二叉树switch-case的Release版反汇编代码

对于这种二叉树结构的识别，一般情况下只需要看两步跳转即可，如果其每次跳转所对比的值都是其后面分支跳转的中间值之一，那么这就有可能是一个二叉树。我们以本程序为例，第一次跳转及其后面的分支如下：

我们不难发现，上面的第一个跳转所对比的值位于其后面两个分支对比值的区域中。我们再跟进分支1看看。

同样，分支1也是位于其两个子分支比对值的区域内，现在我们至少就有60%的把握可以确定这是一个二叉树结构了。当然，如果想要得到更为精准的结果，还是要把大部分流程跟一遍的，如图2所示就是本二叉树的结构图。

图2  代码清单9-33所示的二叉树结构

其实上面的代码是经过细心修剪过的，所以看起来结构清晰明了。当我们实际做逆向时也应该如此，在一开始要去其枝蔓留其骨干，这样才能更为顺利地识别类似于二叉树这样较复杂的数据结构。

上面讲解了两种数据结构（间接表和二叉树），其实对于switch-case分支结构的识别就是对这两种数据结构的识别。但是我们怎样才能知道这种数据结构是编译器生成的，而并非是别人写的代码呢？这个问题很难回答，我们的逆向工程越是复杂，其理论上的不确定性也越高。就像上面的代码，如果我们将所有分支按照二叉树的规则排好序，并用if-else分支来实现它的话，那么其生成的代码与以上反汇编代码不会相差多少。有兴趣的朋友可以自己试验一下。