## Tuesday, April 10, 2012

### Hex puzzle (2)

Let's continue with the puzzle introduced in the last post (here).

The next step is to stitch the lines together to form the complete text. If they contained random bytes, that would be relatively easy. There are 65536 possible two-byte combinations. We have a total of 340 * 25 = 8500 two-byte (4 hex character) combinations in our data, so the expected number of times any combination should appear in random data is much less than 1.

However, the data is not random, instead, it is highly skewed. Simple modifications to count.py (from last time) show a total of only 370 two-byte combinations in the data (i.e. 65166 of all possible values are not observed), and the top 20 have counts ranging from 464 down to 72.

 ```464 4341 CA 331 4943 IC 309 4167 Ag 281 4c43 LC 234 734c sL 174 4173 As 154 4377 Cw 140 7773 ws 139 7349 sI 139 674d gM 139 674c gL 137 4c44 LD 126 674e gN 104 6749 gI 103 7767 wg 95 4e69 Ni 89 5973 Ys 78 4944 ID 76 4947 IG 72 4e6a Nj ```

In the table above, the first column is the count, the second and third are the hex and ASCII representations.

That compares with a maximum count of 3-4 for random data, and an observed total of 8000 different values on an average run with random data.

This suggests that we should undertake some data exploration to see whether the repetitive character of the data will cause difficulties for the assembly.

The core operation is to take an individual entry at index i in the data (the query), and depending on a parameter (tlen) for the number of characters to choose at the very end of the query, make a substring sequence t, the target to search for. Then, we go through all the other entries looking for a match containing t, and when one is found we save the index of the query and the match as well as the position k where the target t begins in the match string.

The quality of these matches can be assessed in various ways. We expect that the sequence of each match string upstream of the target should be exactly the same as the query. We calculate the offset o where the beginning of the match string should be found in the query. Since this depends on tlen (o = len(L[i]) - k - n) we calculate it for each hit and save it with the other parameters. The offset is also useful for printing the actual alignments in show.

A second quality test is to examine the match strings downstream of the target. In the region of overlap, we expect they should be identical as well. A failure of either test would suggest that the data is causing trouble for our simple search algorithm.

As mentioned last time, the observed hex digits comprise all (and only) those which encode ASCII characters 0..1A..Za..z. Rather than print out strings of 100 characters, it will simplify the output to convert the data to ASCII first. We're assuming that this is what we need to do with the data, but I peeked at the answer on reddit, so it's safe to go ahead.

python convert.py > data.mod.txt
 ```import binascii from utils import load_data L = load_data('reddit.txt') for line in L: print binascii.unhexlify(line)```

Note the extremely repetitive nature of the data by comparing some adjacent output lines:

 ```A1NiAsNiAsMyAsMSA0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAx A1NywsICAyNSwsICA0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAx AgLDUgLDcgLDMgLDAgLDAgLDcgLDIgLDIgLDYgLDYgLDEgNTQs AgLDUgLDcgLDMgLDAgLDAgLDcgLDYgLDIgLDYgLDYgLDEgNTQs xpIG42dCwgIG00YSxpIG42KCwpICAzeywgICAyICwgICA2ICxp xpIG43dCwgIGE3WyxdICA3PSwgIHswNCwsICA2NCwsICAxNiws```

However, for a well-chosen query (one with a rare two-byte combination as the target) and a long enough target length, it's easy to find matches that appear correct. In the output below, we examine the string found at index 0 in the data as the query. The analysis finds 25 matches, data strings where the terminal 4 characters appear somewhere in the match, and all of those matches are perfect ones whether looking upstream and comparing against the query, or looking downstream in each one (beyond the target) and comparing with each other, as shown in the second half of the output.

We'll exercise these routines a bit more next time. I want to see how big to make the target size, and also whether we should exclude some strings from the preliminary analysis. But overall, it looks like we might be OK.

 ```> python search.py i= 0 : 25 matches found 0NiwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc GExc NiwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc iwsICAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CAyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc AyJyxmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc xmICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc mICcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CcwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc cwLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc wLCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc LCwgIDc2KSw7ICAxJCxiICA2PSwgIGExc CwgIDc2KSw7ICAxJCxiICA2PSwgIGExc wgIDc2KSw7ICAxJCxiICA2PSwgIGExc gIDc2KSw7ICAxJCxiICA2PSwgIGExc CAxJCxiICA2PSwgIGExc AxJCxiICA2PSwgIGExc xJCxiICA2PSwgIGExc JCxiICA2PSwgIGExc CxiICA2PSwgIGExc xiICA2PSwgIGExc A2PSwgIGExc 2PSwgIGExc SwgIGExc gIGExc IGExc GExc no mismatches upstream GExc j jR jRyLGE jRyLGEg jRyLGEgeTYo jRyLGEgeTYoL jRyLGEgeTYoLDc jRyLGEgeTYoLDcg jRyLGEgeTYoLDcgL jRyLGEgeTYoLDcgLD jRyLGEgeTYoLDcgLDQ jRyLGEgeTYoLDcgLDQg jRyLGEgeTYoLDcgLDQgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDY jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLD jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDA jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUg jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDc jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgL jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgLD jRyLGEgeTYoLDcgLDQgLDkgLDIgLDYgLDAgLDUgLDcgLDM no mismatches downstream```

search.py
 ```from utils import load_data # tlen is minimum overlap # functions deal with one string at a time # do not assume upstream matches # e is search string, f is potential match def one_search(i,L,tlen): # search result has associated tlen oL = list() e = L[i] t = e[-tlen:] for j,f in enumerate(L): if i == j or not t in f: continue # offset is pos in e where f should start # not guaranteed to match except over t offset = len(e) - f.index(t) - tlen oL.append((j,offset)) oL.sort(key=lambda item:item[1]) return oL # mmL is a list of mismatched strings # ummL contains upstream mismatches def test_upstream(i,L,oL,ummL): e = L[i] for j,o in oL: f = L[j] if not f.startswith(e[o:]): if i < j: ummL.append((i,j)) else: ummL.append((j,i)) def trim_downstream(oL,L,tlen): pL = list() for j,o in oL: f = L[j] k = len(f) - o pL.append((j,f[k:])) return pL def test_downstream(pL,dmmL): mismatches = 0 for i,s1 in pL: for j, s2 in pL: if s1 == s2 or len(s1) < len(s2): continue if not s1.startswith(s2): if i < j: dmmL.append((i,j)) else: dmmL.append((j,i)) if __name__ == '__main__': L = load_data('data.mod.txt') tlen = 4 i = 0 e = L[i] oL = one_search(i,L,tlen) print 'i=', i, ':', len(oL), 'matches found' print e print ' ' * (len(e)-tlen) + e[-tlen:] print for j,o in oL: k = len(e) - o print ' '*o + L[j][:k] ummL = list() test_upstream(i,L,oL,ummL) if ummL: print len(ummL), 'mismatches' else: print 'no mismatches upstream\n' dmmL = list() print e[-tlen:] pL = trim_downstream(oL,L,tlen) for item in pL: print ' '*tlen + item[1] test_downstream(pL,dmmL) if dmmL: print len(dmmL), 'mismatches' else: print 'no mismatches downstream' ```