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