3. PREPROCESS

일부 퍼저는 첫 번째 fuzz iteration이 반복되기 전에 fuzz configuration의 초기 세팅을 변경한다.

이러한 전처리는 일반적으로 PUT을 계측(instrument)하거나 잠재적인 중복 구성(configurations) 배제(즉, "시드 선택(seed selection)"), 시드 트리밍(seed trimming) 및 드라이버 애플리케이션 생성에 사용된다.

§ 5.1.1 (p.9)에서 자세히 설명하듯이, PR E R O C E S는 향후 입력 생성을 위한 모델 준비에도 사용될 수 있다(IN P U TGE N).

3.1 Instrumentation

black-box 퍼저와 달리 grey- 과 white-box 퍼저는 INPUTEVAL이 fuzz run을 수행함에 따라 실행 피드백을 수집하거나 runtime에 메모리 내용을 fuzz(in-memory-fuzzing) 하도록 PUT를 계측할 수 있다.

수집된 정보의 양(The amount of collected information)은 퍼저의 색상(예: black, white 또는 grey 박스)을 정의한다.

PUT의 내부에 대한 정보를 얻는 다른 방법이 있지만(예: 프로세서 추적(processor traces) 또는 시스템 호출(system call usage) 사용), 계측(instrumentation)은 주로 가장 귀중한 피드백을 수집하는 방법이다.

프로그램 instrumentation 은 정적(static) 또는 동적(dynamic) instrumentation 중 하나이다. 전자는 PUT 실행 전(PR E R O C E S S)에 발생하는데에 비해 후자는 PUT 실행 중(IN P U TEV A L)에 발생한다. 본 논문에서는 정적 및 동적 계측을 모두 요약한다.

⇒ 정적 instrumentation 동적 instrumentation

바이너리 계측(Binary Instrumentation)

Static instrumentation (정적 계측)

정적 instrumentation은 소스코드 또는 중간 코드에서 컴파일시(런타임 이전) 수행되고 런타임 전에 발생하기 때문에 일반적으로 동적 계측보다 런타임 오버헤드가 적다. PUT이 라이브러리에 의존하는 경우 일반적으로 동일한 계측 방법을 이용해 개별적으로 계측해야한다. 즉, 계측을 위해 해당 라이브러리를 다시 컴파일해야한다.

source-based instrumentation 뿐만 아니라 바이너를 대상으로 계측하는 binary-level 정적 계측 도구(즉, 이진 재작성)도 개발됐다.

Dynamic instrumentation (동적 계측)

동적계측은 정적 계측보다 오버헤드가 높지만 런타임에 수행되기 때문에 별도의 전처리 과정에서의 컴파일없이도 동적으로 연결된 라이브러리를 쉽게 계측할 수 있다는 장점이 있다.

DynInst, DynamoRIO, Pin, Valgrind, and QEMU와 같은 잘 알려진 동적 계측 도구가 있다.

퍼저는 여러 유형의 계측을 지원할 수 있다. 예를 들어, AFL은 수정된 컴파일러를 사용하여 소스코드 레벨에서 정적 계측을 지원하거나 QEMU의 도움을 받아 이진 수준에서 동적 계측을 지원한다.

dynamic instrumentation를 사용하는 경우, AFL은 (1) PUT 자체의 실행 가능 코드(기본 설정) 또는 (2) PUT 및 외부 라이브러리의 실행 가능 코드(AFL_INST_LIBS 옵션 포함) 중 하나를 실행할 수 있다.

두 번째 옵션(조우된 모든 코드를 계측하는 것)은 외부 라이브러리의 코드에 대한 커버리지 정보를 보고할 수 있으므로 커버리지에 대한 보다 완전한 그림을 제공한다. 단, 이것은 AFL이 외부 라이브러리 함수에 추가 경로를 퍼징하도록 하기도 한다.

⇒ 대상 프로그램(PUT)만 퍼징하고 취약점을 찾고 싶은건데 외부라이브러리 퍼징하면 안좋음. 물론 프로그램의 실행이 얼마나 깊숙이 이루어졌는지 파악하기는 수월(커버리지에 대한 완전한 그림)할 수 있지만.

3.1.1 Execution Feedback

Grey-box 퍼저는 일반적으로 실행 피드백을 입력으로 받아 테스트 케이스를 진화시킨다. AFL과 그 하위 프로그램은 PUT의 모든 분기 명령(branch instruction)을 계측하여 분기 커버리지(branch coverage)를 계산한다.

단, 비트벡터(bit vector)에 저장되어있는 분기 커버리지(branch coverage) 정보는 path collisions(경로 충돌)의 이유가될 수 있다.

최근 CollAFL은 path-sensitive hash function를 도입하여 이 문제를 해결했다.

한편, LibFuzzer 및 Syzkaller는 node coverage를 실행 피드백으로 사용한다.

=> path collisions : path-sensitive hash function와 node coverage로 해결가능

Honggfuzz는 사용자가 사용할 실행 피드백(execution feedback)을 선택할 수 있도록 한다.

3.1.2 In-Memory Fuzzing

큰 프로그램을 테스트할 때 실행 오버헤드를 최소화하기 위해 각 fuzz iteration에 대해 프로세스를 다시 실행하지 않고 PUT의 일부만 퍼징하는 것이 바람직할 수 있다.

예를 들어 복잡한(GUI 등) 어플리케이션에서는 입력을 받기 전에 몇 초간의 처리가 필요한 경우가 많은데, 이러한 프로그램을 퍼지하는 방법 중 하나는 GUI가 초기화된 후에 PUT의 스냅샷을 만드는 것이다. 새로운 테스트 케이스를 fuzz하기 위해 새로운 테스트 케이스를 메모리에 직접 쓰고 실행하기 전에 메모리 스냅샷을 복원하는 방식으로 퍼징할 수 있다.

같은 직관(원리 / 개념)이 클라이언트와 서버 간의 많은 상호작용을 수반하는 네트워크 애플리케이션에 대한 퍼징에도 적용된다.

이 기술은 in-memory fuzzing이라고 불린다. 예를 들어 GRR은 입력 바이트를 로드하기 전에 스냅샷을 생성한다. 이렇게 하면 불필요한 시작 부분의 코드들을 건너뛸 수 있다.

또한 AFL은 프로세스 시작의 부담을 피하기 위해 포크 서버를 사용한다. in-memory fuzzing과 같은 목적이지만, 포크 서버에는 퍼징 반복마다 새로운 프로세스를 fork한다. (6 참조).

일부 퍼저는 각 반복 후에 PUT 상태를 복원하지 않고 함수에 대해서 in-memory fuzzing을 한다. 이러한 기술을 in-memory API 이라고 부른다.

⇒ in-memory API : PUT 상태가 아니라 함수에 대해서만 수행하는 in-memory fuzzing

예를 들어 AFL에는 persistent mode라고 하는 옵션이 있다. 이 옵션은 프로세스를 재부팅하지 않고 루프 내에서 in-memory API 퍼징을 반복 실행한다. 이 경우 AFL은 같은 실행으로 여러 번 호출되는 함수에 의한 잠재적인 부작용을 무시한다.

in-memory API 퍼징은 효율적이기는 하지만 예기치 않은 퍼징 결과가 발생할때가 있다. 좀 더 구체적으로 인메모리 퍼징에서 발견된 버그(또는 크래시)는 재현할 수 없는 경우가 있다. 이는 (1) 타깃 함수의 유효한 호출 컨텍스트를 구축하는 것이 항상 가능한 것은 아니며 (2) 여러 함수 호출에 걸쳐 포착되지않는 부작용이 발생할 수 있기 때문이다.

In-Memory API Fuzzing의 재현가능성(soundness)은 주로 entry point function에 따라 달라지며, 이러한 함수를 찾는 것은 어려운 작업이다.

⇒ soundness(건전성) : 형식 체계 내에서 증명가능한 명제가 의미론 상으로도 참이 되는 성질. 재현가능성 보장 정도의 의미

3.1.3 Thread Scheduling

race condition 버그는 드물게 발생할 수 있는 비결정론적 행동(non-deterministic behaviors, 간혹 어쩌다가 한번 나타나는거. 우연히)에 의존하기 때문에 트리거하기 어려울 수 있다.

instrumentation을 이용해서 스레드가 스케줄링되는 방법을 명시적으로 제어할 수 있는데, 이게 이제 다른 비결정적(non-deterministic) 프로그램 동작을 트리거하기 위해 사용될 수 있다. 기존의 연구는 무작위로 스레드를 스케줄링하는 것조차 race condition 버그를 찾는 데 효과적일 수 있다는 것을 보여주었다.

3.2 Seed Selection

2장에서 퍼저는 퍼징 알고리즘의 동작을 제어하는 fuzz configuration들의 셋을 받는다고 했는데, mutation-based 퍼저에서의 시드처럼 fuzz configuration은 매우 중요하다.

예를 들어 MP3 파일을 입력으로 받아들이는 MP3 플레이어를 fuzzing 한다고 가정하자. 유효한 MP3 파일이 무제한으로 존재하기 때문에 퍼징을 위해 어떤 시드를 사용해야 좋은지 의문이 생긴다. 초기 시드 풀의 크기를 줄이는 문제를 시드 선택 문제(seed selection)라고 한다.

⇒ 수없이 많은 인풋의 경우의 수들 중에서 의미있는 인풋이 될 가능성이 있는 형태의 인풋을 추려가는 과정

시드 선택 문제(seed selection)를 다루는 몇 가지 접근법과 도구가 있다. 일반적인 접근방식은 커버리지 메트릭을 최대화하는 최소한의 시드 세트(node coverage)를 찾는 것이다.이 프로세스를 minset 계산이라고 부른다.

예를 들어 현재 구성 C 집합이 {s1 → {10, 20}, s2 → {20, 30}의 PUT 주소를 포함하는 두 개의 시드 s1 및 s2로 구성되어 있다고 가정하자.

s1 및 s2만큼 빠르게 실행되는 세 번째 시드 s3 → {10, 20, 30}이 있으면 실행 시간의 절반을 쓰고도 더 많은 프로그램 로직을 테스트하기 때문에 s1 및 s2 대신 seed s3이 타당하다고 주장할 수 있다.

이러한 직관은 코드 커버리지가 1% 증가하면 버그가 0.92% 증가했다는 Miller의 보고서에 의해 뒷받침된다. § 7.2에서 설명한 바와 같이 이 단계는 CON FUP D A T E에서 진행될 수도 있다. 이것은 캠페인 전체에서 어떤 시드를 새로운 시드로 시드 풀에 도입할지를 고민하는 퍼저에 도움이 된다.

퍼저는 다양한 coverage metic을 이용하는데, 먼저 AFL의 miniset은 각 branch의 logarithmic counter를 이용한 branch coverage을 기반으로 한다. 이 결정의 이론적 해석(rationale)은 크기 순서가 다른 경우에만 다른 브런치라고 생각하고 브런치를 셀 수 있도록 한다. (to allow branch counts to be considered different only when they differ in orders of magnitude.)

Honggfuzz는 실행된 명령 수, 실행된 분기 수 및 고유한 기본 블록에 따라 coverage를 계산한다. 이 메트릭을 사용하면 퍼저가 minset에 더 긴 실행을 추가할 수 있으므로 서비스 거부 취약점(DOS) 또는 성능 문제를 발견하는 데 도움이 된다.

3.3 Seed Trimming

시드가 작을수록 메모리 소비량이 적어지고 throughput이 높아진다. 따라서, 어떤 퍼저는 퍼징을 하기전에 시드의 크기를 줄이려고 하는데, 이것을 seed trimming라고 한다. seed trimming은 PR E P R O C E S의 메인 퍼징 루프 이전 또는 CON FUP D A TE의 일부로 발생할 수 있다.

seed trimming을 사용하는 주목할 만한 퍼저는 AFL이다. 이러한 퍼저는 코드 커버리지 계측(code coverage instrumentation)을 사용하여 변경된 시드가 동일한 커버리지에 도달하는 한 시드의 일부를 반복적으로 제거한다. (remove a portion of the seed as long as the modified seed achieves the same coverage.)

⇒ seed triming : 이 부분은 없어도 그 커버리지에 도달한다 하는 부분을 계속 찾아가는 과정. 시드의 크기를 줄이는 것이 목표

size minset 알고리즘은 크기가 작은 시드에 높은 우선순위를 부여하여 시드를 선택하므로 랜덤 시드 선택에 비해 고유한 버그(unique bugs)가 적다고 보고했다.

⇒ unique bugs가 적다는 것은 다양한 취약점을 잘 못 찾는다는 것. 안좋은 것. 크기가 작은 시드를 계속해서 사용하면 오히려 랜덤시드에 비해 고유한 버그가 적어질 수도 있다.

Linux 시스템 콜 핸들러를 퍼징하는 경우, MoonShine은 syzkaller를 확장하여 정적 분석을 사용하여 감지된 호출 간의 종속성을 유지(preserving the dependencies)하면서 시드 크기를 줄인다.

3.4 Preparing a Driver Application

PUT를 직접 퍼징하기 어려운 경우에는 퍼징용 드라이버를 준비해야한다. 이 프로세스는 퍼징 캠페인의 시작에서 한 번만 수행되지만 실제로는 대부분 수동으로 해야한다.

예를 들어, 우리의 목표가 라이브러리라면, 우리는 라이브러리의 함수를 호출하는 드라이버 프로그램을 준비해야한다. 마찬가지로, 커널 퍼저는 커널을 테스트하기 위해 커널 시스템 콜을 호출하는 userland 애플리케이션을 퍼징할 수 있다. IoTFuzer는 운전자가 해당 스마트폰 애플리케이션과 통신하도록 함으로써 IoT 기기를 대상으로 퍼징한다.