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

The term “fuzz” was originally coined by Miller et al. in 1990 to refer to a program that “generates a stream of random characters to be consumed by a target program” [152,p. 4].

“fuzz”라는 용어는 본래 “타겟 프로그램이 소비(consumed) 할 랜덤 문자열 스트림을 생성하는” 프로그램을 나타내기위해 만들어졌다. 즉, 취약점 탐지와는 무관하게 프로그램에 넣을 인풋들을 랜덤으로 생성하는 프로그램을 나타내는 단어가 "fuzz"였다.

 

Since then, the concept of fuzz as well as its action—“fuzzing”—has appeared in a wide variety of contexts, including dynamic symbolic execution [90], [226], grammar based test case generation [88], [105], [213], permission testing [24], [80], behavioral testing [122], [175], [224], complexity testing [135], [222], kernel testing [216], [196], [186], representation dependence testing [121], function detection [227], robustness evaluation [223], exploit development [111], GUI testing [197], signature generation [72], and penetration testing [81], [156].

그 이후로 “fuzz”의 개념과 동작 즉, fuzzing은 다양한 맥락에서 등장했다.

동적 심볼릭 익스큐션, 문법기반 테스트 케이스 생성, 권한 테스팅, 동작 테스팅, 복잡도 테스팅, 커널 테스팅, 디펜던시 표현 테스팅, 함수 검출, 소프트웨어 견고성 평가, 익스플로잇 개발, GUI 테스팅, 시그니처 생성 그리고, 침투(penetration) 테스팅 등의 기술과 개념들이 fuzzing이라는 개념과 동작을 설명하기 위해 등장했다. 대충 동적으로 실행해서 동작을 어떻게 하는지 지켜보는 기술들이 fuzzing이라는 개념을 대변했다.

 

To systematize the knowledge from the vast literature of fuzzing, let us first present a terminology of fuzzing extracted from modern uses.

퍼징에 관한 방대한 문헌으로부터 지식을 체계화하기 위해서, 최근에 많이 사용된 사례에서 뽑아낸 퍼징관련 용어들을 소개할 예정이다.

 

2.1 Fuzzing & Fuzz Testing

Intuitively, fuzzing is the action of running a Program Under Test (PUT) with “fuzz inputs”.

직관적으로, 퍼징이라는 것은 “fuzz inputs”을 넣어 테스트용 프로그램(PUT)을 실행하는 작업이다.

 

Honoring Miller et al., we consider a fuzz input to be an input that the PUT may not be expecting, i.e., an input that the PUT may process incorrectly and trigger a behavior that was unintended by the PUT developer.

fuzz input은 PUT가 예상하지 못할 수 있는 입력, 즉 PUT 개발자에 의해 의도하지 않은 동작을 트리거할 수 있는 입력이라고 간주한다.

 

To capture this idea, we define the term fuzzing as follows. 

이 아이디어를 이용해서 우리는 퍼징이라는 용어를 다음과 같이 정의한다.

 

Definition 1 (Fuzzing). Fuzzing is the execution of the PUT using input(s) sampled from an input space (the “fuzz input space”) that protrudes(튀어나오다, 돌출되다) the expected input space of the PUT.

정의 1(Fuzzing) : Fuzzing은 PUT의 예상되는 입력 공간을 벗어나는 입력 공간("퍼지 입력 공간")에서 뽑아낸 입력을 사용하여 PUT를 실행하는 것이다. (그로써 의도하지 않은 동작을 트리거하는게 목표)

 

⇒ input(s) vs input spcae(”fuzz input space”) vs expected input space of the PUT

• input(s) : 프로그램에 들어가는 입력들
• input spcae(”fuzz input space”) : 의도하지 않은 동작을 트리거하기위해 프로그램에 넣어보려 대기중인 인풋들
• expected input space of the PUT : PUT을 개발할때 들어올 것이라고 예상했던 인풋들 (정상적인 동작을 하는 인풋들)

⇒ protrudes the expected input space of the PUT : 예상했던 입력들을 벗어나게끔 하는 ⇒ 의도치 않은 동작을 유도하는

 

Three remarks are in order.

이 정의에 대한 세가지 이야기를 해보면

 

First, although it may be common to see the fuzz input space to contain the expected input space, this is not necessary—it suffices for the former to contain an input not in the latter.

첫째, fuzz input space가 정상적인 동작을 하는 PUT의 인풋영역(the expected input space of PUT)을 포함한다고 보는게 일반적일 수있지만, 이것은 필요하지않다. 전자(fuzz input space)가 후자(expected input space)에 없는 입력을 포함하는 것으로 충분하다.

 

그니까 퍼징을 통해서 하고자하는건 예상치 못한 입력을 넣어 예상치 못한 동작이 있는지 확인해보기 위함이니까, 우리가 퍼징을 위해 생성하고자하는 input 들(fuzz input space)이 정상적으로 동작할 것으로 예상되는 인풋의 범위안에 들든 말든 뭐 딱히 중요하지가 않다. (예상못한 인풋을 넣어서 비정상적인 동작을 유도하면 오히려 땡큐다.)

 

Second, in practice fuzzing almost surely runs for many iterations; thus writing “repeated executions” above would still be largely accurate.

둘째, 실제로 fuzzing을 할때 많은 반복들을 실행한다. 때문에 위의 "반복 실행(repeated executions)"이라는 단어를 쓰는 것은 여전히 대부분 정확하다. 퍼징을 하면 계속해서 새로운인풋 생성, 입력등등의 작업들을 계속해서 반복할 수 밖에 없음. 그래서 "repeated executions" 이라는 표현은 정확한 표현이다.

 

Third, the sampling process is not necessarily randomized, as we will see in §5. Fuzz testing is a form of software testing technique that utilizes fuzzing.

샘플링 프로세스(다음 인풋으로 뭐넣지?를 결정하는 과정)은 반드시 싹 다 무작위는 아니다.. 그림5 에서 볼 수 있듯이, Fuzz testing은 fuzzing을 이용한 소프트웨어 테스트의 한 종류일 뿐이다.

⇒ 샘플링 프로세스 즉, 다음 인풋을 결정하는 과정은 무조건 무작위가 아니고 뭐 커버리지 가이디드 등등 좀 더 효율적으로 샘플을 선택하는 기능이 포함될 수도 있다.

⇒ Fuzz testing과 fuzzing은 다른 뜻이다!! fuzzing 안에 fuzz testing이 있다. 상위어 : fuzzing 하위어 : fuzz testing

 

To differentiate it from others and to honor what we consider to be its most prominent(중요한, 유명한, 눈에 잘띄는, 두드러진, 현저한, 돌출된) purpose, we deem(~로 여기다/생각하다) it to have a specific goal of finding security-related bugs, which include program crashes.

Fuzzer를 다른 프로그램들과 구분하고 정체성을 갖도록 정의하기 위해서, Fuzzer 라는 프로그램의 가장 중요한 목적이 뭔지를 생각해보면 프로그램 crashes를 포함한 보안 관련 버그를 찾는 것이라 생각한다.

 

In addition, we also define fuzzer and fuzz campaign, both of which are common terms in fuzz testing: Definition 2 (Fuzz Testing). Fuzz testing is the use of fuzzing to test if a PUT violates a security policy.

또, fuzzer 와 fuzz campaign도 정의하고 있다. fuzz testing 에서는 이 양쪽 모두를 통용되는 단어(common terms)로 사용하고 있다. 정의 2(fuzz testing) : fuzz testing는 fuzzing을 사용하여 PUT가 보안 정책을 위반하는지 여부를 테스트하는 것이다.

⇒ fuzzing : 대상 프로그램에 랜덤한 인풋값들을 넣는 행위

⇒ fuzz testing : 대상 프로그램에 랜덤한 인풋값들을 넣어, 보안 정책(security policy)을 위반(violate)하는 경우(crash 발생)가 있는지를 검사/테스팅하는 행위

 

Definition 3 (Fuzzer). A fuzzer is a program that performs fuzz testing on a PUT.

정의 3 (Fuzzer) : fuzzer는 PUT에 fuzz testing을 수행하는 프로그램이다.

 

Definition 4 (Fuzz Campaign). A fuzz campaign is a specific execution of a fuzzer on a PUT with a specific security policy.

정의 4 (Fuzz Campaign) : fuzz campaign은 퍼저 실행단위이다. (퍼징 한번 실행했다. ⇒ fuzz campaign 한번 끝냄) 특정한 보안 정책을 가지고 프로그램에 대해 퍼저를 한번 실행시키는 것. 그 실행 자체를 fuzz campaign이라고함

 

The goal of running a PUT through a fuzzing campaign is to find bugs [26] that violate the specified security policy. For example, a security policy employed by early fuzzers tested only whether a generated input—the test case—crashed the PUT.

퍼징 캠페인을 통해 PUT를 실행하는 목적은 지정된 보안 정책을 위반하는 버그를 찾는 것이다. 예를 들어, 초기 퍼저에 의해 채택된 보안 정책은 생성된 입력(테스트 케이스)가 PUT에 crashes 발생시켰는지 여부만 테스트했다.

 

However, fuzz testing can actually be used to test any security policy observable from an execution, i.e., EM-enforceable.

fuzz testing은 실제로 실행에서 관찰할 수 있는 모든 보안 정책, 즉 EM(Execution Monitoring)-enforceable [183]을 테스트하는 데에도 사용될 수 있다.

 

The specific mechanism that decides whether an execution violates the security policy is called the bug oracle.

실행이 보안 정책을 위반하는지 여부를 결정하는 특정 메커니즘을 bug oracle이라고 한다.

* EM-enforceable : 실행했을때 나타날 수 있는 결과에 대해 경우의 수(정상실행, crash, 익스가능, 익스불가능)를 관찰하는거

 

Definition 5 (Bug Oracle). A bug oracle is a program, perhaps as part of a fuzzer, that determines whether a given execution of the PUT violates a specific security policy.

정의 5(Bug Oracle). 버그 오라클은 특정 PUT 실행이 특정 보안 정책을 위반하는지 여부를 판단하는 프로그램이다.

 

We refer to the algorithm implemented by a fuzzer simply as its “fuzz algorithm”. Almost all fuzz algorithms depend on some parameters beyond (the path to) the PUT.

우리는 퍼저에 의해 구현된 알고리즘을 단순히 "fuzz algorithm"이라고 부릅니다. 거의 모든 fuzz algorithm은 PUT(으로의 경로) 너머의 일부 파라미터에 의존한다.

⇒ beyond the path to the PUT : PUT을 실행하기위해 필요한 틀 안에서 바꿀 수 있는 (특정 인풋을 프로그램에 전달할 수 있는 조건을 만족한 상태가 전제되어야 하는 - ex. 드라이버 통신규약을 준수한 상태에서 변경가능한 값만 변경하여 퍼징)의 파라미터에 의존한다.

 

Each concrete setting of the parameters is a fuzz configuration: Definition 6 (Fuzz Configuration).

A fuzz configuration of a fuzz algorithm comprises the parameter value(s) that control(s) the fuzz algorithm.

파라미터의 각 구체적인 설정은 fuzz configuration이다. 정의 6(fuzz configuration) : fuzz algorithm의 fuzz configuration은 fuzz algorithm을 컨트롤하는 파라미터 값을 포함하여 구성되어있다.

 

The definition of a fuzz configuration is intended to be broad. Note that the type of values in a fuzz configuration depend on the type of the fuzz algorithm.

fuzz configuration의 정의는 광범위하도록 의도되어 있다. fuzz configuration의 값 유형은 fuzz algorithm의 유형에 따라 달라집니다.

 

For example, a fuzz algorithm that sends streams of random bytes to the PUT [152] has a simple configuration space {(PUT)}.

예를 들어 랜덤 바이트 스트림을 PUT으로 전송하는 fuzz algorithm에는 단순한 configuration space {(PUT)}이 있다.

 

On the other hand, sophisticated(세련된, 고양있는, 정교한, 복잡한) fuzzers contain algorithms that accept a set of configurations and evolve the set over time—this includes adding and removing configurations.

한편, 고도의 퍼저에는, a set of configurations를 받아 들여, 시간이 지남에 따라 세팅을 진화시키는 알고리즘이 포함되어 있습니다. 이 알고리즘에는 configurations의 추가와 삭제가 포함된다.

⇒ add & remove configurations 는 곧 evolve the set 이다.

 

For example, CERT BFF [49] varies both the mutation ratio and the seed over the course of a campaign, and thus its configuration space is {(PUT, s1, r1),(PUT, s2, r2), . . .}. A seed is a (commonly well-structured) input to the PUT, used to generate test cases by modifying it.

예를 들어 CERT BFF[49]는 campaign의 진행에 따라 mutation ratio(뮤테이션 비율 : mutation ⇒ 새로운 인풋을 만들어내는 행위. 돌연변이)와 seed를 모두 변화시키기 때문에 그 configuration space는 {(PUT, s1, r1), (PUT, s2, r2), ..}이다. 시드는 PUT에 입력된 (일반적으로 잘 구성된) 것으로, 이를 수정하여 테스트 케이스를 생성하기 위해 사용된다.

⇒ 시드를 뮤테이션해서 테스트 케이스를 마구마구 생성해냄

 

Fuzzers typically maintain a collection of seeds, and some fuzzers evolve the collection as the fuzz campaign progresses. This collection is called a seed pool.

퍼저는 일반적으로 a collection of seeds를 유지하며, 일부 퍼저는 fuzz campaign이 진행됨에 따라 collection을 발전시킵니다. 이 collection을 seed pool이라고 합니다.

⇒ 퍼징을 할때마다(fuzzer campaign - 한번 퍼징 실행 할때마다) 시드 모음집을 업데이트 해줌. (오 이 seed pool 기반으로 또 퍼징해봐)

 

Finally, a fuzzer is able to store some data within each configuration. For instance, coverage-guided fuzzers may store the attained coverage in each configuration.

마지막으로 퍼저는 각 configuration 내에서 일부 데이터를 저장할 수 있다. 예를 들어, coverage-guided fuzzers는 도달한 커버리지를 각 Configuration에 저장할 수 있다.

 

2.2 Paper Selection Criteria

To achieve a well-defined scope, we have chosen to include all publications on fuzzing in the last proceedings of 4 major security conferences and 3 major software engineering conferences from Jan 2008 to February 2019.

명확한 범위를 달성하기 위해 2008년 1월부터 2019년 2월까지 4개의 주요 보안 회의와 3개의 주요 소프트웨어 엔지니어링 회의의 마지막 과정에 퍼징에 관한 모든 출판물을 포함하기로 결정했다.

 

For writings that appear in other venues or mediums, we include them based on our own judgment on their relevance. As mentioned in §2.1, fuzz testing only differentiates itself from software testing in that fuzz testing is security related.

다른 장소나 미디어(in other venues or mediums)에 게재된 글의 경우 관련성이 있는지 없는지 우리가 스스로 판단해서 포함할지말지를 정한다. §2.1에서 언급했듯이 fuzz testing은 fuzz testing이 보안과 관련되어 있다(security related)는 점에서 소프트웨어 테스팅과 차별화된다.

 

In theory, focusing on security bugs does not imply a difference in the testing process beyond the selection of a bug oracle. The techniques used often vary in practice, however. When designing a testing tool, access to source code and some knowledge about the PUT are often assumed.

이론적으로 버그에 초점을 맞춘다고 해서 퍼징이나 소프트웨어 테스팅이나 뭐 크게 다른게 아니라 버그 오라클을 선택하는 것 이상에 차이가 있는 것은 아니다. 그러나 실제로 사용되는 기술은 종종 다르다. 테스트 도구를 설계할 때 소스 코드에 대한 접근과 PUT에 대한 일부 지식이 가정되는 경우가 많다.

 

Such assumptions often drive the development of testing tools to have different characteristics compared to those of fuzzers, which are more likely to be employed by parties other than the PUT’s developer. Nevertheless, the two fields are still closely related to one another.

이러한 가정들이 단순 소프트웨어 테스트 도구와 퍼저를 개발할때에 다른 특성을 가지도록 유도한다. 퍼저는 PUT의 개발자 이외의 당사자에 의해 채택될 가능성이 높다. 그럼에도 불구하고, 두 분야는 여전히 밀접하게 연관되어 있다.

⇒ 단순 소프트웨어 테스트 도구는 해당 PUT을 개발하는 사람이 쓸 확률이 높다.

⇒ 퍼저는 꼭 그 개발자가 아니더라도 다른 사람들이 쓸 수도있다. (취약점 탐지를 위해)

 

Therefore, when we are unsure whether to classify a publication as relating to “fuzz testing” and include it in this survey, we follow a simple rule of thumb: we include the publication if the word fuzz appears in it.

따라서 출판물을 "fuzz testing"와 관련된 것으로 분류하여 이 조사에 포함시켜야 할지 확신할 수 없는 경우, 간단한 경험 규칙(주먹구구식 규칙)을 따릅니다. fuzz라는 단어가 나오면 그냥 해당 출판물을 포함한다.

 

2.3 Fuzz Testing Algorithm

We present a generic algorithm for fuzz testing, Algorithm 1, which we imagine to have been implemented in a model fuzzer.

우리는 fuzz testing을 위한 일반적인 알고리즘인 Algorithm 1을 제시합니다. 이 알고리즘은 모델 퍼저에서 구현되었다고 가정합니다.

 

Algorithm 1 : Fuzz Testing

Input: C, tlimit
Output: B // a finite set of bugs
B ← ∅
// C는 fuzz 인풋이 아니라 이번 Fuzz testing fuzz Configurations
C ← PREPROCESS(C)
while telapsed < tlimit ∧ CONTINUE(C) do
	conf ← SCHEDULE(C, telapsed, tlimit)
	// configuration 고려해서 인풋 새로 생성
	tcs ← INPUTGEN(conf)

	// Obug is embedded in a fuzzer
	// 한번 실행했을때 발견된 버그 & 그 인풋이 어떤 결과냈는지 그 정보 던져줌
	B', execinfos ← INPUTEVAL(conf, tcs, Obug)

	// 요번 실행 정보들 이용해서 configuration 업데이트
	C ← CONFUPDATE(C, conf, execinfos)

	B ← B ∪ B'
return B

It is general enough to accommodate existing fuzzing techniques, including black-, grey-, and white-box fuzzing as defined in §2.4.

이 알고리즘 1은 § 2.4에 정의된 바와 같이 블랙, 그레이, 화이트 박스 퍼징을 포함한 기존 퍼징 기법을 다 설명할 수 있을 정도로 일반적이다.

 

Algorithm 1 takes a set of fuzz configurations C and a timeout tlimit as input, and outputs a set of discovered bugs B. It consists of two parts.

알고리즘 1은, fuzz configurations C 와 타임 아웃 tlimit 의 세트를 입력으로서 받아들여, 검출된 버그의 셋인 B를 출력한다. 이건 두 부분으로 구성되어 있다.

 

The first part is the PREPROCESS() function, which is executed at the beginning of a fuzz campaign.

첫 번째 부분은 PREPROCESS() 함수로 fuzz campaign 시작 시 실행된다.

 

The second part is a series of five functions inside a loop: SCHEDULE, INPUTGEN, INPUTEVAL, CONFUPDATE, and CONTINUE. Each execution of this loop is called a fuzz iteration and each time INPUTEVAL executes the PUT on a test case is called a fuzz run.

두 번째 부분은 루프 내부의 5가지 기능(SCHEDULE, INPUTGEN, INPUTEVAL, CONFUPDATE, and CONTINUE)으로 구성되어 있다. 이 루프의 각 실행을 fuzz iteration이라고 하며, INPUTEVAL이 테스트 케이스에서 PUT를 실행하는 것을 fuzz run이라고 한다.

=> fuzz iteration : fuzz testing algorithm에서 루프의 각실행

=> fuzz run : inputeval 함수가 PUT을 한번 실행하는 것

 

Note that some fuzzers do not implement all five functions. For example, to model Radamsa [102], which never updates the set of fuzz configurations, CONFUPDATE always returns the current set of configurations unchanged.

일부 퍼저는 5가지 기능을 모두 구현하지 않는다. 예를 들어, 퍼지 구성을 업데이트하지 않는 Radamsa [ 102 ]모델링을 위해 CONFUPDATE는 항상 현재 set of configurations를 변경하지 않고 반환한다.

⇒ Radamsa : 뮤테이션 알고리즘, 완전 랜덤

 

PREPROCESS (C) → C

PREPROCESS (C) → C A user supplies PREPROCESS () with a set of fuzz configurations as input, and it returns a potentially-modified set of fuzz configurations.

PREPROCESS (C) → C 는 a set of fuzz configurations를 인풋으로 PREPROCESS () 함수를 실행하고 potentially-modified set of fuzz configurations(수정됐을지도 모르는 fuzz configuration)을 결과로 받아서 C에 넣어준다.

 

Depending on the fuzz algorithm, PREPROCESS () may perform a variety of actions such as inserting instrumentation code to PUTs, or measuring the execution speed of seed files. See §3.

fuzz algorithm에 따라 PREPROCESS()는 PUT에 instrumentation code를 삽입하거나 시드 파일의 실행 속도를 측정하는 등의 다양한 작업을 수행할 수 있다.

⇒ instrumentation : 코드 커버리지 측정을 위해 필요한 코드. 예를들어 이 코드 실행여부로 프로그램 실행흐름을 추적함.

 

conf ← SCHEDULE(C, telapsed, tlimit)

conf ← SCHEDULE(C, telapsed, tlimit) takes in the current set of fuzz configurations, the current time telapsed, and a timeout tlimit as input, and selects a fuzz configuration to be used for the current fuzz iteration. See §4.

현재 퍼지 구성 세트, 현재 시간 및 타임아웃 tlimit을 입력으로 받아들여 현재 fuzz iteration에 사용할 fuzz configuration을 선택한다.

tcs ← INPUTGEN(conf)

tcs ← INPUTGEN(conf) takes a fuzz configuration as input and returns a set of concrete test cases tcs as output.

fuzz configuration을 입력으로 사용하고 a set of concrete test cases를 출력으로 반환한다.

 

When generating test cases, INPUTGEN() uses specific parameter(s) in conf. Some fuzzers use a seed in conf for generating test cases, while others use a model or grammar as a parameter. See §5.

test cases를 생성할 때 INPUTGEN()은 conf에서 특정 파라미터를 사용합니다. 일부 퍼저는 test cases를 생성하기 위해 conf에서 시드를 사용하는 반면 어떤 퍼저는 model or grammar을 매개 변수로 사용한다. § 5를 참조해 주세요.

 

⇒ test case 생성할때 conf 에서 시드나 model 혹은 문법을 고려해서 생성함

 

B', execinfos ← INPUTEVAL(conf, tcs, Obug)

B', execinfos ← INPUTEVAL(conf, tcs, Obug) takes a fuzz configuration conf, a set of test cases tcs, and a bug oracle Obug as input.

fuzz configuration conf, a set of test cases tcs 및 bug oracle Obug를 입력으로 받아들인다.

 

It executes the PUT on tcs and checks if the executions violate the security policy using the bug oracle Obug. It then outputs the set of bugs found B′ and information about each of the fuzz runs execinfos, which may be used to update the fuzz configurations.

tcs 로 PUT를 실행하여 bug oracle Obug를 사용하여 실행이 보안 정책을 위반하는지 여부(크래시 발생여부)를 확인합니다. 다음으로 발견된 B'의 버그 세트와 각 퍼지 실행 execinfo에 대한 정보를 출력한다. 이 정보는 fuzz configurations 갱신에 사용할 수 있다.

 

We assume Obug is embedded in our model fuzzer. See §6.

Obug는 우리 모델 퍼저에 포함되어있다고 가정

=> bug oracle : 실행이 보안 정책을 위반하는지 여부를 결정하는 특정 메커니즘. 크래시 여부 판단 알고리즘

C ← CONFUPDATE(C, conf, execinfos)

CONFUPDATE() takes a set of fuzz configurations C, the current configuration conf, and the information about each of the fuzz runs execinfos, as input. It may update the set of fuzz configurations C.

CONFUPDATE()는 a set of fuzz configurations C, 현재 configuration Conf 및 각 fuzz runs 정보에 대한 execinfo를 입력으로 사용한다.CONFUPDATE() 를 실행하면 fuzz configurations set C 를 갱신할 수 있다.

 

For example, many grey-box fuzzers reduce the number of fuzz configurations in C based on execinfos. See §7.

예를 들어, 많은 그레이 박스퍼저는execinfo를 기반으로 C의 fuzz configurations를 줄인다.

⇒ fuzz configuration이 줄어들면 좋은 것. 해당 specific한 PUT에 적합한 구성을 찾아간다는 뜻이니까

 

CONTINUE(C)

CONTINUE(C) takes a set of fuzz configurations C as input and outputs a boolean indicating whether a new fuzz iteration should occur. This function is useful to model white-box fuzzers that can terminate when there are no more paths to discover.

일련의 fuzz configurations C 를 입력으로 하여 새로운 fuzz iteration이 발생할지 여부를 나타내는 참 거짓을 출력한다. 이 기능은 검색할 경로가 더 이상 없을 때 종료될 수 있는 화이트 박스 퍼저를 모델링하는 데 유용하다.

 

2.4 Taxonomy of Fuzzers

For this paper, we have categorized fuzzers into three groups based on the granularity of semantics a fuzzer observes in each fuzz run. These three groups are called black-, grey-, and white-box fuzzers, which we define below.

이 논문에서, 우리는 퍼저가 각 fuzz run에서 관찰하는 의미론의 세분성을 기반으로 퍼저를 세 개의 그룹으로 분류했다. 이 세 가지 그룹을 블랙, 그레이 및 화이트 박스 퍼저라고 합니다.이러한 그룹을 이하에서 정의합니다.

 

Note that this classification is different from traditional software testing, where there are only two major categories (black and white-box testing) [158]. As we will discuss in §2.4.3, grey-box fuzzing is a variant of white-box fuzzing that can only obtain some partial information from each fuzz run.

이 분류는 두 가지 주요 범주(black and white-box testing)가 있는 기존 소프트웨어 테스트와는 다르다[158]. § 2.4.3에서 설명하듯이 grey-box fuzzing은 white-box fuzzing의 변형으로 각 퍼징에서 일부 정보만 얻을 수 있다.

 

 

2.4.1 Black-box Fuzzer

The term “black-box” is commonly used in software testing [158], [32] and fuzzing to denote techniques that do not see the internals of the PUT—these techniques can observe only the input/output behavior of the PUT, treating it as a black-box.

"블랙박스"라는 용어는 소프트웨어 테스트 [158], [32] 및 퍼징에서 PUT의 내부가 보이지 않는 기술을 나타내기 위해 일반적으로 사용된다. 이러한 기술은 PUT의 입력/출력 동작만 관찰할 수 있으며 블랙박스로 취급할 수 있다.

 

In software testing, black-box testing is also called IO-driven or data-driven testing [158]. Most traditional fuzzers [13], [103], [49], [6], [50] are in this category.

소프트웨어 테스트에서 블랙박스 테스트는 IO 기반 또는 데이터 기반 테스트라고도 한다[158]. 대부분의 전통적인 퍼저[13], [103], [49], [6], [50]가 이 범주에 속한다.

 

Some modern fuzzers, e.g., funfuzz [187] and Peach [76], also take the structural information about inputs into account to generate more meaningful test cases while maintaining the characteristic of not inspecting the PUT.

Funfuzz [187] 및 Peach [76]와 같은 일부 현대 퍼저는 PUT를 검사하지 않는 특성을 유지하면서 보다 의미 있는 테스트 케이스를 생성하기 위해 입력에 대한 구조 정보(the structural information about inputs)를 고려한다.

 

A similar intuition is used in adaptive random testing [57].

적응형 무작위 테스트(adaptive random testing)에서도 유사한 직관이 사용된다 [57].

적응형 랜덤 테스트는 입력 공간 내에서 테스트 케이스를 보다 균등하게 분배하는 것을 목표로 한다. non-point types of failure patterns의 경우, 테스트 케이스의 균등 분포가 일반적인 무작위 테스트보다 적은 테스트 케이스를 사용하여 고장을 탐지할 가능성이 높다는 직관에 기초한다.

 

2.4.2 White-box Fuzzer

At the other extreme of the spectrum, white-box fuzzing [90] generates test cases by analyzing the internals of the PUT and the information gathered when executing the PUT. Thus, white-box fuzzers are able to explore the state space of the PUT systematically.

스펙트럼의 다른 극단(블랙 박스 퍼징과 반대로)에서 화이트 박스 퍼징[90]은 PUT의 내부와 PUT 실행 시 수집된 정보를 분석하여  테스트 케이스를 생성한다. 따라서 화이트 박스 퍼저는 PUT의 상태 공간(state space)을 체계적으로 탐색할 수 있습니다.

 

The term white-box fuzzing was introduced by Godefroid [87] in 2007 and refers to dynamic symbolic execution (DSE), which is a variant of symbolic execution [39], [126], [108].

화이트 박스 퍼징이라는 용어는 Godefroid[87]에 의해 2007년에 도입되었으며 symbolic execution의 변형인 Dynamic Symbolic Execution(DSE)을 의미한다[39], [126], [108].

 

In DSE, symbolic and concrete execution operate concurrently, where concrete program states are used to simplify symbolic constraints, e.g., concretizing system calls.

DSE에서는 심볼릭과 구체적인(concrete) 실행이 동시에 작동하며, 구체적인 프로그램 states는 symbolic constraints(예: 시스템 호출 구체화)을 단순화하기 위해 사용됩니다.

 

DSE is thus often referred to as concolic testing (concrete + symbolic) [191], [89]. In addition, white-box fuzzing has also been used to describe fuzzers that employ taint analysis [84]. The overhead of white-box fuzzing is typically much higher than that of black-box fuzzing.

따라서 DSE는 종종 concolic testing (concrete + symbolic)로 언급된다[191], [89]. 또한 화이트 박스 퍼징은 taint analysis을 사용하는 퍼저를 설명하는 데에도 사용되었다[84]. 화이트 박스 퍼징의 오버헤드는 일반적으로 블랙 박스 퍼징의 오버헤드보다 훨씬 높다. (⇒ 고려할 정보가 많아서)

 

This is partly because DSE implementations [90], [46], [25] often employ dynamic instrumentation and SMT solving [155]. While DSE is an active research area [90], [88], [38], [172], [112], many DSEs are not white-box fuzzers because they do not aim to find security bugs.

이는 부분적으로 DSE 구현 [90], [46], [25]에서 dynamic instrumentation과 SMT 해결[155]을 사용하는 경우가 많기 때문이다. DSE는 [90], [88], [38], [172], [112]의 활성 연구 영역이지만, 많은 DSE는 보안 버그를 찾는 것을 목적으로 하지 않기 때문에 화이트 박스 퍼저가 아니다.

⇒ SMT?? SMT는 Simultaneous Multi-Threading(동시 멀티스레딩)의 약자로, 말 그대로 여러 개의 스레드들이 동시에 동작하는 멀티스레딩이다.

 

As such, this paper does not provide a comprehensive survey on DSEs and we refer the reader to recent survey papers [17], [185] for more information on DSEs for non-security applications.

따라서, 이 논문는 DSE에 대한 포괄적인 조사를 제공하지 않으며, 비보안 애플리케이션의 DSE에 대한 자세한 내용은 최근 논문[17], [185]를 참조하라.

 

2.4.3 Grey-box Fuzzer

Some fuzzers [78], [68], [205] take a middle ground approach which is dubbed grey-box fuzzing. In general, greybox fuzzers can obtain some information internal to the PUT and/or its executions. Unlike white-box fuzzers, greybox fuzzers do not reason about the full semantics of the PUT; instead, they may perform lightweight static analysis on the PUT and/or gather dynamic information about its executions, such as code coverage.

일부 퍼저[78], [68], [205]는 그레이 박스 퍼저라고 불리는 화이트-블랙의 중간 접근 방식을 취한다. 일반적으로 그레이박스 퍼저는 PUT 및/또는 그 실행에 관한 내부 정보를 얻을 수 있다. 화이트 박스 퍼저와 달리 그레이 박스 퍼저는 PUT의 완전한 의미론(semantics ⇒ 알고있는게 화박퍼)에 대해 추론하지 않는다. 대신 PUT에 대해 경량 정적 분석(lightweight static analysis)을 수행하거나 코드 커버리지와 같은 실행에 대한 동적 정보를 수집할 수 있다.

 

Grey-box fuzzers rely on approximated, imperfect information in order to gain speed and be able to test more inputs. Although there usually is a consensus between security experts, the distinction between black-, grey- and white-box fuzzing is not always clear.

회색 상자 퍼저는 속도를 높이고 더 많은 입력을 테스트하기 위해 대략적이고 불완전한 정보(⇒ full semantics와 반대되는 말)에 의존한다. 일반적으로 보안 전문가들 사이에 공감대가 형성되지만 블랙박스, 그레이박스, 화이트박스 퍼징의 구별이 항상 명확하지는 않다.

 

Black-box fuzzers may collect some information about fuzz runs, and white-box fuzzers often use some approximations. When classifying the fuzzers in this survey, particularly in Table 1, we used our best judgement.

블랙박스 퍼저는 퍼즈런에 대한 정보를 수집할 수 있으며 화이트박스 퍼저는 종종 근사치를 사용한다. 이 조사, 특히 표 1에서 퍼저를 분류할 때 최선의 판단을 사용했다.

 

An early example of grey-box fuzzer is EFS [68], which uses code coverage gathered from each fuzz run to generate test cases with an evolutionary algorithm.

회색 상자 퍼저의 초기 예는 EFS[68]이며, 각 퍼즈 실행에서 수집된 코드 커버리지를 사용하여 진화 알고리즘으로 테스트 케이스를 생성한다.

 

Randoop [166] also used a similar approach, though it did not target security vulnerabilities. Modern fuzzers such as AFL [231] and VUzzer [176] are exemplars in this category.

Randoop [ 166 ]또한 유사한 접근방식을 사용했지만 보안 취약점을 대상으로 하지는 않았다. AFL [231] 및 VUzzer [176]와 같은 최신 퍼저가 이 범주의 예이다.

2.5 Fuzzer Genealogy and Overview

Figure 1 (p. 5) presents our categorization of existing fuzzers in chronological order. Starting from the seminal work by Miller et al. [152], we manually chose popular fuzzers that either appeared in a major conference or obtained more than 100 GitHub stars, and showed their relationships as a graph.

그림 1(페이지 5)은 기존 퍼저의 분류를 시간순으로 제시한다. 밀러 외 연구진의 앞으로 전개되는 연구들에 영향력이 컸던 연구부터 시작한다. [152] 메이저 컨퍼런스에 출연하거나 100개 이상의 GitHub 스타를 획득한 인기 퍼저를 수작업으로 선택해, 그 관계를 그래프로 나타냈다.

 

Black-box fuzzers are in the left half of the figure, and greyand white-box fuzzers are in the right half. Furthermore, fuzzers are subdivided depending on the type of input the PUT uses: file, network, UI, web, kernel I/O, or threads (in the case of concurrency fuzzers).

블랙박스 퍼저는 그림의 왼쪽 절반에, 회색과 흰색 박스 퍼저는 오른쪽 절반에 있습니다. 또한 퍼저는 파일, 네트워크, UI, 웹, 커널 I/O, 스레드(동시 퍼저의 경우) 등 PUT가 사용하는 입력 유형에 따라 세분화된다.

 

Table 1 (p. 6) presents a detailed summary of the techniques used in the most notable fuzzers in Figure 1. We had to omit some of fuzzers in Figure 1 due to space constraints.

표 1(p. 6)은 그림 1의 가장 주목할 만한 퍼저에 사용된 기법의 상세 요약을 보여준다. 공간 제약으로 인해 그림 1의 퍼저 중 일부를 생략해야 했다.

 

Each fuzzer is summarized based on its implementation of the five functions of our model fuzzer, and a miscellaneous(⇒ 여러가지 잡다한) section that provides other details on the fuzzer.

각 퍼저는 모델 퍼저의 5가지 기능구현과 기타 퍼저에 대한 상세 내용을 제공하는 여러 가지 잡다한 섹션을 바탕으로 요약되어 있다.

 

We describe the properties described by each column below. The first column (feedback gathering granularity) indicates whether the fuzzer is black- ( ), white- (#), or grey-box (H#). Two circles appear when a fuzzer has two phases which use different kinds of feedback gathering.

아래 각 열에서 설명하는 속성을 설명한다. 첫 번째 열(피드백 수집 조각)은 퍼저가 black((), white(#), grey-box(H#) 중 어느 쪽인지 나타낸다. 퍼저에 다른 종류의 피드백 수집을 사용하는 두 개의 단계가 있을 때 두 개의 원이 나타난다.

⇒ granularity : 과립 또는 곡물에 존재하는 상태 인 Granularity는 재료 또는 시스템이 구별 가능한 조각으로 구성되는 정도. 낟알 모양, 입자

 

For example, SymFuzz [52] runs a white-box analysis as a preprocessing step in order to optimize the performance of a subsequent black-box campaign ( +#), and hybrid fuzzers, such as Driller [200], alternate between white- and greybox fuzzing (H#+#).

예를 들어 SymFuzz[52]는 black-box 캠페인(+#)의 성능을 최적화하기 위해 white-box 분석을 전처리 단계로 실행하고 Driller [200]와 같은 하이브리드 fuzzer(H#+#)는 white-box 퍼징과 grey-box 퍼징을 번갈아 수행한다.

 

The second column shows whether the source code of the fuzzer is publicly available.

두 번째 열은 퍼저의 소스 코드를 공개적으로 사용할 수 있는지 여부를 나타낸다.

The third column denotes whether fuzzers need the source code of the PUT to operate.

세 번째 열은 퍼저가 작동하기 위해 PUT의 소스 코드가 필요한지 여부를 나타낸다.

The fourth column points out whether fuzzers support in-memory fuzzing (see §3.1.2).

네 번째 열은 퍼저가 메모리 내 퍼징(in-memory fuzzing)을 지원하는지 여부를 나타낸다(제3.1.2항 참조).

The fifth column is about whether fuzzers can infer models (see §5.1.2).

다섯 번째 열은 퍼저가 모델을 추론(infer models)할 수 있는지 여부에 관한 것이다(제5.1.2조 참조).

The sixth column shows whether fuzzers perform either static or dynamic analysis in PR E P R O C E S S.

여섯 번째 열은 퍼저가 PR E P R O C E S에서 정적 또는 동적 분석을 수행하는지 여부를 나타낸다.

The seventh column indicates if fuzzers support handling multiple seeds, and perform scheduling. The mutation column specifies if fuzzers perform input mutation to generate test cases.

일곱 번째 열은 퍼저가 여러 시드 처리를 지원하는지 여부 및 스케줄링을 수행하는지 여부를 나타낸다. mutation 컬럼은 퍼저가 입력 변환을 실행하여 테스트 케이스를 생성하는지 여부를 지정한다.

 

 

We use H# to indicate fuzzers that guide input mutation based a on the execution feedback. The model-based column is about whether fuzzers generate test cases based on a model.

실행 피드백에 따라 입력 변환을 유도하는 퍼저를 나타내기 위해 H#을 사용한다. 모델 기반 열은 퍼저가 모델을 기반으로 테스트 케이스를 생성하는지 여부에 대한 것이다.

 

The constraint-based column shows that fuzzers perform a symbolic analysis to generate test cases. The taint analysis column means that fuzzers leverage taint analysis to guide their test case generation process.

제약 조건(constraint) 기반 열은 퍼저가 테스트 케이스를 생성하기 위해 symbolic analysis를 수행함을 보여준다. 오염 분석(taint analysis) 열은 퍼저가 오염 분석을 활용하여 테스트 사례 생성 프로세스를 안내한다는 것을 의미한다.

 

The two columns in the IN P U TEV A L section show whether fuzzers perform crash triage using either stack hashing or code coverage.

INPUTEVAL 섹션의 2열은, 퍼저가 stack hashing 또는 코드 커버리지 중 무엇을 사용해 crash triage를 실행할지를 나타내고 있다.

⇒ triage : 우선순위 결정. crash triage 에는 충돌을 추가로 조사할 가치가 있는지(보안 연구가의 경우 일반적으로 crash가 취약점으로 인한 것인지 여부를 결정하는 것을 의미함)을 결정하기 위해 fuzzer에서 발견한 각 crash를 검사하는 것이 포함된다.

 

The first column of the CO N FUP D A T E section indicates if fuzzers evolve the seed pool during CO N FUP D A T E, such as adding new seeds to the pool (see §7.1).

CO N FUP D A TE 섹션의 첫 번째 열은 풀장에 새로운 시드를 추가하는 등 CO N FUP D A TE 동안 퍼저가 시드 풀을 진화시키는지 여부를 나타낸다(제7.1절 참조).

 

The second column of the CO N FUP D A T E section is about whether fuzzers learn an input model in an online fashion(⇒ 손으로 빚다).

CO N FUP D A TE 섹션의 두 번째 열은 퍼저가 온라인 방식으로 입력 모델을 학습하는지 여부에 대한 것이다.

 

Finally, the third column of the CO N FUP D A T E section shows which fuzzers remove seeds from the seed pool (see §7.2).

마지막으로, CO N FUP D A TE 섹션의 세 번째 열은 어떤 퍼저가 시드 풀에서 seed을 제거하는지 보여준다(제7.2절 참조).