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

5 INPUT GENERATION

Since the content of a test case directly controls whether or not a bug is triggered, the technique used for input generation is naturally one of the most influential design decisions in a fuzzer.
Test Case 의 내용에 따라 버그가 트리거 되는지 여부가 직접적으로 결정되기 때문에, input generation은 퍼저에서 가장 중요한 design decision이다.

Traditionally, fuzzers are categorized into either generation- or mutation-based fuzzers.
전통적으로 fuzzer는 1. generation-based fuzzer 2. mutation-based fuzzer로 분류된다.

Generation based fuzzers produce test cases based on a given model that describes the inputs expected by the PUT. We call such fuzzers model-based fuzzers in this paper.
Generation based fuzzers 에서는 주어진 Model이 PUT에 의해 예상되는 입력을 알려주고 이를 기반으로 Test Case를 생성한다. 우리는 그런 fuzzer를 model-based fuzzers라고 부른다.

On the other hand, mutation-based fuzzers produce test cases by mutating a given seed input. Mutation-based fuzzers are generally considered to be model-less because seeds are merely example inputs and even in large numbers they do not completely describe the expected input space of the PUT.
반면에 mutation-based fuzzers는 주어진 seed input을 mutating 하여 Test Case를 생성한다. 이 때 seed는 입력의 예시이고 seed가 아무리 많더라도 모든 PUT의 예상 입력 공간을 전부 설명해주지는 못하기 때문에 Mutation-based fuzzer는 일반적으로 Model이 없는 것으로 간주된다.

In this section, we explain and classify the various input generation techniques used by fuzzers based on the underlying test case generation (INPUTGEN) mechanism.
이 섹션에서는 기본 test case 생성(INPUTGEN) 메커니즘을 기반으로 퍼저가 사용하는 다양한 입력값 생성 기술을 설명하고 분류한다.

• generation-based fuzzer(model-based fuzzer)
  • PUT의 입력 형태를 고려한 Model 있음
  • model이 PUT에 의해 예상되는 입력을 알려주고 이를 이용해서 test case를 생성함
• mutation-based fuzzer
  • 일반적으로 PUT의 입력 형태를 고려한 모델이 없다고 간주
  • seed를 mutation하여 인풋을 생성함

5.1 Model-based (Generation-based) Fuzzers

Model-based fuzzers generate test cases based on a given model that describes the inputs or executions that the PUT may accept, such as a grammar precisely characterizing the input format or less precise constraints such as magic values identifying file types.
Model-based fuzzers는 PUT이 받아들일 수 있는 입력 또는 실행을 설명할 수 있는 주어진 Model을 기반으로 test case를 생성한다. 이 Model은 예를 들어 입력 형식을 정확하게 characterizing 하는 문법이나 파일 type을 식별하는 magic value와 같이 덜 정확한 제약조건(less precise constraints) 같은 것이다.

5.1.1 Predefined Model

Some fuzzers use a model that can be configured by the user. For example, Peach [76], PROTOS [120], and Dharma [3] take in a specification provided by the user.
일부 fuzzer는 사용자가 구성할 수 있는 Model을 사용흔다. 예를 들어 Peach [76], PROTOS [120] 및 Dharma [3]는 사용자가 제공한 규격(specification provided by the user)을 사용한다.

Autodaf´e [214], Sulley [16], SPIKE [13], and SPIKEfile [202] expose APIs that allow analysts to create their own input models. Tavor [240] also takes in an input specification written in Extended Backus-Naur form (EBNF) and generates test cases conforming to the corresponding grammar.
Autodaf'e [214], Sulley [16], SPIKE [13] 및 SPIKE 파일 [202]은 분석가가 자체 입력 Model 을 만들 수 있는 API를 노출한다.
Tavor [240]은 또한 확장 백커스-나우르 형식(EBNF)으로 작성된 입력 규격을 받아들여 해당 문법에 부합하는 test case를 생성한다.

• EBNF (Extended Backus-Naur form )
  • 컴퓨터 과학 에서 EBNF ( Extended Backus-Naur form ) 는 메타 구문 표기법 계열이며 , 그 중 어떤 것이든 컨텍스트 없는 문법을 표현하는 데 사용할 수 있음 . EBNF는 컴퓨터 프로그래밍 언어 와 같은 형식 언어 를 형식적으로 설명하는 데 사용됨 .
  Extended Backus-Naur form - Wikipedia

Similarly, network protocol fuzzers such as PROTOS [120], SNOOZE [29], KiF [12], and T-Fuzz [114] also take in a protocol specification from the user. Kernel API fuzzers [115], [216], [157], [162], [221] define an input model in the form of system call templates.
마찬가지로, PROTOS [120], SNOZE [29], KiF [12] 및 T-Fuzz [114]와 같은 네트워크 프로토콜 fuzzer도 사용자로부터 프로토콜 사양을 받아들인다. 커널 API fuzzer [115], [216], [157], [162], [221]은 System call 템플릿의 형태로 입력 Model을 정의한다.

These templates commonly specify the number and types of arguments a system call expects as inputs.
이러한 템플릿은 일반적으로 system call이 예상하는 argument의 수와 type을 입력으로 지정한다.
=> argument와 parameter의 차이점

• Argument는 함수 혹은 메서드를 호출할 때, 전달 혹은 입력되는 실제 값.단어 번역 의미
• Parameter는 함수 혹은 메서드 정의에서 나열되는 변수 명.

Parameter	매개변수	함수와 메서드의 입력 변수(Variable) 명
Arguemtn	인자, 전달인자	함수와 메서드의 입력 값(Value)

The idea of using a model in kernel fuzzing originated in Koopman et al.’s seminal work where they compared the robustness of OSes with a finite set of manually chosen test cases for system calls.
커널 fuzzing에서 Model을 사용하는 아이디어는 System call을 위해 수동으로 선택한 test case와 OS의 견고성(robustness of OSes)을 비교한 Koopman 등의 주요 연구에서 비롯되었다.

Nautilus employs grammar-based input generation for general-purpose fuzzing, and also uses its grammar for seed trimming (see §3.3).
Nautilus는 범용 목적의 fuzzing(general-purpose fuzzing)을 위해 문법 기반 입력 생성을 사용하고 seed trimming을 위해 문법을 사용한다(제3.3 참조).

• seed trimming → seed 크기 줄이기
• 시드가 작을수록 메모리는 더 적게 소비하고, 더 높은 throughput을 유도한다. 따라서 어떤 퍼저는 퍼징을 하기 전에 먼저 시드의 크기를 줄인다. 이런 기술을 seed trimming 이라고 한다. 시드 트리밍은 PREPROCESS에서 메인 fuzzing loop을 수행하기 전에 수행되거나, CONFUPDATE의 일부분으로 수행된다.

Other model-based fuzzers target a specific language or grammar, and the model of this language is built in to the fuzzer itself. For example, cross fuzz [232] and 10 DOMfuzz [187] generate random Document Object Model (DOM) objects. Likewise, jsfunfuzz [187] produces random, but syntactically correct JavaScript code based on its own grammar model.
다른 model 기반 fuzzer는 특정 언어 또는 문법을 대상으로 하며, 이 언어의 model은 fuzzer 자체에 내장되어 있다. 예를 들어, cross fuzz [232] 및 10 DOM 퍼지 [187]는 랜덤 문서 객체 모델(DOM) 객체를 생성한다. 마찬가지로, jsfunfuzz [187]는 자체 문법 model을 기반으로 랜덤이지만 구문상으로는 정확한 자바스크립트 코드를 생성한다.

QuickFuzz [94] utilizes existing Haskell libraries that describe file formats when generating test cases.
QuickFuzz [94]는 테스트 케이스를 생성할 때 파일 형식(format)을 설명하는 기존 Haskell 라이브러리를 활용한다.

Some network protocol fuzzers such as Frankencerts [41], TLS-Attacker [195], tlsfuzzer [124], and llfuzzer [198] are designed with models of specific network protocols such as TLS and NFC.
Francerts [41], TLS-Attacker [195], TLS-Attacker [124] 및 llfuzer [198]와 같은 일부 네트워크 프로토콜 fuzzer는 TLS 및 NFC와 같은 특정 네트워크 프로토콜의 model로 설계된다.

Dewey et al. [69], [70] proposed a way to generate test cases that are not only grammatically correct, but also semantically diverse by leveraging constraint logic programming.
듀이 외 [69], [70]은 제약 논리 프로그래밍을 활용하여 문법적으로 정확할 뿐만 아니라 의미적으로 다양한 test case를 생성하는 방법을 제안했다.

LangFuzz [105] produces code fragments by parsing a set of seeds that are given as input. It then randomly combines the fragments, and mutates seeds with the fragments to generate test cases.
LangFuzz [105]는 입력으로 제공되는 seed 세트를 파싱하여 코드 조각을 생성한다. 그런 다음 조각들을 무작위로 결합하고, seed를 코드 조각들과 mutate시켜 test case를 생성한다.

Since it is provided with a grammar, it always produces syntactically correct code.
LangFuzz was applied to JavaScript and PHP.
문법과 함께 제공되기 때문에 항상 구문적으로 올바른 코드를 생성한다.
LangFuzz는 자바스크립트와 PHP에 적용되었다.

BlendFuzz [229] is based on similar ideas as LangFuzz, but targets XML and regular expression parsers.
BlendFuzz [229]는 LangFuzz와 유사한 아이디어를 기반으로 하지만 XML 및 정규 표현식 파서를 대상으로 한다.

5.1.2 Inferred Model

Inferring the model rather than relying on a predefined or user-provided model has recently been gaining traction.
사전에 정의되거나 사용자가 제공한 model에 의존하지 않고 model을 추론하는 것이 최근 주목을 받고 있다.
⇒ 미리 모델을 정하지 않고, 모델을 찾아가는 방식이 주목을 받고 있음.

Although there is an abundance of published research on the topic of automated input format and protocol reverse engineering [66], [45], [141], [63], [28], only a few fuzzers leverage these techniques.
자동화된 입력 형식(포맷)과 프로토콜 리버스 엔지니어링의 주제에 대해 발표된 연구가 풍부하지만, [66], [45], [141], [63], [28]처럼 이러한 기법을 활용하는 퍼저가 많지는 않다.

Similar to instrumentation (§3.1), model inference can occur in either PREPROCESS or CONFUPDATE.
instrumentation(§ 3.1)과 유사하게 model 추론은 PREPROCESS 또는 CONFUPDATE에서 발생할 수 있다.

5.1.2.1 Model Inference in PREPROCESS:

Some fuzzers infer the model as a preprocessing step. TestMiner [67] searches for the data available in the PUT, such as literals, to predict suitable inputs. Given a set of seeds and a grammar, Skyfire [217] uses a data-driven approach to infer a probabilitistic context-sensitive grammar, and then uses it to generate a new set of seeds.
일부 fuzzer는 Model을 전처리 단계(preprocessing step)에서 추론한다. TestMiner는 적절한 입력을 예측하기 위해 Literal과 같이 PUT에서 사용할 수 있는 데이터를 검색한다. seed set와 문법이 주어지면 Skyfire는 데이터 기반 접근 방식을 사용하여 확률론적 문맥 의존 문법을 추론한 다음 이를 사용하여 새로운 시드 집합을 생성한다.
⇒ 어떤 형태로 입력받는지 모르니까 PUT안에서 사용하는 데이터 뭐가있는지 검색하고 확률론적 문맥에 따른 문법 추론(infer a probabilitistic context-sensitive grammar)하여 새로운 시드 집합을 생성한다.
Unlike previous works, it focuses on generating semantically valid inputs. IMF [99] learns a kernel API model by analyzing system API logs, and it produces C code that invokes a sequence of API calls using the inferred model.
이전 작업들과 달리, 이는 의미적으로 유효한 입력(semantically valid inputs)을 생성하는데 중점을 둔다. IMF는 시스템 API 로그를 분석하여 커널 API 모델을 학습하고, 추론된 모델을 사용하여 일련의 API 호출을 호출하는 C 코드를 생성한다.

CodeAlchemist breaks JavaScript code into “code bricks”, and computes assembly constraints, which describe when distinct bricks can be assembled or merged together to produce semantically valid test cases. These constraints are computed using both a static analysis and dynamic analysis.
CodeAlchemist은 자바스크립트 코드를 "code bricks"로 분할하고 어셈블리 제약조건을 계산한다. 이 어셈블리 제약조건은 의미론적으로 유효한 test case를 생성하기 위해 서로 다른 brick을 조립하거나 병합할 수 있는 지를 설명한다. 이러한 제약 조건은 정적 분석과 동적 분석을 모두 사용하여 계산한다.

Neural [62] and Learn&Fuzz [91] use a neural network-based machine learning technique to learn a model from a given set of test files, and generate test cases from the inferred model. Liu et al. [142] proposed a similar approach specific to text inputs.
Neural와 Learn&Fuzz는 신경망 기반 기계 학습 기술을 사용하여 주어진 테스트 파일 세트에서 모델을 학습하고, 추론된 Model에서 test case를 생성한다. Liu외 연구진은 특정한 텍스트 입력에 유사한 접근 방식을 제안했다.

5.1.2.2 Model Inference in CONFUPDATE:

Other fuzzers can potentially update their model after each fuzz iteration. PULSAR [85] automatically infers a network protocol model from a set of captured network packets generated from a program.
다른 fuzzer는 각각의 fuzz 반복 후에 잠재적으로 모델을 업데이트할 수 있다. PULSAR [85]는 프로그램에서 생성된 캡처된 네트워크 패킷 셋으로부터 네트워크 프로토콜 model을 자동으로 추론한다.

The learned network protocol is then used to fuzz the program. PULSAR internally builds a state machine, and maps which message token is correlated with a state. This information is later used to generate test cases that cover more states in the state machine.
학습된 네트워크 프로토콜은 프로그램을 퍼징하는 데 사용된다. PULSAR는 내부적으로 state machine를 구축하고 어떤 메시지 토큰이 상태와 상관관계가 있는지(which message token is correlated with a state) 매핑한다. 이 정보는 나중에 상태 시스템의 더 많은 상태를 다루는 test case를 생성하는 데 사용한다.

Doup´e et al. [73] propose a way to infer the state machine of a web service by observing the I/O behavior. The inferred model is then used to scan for web vulnerabilities. The work of Ruiter et al. [180] is similar, but targets TLS and bases its implementation on LearnLib [174]. GLADE [30] synthesizes a context-free grammar from a set of I/O samples, and fuzzes the PUT using the inferred grammar.
Doup'et. [73] 입출력 동작을 관찰하여 웹 서비스의 state machine를 추론하는 방법을 제안한다. 그런 다음 추론된 모델을 사용하여 웹 취약잠을 검색한다. Ruiter 등의 작업 [180]은 유사하지만 TLS를 대상으로 하며 LearnLib [174]를 기반으로 구현된다. GLADE [30]는 일련의 I/O 샘플에서 context-free 문법을 합성하고, 추론된 문법을 사용하여 PUT를 fuzz 한다.

Finally, go-fuzz [215] is a greybox fuzzer, which builds a model for each of the seed it adds to its seed pool. This model is used to generate new inputs from this seed.
마지막으로, go-fuzz [215]는 grey-box fuzzer로, seed pool에 추가하는 각각의 seed model을 구축한다. 이 model은 seed를 이용해서 새 입력을 생성한다.