[3장] Fuzzing: Art, Science, and Engineering 번역

3. PREPROCESS

Some fuzzers modify the initial set of fuzz configurations before the first fuzz iteration.

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

 

Such preprocessing is commonly used to instrument the PUT, to weed out potentially redundant configurations (i.e., “seed selection” [177]), to trim seeds, and to generate driver applications.

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

 

As will be detailed in §5.1.1 (p. 9), PR E P R O C E S S can also be used to prepare a model for future input generation (IN P U TGE N).

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

 

3.1 Instrumentation

Unlike black-box fuzzers, both grey- and white-box fuzzers can instrument the PUT to gather execution feedback as IN P U TEV A L performs fuzz runs (see §6), or to fuzz the memory contents at runtime.

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

 

The amount of collected information defines the color of a fuzzer (i.e., black-, white-,or grey-box).

수집된 정보의 양은 퍼저의 색상(예: 검은색, 흰색 또는 회색 상자)을 정의한다.

 

Although there are other ways of acquiring information about the internals of the PUT (e.g., processor traces or system call usage [204], [92]), instrumentation is often the method that collects the most valuable feedback.

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

 

Program instrumentation can be either static or dynamic—the former happens before the PUT runs (PR E P R O C E S S), whereas the latter happens while the PUT is running (IN P U TEV A L). But for the reader’s convenience, we summarize both static and dynamic instrumentation in this section.

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

바이너리 계측(Binary Instrumentation)

바이너리 계측(Binary Instrumentation)

 

Static instrumentation is often performed at compile time on either source code or intermediate code.

정적 instrumentation은 종종 소스 코드 또는 중간 코드에서 컴파일 시 수행된다.

 

Since it occurs before runtime, it generally imposes less runtime overhead than dynamic instrumentation.

런타임 전에 발생하기 때문에 일반적으로 동적 계측보다 런타임 오버헤드가 적다.

 

If the PUT relies on libraries, these have to be separately instrumented, commonly by recompiling them with the same instrumentation.

PUT가 라이브러리에 의존하는 경우 개별적으로 계측해야 한다. 일반적으로 동일한 계측으로 해당 라이브러리를 다시 컴파일해야한다.

 

Beyond source-based instrumentation, researchers have also developed binary-level static instrumentation (i.e., binary rewriting) tools [238], [132], [77].

source-based instrumentation 을 넘어 연구자들은 binary-level 정적 계측 도구(즉, 이진 재작성)도 개발했다 [238], [132], [77].

 

Although it has higher overhead than static instrumentation, dynamic instrumentation has the advantage that it can easily instrument dynamically linked libraries, because the instrumentation is performed at runtime.

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

 

There are several well-known dynamic instrumentation tools such as DynInst [173], DynamoRIO [42], Pin [144], Valgrind [163], and QEMU [33]. 

DynInst [173], DynamoRIO [42], Pin [144], Valgrind [163], and QEMU [33]와 같은 잘 알려진 동적 계측 도구가 있다.

 

A given fuzzer can support more than one type of instrumentation. For example, AFL supports static instrumentation at the source code level with a modified compiler, or dynamic instrumentation at the binary level with the help of QEMU [33].

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

 

When using dynamic instrumentation, AFL can either instrument (1) executable code in the PUT itself, which is the default setting, or (2) executable code in the PUT and any external libraries (with the AFL_INST_LIBS option).

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

 

The second option—instrumenting all encountered code—can report coverage information for code in external libraries, and thus provides a more complete picture of coverage. However, this will also encourage AFL to fuzz additional paths in external library functions.

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

⇒ 대상 프로그램(PUT)만 퍼징하고 싶은건데 외부라이브러리 퍼징하면 안좋음.

 

3.1.1 Execution Feedback

Grey-box fuzzers typically take execution feedback as input to evolve test cases. AFL and its descendants compute branch coverage by instrumenting every branch instruction in the PUT.

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

 

However, they store the branch coverage information in a bit vector, which can cause path collisions.

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

 

CollAFL [83] recently addressed this issue by introducing a new path-sensitive hash function.

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

 

Meanwhile, LibFuzzer [7] and Syzkaller [216] use node coverage as their execution feedback.

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

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

 

Honggfuzz [204] allows users to choose which execution feedback to use.

Honggfuzz[204]는 사용자가 사용할 실행 피드백을 선택할 수 있도록 한다.

 

3.1.2 In-Memory Fuzzing

When testing a large program, it is sometimes desirable to fuzz only a portion of the PUT without re-spawning a process for each fuzz iteration in order to minimize execution overhead.

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

 

For example, complex (e.g., GUI) applications often require several seconds of processing before they accept input.

예를 들어 복잡한(GUI 등) 어플리케이션에서는 입력을 받기 전에 몇 초간의 처리가 필요한 경우가 많다.

 

One approach to fuzzing such programs is to take a snapshot of the PUT after the GUI is initialized. To fuzz a new test case, one can then restore the memory snapshot before writing the new test case directly into memory and executing it.

이러한 프로그램을 퍼지하는 방법 중 하나는 GUI가 초기화된 후에 PUT의 스냅샷을 만드는 것이다. 새로운 테스트 케이스를 fuzz하기 위해 새로운 테스트 케이스를 메모리에 직접 쓰고 실행하기 전에 메모리 스냅샷을 복원할 수 있다.

 

The same intuition applies to fuzzing network applications that involve heavy interaction between client and server. This technique is called in-memory fuzzing [104].

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

 

As an example, GRR [211], [92] creates a snapshot before loading any input bytes. This way, it can skip over unnecessary startup code.

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

 

AFL also employs a fork server to avoid some of the process startup costs. Although it has the same motivation as in-memory fuzzing, a fork server involves forking off a new process for every fuzz iteration (see §6).

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

 

Some fuzzers [7], [231] perform in-memory fuzzing on a function without restoring the PUT’s state after each iteration. We call such a technique as an in-memory API fuzzing.

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

 

For example, AFL has an option called persistent mode [233], which repeatedly performs in-memory API fuzzing in a loop without restarting the process. In this case, AFL ignores potential side effects from the function being called multiple times in the same execution.

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

 

Although efficient, in-memory API fuzzing suffers from unsound fuzzing results: bugs (or crashes) found from inmemory fuzzing may not be reproducible, because (1) it is not always feasible to construct a valid calling context for the target function, and (2) there can be side-effects that are not captured across multiple function calls.

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

 

Notice that the soundness of in-memory API fuzzing mainly depends on the entry point function, and finding such a function is a challenging task.

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

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

 

3.1.3 Thread Scheduling

Race condition bugs can be difficult to trigger because they rely on non-deterministic behaviors which may only occur infrequently.

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

 

However, instrumentation can also be used to trigger different non-deterministic program behaviors by explicitly controlling how threads are scheduled [189], [190], [169], [116], [131], [47], [181]. Existing work has shown that even randomly scheduling threads can be effective at finding race condition bugs [189].

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

3.2 Seed Selection

Recall from §2 that fuzzers receive a set of fuzz configurations that control the behavior of the fuzzing algorithm. Unfortunately, some parameters of fuzz configurations, such as seeds for mutation-based fuzzers, have large value domains.

2장에서 퍼저는 퍼징 알고리즘의 동작을 제어하는 fuzz configuration들의 셋을 받는다고 했는데, 불행하게도 mutation-based 퍼저에서의 시드같은 몇가지 퍼즈구성은 매우 중요하다.

 

For example, suppose an analyst fuzzes an MP3 player that accepts MP3 files as input. There is an unbounded number of valid MP3 files, which raises a natural question: which seeds should we use for fuzzing? This problem of decreasing the size of the initial seed pool is known as the seed selection problem [177].

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

 

There are several approaches and tools that address the seed selection problem [177], [76]. A common approach is to find a minimal set of seeds that maximizes a coverage metric, e.g., node coverage, and this process is called computing a minset.

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

 

For example, suppose the current set of configurations C consists of two seeds s1 and s2 that cover the following addresses of the PUT: {s1 → {10, 20} , s2 → {20, 30}}.

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

 

If we have a third seed s3 → {10, 20, 30} that executes roughly as fast as s1 and s2, one could argue it makes sense to fuzz s3 instead of s1 and s2, since it intuitively tests more program logic for half the execution time cost.

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

 

This intuition is supported by Miller’s report [153], which showed that a 1% increase in code coverage increased the percentage of bugs found by .92%. As is noted in §7.2, this step can also be part of CO N FUP D A T E, which is useful for fuzzers that can introduce new seeds into the seed pool throughout the campaign.

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

 

Fuzzers use a variety of different coverage metrics in practice. For example, AFL’s minset is based on branch coverage with a logarithmic counter on each branch. The rationale behind this decision is to allow branch counts to be considered different only when they differ in orders of magnitude.

다양한 coverage metic이 존재하는데, 먼저 AFL은 각 branch의 logarithmic counter를 이용한 branch coverage 기반 퍼저이다. branch counter의 크기 정도(상용로그의 척도: 근사값의 크기 등급)가 달라야 다른 branch count로 취급하도록 구현되어있다.

 

Honggfuzz [204] computes coverage based on the number of executed instructions, executed branches, and unique basic blocks. This metric allows the fuzzer to add longer executions to the minset, which can help discover denial of service vulnerabilities or performance problems.

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

3.3 Seed Trimming

Smaller seeds are likely to consume less memory and entail higher throughput. Therefore, some fuzzers attempt to reduce the size of seeds prior to fuzzing them, which is called seed trimming. Seed trimming can happen prior to the main fuzzing loop in PR E P R O C E S S or as part of CO N FUP D A T E.

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

 

One notable fuzzer that uses seed trimming is AFL [231], which uses its code coverage instrumentation to iteratively remove a portion of the seed as long as the modified seed achieves the same coverage. Meanwhile, Rebert et al. [177]

seed trimming을 사용하는 주목할 만한 퍼저는 AFL [231]이다.이러한 퍼저는 코드 커버리지 계측을 사용하여 변경된 시드가 동일한 커버리지에 도달하는 한 시드의 일부를 반복적으로 제거한다. 한편, 레버트 외 연구진 [177]

⇒ 이 부분은 없어도 그 커버리지에 도달한다 하는 부분을 계속 찾아가는 과정

 

reported that their size minset algorithm, which selects seeds by giving higher priority to smaller seeds in size, results in fewer unique bugs compared to a random seed selection.

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

⇒ unique bugs가 적다는 것은 다양한 취약점을 잘 못 찾는다는 것. 안좋은 것.

 

For the specific case of fuzzing Linux system call handlers, MoonShine [167] extends syzkaller [216] to reduce the size of seeds while preserving the dependencies between calls which are detected using a static analysis.

Linux 시스템 콜핸들러의 퍼징의 구체적인 경우, MoonShine [167]는 시드의 크기를 줄이면서 정적 분석을 사용하여 검출된 콜 간의 의존성을 보존하기 위해 syzkaller [216]를 확장한다.

3.4 Preparing a Driver Application

When it is difficult to directly fuzz the PUT, it makes sense to prepare a driver for fuzzing.

PUT를 직접 퍼징하기 어려운 경우에는 퍼징용 드라이버를 준비하는 것이 타당하다.

 

This process is largely manual in practice although this is done only once at the beginning of a fuzzing campaign.

이 프로세스는 퍼징 캠페인의 시작에서 한 번만 수행되지만 실제로는 대부분 수동이다.

 

For example, when our target is a library, we need to prepare for a driver program that calls functions in the library. Similarly, kernel fuzzers may fuzz userland applications to test kernels [125], [165], [31]. IoTFuzzer [54] targets IoT devices by letting the driver communicate with the corresponding smartphone application.

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