[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey (2) Systemization, Taxonomy and Test Programs

[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey

원문 : https://arxiv.org/abs/1812.00140

---

[목차]

2. Systemization, Taxonomy and Test Programs

2.1 Fuzzing & Fuzz Testing

2.2 Paper Selection Criteria

2.3 Fuzz Testing Algorithm

2.4 Taxonomy of Fuzzers

2.4.1 Black-box Fuzzer

2.4.2 White-box Fuzzer

2.4.3 Grey-box Fuzzer

2.5 Fuzzer Genealogy and Overview

---

2. Systemization, Taxonomy and Test Programs

fuzz라는 용어는 Miller 교수가 타겟 프로그램에서 사용할 랜덤한 character stream을 생성하는 프로그램을 지칭하기 위해 만들었다. 그 이후로 fuzz라는 개념과 그 동작인 fuzzing은 아래처럼 여러 context에서 다양하게 해석된다.

dynamic symbolic execution grammarbased test case generation permission testing behavioral testing complexity testing kernel testing representation dependence testing function detection robustness evaluation exploit development GUI testing signature generation penetration testing

방대한 퍼징 문헌의 지식을 체계화하기 위해, 먼저 퍼징 용어를 제시한다.

---

2.1 Fuzzing & Fuzz Testing

fuzzing은 fuzz input으로 대상 프로그램 PUT(Program Under Test)를 실행하는 행위다. Miller의 정신을 계승하여, fuzz input을 PUT가 기대하지 않을 수 있는 입력, 즉 PUT가 잘못 처리하고 PUT 개발자가 의도하지 않은 동작을 트리거 할 수 있는 입력이라고 생각한다. 이 아이디어를 포함하기 위해 fuzzing이라는 용어를 다음과 같이 정의한다.

• 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. [퍼징은 PUT의 예상 입력 공간을 벗어나는 퍼즈 입력 공간(fuzz input space)에서 샘플링 된 입력을 사용하여 PUT를 실행하는 것이다.]

이때 주목할 만한 점 세 가지가 있다.

1. 예상되는 입력 공간을 포함하는 퍼즈 입력 공간을 흔히 볼 수 있지만, 이는 불필요하다. 즉, 전자가 후자에 없는 입력을 포함하는 것으로 충분하다.

   [즉 fuzz input space가 expected inpust space를 다 포함할 필요는 없고, unexpected input space만 포함하면 된다. 퍼징의 목적이 PUT의 예상 범위 바깥을 탐색한다는 것과 논리가 관통한다.]

2. 실제로 퍼징은 많은 반복을 수반한다. 따라서 반복 실행이라고 하는 것이 정확할 것이다.

3. 샘플링 과정이 반드시 랜덤할 필요는 없다.

fuzz testing은 퍼징을 활용하는 소프트웨어 테스트 기술의 한 형태이다. 다른 소프트웨어 테스트 기술들과 뚜렷하게 구분되는 차이점은 보안 관련 버그를 탐지한다는 목표가 있다는 것이다. fuzzer와 fuzz campaign은 다음과 같이 정의한다.

• Definition 2 (Fuzz Testing).

💡

Fuzz testing is the use of fuzzing to test if a PUT violates a security policy. [Fuzz testing은 PUT가 보안 정책(:security policy)을 위반하는지 테스트하기 위해 fuzzing을 사용하는 것이다.]

• Definition 3 (Fuzzer).

💡

A fuzzer is a program that performs fuzz testing on a PUT. [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. [fuzz campaign은 특정 보안 정책을 준수하는지 테스트 하기 위한, PUT에서의 fuzzer의 특정 실행을 의미한다.]

fuzzing campaign을 통해 PUT를 실행하는 목적은 지정된 보안 정책을 위반하는 버그를 찾기 위함이다. 예를 들어, 초기 퍼저의 보안 정책은 test case라고 불리는 생성된 입력이 PUT에서 crash를 일으키는지 여부였다. 그러나 fuzz testing은 실행에서 관찰할 수 있는 어떤 보안 정책이라도 테스트하는데 사용할 수 있다(i.e. EM-enforceable). 어떤 실행이 보안 정책을 위반하는지 결정하는 특정 매커니즘을 bug oracle이라고 한다.

• 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. [bug oracle은 PUT의 실행이 특정 보안 정책을 위반하는지 여부를 판단(결정)하는 프로그램(보통은 퍼저의 일부로 포함되어 있음)이다.]

퍼저에 의해 구현된 알고리즘을 퍼즈 알고리즘(:fuzz algorithm)이라고 한다.

거의 모든 퍼즈 알고리즘은 외부에서 PUT로 전달되는 파라미터(:parameter)에 따라 다르다. 각 파라미터의 구체적인 설정을 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은 퍼즈 알고리즘을 제어하는 파라미터 값들로 구성되어있다.]

fuzz configuration의 정의는 광범위하다. fuzz configuration에서 값의 타입은 퍼즈 알고리즘의 유형에 따라 다르다.

예를 들어 PUT로 random byte stream을 보내는 fuzz 알고리즘은 간단한 configuration space {(PUT)}을 가진다.

반면에 복잡한(:sophisticated) 퍼저는 configuration set을 accept하고 시간이 지남에 따라 set을 evolve하는 알고리즘을 포함한다. 여기엔 configuration의 추가와 제거를 하기도 한다. 예를 들어 CERT BFF는 캠페인 과정에서 변이(:mutation) 비율과 시드(seed) 둘 다 변경하므로, configuration space는 {(PUT, s1, r1), (PUT, s2, r2), ... }이다.

seed는 PUT에 대한 (일반적으로 잘 구조화된)입력으로, 수정하여 테스트 케이스를 만드는 데 사용된다. 퍼저는 일반적으로 시드 collection을 유지하고, 일부 퍼저는 fuzz campaign 진행에 따라 collection을 evolve시킨다. 이 collection을 시드 풀(seed pool)이라고 한다. 마지막으로, 퍼저는 각 configuration 내부에 일부 데이터를 저장할 수 있다. 예를 들어, 커버리지 기반(:coverage-guided) 퍼저는 각 configuration에서 획득한 커버리지를 저장한다.

---

2.2 Paper Selection Criteria

범위를 잘 설정하기 위해, 2008년 1월부터 2019년 2월까지 4개의 메이저 보안 컨퍼런스와 3개의 메이저 소프트웨어 엔지니어링 컨퍼런스의 논문집에서 퍼징에 관한 모든 출판물을 포함했다.

4개의 메이저 보안 컨퍼런스는 다음과 같다. (모두 알파벳 순서)

1. ACM Conference on Computer and Communications Security (CCS)

2. IEEE Symposium on Security and Privacy (S&P)

3. Network and Distributed System Security Symposium (NDSS)

4. USENIX Security Symposium (USEC)

3개의 메이저 소프트웨어 엔지니어링 컨퍼런스는 다음과 같다.

1. ACM International Symposium on the Foundations of Software Engineering (FSE)

2. IEEE/ACM International Conference on Automated Software Engineering (ASE)

3. International Conference on Software Engineering (ICSE)

다른 곳에 등장하는 퍼저들의 경우 관련성을 자체적으로 판단하여 포함하였다.

testing tool을 설계할 때, 소스코드에 대한 접근과 PUT에 대한 일부 지식이 전제되는 경우가 많다. 이러한 전제 때문에 때로는 퍼저와는 다른 성격의 테스팅 도구가 개발되곤 한다.

그럼에도 불구하고 두 분야 밀접한 관련이 있다. 따라서 어떤 publication을 fuzz test와 관련된 것으로 분류하고, 본 연구에 포함할지 여부를 확신할 수 없는 경우, 다음과 같은 간단한 경험 법칙(:rule of thumb)을 따른다: fuzz라는 단어를 사용한 출판물이면 본 연구에 포함한다.

---

2.3 Fuzz Testing Algorithm

본 논문에서는 fuzz testing을 위한 generic한 알고리즘인 Algorithm 1을 제시한다.

• ALGORITHM 1: Fuzz Testing

  

이는 2.4절에 정의된 블랙 박스(black-box), 그레이 박스(grep-box), 화이트 박스(white-box) 퍼징을 포함하는 기존 퍼징 기술을 수용할 만큼 충분히 일반적이다.

Algorithm 1은 fuzz configuration set인 $\mathbb{C}$와 timeout인 $t_{limit}$을 입력으로 사용하고, 발견한 버그들의 set $\mathbb{B}$를 출력으로 한다. 이는 두 파트로 구성되어있다.

첫 번째 파트는 fuzz campaign이 시작될 때 실행되는 PREPROCESS 함수다.

두 번째 파트는 loop 안의 다섯 가지의 연속하는 함수들이다: SCHEDULE, INPUTGEN, INPUTEVAL, CONFUPDATE, CONTINUE.

이 loop의 각 실행을 fuzz iteration이라고 하며, $\text{}$INPUTEVAL이 test case에서 PUT를 실행하는 각 행위를 fuzz run이라고 한다. 어떤 퍼저는 다섯 가지 함수를 모두 구현하지는 않았을 수도 있다. 예를 들어 fuzz configuration의 set을 업데이트 하지 않는 Radamsa를 모델링하면 CONFUPDATE는 현재 configuration set을 그대로 return한다.

• $\mathbf{P}\text{REPROCESS}(\mathbb{C})\rightarrow \mathbb{C}$

  사용자는 입력으로 fuzz configureation set과 함께 PREPROCESS를 제공하고, 잠재적으로 수정된(:potentially-modified) fuzz configuration set을 리턴한다. 퍼즈 알고리즘에 따라 PREPROCESS는 PUT에 instrumentation 코드 삽입이나 시드 파일의 실행 속도 측정 등 다양한 동작을 수행할 수 있다. (3절)

• $\mathbf{S}\text{CHEDULE}(\mathbb{C}, t_{elapsed}, t_{limit})\rightarrow \text{conf}$

  SCHEDULE은 현재 fuzz configuration set, 현재 시간인 $t_{elapsed}$ 및 제한 시간인 $t_{limit}$을 입력으로하고 현재 fuzz iteration에 사용할 fuzz configuration을 선택한다. (4절)

• $\mathbf{I}\text{NPUT}\mathbf{G}\text{EN}(\text{conf})\rightarrow \text{tcs}$

  INPUTGEN은 fuzz configuration을 입력으로 하고, 구체적인 test case set인 $\text{tcs}$를 리턴한다. 테스트 케이스들을 모을 때, INPUTGEN은 $\text{conf}$에서 구체적인 파라미터를 사용한다. test case를 생성하기 위해 $\text{conf}$에 있는 시드를 사용하는 퍼저도 있고, 모델이나 문법(:grammer)을 파라미터로 사용하는 퍼저도 있다. (5절)

• $\mathbf{I}\text{NPUT}\mathbf{E}\text{EVAL}(\text{conf}, \text{tcs}, O_{bug}) \rightarrow \mathbb{B'}, \text{execinfos}$

  INPUTEVAL은 fuzz configuration인 $\text{conf}$, 테스트 케이스들의 set인 $\text{tcs}$, 버그 오라클인 $O_{bug}$를 입력으로 받는다. $\text{tcs}$에서 PUT를 실행하고, 그 실행이 보안 정책을 위반하는지 여부를 버그 oracle $O_{bug}$를 사용하여 확인한다. 그런 다음 발견된 버그의 set인 $\mathbb{B}$와 보통 fuzz configuration 업데이트에 쓰이는 각 fuzz run에 대한 정보인 $\text{execinfos}$를 반환한다. $O_{bug}$는 model fuzzer에 임배딩되어 있다고 가정한다. (6절)

• $\mathbf{C}\text{ONF}\mathbf{U}\text{PDATE}(\mathbb{C},\text{conf}, \text{execinfos}) \rightarrow \mathbb{C}$

  CONFUPDATE는 fuzz configuration의 set인 $\mathbb{C}$, 현재 configuration인 $\text{conf}$, 각 fuzz run에 대한 정보인 $\text{execinfos}$를 입력으로 한다. 그리고 fuzz configurations의 set인 $\mathbb{C}$를 업데이트 한다. 예를 들어, 많은 그레이 박스 퍼저는 $\text{execinfos}$를 기반으로 fuzz configuarion의 수를 줄인다. (7절)

• $\mathbf{C}\text{ONTINUE}(\mathbb{C}) \rightarrow \{\text{True, False}\}$

  CONTINUE는 fuzz configuration의 set인 $\mathbb{C}$를 입력으로, 새로운 fuzz iteration이 필요한지(:occur)의 여부를 나타내는 boolean을 리턴한다. 이 함수는 탐색할 경로가 더 이상 없을 때 종료될 수 있는 화이트 박스 퍼저를 모델링하는 데 유용하다.

---

2.4 Taxonomy of Fuzzers

본 논문에서는 퍼저가 각 fuzz run에서 관찰하는 의미론(:semantic)적인 세분성(:granularity)을 기반으로 퍼저를 세 그룹으로 분류했다. 세 그룹은 블랙 박스 퍼저, 그레이 박스 퍼저, 화이트 박스 퍼저라고 불리며 아래와 같이 정의했다.

이 분류는 두 개의 주요 범주(블랙 박스 테스트와 화이트 박스 테스트)만 있는 기존의 소프트웨어 테스트와 다르다. 그레이 박스 퍼징은 화이트 박스 퍼징의 변형으로, 각 fuzz run에서 일부 단편적인 정보(:partial)만을 얻을 수 있는 경우를 의미한다.

---

2.4.1 Black-box Fuzzer

소프트웨어 테스트와 퍼징에서 사용되는 용어인 블랙 박스는 일반적으로 PUT의 내부를 관찰할 수 없는 기술을 의미한다. 입력과 출력 동작만 관찰할 수 있어서 블랙 박스라고 부른다. 소프트웨어 테스트에서는 블랙 박스 테스트를 IO-driven testing 또는 data-driven testing이라고 부른다.

zzuf, BFF, GPF와 같은 대부분의 전통적인 퍼저들은 블랙 박스 퍼저에 해당된다. funfuzz나 Peach와 같은 일부 최신 퍼저는 보다 의미 있는 테스트 케이스를 생성하기 위해 입력에 대한 입력에 대한 구조적 정보를 고려하여, PUT를 검사(:inspect)하지 않는 특성을 유지한다. <Adaptive random testing: The ART of test case diversity>에서 유사한 아이디어가 사용된다.

---

2.4.2 White-box Fuzzer

화이트 박스 퍼징은 블랙 박스 퍼징과 반대로 PUT 내부와 PUT를 실행하면서 얻은 정보를 분석하여 테스트 케이스를 생성한다. 따라서 화이트 박스 퍼저는 PUT의 state space을 체계적으로 탐색할 수 있다.

화이트 박스 퍼징이라는 용어는 2007년 Godefroid의 연구 <Random testing for security: Blackbox vs. whitebox fuzzing>에서 도입되었는데, symbolic execution의 변형인 dynamic symbolic execution(DSE)를 다룬다.

DSE에서 symbolic/concrete execution이 동시에 작동하며, concrete 프로그램 상태는 symbolic constraints을 단순화하는 데 사용된다(예: concretizing system calls). 그래서 DSE는 concolic(concrete + symbolic) testing이라고도 한다.

또한 화이트 박스 퍼징은 taint analysis를 사용하는 퍼저를 설명하는데도 사용되었다:<Taint-based directed whitebox fuzzing>. 화이트 박스 퍼징은 일반적으로 블랙 박스 퍼징보다 오버 헤드(over head)가 훨씬 높다. 이는 DSE를 구현할 때 종종 dynamic instrumentation과 SMT solving을 사용하기 때문이기도 하다. DSE는 활발한 연구 분야지만, 많은 DSE가 보안 버그를 찾는 것을 목표로 하지는 않기 때문에 화이트 박스 퍼저가 아니다. 따라서 이 본 논문에서는 DSE에 대한 포괄적인 survey를 제공하지 않으며, DSE에 대한 자세한 내용은 최근 survey 논문인 <An orchestrated survey of methodologies for automated software test case generation>와 <All you ever wanted to know about dynamic taint analysis and forward symbolic execution>을 참고하라.

---

2.4.3 Grey-box Fuzzer

그레이 박스 퍼징이라는 절충적인(:middle ground) 접근 방식을 사용하는 퍼저도 있다. 그레이 박스 퍼저는 더 많은 입력을 테스트하고 속도 측면의 최적화를 위해 근사적이고 불완전한 정보에 의존한다.

보통 그레이 박스 퍼저는 PUT와(또는) 실행에 대한 내부 정보를 얻을 수 있다. 화이트 박스 퍼저와 달리, 그레이 박스 퍼저는 PUT에 대한 full semantics을 추론(:reason)하지는 않는다. 대신 가벼운 정적 분석을 수행하거나 PUT와(또는) 코드 커버리지와 같은 실행에 대한 동적인 정보를 획득할 수 있다.

블랙 박스 퍼징, 그레이 박스 퍼징, 화이트 박스 퍼징의 구분이 항상 명확한 것은 아니다. 블랙 박스 퍼저가 fuzz run에 대한 정보를 획득할 수도 있으며, 화이트 박스 퍼저자 종종 개략적인 정보를 활용하기도 한다. 본 연구에서, 특히 Table 1에서 최선의 판단을 하기 위해 노력했다.

그레이 박스 퍼저의 초기 예는 EFS로, 각 fuzz run에서 획득한 코드 커버리지를 이용해 evolutionary 알고리즘으로 테스트 케이스를 생성했다. Randoop도 비슷한 접근 방식을 사용했지만, 보안 취약점이 목표는 아니었다. 최신 퍼저인 AFL이나 VUzzer가 그레이 박스 퍼저에 속한다.

---

2.5 Fuzzer Genealogy and Overview

아래 Figure 1은 현재 존재하는 퍼저들을 시간순으로 나타낸 그림이다.

• Figure 1

  Miller의 퍼저로 거슬러 올라가는 퍼저들의 계보. 같은 행의 각 노드는 같은 연도에 나타난 퍼저임을 의미한다. X —> Y 꼴의 실선 화살표는 Y가 X의 기술을 인용, 참조, 사용하고 있다는 것을 의미한다. 📕은 논문으로 출판되었음을 의미한다.

  

최초의 퍼저인 Miller의 퍼저부터, 메이저 컨퍼런스에서 발표되었거나 100개 이상의 github star를 받은 인기 있는 퍼저들을 골라서 관계도를 그래프로 나타냈다. 블랙 박스 퍼저는 왼쪽에, 그레이 박스 퍼저와 화이트 박스 퍼저는 오른쪽에 배치했다.

이후 파일, 네트워크, UI, 웹, 커널, I/O, 스레드(concurrency fuzzer)와 같이 PUT의 입력 종류에 따라 세분화했다.

아래 Table 1은 Figure 1에서 가장 주목할만한 퍼저에 사용된 기술을 요약한 표이다.

• Table 1

  instrumentation granularity와 이름으로 정렬한 퍼저들 개요. 블랙박스(●), 그레이박스(◑), 화이트박스(○)

  

공간상 제약으로 Figure 1의 일부 퍼저를 생략했다.

각 퍼저를 앞서 제시한 model fuzzer의 다섯 가지 함수(PREPROCESS, SCHEDULE, INPUTGEN, INPUTEVAL, CONFUPDATE)와 퍼저의 세부 정보를 제공하는 기타 섹션(Misc.)으로 분류했다.

다음은 각 열이 나타내는 특징들이다.

• [Misc.]

  Feedback Gathering Granularity : 퍼저가 블랙 박스(●), 그레이 박스(◑), 화이트 박스(○) 중 무엇인지 나타낸다. 퍼저가 서로 다른 종류의 피드백을 획득해 사용하는 경우 원이 두 개다. 예를 들어, SymFuzz는 전처리로 화이트 박스를 분석하여 후속 블랙 박스 캠페인의 성능을 최적화한다(●+○). Driller와 같은 하이브리드 퍼저는 화이트 박스 퍼징과 그레이 박스 퍼징을 번갈아가며 사용한다(○+◑).

  Open-Sourced : 퍼저가 오픈소스코드인지 나타낸다.

  Source Code Required : 퍼징을 할 때 PUT의 소스코드가 필요한지 나타낸다.

• [PREPROCESS]

  Support In-memory Fuzzing : 퍼저가 in-memory 퍼징(3.1.2)을 지원하는지 나타낸다.

  Model Construction : 퍼저가 모델을 추론(:infer)할 수 있는지 나타낸다.

  Program Analysis : 퍼저가 PREPROCESS 단계에서 정적 분석이나 동적 분석을 수행하는지 나타낸다.

• [SCHEDULE]

  Seed Scheduling : 퍼저가 여러 개의 시드를 처리하고 스케줄링을 수행하는지 나타낸다.

• [INPUTGEN]

  Mutation : 퍼저가 테스트 케이스를 생성하기 위해 입력에 변이(:mutation)를 수행하는지 여부를 나타낸다. execution feedback을 통한 입력 변이 기반 퍼저인지 나타내기 위해 ◑ 심볼을 사용한다.

  Model-based : 퍼저가 모델을 기반으로 테스트 케이스를 생성하는지 나타낸다.

  Constraint-based : 퍼저가 테스트 케이스 생성을 위해 symbolic analysis을 하는지 나타낸다.

  Taint Analysis : 테스트 케이스 생성 과정을 위해 taint analysis를 사용하는지 나타낸다.

• [INPUTEVAL]

  Crash Triage: Stack Hash : 퍼저가 크래시 분류(:triage)를 수행할 때 stack hashing을 사용하는지 나타낸다.

  Crash Triage: Coverage : 퍼저가 크래시 분류(:triage)를 수행할 때 코드 커버리지를 사용하는지 나타낸다.

• [CONFUPDATE]

  Evolutionary Seed Pool Update : CONFUPDATE 단계에서 "시드 풀에 새로운 시드 추가"와 같은 시드 풀 evolve 과정이 있는지 나타낸다.

  Model Update : 퍼저가 online 방식으로 입력 모델을 학습하는지 나타낸다. [머신러닝의 online]

  Seed Pool Culling : 시드 풀에서 시드를 제거하는지 나타낸다.

---

Uploaded by Notion2Tistory v1.1.0