Intel Pin을 이용해서 실행한 프로그램의 trace와 모든 실행된 basic block을 뽑습니다.
그 중 가장 많이 실행된 basic block들을 모아서 실행 순서대로 정리하려고 합니다.
basic block들은 시작 지점이 하나고 끝 지점이 call/jump로 되어 있는 명령어들의 실행 순서로 된 집합입니다.
정렬의 예를 들자면,
입력 파일이 이렇게 되어 있습니다.
=============================
Basic block 1071940: 4255
1071940 CALL 0x1072056
Basic block 1071f6f: 4255
1071f6f PUSHF
1071f70 DEC ECX
1071f71 CMC
1071f72 CALL 0x1071940
Basic block 1072056: 4255
1072056 ADD ECX, 0xc50000
107205c PUSHF
107205d DEC ESI
107205e MOV BYTE [ESP+0xc], 0x7d
1072063 CALL 0x1072bd7
Basic block 107206d: 4255
107206d MOV ECX, [EAX*4+0x1072d59]
1072074 MOV [ESP], CL
1072077 PUSHA
1072078 JMP 0x1071f6f
Basic block 107211a: 4255
107211a ROR AL, 0x3
107211d SAL CL, 0x6
1072120 STC
1072121 BSF ECX, EDI
1072124 SUB BL, AL
1072126 NOT CH
1072128 PUSHF
1072129 CALL 0x1072737
Basic block 1072737: 4255
1072737 MOVZX ECX, DL
107273a MOVZX EAX, AL
107273d CALL 0x107206d
Basic block 1072bd7: 4255
1072bd7 MOV [ESP+0x40], ECX
1072bdb MOV [ESP+0xc], CL
1072bdf PUSH DWORD [ESP+0x40]
1072be3 RET 0x44
Basic block 1072487: 4218
1072487 RCL CH, CL
1072489 MOV AL, [ESI-0x1]
107248c SHL CL, 0x1
107248e AND CH, CL
1072490 SUB AL, BL
1072492 BT CX, SI
1072496 AND CH, AH
1072498 XOR AL, 0xa8
107249a BSWAP ECX
107249c SETA CH
107249f NOT AL
10724a1 BT BX, DI
10724a5 CALL 0x107211a
=============================
출력 파일은 이렇게 되어야 합니다.
=============================
Basic block 1072487: 4218
1072487 RCL CH, CL
1072489 MOV AL, [ESI-0x1]
107248c SHL CL, 0x1
107248e AND CH, CL
1072490 SUB AL, BL
1072492 BT CX, SI
1072496 AND CH, AH
1072498 XOR AL, 0xa8
107249a BSWAP ECX
107249c SETA CH
107249f NOT AL
10724a1 BT BX, DI
10724a5 CALL 0x107211a
Basic block 107211a: 4255
107211a ROR AL, 0x3
107211d SAL CL, 0x6
1072120 STC
1072121 BSF ECX, EDI
1072124 SUB BL, AL
1072126 NOT CH
1072128 PUSHF
1072129 CALL 0x1072737
Basic block 1072737: 4255
1072737 MOVZX ECX, DL
107273a MOVZX EAX, AL
107273d CALL 0x107206d
Basic block 107206d: 4255
107206d MOV ECX, [EAX*4+0x1072d59]
1072074 MOV [ESP], CL
1072077 PUSHA
1072078 JMP 0x1071f6f
Basic block 1071f6f: 4255
1071f6f PUSHF
1071f70 DEC ECX
1071f71 CMC
1071f72 CALL 0x1071940
Basic block 1071940: 4255
1071940 CALL 0x1072056
Basic block 1072056: 4255
1072056 ADD ECX, 0xc50000
107205c PUSHF
107205d DEC ESI
107205e MOV BYTE [ESP+0xc], 0x7d
1072063 CALL 0x1072bd7
Basic block 1072bd7: 4255
1072bd7 MOV [ESP+0x40], ECX
1072bdb MOV [ESP+0xc], CL
1072bdf PUSH DWORD [ESP+0x40]
1072be3 RET 0x44
=============================
즉 basic block의 마지막 명령어에서 call/jump target을 찾아, 실행이 되는 순서대로 나열하려고 합니다.
처음에는 map을 써서 자동 정렬시키려 했는데,
생각해보니 주소가 작은 순서부터 실행되는 게 아니라서 소용이 없네요.
이거 알고리즘을 어떻게 짜야 할까요?
