Binary instrumentation, a technology for analyzing the behavior of binary execution by injecting the instrumentation code, is now used in various regions such as malware analysis, memory error detection, binary vulnerability patch, and so on. Recently, there has been many studies in binary reassemble technique, which is one of the static binary instrumentation reassembles the disassembly code after modifying itself. However, this technology has several fundamental issues: undecidable disassembling issue, and components relocation issue, which could cause the run time errors on reassembled binary. Among them, recent study[9] showed undecidable disassembling[16][18] issue could be resolved through brute force reverse engineering[20], which was previously used only in the malicious code analysis. So recent binary reassembly studies[10][11][27] have tendency to focuse on addressing the component relocation issue, which is the second issue. However, the component relocation issue could not be completely resolved on static instrumentation technology, and is fundamentally an undecidable problem. But previous studies did not clarify the cause of the component relocation on reassembled binary, and its effect on the correctness of binary. This dissertation organizes the detailed criteria that must be met in binary reassembly technology, and shows experimental result about why those criteria are fundamentally contradictory to the underlying premise in binary reassembly technology. And based on result of experiments, we reveal the component relocation issue on binary reassembling is an undecidable problem, and binary reassembly technology has the fundamental limitation.
바이너리 실행을 관찰하고 측정하기 위한 기술인 바이너리 계측(instrumentation)은 악성코드 분석이나 메모리 오류 탐지, 바이너리 취약점 패치 등 다양한 영역에 사용되고 있는 기술이다. 최근에는 정적으로 역어셈블된 바이너리에 코드를 변형한 후 재조립(reassemble)하는 기술이 대두되고 있으나, 역어셈블의 부정확성 문제와 컴포넌트의 재배치 문제로 인해 재조립 바이너리에서 실행 오류가 발생하게 되는 경우가 빈번히 발생한다. 이 중 역어셈블의 부정확성 문제의 경우, 최근의 연구[9]에서는 브루트 포스 역어셈블 기술을 이용하여 이를 해소할 수 있음을 보였는데, 이러한 시도는 과거 악성 코드 분석 영역에서만 사용되던 기술을 확장 적용함으로써 바이너리 재조립 기술 발전 가능성을 보이는 듯 하였다. 이후 최근까지도 바이너리 재조립 연구는 활발히 진행되고 있으며, 이들 연구는 이제 컴포넌트 재배치 문제를 해소하는 것에 초점을 맞추고 이루어지고 있다[10][11][27]. 하지만, 컴포넌트의 재배치 문제는 본질적으로 결정 불가능 문제이며, 정적 계측 기술에서 완전히 해소될 수 없으므로 이러한 연구 방향은 한계를 가진다. 그럼에도 불구하고 과거의 바이너리 재조립 연구[10][11][27]에서는 컴포넌트의 재배치 문제가 발생하는 근본적인 원인에 대한 고찰이 부족하였고, 이것이 바이너리의 실행 정확도에 미치는 영향에 대해 명확하게 규명되지 못하였다. 본 학위논문에서는 바이너리 재조립 기술에서 반드시 부합되어야 할 세부 기준들이 바이너리 재조립 기술에서의 기초 전제와 근본적으로 모순됨을 밝힌다. 그리고 실험과 사례들을 바탕으로, 컴포넌트의 재배치 문제는 결정 불가능 문제이며 바이너리 재조립 기술은 본질적으로 한계를 가지는 기술임을 밝힌다.
