Big-O Complexity != Actual Performance

Any easy mistake to make is to assume that because one algorithm has a better Big-O complexity, it must be faster to execute. Similarly, two algorithms with the same Big-O, tackling the same problem, and all things similar may have vastly different performance.

Consider for example a "unique string" algorithm, where you want to check if a string contains all unique characters. A naive approach to the problem, which does not use extra data structures, is to go through the string, iterating each letter against the entire string searching for a match. This approach is O(n^2).

int strunique_naive(const char *str)
{
    char *iter, *tmp;

    for (iter = (char *)str; *iter != '\0'; ++iter)
        for (tmp = (char *)str; *tmp != '\0'; ++tmp)
            if (*tmp == *iter)
                return 0;

    return 1;
}

Now consider a better approach to the problem. We can optimize the algorithm by adding an offset for the iterating over the string part, since for example in a short string there is no reason to test the last character with the first character as the first character already performed that test during its loop-through.

int strunique_better(const char *str)
{
    size_t offset = 0;    /* offset at 0 */
    char *iter, *tmp;

    for (iter = (char *)str; *iter != '\0'; ++iter, ++offset)
        for (tmp = (char *)str + offset; *tmp != '\0'; ++tmp)
            if (*tmp == *iter)
                return 0;

    return 1;
}

int strunique_best(const char *str)
{
    size_t offset = 1;   /* pre-emptively shift offset up */

    /* repeat code above */
}

When we calculate the number of loops for the worst-case scenario (i.e. a string that is unique) for the naive algorithm, we get n^2 loops. The better algorithm is done in (n^2 + n) / 2, and the best is n * (n - 1) / 2 loops. The following table shows the differences:

# of Loops on Worst Case

	strunique_naive	strunique_better	strunique_best
1 character	1	1	0
2 characters	4	3	1
3 characters	9	6	3
5 characters	25	15	10
10 characters	100	55	45
100 characters	10,000	5,050	4,950

So why can you not trust Big-O complexity for actual performance? All 3 algorithms are actually O(n^2)! The better and best algorithms just have an improved actual performance equation.

Algorithm Benchmarks

	strunique_naive	strunique_better	strunique_best
Big-O Complexity	O(n^2)	O(n^2)	O(n^2)
Actual Performance	n^2	(n^2 + n) / 2	n * (n - 1) / 2

Pwn Adventure 3 Speed Hack

The Ghost in the Shellcode CTF has a number of challenges within an Unreal engine MMO. The game, Choose Your Pwn Adventure 3, is designed to be hacked. The hackable game code is mostly in a DLL called GameLogic.dll, which is a C++ binary with a provided debug .pdb file.

You start out running pretty slowly, so getting around the huge island is a pain. It's simple to get some basic speed hacking going though.

After going through the DLL and looking at function names that seemed interesting, I ran across the following:

I followed the offset and found the following there:

.rdata:10078B14 __real@40400000 dd 3.0

The hex for the float value was 0x4040. I changed this modifier to be a little bit higher by patching the DLL with a hex editor.

And that's it.

Practical Reverse Engineering p. 79 #10

Question number 10 on page 79 of Practical Reverse Engineering is as follows:

Figure 2-16 is a function from Windows RT. Read MSDN if needed. Ignore the security PUSH/POP cookie routines.

Here is the disassembly of the function:

Figure 2-16. Practical Reverse Engineering. © 2014 by Bruce Dang

 The ARM processor is in Thumb state, but transfers out during some of the syscalls. The function queries different clock APIs depending on the size of the supplied struct.

size_t QueryChrono(size_t *bytes_copied, 
                   size_t max_size, 
                   struct *clock_info)
{
    /* MOVS R4, #0 */
    bytes_copied = 0;

    /* CMP R5, #0x10 */
    if (max_size >= 16)
    {
        SYSTEMTIME sysTime;           /* SUB SP, SP, #0x10 */
        GetSystemTime(&sysTime);      /* LDR R3, =__imp_GetSystemTime */

        /* LDR R3, [SP,#0x1C+var_1C] */
        /* LDR R3, [SP,#0x1C+var_18] */
        /* LDR R3, [SP,#0x1C+var_14] */
        /* LDR R3, [SP,#0x1C+var_10] */
        /* STR R3, [R6,#0xC] */
        memcpy(clock_info->sysTime0x0, &sysTime, sizeof(SYSTEMTIME));

        bytes_copied = 16;              /* MOVS R4, #0x10 */
    }

    /* SUBS R3, R5, R4 */
    /* CMP R3, #4 */
    if ((max_size - bytes_copied) >= 4)
    {
        /* LDR R3, =__imp_GetCurrentProcessId */
        /* STR R0, [R6,R4] */
        *(clock_info + bytes_copied) = GetCurrentProcessId();

        bytes_copied += 4;              /* ADDS R4, #4 */
    }


    /* SUBS R3, R5, R4 */
    /* CMP R3, #4 */
    if ((max_size - bytes_copied) >= 4)
    {
        /* LDR R3, =__imp_GetTickCount */
        /* STR R0, [R6,R4] */
        *(clock_info + bytes_copied) = GetTickCount();

        bytes_copied += 4;              /* ADDS R4, #4 */
    }


    /* SUBS R3, R5, R4 */
    /* CMP R3, #9 */
    if ((max_size - bytes_copied) >= 8)
    {
        /* MOV R0, SP */
        LARGE_INTEGER perfCount;

        /* LDR R3, =__imp_QueryPerformanceCounter */
        QueryPerformanceCounter(&perfCount);

        /* STR R3, [R6,R4] */
        /* STR R3, [R2,#4] */
        memcpy((clock_info + bytes_copied), &perfCount,
                sizeof(LARGE_INTEGER));

        bytes_copied += 8;              /* ADDS R4, #8 */
    }

    return bytes_copied;                /* MOV R0, R4 */
}

Practical Reverse Engineering p. 79 #9

Question number 9 on page 79 of Practical Reverse Engineering is as follows:

What does the function shown in Figure 2-15 do?

Here is the function's disassembly:

Figure 2-15. Practical Reverse Engineering. © 2014 by Bruce Dang

The ARM processor is in Thumb state. This is essentially the same functionality as Figure 2-14, except the count variable is gone.

int32_t comparison(char *str1, char *str2)
{
    /* LDR R5, =byteArray */
    static BYTE byteArray[] = {0, 1, ..., 0xff};

    while(1)
    {
        /* CMP R4, #0 */
        if (*str1 == '\0')
            break;

        /* LDRB R3, [R1] */
        /* LDRB R4, [R3,R6] */
        /* LDRB R3, [R5,R6] */
        /* CMP R3, R4 */
        if (byteArray[*str1] != byteArray[*str2])
            break;

        ++str1;         /* ADDS R0, #1 */
        ++str2;         /* ADDS R1, #1 */
    }

    /* LDRB R2, [R3,R5] */   
    /* LDRB R3, [R3,R5] */
    /* SUBS R0, R3, R2 */
    return byteArray[*str1] - byteArray[*str2];   
}

Practical Reverse Engineering p. 79 #8

Question number 8 on page 79 of Practical Reverse Engineering is as follows:

In Figure 2-14, byteArray is a 256-character array whose content is byteArray[] = {0, 1, ..., 0xff}.

Here is the disassembly of the function:

Figure 2-14. Practical Reverse Engineering. © 2014 by Bruce Dang

The ARM processor is in Thumb state. We infer that this function takes two strings, as there is byte comparisons and the null byte ends the main loop. There is a 3rd argument which can terminate the main loop early as well. The function is a pretty straightforward translation to C.

int32_t comparison(char *str1, char *str2, uint32_t count)
{
    /* LDR R6, =byteArray */
    static BYTE byteArray[] = {0, 1, ..., 0xff};

    /* CMP R2, #0 */
    while (count > 0)
    {
        --count;    /* SUBS R2, #1 */

        /* LDRB R5, [R0] */
        /* CBZ R5, loc_100E352 */
        if (*str1 == '\0')
            break;

        /* LDRB R3, [R1] */
        /* LDRB R4, [R3,R6] */
        /* LDRB R3, [R5,R6] */
        /* CMP R3, R4 */
        if (byteArray[*str1] != byteArray[*str2])
            break;

        ++str1;     /* ADDS R0, #1 */
        ++str2;     /* ADDS R1, #1 */
    }

    /* SUBS R2, #1 */
    /* CMP R2, #0 */
    if ((count - 1) >= 0)
    {
        /* LDRB R2, [R3,R6] */   
        /* LDRB R3, [R3,R6] */
        /* SUBS R0, R3, R2 */
        return byteArray[*str1] - byteArray[*str2];    
    }

    return NULL;        /* MOVS R0, #0 */
}

Practical Reverse Engineering p. 79 #7

Question number 7 on page 79 of Practical Reverse Engineering is as follows:

Figure 2-13 illustrates a common routine, but you may not have seen it implemented this way.

Here is the disassembly of the function:

Figure 2-13. Practical Reverse Engineering. © 2014 by Bruce Dang

The ARM processor is in Thumb state. We immediately recognize this is a strlen() routine. There is a bit field clear at the end, whose purpose is unclear. Here is how the function is implemented:

size_t strlen(const char *str)
{
    /* CBNZ R0, loc_100E1D8 */
    if (r0 == NULL)
        return 0;   /* MOVS R0, #0 */

    /* MOV R2, R0 */
    char *index = str;
    
    while (1)               /* loc_100E1E4 */
    {
        /* CMB R3, #0 */
        if (*index == '\0')
            break;

        ++index;            /* ADDS R2, #1 */
    }

    /* SUBS R0, R2, R0 */
    return (index - str);
}

Practical Reverse Engineering p. 79 #6

Question number 6 on page 79 of Practical Reverse Engineering is as follows:

Figure 2-12 involves some twiddling.

Here is a disassembly of the function:

Figure 2-12. Practical Reverse Engineering. © 2014 by Bruce Dang

The ARM processor is in Thumb state. The function takes a struct that has a size value and array in it. The array is enumerated looking for a search value, then returning a type of bitmask on its location.

uint64_t search_mask(struct *r0, DWORD search)
{
    /* loc_103B3A8 */
    for (   
        DWORD i = 0;            /* MOVS R2, #0 */
        i < r0->numElements;    /* CMP R2, R4 */
        ++i;                    /* ADDS R2, #1 */
    )
    {
        /* LDR.W R3, [R0,#4]! */
        /* CMP R3, R1 */
        if (r0->elements[i] == search)
        {
            /* SUBS.W R3, R2, #0X20 */
            /* LSLS R1, R3 */
            search = 1 << (i - 0x20);

            /* MOVS R3, #1 */
            /* LSLS.W R0, R3, R2 */
            return (uint64_t) 1 << i;  
        }

    }

    search = 0; /* MOVS R1, #0 */
    return 0;   /* MOVS R0, #0 */
}

Here is a struct definition:

struct r0
{
    DWORD numElements;  /* 0x0 */
    DWORD elements[?];  /* 0x4 */
}