反汇编算法介绍和应用——递归下降算法分析
上一篇博文我介绍了Windbg使用的线性扫描（linear sweep）反汇编算法。本文我将介绍IDA使用的递归下降（recursive descent）反汇编算法。（转载请指明来源于breaksoftware的csdn博客）
递归（recursive）可能大家都很清楚，说白了就是自己调用自己。那么什么是recursive descent呢？似乎很难理解。recursive还是有循环和回归的意思，那么recursive descent就可以理解为“不停减少的循环”和“不停减少的回归”。或许这么说还是不是很好理解，那我们来研究下这个算法的思路的来源，这样可以容易理解这个算法的精髓。
回顾《反汇编算法介绍和应用——线性扫描算法分析》，我们知道线性扫描一个很大的缺点是：因为其不知道程序执行流而导致将数据识别为代码。我们可能会骂这个算法不智能，那么如何才能智能起来呢？想想我们的二进制文件在系统中正常运行时是不会出错的，因为CPU总是可以找到真正的指令起始地址，那么我们反汇编算法只要能模拟CPU执行指令就可以得到正确的反汇编结果了。OK！没错，递归下降算法一个主要的思路就是源于这样的思考结果。但是我们反汇编是静态的，而CPU执行指令是动态的，静态分析无法得知动态执行的结果，这个严重的缺陷会导致我们想完全模拟CPU执行去反汇编的思路变得不现实。但是不要退却，没有完美的方案，只有最可以接受的方案。那我们开始研究下怎么修改我们的思路,让我们的算法变得“最令人可以接受”。
研究修改的方法之前我们要了解CPU执行指令“顺序”的一些基础知识，知己知彼百战百胜。
A 顺序流指令
熟悉汇编的朋友，应该对add、sub、mov、push和pop等指令很熟悉，这类指令执行后，会执行与其地址紧接着的下一条指令。CPU识别这类指令如线性扫描一般简单，那么我们的递归下降算法也就如线性扫描方式去识别这样的指令就行了。
B 无条件跳转指令
jmp是无条件跳转指令。CPU执行这条指令后会跳转到jmp指令参数所指向的地址。这个操作对CPU来说，和顺序流指令没什么区别，只是将EIP改成要跳转的地址。但是这个动态的过程却害惨了静态分析的线性扫描算法，那我们递归下降算法要吸取教训：我们从jmp到的地址开始分析下一条指令。貌似这个想法天衣无缝，但是现实往往是残酷的。请问你一定能得到jmp的地址么？对于jmp 00401010这类的指令我们当然可以得到下条指令的地址，即0x00401010。那么jmp eax呢？eax是多少？CPU知道，我们不知道。这个缺陷我们Mark下。
C 有条件跳转指令
ja和je等是有条件跳转指令，即符合某些要求后才执行跳转，不符合要求则执行其紧接着的那条指令。这些指令的执行顺序如同A、B两种指令的灵魂附体。即条件为真，则走A流程分支；条件为假，则走B流程分支。这么一拆解，我想递归下降算法怎么去分析有条件跳转指令就清楚了。
但是有个问题需要说下，CPU执行这类指令时是知道要走A流程分支还是要走B流程分支的，它不会同时一起走这两条流程。而且可能整个程序运行完了，这个指令的一个分支还没走过（比如if(1){}else{}，else永远进不去的）。而我们的递归下降算法是要分析出所有分支的！
那怎么办呢？那我们就将A和B分支的地址中的某一个优先分析，另一个延后分析。可是手心手背都是肉，我们如何取舍？这个时候，我们就要学习国羽和国乒的做法——不惜“让球”，也要选择出最有利于目前流程顺利进行的方法。那么A、B这两个孩子谁有缺陷呢？如上所述，A流程分支没缺陷，而B流程分支存在一定的隐患。那我们就将要执行跳转的B流程分支保存到一个延后分析的列表中。
最后说一句：C有B的灵魂，C有B的缺陷。
D 函数调用指令
call指令是函数调用指令，但是目前，我们可以将其看成B流程。或许有人会说call指令怎么会和jmp混为一谈呢？我们看一个call例子
想想，如果我们将紧跟call指令的分支优先分析，将会出现将0xE8当成call来解析的情况。那么或许之后得靠跳转分支的分析结果再来纠正，这样还不如优先反汇编跳转分支。说了这么多，再说说上面所说的如何利用call指令分析的缺陷。通过以上例子，我们发现，如果让递归下降算法不知道其call后跳转分支的返回地址，然后在紧跟call指令的位置插入一些废信息，那就造成IDA分析失败了。看例子
看！已经错了，当然windbg也是分析错的。
到此，关于反汇编算法的两篇博文写完了。仅供大家参考。
