Practical Reverse Engineering Exercise Solutions: Page 78 / Exercise 1

This is the first blog post to a series of ARM challenges from the book Practical Reverse Engineering. In addition to the official ARM manual, the following web page turned out to be very helpful when solving the exercises, as it describes the different ARM instructions in great detail.

https://www.heyrick.co.uk/armwiki/Main_Page

Without further ado, let us explore the first function. The extract below shows the ARM disassembly of a function named mystery1, which we are supposed to decompile into C code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

01:             mystery1
02: F0 01 2D E9   STMFD    SP!, {R4–R8}
03: 00 30 D0 E5   LDRB     R3, [R0] ; load one (unsigned) byte from memory location [R0] into R3, addressing mode: offset
04: 2D 00 53 E3   CMP      R3, #0x2D ; perform R3 - 0x2D 
05: 29 00 00 0A   BEQ      loc_B348
06: 2B 00 53 E3   CMP      R3, #0x2B ; perform R3 - 0x2B
07: 00 60 A0 E3   MOV      R6, #0 
08: 01 30 F0 05   LDREQB   R3, [R0,#1]! ; conditional load of one byte from memory at address R0+1 into R3, afterwards perform R0 = R0+1

09:      loc_B2AC
10: 30 00 53 E3   CMP      R3, #0x30 ; perform R3 - 0x30 and update conditional flags
11: 04 00 00 1A   BNE      loc B2C8 
12: 01 30 80 E2   ADD      R3, R0, #1 ; R3 = R0 + 1

13:      loc_B2B8
14: 03 00 A0 E1   MOV      R0, R3 
15: 01 20 D3 E4   LDRB     R2, [R3],#1 ; load with post-indexed mode, R2 = [R3]; R3 = R3+1;
16: 30 00 52 E3   CMP      R2, #0x30 ; 
17: FB FF FF 0A   BEQ      loc_B2B8

18:      loc_B2C8
19: 00 C0 A0 E3   MOV      R12, #0 ; R3!=  0x30
20: 00 40 A0 E3   MOV      R4, #0
21: 00 50 A0 E3   MOV      R5, #0
22: 0A 80 A0 E3   MOV      R8, #0xA
23: 01 00 00 EA   B        loc_B2E4

24:      loc_B2DC
25: 07 40 92 E0   ADDS     R4, R2, R7
26: C7 5F A3 E0   ADC      R5, R3, R7,ASR#31

27:      loc_B2E4
28: 0C 70 D0 E7   LDRB     R7, [R0,R12]
29: 01 c0 8C E2   ADD      R12, R12, #1
30: 94 28 83 E0   UMULL    R2, R3, R4, R8
31: 30 70 57 E2   SUBS     R7, R7, #0x30
32: 07 00 00 4A   BMI      loc_B318
33: 09 00 57 E3   CMP      R7, #9
34: 98 35 23 E0   MLA      R3, R8, R5, R3
35: 04 00 00 CA   BGT      loc_B318
36: 0B 00 5C E3   CMP      R12, #0xB
37: F3 FF FF 1A   BNE      loc_B2DC 

38:      loc_B30C
39: 00 00 A0 E3   MOV      R0, #0

40:      loc_B310
41: F0 01 BD E8   LDMFD    SP!, {R4–R8} ; restore the contents of R4-R8 by loading from the memory
42: 1E FF 2F E1   BX       LR ; return, switch to Thumb mode (Branch and exchange)

43:      loc_B318
44: 06 20 54 E0   SUBS     R2, R4, R6
45: C6 3F C5 E0   SBC      R3, R5, R6,ASR#31
46: 02 01 52 E3   CMP      R2, #0x80000000
47: 00 00 D3 E2   SBCS     R0, R3, #0
48: F7 FF FF AA   BGE      loc_B30c

49: 00 00 56 E3   CMP      R6, #0
50: 01 00 00 0A   BEQ      loc_B33C 
51: 00 40 74 E2   RSBS     R4, R4, #0
52: 00 50 E5 E2   RSC      R5, R5, #0

53:      loc_B33C
54: 00 40 81 E5   STR      R4, [R1]
55: 01 00 A0 E3   MOV      R0, #1
56: F1 FF FF EA   B        loc_B310

57:      loc_B348
58: 01 30 F0 E5   LDRB     R3, [R0,#1]!
59: 01 60 A0 E3   MOV      R6, #1
60: D5 FF FF EA   B        loc_B2Ac
61:             ; End of function mystery1 

Disassembly Analysis

First of all, we notice that each instruction of the disassembly has a width of 32 bits, which is a strong indicator for ARM state rather than Thumb state. Furthermore, the contents of the registers r4-r8 are stored on the stack with the STMFD command rather than with a PUSH, as in the case of Thumb state.

The very first instruction is STMFD SP!, {R4-R8}.

STMFD is a synonym for STMDB, meaning to store multiple register values in memory in DB mode (decrement before). That is, the last location of the data written to memory will be stored 4 bytes below the previous value of SP. Due to the exclamation mark after SP, writeback is enabled and SP will point to the first location of the data written to memory.

The instruction LDREQB  R3, [R0,#1]!  deserves to be mentioned as well. It performs a load operation of a single unsigned byte from memory into the R3 register. The addressing mode is pre-indexed, meaning R0 (i.e., the base register) will be modified. The value will be retrieved from the memory location [R0+1] and R0 will be afterwards updated to R0+1.

LDRB R2, [R3],#1 is a load operation with the post-index address mode. It loads the data at memory address R3 into R2 and afterwards sets R3 to R3+1.

UMULL R2, R3, R4, R8 multiplies two 32-bit unsigned values to produce a 64 bit result. In particular, it will multiply the values stored in registers R4 and R8 and store the lower and upper 32 bits of the result in R2 and R3 respectively.

SUBS R7, R7, #0x30 performs the substraction R7 = R7 - 0x30 and updates the arithmetic conditional flags depending on the result.

SBC R3, R5, R6,ASR#31 is another instruction worth of explaining. SBC stands for Substract with Carry and in the most basic scenario would perform the operation Rd = Rn - Op2 - !C, where C stands for the carry flag. In this case, however, we have an additional shift operation to perform, namely an arithmetic right shift operation of 31 bits with carry output. To summarize, the operation means the following: R3 = R5 - (R6 >> 31) - !C

BMI loc_B318 means that a branch to address loc_b318 is performed when the minus/negative flag is set, i.e., the N flag has the value 1.

MLA  R3, R8, R5, R3 has the following meaning: It multiplies the values in registers R8 and R5 and adds the value of R3. The lower 32 bits of the result are saved into register R3.

BGT loc_B318 performs a branch to loc_B318 when the Z flag has the value 0 and the N (negative) flag matches the V (overflow) flag.

RSBS R4, R4, #0 carries out a Reverse Substract. More precisely, the register value is substracted from an immediate and the result is written to the destination register. In particular, R4 is substracted from 0 and written back to R4. The conditional flags in CPSR will be updated due to the S suffix of the instruction.

RSC  R5, R5, #0 is actually very similar to RSB (reverse substract). The only difference is that RSC performs a reverse substract with carry. It substracts the R5 value and the value of NOT (Carry flag) from the immediate value #0. The result is written back to R5: R5 = 0 - R5 - !(Carry flag)

STR R4, [R1] is the basic Store Register operation to store a value from a register to memory. It takes the value from R4 and stores it in the memory area pointed to by the address in R1.

ADC R5, R3, R7,ASR#31 performs an addition with the Carry flag and stores the result in the destination register. Here, a arithmetic shift to the right (ASR) is contained as well. The equivalent of this instruction is as follows: R5 = R3 + (R7 >> 31) + Carry flag.

Function Analysis:

There are two possible values of R0 when the function mystery1() exits, namely 0 and 1. Thus, we deduce that the data type of the function’s return value is of type BOOL.

Current function prototype:

1

BOOL mystery1();

In the exercise description, we are already told mystery1() takes two arguments. The first argument is passed in R0 and accessed right at the start of the function in line 03. The second argument, however, is not accessed before line 54. Both of the arguments contain addresses, i.e., they are pointers to some kind of structs.

Current function prototype:

1

BOOL mystery1(int* arg1, int* arg2);

What is more, the return value of the function is 1 and data stored to the address at R1 (arg2) if and only if the block in line 53 is executed. Otherwise, the return value is 0 and R1 is not being accessed. This means that the return value should indicate to the caller whether a value was stored in the address contained in arg2. As a consequence, we modify the method name to reflect this behaviour:

Current function prototype:

1

BOOL storeValue_mystery1(int* arg1, int* arg2);

We notice that all load operations (LDR) of the function only load single byte values and the original load address is taken from the first argument. The loaded byte values are being compared to fixed values such as 0x2d, 0x2b, 0x30, whose ASCII character representation is -, + and 0 respectively.  Furthermore, the value of R0 is increased in multiple locations by 1 (e.g., lines 08, 58, 12, 15). This strongly suggests the data type of argument1 is in fact a string or an array of characters.

Current function prototype:

1

BOOL storeValue_mystery1(char* arg1, int* arg2);

The first blocks of the function check whether the first byte of arg1 matches the value 0x2d (-) or 0x2b (+). Depending on the outcome, the program sets the register r6 with a value of 1 in the case of a “-” and 0 otherwise. When looking at the other parts of the program, it turns out r6 can only assume the values 0 and 1, thus we deduce it is of type BOOL.

The program continues in line 9 to examine the second byte of arg1 for a value of 0x30 (0). The program continues to retrieve successive bytes from arg1 in a loop as long as the 0-character is read.

Up to line 18, we can make already a first attempt at the decompilation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

BOOL storeValue_mystery1(char* arg1, int* arg2) {
    int index = 0;
    BOOL minus;

    if (arg1[index] == '-') {
        minus = TRUE;
        index = index + 1;
    }
    else {
        minus = FALSE;
        if (arg1[index] == '+') {
            index = index + 1;
        }
    }

    while (arg1[index] == '0') {
        index = index + 1;
    }
    // STOP - Line 18
    /* TODO * /
       }

Up to now, we know that the input string matches the following regular expression:

"(+|-)0*"

Beginning with line 18, the disassembly becomes more involved. It seems the function checks whether the subsequent bytes are in the range [0x30-0x39]. The plot thickens: Their ASCII representation are the numbers 0 to 9. Line 36 ensures that at most 10 of these characters are read from arg1.

In register R8, there is a constant value 0xA, whose decimal value is 10. This value is used in the multiplication operation in line 30.

We can add these new insights to our decompiled function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

BOOL storeValue_mystery1(char* arg1, int* arg2) {
    int index = 0;
    char minus;

    if (arg1[index] == '-') {
        minus = 1;
        index = index + 1;
    }
    else {
        minus = 0;
        if (arg1[index] == '+') {
            index = index + 1;
        }
    }

    while (arg1[index] == '0') {
        index = index + 1;
    }

    int indexNumbers = 0;
    long long result = 0;


    while ((arg1[index+indexNumbers]) <= '9') AND (arg1[index+indexNumbers] >= '0')) {
        char currentNumber = arg1[index+indexNumbers] - 0x30;
        result = result * 10;
        indexNumbers = indexNumbers + 1;
        result = result + currentNumber;
        if (indexNumbers == 11) {
            return 0; // reached maximum number of characters
        }
    }

    /* TODO */

}

As soon as the input string contains no further valid numeric characters, we arrive in the block of line 43. The result in r4 is decremented by the minus character value and written to a different register. Afterwards, the modified result is compared to the hexadecimal value 0x8000000, which is the hexadecimal representation of 2^31. When the modified result is greater or equal than this value, the function aborts and returns 0.  Notice that the range of signed 32 bit integers is [-2^31; 2^31 - 1].

When the minus character is set, the result value is negated (line 51: R4 = 0 - R4). Finally, the result value is written to the memory address contained in R1 (line 54) and 1 is returned (line 55). We can now complete the function decompilation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

BOOL convertStringToInteger(char* source, int* destination) {
    int index = 0;
    char minus;

    if (source[index] == '-') {
        minus = 1;
        index = index + 1;
    }
    else {
        minus = 0;
        if (source[index] == '+') {
            index = index + 1;
        }
    }

    while (source[index] == '0') {
        index = index + 1;
    }

    int indexNumbers = 0;
    long long result = 0;


    while ((source[index+indexNumbers]) <= '9') AND (source[index+indexNumbers] >= '0')) {
        char currentNumber = source[index+indexNumbers] - 0x30;
        result = result * 10;
        indexNumbers = indexNumbers + 1;
        result = result + currentNumber;
        if (indexNumbers == 11) {
            return 0; // reached maximum number of characters
        }
    }

    long long modifiedResult = result - minus;
    if (abs(modifiedResult) >= 2^31) {
        return 0;
    }

    if (minus == 1) {
        modifiedResult = - modifiedResult;
    }

    *destination = modifiedResult;
    return 1;
}