Tiny Spell Checker (Part II)

In the previous post I introduced the tiny spell checker challenge and some of the solutions our team discussed. In this post I'll go into a bit more detail about the solution I put forward, how well it performed, and some limitations of the approach.

I combined the use of a bloom filter with additional validation using n-grams.

Bloom Filter

The bloom filter is a well-known data structure for checking the existence of an element in a set. The bloom filter provides good space efficiency at the cost of a probabilistic result. In other words, you can ask whether an item exists within a set and get one of two answers: no or probably. You can control how often probably is returned for an item that is not in the set through a few parameters: the number of items in the filter, the number of bits in the filter, and the number of hash functions used to compute the bit indices. 

In my case, the input size was fixed (the number of words in the dictionary) so I could control the number of bits and the number of hashes. Since this challenge was primarily about size I fixed the number of hashes and experimented with a bit count that would fit within the challenge constraints. 

That left me with a calculated probability of returning a false positive somewhere around 1 in 3. We will see how this ultimately impacts the performance of the spell checker below. However, there was still a bit of space remaining to attempt to reduce the number of false positives so I looked to using something else I was exploring in parallel: n-grams.

N-gram Validation

I spent a significant amount of time while exploring the solution thinking about compression. How could I compress the 6.6M to something even close to the 256K size limit for the challenge (zip gets close to 1.7M, for example). As part of that I looked into n-gram substitution - specifically, could I take advantage of known suffixes or prefixes to reduce the amount that needs to otherwise be compressed. 

This ultimately didn't pan out as I ended up needing to store more in metadata to decode the table than the size reduction of the approach. However, one of the challenges with bloom filters is false positives, especially when the table size is constrained and there are many inputs. So when I pivoted to using a bloom filter I returned to the n-gram approach as as a secondary validation mechanism. 

For each of the words in the dictionary I extracted each n-gram and added it to a set. Checking for a valid word then consisted of extracting each n-gram of the input word and verifying it was part of the set.

Much like the bloom filter this has the property of no false negatives (i.e. any n-gram not in the set must be from a misspelled word) with the potential for false positives (i.e. can construct a word from the n-grams set that is not a valid word from the original dictionary). 

For the 6.6M dictionary, the following table indicates the space necessary to encode all of the n-grams of a particular size. 

N	Size
2	1,766
3	33,892
4	330,872
5	1,459,024

To keep within the size constrains of the problem I could only use n-grams of size 2 or 3. I wanted the larger since this was for validation and I felt there would be higher false positive rate using the shorter n-gram size (although, to be fair, I did not measure this).

Building Metadata into the Executable

As I wanted an all-in-one solution, I serialized both the bloom filter and n-gram set to disk as a separate process before building the executable. 

I used a std::bitset for the bloom filter and made sure to set the size to something divisible by 8 so it was possible to serialize without accounting for padded bits. For the n-gram set I ended up using std::set< std::string > so serialization was just a matter of writing the 3-byte sequences out to file. The order in the set didn't matter so I could simply dump the values contiguously given I knew the n-gram size.

With both data sets serialized to disk I used the linker to generate object files out of the binary data so I could link them when building the final executable.

$ ld -r -b binary -o ngram_data.o ngram.bin

$ nm ngram_data.o 

0000000000008464 D _binary_ngram_bin_end

0000000000008464 A _binary_ngram_bin_size

0000000000000000 D _binary_ngram_bin_start

Limitations

Capitalization: To achieve some of the size results I had to make some concessions. For example, all string operations (hashing and n-gram) is performed on lower case strings. This completely removes any capitalization support in this application (a necessary feature for any serious spell checker). 

Speed: Because of the way the dictionary is packed, there is a large upfront cost (relative to the check itself) to load the information into usable data structures before a single word can be checked. I would have liked to have had something that could be searched directly from memory but opted for a more simplistic serialization approach instead.

Results

I computed the full dictionary (6.6M) for n-grams of size 3, hashed each of the 654K words for the bloom filter, and serialized and linked each of those into an executable that came in at 243K. 

In the worst test case (replacing 50% of the dictionary words with invalid words) the f-score was about 0.86 without using n-grams and closer to 0.88 with n-gram validation.

Looking back at the expected false positive rate of the bloom filter (roughly 1 in 3) this is the expected output. With a 654K input, 50% of which are replaced with invalid words, we would expect somewhere around 115K false positives which is consistent with an f-score near 0.85.

Adding in the n-gram effectively helps lower the probability of a false positive from 1 in 3 to just over 1 in 4. There is plenty of room here for optimizations such as fine-tuning the bloom filter to be closer to the size limit, pruning the n-gram list to the most frequent values to reduce size, and so on, but this was a decent start to thinking about the problem.

Tiny Spell Checker (part 1)

Inspired by a post I read about how designing a spell checker used to be a major software development effort[1] I designed a coding challenge of sorts for the teams I work with. We have these types of technical exchanges semi-regularly as a way to collaborate and explore technology problems; they also serve as a great team building exercise.         

I'd like to introduce the problem here and some of the solution space we considered. I plan on providing a bit more detail about my final solution in a future post. 

As an aside, we generally avoid making this competitive; it decreases participation and distracts from the main purpose of exploring the problem space and learning about others' approaches (which may be entirely non-technical).

Below are some of the topics we discussed during the showcase. The topics are primarily centered on various compresssion mechanisms (lossless and otherwise) as you might expect. However, there were additional conversations that considered a broader context. For example:

• translating to another language which had better compression properties 
• using phonetics (stenography)
• a literature survey of compression techniques
• trade-offs in time, space, and accuracy of each approach

It is those last two bullets that really highlight the benefit of these exchanges. 

It is one thing to be able to implement a decent compression algorithm; but learning how to consider the problem under extended or different constraints allows us to apply these ideas to the projects we are working on and generally makes us better developers.

Asymmetric Numeral Systems (ANS)

A set of entropy encoding methods that include probability distributions and finite state machines which combine to achieve performant compression. In particular, we discussed the table-based version of ANS (tANS).

Huffman Coding

Lossless compression technique that uses symbol frequencies (probability) to build a table for encoding symbols relative to their frequency: the more frequent a symbol the fewer the bits used to encode it.

Some additional discussion was the cost of using a well-known table or building it from the input dictionary and storing it in the encoded (compressed) output.

n-grams

Encoding common groups of letters into a single symbol/value. For example, encoding the sequence "ing" as a single value. 

This is very similar to Huffman but operating on n-grams instead of a single byte.

Rabin-Karp

Is an algorithm for searching for a string in a body of text. At a high level it leverages a hash to do approximate string matching and only does full string matching if there is an approximate match.

Trie

A data structure that encodes words in a prefix tree and indicates whether a particular word exists in the tree (i.e. is valid) when all letters follow a path in the tree and end at a word terminator node.

Bloom filter

A data structure that, given a hash function, can answer either: an element may be encoded in the set; or it is definitely not in the set. That is, there is the possibility for false positives but not false negatives when checking for existence of elements.

A nice property of this data structure is that it has known properties regarding the false positive rate given a size and hashing strategy used so it can be tuned to a specific accuracy given size constraints.

Of Binary Bombs (the secret)

So far, I've described six stages of this bomb along with their solution. These stages have built up in difficulty while describing often used programming constructs such as: string comparison, arrays, a switch statement, recursion, lookup tables, linked lists, and here in the final stage a binary search tree.

While solving the 6th phase will successfully defuse the bomb there is a curious section of code executed at the end. The most important thing to notice is that we can not trigger the bomb from this point on; the entire function will only jump to a graceful exit unless we unlock the secrets. Recall the code for sym.phase_defused:

Initially, there is a check for the total number of lines entered so far; until this point that check has failed. Here the jump is bypassed and execution proceeds to call to sscanf. Two important arguments to sscanf here are: the format string: str._d_s (%d %s) and 0x804b770. From that first argument we can infer the types that will be read and the second indicates from where we will read that data. Unlike in prior phases, there is no input line read to start this phase so 0x804b770 must already have data located in it.

If we look at what is stored there we find nothing special - certainly not something that looks like a number followed by a string.

This analysis is using a static binary, however, so this memory may get filled in at runtime. We have looked at each function in turn and the only changes in memory are driven by the inputs we provide. So where, is this address in memory? If we look for known addresses around this we see that 0x804b770 is located at sym.input_strings+240. Remember in phase 2 we determined that sym.input_strings was a global array of 80-byte character arrays to hold the inputs we provide. So 240 bytes beyond that is the 4th solution we provided (the number 9). There was no string after that but that is part of the secret...

The sym.read_line grabs the entire input line and in phase 4 sscanf only looked for %d which leaves the remainder of the buffer untouched. Nothing prevents us from providing some trailing values after the number so long as there is a space between them.

Supposing we did provide a trailing string the next step is to check that string against str.austinpowers. So that is the secret to accessing the secret phase: update the 4th input to be '9 austinpowers'. 

The secret phase reads in an additional line from the input stream and converts it to a long value using strtol. That value is decremented and compared against 0x3e8 (1000) - the bomb is triggered if our decremented value is greater than that. If the input passes that check we enter the final function: sym.fun7. Prior to going into detail, however, it is important to note that the return value from this function needs to be 0x7 to avoid triggering the bomb. The initial value to sym.fun7 is sym.n1 (0x0804b320).

This is a recursive function very similar to the one explained in stage 4. To understand what is happening with the control flow it is important to first understand what is contained in sym.n1. However, unlike stage 4 this variable name gives us little indication of what the memory may contain.

Looking at the first 16 bytes of that memory location we see the values are (after adjusting for endianess and assuming 32-byte values): 0x24, 0x0804b314, 0x0804b308, 0x0. The second two look very much like memory addresses in a range very close to sym.n1.

Following these two addresses we arrive at a very similar layout. This begins to resemble a recursive data structure most people will recognize: a binary tree. In C it is represented as:

struct bst {
    int value;
    struct bst *left, *right;
};      

Mapping out the entire tree yields the following:

Now, that will make it easier to follow the control flow in sym.fun7 but there are still some pieces that are needed before a solution can be derived directly. Back in sym.fun7, there is an initial check for a nil next pointer and then the remainder of the function follows a pre-order traversal of the binary search tree.

The main concern at this point is understanding how the return value is calculated. Ultimately, we need to understand when the return value will be 7 so that we can provide input that will force a return at that particular point. The control flow on the left subtree either continues down the next left subtree when the argument node value is less than the current node or the right subtree if the value is greater than the current node. If the value is equal to the current node, eax is set to zero and the function returns.

The return path from a left tree traversal simply doubles the value of eax and returns to the caller. The return from the right subtree is a little more interesting - in addition to eax being doubled it is also incremented by one prior to returning to the caller. Since eax is used to hold intermediate memory addresses, the calculation probably only makes sense when the search value is found in the tree (thus setting eax to 0).

Since a found value returns 0 initially any return from a left subtree will only propagate the zero value; in order to get to seven we need to rely on the increment on the return path of the right subtree path. The only path that leads to the target return value is the one from the rightmost leaf in the tree.

To force a return value of 7 we must provide a value of 1001.

Of Binary Bombs (part 6)

In the last installment (phase 5) Dr. Evil used masking and a lookup table to try and defeat any secret agent. I will continue on here with the final phase of this binary bomb: phase 6. (This isn't really the final stage - check out the secret stage)

Our input string is loaded into the edx register as usual but then there is a strange reference to a sym.node1 that gets loaded into local stack space. That makes our first order of business to find what is stored in sym.node1.

The name node1 gives a fairly blatant hint at how we should look at this memory (without the symbols, this task would be a whole lot less straightforward). The first several bytes are pretty sparse: interpreting as 32-bit values we get 0xfd (253), 0x01 (1), and then the value 0x0804b260 (this is stored in little endian). That looks like another memory address; lets see.

Same structure. 0x02d5 (725), 0x02 (2), 0x0804b254. And the pattern continues. I'll take a leap and say that we have something that looks like the following C structure:

struct list_ {
    int value_;
    int index_;
    struct list_ *next_;
};      

I'm going to walk the list for a while to collect the values (and verify the counter continues in order). That results in the following (value_,index_) pairs starting from sym.node1.

(253, 1)
(725, 2)
(301, 3)
(997, 4)
(212, 5)
(432, 6)

The list is terminated at that point with a null next_ pointer. At this point, the values of the list are known so it is appropriate to resume walking the body of sym.phase_6.

Currently, the input string is loaded into edx and the linked list is stored in a local value; next a local buffer is loaded to eax and sym.read_six_numbers is called. I described this function in phase 2 and we can expect that the local buffer will contain our six input numbers after the call. I have a guess at this point what they should be but I want to verify first to avoid any of Dr. Evil's tricks.

The remainder of this phase can be broken down into four distinct loops. They are:

1. Verify the input values
2. Collect the nodes of the above list according to the input values
3. Reorder the original list with that collection
4. Verify the resulting list

While the input verification has a nested loop it is the most straightforward of the steps: it checks that all values are unique and less than 7.

Initially, collecting nodes according to the input values is a little harder to grasp as it too is a nested loop construct but is now dealing with offsetting into structures and moving memory locations (C pointers) around.

Specifically, the commented line below walks the linked list. This is something that would have not been evident had I not understood the memory in sys.node1.

    mov eax, [edx+ecx]
    lea esi, [esi]
    mov esi, [esi+0x8]  ; this uses the 'next' pointer  
    inc ebx
    cmp ebx, eax

The third step, reordering the original list, is short and looks simple enough but took me some time to fully grok. I needed to understand that the previous step was storing local copies of the nodes in the original list. From that the original list is overwirtten here in the order specified by the input.

Finally, the overwritten list is checked to ensure that the value_ elements are arranged in decreasing order.

With that final piece of information the necessary input sequence becomes clear - the solution is to provide index_ values that order the value_ members from largest to smallest.

Below is a mapping of this functionality to some C code that it may have come from.

struct list_ {
    int value_, index_;
    struct list_ *next;
};

void phase_6 (const char * input) {                 
    
    int i = 0;
    struct list_ *list = ..., *node = list;
    int values[6] = {0};     
    struct list_ *nodes[6] = {0};
    read_six_numbers (input, values);
        
    // 0x08048db8 - 0x08048e00
    for (; i < 6; ++i) {
        int j = i + 1;
        if (values[i] > 6) explode_bomb ();
        for (; j < 6; ++j) 
            if (values[i] == values[j]) 
                explode_bomb ();
    }

    // 0x08048e02 - 0x08048e42
    for (i = 0 ; i < 6; ++i) {
        node = list;
        while (node) {
            if (node->index_ == values[i]) {
                nodes[i] = node;
                break;
            }        
            node = node->next;
        }        
    }

    // 0x08048e44 - 0x08048e60
    i = 1;
    list = nodes[0];
    node = list;
    while (i <= 5) {
        node->next = nodes[i];
        node = node->next;
        ++i;
    }
    node->next = 0;

    // 0x08048e67 - 0x08048e85
    node = list;
    for (i = 0; i < 5; ++i)
        if (node->value_ < node->next->value_)
            explode_bomb ();

}

Of Binary Bombs (part 5)

Part 4 detailed a recursive function that calculated the nth entry into the Fibonacci sequence. Here we continue with the next stage to defeating Dr. Evil.

There is a familiar face here: sym.string_length. Recall in phase 1 I glazed over sym.string_not_equal which had buried inside a call to sym.string_length - if you've been following along at home this is not a surprise. The result of this call (which expects our input string as an argument) should be 6.

    cmp eax, 0x6

This is our first clue to solving the riddle.

Peeking ahead a little there are two memory locations referenced directly: sym.array.123 and str.giants. Before we get too far into the details of sym.phase_5 lets look at what each of these contain. Using the memory printing capabilities of radare2 we can do this with: px @ sym.array.123 and ps @ str.giants to get the hex and ASCII representations, respectively.

Not surprisingly str.giants contains the string 'giants' and the content of sym.array.123 is listed below:

Alright, now that we've got some context lets continue with the code.

    lea ecx, [ebp-0x8]      ; load an empty local array
    mov esi, sym.array.123  ; set a pointer to the first element of the memory above
    mov al, [edx+ebx]       ; target of the jump below 
    and al, 0xf
    movsx eax, al
    mov al, [eax+esi]
    mov [edx+ecx], al
    inc edx
    cmp edx, 0x5
    jle 0x8048d57

After loading the address of a local array the code enters a loop from 0 to 5 (for the six characters of our input). The body of that loop does the following:

Selects the nth byte from the user input string, masks off the bottom 4 bits, and then uses that as an index into sym.array.123. The byte at that index is then copied to the local array.

    mov al, [edx+ebx]
    and al, 0xf
    movsx eax, al
    mov al, [eax+esi]
    mov [edx+ecx], al

In C, that might look similar to

char array123[] = "isrveawhobpnutfg", local[6] = {0}, *input = ...;
int i = 0;

for (; i < 6; ++i)
    local[i] = array123[input[i] & 0xf];

After the loop the local array is null terminated and compared against str.giants; matching strings avoids triggering the bomb. Now all we need is to determine what indices from sym.array.123 yield the string 'giants.'

Recall the memory stored in sym.array.123 - isrveawhobpnutfg. The necessary index sequence then becomes: 0xf, 0x0, 0x5, 0xb, 0xd, 0x1. Since our ASCII input is masked we need to find ASCII strings with lower-order bits matching these values. I list the valid combinations (for printable ASCII) below:

0xf : / ? O _ o
0x0 : 0 @ P ` p
0x5 : % 5 E U e u
0xb : + ; K [ k {
0xd : - = M ] m }
0x1 : ! 1 A Q a q

Any combination of those values should be a valid input to solve this stage. Let's try one: 'opekma'

Sweet, almost there. Next up is phase 6 the [supposed] last stage...

Of Binary Bombs (part 4)

Part 3 of this series explored phase_3 of this riddle which marked the first phase that accepted more than a single correct input sequence. Here I'll continue with the next phase: sym.phase_4.

At first, some arguments are loaded onto the stack to prep for a call to sscanf but rather than an immediate string as the format string argument, an address is provided. Recall in in phase_2 that we could get a hint of the input by printing str._d_d_d_d_d_d (ps @ str._d_d_d_d_d_d) - here we need to understand the arguments to sscanf a little to know that the address 0x8049808 should contain a format string. Indeed, it does (ps @ 0x8049808 yields %d) - our input string needs to be a number. That number needs to be larger than 0.

    cmp dword [ebp-0x4], 0x0
    jg 0x8048d0e

After the input is checked, its value is pushed to the stack and control is passed to sym.func4.

The second requirement of our input is now revealed:

    cmp ebx, 0x1
    jle 0x8048cd0

For values larger than 1 sym.func4 is called recursively.

    lea eax, [ebx-0x1]
    push eax
    call sym.func4

So the input value to sym.func4 (our input, initially) is decremented by 1 and passed to the recursive call. The result of that call is saved to esi and then sym.func4 is called recursively yet again - this time after decrementing the input by 2.

    lea eax, [ebx-0x2]
    push eax
    call sym.func4

The return value of the second recursion is added to the result of the first and that sum becomes the return value of this depth of the recursive call. In C, this looks something like:

int func4 (int n) {
    if (n < 2) { return 1; }
    return func4 (n - 1) + func4 (n - 2);
}

Back in sym.phase_4 there is the following check:

    cmp eax, 0x37

The input, when fed to sym.func4, should return 55. The recursion of n-1 + n-2 is one way to calculate the Fibonacci number at index n. That, coupled with the fact that 55 is a Fibonacci number, allows us to derive the necessary input value of 9.

Next up, part 5.

Of Binary Bombs (part 3)

In part 2 I explained both sym.read_line and the solution to sym.phase_2. Here I work through the third phase of Dr. Evil's nasty binary bomb.


I'll assume to start directly at sym.phase_3 beyond the input handling routines previously discussed.

Phase 3 starts with a call to sscanf with a format string of "%d %c %d". So we should provide a number, character, and a number. The first number should be less than or equal to 7

    cmp dword [ebp-0xc], 0x7

and is used to calculate a jump address

    mov eax, [ebp-0xc]
    jmp dword [eax*4+0x80497e8]

If we start with eax containing 0 this jumps us to a location stored at 0x80497e8. That address is 0x08048be0 - or just over the next instruction.

    mov bl, 0x71
    cmp dword [ebp-0x4], 0x309

This sets bl to 0x71 (ASCII 'q') and compares the third input to 777. If the third input is 777 control jumps to

    cmp bl, [ebp-0x5]

So, to avoid the bomb we can provide the following input: 0 q 777 and we have a valid solution.

But what about setting eax to something other than 0 to start? Let's look at the other possible jump addresses for values less than 8 but greater than 0 for the first input. I've abbreviated the code and commented what is different from the above description.

; eax == 1 - 0x08048c00
    mov bl, 0x62                ; ASCII 'b'
    cmp dword [ebp-0x4], 0xd6   ; 214

; eax == 2 - 0x08048c16
    mov bl, 0x62                ; ASCII 'b'
    cmp dword [ebp-0x4], 0x2f3  ; 755
        
; eax == 3 - 0x08048c28
    mov bl, 0x6b                ; ASCII 'k'
    cmp dword [ebp-0x4], 0xfb   ; 251
        
; eax == 4 - 0x08048c40
    mov bl, 0x6f                ; ASCII 'o'
    cmp dword [ebp-0x4], 0xa0   ; 160
  
; eax == 5 - 0x08048c52
    mov bl, 0x74                ; ASCII 't'
    cmp dword [ebp-0x4], 0x1ca  ; 458

; eax == 6 - 0x08048c64
    mov bl, 0x76                ; ASCII 'v'
    cmp dword [ebp-0x4], 0x30c  ; 780

; eax == 7 - 0x08048c76
    mov bl, 0x62                ; ASCII 'b'
    cmp dword [ebp-0x4], 0x20c  ; 524

So it looks as if there are several answers to this part of the riddle. Let's verify at least one of the others work.

Next, phase 4.

Of Binary Bombs (part 2)

In part 1 I worked out the setup of the binary bomb and walked through the solution to the first phase of the riddle. This post continues from there to examine phase 2.

After defusing phase 1 the program reads the next line from the user (sym.read_line) and calls sym.phase_2. In my first post I glazed over the sym.read_line with some hand-waving so I'd like to revisit that here with a little more attention. As a reminder, in radare2 you can search for a symbol while in visual mode with s (s sym.read_line).

The first thing that happens in sym.read_line (after managing the pointers and local variables) is a call to sym.skip. sym.skip has a little more to it than just this but basically determines which input line is to be read by looking at the global variable sym.num_input_strings and using that as an index into sym.input_strings (a global holding each input string in an 80-byte char array). It returns the string read in eax.

Once a line is read from the input stream the following instructions check the return value of sym.skip.

    test eax, eax
    jne 0x804925f

Only if the return value of sym.skip is zero (when null is returned) does execution not jump to 0x0804925f. I will cover later what happens in the null return case. For now, non-null returns follow this explanation.

    mov eax, [sym.num_input_strings]

At this point, we have entered 2 strings but the global counter sym.num_input_strings has only been updated once so contains the value 1.

    lea eax, [eax+eax*4]
    shl eax, 0x4
    lea edi, [eax+sym.input_strings]

The above sets eax to eax * 5, multiplies the result by 16, and loads the string at sym.input_strings+eax into edi. In this case (sym.num_input_strings == 1) this yields the second index in the sym.input_strings array (recall that each entry there is 80 bytes).

The next set of instructions calculate the length of the input string by decrementing a counter for each non-null byte in the string. The calculation uses some shortcuts for efficiency so is not directly mapped to traditional C-like counting (google 'asm string length' for details).

    mov al, 0x0
    cld
    mov ecx, 0xffffffff 
    repne scasb
    mov eax, ecx
    not eax
    lea edi, [eax-0x1]

Our input strings must fit within the 80-byte array so checking that the string (less newline) is less than 0x4f (79) bytes is done next

    cmp edi, 0x4f

Finally, the newline is replaced with a zero byte

    mov byte [edi+eax+0x804b67f], 0x0

the input string is placed in eax and the global sym.num_input_strings is incremented by 1.

At this point eax contains the input string and I can resume with the second phase of the bomb.

After the prologue and setting aside 32 bytes of local space the input string is copied to edx and the local buffer address is loaded into eax. These two arguments are pushed onto the stack and sym.read_six_numbers is invoked. To avoid making this post too long I'll skip over the detail of sym.read_six_numbers and just mention that the numbers in the input string are read into the local array via sscanf with a format string of "%d %d %d %d %d %d" (Hint #1). 

The following check verifies that the first entry in the local array has the value 1 and is the second hint to solving this phase.

    cmp dword [ebp-0x18], 0x1                

The next section of code is the meat of phase 2 and how we determine what numbers to include in our string.

    mov ebx, 0x1
    lea esi, [ebp-0x18] 
    lea eax, [ebx+0x1]  ; target of jump below (0x8048b76)
    imul eax, [esi+ebx*4-0x4] 
    cmp [esi+ebx*4], eax   
    je 0x8048b88 
    call sym.explode_bomb
    inc ebx             ; target of jump above (0x8048b88)
    cmp ebx, 0x5  
    jle 0x8048b76 

This is a loop from 1 to 5 using ebx as the counter. The initialization sets ebx to 1 and esi to the beginning of the array of converted numbers (the local array). On each iteration of the loop eax is set to ebx + 1 then multiplied by the nth entry of the local array (n is ebx - 1). The result of that is compared to the next entry in the array. In C parlance this might look like:

    int xs[] = {...}; 
    for (i = 0; i < 5; ++i)
        if ((i+1) * xs[i] != xs[i+1]) 
            FAIL();

If we know that xs[0] must be 1 we can now use the above to calculate the remainder of the array.

    x[1] = 2 * x[0] => 2
    x[2] = 3 * x[1] => 6 
    x[3] = 4 * x[2] => 24
    ...

Ultimately, our input requirements become: 1 2 6 24 120 720. This works as expected and phase 2 is now solved.

On to phase 3.

Of Binary Bombs (part 1)

I was recently turned on to radare2 (http://www.radare.org/y/) and, in an attempt to use-it-to-learn-it, I am going to try and solve the sample binary bomb provided as an example lab for the CMU computer systems course. I'm aiming to make my next few posts an account of trying to solve that puzzle (and learn this new tool).

Caveat lector: I've basically no experience with binary tools and assembly language so this will be deliberate and likely full of amateur mistakes.


I expect to be able to analyze this as the program would be run so I'm staring at the main entry point and assuming that there is nothing tricky happening prior to that. Load up radare2 and enter visual mode (press 'V' at the command prompt) then press 'p' until the view is one that resembles assembly instructions. Once there search for the main entry point (at the command prompt: s main). That will bring you to a screen that looks similar to:

First thing to happen in this program is to check the arguments to main to determine whether to read from stdin or from a file. This progresses from the function prologue: saving the base pointer (ebp); copy the stack pointer (esp); and reserve 20 bytes for local use (sub esp, 0x14). The program then continues to look at the value of argc and acts accordingly eventually assigning the input stream (stdin or otherwise) to sym.infile.

Without error, control flow reaches address 0x08048a30 (in my version) which is a call to sym.initialize_bomb. Radare2 allows you to set marks much like you would in vim so if you are familiar with that, set a mark here with ma and hit enter at this address to follow to sym.initialize_bomb. Alternatively, at the command prompt, search for the function symbol with s sym.initialize_bomb. In either case you should see the following:

Here, the program simply sets up to handle SIGINT with the function sig_handler and returns. If you are using marks you can return to the previous address with 'a.

The program continues with a couple of generic prompts, proceeds to read a line of input (which does some internal bookkeeping), and jumps to phase 1 (sys.phase_1). Place a local mark (ma) and jump to the first phase code: we are now ready to start the actual process of solving Dr. Evil's nasty riddle.

Phase 1 is intended to be easy. The first line of input provided to the program is copied to eax, and then two arguments are set up: a global string (at address 0x080497c0) and eax. These arguments are sent to strings_not_equal which returns 0 if the two arguments are the same length and contain the same strings. The check test eax, eax (true when eax is 0) avoids exploding the bomb so we want eax (the first input string) to be the same as whatever is in 0x080497c0.

The radare2 command to print memory as a string is ps. Entering command mode (:) and typing ps @ 0x080497c0 yields: 'Public speaking is very easy.' (the period is significant). Entering that provides:

Next, I'll tackle phase 2.

10 points: 10 plots

As an exercise in expanding my ability to display data I challenged myself to present 10 data points in 10 ways that were as distinct as possible. The idea was simple: use 10 random data points; minimize the axis and other ancillary information so as to focus on the data as much as possible; and try to minimize the overlap between each of the approaches.

Initially, I expected this would be a trivial task - something that would take a single sitting and a little bit of thought. A few attempts later and I kept circling back on a few common ideas while considering just how many approaches I'd not considered. What exists below is a collection of the results of that exercise with explanation if necessary.

1 - Standard Cartesian (scatterplot)

2 - Derivative Cartesian: uses labels instead of points to eliminate the need for tick marks on the x-axis.

3 - Impulses. Mixing the number and characters on the x-axis tick marks is questionable and could just as well have been labels at the top of each impulse

4 - Sorted derivative Cartesian

5 - Boxplot

6 - Barplot

7 - Radial. Points are interpreted as radians and placed starting from 0 radians

8 - Heatmap

9 - Cumulative Sum

10 - Financial/Intensity: Positive values are blue, negative are red. Absolute values define the radius of the circle used.

I considered others such as LOESS fit but they either needed the points to accompany them (to show what was being fitted) which made them too close to the Cartesian plot, or they were too complex for just 10 points.

It was interesting to see how difficult it turned out to be to stretch 10 points into 10 distinct presentation approaches.