이 논문은 역분석을 모듈화된 패스로 구성된 선언적 프레임워크인 'Manifold'를 통해 구현한 '증거 기반 초집합 역컴파일 (PGSD)'을 제안하며, 기존 도구들보다 유연하고 확장 가능한 방식으로 바이너리를 C99 로 변환하여 Ghidra 나 IDA Pro 와 동등하거나 더 나은 품질을 달성함을 보여줍니다.
원저자:Chang Liu, Yihao Sun, Thomas Gilray, Kristopher Micinski
지금까지 우리가 사용하던 역공학 도구들 (IDA Pro, Ghidra 등) 은 마치 거대한 단단한 블록과 같았습니다.
비유: 요리사가 재료를 다듬고, 볶고, 양념하는 모든 과정을 한 번에 해치우는 '올인원' 조리법이라고 상상해 보세요.
문제점: 만약 요리사가 "이 재료를 어떻게 다듬을까?"라고 고민하다가 실수를 하면, 그 실수가 나중에 모든 과정에 영향을 미쳐 요리를 망칠 수 있습니다. 또한, 새로운 재료를 추가하거나 레시피를 바꾸려면 거대한 조리법 전체를 다시 짜야 해서 매우 어렵습니다.
현재의 상황: 기존 도구들은 기계어 코드를 해석할 때, "이게 변수일 거야"라고 일찍 결정해 버립니다. 만약 그 결정이 틀렸다면, 나중에 그걸 고치기 위해 전체를 다시 뒤져야 하거나 아예 포기하게 됩니다.
2. 새로운 방식 (Manifold): "모든 가능성을 열어두는 탐험가"
이 논문에서 제안한 **Manifold(매니폴드)**라는 도구는 완전히 다른 접근법을 사용합니다.
🌲 비유: "숲속의 여러 갈래 길"
기존 도구들이 "이 길로 가면 돼!"라고 하나만 선택했다면, Manifold 는 **"이 길, 저 길, 저기 저 길... 모두 가능성이 있어. 일단 다 가보자!"**라고 말합니다.
모든 가능성 보존: 기계어 코드를 해석할 때, "이게 정수일까? 부동소수점일까?"라고 헷갈리면, 두 가지 모두를 동시에 후보로 남깁니다.
증거 추적 (Provenance): 각 후보가 왜 나왔는지 그 '증거' (어떤 규칙으로 추론했는지) 를 꼼꼼히 기록해 둡니다. 마치 탐험가가 "여기서 왼쪽으로 갔을 때 A 가 나왔고, 오른쪽으로 갔을 때 B 가 나왔다"라고 지도에 다 적어두는 것과 같습니다.
나중에 결정: 모든 길을 다 탐험한 뒤, 가장 논리적이고 오류가 없는 하나의 길을 최종적으로 선택합니다.
3. 어떻게 작동할까? (논리 퍼즐을 맞추듯)
Manifold 는 **논리 프로그래밍 (Datalog)**이라는 기술을 사용합니다.
비유:레고 블록 조립
기계어 코드는 흩어진 레고 조각들입니다.
Manifold 는 이 조각들을 하나씩 조립해 나갑니다.
"이 조각은 A 라는 레고일 수도 있고, B 일 수도 있어"라고 생각하며 두 가지 버전의 조립도를 모두 만들어 둡니다.
나중에 "아, A 버전으로 조립하면 문이 안 열리네? 그럼 B 버전이 맞구나!"라고 오류가 없는 쪽을 골라냅니다.
이 과정에서 **Clang(컴파일러)**이라는 '심판'을 불러와서 "이 코드가 컴파일 (실행) 될 수 있니?"라고 물어보고, 오류가 나는 쪽은 탈락시킵니다.
4. 왜 이것이 중요한가요?
유연함: 새로운 분석 방법을 추가할 때, 거대한 코드를 고칠 필요 없이 새로운 '규칙 (패스)' 하나만 추가하면 됩니다. 마치 레고 세트에 새로운 부품을 추가하는 것처럼 쉽습니다.
정확성: 일찍 결정해서 생기는 실수를 줄여줍니다. 여러 가능성을 비교하며 가장 좋은 답을 찾기 때문에, 기존 도구들보다 컴파일 오류가 훨씬 적게 발생합니다.
범용성: 어떤 컴파일러 (GCC, Clang 등) 로 만들었든, 어떤 최적화 수준이든 상관없이 잘 작동합니다.
5. 결론: "완벽한 해답을 찾기보다, 가능한 모든 답을 모아 최선의 것을 고른다"
이 논문은 역공학 (Reverse Engineering) 을 **"하나의 정답을 찾는 과정"**이 아니라, **"모든 가능한 시나리오를 만들어내고 그중 가장 타당한 것을 선택하는 과정"**으로 바꿉니다.
기존: "이게 맞다!"라고 확신하고 나아가다가, 나중에 "아, 틀렸어!"라고 후회하는 방식.
Manifold: "이게 맞을 수도 있고, 저게 맞을 수도 있어. 일단 두 가지 다 만들어보고, 나중에 가장 깔끔한 것을 고르자!"는 방식.
이 방식 덕분에 보안 연구자나 해커들은 더 정확하고, 더 쉽게, 그리고 더 유연하게 프로그램의 비밀을 파헤칠 수 있게 되었습니다. 마치 어두운 숲속에서 모든 길을 다 찍어둔 지도를 들고 다니는 것과 같습니다.
논문 요약: Superset Decompilation (PGSD 및 Manifold 시스템)
1. 문제 정의 (Problem)
현대 컴파일러 아키텍처는 모듈화된 다중 패스 (multi-pass) 구조와 잘 정의된 중간 표현 (IR) 을 기반으로 발전해 왔으나, 역공학 (Reverse Engineering, RE) 도구들은 여전히 **단일적이고 명령형 (monolithic and imperative)**인 아키텍처에 머물러 있습니다.
모듈성 부재: 기존 디컴파일러 (IDA Pro, Ghidra 등) 는 수만~수백만 줄의 C++/Java 코드로 구성되어 있으며, 제어 흐름 복원, 타입 재구성, 변수 추론 등 핵심 작업들이 단일 가변적 (mutable) 프로그램 표현에 강하게 결합되어 있습니다. 이는 새로운 분석을 추가하거나 기능을 확장할 때 기존 코드를 깊이 파고들어야 하므로 유지보수와 확장이 어렵습니다.
조기 결정 (Premature Commitment) 의 한계: 컴파일은 많은 정보를 잃어버리는 과정이므로, 역방향인 디컴파일은 본질적으로 모호성 (ambiguity) 을 내포합니다. 기존 도구들은 분석 초기에 단일 해석 (interpretation) 으로 결정하여 대안들을 폐기합니다. 이는 분석가가 나중에 필요로 할 수 있는 가설적 해석 (예: 데이터 영역이 실행 코드로 변환된 경우 등) 을 잃게 만들어, 역공학자의 가설 기반 추론 (hypothesis-driven reasoning) 을 방해합니다.
정합성 vs 정밀도의 딜레마: 완전한 정합성 (soundness) 을 보장하려면 형식적 검증이 필요하지만, 실제 상용 컴파일러나 복잡한 ISA(x86-64 등) 에 대한 형식적 명세가 부재하여 이를 달성하기 어렵습니다.
2. 방법론 (Methodology)
저자들은 역공학을 이진 파일의 고수준 설명 공간에서의 구조화된 탐색으로 재정의하고, 이를 해결하기 위해 **선언적 (declarative)**인 접근법을 제안합니다.
PGSD 는 디컴파일을 단일 결과가 아닌, **모든 가능한 고수준 후보 (superset of candidates) 의 숲 (forest)**으로 간주하는 프레임워크입니다.
모노톤 (Monotonic) 사실 저장소: 모든 패스 (pass) 는 공유된 관계 저장소 (relation store) 에 새로운 사실 (facts) 만을 추가하며, 기존 사실을 삭제하거나 무효화하지 않습니다.
출처 추적 (Provenance): 각 추론된 사실에 대해 어떤 규칙과 경로를 통해 도출되었는지에 대한 '출처 (provenance)' 정보를 다항식 (polynomial) 형태로 유지합니다. 이를 통해 모호한 해석을 초기에 제거하지 않고, 병렬 후보로 유지하다가 최종 선택 단계에서 해결합니다.
논리 프로그래밍: Datalog 를 사용하여 분석 규칙을 선언적으로 정의합니다. 이는 복잡한 제어 흐름과 타입 추론을 관계형 연산으로 자연스럽게 표현할 수 있게 합니다.
2.2 Manifold 시스템 구현
PGSD 를 구현한 시스템으로, Linux ELF 바이너리를 C99 코드로 변환합니다.
아키텍처: CompCert 컴파일러의 IR 계층 구조 (x86-64 → Asm → Mach → LTL → RTL → Cminor → Csharpminor → Clight) 를 역방향으로 거슬러 올라가는 나노-패스 (nano-pass) 구조를 사용합니다.
패스 유형:
디컴파일 패스 (Decompile Passes): 하위 IR 에서 상위 IR 로 변환을 수행하며, 모호한 경우 여러 후보를 모두 저장합니다.
분석 패스 (Analysis Passes): 스택 프레임 분석, 타입 추론, 구조체 복원 등 보조 정보를 생성하여 저장소에 추가합니다.
구현 언어: Rust 와 Datalog(Ascent 엔진) 를 결합하여 약 35K 줄의 코드로 구현되었습니다.
후보 선택 (Disambiguation): 최종적으로 Clang 을 '오라클 (oracle)'로 활용하여 생성된 여러 C 코드 후보 중 컴파일 오류가 가장 적은 코드를 선택합니다.
3. 주요 기여 (Key Contributions)
선언적 디컴파일 아키텍처: Datalog 추론 규칙을 사용하여 CompCert 의 특정 컴파일 변환을 역전시키는 개별 나노-패스들을 정의했습니다.
PGSD 프레임워크: IR 을 그래프로 모델링하고, 공유된 모노톤 관계 저장소 위에서 작동하는 분석 패스의 의미론을 형식화했습니다. 이는 모호성을 유지하면서 정합성을 확보하는 새로운 패러다임입니다.
Manifold 시스템: x86-64 ELF 바이너리를 C 코드로 변환하는 실제 시스템 구현 및 평가.
실증적 평가: GNU Coreutils 및 Assemblage 데이터셋을 통해 기존 디컴파일러 (Ghidra, IDA Pro, angr, RetDec) 와 비교 평가했습니다.
4. 실험 결과 (Results)
실험 환경: GNU Coreutils 9.10 (GCC 11.4.0, -O3), 101 개 프로그램, AMD EPYC 서버.
출력 품질 (Output Quality):
함수 복구 (Function Recovery): 모든 툴이 약 0.9 의 정확도를 보였으며, Manifold 는 심볼 테이블 정보를 활용하지 않았음에도 기존 툴들과 유사한 성능을 보였습니다.
타입 및 구조체 정확도: 인자 수 (Argument Count) 정확도는 Manifold 가 0.69 로 기존 툴 (0.94) 보다 낮았으나, 이는 시그니처 라이브러리의 부재 때문입니다. 구조체 복구 (Struct Recovery) 는 모든 툴에서 낮았으나 (Manifold 0.03), Manifold 는 구조적 복원 능력에서 경쟁력을 보였습니다.
코드 유사성 (CodeBLEU): IDA 가 가장 높았으나, Manifold 는 angr 과 유사한 수준 (Coreutils 기준 0.28) 을 보였습니다. 특히 hostid, whoami 와 같이 구조가 단순한 유틸리티에서는 IDA 와 동급의 성능을 냈습니다.
컴파일 오류: Manifold 는 Clang 을 통한 검증 과정에서 가장 적은 수의 컴파일 오류를 발생시켰습니다. 이는 후보 선택 단계에서 Clang 에 의해 검증된 결과입니다.
일반화 및 견고성 (Generalization):
GCC 와 Clang, 다양한 최적화 레벨 (-O0 ~ -O3, -Os) 에서 일관된 성능을 보였습니다. 이는 Manifold 가 특정 컴파일러의 관용구 (idiom) 가 아닌 x86-64 컴파일 과정의 일반적 속성 (스택 규칙, 호출 규약 등) 을 포착했음을 의미합니다.
확장성 (Scalability):
바이너리 크기에 비례하여 실행 시간이 선형적으로 증가했으나, jq 와 같이 복잡한 타입 추론이 필요한 경우 메모리 사용량이 급증했습니다 (최대 50GB). 이는 다중 후보를 유지하는 방식의 본질적 비용이며, 메모리 관리가 주요 병목 현상임을 확인했습니다.
5. 의의 및 결론 (Significance)
아키텍처의 혁신: 역공학 도구를 단일 모놀리식 구조에서 모듈화된 논리 기반 패스 구조로 전환하여 확장성과 유지보수성을 획기적으로 개선했습니다. 새로운 기능 추가가 기존 코드 수정 없이 새로운 패스 작성만으로 가능합니다.
모호성 처리의 패러다임 전환: "정답"을 한 번에 찾으려 하지 않고, 모든 가능한 해석을 출처 정보와 함께 유지하다가 최종적으로 검증하는 방식을 도입하여 역공학자의 탐구적 사고를 지원합니다.
실용적 가치: Manifold 는 기존 상용/오픈소스 툴들과 경쟁 가능한 품질을 유지하면서, 더 적은 컴파일 오류를 생성하고 다양한 컴파일러 환경에서 견고하게 작동함을 입증했습니다.
이 연구는 역공학 도구의 설계에 있어 선언적 프로그래밍과 형식적 방법론의 결합이 어떻게 실용적이고 확장 가능한 솔루션을 만들 수 있는지를 보여주는 중요한 사례입니다.