4.窥孔优化(以除法还原示例)
窥孔优化是反编译器一个很重要的还原技术。而且这个技术没有捷径可言，大部分情况，都是特定规则的集合。
这一章将以最经典的“整数除法”为例，展示编译器和反编译器的对于整数除法的优化与还原技术。
编译器对乘法与除法优化
对于很多算数表达式，为了提升效率编译器会进行等价的替换。
典型案例之一就是使用左移替代2的倍数的乘法：
//源码示例，这里a为无符号整数
a = a * 4
//编译器优化后
a = a << 2这一优化就是”窥孔优化“的一种，因为在现代CPU中除法和乘法运算是十分昂贵的，尤其是除法。（据说以前除法比加法慢50倍以上，比乘法慢10倍以上，直到Intel的Cannon Lake架构出现，Cannon Lake将64位整数除法的最大延时从96个周期降为了18个周期。这样除法就只比加法慢20倍，比乘法慢5倍）
实际的情况比想象中更加的复杂，单说加减乘除就有各种优化方法，下面是几个常见的典型除法类的优化示例：
无符号除法优化 https://godbolt.org/z/acm19_div3
//除法优化示例，这里edi为无符号整数
edi = edi / 3
//优化后编译成汇编 即 edi = (edi * 0xaaaaaaab) >> 33
mov eax, edi ; eax = edi
mov edi, 2863311531 ; edi = 0xaaaaaaab
imul rax, rdi ; rax = rax * 0xaaaaaaab
shr rax, 33 ; rax >>= 332.有符号除法优化
3.无符号取余优化
在GCC中，有专门的规则实现这一类优化，叫做match.pd的文件专门描述这一类优化。他是一种类LISP规则语言，反正我是看不懂，可以看上面的注释，看看具体实现了哪种优化。
反编译器的反窥孔优化：
为了将优化后的算式“反向优化”为人类可理解的算法，反编译器和编译器一样，都有这一类的匹配规则，称之为“反窥孔优化”。但是，编译器的窥孔优化不一定是绝对能还原的，所以
我这里以Ghidra为例（IDA不开源，有空再研究这玩意咋实现），Ghidra提供了一些列的规则处理这种特殊情况
https://www.lockshaw.io/static/ghidra/decompiler/doc/classRule.html#details
其中的除法优化示例：RuleDivOpt 类，他会将优化后乘法+右移的功能反编译成除法
公式为：
sub( (zext(V)*c)>>n, 0) => V / (2^n/(c-1))sub( (sext(V)*c)s>>n, 0) => V s/ (2^n/(c-1))
看上面这个公式不太直观。还是举个例子后模拟ghidra的运算方法
参考汇编，代入公式 ( 2^n / (c-1) ) 其中 n=34, c=3435973837
换成整数，约为5，因此可以反编译优化为 x / 5
反窥孔优化简单汇总
下面简单汇总了一些反窥孔优化的项目，都是从ghidra抄的
其中 V、W、X代表变量
c、d代表常量
对抗：不透明谓词混淆
ref:https://www.zhihu.com/question/46259412
ref:https://bbs.kanxue.com/thread-270019.htm
不透明谓词是一套很有趣且实用的静态反编译对抗技术。
它和窥孔优化很像，只不过是反向。窥孔优化从复杂到简单，它从简单到复杂。
通过添加反编译器无法计算的条件进行混淆。
todo：介绍对抗不透明谓词的反编译技术
reference
https://medium.com/@prathamesh1615/adding-peephole-optimization-to-gcc-89c329dd27b3
https://fuzhe1989.github.io/2020/01/22/optimizations-in-cpp-compilers/
https://www.computer.org/csdl/proceedings-article/arith/2005/23660131/12OmNyQYt7U
Last updated