[PAPER] (State of) The Art of War:Offensive Techniques in Binary Analysis

PAPER

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7546500

 

ABSTRACT

이 논문에서는 여러 분석 기술들을 구현한 바이너리 분석 프레임워크를 제안한다. 제안한 바이너리 분석 프레임워크가 효율적인 바이너리 취약점 분석 기술임을 평가하기 위해 DARPA에서 생성한 데이터셋을 통해 평가한다. 이 프레임워크는 오픈소스이다.

 

1. INTRODUCTION

바이너리 분석의 중요성

1. interpreted 언어도 바이너리 프로그램에 의해 인터프리트 되었거나, JIT(Just-In-Time)으로 바이너리 코드로 컴파일 되었다.
2. OS나 성능이 중요한 애플리케이션은 여전히 바이너리 코드로 컴파일 되는 언어(C, C++ 등)로 작성된다.
3. IoT는 자원이 제약된 기기에 의해 동작한다.

저수준 언어에서의 취약점

• buffer overflow 취약점
• memory corruption 취약점
• 이러한 취약점들로 범용 컴퓨팅 기기뿐만 아니라 스마트락, pacemaker, 자동차 등에서도 원격에서 익스플로잇 가능한 취약점들이 발견되고 있다.
• 컴파일러, 툴체인에서도 버그가 있다.
  • Xcode Ghost: 악성 버전의 Xcode로, 컴파일 타임에 악성 코드를 넣어서 40개가 넘는 유명한 앱들이 감염되었다.

offensive analysis 기술에서 직면한 문제

1. 많은 바이너리 분석 기술들은 연구 프로토타입으로만 존재한다.
   • 연구에 기여했던 많은 노력이 낭비되고, 이후의 연구자들은 이 접근을 기반으로 연구 구현 측면에서 처음부터 다시 시작해야 한다.
2. 많은 연구의 결과는 다시 시스템을 만들어야 하고 대중에게 보여줄 수 없게 되면서 작업은 비실용적이게 된다.

다른 기술과 비교했을 때 바이너리 분석 기술의 적용 가능성은 불분명하게 된다.

현대 운영체제의 복잡성과 정확하고 즉각적으로 애플리케이션의 환경과 상호작용하는 것을 모델링하는 어려움으로 비교를 위한 요인을 만들기 어렵다. 비교할 수 있어도 시스템을 서로 다른 구현 요소와 평가 데이터셋으로 진행하는 경향이 있다.

offensive 분석 기술에서 직면한 문제 해결을 위한 angr 제작

• 글로만 존재해왔던 바이너리 분석 기술들을 통합한 바이너리 분석 프레임워크
  • 시스템화하고 바이너리 분석 기술을 개발
• 정적 그리고 동적 기술을 사용하여 많은 종류의 분석에 대한 뼈대를 제공하여 제안된 연구 접근들을 쉽게 구현할 수 있다.
• DARPA는 바이너리 분석, 취약점 발굴, 익스플로잇 제작, 소프트웨어 패치의 현재 상태를 확인하기 위해 만든 대회인 Cyber Grand Challenge를 만들었고, DARPA는 자동화된 분석 시스템의 실질적인 문제를 제시하고 이러한 문제의 실체(취약점 및 익스플로잇)를 만들기 위한 애플리케이션들을 작성하고 공개하였다. 이 바이너리 데이터셋은 글로만 제안되었던 다양한 분석의 상대적 효과를 측정하는 테스트셋을 제공했다.
• DARPA CGC에서 자동화된 바이너리 분석 시스템을 사용하여 공격하거나 방어를 했다.

논문 목적

• 바이너리 분석 시스템에 공격 기술을 구현하여 공격 기술들의 효과를 이해하는 것

논문 내용

• angr 상세 설명
• 공격 기술들을 사용하여 개발한 offensive 분석들 제안 (글로만 존재해왔던 기술들을 사용한)
• 기술들의 능력을 늘리는데 어떤 어려움이 있었고 어떤걸 향상시켰는지 설명한다.
• 분석 엔진에 기술들을 구현하면서, 분석 엔진에서의 구현 차이에서보다 접근에서의 이론적 차이에서의 효과에서의 차이를 경험할 수 있었다. 이는 DARPA에서 제공한 데이터셋으로 이러한 접근을 평가할 수 있도록 했다.

기여

• 현대 offensive 바이너리 분석 기술의 효과의 이해를 제공하기 위해 기존의 오펜시브 바이너리 분석 접근을 하나의 프레임워크로 재현했다.
• 여러 바이너리 분석 기술을 하나의 큰 규모에 결합하는 어려움과 이러한 어려움을 해결할 방법을 설명한다.
• 바이너리 코드 분석 연구에 사용될 프레임워크인 angr를 오픈 소스화 했다.

 

 

2. AUTOMATED BINARY ANALYSIS

연구자들은 자동화된 바이너리 분석 기술을 몇 년 동안 연구해왔고 이 필드에 많은 발전이 있었지만, 자동화된 바이너리 분석 시스템은 실제로 개발하고 배포하는데 어려움이 있어왔다. 실제 소프트웨어에는 자동화된 분석을 만드는데 기술적 한계가 있기 때문이다.

이 섹션에서는, 자동화된 분석의 어려움과 어떻게 DARPA의 CGC 대회가 서로 다른 분석 접근 방법들을 비교하는데 의미있는걸 제공하는지 설명한다.

 

A. Trade-offs

Replayability

버그는 항상 동일하게 만들어지지 않고, 분석으로 발견한 버그는 재연이 불가능할 수 있다. 애플리케이션 실행 처음부터 어떤게 취약점을 트리거하기 위해 필요한 것인지 찾아봐야 하는 분석이 필요할 때도 있다. 분석 시 버그가 특정 모듈에서 찾을 수 있다는걸 알아도, 해당 모듈을 실행할 방법을 알 수 없다면 크래시를 재연할 수 없게 된다.

재연 가능한 입력을 만드는 분석 기술은 분석하고자 하는 코드에 도달할 방법을 이해해야 한다. 버그에 대한 입력을 트리거할 수 없으면, 이는 false positive가 된다. 즉, 탐지 했던 흐름은 실제 취약점을 나타내지 않는 것이다.

 

Semantic insight

어떤 분석은 의미상 의미있는 방법을 프로그램에서 찾을 능력이 부족할 수 있다.

동적 분석 시 코드를 추적해야 할 수 있는데, 왜 코드가 실행 됐는지나 어떤 입력이 애플리케이션을 그렇게 동작하게 했는지 이해하지 못할 수도 있다. 프로그램의 동작에 대한 입력의 특정 바이트를 알 수 있는 심볼릭 분석이 더 의미있는 이해가 될 수 있다.

분석하는 프로그램에 대한 의미론적인 통찰력을 위해서는 많은 데이터가 필요하다. 의미론적으로 통찰력 있는 동적 분석은 프로그램의 특정 분기를 취하기 위해 유지해야 하는 조건이 있을 수 있다.

재연성과 높은 의미론적 이해를 가지려는 분석은 확장성에 문제가 있을 수 있다. 애플리케이션의 모든 의미있는 정보를 보유하는 것은 모든 가능한 조건 아래에서 프로그램을 실행하는 자원을 처리할 능력이 필요하다. 이러한 분석은 확장성이 없고 다른 모든 잠재적으로 발견 가능한 취약점을 찾을 수 있는 가능성과 그런 정보를 포기해야 한다.

environment model

분석에서 높은 의미론적 이해를 위해서는 애플리케이션의 환경과 상호작용할 수 있어야 하는데, 현대 운영체제는 복잡하다. Linux에는 삼백 개가 넘는 시스템 호출이 있어서 시스템을 완전히 분석하려면 모든 시스템 호출의 영향을 고려해서 설계해야 한다.

 

Example

int main(void){
    char buf[32];
    char *data = read_string();
    unsigned int magic = read_number();
    
    // difficult check for fuzzing
    if(magic == 0x31337987){
        // buffer overflow
10        memcpy(buf, data, 100);
    }
    if(magic < 100 && magic % 15 == 2 && magic % 11 == 6){
				// Only solution if 17; safe
16				memcpy(buf, data, magic);
		}
	
		// symbolic execution will suffer from path explosion
		int count = 0;
		for(int i=0; i < 100; i++){
				if(data[i] == 'Z')
						count++;
		}
		
		if(count >= 8 && count <= 16){
				// buffer overflow
30				memcpy(buf, data, count*20);
		}

		return 0;
}

바이너리 분석의 여러 문제를 보여주기 위해, Listing 1에서 여러 취약점이 존재하는 프로그램 예시를 보여준다.

정적 분석

memcpy() 함수가 세 번 호출되는데, 데이터 양에 따라 정적 분석으로는 모든 세 개의 memcpy() 호출에서 잠재적인 버그라고 할 수도 있는데, 16 라인에서 buffer overflow가 불가능한 정보가 없을 수 있기 때문이다. 또한 정적 분석 시 각 버그 위치에서 버그를 트리거할 입력을 제공할 수 없을 수 있다.

동적 분석

fuzzing과 같은 동적 분석 기술로는 찾은 버그를 트리거할 입력을 만들 수 있는 장점이 있다. 하지만 간단한 fuzzing 기술로는 얕은 버그만 찾거나 필요한 입력을 코드에 주지 못할 수도 있다. 동적 분석으로 라인 10의 버그를 찾기 힘든데, 특정 조건을 만족하는 입력이 필요하기 때문이다. 라인 30의 경우 fuzzing 기술은 랜덤 입력으로 버그를 트리거할 입력을 찾을 수 있다.

Dynamic Symbolic Execution (DSE)

라인 10의 버그를 찾을 수 있는, 많은 가능한 입력을 한 번에 찾을 수 있는 추상 데이터 모델이다.

하지만 동적 심볼릭 기술은 강한 반면 “경로 폭발 문제”(path explosion)가 있다. 경로 폭발 문제는 경로 수가 각 분기마다 기하급수적으로 증가해서 다루기 힘들게 되는 것이다.

심볼릭 실행으로 라인 10과 16의 취약점을 찾을 수 있는데, 라인 30의 취약점은 찾을 수 없을 수도 있다. 라인 30에는 버그를 트리거하지 않는 너무 많은 잠재적인 경로가 존재하기 때문이다.

 

B. The DARPA Cyber Grand Challenge

DARPA Cyber Grand Challenge

2013년 10월, DARPA는 DARPA Cyber Grand Challenge를 발표했다. CGC는 모든 참가자들이 자율적인 프로그램이 되는 경기에서 전세계 팀들이 서로 맞붙는다.

CGC 목적

모든 시스템은 제공한 소프트웨어에서 취약점을 식별하고 익스플로잇하고 패치 해야 한다.

DARPA CGC 샘플 사용 목적

DARPA CGC에서 제공하는 바이너리는 복잡성 범위가 다양한데, 4KB부터 10MB 크기까지 다양하고 구현된 기능이 간단한 에코 서버, 웹 서버부터 이미지 처리라이브러리까지 다양하다. DARPA는 대회에서 사용한 모든 바이너리를 오픈소스로 공개하고 취약점에 대한 PoC 익스플로잇과 write-up도 공개했다.

DARPA CGC 샘플은 간단한 환경 모델이 바이너리 분석 기술을 정확히 구현하고 평가할 수 있어서 이 논문에서 평가 시 데이터셋으로 사용했다.

 

C. Comparative Analysis of CGC Binaries

처리하는 애플리케이션에 따라 서로 다른 오펜시브 바이너리 분석 기술을 사용한다. 예를 들면, 서로 다른 도메인의 데이터를 분석할 수 있고, 애플리케이션의 서로 다른 레벨을 활용할 수 있다.

다음 두 섹션에서는 현재 분석 기술들을 조사했고, 이후 논문 내용으로는 몇 가지 분석을 골라서 깊이있게 평가한다.

 

 

3. BACKGROUND: STATIC VULNERABILITY DISCOVERY

정적 분석 기술

정적 기술은 프로그램을 실행하지 않고 분석하는 것이다.

정적 분석을 프로그램 속성을 그래프로 모델링하는 두 가지 패러다임으로 분류했다.

정적 취약점 식별 기술의 두 가지 단점

1. 결과를 재연할 수 없다.
   • 정적 분석으로 찾은 취약점을 트리거하는 방법에 대한 정보가 복구되지 않으므로 손으로 확인해야 한다.
2. 분석은 단순한 데이터 도메인에서 작동할 수 있어서, semantic insight를 감소시킨다.
   • 취약점 존재에 대해 진술 시 false positive가 높을 수 있다.

 

A. Recovering Control Flow

prerequisite

• node: basic blocks of instructions
• edge: 가능한 control flow

control flow 복원 방법

• 재귀 알고리즘으로 구현
  1. basic block(Ba)을 디스어셈블하고 분석
  2. 가능한 출구를 식별 (연속한 basic block Bb와 Bc)
  3. 추가되지 않았으면 CFG에 추가
  4. Ba와 Bb, Bc 연결
  5. 새로운 출구가 식별되지 않을 때까지 Bb와 Bc에 대해 위 과정 재귀적으로 반복

CFG 복원 시 문제점: indirect jump

간접 점프는 바이너리의 제어 흐름이 레지스터나 메모리 장소로 이동할 때 발생한다.

간접 점프의 타겟은 여러 요인에 의해 다를 수 있다. 간접 점프는 다음의 여러 카테고리로 나눌 수 있다.

Computed

특정 코드에서의 계산으로 애플리케이션에 의해 점프의 타겟이 결정된다. 계산은 레지스터나 메모리에 있는 값에 의존될 수 있다. 이러한 예로는 점프 테이블이 있는데, 애플리케이션은 레지스터나 메모리의 값을 메모리에 저장된 점프 테이블의 인덱스를 알기 위해 사용한다. 인덱스로부터 타겟 주소를 읽고 그 주소로 점프한다.

Context-sensitive

간접 점프는 애플리케이션의 문맥에 따라 이루어질 수 있다. 표준 C 라이브러리의 qsort()를 예로 들 수 있다. qsort() 함수는 전달된 값을 비교하기 위해 callback을 사용하고, qsort() 내 basic block의 점프 타겟은 callback 함수를 제공하는 caller에 따라 결정된다.

Object-sensitive

객체 지향 언어에서, 객체의 다형성은 virtual tables의 함수 포인터로 구현된 가상 함수 사용이 필요하다. 이 함수 포인터는 런타임에 참조되어 점프 타겟을 결정한다. 즉, 함수 caller에 의해 전달된 객체의 타입에 따라 점프 타겟이 결정된다.

CFG 복원의 목적

CFG 생성 위해 가능한 많은 간접 점프의 타겟을 해결하는 것

CFG 복원 분석 두 가지 속성

얼마나 점프 타겟이 잘 해결되었는지에 따라 두 가지 속성이 있다.

Soundness

CFG 복원 기술은 모든 잠재적인 제어 흐름 이동이 생성된 그래프에서 나타날 때 sound하다고 한다. 잠재적인 basic block의 타겟이 빠지게 되면, 타겟으로 하는 block은 CFG 복원 알고리즘에서 볼 수 없고 직접이나 간접 점프에서도 빠지게 된다.

soundness는 바이너리에서 간접 점프 타겟 식별의 true positive 비율로 간주할 수 있다.

Completeness

완전한 CFG 복원은 가능한 제어 흐름 이동을 보여주는 모든 edge를 가지는 CFG를 만든다.

CFG 분석이 completeness 면에서 실수를 하면, 실제로 존재하지 않는 edge를 가질 수 있다. completeness는 간접 점프 타겟 식별의 false positive 비율의 역으로 생각할 수 있다.

 

B. Vulnerability Detection with Flow Modeling

어떤 취약점은 프로그램의 그래프 분석 시 발견할 수도 있다.

Graph-based vlunerability discovery

프로그램 속성 그래프(control-flow graph, data-flow graph, control-dependence graph)는 소프트웨어에서 취약점을 식별하는데 사용할 수 있다. 기술은 control-flow나 data-dependency graph 내 노드들에서 보이는 버그의 모델을 만들고 애플리케이션에서 이 모델을 식별하는데 의존한다. 이 기술은 취약한 소스 코드의 복사본을 찾는데 맞춰져 있어서 이미 존재하는 취약점에 대한 지식을 활용할 수 있다. 하지만, 이 논문에서는 완전히 새로운 취약점을 찾는데 집중했다.

 

C. Vulnerability Detection with Data Modeling

Value-Set Analysis

정적 분석 접근 중 하나로 Value-Set 분석(VSA)이 있다. VSA는 프로그램의 특정 지점에서 프로그램 상태(메모리나 레지스터의 값)의 초과 근사치를 식별한다. 이는 간접 점프나 가능한 메모리 write 연산의 타겟에 대한 가능한 타겟을 이해하는데 사용할 수 있다.

읽고 쓰는 메모리 접근 패턴을 분석해서 변수와 버퍼 장소를 바이너리에서 식별할 수 있다. 이후 복원된 변수와 버퍼 장소는 overlapping 버퍼를 찾는데 분석될 수 있고, overlapping 버퍼는 buffer overflow 취약점의 원인이 될 수 있다.

 

 

4. BACKGROUND: DYNAMIC VULNERABILITY DISCOVERY

동적 분석

특정 입력에서 동작에 대한 프로그램 실행을 검사하는 분석이다.

동적 기술은 concrete execution과 symbolic execution으로 분류할 수 있다. 이 기술들은 입력이 높은 재연 가능성이 있지만 의미론적 통찰력 측면에서는 다양하다.

 

A. Dynamic Concrete Execution

동적 concrete execution은 최소화된 instrument된 환경에서 프로그램을 실행하는 개념이다.

이 분석은 하나의 경로 레벨에 대해 특정 입력을 주었을 때 프로그램 내 어떤 경로가 되는지에 대해 알아보는 것이다. 따라서 동적 concrete execution에는 사용자에 의한 테스트 케이스가 필요하다.

1) Fuzzing

fuzzing은 취약점을 찾기 위한 dynamic concrete execution 방법 중 하나로, 크래시를 트리거하기 위해 여러 형태의 입력을 주는 동적 기술이다.

input

입력은 하드코딩된 규칙으로 생성되며, 특정 입력으로 애플리케이션에 크래시가 발생하면 해당 입력은 버그를 트리거한 것으로 간주된다. 다른 방법으로는 입력을 랜덤하게 변형하며 생성할 수 있다.

test case

fuzzer는 교묘하게 조작된 테스트 케이스가 없으면, fuzzer는 프로그램의 깊이 없는 기능을 제외하고는 아무것도 훈련하지 못하게 된다.

Coverage-based fuzzing

code-coverage-based fuzzer는 코드가 많이 실행될수록, 취약한 코드를 실행할 기회가 더 높다는 통찰력을 기반으로 하고 있다. 따라서 실행되는 코드 양을 최대화하는 입력을 만드는 것이 목표이다.

American Fuzzy Lop(AFL)는 code coverage 매트릭을 원칙으로 하고 있고, 이 fuzzer로 많은 취약점들을 발견해왔다.

coverage-based fuzzing은 타겟 애플리케이션에 대한 의미론적인 통찰력이 부족한 단점이 있는데, 이는 아직 실행하지 않은 코드를 탐지할수는 있어도 어떤 입력이 해당 코드를 실행했는지에 대한 이해는 없음을 의미한다.

Taint-based fuzzing

taint-based fuzzer는 장래의 실행에서 입력의 어떤 부분을 변형해야 하는지 이해하기 위해 애플리케이션이 어떻게 입력을 처리하는지 분석하는 것이다. 정적 기술에 데이터 기반 복원과 같은 taint 추적을 결합하기도 한다.

taint-based fuzzer는 프로그램 내 주어진 경로에서 입력의 어떤 부분이 변형되어야 하는지에 대한 이해는 있지만, 입력을 어떻게 변형해야 하는지는 알지 못한다.

2) Dynamic Symbolic Execution

symbolic 기술은 정적 분석과 동적 분석 사이 갭을 연결하고 fuzzing에서의 제한된 의미론적 통찰력을 해결하는 방법을 제공한다.

dynamic symbolic execution은 에뮬레이트된 환경에서 프로그램을 실행하는데 사용하는 동적 기술이다. 이러한 시스템은 애플리케이션을 에뮬레이트할 때, 프로그램 실행 동안의 레지스터와 메모리 상태와 변수의 제약을 추적한다. 조건 분기에 도달하면, 실행은 나뉘어 두 경로를 따라가면서 분기가 사용한 경로의 제약조건을 분기조건으로 저장하고 분기가 사용하지 않은 경로의 제약조건을 분기 조건의 역으로 저장한다.

high semantic insight

높은 의미론적 통찰력을 갖는 기술은 실행 중인 경로에서 조건이 발생했을 때 애플리케이션에 적절한 입력을 만들기 위한 경로 제약을 사용함으로써 어떻게 특정 프로그램의 상태를 트리거할 수 있는지 알 수 있다.

Classical dynamic symbolic execution

dynamic symbolic execution은 소프트웨어의 취약점을 찾는데 바로 사용할 수 있다.

초기에는 소스 코드를 테스트하는데 사용되었다. 이후 바이너리 코드에 사용되었는데, Mayhem과 S2E를 사용해서 취약한 상태(ex. 공격자 입력에 의한 instruction pointer overwrite)가 식별될 때까지 경로 탐색을 수행한다.

trade-off: path explosion 문제

path explosion 문제 때문에 제한된 확장성을 갖는다. 새로운 경로는 매 분기마다 생성되므로 프로그램 내 경로 수가 기하 급수적으로 증가하게 된다.

prioritizing promising path

유망한 경로에 우선순위를 매겨서 path explosion 문제를 해결할 수도 있는데, 이 path explosion 문제를 완전히 극복하지 못했고 이러한 방식을 사용하는 시스템에서 버그가 적게 발견됐다.

Symbolic-assisted fuzzing

path explosion 문제를 해결하기 제안된 방법으로 symbolic execution에 fuzzing을 결합한 symbolically-guided fuzzer를 사용한다. 이 fuzzer는 dynamic symbolic execution 엔진에서 입력을 처리하며 fuzzing 구성요소에서 식별된 입력을 변경해간다. dynamic symbolic execution은 이전에 탐색하지 않은 코드를 트리거하고 fuzzing 요소가 계속 code coverage를 할 수 있도록 하는 추가적인 테스트 케이스를 제공하면서 적절하게 입력을 변형하기 위해 프로그램에 대한 심층적인 이해가 있다.

Under-constrained symbolic execution

애플리케이션의 일부분만 실행해서 dynamic symbolic execution의 용이성을 높일 수 있다. 잠재적인 버그를 찾는데는 효과적이나, 두 가지 단점이 있다. 애플리케이션에서 실행하는 부분에 대한 문맥 적절성을 보장할 수 없고, 확장성 면에서 탐지한 버그를 재연 가능성을 포기해야 한다.

 

 

5. BACKGROUND: EXPLOITATION

취약점 발견 분석은 실질적으로 크래시를 발생시키는 입력을 찾는 것이다.

이 섹션에서는 식별한 크래시를 재연하는 과정과, 크래시 영향을 입증하기 위해 자동으로 익스플로잇을 생성하는 방법, 그리고 현대 예방 기술에서 익스플로잇을 굳건하게 하는 방법에 대해 다룬다.

A. Crash Reproduction

대부분 fuzzer에서 실행을 de-randomization하는 이유

대부분의 fuzzing 접근법에는 두 개의 애플리케이션 인스턴스에 제공된 동일한 입력은 동일한 결과를 만들 것이라는 추정이 있다. 하지만 분석 환경을 벗어났을 때는 발견된 크래시가 재연 불가능할 수 있다. 랜던화되지 않는 분석 환경에서는 크래시를 발생시킨 입력은 항상 동일한 경로에 들어가서 크래시를 발생시킬 것인데, 분석 환경을 벗어나면 항상 어떤 토큰 값은 달라질 것이고 크래시를 발생시켰던 입력은 크래시가 발생하지 않는 경로에 들어갈 수 있다.

unreplayable crashing input

Missing Data

취약점 탐지 기술에서는 애플리케이션에서 처음 받는 값이 아니면 올바른 응답값을 추정하도록 되어있다. 따라서 랜덤화되지 않는 환경에서는 fuzzer와 같은 분석 엔진은 프로그램에서 검색하기 전에 토큰과 같은 값들을 짐작하는데, 분석 환경 밖에서는 토큰 값이 매칭되지 않게 되고 이에 따라 크래시가 발생하지 않는다.

분석 환경 밖에서는 크래시를 발생시킨 입력이 크래시를 재연할 수 없게 되고, 새로운 크래시를 발생시키는 입력을 찾을 수도 있다. 관련하여 data leak 식별에 대한 분석이 존재하는데, angr에는 구현하지 않았다.

Missing relationships

낮은 의미론적 통찰력을 가지는 fuzzing과 같은 기술은 프로그램에서 검색한 데이터와 이후의 데이터 사이의 관계를 복원할 수 없다.

예를 들면, 사용자가 제공한 토큰 값이 이후에 크래시를 발생시키는데 사용되더라도, 사용자가 제공한 토큰값과 사용자가 크래시를 발생시키기 위해 제공해야 하는 토큰값 사이에 관계를 알지 못한다.

input specification은 애플리케이션에 제공받은 데이터와 나중에 제공된 데이터 사이 관계를 정의할 수 있는데, 이러한 접근법은 Replayer이다. Replayer는 분석 환경에서의 프로그램 경로를 리얼월드에서는 어떤 프로그램 경로로 줘야 하는지 계산하는 것이다.

 

B. Exploit Generation

모든 크래시가 익스플로잇 가능한 것은 아니다.

익스플로잇 가능한 크래시를 이해하는건 버그 분류에 도움이 된다.

 

C. Exploit Hardening

실행 불가능한 스택 영역과 Address Space Layout Randomization(ASLR)과 같은 보호기법으로 전통적인 익스플로잇이 불가능하게 되었다.

현재 자동화된 익스플로잇 기술은 현대 방어 기술이 적용되기 전에 설계되었기 때문에 현대 소프트웨어에는 그러한 익스플로잇 기술이 실용적이지 않게 되었다. 따라서 이러한 방어 기법을 우회하는 익스플로잇들이 만들어졌는데, 예를 들면 전통적인 shellcode 기반 익스플로잇을 Return-Oriented Programming(ROP) 익스플로잇으로 우회할 수 있다.

 

6. ANALYSIS ENGINE

A. Design Goals

Cross-architecture support

임베디드 기기의 증가로, ARM, MIPS 등 여러 하드웨어 아키텍처와, 32bit뿐만 64bit 아키텍처 바이너리를 지원해야 한다.

Cross-platform support

현대 분석 시스템은 서로 다른 운영체제를 사용하는 소프트웨어를 지원해야 한다. 따라서 운영체제는 추상화되어 서로 다른 실행 포맷을 로딩하도록 지원해야 한다.

Support for different analysis paradigms

유용한 분석 엔진은 넓은 범위의 분석을 지원해야 한다. 이를 위해서는 엔진을 추상화해서 서로 다른 메모리 모델뿐만 아니라 서로 다른 데이터도 제공해야 한다.

Usability

angr의 목적은 바이너리 분석 기술을 유용하게 재현하고, 향상시키고, 그리고 만드는 도구를 제공하는 것이다. 따라서 angr의 learning curve를 낮게, 사용성을 높게 유지하려고 노력했다.

angr는 Python으로만 구현했는데, Python은 상수 시간의 낮은 성능을 보인다. 언어 오버헤드가 중요해지면 angr는 Python JIT engine인 PyPy를 돌려서 속도를 높일 수 있다.

angr 목표

바이너리 분석 기술의 재현

 

B. Submodule: Intermediate Representation

PyVEX: cross architecture 지원

여러 아키텍처를 지원하기 위해, 아키텍처 기반 네이티브 바이너리 코드를 intermediate representation(IR, 컴파일러나 가상머신에서 소스코드를 표현하는데 사용하는 데이터 구조 또는 코드)로 바꾼다. IR lifter를 직접 만들지 않고, libVEX를 차용했다. libVEX는 VEX라는 IR를 만드는데, Firmalice를 위해 만들어진 PyVEX를 사용했다. PyVEX는 VEX IR를 Python에 binding시킬 수 있다. VEX를 사용해서 32bit, 64bit 버전의 ARM, MIPS, PPC, x86 프로세서를 지원할 수 있다.

 

C. Submodule: Binary Loading

CLE: 바이너리를 시스템에 로딩

• CLE 모듈은 프로그램 상태 초기화, 재배치, 동적 심볼 구하기, 그리고 주어진 바이너리와 라이브러리 로딩을 처리하기 위해 서로 다른 바이너리 포맷을 추상화한다.
• CLE는 POSIX를 준수하는 시스템(Linux, FreeBSD 등), Windows, (DARPA CGC에서 만든)DECREE OS 바이너리들을 지원한다.
• CLE는 많은 바이너리 객체에 대한 기본 클래스(애플리케이션 바이너리, POSIX .so, Windows .dll)들, 객체의 세그먼트와 섹션, 섹션 내 심볼들을 제공하여 binary loader로써 확장된 인터페이스를 제공한다.
• 파일 포맷 파싱 라이브러리 사용(elftools, pefile)하여 객체를 파싱하고, 로드된 애플리케이션의 메모리 이미지가 인식할 수 있도록 재배치한다.

 

D. Submodule: Program State Representation/Modification

SimuVEX: 프로그램 상태 표현

• SimuVEX 모듈은 프로그램 상태(레지스터와 메모리에 대한 값, 열린 파일 등)를 표현한다.
• SimuVEX는 VEX IR의 symbolic engine이다.
• SimState: state가 생성되었을 때 사용자나 분석에 의해 구체화되는 state options에 의해 제어되는 state plugins의 집합으로 state가 표현된다.

Registers

• SimuVEX는 프로그램 특정 지점에서의 레지스터 값을 추적한다.

Symbolic memory

• symbolic execution을 제공하기 위해, SimuVEX는 state plugin으로 symbolic memory model을 제공한다.

Abstract memory

메모리를 모델링하기 위한 정적 분석 시 추상화된 메모리 상태 플러그인이 사용된다.

POSIX

• POSIX를 준수하는 시스템 분석 시, SimuVEX는 POSIX 상태 플러그인에서 시스템 상태를 추적한다.
• 예를 들면, 파일이 symbolic 상태로 열렸을 때 각 파일은 memory 지역과 symbolic 위치 인덱스로 나타낼 수 있다.

Log

• SimuVEX는 log 플러그인에 각 상태마다 (메모리 쓰기, 파일 읽기 등) 로깅을 추적한다.

Inspection

• SimuVEX는 디버깅 인터페이스 제공한다.
• breakpoint, taint, symbolic condition 제공
• SimuVEX의 행위를 바꿀 수 있음

Solver

• Claripy라는 data model provider를 통해 서로 다른 데이터 영역에 인터페이스를 노출하기 위한 플러그인
• 플러그인에 symbolic 모드를 설정하면 데이터를 심볼릭하게 레지스터, 메모리, 파일을 해석한다.

Architecture

• 분석에 유용한 아키텍처 관련 정보를 제공한다. (stack pointer이름, 아키텍처의 word 크기 등)
• archinfo 모듈에서 가져온 정보를 제공

프로그램 상태 변경

시스템 호출은 Python 함수 형태로 구현되어, Python 함수를 사용하여 프로그램 상태를 변경하는 등을 할 수 있다.

Python 함수인 SimRun은 현재 실행 상태를 나타낸다.

 

E. Submodule: Data Model

Claripy: expression 추상화

• SimState: 레지스터와 메모리에 저장된 값
• SimState는 Claripy 모듈의 추상화로 나타낼 수 있다.

expression tree

• expression에서 값을 leaf 노드로, 연산자를 non-leaf 노드로 표현한다.
• 예) x + 5 표현이 있을 때 x와 5의 링크와 인자값을 유지하여 expression tree 형태로 x+5 표현을 나타낸다.

Claripy backend

• concreate domain(정수, 부동소수점 수), symbolic domain(Z3 SMT solver에 의한 symbolic 정수, symbolic 부동소수점 수), value-set abstract domain(value set 분석 시 사용)
• 표현들은 claripy backend가 제공하는 data domain으로 해석된다.

Claripy frontend

• FullFrontend: symbolic solving을 사용자에게 노출시키고, 제약을 추적하고 Z3 backend를 사용하여 문제를 해결한 후 결과를 캐싱한다.
• CompositeFrontend: 제약을 독립적인 집합으로 나누는 것은 solver에 로드되는 것을 줄일 수 있다. 이 frontend는 이러한 기능을 제공하는 인터페이스이다.
• LightFrontend: VSA backend를 사용해서 VSA domain에 표현을 해석하는데 사용, 제약 추적 X
• ReplacementFrontend: LightFrontend에 VSA 값에 제약 지원을 추가하여 확장한 것.
  • x + 1 < 10와 같은 constraint가 있을 때, ReplacementFrontend는 0 ≤ x ≤ 8과 같이 변수 범위를 식별한다. 이후 주어진 범위 내에서 VSA가 만들 수 있는 변수 x의 더 정확히 가능한 값을 구한다.
• HybridFrontend: FullFrontend와 ReplacementFrontend 결합하여 symbolic constraint 해결을 위해 빠르게 근사치를 제공한다. angr는 공식적으로 이 능력이 가능한 첫 번쩨 도구이다.

 

F. Submodule: Full-Program Analysis

Project

• 바이너리를 관련된 라이브러리와 함께 나타낸 객체
• 이 객체를 통해 모든 서브 모듈이 제공하는 기능을 사용할 수 있다. (상태 생성, 공유 객체 검사, 바이너리 코드 후킹 등)

PathGroup: Path Groups

• dynamic symbolic execution 인터페이스
• 경로가 나뉘고 병합될 때마다의 경로 계층성을 추적하며 어떤 경로가 유망하며 어떤 경로를 제거해야 하는지 이해할 수 있다.

Analysis: Analyses

• 전체 프로그램 분석 추상화 제공
• 정적 분석의 control-flow graph 복원 등과 같은 lifecycle을 관리하고 동적 분석 관리

 

G. Open-Source Release

미래의 바이너리 분석의 근간을 제공하기 위해 angr을 오픈소스로 배포했다.

제공 기능

• 분석 엔진 모듈
• control-flow graph 복원
• 정적 분석 프레임워크
• 동적 symbolic execution 엔진
• 제약받지 않는 symbolic execution 구현

 

반응형

7. IMPLEMENTATION: CFG RECOVERY

이 섹션에서는 angr에서 CFG 복원 방법을 설명한다.

CFG 복원

angr는 프로그램의 entry point부터 최적화 부분까지 CFG 복원을 수행한다.

forced execution, backward slicing, symbolic execution을 활용하여 모든 간접 점프의 점프 타겟까지 CFG을 복원한다.

CFG 복원 알고리즘 단점

1. 느리다.
2. 자동으로 dead code를 처리하지 않는다.
3. miss code가 있을 수 있다. → 복원되지 않은 간접 점프에서만 도달 가능한 코드와 같은

CFG 복원 알고리즘 보완: 2차 알고리즘 사용

• CFG 복원 알고리즘의 3가지 단점을 보완하기 위해, 빠른 바이너리 디스어셈블리를 사용하는 알고리즘을 만들었다.
• 이 알고리즘은 함수, intra-function 제어 흐름, 직접 inter-function 제어 흐름을 식별하기 위해 휴리스틱에 의한 알고리즘
• 단점
  • CFG 복원 알고리즘보다 정확도가 훨씬 떨어진다.
  • 함수 도달성에 대한 정보가 부족
  • 문맥 인식(context-sensitive)이 아님
  • 복잡한 간접 점프를 복원할 수 없음

이 섹션에서는 발전된 CFG 복원 알고리즘인 CFGAccurate를 소개하고, 더 빠른 알고리즘인 CFGFast를 설명한다.

 

A. Assumptions

CFGAccurate에서 알고리즘 실행 시간 최적화 위한 가정들

1. 프로그램 내 모든 코드는 서로 다른 함수로 분리가 가능하다.
2. 모든 함수는 명시적 호출 명령어에 의해 호출될 수 있거나 tail jump에 의해 처리될 수 있다.
   • tail jump는 재귀 함수에서 스택 공간을 줄이기 위한 최적화로, 마지막 함수 호출이 jump로 바뀌어서 새로 호출되는 함수는 caller의 리턴 주소를 재사용한다.
3. 각 함수의 stack cleanup은 함수가 어디에서 호출 되었던 예측 가능하다. 이는 CFGAccurate가 이미 분석된 함수를 스킵할 수 있도록 한다.

난독화되었거나 일반적이지 않은 바이너리의 경우 이러한 가정을 제거할 수는 있지만 CFG 복원 실행 시간을 늘릴 수 있다.

CFG 복원하기 위한 근본적인 부분

1. 모든 함수는 call-site(함수가 호출된 코드) 이후 명령어에 리턴된다.
2. 간접 분기의 점프 타겟은 항상 control flow graph에 의해 결정된다. (프로그램 상태나 문맥이 아닌)
3. 간접 점프의 점프 타겟에 대한 expression은 관용구 집합에 매칭되어야 한다.
4. stack pointer는 리턴된 후 함수에 진입하기 전까지 동일하다.
5. 어떠한 두 함수도 overlap 될 수 없다. 즉, 함수는 basic block을 공유할 수 없다. CFGAccurate가 코드를 공유하는 함수를 처리한다.
6. symbol table이나 재배치 정보와 같은 추가 정보를 사용할 수 있다.

 

B. Iterative CFG Generation

• CFGAccurate는 CFG 생성에 사용하는 4가지 기술
  • forced execution
  • backward slicing
  • symbolic execution
  • value set analysis
• CFG는 애플리케이션의 entry point의 basic block에서 초기화된다.
• 간접 점프 리스트: 아직 해결되지 않은 점프 타겟을 리스트에 저장한다. 처리해야 할 점프가 식별되면 간접 점프 리스트에 추가된다.
• 모든 기술을 사용한 결과 간접 점프 리스트나 CFG에 변화가 없으면 CFGAccurate는 종료된다.

 

C. Forced Execution

• Forced Execution은 매 분기점에서의 실행될 두 조건 분기의 방향을 보장한다.
• CFGAccurate는 basic block의 work list와 분석된 블록 리스트를 가진다.
• 분석이 시작되면, work list를 CFG 내 모든 basic block으로 초기화한다.
• CFGAccurate가 work list 내 basic block을 분석한 후, CFG에 해당 basic block과 블록에 대한 직접 점프를 추가한다.
• forced execution은 예측할 수 없는 순서로 코드를 실행하기 때문에 실제로 프로그램을 실행할 때와 간접 점프의 타겟이 다를 수 있어서 이 과정에서 간접 점프는 처리할 수 없다. 간접 점프들은 나중에 분석하기 위해 간접 점프 리스트에 넣어 놓는다.

 

D. Symbolic Execution

• forced execution 과정에서는 간접 점프를 처리할 수 없어 간접 점프들이 처리되지 않고 간접 점프 리스트에 들어있다.
• 간접 점프 리스트에 있는 간접 점프마다 CFGAccurate는 CFG를 첫 번째 merge point를 만날 때까지 또는 순회하는 블록 수의 한계점까지 뒤에서부터 순회한다.
• 해당 지점에서 간접 점프에 대해 symbolic execution을 수행하고 간접 점프의 타겟으로 가능한 값을 구하는데 constraint solver를 사용한다.
• 만약 한계치 크기보다 계산한 가능한 타겟 집합이 더 작으면 성공적으로 수행된 것으로 간주하고, 점프 처리가 성공적으로 끝나면 해당 점프는 간접 점프 리스트에서 제거되고 해당 점프 타겟 값을 위한 edge와 node를 CFG에 추가한다.

 

E. Backward Slicing

• 문맥(context) 부족으로 forced execution과 symbolic execution은 대부분의 점프를 처리하지 못한다.
  • 함수가 인자로 pointer를 넘기면 해당 pointer는 간접 점프 타겟으로 사용되는데, 이 분석들은 이 pointer를 처리하지 못한다.
• backward slicing으로 context-sensitive 요소를 사용해서 더 완성도 있는 CFG를 만든다.
• program slice: program statement의 부분집합
• CFGAccurate는 처리되지 않는 점프부터 시작해서 backward slice를 계산한다. slice는 이전 call context 시작으로부터 확장된다. 즉, 어떤 간접 점프가 함수 Fb와 Fc에서 모두 호출되는 함수 Fa에서 분석되면, slice는 backward를 점프가 있는 함수 Fa 에서 두 함수 Fb와 Fc의 시작노드로 확장한다.
• CFGAccurate는 angr의 symbolic execution engine을 사용해서 slice를 실행하고, constraint engine을 사용해서 가능한 symbolic 점프의 타겟을 식별한다. (모두 점프 타겟 집합을 구하기 위한 threshold 사이즈를 256으로 사용)
• 점프 타겟이 성공적으로 구해지면, 해당 점프는 간접 점프 리스트에서 제거되고 edge와 basic block을 CFG에 추가한다.

 

F. CFGFast

빠른 CFG 복원 알고리즘의 목표

• 높은 code coverage를 갖는 그래프를 생성하는 것

이 알고리즘은 control flow가 부족한 그래프라 완전하지 않지만, manual과 자동화된 바이너리 분석에 유용하다.

Function identification

• 애플리케이션 내 함수를 식별하기 위해 하드코딩된 함수 프롤로그 시그니처를 사용한다.
• 애플리케이션이 함수 위치를 알 수 있는 심볼을 포함하면, 이 심볼은 그래프의 함수 시작 위치로 사용될 가능성이 있다.
• entry point를 나타내는 basic block도 그래프에 추가된다.

Recursive disassembly

• 식별한 함수에서 직접 점프를 복원하는데 사용

Indirect jump resolution

• CFGFast에는 점프 테이블 식별과 간접 호출 타겟 처리를 위한 방법을 포함한다.

 

G. Using the CFG Recovery

angr의 CFG recovery 알고리즘

1. CFGFast
2. CFGAccurate

 

 

8. IMPLEMENTATION: VALUE SET ANALYSIS

Value Set Analysis(VSA)

• Value-Set 분석은 바이너리 프로그램을 위한 수치적 분석과 포인터 분석을 결합한 정적 분석 기술이다.
• Value-Set Abstract domain이라는 추상 domain을 사용하여, 각 프로그램 지점에서 레지스터나 추상 장소에서 가질 수 있는 가능한 값을 계산한다.
• VSA는 함수의 모든 프로그램에 대한 fix-point를 도달할 때까지 프로그램을 분석한다. 메모리 쓰기를 주소 A에 수행한다면, 계산된 fix-point에서 A 값은 모든 가능한 쓰기 타겟 리스트를 가지고 있다.
• Balakrishnan et al에서 제안된 원래 VSA 디자인의 경우 리얼월드 바이너리 대상으로는 잘 되지 않는다. 리얼월드 바이너리에서 VSA가 동작하도록 하고 분석의 정확도를 높이기 위해 많이 개선했다.

별도의 strided-interval 집합 생성

VSA 데이터 타입인 strided interval은 concrete 값 집합을 근사하는데 적합하지만, 이러한 값은 프로그램 내 점프 타겟으로 사용되어 strided-interval의 과대 근사치는 복원된 CFG에서 soundness 하지 않을 수 있다. 이를 해결하기 위해 새로운 데이터 타입인 strided interval 집합을 만들었다. strided interval 집합은 조합되지 않는 strided interval의 집합인데, 한계치인 K보다 많은 원소를 가질 때 strided interval 집합은 조합될 수 있다. 한계치는 semantic 통찰력과 확장성의 균형을 제어할 수 있다. (높은 K는 높은 정확도를 갖지만, 분석 복잡도 비용이 높아진다.)

대수 solver를 path predicates에 적용

분기 조건 추적은 조건문 종료나 합병 과정 시 변수를 제약할 수 있어 보다 정확한 분석 결과를 얻을 수 있다. Affine-Relation 분석은 분기 조건 추적 기술로 제안되었지만, 모두 구현이 복잡했고 실제로는 계산 비용이 크다.

따라서 strided interval domain에 적용될 수 있는 경량의 대수 solver를 구현했다. 새로운 경로가 보이면, 변수의 수 범위를 얻기 위해 단순화하고 계산을 한다. 이후 새로 생성된 수 범위와 원리 값을 교차해서 새로운 분기 조건을 만났을 때 fix-point의 정확도를 높일 수 있도록 했다.

signedness-agnostic domain 사용

원래는 모든 값이 부호가 있음을 가정하고 부호있는 strided interval에 VSA가 수행된다. 하지만 이는 부호없는 산술 계산 시 과대 근사치를 가져오게 된다. 점프 주소가 부호없는 수이기 때문에 점프 주소 계산은 부호없는 값으로 진행되어 이 과대 근사치는 더 문제가 된다.

이를 해결하기 위해 signedness-agnostic domain을 사용하는 것이다. wrapped interval analysis는 LLVM 코드 분석 위한 interval domain으로 signed와 unsigned 수를 동시에 처리한다.

memory corruption 탐지 위한 VSA의 사용

1. VSA로 프로그램 내 모든 읽기와 쓰기 접근 패턴을 수집한다.이 과정에서, 스택과 힙 영역의 변수 복원을 진행한다.
2. 비정상적인 버퍼(overlapping buffer, out-of-bound buffer)를 찾기 위해 스택과 힙 영역을 스캔한다.
3. 모든 비정상적 버퍼를 잠재적인 memory corruption으로 알린다.

 

A. Using VSA

VSA 분석을 위해 angr는 Value Flow Graph라는 인터페이스를 제공한다.

VFG는 각 프로그램 지점에서의 VSA fix-point를 나타내는 프로그램 상태를 포함한느 CFG를 발전시킨 그래프이다.

VFG에 전달된 파라미터에 따라 하나의 함수만 포함할 수도 있고 함수 호출 트리나 전체 프로그램을 포함할 수 있다.

VFG program state

VFG의 프로그램 상태는 SimuVEX가 제공하는 추상화된 메모리를 나타낸다. 메모리에서 값은 Claripy가 제공하는 value-set 형태로 되어있다.

 

 

9. IMPLEMENTATION: DYNAMIC SYMBOLIC EXECUTION

동적 심볼릭 실행 모듈은 Mayhem 기술 기반으로 만들어졌다. 경로 우선순위 기술과 동일한 메모리 모델을 사용한다.

동적 심볼릭 실행 모듈은 angr의 주요 기능 중 하나로,Veritesting이나 under-constrained symbolic execution 분석은 이 모듈을 기반으로 이루어진다.

SimuVEX가 제공하는 심볼릭 메모리 모델을 놓기 위해 Z3에 Claripy 인터페이스를 사용한다. 각각의 실행 경로는 Path 객체에 의해 관리되며 Path 객체는 경로, path predicate, 경로 관련 정보에 대한 행위를 추적한다. 경로 그룹은 PathGroup 기능에 의해 관리된다. PathGroup은 dynamic symbolic execution 과정에서 경로의 분할, 합병, 필터링을 관리하는 인터페이스를 제공한다.

Veritesting을 Veritesting 분석으로 지원한다.

 

 

10. IMPLEMENTATION: UNDER_CONSTRAINED SYMBOLIC EXECUTION

UC-KLEE에서 제안된 under-constrained symbolic execution을 구현했으며 UC-angr 라 부른다.

• under-constrained symbolic execution
• symbolic execution 기술은 프로그램에 모든 가능한 입력을 고려해서 버그를 찾지만, 확장성 제약이 있다. under-constrained symbolic execution은 전체 프로그램이 아닌 함수 각각을 체크하여 확장성을 개선한다.

under-constrained symbolic execution

under-constrained symbolic execution은 함수 각각에 대해 실행하는 기술이다.

분석 시 어떻게 특정 함수를 가져오는지 알 수 없기 때문에, UCSE에 의해 탐지된 버그는 재연 불가능하다. 각 함수는 문맥(context, 실제 실행에서 호출되는 인자나 전역 변수와 같은) 없이 실행되기 때문에 이 분석은 정확하지 않고 false positive가 있다.

UCSE는 under-constrained 상태로 빠진 문맥을 태그해놓는다. under-constrained 데이터가 포인터로 사용되면, 새로운 under-constrained 영역이 생성되고 포인터는 이 새로운 영역을 가리킨다. 이 필요에 의한 메모리 할당은 분석해야 하는 복잡한 데이터 구조체를 관리할 수 있게 한다. 보안 위반 사항이 식별되면(스택의 리턴 주소에 값을 쓰는 등) 값은 under-constrained 상태로 체크된다. 해당 상태에서 위반 사항은 false positive로 필터링된다.

 

UCSE 기술에서 변경한 사항

Global memory under-constraining

기존 UC-KLEE는 전역 메모리를 under-constrained로 접근하는걸 다루지 않는다. 하지만 프로그램 문맥에서 전역 메모리는 UCSE로 예측할 수 없어서 전역 데이터는 덮어 써졌을 수도 있다.

따라서 모든 전역 데이터를 under-constrained로 표시해서 false positive 비율을 낮췄다.

Path limiters

UC-KLEE는 path explosion 문제를 예방하기 위해 몇 가지 제한을 해두었다. 추가 제한으로는 path explosion이 발생할 것 같으면 함수 분석을 그만둔다. 하드코딩으로 제한을 했고, 이러한 함수 분기가 여러 경로에서 보이면 함수를 return문으로 대체하고 함수의 call site에서부터 분석을 다시하도록 했다. 이는 path explosion을 피할 수 있지만 분석 정확도는 낮아진다.

false positive 필터링

익스플로잇 상태를 발견하면, under-constrained 데이터의 constraint 부족으로 이 상태가 익스플로잇 가능하다고 여기지 않는다.

먼저, 상태가 익스플로잇 불가능함을 나타내는 constraint E로 constraint solve를 한다.

예를들면, 리턴 주소를 overwrite하는 위반사항이 발견되면, 이 상태에 제약을 줘서 리턴 주소가 overwrite될 수 없다고 한다. 익스플로잇 못하는 상태에서 가능한 솔루션으로 under-constrained 값을 constrain하고 이를 U라 한다. constraint U를 가지면서 E를 제가해가고계속 상채가 익스플로잇 가능한지 체크한다. 계속 익스플로잇 가능하면 이는 문맥에서 없는 데이터에 의존적이지 않는 흐름임을 의미한다. 하지만 여전히 false positive를 가질 수 있다.

UC-angr은 Simstate 플러그인으로 구현되었다.

 

 

11. IMPLEMENTATION: SYMBOLIC-ASSISTED FUZZING

이 섹션에서는 symbolic-assisted fuzzing의 요약을 제공하고, 이 퍼저인 Driller는 다른 논문에서 자세히 설명한다.

symbolic-assisted fuzzing

symbolic-assisted fuzzing은 AFL fuzzer을 기반으로 angr를 심볼릭 트래거로 사용한다. AFL 행위를 추적하면서 AFL에서 만든 입력에 따라 언제 심볼릭 추적을 시작할지 결정한다. AFL이 입력을 변형해가면서 새로운 상태 변환을 발견하면 AFL은 이를 보고한다. AFL이 유니크하다고 한 모든 경로에 angr를 호출해서 AFL이 해당 전환에서 찾을 수 없었던 입력을 찾아본다.

symbolically tracing

AFL이 제공하는 concrete 입력 기반으로 angr의 symbolic execution engine은 심볼릭적인 추적을 제공하고, Driller의 symbolic 요소는 angr의 이 symbolic execution engine을 사용하여 구현된다. 각 입력은 하나의 경로에 대응되므로 symbolic execution에서 path explosion 문제를 피할 수 있다. 또한 이러한 입력은 AFL에 의해 추적하기로 유망한 것만 살아남아서 그렇지 않으면 필터링된다.

symbolic-assisted fuzzing에서의 PathGroup 사용

각 입력은 PathGroup 내 한 경로에 대응된다. PathGroup 각 단계마다 모든 분기는 해당 경로로 이끈 가장 최근의 점프 명령어를 ALF이 알지 못한 것으로 체크된다. 이러한 점프가 발견되면, SMT Solver는 이 점프로 이동할 입력을 생성하기 위해 사용된다. 이 입력은 AFL애 피드백되어 추후 퍼징에 사용한다.

 

 

12. IMPLEMENTATION: CRASH REPRODUCTION

입력값과 출력값 사이의 잃어버린 관계를 회복하기 위해 Replayer에서 제안한 접근법을 사용해서 symbolic execution engine 위에 Replayer를 구현했다.

크래시 재연 문제 정의

• input specification is: 크래시를 발생시킨 입력
• s: 프로그램 초기 상태
• q: 크래시 상태
• P: 프로그램

크래시 재연 알고리즘

프로그램 P에 대해 초기 상태가 sa, 크래시 상태가 qa, 입력이 ia일 때, 알고리즘은 이 입력을 가져온다. 입력 ia는 instrumented(de-randomized) 환경에서 sa를 qa로 가게 한 입력이지만 uninstrumented 환경에서는 재연되지 않는다.

1. 입력 ia를 사용해서 심볼릭하게 sa(초기상태)에서 qa(크래시 상태)까지의 경로를 실행하면서 생성되는 모든 constraint를 기록한다.
2. 주어진 constraint, 실행 경로, 프로그램 P, 새로운 초기 상태 sb에서, unconstrained 입력으로 심볼릭하게 프로그램 P를 실행하면서 새로운 크래시 상태 qb에 도달할 때까지 기록된 실행 경로를 따라간다. 이때 입력과 출력에 대한 입력 constraint를 분석할 수 있고, 입력과 출력 사이 관계도 복원할 수 있다.

Replayer limitation

1. 크래시 재연에 필요한 모든 데이터를 갖지 못할 수 있다.
2. Replayer는 특정 경로만 사용하기 때문에 입력을 만들기 때문에, 바이너리의 실행 추적이 변하면 올바른 입력을 계산하지 못한다.

 

 

13. IMPLEMENTATION: EXPLOIT GENERATION

자동으로 익스플로잇을 생성하는 것으로 angr 도구의 효율성을 평가할 수 있다.

Vulnerable States

AEG/Mayhem과 다르고 AXGEN과는 비슷하게, angr를 사용해서 크래시를 발생시키는 입력으로 concolic execution을 통해 익스플로잇을 생성한다.

크래시를 발생시킨 입력이 실행한 경로와 동일한 경로를 추적하면서 concolic execution을 수행한다. 프로그램에 크래시가 발생하면 concolic execution이 멈추고 크래시 원인을 알기 위해 symbolic 상태를 관찰하고 익스플로잇 가능성을 측정한다. 특정 레지스터의 symbolic bit를 세서 크래시를 frame pointer overwrite, instruction pointer overwrite, arbitrary write 등으로 분류한다.

Instruction Pointer Overwrite Technique

instruction pointer에서 symbolic bit가 탐지되면, instruction pointer가 shellcode나 ROP gadget과 같이 제어 가능한 명령어를 가리키도록 만든다.

Exploiting CGC Binaries

Cyber Grand Challenge는 7개의 시스템 호출만 포함하는 custom OS를 사용한다. 시스템 호출 부족은 레지스터 제어나 메모리에 읽기 쓰기가 제한된다.

DARPA 표준으로, CGC에는 다음의 두 가지 타입의 익스플로잇이 존재한다.

1. 범용 레지스터나 instruction 레지스터를 공격자가 제어 가능함을 보이는 익스플로잇
2. 메모리 공간에서 공격자가 제어 가능한 읽기를 할 수 있는 익스플로잇

 

 

14. IMPLEMENTATION: EXPLOIT HARDENING

ROP chain compiler

현대 방어 기술에도 굳건한 익스플로잇을 위해 Q의 아이디어를 기반으로 ROP chain compiler를 구현했다. 메모리에 데이터 쓰기나 라이브러리 내 임의 함수 호출 등의 원하는 기능을 수행할 수 있는 ROP payload를 자동으로 생성해준다.

Approach

1. Gadget discovery

ROP gadget을 찾기 위해 모든 실행가능한 코드를 스캔한다. 그리고 가젯의 용도에 따라 분류했다. 분류를 위해 angr의 Path 객체가 제공하는 action history와 Claripy가 제공하는 symbolic relation을 활용했다.

2. Gadget arrangement

이후 gadget의 배치를 결정한다.

예를 들면, 스택에 데이터를 넣는 가젯은 데이터를 빼는 가젯과 쌍을 이뤄서 데이터를 다른 레지스터로 옮기는 것을 만들 수 있다.

3. Payload generation

gadget들을 배치한 후, gadget을 체이닝해서 더 고수준 행위를 할 수 있도록 한다.

gadget을 angr의 프로그램 상태로 적고, 주어진 입력에 대해 SMT solver가 결과를 내도록 해서 주어진 인자에 대한 출력을 얻는다.

improvement

1. 스택 포인터가 스택을 가리키는지 식별할 수 있다.
2. gadget 분류

 

 

15. COMPARATIVE EVALUATION

DARPA의 CGC 바이너리를 평가에 사용했다.

평가 항목

• CFG recovery
• dynamic and static vulnerability discovery
• crash replay
• exploitation
• exploit hardening

 

A. CFG recovery

CFG 복원 알고리즘

1. CFGAccurate
   • forced execution
   • 간접 점프 처리할 수 있는 backwards slicing, symbolic back-traversal
2. CFGFast
   • 재귀적 디스어셈블
   • 휴리스틱
   • 빠르게 함수와 내부 함수 제어 흐름 식별

IDA Pro와 비교

IDA Pro는 CFG 복원 기술을 사용한다.

IDA Pro는 바이너리를 재귀적으로 디스어셈블하면서 심볼과 휴리스틱을 사용해서 함수를 식별하고 간접 점프 타겟을 처리하기 위해 데이터 흐름 분석을 진행한다.

평가 시 복원된 basic block 수와 제어 흐름 이동을 사용했다.

 

B. Evaluation of Vulnerability Analysis Techniques

24시간 동안 돌리면서 DARPA 데이터셋 대상으로 취약점 발견 기술 평가를 진행했다.

위 표는 CGC 대회에서 등수별 바이너리 크래시 수를 보여준다.

1등과 7등 팀은 대회에서 모두 symbolically-assisted fuzzing 기술을 사용했다. 연구에서 구현한 Driller는 1등 팀과 같은 수의 취약점을 식별할 수 있었다.

Dynamic symbolic execution

dynamic symbolic execution은 dynamic symbolic execution만을 사용하거나 이 기술에 Veritesting path explosion 예방 기술이 있는 두 방법으로 평가를 진행했다.

예상했듯이 dynamic symbolic execution에는 path explosion 문제가 빈법하게 나타났다. 16개의 CGC 바이너리 중에서 취약점들을 찾을 수 있었다. path explosion 문제를 예방하기 위해 만들어진 Veritesting의 경우 11개의 취약점만 식별할 수 있었다. Veritesting이 dynamic symbolic execution보다 적은 취약점을 찾았다는 것이 놀라웠다. Veritesting은 path explosion 문제 때문에 효율적으로 path 합병을 진행하는데, 이러한 path 합병은 복잡한 표현을 사용해서 constraint solver에 오버헤드가 발생한다.

Symbolic-assisted fuzzing

symbolic-assisted fuzzer는 AFL를 사용한다. 입력이 어떤 코드 섹션에 들어가는지 식별하기 위해 각 AFL이 만드는 입력은 dynamic symbolic execution engine에 의해 추적된다. 모든 입력은 concrete(입력은 분기하지 않음)하기 때문에 추적 과정에서 path explosion이 없고 DSE engine은 code coverage를 증가시키지 않는 입력은 필터링한다.

symbolic-assisted fuzzer로 77개의 취약점을 찾았고, AFL만을 사용했을 때는 66개 취약점을 찾았다.

DSE vs. fuzzing

fuzzing이 DSE보다 거의 3배는 더 많은 취약점을 찾을 수 있었다.

크래시를 발생시키는 입력을 분석했을 때, dynamic symbolic execution은 short path를 나타내는 경향이 있었다.

dynamic symbolic execution이 찾을 수 없었던 취약점을 살펴보면 분석 복잡성 증가가 원인임을 알 수 있었다. 주어진 경로 A에서, A가 다음 점프 끝에서 분할될 것이라는 가능성 pa가 있고, A1은 점프가 가지는 경로를 따라가고 A2는 그렇지 않은 경로를 따라간다. 다음 조건 점프에서, a1와 A2가 복제될 가능성이 있으므로 기하 급수적으로 분석해야 하는 경로가 증가하게 된다. (path explosion)

따라서 dynamic symbolic execution은 많은 basic block을 실행할 필요가 없는 크래시를 찾는데 적합하다.

code coverage 측정

기술의 효율성을 평가하기 위해 테스트 케이스에서 만들어진 code coverage를 계산했다. symbolic execution이 바이너리 당 평균 330 block 을 커버할 수 있었고, fuzzing은 689, symbolic-assisted fuzzing은 698을 커버할 수 있었다.

fuzzing이나 symbolic-assisted fuzzing에서 만들어진 경로가 그래프에 결합되면, CFGAccurate보다 더 많은 code coverage가 가능한 CFG가 가능하다.

Under-constrained symbolic execution

UC-angr는 CGC 바이너리에서 371개의 취약점을 발견할 수 있었다. 하지만, 이 접근법의 경우 함수는 문맥이 없기 때문에 결과에 많은 false positive가 있고 재연 불가능할 수 있다.

UC-angr의 결과에서 346개의 false positive를 식별했고 false positive 비율이 93%이다.

Static buffer overlap detection

UC-angr와 비슷하게 VSA 결과는 재연 불가능하고 false positive가 있다. VSA는 27개의 취약점을 찾을 수 있었고 나머지는 130개의 false positive였다. VSA의 false positive 비율은 82.8%이다.

Non-replayable vs replayable analyses

재연 불가능한 기술인 VSA와 under-constrained symbolic execution은 낮은 성능을 보였는데, 재연성 대신 더 많은 code coverage가 가능하다. 문맥이 부족했기 떄문에 결과에 많은 false positive가 있었다. false positive 비율을 낮추기 위해 false positive 필터링을 했는데, 많은 true positive도 필더링되었다.

실제 바이너리에 정적 분석 기술을 적용하려면 아직은 더 많은 연구가 필요하다.

 

C. Exploitation Evaluation

취약점 분석 기술들로부터 크래시가 식별된 후, 이 크래시를 재연하고 익스플로잇하는 작업을 진행했다.

Crash replay

환경 데이터와 de-randomized 분석 환경 때문에 크래시를 발생시킨 입력은 실제로 재연 불가능할 수 있다.

취약점 분석 기술로는 발견할 수 없었던 취약점에 대한 입력을 DARPA가 제공하는 것을 참고하여 각 바이너리에 대한 크래시를 분석했다. 이 크래시를 발생시키는 입력 중 6개는 재연이 불가능했다.

DARPA는 랜덤 데이터에 의한 제어 흐름을 허용하지 않는다. 이는 Replayer의 한계가 이 CGC 바이너리에 대해서는 없다는 것이다.

더 복잡한 제어 흐름을 갖는 리얼월드 바이너리를 대상으로 기술을 적용하려면 더 많은 연구가 필요하다.

Automatic exploit generation

Replayer로 크래시 식별 후, 타겟 애플리케이션에서 믿을 만한 크래시를 내는 input specification을 해야 한다. 하지만 이러한 입력은 여전히 익스플로잇 불가능하다.

CGC 애플리케이션 대상으로 자동으로 익스플로잇을 만들기 위해 AEG 시스템에서 제안한 기술을 사용했는데, 이 기술로는 4개의 크래시만 익스플로잇이 가능했다. 바이너리를 더 깊이 분석해보면, CGC의 목표는 익스플로잇이 아닌 바이너리에 대한 크래시를 찾는 것이기 때문에 실제로 익스플로잇이 불가능한 것이다. 또한 CGC 바이너리는 실제 익스플로잇 시나리오를 가지고 있는데 AEG에서 제안한 기술은 대부분 이에 적용할 수 없었다.

복잡한 취약점에 대한 자동화된 익스플로잇을 제공하려면 추가 연구가 필요하다.

Exploit hardening

익스플로잇 가능한 취약점도 현대 보호기법으로 불가능할 수 있어서 exploit hardening이 필요하다. Q에서 제안된 기술로 구현했고, AEG에서 만든 것으로 익스플로잇을 굳건히 했다.

Q로 구현한 것은 바이너리에 대한 충분한 정보를 활용할 수 없어서 익스플로잇이 불가능한 것도 있었다. 예를 들면, 스택에 공각자가 제어할만한 데이터가 없고 stack pivot이 다른 프로그램 부분의 공격자가 제어할 수 있는 데이터를 사용해야 했다. Q 접근법은 이러한 동작에 대한 처리가 없어서 이러한 익스플로잇은 현대 보호기법 대상으로는 불가능했다.

 

 

16. CONCLUSIONS

이 논문에서는 자동화된 식별과 바이너리에서 취약점을 익스플로잇하는 많은 기술들이 구현된 프레임워크인 angr를 소개했다. 하나의 시스템에 여러 분석 접근들을 구현해서 기술 평가 시 효율성을 판단할 수 있었다. 또한 평가 결과로 기존의 기술들을 향상하는데 연구 방향을 알 수 있었다.

angr를 오픈소스화해서 바이너리 분석 분야에서 사용할 수 있도록 하였다.