## Trace (RE, 4p) 	follow the trace trace.log	update:	the flag is at 0x400D80	*(uint32_t*)0x00410EA0 == 0x400D80  ###ENG[PL](#pl-version)
We are given very long execution trace (list of opcodes executed by processor, in order) and want to get flag out of it.
It seems funny, because that was really interesting challenge. At the beginning we didn't even know where tha flag was, because tracelog doesn't contain any data (only opcodes).
We started from processing call log. We wanted to get program code from it, so we just sorted it (we wanted to get real program code that was executed)
    sort trace.log | uniq > prog
Then we hacked quick and dirty script to process that code and split it into basic blocks:
```pythonimport string
blocks=[[]]blockno={}
def is_final(ins):    FINAL="move r1, r1"    return string.find(ins, FINAL)!=-1
for line in open("prog").read().split("\n")[:-1]:    blocks[-1].append(line)    blockno[line]=len(blocks)-1    if is_final(line):        blocks.append([])blocks=blocks[:-1]
f=open("basic_blocks","w")for cnt, block in enumerate(blocks):    f.write("Basic block #"+str(cnt)+"\n")    for line in block:        f.write(line+"\n")    f.write("\n========\n\n")f.close()
bb=[]next_check=Truefor line in open("log").read().split("\n")[:-1]:    if is_final(line):        next_check=True        continue    if next_check:        next_check=False        bb.append(blockno[line])
print bb```
Result of running that script (with my manual annotations after //, no point in delaying that):
```asm// function red() - strlenBasic block #0[INFO]00400770       addiu r29, r29, 0xffffffe8     // r29 -= 18[INFO]00400774               sw r30, [r29+0x14]     // r30 = r29[0x14][INFO]00400778                    move r30, r29     // r30 = r29[INFO]0040077c                sw r4, [r30+0x18]     // r4 = r30[0x18][INFO]00400780                 sw r0, [r30+0x8]     // r0 = r30[8]
// block 0x400784[INFO]00400784                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400788                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]0040078c                  addu r2, r3, r2     // r2 += r3[INFO]00400790                  lb r2, [r2+0x0]     // r2 = r2[0][INFO]00400794                bnez r2, 0x4007a8     // if (r2 != 0) goto BLOCK_2
========
Basic block #1[INFO]0040079c                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007a0                       j 0x4007bc     // goto BLOCK_3
========
Basic block #2[INFO]004007a8                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007ac                addiu r2, r2, 0x1     // r2 += 1[INFO]004007b0                 sw r2, [r30+0x8]     // r30[8] = r2[INFO]004007b4                       j 0x400784     // goto 0x400784
========
Basic block #3[INFO]004007bc                    move r29, r30     // r29 = r30[INFO]004007c0               lw r30, [r29+0x14]     // r30 = r29[0x14][INFO]004007c4             addiu r29, r29, 0x18     // r29 += 18[INFO]004007c8                           jr r31     // ret
========
// function green() - strcpyBasic block #4[INFO]004007d0       addiu r29, r29, 0xffffffe8     // r29 -= 18[INFO]004007d4               sw r30, [r29+0x14]     // r29[0x14] = r30[INFO]004007d8                    move r30, r29     // r30 = r29[INFO]004007dc                sw r4, [r30+0x18]     // r30[0x18] = r4[INFO]004007e0                sw r5, [r30+0x1c]     // r30[0x1c] = r5[INFO]004007e4                 sw r0, [r30+0x8]     // r30[8] = r0[INFO]004007e8                       j 0x40081c     // goto 0x40081c
========
Basic block #5[INFO]004007f0                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007f4                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]004007f8                  addu r2, r3, r2     // r2 += r3[INFO]004007fc                 lw r3, [r30+0x8]     // r3 = r30[8][INFO]00400800                lw r4, [r30+0x1c]     // r4 = r30[0x1c][INFO]00400804                  addu r3, r4, r3     // r3 += r4[INFO]00400808                  lb r3, [r3+0x0]     // r3 = r3[0][INFO]0040080c                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400810                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400814                addiu r2, r2, 0x1     // r2 += 1[INFO]00400818                 sw r2, [r30+0x8]     // r30[8] = r2
// block 0x40081c[INFO]0040081c                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400820                lw r3, [r30+0x1c]     // r3 = r30[0x1c][INFO]00400824                  addu r2, r3, r2     // r2 += r3[INFO]00400828                  lb r2, [r2+0x0]     // r2 = r2[0][INFO]0040082c                bnez r2, 0x4007f0     // if r2 != 0: goto BLOCK_5
========
Basic block #6[INFO]00400834                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400838                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]0040083c                  addu r2, r3, r2     // r2 += r3[INFO]00400840                  sb r0, [r2+0x0]     // r2[0] = r0[INFO]00400844                    move r29, r30     // r29 = r30[INFO]00400848               lw r30, [r29+0x14]     // r30 = r29[0x14] [INFO]0040084c             addiu r29, r29, 0x18     // r29 += 18[INFO]00400850                           jr r31     // ret
========
// function blue()Basic block #7[INFO]00400858       addiu r29, r29, 0xffffffd0 [INFO]0040085c               sw r31, [r29+0x2c] [INFO]00400860               sw r30, [r29+0x28] [INFO]00400864                    move r30, r29 [INFO]00400868                sw r4, [r30+0x30]     // r30[0x30] = r4  # buffer start[INFO]0040086c                sw r5, [r30+0x34]     // r30[0x34] = r5  # length[INFO]00400870                lw r2, [r30+0x34]     // r2 = r30[0x34][INFO]00400874                 slti r2, r2, 0x2     // r2 = (r2 < 2)[INFO]00400878                beqz r2, 0x400888     // if (r2 == 0) goto BLOCK_9   # if length >= 2 continue
========
Basic block #8[INFO]00400880                       j 0x4009bc     // goto exitfunc (BLOCK_14)
========
Basic block #9[INFO]00400888                lw r2, [r30+0x30]     // r2 = r30[0x30][INFO]0040088c                 lbu r2, [r2+0x0]     // r2 = r2[0]   # first byte of buffer[INFO]00400890                sb r2, [r30+0x20]     // r30[0x20] = r2[INFO]00400894                addiu r2, r0, 0x1     // r2 = 1[INFO]00400898                sw r2, [r30+0x18]     // r30[0x18] = r2[INFO]0040089c                addiu r2, r0, 0x1     // r2 = 1[INFO]004008a0                sw r2, [r30+0x1c]     // r30[0x1c] = r2[INFO]004008a4                       j 0x40092c     // goto unnamed block
========
Basic block #10[INFO]004008ac                lw r2, [r30+0x1c]     // r2 = r30[0x1c] # indeks[INFO]004008b0                lw r3, [r30+0x30]     // r3 = r30[0x30] # start buffera[INFO]004008b4                  addu r2, r3, r2     // r2 += r3[INFO]004008b8                  lb r2, [r2+0x0]     // r2 = r2[0] # next character[INFO]004008bc                lb r3, [r30+0x20]     // r3 = r30[0x20] # first byte of buffer[INFO]004008c0                   slt r2, r2, r3     // r2 = (r2 < r3)[INFO]004008c4                beqz r2, 0x400920     // if r2 != 0 goto unnamed block # if (r2 >= r3) 
========
Basic block #11[INFO]004008cc                lw r2, [r30+0x18]     // r2 = r30[0x18]  # counter18[INFO]004008d0                lw r3, [r30+0x30]     // r3 = r30[0x30] # start of buffer[INFO]004008d4                  addu r2, r3, r2     // r2 += r3[INFO]004008d8                 lbu r2, [r2+0x0]     // r2 = r2[0] # take byte from buffer[counter18][INFO]004008dc                sb r2, [r30+0x21]     // r30[0x21] = r2[INFO]004008e0                lw r2, [r30+0x18]     // r2 = r30[0x18][INFO]004008e4                lw r3, [r30+0x30]     // r3 = r30[0x30] # adress buffer[INFO]004008e8                  addu r2, r3, r2     // r2 += r3[INFO]004008ec                lw r3, [r30+0x1c]     // r3 = r30[0x1c] # counter1c[INFO]004008f0                lw r4, [r30+0x30]     // r4 = r30[0x30] # adress buffer[INFO]004008f4                  addu r3, r4, r3     // r3 += r4[INFO]004008f8                  lb r3, [r3+0x0]     // r3 = r3[0] # buffer[counter1c][INFO]004008fc                  sb r3, [r2+0x0]     // r2[0] = r3  # buffer[counter18] = buffer[counter1c][INFO]00400900                lw r2, [r30+0x1c]     // r2 = r30[0x1c][INFO]00400904                lw r3, [r30+0x30]     // r3 = r30[0x30][INFO]00400908                  addu r2, r3, r2     // r2 += r3  # adress buffer[counter1c][INFO]0040090c               lbu r3, [r30+0x21]     // r3 = r30[0x21][INFO]00400910                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400914                lw r2, [r30+0x18]     // \[INFO]00400918                addiu r2, r2, 0x1     // r30[r18] += 1[INFO]0040091c                sw r2, [r30+0x18]     // /
// block[INFO]00400920                lw r2, [r30+0x1c]     // \[INFO]00400924                addiu r2, r2, 0x1     // r30[r1c] += 1[INFO]00400928                sw r2, [r30+0x1c]     // /
// block[INFO]0040092c                lw r3, [r30+0x1c]     // r3 = r30[0x1c]   # some index (indeks1c)[INFO]00400930                lw r2, [r30+0x34]     // r2 = r30[0x34]   # length[INFO]00400934                   slt r2, r3, r2     // r2 = (r3 < r2)[INFO]00400938                bnez r2, 0x4008ac     // if index is not longer than lengrth, jump to BLOCK_10
========
Basic block #12[INFO]00400940                lw r2, [r30+0x18]     // l2 = r30[0x18]   # indeks2 (indeks18)[INFO]00400944         addiu r2, r2, 0xffffffff     // r2 -= 1[INFO]00400948                lw r3, [r30+0x30]     // r3 = r30[0x30][INFO]0040094c                  addu r2, r3, r2 [INFO]00400950                 lbu r2, [r2+0x0]     // r2 = buffer[r18 - 1][INFO]00400954                sb r2, [r30+0x21]     // r30[0x21] = r2[INFO]00400958                lw r2, [r30+0x18] [INFO]0040095c         addiu r2, r2, 0xffffffff     // r2 = r30[0x18] - 1[INFO]00400960                lw r3, [r30+0x30] [INFO]00400964                  addu r2, r3, r2     // r2 = &buffer[r2][INFO]00400968                lw r3, [r30+0x30][INFO]0040096c                  lb r3, [r3+0x0]     // r3 = buffer[0] [INFO]00400970                  sb r3, [r2+0x0]     // buffer[r18-1] = buffer[0][INFO]00400974                lw r2, [r30+0x30] [INFO]00400978               lbu r3, [r30+0x21] [INFO]0040097c                  sb r3, [r2+0x0]     // buffer[0] = r30[r21];[INFO]00400980                lw r2, [r30+0x18]     [INFO]00400984         addiu r2, r2, 0xffffffff     // r2 -= 1[INFO]00400988                lw r4, [r30+0x30] [INFO]0040098c                      move r5, r2     // r5 = r2[INFO]00400990                     jal 0x400858     // call blue()
========
Basic block #13[INFO]00400998                lw r2, [r30+0x18][INFO]0040099c                lw r3, [r30+0x30] [INFO]004009a0                  addu r4, r3, r2     // r4 = &buffer[r18] [INFO]004009a4                lw r3, [r30+0x34] [INFO]004009a8                lw r2, [r30+0x18] [INFO]004009ac                  subu r2, r3, r2     // r2 = buflen - r18[INFO]004009b0                      move r5, r2     // r5 = r2[INFO]004009b4                     jal 0x400858     // call blue()
========
Basic block #14[INFO]004009bc                    move r29, r30     // exit func[INFO]004009c0               lw r31, [r29+0x2c]     // r31 = r29[0x2c][INFO]004009c4               lw r30, [r29+0x28]     // r39 = r29[0x28][INFO]004009c8             addiu r29, r29, 0x30     // r29 += 0x30[INFO]004009cc                           jr r31     // ret
========
// main()Basic block #15[INFO]004009d4       addiu r29, r29, 0xfffffec8 [INFO]004009d8              sw r31, [r29+0x134] [INFO]004009dc              sw r30, [r29+0x130] [INFO]004009e0                    move r30, r29 [INFO]004009e4                    lui r28, 0x42 [INFO]004009e8       addiu r28, r28, 0xffff8eb0 [INFO]004009ec               sw r28, [r29+0x10][INFO]004009f0                     lui r2, 0x41 [INFO]004009f4                lw r2, [r2+0xea0] [INFO]004009f8                      move r4, r2     // r4 = FLAG [INFO]004009fc                     jal 0x400770     // strlen(FLAG)[INFO]00400a00                      move r1, r1 
========
Basic block #16[INFO]00400a04               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400a08                sw r2, [r30+0x2c]     // r30[0x2c] = r2 (result of strlen)[INFO]00400a0c                sw r0, [r30+0x18]     // r30[0x18] = 0[INFO]00400a10                       j 0x400a4c [INFO]00400a14                      move r1, r1 
========
Basic block #17 - compute something funny, looks like abcdefghi... array[INFO]00400a18                lw r2, [r30+0x18]     // r2 = r30[0x18] [INFO]00400a1c                andi r2, r2, 0xff     // r2 &= 0xFF[INFO]00400a20               addiu r2, r2, 0x61     // r2 += 0x61   # += 'a'[INFO]00400a24                andi r2, r2, 0xff     // r2 &= 0xFF[INFO]00400a28                 sll r3, r2, 0x18     // r3 = r2 << 0x18[INFO]00400a2c                 sra r3, r3, 0x18     // r3 = r3 >> 0x18[INFO]00400a30              addiu r4, r30, 0x30     // r4 = r30 + 0x30[INFO]00400a34                lw r2, [r30+0x18]     // r2 = r30[0x18]    # indekx[INFO]00400a38                  addu r2, r4, r2     // r2 += r4          # bufer[index]?[INFO]00400a3c                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400a40                lw r2, [r30+0x18]     // \[INFO]00400a44                addiu r2, r2, 0x1     // r30[0x18] += 1[INFO]00400a48                sw r2, [r30+0x18]     // /
// block[INFO]00400a4c                lw r2, [r30+0x18]     // r2 = r30[0x18] (starting with 00[INFO]00400a50                slti r2, r2, 0x1a     // while r2 < 0x1a, so string length[INFO]00400a54                bnez r2, 0x400a18 
========
Basic block #18[INFO]00400a5c                sw r0, [r30+0x1c]     // r30[0x1c] = 0[INFO]00400a60                       j 0x400aa0     // goto ...
========
Basic block #19[INFO]00400a68                lw r2, [r30+0x1c]     // r2 = r30[0x1c]  # offset in buffer?[INFO]00400a6c               addiu r2, r2, 0x1a     // r2 += 0x1a[INFO]00400a70                lw r3, [r30+0x1c]     // r30 = r30[0x1c] # index[INFO]00400a74                andi r3, r3, 0xff     // r3 &= 0xFF[INFO]00400a78               addiu r3, r3, 0x41     // r3 += 0x41   # 'A'[INFO]00400a7c                andi r3, r3, 0xff     // r3 &= 0xFF[INFO]00400a80                 sll r3, r3, 0x18     // r3 <<= 0x18[INFO]00400a84                 sra r3, r3, 0x18     // r3 >>= 0x18[INFO]00400a88              addiu r4, r30, 0x30     // r4 = r30 + 0x30  # another buffer?[INFO]00400a8c                  addu r2, r4, r2     // r2 += r4         # buffer[index]?[INFO]00400a90                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400a94                lw r2, [r30+0x1c]     // \[INFO]00400a98                addiu r2, r2, 0x1     // r30[0x1c] += 1[INFO]00400a9c                sw r2, [r30+0x1c]     // /[INFO]00400aa0                lw r2, [r30+0x1c]     // stupid compiler
// block[INFO]00400aa4                slti r2, r2, 0x1a     // loop 26 times[INFO]00400aa8                bnez r2, 0x400a68
========
Basic block #20[INFO]00400ab0                sw r0, [r30+0x20]     // r30[0x20] = 0[INFO]00400ab4                       j 0x400af4 [INFO]00400ab8                      move r1, r1 
========
Basic block #21[INFO]00400abc                lw r2, [r30+0x20]     //[INFO]00400ac0               addiu r2, r2, 0x34     //  offset in buffer[INFO]00400ac4                lw r3, [r30+0x20]     //[INFO]00400ac8                andi r3, r3, 0xff     //[INFO]00400acc               addiu r3, r3, 0x30     //[INFO]00400ad0                andi r3, r3, 0xff     //[INFO]00400ad4                 sll r3, r3, 0x18     //[INFO]00400ad8                 sra r3, r3, 0x18     //[INFO]00400adc              addiu r4, r30, 0x30     //  create buffer filled with 012345...[INFO]00400ae0                  addu r2, r4, r2     //[INFO]00400ae4                  sb r3, [r2+0x0]     //[INFO]00400ae8                lw r2, [r30+0x20]     //[INFO]00400aec                addiu r2, r2, 0x1     //[INFO]00400af0                sw r2, [r30+0x20]     //[INFO]00400af4                lw r2, [r30+0x20]     //[INFO]00400af8                 slti r2, r2, 0xa     //[INFO]00400afc                bnez r2, 0x400abc     //
========
Basic block #22[INFO]00400b04               addiu r2, r0, 0x7b     // r2 = 0x7b  # {[INFO]00400b08                sb r2, [r30+0x6e]     // r30[0x6e] = r2[INFO]00400b0c               addiu r2, r0, 0x7d     // r2 = 0x7d  # }[INFO]00400b10                sb r2, [r30+0x6f]     // r30[0x6f] = r2[INFO]00400b14                     lui r2, 0x41     // r2 = 0x41[INFO]00400b18                lw r3, [r2+0xea0]     // r3 = &FLAG[INFO]00400b1c              addiu r2, r30, 0x30     // r2 = r30 + 0x30   - start of buffer[INFO]00400b20               addiu r2, r2, 0x40     // r2 += 0x40        - 40 byte offset[INFO]00400b24                      move r4, r2     // r4 = r2           - copy there[INFO]00400b28                      move r5, r3     // r5 = r3           - flag[INFO]00400b2c                     jal 0x4007d0     // strcpy()
========
Basic block #23[INFO]00400b34               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400b38              addiu r2, r30, 0x30     // r2 = r30 + 0x30[INFO]00400b3c                      move r4, r2     // r4 = r2[INFO]00400b40                     jal 0x400770     // strlen()    # wychodzi 90
========
Basic block #24[INFO]00400b48               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400b4c                      move r3, r2     // r3 = r2[INFO]00400b50              addiu r2, r30, 0x30     // r2 = r30 + 0x30[INFO]00400b54                      move r4, r2     // r4 = r2  # r2 = buffer start[INFO]00400b58                      move r5, r3     // r5 = r3  # r5 = 90 (strlen result)[INFO]00400b5c                     jal 0x400858     // NIEBIESKA()[INFO]00400b60                      move r1, r1 
========
Basic block #25[INFO]00400b64               lw r28, [r30+0x10] [INFO]00400b68              addiu r2, r30, 0x30 [INFO]00400b6c                      move r4, r2 [INFO]00400b70                     jal 0x400770 [INFO]00400b74                      move r1, r1 
========
Basic block #26[INFO]00400b78               lw r28, [r30+0x10] [INFO]00400b7c                sw r2, [r30+0x2c] [INFO]00400b80                sw r0, [r30+0x24] [INFO]00400b84                sw r0, [r30+0x28] [INFO]00400b88                       j 0x400bd4 [INFO]00400b8c                      move r1, r1 
========
Basic block #27[INFO]00400b90              addiu r3, r30, 0x30 [INFO]00400b94                lw r2, [r30+0x28] [INFO]00400b98                  addu r2, r3, r2 [INFO]00400b9c                  lb r3, [r2+0x0] [INFO]00400ba0                lw r2, [r30+0x28] [INFO]00400ba4                addiu r2, r2, 0x1 [INFO]00400ba8              addiu r4, r30, 0x30 [INFO]00400bac                  addu r2, r4, r2 [INFO]00400bb0                  lb r2, [r2+0x0] [INFO]00400bb4             beq r3, r2, 0x400bc8 [INFO]00400bb8                      move r1, r1 
========
Basic block #28[INFO]00400bbc                lw r2, [r30+0x24] [INFO]00400bc0                addiu r2, r2, 0x1 [INFO]00400bc4                sw r2, [r30+0x24] [INFO]00400bc8                lw r2, [r30+0x28] [INFO]00400bcc                addiu r2, r2, 0x1 [INFO]00400bd0                sw r2, [r30+0x28] [INFO]00400bd4                lw r2, [r30+0x2c] [INFO]00400bd8         addiu r3, r2, 0xffffffff [INFO]00400bdc                lw r2, [r30+0x28] [INFO]00400be0                   slt r2, r2, r3 [INFO]00400be4                bnez r2, 0x400b90 [INFO]00400be8                      move r1, r1 
========
Basic block #29[INFO]00400bec                lw r3, [r30+0x24] [INFO]00400bf0               addiu r2, r0, 0x3f [INFO]00400bf4             beq r3, r2, 0x400c10 [INFO]00400bf8                      move r1, r1 
========
Basic block #30[INFO]00400c10              addiu r2, r30, 0x30 [INFO]00400c14                      move r4, r2 [INFO]00400c18          lw r2, [r28+0xffff8034] [INFO]00400c1c                     move r25, r2 [INFO]00400c20                         jalr r25 [INFO]00400c24                      move r1, r1 ```
This code also prints order in which blocks were executed. That allowed us to draw this pretty graph (I allowed myself to color functions):
![](./graph.png)
As you might have noticed, I recognised red and green function immediately (that's only because they were rather obvious) - they were strlen and strcpy respectively.I also analysed what the code is doing at the beginnign (EP is in block 15) - it is creating one big buffer in memory, and appending flag to it.So in the end, we are stuck with following blob in memory:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}[FLAGFLAGFLAGFLAGFLAGFLAG]
And then, blue function is called. Blue function was really complex, so I took liberty to implement it in C:
```cppvoid blue(char *buffer, int buflen) {    if (buflen > 1) {        int r18 = 1;        int r20 = buffer[0];        int r21;        for (int r1c = 1; r1c < buflen; r1c++) {            if (buffer[r1c] >= r20) {                continue;            }            r21 = buffer[r18];            buffer[r18] = buffer[r1c];            buffer[r1c] = r21;            r18 += 1;        }        r21 = buffer[r18-1];        buffer[r18-1] = buffer[0];        buffer[0] = r21;
        blue(buffer, r18-1);        blue(buffer+r18, buflen-r18);    }}```
If I were not mistaken (and I were not), this function should behave exactly like function that our trace executed.This is some variant of quicksort (I'm not theory-savy enough to know exact variant name, but that couldn't be less relevant in solving this challenge).
So the problem arised - what now? We knew *what* was executed, we knew *how* it executed, how can we get possibly recover flag from that?
The path we went were probably not the easiest, but it worked. So, first we choose important "checkpoints" inside function:
```cppvoid blue(char *buffer, int buflen) {    // STARTFX    if (buflen > 1) {        // STARTMAIN        int r18 = 1;        int r20 = buffer[0];        int r21;        for (int r1c = 1; r1c < buflen /*FOR_CHECK*/; r1c++ /*FOR_INC*/)) {            // STARTFOR            if (buffer[r1c] >= r20) {                // SKIP                continue;            }            // SWAP_18_1C            r21 = buffer[r18];            buffer[r18] = buffer[r1c];            buffer[r1c] = r21;            r18 += 1;            // ENDFOR        }        // AFTERFOR        r21 = buffer[r18-1];        buffer[r18-1] = buffer[0];        buffer[0] = r21;
        blue(buffer, r18-1);        blue(buffer+r18, buflen-r18);        // ENDMAIN    }    // ENDFX}```
Than we processed trace.log once again, but looking only at "checkpoints"
```pythondata = open('log').read().split('\n')
for line in data:    if '[INFO]00400858' in line:        print 'STARTFX'    if '[INFO]00400888' in line:        print 'STARTMAIN'    if '[INFO]004008ac' in line:        print 'STARTFOR'    if '[INFO]004008cc' in line:        print 'SWAP_18_1C'    if '[INFO]00400920' in line:        print 'FOR_INC'    if '[INFO]0040092c' in line:        print 'FOR_CHECK'    if '[INFO]00400940' in line:        print 'AFTERFOR'    if '[INFO]004009bc' in line:        print 'ENDMAIN'```
And finally, we hacked (ugly!) script to "follow" log, and do exactly as it told us:
```pythonlog = [x.strip() for x in open('calllog').read().split('\n')]
known = []  # known "facts" about characters in flag
def process(log, il, state):    if log[il] != 'STARTFX':        raise 'error'    il += 1    if len(state) > 1:        if log[il] != 'STARTMAIN':            raise 'error'        il += 1        r18 = 1        for r1c in range(1, len(state)+1):            if log[il] != 'FOR_CHECK':                raise 'error'            il += 1            if r1c == len(state):                break            if log[il] == 'AFTERFOR':                break            if log[il] != 'STARTFOR':                raise 'error'            il += 1            if log[il] == 'SWAP_18_1C':                # we are in 'swap' branch, so buffer[r1c] < state[0]                known.append([state[r1c], '<', state[0]])                il += 1                state[r1c], state[r18] = state[r18], state[r1c]                r18 += 1            else:                # we are /not/ in 'swap' branch, so buffer[1rc] >= state[0]                known.append([state[0], '<=', state[r1c]])            if log[il] != 'FOR_INC':                print il                raise 'error'            il += 1        if log[il] != 'AFTERFOR':            print il, log[il]            raise 'error'        il += 1        state[r18-1], state[0] = state[0], state[r18-1]
        il, state[:r18-1] = process(log, il, state[:r18-1])        il, state[r18:] = process(log, il, state[r18:])    if log[il] != 'ENDMAIN':        raise 'error'    il += 1    return il, state
# stars (*) are placeholders for unknown charactersstate = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}0ctf{********************}')
# replace stars with integers (0 - first unknown, 1 - second unknown, etc)j = 0for i in range(len(state)):    if state[i] == '*':        state[i] = j        j += 1vars = jprocess(log, 0, state)  # processprint state```
Miraculously, that worked. After running that code we were presented with:
    ['0', '0', 14, 6, '1', 2, '2', '3', 3, '4', 18, 13, '5', 12, 4, 8, '6',    11, '7', '8', 16, '9', 10, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',    'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',    'X', 'Y', 'Z', 'a', 'b', 'c', 'c', 'd', 'e', 'f', 'f', 'g', 'h', 'i',    'j', 7, 'k', 17, 9, 'l', 'm', 5, 'n', 'o', 'p', 'q', 19, 1, 'r', 15,    's', 't', 0, 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '{', '}', '}']
If everything worked fine, that should be array after being sorted by algorithm - and everything looked fine.That meant that, for example, judging by their position in sorted array, 14-th and 6-th variable were between'0' and '1' (characters) - so they could be either '0' character or '1' character.
Unfortunately, that was not enough (almost every character had 2 possible values).
But wait, that's more - we know results of comparing variables to other characters - can we use that knowledge to improve ourguesses? It turns out that we can (with even uglier script):
```pythonres = {}for i in range(len(state)):    if not isinstance(state[i], basestring):        j = i        while not isinstance(state[j], basestring):            j -= 1        k = i        while not isinstance(state[k], basestring):            k += 1        res[state[i]] = [state[j], state[k]]
print res
for iteration in range(10):    possible = []    for i in range(vars):        mn, mx = res[i]        for less, op, gtr in known:            if not isinstance(gtr, basestring) and not isinstance(less, basestring):                continue            if op == '<':                if less == i:   # 1 < 'z'                    if mx >= gtr:                        mx = chr(ord(gtr)-1)                if gtr == i:    # 'z' < 1                    if mn <= less:                        mn = chr(ord(less)+1)            if op == '<=':                if less == i:   # 1 <= 'z'                    if mx >= gtr:                        mx = gtr                if gtr == i:    # 'z' <= 1                    if mn <= less:                        mn = less        res[i] = [mn, mx]        if mn == mx:            for xxx in known:                if xxx[0] == i:                    xxx[0] = mn                if xxx[2] == i:                    xxx[2] = mn        else:            pass            #possible.append([mn, mx])
for i in range(vars):    print res[i]```
And result of running that hellish script is (each line represents minimal and maximal possible value for character):
    ['t', 't']    ['r', 'r']    ['1', '1']    ['3', '3']    ['5', '5']    ['m', 'm']    ['1', '1']    ['k', 'k']    ['5', '5']    ['l', 'l']    ['9', 'A']    ['6', '6']    ['5', '5']    ['5', '5']    ['1', '1']    ['r', 's']    ['9', '9']    ['l', 'l']    ['5', '5']    ['r', 'r']
That left us with only 4 possibilities (2 characters had 2 possible values each, rest was uniquely determined):
We just bruteforced that 4 possible flags, and finally got our well-deserved 4 points.We really did a lot of hard work when solving this challenge, it's probable that this was NOT the easiest way.
If I remember correctly, correct flag from 4 possible values were `0ctf{tr135m1k5l96551s9l5r}`.
###PL version
Dostajemy długi trace wykonania (lista opkodów wykonywanych po kolei przez procesor) i chcemy z niego wyciagnąć flagę.
Brzmi zabawnie, bo i było to ciekawe zadanie. Na początku nie wiadomo w ogóle skąd mielibyśmy wziąć tą flagę, skoro w tracelogu nie ma żadnych danych (tylko opcody).
Zaczeliśmy od doprowadzenia call loga do sensownego stanu. Na dobry początek, posortowaliśmy go (żeby uzyskać faktyczny kod programu który był wykonywany):
    sort trace.log | uniq > prog
Następnie napisaliśmy na szybko skrypt do przetworzenia tego kodu i podzielenia go na bloki:
```pythonimport string
blocks=[[]]blockno={}
def is_final(ins):    FINAL="move r1, r1"    return string.find(ins, FINAL)!=-1
for line in open("prog").read().split("\n")[:-1]:    blocks[-1].append(line)    blockno[line]=len(blocks)-1    if is_final(line):        blocks.append([])blocks=blocks[:-1]
f=open("basic_blocks","w")for cnt, block in enumerate(blocks):    f.write("Basic block #"+str(cnt)+"\n")    for line in block:        f.write(line+"\n")    f.write("\n========\n\n")f.close()
bb=[]next_check=Truefor line in open("log").read().split("\n")[:-1]:    if is_final(line):        next_check=True        continue    if next_check:        next_check=False        bb.append(blockno[line])
print bb```
Wynik wykonania tego kodu (razem z moimi ręcznymi anotacjami dodanymi później, nie ma sensu odkładać ich na później)
```asm// function red() - strlenBasic block #0[INFO]00400770       addiu r29, r29, 0xffffffe8     // r29 -= 18[INFO]00400774               sw r30, [r29+0x14]     // r30 = r29[0x14][INFO]00400778                    move r30, r29     // r30 = r29[INFO]0040077c                sw r4, [r30+0x18]     // r4 = r30[0x18][INFO]00400780                 sw r0, [r30+0x8]     // r0 = r30[8]
// block 0x400784[INFO]00400784                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400788                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]0040078c                  addu r2, r3, r2     // r2 += r3[INFO]00400790                  lb r2, [r2+0x0]     // r2 = r2[0][INFO]00400794                bnez r2, 0x4007a8     // if (r2 != 0) goto BLOCK_2
========
Basic block #1[INFO]0040079c                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007a0                       j 0x4007bc     // goto BLOCK_3
========
Basic block #2[INFO]004007a8                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007ac                addiu r2, r2, 0x1     // r2 += 1[INFO]004007b0                 sw r2, [r30+0x8]     // r30[8] = r2[INFO]004007b4                       j 0x400784     // goto 0x400784
========
Basic block #3[INFO]004007bc                    move r29, r30     // r29 = r30[INFO]004007c0               lw r30, [r29+0x14]     // r30 = r29[0x14][INFO]004007c4             addiu r29, r29, 0x18     // r29 += 18[INFO]004007c8                           jr r31     // ret
========
// function green() - strcpyBasic block #4[INFO]004007d0       addiu r29, r29, 0xffffffe8     // r29 -= 18[INFO]004007d4               sw r30, [r29+0x14]     // r29[0x14] = r30[INFO]004007d8                    move r30, r29     // r30 = r29[INFO]004007dc                sw r4, [r30+0x18]     // r30[0x18] = r4[INFO]004007e0                sw r5, [r30+0x1c]     // r30[0x1c] = r5[INFO]004007e4                 sw r0, [r30+0x8]     // r30[8] = r0[INFO]004007e8                       j 0x40081c     // goto 0x40081c
========
Basic block #5[INFO]004007f0                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]004007f4                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]004007f8                  addu r2, r3, r2     // r2 += r3[INFO]004007fc                 lw r3, [r30+0x8]     // r3 = r30[8][INFO]00400800                lw r4, [r30+0x1c]     // r4 = r30[0x1c][INFO]00400804                  addu r3, r4, r3     // r3 += r4[INFO]00400808                  lb r3, [r3+0x0]     // r3 = r3[0][INFO]0040080c                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400810                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400814                addiu r2, r2, 0x1     // r2 += 1[INFO]00400818                 sw r2, [r30+0x8]     // r30[8] = r2
// block 0x40081c[INFO]0040081c                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400820                lw r3, [r30+0x1c]     // r3 = r30[0x1c][INFO]00400824                  addu r2, r3, r2     // r2 += r3[INFO]00400828                  lb r2, [r2+0x0]     // r2 = r2[0][INFO]0040082c                bnez r2, 0x4007f0     // if r2 != 0: goto BLOCK_5
========
Basic block #6[INFO]00400834                 lw r2, [r30+0x8]     // r2 = r30[8][INFO]00400838                lw r3, [r30+0x18]     // r3 = r30[0x18][INFO]0040083c                  addu r2, r3, r2     // r2 += r3[INFO]00400840                  sb r0, [r2+0x0]     // r2[0] = r0[INFO]00400844                    move r29, r30     // r29 = r30[INFO]00400848               lw r30, [r29+0x14]     // r30 = r29[0x14] [INFO]0040084c             addiu r29, r29, 0x18     // r29 += 18[INFO]00400850                           jr r31     // ret
========
// function blue()Basic block #7[INFO]00400858       addiu r29, r29, 0xffffffd0 [INFO]0040085c               sw r31, [r29+0x2c] [INFO]00400860               sw r30, [r29+0x28] [INFO]00400864                    move r30, r29 [INFO]00400868                sw r4, [r30+0x30]     // r30[0x30] = r4  # buffer start[INFO]0040086c                sw r5, [r30+0x34]     // r30[0x34] = r5  # length[INFO]00400870                lw r2, [r30+0x34]     // r2 = r30[0x34][INFO]00400874                 slti r2, r2, 0x2     // r2 = (r2 < 2)[INFO]00400878                beqz r2, 0x400888     // if (r2 == 0) goto BLOCK_9   # if length >= 2 continue
========
Basic block #8[INFO]00400880                       j 0x4009bc     // goto exitfunc (BLOCK_14)
========
Basic block #9[INFO]00400888                lw r2, [r30+0x30]     // r2 = r30[0x30][INFO]0040088c                 lbu r2, [r2+0x0]     // r2 = r2[0]   # first byte of buffer[INFO]00400890                sb r2, [r30+0x20]     // r30[0x20] = r2[INFO]00400894                addiu r2, r0, 0x1     // r2 = 1[INFO]00400898                sw r2, [r30+0x18]     // r30[0x18] = r2[INFO]0040089c                addiu r2, r0, 0x1     // r2 = 1[INFO]004008a0                sw r2, [r30+0x1c]     // r30[0x1c] = r2[INFO]004008a4                       j 0x40092c     // goto unnamed block
========
Basic block #10[INFO]004008ac                lw r2, [r30+0x1c]     // r2 = r30[0x1c] # indeks[INFO]004008b0                lw r3, [r30+0x30]     // r3 = r30[0x30] # start buffera[INFO]004008b4                  addu r2, r3, r2     // r2 += r3[INFO]004008b8                  lb r2, [r2+0x0]     // r2 = r2[0] # next character[INFO]004008bc                lb r3, [r30+0x20]     // r3 = r30[0x20] # first byte of buffer[INFO]004008c0                   slt r2, r2, r3     // r2 = (r2 < r3)[INFO]004008c4                beqz r2, 0x400920     // if r2 != 0 goto unnamed block # if (r2 >= r3) 
========
Basic block #11[INFO]004008cc                lw r2, [r30+0x18]     // r2 = r30[0x18]  # counter18[INFO]004008d0                lw r3, [r30+0x30]     // r3 = r30[0x30] # start of buffer[INFO]004008d4                  addu r2, r3, r2     // r2 += r3[INFO]004008d8                 lbu r2, [r2+0x0]     // r2 = r2[0] # take byte from buffer[counter18][INFO]004008dc                sb r2, [r30+0x21]     // r30[0x21] = r2[INFO]004008e0                lw r2, [r30+0x18]     // r2 = r30[0x18][INFO]004008e4                lw r3, [r30+0x30]     // r3 = r30[0x30] # adress buffer[INFO]004008e8                  addu r2, r3, r2     // r2 += r3[INFO]004008ec                lw r3, [r30+0x1c]     // r3 = r30[0x1c] # counter1c[INFO]004008f0                lw r4, [r30+0x30]     // r4 = r30[0x30] # adress buffer[INFO]004008f4                  addu r3, r4, r3     // r3 += r4[INFO]004008f8                  lb r3, [r3+0x0]     // r3 = r3[0] # buffer[counter1c][INFO]004008fc                  sb r3, [r2+0x0]     // r2[0] = r3  # buffer[counter18] = buffer[counter1c][INFO]00400900                lw r2, [r30+0x1c]     // r2 = r30[0x1c][INFO]00400904                lw r3, [r30+0x30]     // r3 = r30[0x30][INFO]00400908                  addu r2, r3, r2     // r2 += r3  # adress buffer[counter1c][INFO]0040090c               lbu r3, [r30+0x21]     // r3 = r30[0x21][INFO]00400910                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400914                lw r2, [r30+0x18]     // \[INFO]00400918                addiu r2, r2, 0x1     // r30[r18] += 1[INFO]0040091c                sw r2, [r30+0x18]     // /
// block[INFO]00400920                lw r2, [r30+0x1c]     // \[INFO]00400924                addiu r2, r2, 0x1     // r30[r1c] += 1[INFO]00400928                sw r2, [r30+0x1c]     // /
// block[INFO]0040092c                lw r3, [r30+0x1c]     // r3 = r30[0x1c]   # some index (indeks1c)[INFO]00400930                lw r2, [r30+0x34]     // r2 = r30[0x34]   # length[INFO]00400934                   slt r2, r3, r2     // r2 = (r3 < r2)[INFO]00400938                bnez r2, 0x4008ac     // if index is not longer than lengrth, jump to BLOCK_10
========
Basic block #12[INFO]00400940                lw r2, [r30+0x18]     // l2 = r30[0x18]   # indeks2 (indeks18)[INFO]00400944         addiu r2, r2, 0xffffffff     // r2 -= 1[INFO]00400948                lw r3, [r30+0x30]     // r3 = r30[0x30][INFO]0040094c                  addu r2, r3, r2 [INFO]00400950                 lbu r2, [r2+0x0]     // r2 = buffer[r18 - 1][INFO]00400954                sb r2, [r30+0x21]     // r30[0x21] = r2[INFO]00400958                lw r2, [r30+0x18] [INFO]0040095c         addiu r2, r2, 0xffffffff     // r2 = r30[0x18] - 1[INFO]00400960                lw r3, [r30+0x30] [INFO]00400964                  addu r2, r3, r2     // r2 = &buffer[r2][INFO]00400968                lw r3, [r30+0x30][INFO]0040096c                  lb r3, [r3+0x0]     // r3 = buffer[0] [INFO]00400970                  sb r3, [r2+0x0]     // buffer[r18-1] = buffer[0][INFO]00400974                lw r2, [r30+0x30] [INFO]00400978               lbu r3, [r30+0x21] [INFO]0040097c                  sb r3, [r2+0x0]     // buffer[0] = r30[r21];[INFO]00400980                lw r2, [r30+0x18]     [INFO]00400984         addiu r2, r2, 0xffffffff     // r2 -= 1[INFO]00400988                lw r4, [r30+0x30] [INFO]0040098c                      move r5, r2     // r5 = r2[INFO]00400990                     jal 0x400858     // call blue()
========
Basic block #13[INFO]00400998                lw r2, [r30+0x18][INFO]0040099c                lw r3, [r30+0x30] [INFO]004009a0                  addu r4, r3, r2     // r4 = &buffer[r18] [INFO]004009a4                lw r3, [r30+0x34] [INFO]004009a8                lw r2, [r30+0x18] [INFO]004009ac                  subu r2, r3, r2     // r2 = buflen - r18[INFO]004009b0                      move r5, r2     // r5 = r2[INFO]004009b4                     jal 0x400858     // call blue()
========
Basic block #14[INFO]004009bc                    move r29, r30     // exit func[INFO]004009c0               lw r31, [r29+0x2c]     // r31 = r29[0x2c][INFO]004009c4               lw r30, [r29+0x28]     // r39 = r29[0x28][INFO]004009c8             addiu r29, r29, 0x30     // r29 += 0x30[INFO]004009cc                           jr r31     // ret
========
// main()Basic block #15[INFO]004009d4       addiu r29, r29, 0xfffffec8 [INFO]004009d8              sw r31, [r29+0x134] [INFO]004009dc              sw r30, [r29+0x130] [INFO]004009e0                    move r30, r29 [INFO]004009e4                    lui r28, 0x42 [INFO]004009e8       addiu r28, r28, 0xffff8eb0 [INFO]004009ec               sw r28, [r29+0x10][INFO]004009f0                     lui r2, 0x41 [INFO]004009f4                lw r2, [r2+0xea0] [INFO]004009f8                      move r4, r2     // r4 = FLAG [INFO]004009fc                     jal 0x400770     // strlen(FLAG)[INFO]00400a00                      move r1, r1 
========
Basic block #16[INFO]00400a04               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400a08                sw r2, [r30+0x2c]     // r30[0x2c] = r2 (result of strlen)[INFO]00400a0c                sw r0, [r30+0x18]     // r30[0x18] = 0[INFO]00400a10                       j 0x400a4c [INFO]00400a14                      move r1, r1 
========
Basic block #17 - compute something funny, looks like abcdefghi... array[INFO]00400a18                lw r2, [r30+0x18]     // r2 = r30[0x18] [INFO]00400a1c                andi r2, r2, 0xff     // r2 &= 0xFF[INFO]00400a20               addiu r2, r2, 0x61     // r2 += 0x61   # += 'a'[INFO]00400a24                andi r2, r2, 0xff     // r2 &= 0xFF[INFO]00400a28                 sll r3, r2, 0x18     // r3 = r2 << 0x18[INFO]00400a2c                 sra r3, r3, 0x18     // r3 = r3 >> 0x18[INFO]00400a30              addiu r4, r30, 0x30     // r4 = r30 + 0x30[INFO]00400a34                lw r2, [r30+0x18]     // r2 = r30[0x18]    # indekx[INFO]00400a38                  addu r2, r4, r2     // r2 += r4          # bufer[index]?[INFO]00400a3c                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400a40                lw r2, [r30+0x18]     // \[INFO]00400a44                addiu r2, r2, 0x1     // r30[0x18] += 1[INFO]00400a48                sw r2, [r30+0x18]     // /
// block[INFO]00400a4c                lw r2, [r30+0x18]     // r2 = r30[0x18] (starting with 00[INFO]00400a50                slti r2, r2, 0x1a     // while r2 < 0x1a, so string length[INFO]00400a54                bnez r2, 0x400a18 
========
Basic block #18[INFO]00400a5c                sw r0, [r30+0x1c]     // r30[0x1c] = 0[INFO]00400a60                       j 0x400aa0     // goto ...
========
Basic block #19[INFO]00400a68                lw r2, [r30+0x1c]     // r2 = r30[0x1c]  # offset in buffer?[INFO]00400a6c               addiu r2, r2, 0x1a     // r2 += 0x1a[INFO]00400a70                lw r3, [r30+0x1c]     // r30 = r30[0x1c] # index[INFO]00400a74                andi r3, r3, 0xff     // r3 &= 0xFF[INFO]00400a78               addiu r3, r3, 0x41     // r3 += 0x41   # 'A'[INFO]00400a7c                andi r3, r3, 0xff     // r3 &= 0xFF[INFO]00400a80                 sll r3, r3, 0x18     // r3 <<= 0x18[INFO]00400a84                 sra r3, r3, 0x18     // r3 >>= 0x18[INFO]00400a88              addiu r4, r30, 0x30     // r4 = r30 + 0x30  # another buffer?[INFO]00400a8c                  addu r2, r4, r2     // r2 += r4         # buffer[index]?[INFO]00400a90                  sb r3, [r2+0x0]     // r2[0] = r3[INFO]00400a94                lw r2, [r30+0x1c]     // \[INFO]00400a98                addiu r2, r2, 0x1     // r30[0x1c] += 1[INFO]00400a9c                sw r2, [r30+0x1c]     // /[INFO]00400aa0                lw r2, [r30+0x1c]     // stupid compiler
// block[INFO]00400aa4                slti r2, r2, 0x1a     // loop 26 times[INFO]00400aa8                bnez r2, 0x400a68
========
Basic block #20[INFO]00400ab0                sw r0, [r30+0x20]     // r30[0x20] = 0[INFO]00400ab4                       j 0x400af4 [INFO]00400ab8                      move r1, r1 
========
Basic block #21[INFO]00400abc                lw r2, [r30+0x20]     //[INFO]00400ac0               addiu r2, r2, 0x34     //  offset in buffer[INFO]00400ac4                lw r3, [r30+0x20]     //[INFO]00400ac8                andi r3, r3, 0xff     //[INFO]00400acc               addiu r3, r3, 0x30     //[INFO]00400ad0                andi r3, r3, 0xff     //[INFO]00400ad4                 sll r3, r3, 0x18     //[INFO]00400ad8                 sra r3, r3, 0x18     //[INFO]00400adc              addiu r4, r30, 0x30     //  create buffer filled with 012345...[INFO]00400ae0                  addu r2, r4, r2     //[INFO]00400ae4                  sb r3, [r2+0x0]     //[INFO]00400ae8                lw r2, [r30+0x20]     //[INFO]00400aec                addiu r2, r2, 0x1     //[INFO]00400af0                sw r2, [r30+0x20]     //[INFO]00400af4                lw r2, [r30+0x20]     //[INFO]00400af8                 slti r2, r2, 0xa     //[INFO]00400afc                bnez r2, 0x400abc     //
========
Basic block #22[INFO]00400b04               addiu r2, r0, 0x7b     // r2 = 0x7b  # {[INFO]00400b08                sb r2, [r30+0x6e]     // r30[0x6e] = r2[INFO]00400b0c               addiu r2, r0, 0x7d     // r2 = 0x7d  # }[INFO]00400b10                sb r2, [r30+0x6f]     // r30[0x6f] = r2[INFO]00400b14                     lui r2, 0x41     // r2 = 0x41[INFO]00400b18                lw r3, [r2+0xea0]     // r3 = &FLAG[INFO]00400b1c              addiu r2, r30, 0x30     // r2 = r30 + 0x30   - start of buffer[INFO]00400b20               addiu r2, r2, 0x40     // r2 += 0x40        - 40 byte offset[INFO]00400b24                      move r4, r2     // r4 = r2           - copy there[INFO]00400b28                      move r5, r3     // r5 = r3           - flag[INFO]00400b2c                     jal 0x4007d0     // strcpy()
========
Basic block #23[INFO]00400b34               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400b38              addiu r2, r30, 0x30     // r2 = r30 + 0x30[INFO]00400b3c                      move r4, r2     // r4 = r2[INFO]00400b40                     jal 0x400770     // strlen()    # wychodzi 90
========
Basic block #24[INFO]00400b48               lw r28, [r30+0x10]     // r28 = r30[0x10][INFO]00400b4c                      move r3, r2     // r3 = r2[INFO]00400b50              addiu r2, r30, 0x30     // r2 = r30 + 0x30[INFO]00400b54                      move r4, r2     // r4 = r2  # r2 = buffer start[INFO]00400b58                      move r5, r3     // r5 = r3  # r5 = 90 (strlen result)[INFO]00400b5c                     jal 0x400858     // NIEBIESKA()[INFO]00400b60                      move r1, r1 
========
Basic block #25[INFO]00400b64               lw r28, [r30+0x10] [INFO]00400b68              addiu r2, r30, 0x30 [INFO]00400b6c                      move r4, r2 [INFO]00400b70                     jal 0x400770 [INFO]00400b74                      move r1, r1 
========
Basic block #26[INFO]00400b78               lw r28, [r30+0x10] [INFO]00400b7c                sw r2, [r30+0x2c] [INFO]00400b80                sw r0, [r30+0x24] [INFO]00400b84                sw r0, [r30+0x28] [INFO]00400b88                       j 0x400bd4 [INFO]00400b8c                      move r1, r1 
========
Basic block #27[INFO]00400b90              addiu r3, r30, 0x30 [INFO]00400b94                lw r2, [r30+0x28] [INFO]00400b98                  addu r2, r3, r2 [INFO]00400b9c                  lb r3, [r2+0x0] [INFO]00400ba0                lw r2, [r30+0x28] [INFO]00400ba4                addiu r2, r2, 0x1 [INFO]00400ba8              addiu r4, r30, 0x30 [INFO]00400bac                  addu r2, r4, r2 [INFO]00400bb0                  lb r2, [r2+0x0] [INFO]00400bb4             beq r3, r2, 0x400bc8 [INFO]00400bb8                      move r1, r1 
========
Basic block #28[INFO]00400bbc                lw r2, [r30+0x24] [INFO]00400bc0                addiu r2, r2, 0x1 [INFO]00400bc4                sw r2, [r30+0x24] [INFO]00400bc8                lw r2, [r30+0x28] [INFO]00400bcc                addiu r2, r2, 0x1 [INFO]00400bd0                sw r2, [r30+0x28] [INFO]00400bd4                lw r2, [r30+0x2c] [INFO]00400bd8         addiu r3, r2, 0xffffffff [INFO]00400bdc                lw r2, [r30+0x28] [INFO]00400be0                   slt r2, r2, r3 [INFO]00400be4                bnez r2, 0x400b90 [INFO]00400be8                      move r1, r1 
========
Basic block #29[INFO]00400bec                lw r3, [r30+0x24] [INFO]00400bf0               addiu r2, r0, 0x3f [INFO]00400bf4             beq r3, r2, 0x400c10 [INFO]00400bf8                      move r1, r1 
========
Basic block #30[INFO]00400c10              addiu r2, r30, 0x30 [INFO]00400c14                      move r4, r2 [INFO]00400c18          lw r2, [r28+0xffff8034] [INFO]00400c1c                     move r25, r2 [INFO]00400c20                         jalr r25 [INFO]00400c24                      move r1, r1 ```
Ten skrypt wypisał też kolejność w której bloki zostały wykonane. To pozwoliło nam narysować ten piękny graf (pokolorowałem w nim funkcje):
![](./graph.png)
Zielona i czerwona funkcja były łatwe do rozpoznania - to były odpowiednio strcpy i strlen.Przeanalizowałem też kod na początku - tworzy on duży bufor w pamięci, i dokleja do niego flagę.Więc na końcu jesteśmy z takim blobem w pamięci:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}[FLAGFLAGFLAGFLAGFLAGFLAG]
A następnie wywoływana na nim jest niebieska funkcja. Jest ona dużo bardziej skomplikonwaa od poprzednich, więc zaimplementowałem ją w C:
```cppvoid blue(char *buffer, int buflen) {    if (buflen > 1) {        int r18 = 1;        int r20 = buffer[0];        int r21;        for (int r1c = 1; r1c < buflen; r1c++) {            if (buffer[r1c] >= r20) {                continue;            }            r21 = buffer[r18];            buffer[r18] = buffer[r1c];            buffer[r1c] = r21;            r18 += 1;        }        r21 = buffer[r18-1];        buffer[r18-1] = buffer[0];        buffer[0] = r21;
        blue(buffer, r18-1);        blue(buffer+r18, buflen-r18);    }}```
Jeśli się nie myliłem (i nie myliłem się), ta funkcja powinna zachowywać się dokładnie tak jak fukcja z której otrzymaliśmy tracelog.To jakaś wariacja quicksortu, swoją drogą (nie wiem jaka dokładnie, nie ma to znaczenia przy rozwiązywaniu zadania).
Więc powstał problem - co teraz? Wiedzieliśmy co było wykonane, wiedzieliśmy jak było wykonane, jak możemy z tego odzyskać flagę?
Poszliśmy prawdopodobnie bardzo okrężną drogą, ale ważne że zadziałało ostatecznie. Najpierw postanowiliśmy zaznaczyć 'checkpointy' w funkcji:
```cppvoid blue(char *buffer, int buflen) {    // STARTFX    if (buflen > 1) {        // STARTMAIN        int r18 = 1;        int r20 = buffer[0];        int r21;        for (int r1c = 1; r1c < buflen /*FOR_CHECK*/; r1c++ /*FOR_INC*/)) {            // STARTFOR            if (buffer[r1c] >= r20) {                // SKIP                continue;            }            // SWAP_18_1C            r21 = buffer[r18];            buffer[r18] = buffer[r1c];            buffer[r1c] = r21;            r18 += 1;            // ENDFOR        }        // AFTERFOR        r21 = buffer[r18-1];        buffer[r18-1] = buffer[0];        buffer[0] = r21;
        blue(buffer, r18-1);        blue(buffer+r18, buflen-r18);        // ENDMAIN    }    // ENDFX}```
Następnie przetworzyliśmy trace.log patrząc tylko na checkpointy:
```pythondata = open('log').read().split('\n')
for line in data:    if '[INFO]00400858' in line:        print 'STARTFX'    if '[INFO]00400888' in line:        print 'STARTMAIN'    if '[INFO]004008ac' in line:        print 'STARTFOR'    if '[INFO]004008cc' in line:        print 'SWAP_18_1C'    if '[INFO]00400920' in line:        print 'FOR_INC'    if '[INFO]0040092c' in line:        print 'FOR_CHECK'    if '[INFO]00400940' in line:        print 'AFTERFOR'    if '[INFO]004009bc' in line:        print 'ENDMAIN'```
Ostatecznie napisaliśmy (brzydki!) skrypt który podążał logiem i robił dokładnie to samo co było w logu:
```pythonlog = [x.strip() for x in open('calllog').read().split('\n')]
known = []  # known "facts" about characters in flag
def process(log, il, state):    if log[il] != 'STARTFX':        raise 'error'    il += 1    if len(state) > 1:        if log[il] != 'STARTMAIN':            raise 'error'        il += 1        r18 = 1        for r1c in range(1, len(state)+1):            if log[il] != 'FOR_CHECK':                raise 'error'            il += 1            if r1c == len(state):                break            if log[il] == 'AFTERFOR':                break            if log[il] != 'STARTFOR':                raise 'error'            il += 1            if log[il] == 'SWAP_18_1C':                # we are in 'swap' branch, so buffer[r1c] < state[0]                known.append([state[r1c], '<', state[0]])                il += 1                state[r1c], state[r18] = state[r18], state[r1c]                r18 += 1            else:                # we are /not/ in 'swap' branch, so buffer[1rc] >= state[0]                known.append([state[0], '<=', state[r1c]])            if log[il] != 'FOR_INC':                print il                raise 'error'            il += 1        if log[il] != 'AFTERFOR':            print il, log[il]            raise 'error'        il += 1        state[r18-1], state[0] = state[0], state[r18-1]
        il, state[:r18-1] = process(log, il, state[:r18-1])        il, state[r18:] = process(log, il, state[r18:])    if log[il] != 'ENDMAIN':        raise 'error'    il += 1    return il, state
# stars (*) are placeholders for unknown charactersstate = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}0ctf{********************}')
# replace stars with integers (0 - first unknown, 1 - second unknown, etc)j = 0for i in range(len(state)):    if state[i] == '*':        state[i] = j        j += 1vars = jprocess(log, 0, state)  # processprint state```
Nie wiadomo jakim cudem, ale to zadziałąło. Po uruchomieniu tego kodu dostaliśmy coś takiego:
    ['0', '0', 14, 6, '1', 2, '2', '3', 3, '4', 18, 13, '5', 12, 4, 8, '6',    11, '7', '8', 16, '9', 10, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',    'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',    'X', 'Y', 'Z', 'a', 'b', 'c', 'c', 'd', 'e', 'f', 'f', 'g', 'h', 'i',    'j', 7, 'k', 17, 9, 'l', 'm', 5, 'n', 'o', 'p', 'q', 19, 1, 'r', 15,    's', 't', 0, 't', 'u', 'v', 'w', 'x', 'y', 'z', '{', '{', '}', '}']
Jeśli wszystko zadziałało, to powinna być tablica po posortowaniu przez algorytm - i wszystko wyglądało ok.Ten wynik oznacza że np. 14 i 6 zmienna były pomiędzy znakami '0' i '1' - więc mogły być albo znakami '0' albo '1'.
Niestety, to było niewystarczające do odzyskania flagi (prawie każdy znak miał 2 możliwe wartości - za dużo do zgadnięcia).
Ale w sumie, wiemy coś więcej o fladze - a konkretnie wyniki porównywania zmiennych do innych znaków. Czy możemy uzyć tej wiedzydo poprawienia naszych estymat flagi? Okazuje się że tak (z nawet gorszym skryptem):
```pythonres = {}for i in range(len(state)):    if not isinstance(state[i], basestring):        j = i        while not isinstance(state[j], basestring):            j -= 1        k = i        while not isinstance(state[k], basestring):            k += 1        res[state[i]] = [state[j], state[k]]
print res
for iteration in range(10):    possible = []    for i in range(vars):        mn, mx = res[i]        for less, op, gtr in known:            if not isinstance(gtr, basestring) and not isinstance(less, basestring):                continue            if op == '<':                if less == i:   # 1 < 'z'                    if mx >= gtr:                        mx = chr(ord(gtr)-1)                if gtr == i:    # 'z' < 1                    if mn <= less:                        mn = chr(ord(less)+1)            if op == '<=':                if less == i:   # 1 <= 'z'                    if mx >= gtr:                        mx = gtr                if gtr == i:    # 'z' <= 1                    if mn <= less:                        mn = less        res[i] = [mn, mx]        if mn == mx:            for xxx in known:                if xxx[0] == i:                    xxx[0] = mn                if xxx[2] == i:                    xxx[2] = mn        else:            pass            #possible.append([mn, mx])
for i in range(vars):    print res[i]```
Wynik wykonania tego piekielnego skryptu (każda linia oznacza minimalną i maksymalną możliwą wartośc dla każdego znaku):
    ['t', 't']    ['r', 'r']    ['1', '1']    ['3', '3']    ['5', '5']    ['m', 'm']    ['1', '1']    ['k', 'k']    ['5', '5']    ['l', 'l']    ['9', 'A']    ['6', '6']    ['5', '5']    ['5', '5']    ['1', '1']    ['r', 's']    ['9', '9']    ['l', 'l']    ['5', '5']    ['r', 'r']
Więc zostały tylko 4 możliwości (2 znaki miały po 2 możliwości, reszta była unikalna):
Po prostu bruteforcowaliśmy te 4 możłiwości na panelu do zgłaszania flag, i dostaliśmy nasze dobrze zasłużone 4 punkty.
Naprawdę sporo pracy zrobiliśmy podczas rozwiązywania tego zadania - prawdopodpobnie to nie był najprostszy sposób na rozwiązanie tego.
Jeśli dobrze pamiętam, poprawną flagą z 4 możliwych flag było ostatecznie `0ctf{tr135m1k5l96551s9l5r}`.