[PAPER] AFL++: Combining Incremental Steps of Fuzzing Research

Paper

https://www.usenix.org/system/files/woot20-paper-fioraldi.pdf

---

Abstract

state-of-the-art fuzzing 연구를 포함한 오픈소스 도구인 AFL++ 제안함

---

Introduction

fuzzing에서의 어려움

• fuzzing 기술들은 독립적으로 개발되어서 결합해서 사용하는 과정이 오래걸리고 fuzzing 기능 결합이 어려움
• 개발한 도구 평가가 어려움

 

앞선 fuzzing에서의 어려움 해결 위해

• 확장 가능한 API 제안
• 새로운 newline이 될 AFL++ 제안
  • 연구자들은 이미 AFL++에 구현된 state-of-the-art 특징들을 통해 그들이 제안한 특징들을 비교하여 평가할 수 있음
  • 연구에 사용하기 쉬운 특징들 제공
  • coverage-guided fuzzer인 AFL을 기반

 

AFL을 base로 선택한 이유

• 패치나 아카데믹 fork가 가능했지만 18개월 동안 이루어지지 않아 왔기 때문에 패치나 아카데믹 fork를 하기에 좋음
• LIBFUZZER나 HONGGFUZZ는 활발하게 maintain 되어왔고 comparison으로 fork하고 보완하는걸 좋아하지 않음 (ENTROPIC이나 Vranken’s enhancement와 같은 예외는 있음)

 

 

Contributions

1. 최근 fuzzing 연구들을 포함한 유용한 도구인 AFL++ 제안
2. 접근성이 좋고 연구에 결합하거나 구현하기 좋은 Custom Mutator API 제안
3. AFL++에서 선택된 기술과 특징들을 평가하여 향후 연구에 각 기술이 얼마나 타겟 의존적인지 보임

AFL++ 오픈소스 소프트웨어: https://github.com/AFLplusplus/AFLplusplus

테스트 케이스: FuzzBench (Fuzzer benchmarking)

---

State-of-the-Art

1. American Fuzzy Lop (AFL)

AFL은 mutational, coverage guided fuzzer으로, 프로그램 내 탐색되지 않은 지점을 검색하기 위해 테스트 케이스를 변형하고, 만약 새로운 지점이 탐색되면 테스트 케이스 queue에 새로운 coverage가 들어간다.

1) coverage guided feedback

• hybrid metric → edge coverage + hitcount(한 번 fuzzing 돌렸을 때 edge가 얼마나 실행됐는지에 대한 count)
  • 실행 시 hitcount는 bitmap에 로깅되는데, bitmap 크기가 제한적이라 collision이 발생할 수 있음
• queue 내 각 테스트케이스에 대해 trimming(coverage 온전히 유지) 단계에서 타겟 속도 개선하고 테스트 케이스 크기 줄임

 

2) Mutation

AFL에서 mutation 종류

1. deterministic
   • 테스트케이스에 하나의 deterministic mutation(bitflip, addition 등) 포함
2. havoc
   • mutation은 랜덤하게 쌓이고 테스트 케이스 크기에 따라 include가 변함
   • splicing 단계에서 AFL은 두 테스트 케이스를 하나로 merge하거나 havoc 적용 할 수도 있음

 

3) Forkserver

새로운 프로세스 생성 시 execve()는 오버헤드가 크므로, 대신 forkserver 사용

AFL에서 테스트 케이스 실행 위해

1. 자식 프로세스를 fork해서
2. 자식 프로세스는 테스트 케이스를 실행
3. 부모 프로세스는 자식 프로세스 끝나길 기다림

⇒ 초기화나 startup routine에 대한 추가 비용이 없음

 

4) Persistent Mode

fork()는 bottleneck이므로, 각 테스트 케이스에 대해 타겟이 fork하지 않는 대신 루프가 타겟에 패치돼서 한 iteration 당 하나의 테스트 케이스를 실행하도록 함

⇒ fork()에 대한 오버헤드 없어서 크게 성능 개선

 

2. Smart Scheduling

scheduling 목표

• smart한 테스트 케이스 선택으로 전체 coverage 개선 & bug 탐지

1) AFLFast (seed scheduling)

더 많은 branch 탐색하고 더 많은 bug 탐지 위해 low-frequency path에 더 집중

주요 문제

1. low-frequency path에 더 집중하기 위해 fuzzer는 어떤 순서로 seed를 선택해야 하는지? (seed scheduling) ⇒ research strategy로 해결
2. 각 seed에서의 생성된 입력 양을 조정할 수 있을지? ⇒ 6개의 power schedule로 해결: fuzzing 과정 수집되는 파라미터의 에너지 계산

⇒ seed scheduling 방법: 테스트 케이스 fuzz하는데 시간 얼마나 들여야 하는지

 

2) MOpt

mutation scheduling

• seed scheduling에 문제가 있기 때문에 제안됨
• Particle Swarm Optimization 알고리즘 사용하여 mutation operator(mutator)에 서로 다른 확률을 줘서 가능성을 탐색
• 빠르게 coverage 발견 가능
• Pilot module(효과성 기반으로 평가한 mutation operator에 확률 지정), Code module(Pilot 단계에서의 확률 고려하여 mutation 진행)로 fuzzing 단계 나눠서 AFL 변형함

 

3. Bypassing Roadblocks

coverage guided fuzzer 문제: roadblock → larger comparison (string이나 checksum 체크 등)

1) LAF-Intel

LAF-Intel

• comparison 위한 feedback
• 목표: multi-byte comparison의 어려움 해결
• multi-byte comparison을 여러 개의 single-byte comparison으로 split

LAF-Intel 특징

1. =, <=연산자를 >, <, == comparison으로 단순화
2. signed integer comparison ⇒ sign-only comparison, unsigned comparison 변환
3. 64,32,16bit의 모든 unsigned integer comparison을 8bit의 multiple comparison으로 분리

예) if(strcmp(input, “abcdefg”))는 입력 전달하기 어려우니까 if(input[0] == ‘a’ && input[1] == ‘b’ … )와 같이 재작성 → 복잡한 조건을 fuzzer가 해결할 수 있게 함

 

2) RedQueen

• KAFL 기반
• 어려운 comparison과 checksum check를 우회하기 위한 가능성 탐색
• Input-To-State (I2S) comparison
  • 대부분의 roadblock이 Input-To-State comparison 타입
  • 입력 내 operand 중 최소 하나에 direct dependency가 있는 comparison
  • 예) if(input[15964] == 35) crash(); → 커버하기 힘든 branch edge에 입력이 바로 쓰일 때
• colorization 단계에서 입력에서의 entropy를 증가시키고, 테스트 케이스의 coverage를 유지하면서 byte를 랜덤한 값으로 대체
• Input-To-State comparison의 operand를 관찰하면 입력에서 guess해야 할 수 줄일 수 있음
• comparison에서 추출한 I2S token을 대체해가며 입력을 mutation

 

4. Mutate Structured Inputs

fuzzer에서 유효하지 않는 입력을 생성하는 문제

→ input model 사용해서 해결. 생성된 입력의 공간 감소시키고 더 깊은 경로 탐색 가능하게 함

AFLSmart

PEACH를 black-box fuzzing 시 input model로 사용

input structure 고려해서 structured input 생성하도록 해서 invalid input 생성 피하고 deep path 탐색 가능하도록 함

---

A New Baseline for Fuzzing

1. Seed Scheduling

AFLFAST을 기존 모든 schedule 기법(fast, coe, explore(default), quad, lin, exploit)에 power schedule(mmopt, rare) 추가해서 확장함

AFLFast에 추가로 고려한 부분

• queue에서 seed가 선택되는 시간
• 동일한 coverage 갖는 입력 수
• 동일한 coverage 갖는 테스트 케이스 수

mmopt schedule

• 새롭게 발견된 경로를 찾을 수 있도록 가장 새로운 seed에 score 더 줌

rare schedule

• seed의 런타임 무시하고, 다른 seed에서 드물게 처리된 edge를 가진 seed에 집중

 

2. Mutators

AFL++은 기존 AFL의 deterministic하고 havoc pipeline보다 더 많은 mutator를 포함한다. mutator들을 조합해서 사용할 수 있다.

1) Custom Mutator API

AFL fork, patch 없이 AFL++ 내에서 API 사용해서 새로운 연구에 확장해서 쓰거나 특정 타겟 대상으로 취약점 찾는데 적용 가능

afl_custom_(de)init

• initialize, deinitialize module 시 사용

afl_custom_queue_get

• fuzzer가 현재 queue entry를 fuzzing 해야할지 결정하는 callback

afl_custom_fuzz

• 주어진 입력에 대해 custom mutation 수행. 추가 테스트 케이스 accept

afl_custom_havoc_mutation

• 입력에 대해 custom mutation 수행
• havoc 단계에서 다른 mutation와 함께 쌓인다

afl_custom_havoc_mutation_probability

• havoc에서 호출된 custom mutation 확률 리턴
• 디폴트는 6%

afl_custom_post_process

• custom mutator에서 리턴한 데이터 포맷이 타겟 입력에 적합하지 않는 경우, checksum이나 크기 조정할 수 있도록 함

afl_custom_queue_new_entry

• queue에 새로운 테스트 케이스가 추가될 때 호출
• disk에 metadata 저장 시 유용

afl_custom_trim

• AFL++에서 trimming routine 시 복잡한 포맷 구조를 파괴해서 입력 일부는 처리할 수 있고 입력 나머지 부분은 에러 발생할 수 있다. 이때 custom trimming routine 가능한 API 사용
• 각 trimming 연산 시 호출되어 현재 상태 기억하고 초기 입력 데이터 길이 초과하지 않는 trimmed input buffer 리턴

 

2) Input-To-State Mutator

AFL++은 REDQUEEN의 Input-To-State replacement 기반으로 mutator 구현하여 기존 구현에서 몇 가지 최적화 진행

최적화 부분

1. colorization
   • 입력에서 각 바이트의 entropy 높이는데 효과적인 반면 fuzzer 속도 저하시킴
   • mutated 지역에서 coverage bitmap의 hash가 동일하게 유지되면서 기존보다 2배 slowdown하는 bound를 실행 속도가 유지하도록
2. comparison 시 probabilistic fuzzing
   • comparison bypass 충족할 입력을 생성하지 못할 수 있는데, 다음 시간에 이 comparison이 lower 확률로 fuzz 되도록 해서 unsolvable comparison에 너무 많은 시간 소요하지 않도록 함

 

3) MOpt Mutator

AFL++은 MOPT의 Core와 Pilot mode 구현했음

MOPT mutator는 Input-To-State mutator와 결합하여 사용 가능

 

3. Instrumentations

AFL++이 instrumentation 위해 지원하는 backends

NeverZero

AFL에 hitcount 최적화 위해 개발한 instrumentation에 사용되는 backend

bitmap entry 내 바이트 사용 시 edge execution 수가 overflow될 수 있는데 이게 발생하면 fuzzer가 일관성 없는 상태에 있을 수 있다.

 

overflow 해결 방법

1. NeverZero
   • bitmap entry에 carry flag 추가해서 overflow 피하는 방법
   • 매우 효과적, coverage와 속도 관련해서 AFL 개선함
2. Saturated Counters
   • 255 값에 counter 도달 시 counter를 freeze하는 방법
   • AFL 성능 저하함

 

1) LLVM

Context-sensitive Edge Coverage

• edge coverage는 각 block의 ID와 callee의 ID를 XOR하는 것
• code coverage에는 효과적인데 더 많은 collision 갖고 속도 더 느림

Ngram

• N이 2부터 16 사이 숫자일 때, fuzzer는 destination block과 N-1 previous block 고려해서 edge를 logging

LLVM은 coverage feedback 위해 instrument를 패스하는데, AFL++에는 여기에 추가로 더 패스한다. 모든 LAF-INTEL pass가 포함되고, CmpLog pass 가능함

LLVM mode에서 instrument에 특정 source module 지정 가능

INSTRIM(LLVM에서 instrument 시 basic block 선택하는데 효율적)을 patch해서 구현

 

2) GCC

afl-gcc에 GCC 플러그인 추가 → deferred initialization, persistent mode

 

3) QEMU

AFL++은 AFL QEMU에 QEMU 3.1.1 사용해서 patch

→ emulation time에 instrumentation 추가 가능

→ helper 사용해서 AFL에서 불가능하게 한 block linking 가능하게 함

→ Thread Local Storage 사용

→ AddressSanitizer 기반 sanitization 지원

→ CompareCoverage: source-level fuzzing과 binary-level fuzzing 사이 gap 감소 위해 AFL++의 QEMU mode는 CompareCoverage 사용해서 compariso을 LAF-INTEL로 분리 가능

→ persistent mode: AFL++의 QEMU mode는 persistent mode 지원

⇒ 10x speedup 가능하고 이 모드 가능하면 추천함

 

4) Unicornafl

unicornafl: AFL++에서는 펌웨어와 같은 blob 바이너리 퍼징 위해 AFL에 unicorn engine 추가한 afl-unicorn을 확장한 것

original은 forkserver을 initial basic block에서 시작하고 garbage-collected python으로만 가능했는데, AFL++은 unicornafl에 C API, Rust, Python binding 추가해서 AFL++와 직접적으로 통신 가능하게 함

 

5) QBDI

LLVM 사용해서 compiler instrumentation으로 Android 라이브러리나 closed-source 라이브러리를 fuzzing

 

 

4. Platform Support

GNU/Linux, Android, iOS, macOS, FreeBSD, OpenBSD, NetBSD, Debian, Ubuntu, NixOS, Arch Linux, FreeBSD, Kali Linux 지원

AFL++의 QEMU mode의 Wine mode는 Win32 바이너리를 GNU/Linux에서 fuzzing 가능

 

 

5. Snapshot LKM

• fork() → AFL의 state-restore 메커니즘, 타겟 수 많으면 성능 bottleneck 있음
• AFL++은 Linux Kernel Module 통합해서 snapshot과 restore 처리하는 메커니즘 구현
  • fork와 비교했을 때 이 module은 single core에서 2x보다 더 높은 성능
  • multi-core에서 돌릴 때는 성능 좀 달라짐

fork 대신 snapshot 사용하면 타겟 프로그램의 재컴파일 필요 없음

---

Evaluation

FuzzBench 사용해서 평가 진행

평가할 6가지 configuration

1. Default: 디폴트 AFL setup에 특정 fix와 improvement
2. MOpt: mutator
3. Ngram4: instrumentation (4개의 basic block을 path로 interpret)
4. RedQueen: 추가 feedback channel (더 깊은 검색 위해)
5. Ngram4,Rare: Ngram4 instrumentation + Rare scheduling (AFL++)
6. MOpt,RedQueen: MOpt mutation + RedQueen (AFL++)

 

FuzzBench

• 모든 interested project에 21 target을 23 시간 동안(원래는 24시간) fuzzing 해서 평가한 것
• edge coverage에서 의미있는 median 얻으려면 각 fuzzing은 20번 씩 해야 함
• 이 FuzzBench target 21개 중 9개 선택해서 AFL++ 평가

 

6가지 configuration으로 보일 것

• MOPT와 Ngram4가 가능한 새로운 기술의 예시라 한다면, 두 개를 조합했을 때 REDQUEEN mutator나 power schedule(rare)보다 더 유용한 걸 얻을 수 있을 것이다.
• fuzzing 중 이게 분명해지면, 모든 fuzzing 행위는 높게 target-specific 해서 적절한 configuration을 선택하는 것이 중요하다.

 

결과

---

Future Work

1. scaling
   • 테스트 케이스 delivery에 파일 시스템을 사용하기 때문에, 그리고 fork() 시스템콜 의존 때문에 multiple thread로 scaling은 ideal보다 좋지 않음
2. collision-free instrumentation
   • AFL에서 제공하는 instrumentation은 hashing 시 collision이 발생하는데 이는 속도와 정확도 문제가 있음
3. static analysis for optimal fuzz settings
4. plug-in system
   • 기능 추가 필요

---

Conclusion

• AFL++은 주요 fuzzing 연구들을 통합했고, 기술에서 리얼월드 개선이 있음을 보여줌
• AFL++은 아카데믹한 부분을 사용하기 쉽게 하여 academia와 industry 사이 gap을 연결함
• AFL++의 Custom Mutator API는 새로운 연구 아이디어의 prototype을 만들기 쉽고 타겟에 쉽게 조정해서 사용할 수 있음