对跳表机制及其静态逆向的一些想法

逆向 IDA 编译

 2023/11/06 

之前没有听说过跳转表这个词，查了查什么是跳转表，看起来是个用到一些数据结构思想的有点意思的编译机制🤔。

什么是跳表？

跳转表（jump table）是GCC编译器在汇编时针对C语言的switch语句采用的一种汇编机制。查资料的时候发现CSAPP上有讲，这里就结合书上的内容和自己的理解给出一点解释，那我们先来看看switch是如何在汇编层面实现的吧。

switch开关语句可以根据一个整数索引值进行多重分支，提高了C代码的可读性。通过使用跳转表，它的实现可以更加高效。跳转表是一个数组，表项 i 是一个代码片段的地址，这个片段实现当开关索引值为 i 的时候程序应采取的动作。程序代码使用开关索引值来执行一个跳转表内部的数组引用，确定跳转指令的目标。和 if-else 语句相比，跳转表的优点是执行开关语句的时间与开关情况的数量无关。———摘自《深入理解计算机系统》 3.6.8

先简单说，这就是一个 O(1) 的索引然后跳转。不这样的话，汇编层面会变成一连串的类似“if-else”的连续的 cmp + jcc 结构。那么编译器是怎么分别这两种情况的呢？

汇编器在遇到switch语句的时候会先评估case分支的“稀疏程度”，选择使用来进行编译，还是使用跳转表进行编译。这种判断，本质上是一种时间和空间的权衡。对于cmp+jcc结构的编译方法就不过多赘述，类似于下面这种:

#include<stdio.h>
int main()
{
 int a=5;
 switch(a)
 {
 case 1:
 puts("check out disasm!");
 break;
 case 2:
 puts("check out disasm!");
 case 3:
 puts("check out disasm!");
 break;
 default:
 puts("6");
 }
 return 0;
}

上述代码汇编的结果是：

cmp+jcc编译结构

当汇编器认为开关数量比较多（部分版本是4个以上）并且跨度较小分布密集的时候，就会采用跳转表进行编译，类似下面这种。

#include<stdio.h>
int main()
{
    char a=0, b=0;
    a=getchar();
    switch(a)
    {
        case 'a':
            puts("this is case a");
            b=a;
            break;
        case 'b':
            b=a;
            b++;
            break;
        case 'c':
            printf("%c",b);//被编译为了putchar
            b=a;
            break;
        case 'd':
        puts("this is case d");
            b=a;
            break;
        case 'e':
            break;
        case 'f':
            b=a;
            break;
        case 'g':
            break;
        case 'h':
        puts("this is case h");
            break;
        case 'i':
            b++;
        case 'j':
            b=a;
            break;
        default:
            break;
    }
    return 0;
}

上述代码汇编的结果是：

跳转表编译结构
跳转表：

汇编器首先将所有的整数索引值区间移动到一个“最小值从0开始”的区间上，然后用这个转化后的索引值作为数组下标去跳转表中搜寻地址。跳转表中存放的是“跳转表首地址”和程序段对应的case地址的偏移差值，索引过程中会将基地址和下标索引送入寄存器，加和之后取得绝对地址，最后jmp rax。这里多查了查，发现涉及到了编译优化的一些知识，编译器对于switch的优化方法没有这么简单，甚至可能有二分查找（？？），不多写了摆了。

IDA在面对跳表的时候出了什么问题？

上面那段采用跳转表编译的代码，在IDA中按下F5之后变成了这样：

IDA反汇编

我们可以看到，源代码中对于b的一些赋值操作，自增操作在F5之后统统消失了。这导致如果我们不去观察汇编代码而是只用F5的话，IDA会因为跳表的原因丢失大量的源代码信息和操作（示例是自己随便写的，丢失的不多），如果类似b++这样的逻辑操作非常多而且关键的话，这种错误对我们程序分析是十分致命的。可能IDA会直接翻译出这样一段内容（来自这篇文章），这也代表它在识别跳表的时候出错了：

1
2
3

if (*v5 <= 0xCu>)
    JUMPOUT(__CS__,(char *)dword_403040 + dword_403040[*v5]);
goto LABEL_24

当然，汇编代码是完好的。那有没有什么办法能手动还原原来所有的内容？

手动修复IDA跳表

首先不得不感叹，IDA确实太强了。它居然内置了手动识别switch跳表的功能。不过这里我用上面的代码进行复现的时候，似乎简单的自增和赋值如果后面没有用到的话依然不会被显示。试了几次之后决定摆烂，参考上面提到的文章，整理switch跳表手动识别窗口的一些内容，意思十分明了的略去：

Element shift amount: 元素偏移数值，和switch计算真实跳转地址有关。根据上面的分析我们可以看出，一般的搜寻地址操作只是简单的相加，根据博文推测这一项是最终计算绝对地址的时候加上的偏移。
Seperate Value table is present：不用管，勾选之后会让你单独设置一个case值表。
Signed jump table elements: 表中偏移值为有符号数（负数/低减高）的时候勾选。
Subtract table elements: 减去表中元素？勾选之后得到的c代码没有了具体内容，全部是JUMPOUT(addr)的格式了。
Table element is insn：勾选之后没啥区别。意义不明

这里手动设置了这样的参数之后伪代码依然没显示自增，不知道为什么，可能需要更复杂的逻辑吧？不过跳表的手动修复方法大体就是这样。后续遇到题目再更新。

Next Post

How2Heap(1)-fastbin（完整版）
Previous Post

pwntools的shellcode逻辑详解

CATALOG

1. 什么是跳表？
2. IDA在面对跳表的时候出了什么问题？
3. 手动修复IDA跳表