Thursday, 7 December 2017

Practical Reverse Engineering Exercise Solutions: Page 79 / Exercise 11

Exercise 11 on page 79 of the book Practical Reverse Engineering specifies the following ARM disassembly of a function called mystery11 - the last exercise of the ARM chapter:

01: 010185B0             mystery11
02: 010185B0 2D E9 F8 4F   PUSH.W   {R3–R11,LR}
03: 010185B4 0D F2 20 0B   ADDW     R11, SP, #0x20
04: 010185B8 B0 F9 5A 30   LDRSH.W  R3, [R0,#0x5A]
05: 010185BC 07 46         MOV      R7, R0
06: 010185BE 90 46         MOV      R8, R2
07: 010185C0 00 EB 83 03   ADD.W    R3, R0, R3,LSL#2
08: 010185C4 D3 F8 84 A0   LDR.W    R10, [R3,#0x84]
09: 010185C8 7B 8F         LDRH     R3, [R7,#0x3A]
10: 010185CA 89 46         MOV      R9, R1
11: 010185CC CB B9         CBNZ     R3, loc_1018602
12: 010185CE B0 F9 5A 40   LDRSH.W  R4, [R0,#0x5A]
13: 010185D2 17 F1 20 02   ADDS.W   R2, R7, #0x20
14: 010185D6 00 EB 44 03   ADD.W    R3, R0, R4,LSL#1
15: 010185DA B3 F8 5C 50   LDRH.W   R5, [R3,#0x5C]
16: 010185DE 00 EB 84 03   ADD.W    R3, R0, R4,LSL#2
17: 010185E2 D3 F8 84 00   LDR.W    R0, [R3,#0x84]
18: 010185E6 83 89         LDRH     R3, [R0,#0xC]
19: 010185E8 06 6C         LDR      R6, [R0,#0x40]
20: 010185EA 03 EB 45 03   ADD.W    R3, R3, R5,LSL#1
21: 010185EE 9B 19         ADDS     R3, R3, R6
22: 010185F0 1C 78         LDRB     R4, [R3]
23: 010185F2 5B 78         LDRB     R3, [R3,#1]
24: 010185F4 43 EA 04 24   ORR.W    R4, R3, R4,LSL#8
25: 010185F8 43 8A         LDRH     R3, [R0,#0x12]
26: 010185FA 23 40         ANDS     R3, R4
27: 010185FC 99 19         ADDS     R1, R3, R6
28: 010185FE FD F7 8D FF   BL       sub_101651C

29: 01018602      loc_1018602
30: 01018602 BA 8E         LDRH     R2, [R7,#0x34]
31: 01018604 BB 6A         LDR      R3, [R7,#0x28]
32: 01018606 D0 18         ADDS     R0, R2, R3
33: 01018608 9A F8 02 30   LDRB.W   R3, [R10,#2]
34: 0101860C 0B B1         CBZ      R3, loc_1018612
35: 0101860E 00 22         MOVS     R2, #0
36: 01018610 00 E0         B        loc_1018614

37: 01018612      loc_1018612
38: 01018612 3A 6A         LDR      R2, [R7,#0x20]

39: 01018614      loc_1018614
40: 01018614 FB 8E         LDRH     R3, [R7,#0x36]
41: 01018616 B8 F1 00 0F   CMP.W    R8, #0
42: 0101861A 01 D0         BEQ      loc_1018620
43: 0101861C 80 18         ADDS     R0, R0, R2
44: 0101861E 9B 1A         SUBS     R3, R3, R2

45: 01018620      loc_1018620
46: 01018620 C9 F8 00 30   STR.W    R3, [R9]
47: 01018624 BD E8 F8 8F   POP.W    {R3–R11,PC}
48: 01018624             ; End of function mystery11

According to the exercise description, the called subroutine sub_101651C in line 28 takes three arguments and does not return anything. Thus, we know the registers R0, R1 and R2 are prepared and passed to the function.

The function is executed in Thumb mode, as we can see from the different instructions having both a width of 16 and 32 bits. Furthermore, Thumb specific instructions such as PUSH.W, POP.W and STR.W are contained in the disassembly.

With regard to the instruction semantics, we shed light on the following examples:

LDRSH.W  R3, [R0,#0x5A]: Load Signed Halfword Into Register. For the ARM architcture, a word is a 32-bit value and a half-word a 16-bit value. Thus, a signed 16-bit integer value (2 bytes) is loaded from the memory location [R0 + 0x5A] into R3.

LDRH     R3, [R0,#0xC]: Load Half Word Into Register. Slightly different than LDRSH, this instruction loads an unsigned 16-bit integer value into the destination register. In particular, it loads from memory at [R0 + 0xC] into register R3.

ADD.W    R3, R0, R3,LSL#2: This composition of arithmetic operations is equal to the following expression: R3 = R0 + (R3 << 2)

ORR.W    R4, R3, R4,LSL#8: This composition of logical operations is equal to the following expression: R4 = R3 |  (R4 << 8)

Let us know examine the data types of mystery11's arguments. R0 seems to be a pointer to a data structure, as we are accessing its field member at offset 0x5A. We create a provisional unknownStruct1:

unknownStruct1:
field5a_sint16; // 2 byte signed integer value (i.e. sint16) - line 4

R1 is first accessed in line 10 and its value is copied into R9, which is  used in line 46 as a destination address for storing a 32 bit value. Thus, we assume it is a pointer as well to an unknown memory structure.

The third argument in R2 is preserved in R8 (line 6) and used for a check against zero (line 41). Hence, we assume it is a 32-bit unsigned integer.

As far as the return value is concerned, we notice the return register R0 is set either in line 32 or 43 before the function exits. In both cases, an addition is performed so we assume it is of type uint32.

Our first function prototype proposal:

uint32 mystery11 (unknownStruct1* arg1, int* arg2, uint32 arg3);

Although the function contains no loops, the plethora of memory accesses does not permit us to reason about its functionality at a high level. Thus, we provide the first attempt to generate C code from the disassembly step-by-step along with the data structures:

unknownStruct1:
field20_uint32; // unknown 4 byte value - line 38
field28_uint32; // unknown 4 byte value - line 31
field34_uint16; // unknown 2 byte value - line 30
field36_uint16; // unknown 2 byte value - line 40
field3a_uint16; // 2 byte unsigned integer - line 9
field5a_sint16; // 2 byte signed integer value (i.e. sint16) - line 4


unknownStruct2:
field84_unknownstruct3_p; // pointer to an instance of unknownStruct3


unknownStruct3:
field02_c; // line 33
field12_uint16; // line 25
field0C_uint16; // line 18
field40_p; // line 19 


unknownStruct4:
field5c_uint16; // line 15


uint32 mystery11 (unknownStruct1* arg1, int* arg2, uint32 arg3) {

sint16 r3 = arg1->field5a_sint16; // line 4
unknownStruct1* r7 = arg1; // line 5
uint32 r8 = arg3; // line 6

unknownStruct2* r3 = arg1 + (arg1->field5a_sint16 * 4); // lines 4, 7

unknownStruct3* r10 = r3->field84_p; // line 8
uint16 r3 = arg1->field3a_uint16; // line 9
int* r9 = arg2; // line 10

if (r3 == 0) { // line 11

uint32 r2 = arg1 + 0x20; // line 13

sint16 r4 = arg1->field5a_sint16; // line 12

unknownStruct4* r3 = arg1 + (r4 * 2); // line 14

uint16 r5 = r3->field5c_uint16; // line 15

unknownStruct2* r3 = arg1 + (r4 * 4);  // line 16 - Probably unknownStruct5 == unknownStruct2, since we access the same memory location as in line 7

unknownStruct3* r0 = r3->field84_p; // line 17 - strong similarity to line 8

uint16 r3 = r0->field0C_uint16; // line 18
int* r6 = r0->field40_p; // line 19  - this is most likely a pointer due to the subsequent address calculations

uint32 r3 = r3 + (r5 * 2); // line 20
r3 = r6 + r3; // line 21

char r4 = r3[0]; // line 22
char r3 = r3[1]; // line 23 

r4 = r3 | (r4 << 8); // line 24 - we effectively obtain a 16-bit value by ORing two 8-bit values, where one was shifted 8 positions to the left

uint16 r3 = r0->field12_uint16; // line 25

r3 = r3 & r4; // line 26

r1 = r6 + r3; // line 27

sub_101651C(r0, r1, r2); 
}

uint16 r2 = arg1->field34_uint16; // line 30
uint32 r3 = arg1->field28_uint32; // line 31

uint32 r0 = r2 + r3; // line 32

char r3 = r10->field02_c; // line 33

if (r3 == 0) { // line 34
uint32 r2 = arg1->field20_uint32; // line 38
}
else {
uint32 r2 = 0; // line 35
}

uint16 r3 = arg1->field36_uint16; // line 40

if (arg3 != 0) { // lines 41,42
r0 = r0 + r2; // line 43
r3 = r3 + r2; // line 44
}

*arg2 = r3; // line 46
}


To be honest, this looks like a huge mess, but it is just our first attempt and we will try to refine the code and make it more readable.

Firstly, we follow the data flow from the end of the program to see what kind of value will be stored in the pointer arg2. We notice there can be at most a 32-bit value, so we change the data type of arg2 from int* to uint32*.
Secondly, we eliminate instructions that are either unnecessary or duplicated.
Thirdly, we try to minimize the number of C code by combining the load with the different arithmetic or comparison operations.
Fourthly, we try to give the variables more descriptive names. For instance, the third argument arg3 is only used to indicate or whether or not the addition in the last conditional block should be executed. Therefore, we choose its name to be "performAddition". The subroutine sub_101651C was named perform_magic.

unknownStruct1:
field20_uint32; // unknown 4 byte value - line 38
field28_uint32; // unknown 4 byte value - line 31
field34_uint16; // unknown 2 byte value - line 30
field36_uint16; // unknown 2 byte value - line 40
field3a_uint16; // 2 byte unsigned integer - line 9
field5a_sint16; // 2 byte signed integer value (i.e. sint16) - line 4


unknownStruct2:
field84_unknownstruct3_p; // pointer to an instance of unknownStruct3


unknownStruct3:
field02_c; // line 33
field12_uint16; // line 25
field0C_uint16; // line 18
field40_p; // line 19 


unknownStruct4:
field5c_uint16; // line 15


uint32 mystery11 (unknownStruct1* unknownStruct1Ptr, int* dest, uint32 indicator) {


unknownStruct2* r3 = unknownStruct1Ptr + (unknownStruct1Ptr->field5a_sint16 * 4); // lines 4, 7
unknownStruct3* r10 = r3->field84_unknownstruct3_p; // line 8

if (unknownStruct1Ptr->field3a_uint16 == 0) { // lines 9,11

sint16 r4 = unknownStruct1Ptr->field5a_sint16; // line 12

unknownStruct4* r3 = unknownStruct1Ptr + (r4 * 2); // line 14

uint16 r5 = r3->field5c_uint16; // line 15

unknownStruct2* r3 = unknownStruct1Ptr + (r4 * 4);  // line 16 - Probably unknownStruct5 == unknownStruct2, since we access the same memory location as in line 7

unknownStruct3* r0 = r3->field84_unknownstruct3_p; // line 17 - strong similarity to line 8

uint16 r3 = r0->field0C_uint16; // line 18
int* r6 = r0->field40_p; // line 19  - this is most likely a pointer due to the subsequent address calculations

uint32 r3 = r6 + r3 + (r5 * 2); // lines 20, 21


uint32 r4 = r3[1] | (r3[0] << 8); // lines 22, 23, 24 - we effectively obtain a 16-bit value by ORing two 8-bit values, where one was shifted 8 positions to the left

uint32 r3 = r0->field12_uint16 & r4; // lines 25, 26

r1 = r6 + r3; // line 27

perform_magic(r0, r1, &(unknownStruct1Ptr->field20_uint32)); // lines 13, 28
}

uint32 r0 = arg1->field34_uint16 + arg1->field28_uint32; // lines 30,31, 32
uint32 r2 = 0; // line 35

if (r10->field02_c == 0) { // line 34
r2 = arg1->field20_uint32; // line 38
}

uint16 r3 = unknownStruct1Ptr->field36_uint16; // line 40

if (indicator != 0) { // lines 41,42
r0 = r0 + r2; // line 43
r3 = r3 + r2; // line 44
}

*dest = r3; // line 46
return r0;
}

No comments:

Post a Comment