2016 IEEE Symposium on Security and Privacy Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser, Christopher Kruegel, Giovanni Vigna
개요
angr라는 시스템을 개발하게 된 이유와, 여러 구현 사항들, 그리고 Evaluation을 담고 있는 논문이다.
Importance
Binary Analysis는 매우 중요한 연구 주제이다. Binrary program은 C/C++같이 성능을 중시하는 프로그램, IoT디바이스처럼 Resource를 최대한 절약해야 하는 프로그램, 심지어 Interpreter언어도 성능때문에 Binrary로 컴파일 하는 경우가 많기 때문이다.
하지만 많은 Low-level 언어들은 Security guarantee를 하지 않기 때문에, 많이 취약점들이 있고, 이를 탐지하고 예방하기 위한 방법이 Binrary analysis이기 때문이다.
Motivation
기존의 Binary Analysis는 많은 연구가 진행중이지만, 여러 문제점들이 있었다. 대부분의 연구들이 Reserach prototype만을 만들어서, 정성적인 분석이 불가능하였기 때문이다. 또한 이러한 시스템을 실제로 이용할려고 하여도, 다른 시스템과 함께 이용할 수 있을지도 불분명한 상황이었다.
이 논문은 이 문제를 하나의 Uniform한 Framwork(angr)를 통해서 해결하고자 하는 Motivation을 가져왔다.
Main Idea
angr라는 Static & Dynamic binary analysis를 할 수 있는 프레임워크를 설계하고, DARPA라는 Ground truth를 사용하여, 현재 바이너리 분석의 state of the art를 분석하였다.
Background
프로그램 분석의 Trade-off
Binary Analysis는 다음의 두가지의 목표달성을 위해서 여러 다양한 Trade-off를 가진다.
- Replayability: 특정 모듈파트가 아니라, 전체 시스템에서 버그를 일으키는 Input을 찾아내어 Replay할 수 있는가?
- Semantic Insight: Semantic적으로 프로그램에서 Input의 왜 혹은 어떤 부분이 버그를 일으키게 하였는가 탐색할 수 있는가?
만약 Replayability를 올리게 되면 Coverage가 떨어질 것이다. Semantic insight을 올리게되면, 처리해야 하는 데이터 양이 늘어나고, 둘다 올리게 되면 Scalability에 문제가 생기게 된다.
정적 분석
정적 분석은 Control flow를 추적하는 것과, Data flow를 추적하는 것으로 나눌 수 있다.
- Control flow 분석
- Control flow분석은 프로그램의 실행 경로를 재귀적으로 추적하여 전체 프로그램의 실행 경로를 완성시키는 것을 목적으로 한다. CFG를 Fundamental한 Challenge가 있는데, 바로 Indirect jump이다. Indirect jump는 프로그램의 실행 경로를, Function pointer처럼 메모리나 레지스터의 값을 이용하여 점프하기 때문에, 추적하기 힘들다. 특히 3개의 요소가 Indirect jump에 영향을 미친다; Computed, Context-sensitive, Object-sensitive. Computed는 jump target이 동적으로 정해지는 것을 의미한다. Context-sensitive는 jump가 어디에서 실행되었는지가 영향을 미치는 것을 의미한다. Object-sensitive는 Object-oriented시스템에서 Virtual function처럼 object type에 의존하는 경우를 의미한다. 이론적으로 Sound하며 Complete한 Control flow를 만드는 것은 매우 힘들다. 따라서, 대부분의 연구들을 이 둘중 어딘가에 위치하게 된다.
- Data flow 분석
- 메모리나 레지스터가 가질 수 있는 가능한 값의 집합을 추적하여서, 프로그램의 버그를 추적한다. 이들 프로그램의 특징은 Sound하지만 Complete하지는 않다는 것이다. 예를 들어서, Value-set Analysis라는 것이 있는데, VSA에서는 Program state의 Over-approximation을 찾는 것을 노력한다. 이러한 측정된 Program state는 프로그램이 야기할 수 있는 취약점 탐색에 사용된다.
동적 분석
동적 분석은 크게 Concrete방식과 Symbolic execution으로 분류된다. 이들 프로그램은 high replayable를 가지지만, Semantic insight에 관해서는 연구마다 크게 다르다.
Dynamic Concrete Execution
Dynamic concrete execution은 Pgoram을 직접 Minimally-instrumented된 환경에서 실행시켜 보는 것이다.
- Fuzzing
- Fuzzing은 test case를 만들어서, 버그를 찾아내는 기법이다. Fuzzing은 크게 Coverage-based fuzzing과 Taint-based fuzzing으로 나뉘어 진다. Coverage-based fuzzing에서는 프로그램이 탐색하는 code coverage를 늘려가는 것을 목적으로 Fuzzing한다. 그러나 Coverage-based fuzzing은 Semantic insight을 제공할 수 없다는 문제가 있다. Taint-based fuzzing은 프로그램이 어떻게 Input data를 처리하는지 좀더 깊은 이해를 통해서 (static analysis 기법이 동원되기도 함) Fuzzing을 보다 효율적으로 실행하고, Semantic insight를 제공한다.
- Dynamic Symbolic Execution
- Dynamic symbolic execution은 프로그램을 실행시키되, Abstracted된 도메인에서 실행시킨다. Abstracted된 도메인에서 변수추적을 하기 때문에 매우 큰 정밀도의 Semantic insight를 제공할 수 있다. 그러나 Dynamic symbolic execution은 Path explosion문제에 직면한다. 즉 탐색해야 하는 path가 branch가 나올때마다 기하급수적으로 늘어나는 문제를 겪게된다.
버그의 원인 찾기
버그의 원인을 Triaging(원인을 찾아가는 것)은 보통 Randomness가 발생하는 부분을 통제함으로서 이루어진다. 그러나 보든 부분을 통제할 수 없기때문에 많은 경우 동적 분석들은 Replayability가 떨어지는 경우가 생긴다. 예를 들어서 Fuzzer에서 특정 랜던값이 버그를 일으키는 경우, Fuzzer은 그 랜덤값이 통제된 랜던값이도록 하여서, 나중에 다시 실행시켰을 때, 버그가 안 일어나도록 한다.
Design
Angr는 Cross-architecture support, Cross-platform support, Different analysis paradigms의 구현, Usability를 고려하여 디자인되었다. angr는 파이썬 라이브러리로, 다양한 분석 툴을 제공한다. 이러한 분석툴은 Implementation적인 것으로 논문을 참고.
Conclusion
많은 Engineering가 문헌 분석을 통해서, 현재 존재하는 Binary Analsysi기법을 일목요연하게 그리고 정밀하게 분석한 매우 의미 있는 논문이다. 또한 angr라는 매우 널리 쓰이는 binary anslysis tool에 대한 설명을 담고 있는 논문이다.