[Paper Review] Intriguer: Field-Level Constraint Solving for Hybrid Fuzzing

ABSTRACT

하이브리드 퍼징은 퍼징과 콘콜릭 실행을 결합한 기술이다. 본 연구에서는 하이브리드 퍼징에 (1) 느린 심볼릭 실행 속도, (2) 불필요한 제약 조건 해결에 많은 시간 사용, (3) 필요 이상의 자원 할당, (4)  트리거 하기 어려운 버그 탐지 불가와 같은 문제점이 있음을 조사했다. 이러한 기존의 하이브리드 퍼징의 단점을 개선하기 위해 Intriguer라는 최신 하이브리드 퍼저를 개발했다. Intriguer는 필드 레벨에서 제약조건을 해결하는 퍼저로 버그 제보 및 23개의 CVE 발급 등으로 좋은 성과를 보였다.

 

INTRODUCTION (Intriguer 주요 내용)

Intriguer의 주요 아이디어는 필드 레벨 지식을 통해 심볼릭 실행을 최적화한 필드 레벨 제약 조건 해결이다. Intriguer는 명령어 레벨에서 동적 오염 분석(dynamic taint analysis, DTA)을 수행하고, mov와 같은 데이터 전송 명령어를 제외한 명령어를 기록한 실행 추적 리스트를 생성(Execution Monitor)한다. 생성된 추적 기록에서 큰 입력 데이터를 사용하는 기록을 최소화(Trace Reduction)하여 심볼릭 실행을 최소화한다. 그리고 입력 포맷을 알 수 없는 입력 필드의 정보를 유추하여 필드 전환 트리를 생성함으로써 심볼릭 에뮬레이션을 간소화하고 최소화된 제약 조건을 구성할 수 있다. 이 과정을 통해 Intriguer는 취약점 발견과 관련성이 높은 심볼릭 에뮬레이션을 수행하고, 복잡한 제약 조건에서만 심볼릭 솔버를 사용하여 트리를 이용해 복잡하지 않은 제약 조건으로 해결함으로써 효율성을 높인다.

 

MOTIVATION

하이브리드 퍼징의 성능을 분석을 통해 얻은 연구 동기를 설명한다.

(1) 느린 심볼릭 실행

Qsym에서 mov 명령어를 에뮬레이트하여 Qsym의 에뮬레이션 시간이 느리다는 것을 확인하였고, 이를 통해 mov와 같은 명령어를 에뮬레이트하는 것을 방지하여 심볼릭 에뮬레이션 시간을 감소해야 함을 알 수 있었다. mov 전과 후의 오염된 명령어를 비교하여 추론된 필드 레벨 내 이 정보를 통해 데이터 흐름을 추적할 수 있다. 명령어 레벨에서 간소화된 DTA를 사용하여 mov와 같은 명령어를 제외하고 실행 추적 시 오염된 오프셋이나 콘크리트 값을 기록하고 필드 레벨 제약 조건 해결에 추적 정보를 사용한다.

(2) 불필요한 제약 조건 해결

정수 명령어나 mov 명령어는 많은 암호 함수에서 사용되는데, 이러한 명령어는 복잡한 제약 조건을 만들어서 제약 조건 해결 시간에서 반복적인 타임아웃이 발생한다. 이 관찰을 통해 명령어로 DTA로 생성된 실행 추적을 그룹화하여 넓은 범위의 입력 크기에 접근하는 그룹의 추적을 감소시켜서 문제를 해결했다.

(3) 필요 이상의 자원 할당

분기 조건의 많은 부분은 프로그램 내에서 복잡하지 않아 심볼릭 솔버 호출 없이도 명령어 레벨의 DTA로 바로 해결할 수 있음을 관찰했다. 복잡한 제약 조건과 복잡하지 않은 제약 조건을 시스템적으로 분류하고, 복잡한 제약 조건에만 심볼릭 솔버를 호출하여 문제를 해결했다.

(4) 트리거하기 힘든 버그 탐지 불가

Intriguer, AFL, VUzzer과 Qsym을 대상으로 실험한 결과, AFL은 트리거 하기 힘든 버그 탐지에 Intriguer보다 많은 시간이 걸렸고, VUzzer와 Qsym은 버그 탐지에 실패했다. 이를 통해 트리거하기 위해 필요한 특정 갑을 알 수 없다면 해당 버그는 탐지되지 않을 수 있음을 관찰할 수 있었고, 산술 범위의 조건을 분기 제약 조건으로 간주하는 것으로 문제를 해결했다.

 

DESIGN (Intriguer 동작 구조)

그림 1 Intriguer 동작 구조

 

Intriguer는 타겟 프로그램과 테스트케이스를 입력으로 받고 흥미로운 오프셋과 값을 발견하기 위한 새로운 경로를 탐색할 수 있는 새로운 테스트케이스를 생성한다. Intriguer는 커버리지 기반 버저가 제공하는 입력 테스트케이스를 입력으로 타겟 프로그램을 실행하여 명령어 레벨의 오염 추적을 수행한다.

이를 위해 Intriguer는 다음 기능을 수행한다.

(1) 실행 추적 감소 (Trace Reduction)

Intriguer는 먼저 실행 추적 감소와 필드 레벨 제약 조건이 가능하도록 데이터 흐름 분석을 위한 명령어 레벨 오염 추적을 진행한다. 기존 콘콜릭 실행 엔진은 버그 발견과 연관 없는 명령어에 많은 심볼릭 에뮬레이션 시간을 할애하기 때문에 Intriguer는 제약 조건 해결 단계 전 연관 없는 오염된 명령어를 실행 추적 리스트에서 제거하여 실행 추적 크기를 줄인다. 특히 mov 명령어와 같은 데이터 전송 명령어를 제외하고 넓은 범위의 입력 크기에 접근하는 오염된 명령어를 제거하여 감소된 실행 추적 리스트를 생성한다.

(2) 필드 추론과 필드 전환 트리 생성

필드(field)는 명령어에서 바로 사용되는 연속된 입력 바이트로 정의한다. Intriguer는 앞서 생성한 실행 추적 리스트에 기록된 오프셋 정보를 활용하여 입력 필드를 연속된 바이트 오프셋으로 구성된 하나의 청크, 즉 하나의 필드로 추론하고, 추론된 명령어 중 필드가 아닌 것은 제거한다. 이후 추론된 필드에 대해 필드 전환 트리를 구성하여 심볼릭 에뮬레이션을 간소화하고 최소화된 제약 조건을 구성한다.

(3) 필드 레벨 제약 조건 해결

Intriguer는 구성된 추론된 필드와 필드 전환 트리를 이용하여 복잡한 제약 조건을 대상으로만 SMT 솔버를 호출하고 복잡하지 않은 제약 조건은 바로 해결한다. 이를 통해 심볼릭 에뮬레이션과 제약 조건을 해결할 때 불필요한 작업을 줄일 수 있다.

Intriguer의 주요 아이디어는 필드 레벨 지식을 통해 심볼릭 실행을 최적화한 필드 레벨 제약 조건 해결이다. 그림 1은 Intriguer 동작 구조로, Intriguer는 타겟 프로그램과 테스트케이스를 입력으로 받고 흥미로운 오프셋과 값을 발견하기 위한 새로운 경로를 탐색할 수 있는 새로운 테스트케이스를 생성한다. Intriguer는 커버리지 기반 버저가 제공하는 입력 테스트케이스를 입력으로 타겟 프로그램을 실행하여 명령어 레벨의 오염 추적을 수행한다.

 

IMPLEMENTATION

execution monitor 구현에 pintool을 사용(Pin 3.7)했다. 제약조건 해결과 경계값 트리거를 위한 구현에는 Z3 (v.4.5)를 사용했고, 퍼저는 AFL 24.41b를 사용하여 구현했다. Intriguer는 Linux, Windows, 그리고 macOS 등 OS 환경에 쉽게 포팅될 수 있다. 현재 구현된 버전은 대부분의 32-bit 명령어와 일부의 64-bit 명령어를 지원한다.

 

EVALUATION

(1) 버그 탐지 능력 측면에서 평가

그림 2 최신 퍼저와 Intriguer의 버그 탐지 수 비교

그림 2는 취약점 탐지 도구 평가 데이터셋인 LAVA-M 프로그램 대상으로 최신 퍼저인 VUzzer와 Qsym과 함께 Intriguer 퍼저를 실행한 결과이다. Intriguer는 모든 취약점을 발견하였다.

그림 3 리얼월드 프로그램에서 AFL, Qsym, Intriguer에서 찾은 버그 수 비교

그림 3을 통해 리얼월드 프로그램에서 Intriguer는 AFL보다 더 많은 버그를 탐지한 것으로 커버리지 기반 퍼저인 AFL이 해결하지 못한 복잡한 제약 조건을 Intriguer가 해결했음을 알 수 있다. objdump, nm, readelf, ffmpeg, 그리고 tiff2pdf에서 Intriguer가 Qsym보다 더 많은 버그를 발견한 것을 통해 Trace Reduction과 필드 레벨 제약 조건 해결을 통한 심볼릭 에뮬레이션 최적화로 더 효과적으로 버그를 발견할 수 있음을 알 수 있다.

 

(2) 코드 커버리지 증가 측면에서 평가

그림 4 Intriguer와 Qsym의 Branch Coverage 실험 결과. (a) 실행 시간. (b) 새로운 branch 수

그림 4는 AFL로 생성된 20개의 테스트케이스를 입력으로 Intriguer와 Qsym을 실행 시간과 branch coverage 측면에서 평가한 결과이다. 이를 통해 Intriguer가 Qsym과 비교했을 때 제약 조건 해결 시간과 에뮬레이션 시간 측면에서 성능이 뛰어남을 확인할 수 있다.

 

(3) Trace Reduction의 의도하지 않은 흥미로운 코드 블록 제거를 제외한 실행 추적 성능 평가

그림 5 Trace Reduction 사용 유무에 따른 새로운 분기 및 버그 탐지 수 비교

그림 5는 실행 추적 감소의 효과성과 버그 탐지 성능을 확인하기 위해 Trace Reduction을 사용하고 사용하지 않는 퍼징을 24시간 동안 수행한 결과이다. Trace Reduction을 사용한 퍼징이 극명하게 더 많은 분기와 버그를 발견할 수 있음을 확인하였다.

 

(4) 필드 전환 트리의 효율성 평가

그림 6 필드 전환 트리 사용 유무에 따른 새롭게 발견한 분기 및 버그 수 비교

그림 6은 Intriguer에서 필드 전환 트리를 사용했을 때와 사용하지 않았을 때 24시간 동안 퍼징을 수행하여 발견한 분기와 버그 수를 나타낸다. 이것으로 필드 전환 트리가 모든 프로그램 내 더 많은 분기와 버그를 발견할 수 있음을 확인하였다.

 

(5) Arithmetic Boundary Instrumentation 평가

그림 6 Arithmetic Boundary Instrumentation 사용 유무에 따른 새롭게 발견한 분기와 버그 수 비교

그림 6은 Intriguer에서 Arithmetic Boundary Instrumentation 사용 유무에 따른 24시간 퍼징 결과 새롭게 발견한 분기와 버그 수를 나타내며, Arithmetic Boundary Instrumentation를 사용했을 때만 트리거하기 힘든 버그를 탐지할 수 있음을 확인할 수 있다.