→ ructf2012 - Reverse400 What I do?

| No TrackBacks
В трех словах:
виртуальная машина, которая выполняет код производящий операции над матрицей, матрица - это представление графа, а алгоритм это поиск кратчайшего пути.
Ответ: Dijkstra

В много слов:
Программа представляет из себя виртуальную машину, с основной функцей:
.text:08048C00 ; char __cdecl vm_exec(struct_vm *vm, int *vm_data)
.text:08048C00 vm_exec         proc near               ; CODE XREF: main+27p
Алгоритм интерпретатора довольно простой, в цикле читается однобайтовый опкод команды, после switch и вызывается функция обработчик нужной команды.
    switch ( *code )
    {
      case 1:
        v2 = code + 1;
        opcode_create_class_1(vm, (char *)vm_data + *(_DWORD *)v2);
        code = v2 + 4;
        break;
...
      case 6:
        v7 = code + 1;
        opcode_add(vm, (int *)vm + *v7, (int *)vm + v7[1]);
        code = v7 + 2;
        break;
...
Команд всего 19, после непродолжительного анализа мы можем написать свой дизассемблер.
def GetMem(start_ea,size):
  r = ""
  for ea in range(start_ea,start_ea+size):
    r += chr(Byte(ea))
  return r

def sign(a):
 if( a >> 15 ):
   return -(65536-a)
 return a

vm_area = 0x0804C080
opcode = [
 {'s':1, 'name':'exit',                 'u':'',         'd':lambda pc,a: "exit" },
 {'s':5, 'name':'class_matrix',         'u':'I',        'd':lambda pc,a: "class_matrix(0x%x) # %d" % (vm_area + a[0],a[0]) },  
 {'s':5, 'name':'class_list',           'u':'I',        'd':lambda pc,a: "class_list(0x%x)   # %d" % (vm_area + a[0],a[0]) },
 {'s':3, 'name':'call_vf1 (get)',       'u':'BB',       'd':lambda pc,a: "matrix%d->vf1_get_val(r%d)" % (a[0],a[1])      }, 
 {'s':3, 'name':'call_vf2 (set)',       'u':'BB',       'd':lambda pc,a: "matrix%d->vf2_set_val(r%d)" % (a[0],a[1])      },
 {'s':3, 'name':'cmp',                  'u':'BB',       'd':lambda pc,a: "cmp r%d,r%d" % (a[0],a[1]) },
 {'s':3, 'name':'add',                  'u':'BB',       'd':lambda pc,a: "add r%d,r%d" % (a[0],a[1]) },
 {'s':3, 'name':'sub',                  'u':'BB',       'd':lambda pc,a: "sub r%d,r%d" % (a[0],a[1]) },
 {'s':3, 'name':'call_vf4 (set col) ',  'u':'BB',       'd':lambda pc,a: "matrix%d->vf4_set_col(r%d)" % (a[0],a[1])    },
 {'s':3, 'name':'call_vf3 (set row)',   'u':'BB',       'd':lambda pc,a: "matrix%d->vf3_set_row(r%d)" % (a[0],a[1])    },
 {'s':2, 'name':'print',                'u':'B',        'd':lambda pc,a: "print r%d" % (a[0]) },
 {'s':3, 'name':'jmp',                  'u':'H',        'd':lambda pc,a: "jmp 0x%x (%d)" % (pc+1+sign(a[0]),a[0]) },    
 {'s':3, 'name':'jz',                   'u':'H',        'd':lambda pc,a: "jz 0x%x (%d)" % (pc+1+sign(a[0]),a[0]) },     
 {'s':3, 'name':'mov reg, #Imm',        'u':'BB',       'd':lambda pc,a: "mov r%d, %d" % (a[0],a[1]) },
 {'s':2, 'name':'inc reg',              'u':'B',        'd':lambda pc,a: "inc r%d" % (a[0]) }, 
 {'s':2, 'name':'dec reg',              'u':'B',        'd':lambda pc,a: "dec r%d" % (a[0]) }, 
 {'s':3, 'name':'list_has_key',         'u':'BB',       'd':lambda pc,a: "list%d->has_key(r%d)" % (a[0],a[1])}, 
 {'s':3, 'name':'list_add_item',        'u':'BB',       'd':lambda pc,a: "list%d->add_item(r%d)" % (a[0],a[1])}, 
 {'s':3, 'name':'mov reg,reg',          'u':'BB',       'd':lambda pc,a: "mov r%d, r%d" % (a[0],a[1]) },
]

def dis(pc = 0x0804C11C, end_pc = 0x0804C1EF):
  while(pc <= end_pc):
    op = Byte(pc)
    add = struct.unpack( opcode[op]['u'], GetMem(pc+1,opcode[op]['s']-1) )
    print "%x: %s" % (pc,opcode[op]['d'](pc,add) )
    pc += opcode[op]['s']
    if( op == 0 ): break
Опкоды 1 и 2 создают по новому экземпляру классов MatrixGraph и PointerToGraph, у меня они называются для простоты matrix и list. Так же есть несколько опкодов, которые вызывают виртуальные функции этих классов.
Запустим наш дизассемблер получим следующий листинг:
804c11c: class_matrix(0x804c084) # 4
804c121: class_list(0x804c118) # 152
804c126: mov r0, 0
804c129: matrix0->vf2_set_val(r0)
804c12c: mov r0, 6
804c12f: mov r3, 0
804c132: dec r3
804c134: mov r1, 0
804c137: mov r2, 5
804c13a: cmp r1,r2
804c13d: jz 0x804c174 (54)
804c140: list1->has_key(r1)
804c143: jz 0x804c16f (43)
804c146: mov r5, 0
804c149: dec r5
804c14b: cmp r5,r3
804c14e: jz 0x804c154 (5)
804c151: jmp 0x804c16c (26)
804c154: matrix0->vf3_set_row(r1)
804c157: matrix0->vf4_set_col(r1)
804c15a: matrix0->vf1_get_val(r4)
804c15d: matrix0->vf4_set_col(r3)
804c160: matrix0->vf3_set_row(r3)
804c163: matrix0->vf1_get_val(r5)
804c166: cmp r4,r5
804c169: jz 0x804c16f (5)
804c16c: mov r3, r1
804c16f: inc r1
804c171: jmp 0x804c13a (65480)
804c174: matrix0->vf3_set_row(r3)
804c177: matrix0->vf4_set_col(r3)
804c17a: matrix0->vf1_get_val(r4)
804c17d: mov r5, 0
804c180: dec r5
804c182: cmp r5,r4
804c185: jz 0x804c191 (11)
804c188: cmp r4,r5
804c18b: jz 0x804c191 (5)
804c18e: jmp 0x804c1db (76)
804c191: list1->add_item(r3)
804c194: mov r1, 0
804c197: mov r2, 5
804c19a: cmp r1,r2
804c19d: jz 0x804c1d2 (52)
804c1a0: matrix0->vf4_set_col(r3)
804c1a3: matrix0->vf3_set_row(r1)
804c1a6: matrix0->vf1_get_val(r2)
804c1a9: matrix0->vf3_set_row(r3)
804c1ac: matrix0->vf1_get_val(r5)
804c1af: matrix0->vf4_set_col(r1)
804c1b2: matrix0->vf3_set_row(r1)
804c1b5: matrix0->vf1_get_val(r4)
804c1b8: add r2,r5
804c1bb: cmp r2,r4
804c1be: jz 0x804c1ca (11)
804c1c1: matrix0->vf4_set_col(r1)
804c1c4: matrix0->vf3_set_row(r1)
804c1c7: matrix0->vf2_set_val(r2)
804c1ca: inc r1
804c1cc: mov r2, 5
804c1cf: jmp 0x804c19a (65482)
804c1d2: dec r0
804c1d4: mov r2, 0
804c1d7: cmp r0,r2
804c1da: jz 0x804c12f (65364)
804c1dd: mov r2, 0
804c1e0: mov r2, 5
804c1e3: matrix0->vf4_set_col(r2)
804c1e6: matrix0->vf3_set_row(r2)
804c1e9: matrix0->vf1_get_val(r0)
804c1ec: print r0
804c1ee: exit
После анализа приблизительный псевдокод будет следующим:
m = class_matrix(0x804c084);
list = class_list(0x804c118)
m[0,0]=0
for(j=0;j<=5;j++){
    r3 = 0xFFFFFFFF;
    for (r1 = 0; r1 <= 5; r1++) {
        if( list1->has_key(r1) ) continue
        if(0xFFFFFFFF <= r3){
            r3 = r1
        }else if(m[r1,r1] > m[r3,r3]){
            r3 = r1
        }
    }

    if( 0xFFFFFFFF > m[r3,r3] && m[r3,r3]>0xFFFFFFFF){
        while (1); //error !?
    }

    list->add_item(r3)

    for (r1; r1<=5; r1++) {
        if( m[r3,r1] + m[r3,r3] <= m[r1,r1] ){
            m[r1,r1] = r2
        }
    }
}

print m[0,0]
exit
Имея подсказку, в виде названия класса MatrixGraph, понимаем что матрица представляет из себя форму хранения графа (см http://en.wikipedia.org/wiki/Adjacency_matrix), а сам алгоритм это поиск кратчайшего пути или алгоритм Дейкстры. Ответ к задаче будет: Dijkstra.

No TrackBacks

TrackBack URL: http://smokedchicken.org/m/mt-tb.cgi/70

About this Entry

This page contains a single entry by snk published on March 18, 2012 9:25 PM.

ructf2012 - Reverse300 $1/\/\PL3 was the previous entry in this blog.

ructf2012 - Unsupported method is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.