汇编冒泡排序逆向还原

vlambda
2022-02-22

汇编冒泡排序逆向还原

冒泡排序大家都很熟悉,本篇文章分析一个arm汇编语言实现的冒泡排序,逆推出编译前的c语言代码,所需工具：IDA,Pixel手机。

⊙一.代码分析的篇幅

⊙二.分析

⊙三.代码还原

⊙四.思路总结

一.代码分析的篇幅

汇编冒泡排序逆向还原

二.分析

2.1 main

下面是arm代码的实现(逐行代码分析):

.text:AEF0F404 ; int __cdecl main(int argc, const char **argv, const char **envp).text:AEF0F404 EXPORT main.text:AEF0F404 main ; DATA XREF: .text:AEF0F3C0↑o.text:AEF0F404 ; .got:main_ptr↓o.text:AEF0F404.text:AEF0F404 var_4F866BD0= -0x4F866BD0.text:AEF0F404 var_44= -0x44.text:AEF0F404 var_40= -0x40.text:AEF0F404 var_3C= -0x3C.text:AEF0F404 var_14= -0x14.text:AEF0F404 var_10= -0x10.text:AEF0F404 var_C= -0xC.text:AEF0F404 var_8= -8.text:AEF0F404 var_4= -4.text:AEF0F404.text:AEF0F404 STMFD SP!, {R11,LR}.text:AEF0F408 MOV R11, SP.text:AEF0F40C SUB SP, SP, #0x48.text:AEF0F410 MOV R0, #0.text:AEF0F414 STR R0, [R11,#var_4].text:AEF0F418 STR R0, [R11,#var_8].text:AEF0F41C B loc_AEF0F420.text:AEF0F420 ; ---------------------------------------------------------------------------

上面的代码是main函数的入口,首先

MOV R11, SP:把栈顶指针赋值给R11(这行代码的执行会把main函数之前的栈顶当作栈低,R11寄存器指向栈底)当main函数执行结束时,会把R11赋值给SP恢复函数调用前的堆栈；

MOV R0,#0;

STR R0, [R11,#var_4];

STR R0, [R11,#var_8]:给R0赋值，同时给以R11为底的栈以4字节大小的情况下分别赋值0(执行这三行代码为了给局部变量初始化)；

B loc_AEF0F420：同时无条件跳转到标号AEF0F420执行继续执行程序；

汇编冒泡排序逆向还原

2.2 loc_AEF0F420

.text:AEF0F420 ; ---------------------------------------------------------------------------.text:AEF0F420.text:AEF0F420 loc_AEF0F420 ; CODE XREF: main+18↑j.text:AEF0F420 ; main+88↓j.text:AEF0F420 LDR R0, [R11,#var_8].text:AEF0F424 CMP R0, #9.text:AEF0F428 BGT loc_AEF0F490.text:AEF0F42C B loc_AEF0F430.text:AEF0F430 ; ---------------------------------------------------------------------------.text:AEF0F430

LDR R0, [R11,#var_8]从堆栈【R11，#var_8】的位置取出0赋值给R0;

CMP R0,#9;

BGT loc_AEF0F490;

B loc_AEF0F430;:比较R0和十进制数值9的大小,当R0>9的时候才会跳转到标号loc_AEFOF490,否则将跳转到标号loc_AEFOF430(在此猜测这里有个while 或者 for循环的c语言语法),在当前的位置因为R0为0,所以无条件跳转到loc_AEFOF430进行执行。

汇编冒泡排序逆向还原

2.3 loc_AEF0F430

.text:AEF0F430 ; ---------------------------------------------------------------------------.text:AEF0F430.text:AEF0F430 loc_AEF0F430 ; CODE XREF: main+28↑j.text:AEF0F430 BL rand.text:AEF0F434 LDR R1, =0xA57EB503.text:AEF0F438 SMULL R2, R3, R0, R1.text:AEF0F43C ADD R1, R3, R0.text:AEF0F440 MOV R3, R1,ASR#6.text:AEF0F444 ADD R1, R3, R1,LSR#31.text:AEF0F448 MOV R3, #0x63 ; 'c'.text:AEF0F44C MUL R12, R1, R3.text:AEF0F450 SUB R0, R0, R12.text:AEF0F454 ADD R0, R0, #1.text:AEF0F458 LDR R1, [R11,#var_8].text:AEF0F45C ADD R3, SP, #0x48+var_3C.text:AEF0F460 STR R0, [R3,R1,LSL#2].text:AEF0F464 LDR R0, [R11,#var_8].text:AEF0F468 LDR R1, [R3,R0,LSL#2].text:AEF0F46C LDR R0, =(unk_AEF0F5C8 - 0xAEF0F478).text:AEF0F470 ADD R0, PC, R0 ; unk_AEF0F5C8 ; format.text:AEF0F474 STR R2, [SP,#0x48+var_40].text:AEF0F478 BL printf.text:AEF0F47C B loc_AEF0F480.text:AEF0F480 ; ---------------------------------------------------------------------------

LDR R1, =0xA57EB503

SMULL R2, R3, R0, R1

ADD R1, R3, R0

MOV R3, R1,ASR#6

ADD R1, R3, R1,LSR#31：看到这里这个常量比较有意思,在arm出现了Magic(首先猜测是这个),然后往下调试的发现 SMULL , 我在想为什么要使用这个指令,因为在arm32位中如果这个Magic常量与rand的返回值的常量相乘的情况下,有可能会结果出现超过32,所以R2寄存器存储低32位,R3寄存器存储高32位,随后这些操作不知道为了做什么运算,但是当我看到ADD R1, R3, R1,LSR#31,原来是上面算除法呀(arm默认没有除法指令,一般情况可以把除法转化为其他指令)，上面的代码明显是被优化后的所以,还不知道除数是多少

MOV R3, #0x63 ; 'c'

MUL R12, R1, R3

SUB R0, R0, R12:首先赋值99(0x63)给R3，随后 R12 = R1*R3，R0=R0-R12,当进行到这个地方的时候,上面的代码和上上面的代码加起来的逻辑不就是求余运算吗，求出来商然后用总数-商*9,(这样就知道上方的代码的逻辑是随机产生一个数然后得到其余数)；

ADD R0, R0, #1：将上面算出来的余数再加1之后存放到R0之中。

LDR R1, [R11,#var_8]：把堆栈存储的局部变量的值拿出来,赋值给R1,赋值结束后R1的值为0

ADD R3, SP, #0x48+var_3C：实际上我们前面开辟的堆栈为0x48,var_3C为-0x3C,实际上R3 = R11+var_3C=SP+#0x48+var_；

LDR R0, [R11,#var_8]

LDR R1, [R3,R0,LSL#2]

LDR R0, =0x150

ADD R0, PC, R0 ; unk_B1BA55C8 ; format

STR R2, [SP,#0x48+var_40]

BL printf

B loc_B1BA5480：LDR R0，[R11, #var_8]从堆栈中的局部变量中取出,R0 在当前赋值为0,然后R1=[R3+R0<<2]相当于从数组中取得offset为0的值,同时R0=0x150,R0=PC+R0(已知arm传参的方式为R0-R3,如果有多余四个的参数,将会压入栈中进行传递参数),R1的值我们根据上上面的代码知道是求余+1的值,R0是format也就是printf格式化的参数，是printf的第一个参数，第二个参数是R1，那么上面的代码就是打印求余的值

loc_AEF0F430:这个标号实现的功能就是随机生成一个数，然后对99取余数求完余数之后再自增1,然后存储到一个数组中,然后从这个数组中再拿出来打印一下观察后续的代码,再看下面的标号loc_B1BA5480发现R0在执行完后又拿出来自增1,然后存放到栈中的局部变量中。

2.4 loc_B1BA5480

loc_B1BA5480LDR R0, [R11,#var_8]ADD R0, R0, #1STR R0, [R11,#var_8]B loc_B1BA5420

发现最后又跳转到了loc_B1BA5420,这不就形成了一个循环

2.4 对2.2 2.3 2.4的总结：他们构成了一个循环就是往数组随机十个值,其中在每个值生成完处理后进行打印,之后进入流程2.2中的 BGT loc_AEF0F490,语句。

目前可以还原的代码为

 int nums[10];    for(int i=0;i<10;i++)                            { nums[i]=1+rand()%99; printf("%d ",nums[i]); }

2.5 loc_B1BA5490 和loc_B1BA549C

loc_B1BA5490MOV R0, #0STR R0, [R11,#var_10]B               loc_B1BA549C
loc_B1BA549CLDR R0, [R11,#var_10]CMP R0, #8BGT loc_B1BA5544B loc_B1BA54AC

上面代码中先来解释标号loc_B1BA5490,他是赋值给局部栈一个0值,然后跳转到loc_B1BA549C，再从局部栈中取出值然后和立即数#8相对比,根据数值的大小跳转到不同的标号,从以前的代码看到这个结构,能够想到什么！没错这个又是个循环从0到8结束,因为初始值为0不大于立即数8所以跳转到标号loc_B1BA54AC的位置；

2.6 loc_B1BA54AC和loc_B1BA54BC

loc_B1BA54ACLDR R0, [R11,#var_10]ADD R0, R0, #1STR R0, [R11,#var_C]B loc_B1BA54BC
loc_B1BA54BCLDR R0, [R11,#var_C]CMP R0, #9BGT loc_B1BA5530B loc_B1BA54CC

和2.5的结构很相似对不对,唯二不同的是这个循环的初始化的值不是0而是1,并且循环的终止值为9,结合2.5来看就是两个嵌套的循环了,写一个循环必须知道三个条件,初始值,步长,终止值！现在已经知道两个可以在后续的部分找到这两个循环的步长，由于现在R0的值不大于9,则要跳转到标号loc_B1BA54CC；

2.7 loc_B1BA54CC

loc_B1BA54CCLDR R0, [R11,#var_C]ADD R1, SP, #0x48+var_3CLDR R0, [R1,R0,LSL#2]LDR R2, [R11,#var_10]LDR R1, [R1,R2,LSL#2]CMP R0, R1BLE loc_B1BA551CB loc_B1BA54EC

外层循环的值由#var_10这块内存的来控制,内层循环的值由#var_C这块栈内存来控制,然后我们根据以前上方的代码可以得知R0为数组在内层循环offset的值,R1位数组在外层循环offset的值，那么以下有两中取值结果如果是R0>R1，即内部循环偏移的数组值大于外部的情况下,就是跳转到标号loc_B1BA54EC，其他情况就跳转到标号loc_B1BA551C!

2.7.1 loc_B1BA54EC

loc_B1BA54ECLDR R0, [R11,#var_10]ADD R1, SP, #0x48+var_3CLDR R0, [R1,R0,LSL#2]STR R0, [R11,#var_14]LDR R0, [R11,#var_C]LDR R0, [R1,R0,LSL#2]LDR R2, [R11,#var_10]STR R0, [R1,R2,LSL#2]LDR R0, [R11,#var_14]LDR R2, [R11,#var_C]STR R0, [R1,R2,LSL#2]B loc_B1BA551C

LDR R0, [R11,#var_10]

ADD R1, SP, #0x48+var_3C

LDR R0, [R1,R0,LSL#2]：这三行代码是把以外部循环offset的数组值取出存放到R0寄存器中；

STR R0, [R11,#var_14]:然后存放到堆栈的局部偏移空间中。

LDR R0, [R11,#var_C]

LDR R0, [R1,R0,LSL#2]

LDR R2, [R11,#var_10]

STR R0, [R1,R2,LSL#2]

LDR R2, [R11,#var_C]

STR R0, [R1,R2,LSL#2]：然后获得内部循环数组偏移的偏移量,将其R0存放在以内部循环偏移的数组中,其实上方的代码做的内容就是交换了值而已

2.7.1.1 loc_B1BA5520

loc_B1BA5520LDR R0, [R11,#var_C]ADD R0, R0, #1STR R0, [R11,#var_C]B loc_B1BA54BC

从这里可以看出内部循环的步长为1，执行完了再跳转到2.6,实际上内部循环做的就是如果以外部循环的为偏移量的数组,小于或者等于以内部循环为偏移量的数组,他们就会互换位置！

2.7.2.1 loc_B1BA5530

loc_B1BA5530B loc_B1BA5534loc_B1BA5534LDR R0, [R11,#var_10]ADD R0, R0, #1STR R0, [R11,#var_10]B loc_B1BA549C

从这可以看出外部循环的步长为1

2.8 loc_B1BA551C

loc_B1BA551CB loc_B1BA5520loc_B1BA5520LDR R0, [R11,#var_C]ADD R0, R0, #1STR R0, [R11,#var_C]B loc_B1BA54BC

从这个地方看出内部循环的步长也为1

2.9 经过对2.5 2.6 2.7 2.8的总结：

代码为冒泡排序有内外两个循环，内循环从1开始到9,包括9

 for(outer=0;outer<9;outer++) //外层循环 for(inner=outer+1;inner<10;inner++) //内层循环 { if(nums[inner]>nums[outer]) //比较大小 { temp=nums[outer]; nums[outer]=nums[inner]; nums[inner]=temp; } //互换 }

2.10 调试输出数组的10个值，然后在最后打印一个换行符,分析流程和上述相同

三.代码还原

#include <stdio.h>#include <stdlib.h>int main( ){
 int i,inner,outer,temp; int nums[10]; for(i=0;i<10;i++) //随机生成10个数并输出 { nums[i]=1+rand()%99; printf("%d ",nums[i]); } for(outer=0;outer<9;outer++) //外层循环 for(inner=outer+1;inner<10;inner++) //内层循环 { if(nums[inner]>nums[outer]) //比较大小 { temp=nums[outer]; nums[outer]=nums[inner]; nums[inner]=temp; } //互换 } for(i=0;i<10;i++) //输出排序后的数列 printf("%d ",nums[i]); printf("\n");
 return 0;}

四.思路总结

耐心+时间+练的多 +c语言掌握+arm汇编熟练度 =还原结果

我是BestToYou,分享工作或日常学习中关于二进制逆向和分析的一些思路和一些自己闲暇时刻调试的一些程序,文中若有错误的地方,恳请大家联系我进行批评指正。

vlambda博客
学习文章列表