同志们，我又来搞阿里的混淆了。开个小玩笑，不能老搞阿里。以前选择阿里作为自己的研究对象，一是他们的混淆因为有足够的强度和代表性；二是阿里较其他厂要开放些，只进行技术交流分享，不恶意分析应用业务逻辑的文章一般都能正常发出。不过它作为我常驻的测试用例，后面还是有点戏份。

代码混淆是个令很多人头疼不已的问题，一个简单的流程平坦混淆就能急剧降低我们逆向分析效率，一个间断跳转混淆，就能废掉IDA等静态分析工具的武功，VM防护更是另大多数选手束手无策。各个大厂，安全厂商都有自己的混淆器，阿里甚至有几套VM防护。各种混淆方案，加上编译器优化使得我们很难写出通用的反混淆算法。

能否有一个通用的，不需进行反混淆就能直接分析我们关注的应用逻辑的方法呢？我将会在本文分享我的尝试。

我这里使用的技术称为时间无关调试。我理解的时间无关调试就是记录程序执行过程中的寄存器，和内存变化，使用记录的trace离线调试分析的过程，简而言之记录trace，分析trace。最初的qira(https://github.com/geohot/qira)，微软的TTD(Time Travel Debugging)，mozilla的record-replay debugging(https://github.com/rr-debugger/rr) 他们本质都是一样的，感兴趣的朋友可以自行搜索相关资料。

我的时间无关调试器分为两部分，trace记录器和trace分析器。记录器的相关信息可以在我上个帖子找到，分析器也就是我们的调试界面。trace分析功能和调试界面最近刚完工，经过简单的测试后就有点儿想迫不及待的想试试它的威力了。这次选用的样本是看雪论坛2021年11月份3w班的一道题目，题目具体信息见(https://bbs.pediy.com/thread-270220.htm)。

先秀工具。

与实时调试器类似的寄存器试图。

没错，我们可以像实时调试器一样浏览任意程序点，任意地址的内存内容。有朋友可能会注意到，为什么内存会有"??"显示？这是因为这块内存在trace的过程中未被访问，我只在内存被使用（读写）的时候才会记录其内容。在其中双击任意已知内容，可以在指令流视图中跳转到他的定义，一般为写入它的指令。

交叉引用视图显示当前指令的寄存器，内存交叉引用。"<-"是使用定义链，表示某条指令定义的值会被当前指令使用。"->"是定义使用链，表示当前指令定义的值的使用者。内存交叉引用显示当前指令读写的内存地址，
对于读内存会在其子树显示写入指令的编号，相反的，写内存地址则会显示它的使用者。在这例子中，"r 4 0000007ff3e99d98"表示当前指令会读取"0000007ff3e99d98"处四字节内容，"00010679 w 4 0000007ff3e99d98" 表示它是由编号为"00010679"的指令写入。

以上四个基本功能是不是已经可以极大提升逆向效率了？我们还有可以让生活更美好的功能。

杀手级功能！字符串引用作用无需多言。我会分析trace时内存出现过的所有字符串，直接秒杀所有字符串加密防护。

另外一个杀手锏！正向污点追踪(Forward Taint Analysis)能标记出受输入影响的相关指令，而逆向(Backward Taint Analysis)污点追踪可帮我们自动回溯变量来源和相关的计算过程。在逆向分析过程中，在对感觉兴趣的寄存器或者内存进行标记之后，使用正向污点追踪可以自动的帮我们找到他们的处理过程。

假设在调试中，发现了某条感兴趣的指令，比如说下图的，"03186869 str，x1, [x24, x0, LSL #0x3]"时，现在想知道"x1"后续如何被处理的，该如何入手？可以使用上面介绍的内存引用，找到他的使用者，然后继续分析它的使用。也可以对x1进行一次正向的污点追踪分析，污点引擎能自动筛选出受x1影响的指令。

可以看到，在污点分析结果中，x1会先在内存中来回倒了几次，最后会在free中使用，应该是释放malloc返回的一个指针。

如果想知道另外一个寄存器x0的来源呢？同样可以使用交叉引用和逆向污点追踪。逆向污点追踪分析结果如下：

很显然，x0依赖memcpy复制的一块内存，是02262601处ubfx执行结果。

有朋友能看出这是个VM吗？这个例子是我在阿里10101命令trace中随手取的。在分析x1的后续使用过程中，污点追踪引擎自动屏蔽了VM解释器取指，解码，执行等各种细节，直接分析出会处理x1相关指令。而x0(=8)则是VM解释器的寄存器参数，对VM实现感兴趣可以研究它的来源，解码等过程。

以为就是我的时间无关调试器的核心功能。仅依赖于trace指令，理论上对任意代码防护均适用。接下来介绍依赖函数分析相关的功能。

使用调用栈我们可以快速跳转到上层调用者，考察调用参数。

这是所有功能里面实现难点最多，同时也是最有趣的一部分。为什么要自己恢复和绘制CFG呢？自己恢复CFG的首要原因就是对抗间接跳转混淆。静态分析间接跳转的跳转目标需要很高的技巧，常见的方法有

而从trace中重建CFG则简单很多。另外一个原因是代码动态修改和映射。像代码加壳，不使用调试器，我们一般只能使用静态工具分析壳代码；一些防护会动态mmap代码，执行之后unmap，如果我们支持trace重建CFG的话就能免去调试，dump内存等步骤，支持对他们进行分析。事实上重建CFG也有些难点，有些情况甚至比静态更难处理。考虑如下两种情形：

在实现的时候我已经考虑这些情况，但还未找到好的处理办法。

最难的一部分来了，绘制CFG。我认为传统的层次布局（Sugiyama Layout）用于调试有以下缺陷：

为了更好的支持调试，我这里参考了Ghidra的实现，目标是为了实现一种“伪”源码调试效果。

Ghidra的CFG很有特色，他们称之为Decompiler Layout，即使用反编译器提供的代码块顺序和缩进信息对CFG布局，这种布局的结果自然而然的接近反编译后的源码，符合我们的需求。
通用的反编译器结构化算法目标一般是生成更结构化的代码，更少的goto语句。Ghidra的结构化算法就会选择一些不是强连通分量的块作为循环成员，将函数提前返回等手段减少goto数量。我目的是为了对CFG布局，我觉得应该：

因此，CFG布局使用的是我自己的结构化算法。该算法不关心块内指令的语义，而是会直接假定两路跳转都是if-else跳转，两路以上的跳转是switch-case跳转来进行结构化分析。

下面是我跟Ghidra绘制的简单对比：

ghidra布局：

我的布局：

阿里间接跳转混淆还原：

我还实现了一个与上面结构化布局配套的块导航图，应该算是一个小创新，独一无二的功能吧。它看起来是这样的：

它可以：

至此，调试器的功能已完全介绍完毕。

下面开始我们的实战。样本libnative-lib.so基址：0x750bd42000。

首先进行第一步，也是最困难的一步，记录算法的执行过程。KanxueSign函数的trace约42w条指令，记录文件大小6.42MB，在我的pixel 3上trace耗时小于500毫秒。我的时间无关调试器是按“亿”级别的规模设计的，42w对我而言个是非常微小的trace，当前我测试过最大的trace约9000w条（1.12GB），阿里10101命令的trace有1100w条（139MB）。

点击check按钮之后，logcat中会有如下打印，我们目标就是还原计算output的算法。

输入输出都是字符串，在字符串视图中先搜下输入，内存中出现过两次，经过简单分析之后，貌似都没有后续使用，所以我们这里选择输出作为切入点开始进行分析。

使用输出第一字节"9b"进行搜索，找到创建它的位置：

在执行“00180674 75f67c41b0 strb w8, [x0, x9, LSL ]”指令后，内存0x7fec60ebd9中将会首次完整出现"9b9da9c850fd456456"。

顺藤摸瓜，在内存视图中选中第一个字节进行逆向污点追踪，找到它的计算过程。

上方的“__vfprintf”函数表明输出可能是执行格式化打印后的结果。将代码执行到“00163000”，查看调用栈：

可以看到程序会使用sprintf格式化字符串。

将程序执行到此处，

此时x2的值正是"9b"。注意此时内存"000000750bd9eb04"仍显示为未知，原因是程序运行到该处时，我们还未曾记录到对它的访问，在sprintf调用返回之后，
重新查看就可以看到它的内容是“%02x”。

在指令流中追踪x2定义：

发现x2是“00162718”处的ldrb指令读取0000007ff3e99fe0的一个字节内容。

在CFG视图中使用“alt+单击”尝试选择“750bd55400”所在基本块所属循环，发现能成功，并且循环只有一个出口。

考察循环退出条件：

很明显x23是个计数器，循环会在执行32次后退出。

将程序执行到“00162718”：

不难得出，该循环把0000007fec60ecf0处，32字节内存内容输出为16进制，正好对上output的前32字节。

接下来继续研究“0000007fec60ecf0”内存数据来源，它必然是由保存在内存某处的输入经过计算而来。
为了找到这输入，我们只需要不断对依赖的ldr指令的目标寄存器进行逆向污点追踪即可。

发现以下路径能回溯到常量：

经过搜索，发现这是个用于计算sha256常量。此时发现x1指向一个字符串（"1810ab738de1810a9cf720"），难道是计算它的sha256？经过验证，发现并不是。

看来有必要研究下sha256的算法过程。为了找到sha256相关例程，对0000007fec60ed10中的sha256 ctx进行正向污点追踪，

发现首次使用sha256 ctx的函数是0001d1e8，运行到此处发现x0指向sha256 ctx，此时x1是个字符串（"mdml=>kod89mdml=e?:knl\\\\\\\\\\\\\\\\\\\\\"），难道最终的hash是它的？
经过验证，也不是。难道不是标准的sha256？为了研究sha256的运行细节，我在随便网上找了一份sha256代码https://github.com/System-Glitch/SHA256.git，在Main loop每轮迭代前后和transform函数返回前打印ctx。

发现使用相同参数运行标准sha256 transform之后的ctx与0001d1e8完全一致，所以0001d1e8是标准的sha256 transform。

使用指令执行历史功能，发现这个函数会执行5次。

其中第二次会使用新的ctx_b对如下数据进行转换：

第三次，四次使用ctx_b对apk路径进行转换

最后一次使用最初的ctx转换ctx_b hash进行转换。

最后一次执行后的ctx即是我们最终的hash，只是字节序有差异。

对第二次调用的输入首字节“07”进行逆向污点追踪：

分析后发现他是经过首次运行的参数（"mdml=>kod89mdml=e?:knl"）原地转换而来。
计算过程如下：

化简后就是

向上考察污点追踪结果即可得到"mdml=>kod89mdml=e?:knl"的来源，发现它依赖参数"1810ab738de1810a9cf720"，

逐字节通过：

也就是

运算得到。

最后我们只要弄清参数"1810ab738de1810a9cf720"的来源，output第一个部分的分析就大功告成了。

接下来的操作大家应该都知道，污点追踪，通过栈视图跳转到调用者：

"1810ab738de1810a9cf720" = sprintf("%08lx%08lx", 0x000001810ab738de, 0x000001810a9cf720)

继续分析x2来源，

考察调用者参数的操作可以得到:

0x000001810ab738de 是使用GetStaticLongField获取的startTime

0x000001810a9cf720 是使用GetStaticLongField获取的firstInstallTime

综上，output第一部分的计算如下：

同样的分析套路可以分析出第二，三部分的算法，这里略过冗长的具体分析过程，直接给出最终算法。

part 2:

使用randomLong查表转换packageCodePath而来

part 3:

上文展示了使用时间无关调试技术对算法进行一次完整逆向还原的过程。此样本最大的弱点就是使用了标准的sha256，在识别出它使用的是标准算法后，节省了我们大量分析混淆代码和实现等价算法的时间，这部分计算只需要使用相同的输入调用标准算法即可。在识别算法时，使用时间无关调试器可以方便在函数级，指令级与标准算法流程之间进行比较，使用正向污点追踪甚至可以直接比较处理输入的完整过程。污点追踪，这个听起来就很高级的技术，在自动化反混淆论文中经常可以看到它的身影，但是貌似很少看到过用它，特别是反向污点追踪进行辅助逆向分析文章，它自动化追踪和溯源能力能将我们从枯燥的单步调试，人肉回溯解脱出来。有了污点引擎的加持，逆向回溯指令操作参数来源，然后正向分析其使用的逆向策略实施起来将会更加简单，直接。未来会不会出现污点追踪的对抗，大家可以拭目以待。

对ollvm的算法进行逆向分析和还原

附件包含样本和完整源码。
游客朋友也可以从我的github下载：reverseme-ollvm11

[注意]看雪招聘，专注安全领域的专业人才平台！