[Fuzzing] AFL++

* Background

퍼징 기술들은 독립적인 경우가 많아서, 기술들을 결합하는데 많은 시간이 걸린다.

기술을 결합하면 타겟에 대한 버그를 기본 설정을 유지한채로 더 빨리 찾을 수 있다.

하지만, 이렇게 결합된 새로운 도구를 평가하기는 어렵고, 퍼징 끼리 호환이 가능하지 못할 수도 있다.

이런 문제의 solution의 open source은 AFL++이다.

 

AFL++은 최근의 퍼징 연구들을 하나의 사용 가능한 tool로 통합하는 기술을 제안한다.

-> AFL++을 사용하여 통합된 기술들에 대해 서로를 비교하며 평가할 수 있으며,

각 기술이 target에 얼마나 의존적인지를 측정할 수 있다.

 

AFL++의 core는 AFL의 forked 버전이다.

AFL을 기반으로 한 이유는, AFL의 관리가 잘 되지 않았지만, 많은 커뮤니티에서 패치해서 사용하고 있었고,

fork를 사용할 수 있었기 때문이다.

 

* Seed scheduling

AFL++은 AFL Fast와 이 외의 power schedules를 통합하여 스케쥴링에 사용

default scheudle은 AFL++의 explore이고 여기에 추가적은 mmopt와 rare 스케쥴을 사용한다.

- Mmopt: 새로 발견된 경로를 더 깊이 탐색하는데 도움이 되도록 새로운 seed의 점수를 높인다.

- Rare: seed의 runtime을 무시하고 다른 seed에 비해 거의 적용되지 않는 edge가 있는 seed에 초점을 둔다.

 

** power schedules는 다음과 같은 3가지의 변수를 결정하는 함수다.

1. queue에서 seed가 선택된 시간

2. 동일 seed에서 같은 커버리지의 input을 생성한 수

3. 일반적으로 동일한 커버리지로부터 테스트 케이스를 생성한 평균 수

 

* Custom Mutator API

- deterministic과 havoc보다 더 많은 mutator를 통합하고, mutator들은 다른 mutator들과 통합 가능

- 쉽게 확장이 가능하고 타겟에 맞게 조정 가능 (조건: API가 계속 성장할 수 있어야한다)

- AFL을 패칭하거나 fork하지 않고도 새로운 스케쥴링, 뮤테이션을 AFL++ 위에 최소화해서 build 가능

- plugin과 API는 서로 완전히 rewrite가 가능해야한다. (ex. AFLSMart로 쓰였다면, AFL++ 플러그인으로 rewrite 가능)

 

afl_custom_(de)init : 각각의 custom mutator는 스스로 모듈을 initialize하거나 deinitialize하는데 사용

AFL++의 pesudo-random generator seed는 init을 통과한다.

(custom mutatr는 반드시 동일한 seed에 대해 같은 퍼징 결과를 갖는지 확인해야함)

afl_custom_queue_get : 현재의 queue entry를 퍼징할지 안할지를 결정하는 콜백

이 루틴에서, 사용자는 input의 메타데이터(ex. structured fuzzing의 가상 구조)를 초기화할수도 있음

afl_custom_fuzz : input에 대한 custom mutation을 수행 + 추가적인 test case도 accept 가능

afl_custom_havoc_mutation : input에 대한 single custom mutation 수행 (havoc step)

return afl_custom_havoc_mutation_probability //havoc이 튜닝이 가능한지의 가능성(defualt:6%)

afl_custom_post_process : 타겟에 대한 인풋을 직접적으로 실행하는데 맞지 않는 mutated data를 리턴할 경우가 있는데 이런 경우나 checksum이나 크기를 수정해야할 때는 이 함수에 정의된 기능을 사용해서 해결할 수 있다.

afl_custom_queue_new_entry : queue에 새로운 test case를 추가한 뒤 호출되는 것으로, disk에 메타데이터를 저장하는데 유용

 

AFL++ 역시 trmming을 통해 복잡한 포맷 구조를 파괴할 수 있다.

trimming은 타겟에서 input의 일부분을 처리할 수 있고, 남은 input에 대한 에러를 유발할 수 있을 때 유용하다.

(※ 각 트리밍 단계 이후에 커버리지 비트맵이 바뀌면 안됨)

 

afl_custom_init_trim : 각 trmming operation이 시작할 때 호출되고 inital buffer를 받는다.

input에 대해 가능한 반복 횟수를 return 해야한다. 

만약에 남은 단계의 양을 측정하지 못하도록 구현되어 있다면 return 1(추후 trimming이 수행하도록)

+) trimming은 afl_cust_post_trim이 0이 될 때까지 반복

afl_custom_trim : 각 trimming operation마다 호출

current state를 기억 (∴각 반복의 복구 스텝 저장 가능)

trimmed input buffer를 return 해야한다. (이 때 데이터는 초기 인풋 데이터의 길이를 초과하면 안됨)

afl_custom_post_trim : trim operation이 끝난 뒤에 호출되며 trimming step이 성공인지 아닌지를 알린다.

다음 trim의 반복 index를 return 해야한다. (0~afl_custom_init_trim에서 return된 max)

 

* I2S(Input-To-State) Mutator

AFL++은 REDQUEEN에서의 I2S를 기반으로 mutator를 구현한다.

1. 기존 REDQUEEN은 colorization에서의 byte의 엔트로피 증가 (느림)

-> critical field(ex.size)를 랜덤하게 muate 

-> colorization 확장(커버리지 비트맵의 hash는 동일, 실행속도가 2배 정도 느려져도 mutation region 유지)

2. 각 comparision의 퍼징 확률 확장

-> 퍼저가 comparision을 우회하는 input을 만드는데 실패했다면, 다음번에는 이 comparision은 더 낮은 확률로 퍼징.

-> 안 풀리는 comparision에 너무 많은 시간을 쏟는 것 방지

3. breakpoint를 이용한 log comparision 사용 X

-> shared table을 이용 (WEIZZ와 유사)

-> 각 comparision log는 256MB의 퍼저와 타겟간의 공유 테이블에 last 256개의 실행 로그 기록

-> 테이블의 처음 part(512KB)는 각 comparision의 메타데이터 정보 저장 ex. size, ID, excution 횟수

-> 512KB는 cache의 locality 측면에서 효율적

-> 메타데이터는 comparision이 없거나, operand의 메모리에 access하지 않는 경우 등록 가능

-> LLVM과 QEMU instrumentation에서 사용 가능

 

* MOpt Mutator

AFL++의 core + MOpt의 Pilot mode + ITS mutator

-> ITS mutator와 combine 가능

 

* Instrumentations

AFL++의 backend instrumentation으로는 LLVM, GCC, QEMU, Unicorn, QBDI가 있다

top에는 proxy module을 제공해서, target에 테스트케이스를 적용할 수 있고, afl-fuzz의 어떤 커버리지도 제공할 수 있다. 원격이거나 coverage가 없는 경우도 가능(ex. ampere consumption, jtag의 브랜치 어드레스)

 

table1은 각 instrumentation이 most important features에 대한 상태다.

 

* NeverZero

AFL의 hit count를 저장하는 bit map entry는 byte로 사용할 때 overflow 문제점이 존재

(edge가 256배수로 hit를 했다면, bitmap은 0으로 넘겨서 퍼져의 state는 inconsistent가 됨)

-> 해결책으로, 1) NeverZero 2) Saturated Counters 가 있다

 

1) NeverZero : bitmap entry에 carry flag를 추가해서 edge가 한번이라도 실행됐다면 entry는 절대 0이 될 수 없음

-> AFL의 커버리지와 속도 측면에서 효과적

-> AFL++의 대부분의 instrumentation에 default로 NeverZero 적용

2) Saturated Counters : 255가 되면 counter가 멈춤

-> AFL의 전반적인 성능 하락

 

* LLVM

LLVM모드에서 AFL++은 edge coverage에다가 추가적인 coverage와 coverage feedback을 위한 pass 지원

-> 사용자가 instrument를 할 특정 소스 모듈 지정 가능 (한 곳에 집중하고 싶을 때 유용)

1) Context-sensitive Edge Coverage

각 block에 할당된 ID와 호출한 block의 ID를 xor해서 edge coverage 계산

-> penalty 부여(많은 충돌, 느린 속도)

-> code coverage 측면에서 효과적

2) Ngram : edge를 로깅할 때, 이전 blcok을 고려하는 대신, 목적지 block과 N-1개의 이전 block 고려(1<N<17)

3) LAF-INTEL : 모든 LAF-INTEL 포함

-> floating-point comparision 분할(실험 모드) ex. video 디코더, javascript interpreter

-> string comparision fucntion analysis : 고정된 string이 할당된 전역 변수/지역 변수 처리 가능

4) CmpLog

5) Persistent mode : shared memory를 통해 새로운 test case를 input으로 넣을 수 있음(기존-stdin/file)

-> pesistent mode의 속도 2배 향상

-> fork mode는 10~20배 향상

6) INSTRIM : LLVM에서 instrumenation을 넣을 때 basic block을 선택하는데 효율적

-> Dominator Tree를 기반으로 분석해서 instrumenation이 필요 없는 구간을 피함

-> 대부분, instrumentation이 들어갈 위치를 절반 이상 줄여줌

-> 속도 향상

 

* GCC

AFL LLVM 모드 같은, deferred initialization과 persistent 모드에 대한 지원을 포함

 

* QEMU

emulation time에 instrumentation 추가

basic block을 선택할 때 basic block이 emulator의 context에는 기록되지 않고, logging routine에서 helper를 통해 인라인 -> AFL이 비활성화한 block linkding 활성화 가능(속도 2-3배 향상) & Thread Local Storage도 가능

 

* CompareCoverage

source-level fuzzing과 binary-level fuzaaing의 특징 gap을 줄이기 위해, QEMU 모드는 CompareCoverage를 이용해서 LAF-INTEL과 비슷한 방법으로 comparision을 분할 가능

-> code 변경 X

-> 모든 비교 연결, 각각의 operand의 byte들이 비교되고, 같다면 다른 비트맵 entry 증가

-> integer comparision만 분할 가능(immediate operand, integer comparision, integer/floating point comparision)

-> LIBFUZZER의 popcnt와 유사하지만, 이는 아주 적은 input을 사용하기 때문에 덜 효율적

 

* Persistent Mode

AFL++은 아래 2가지 방법을 통해, QEMU 모드에서도 persistent mode를 지원 (10배 속도 향상)

1. 함수 반복

: 사용자는 함수의 주소를 특정할 수 있고, 퍼저는 자동으로 persistent loop에 리턴 어드레스 패치

(+ 이 주소는 funtion의 첫 번째의 instruction이 아닐수 있지만 올바른 주소를 스택에 위치시키기 위해 사용자는 offset을 제공해야한다.)

2. entry와 exit point 지정

: 사용자는 loop의 처음과 마지막 instruction의 주소 지정

-> QEMU는 이 주소 사이에서 loop 생성

 

* Unicornafl

펌웨어같은 blob 바이너리의 퍼징을 위해서 AFL++은 unicornafl이라고 불리는 엔진을 지원해서 afl-unicorn을 fork한다. Voss의 원래 버전은 initial basic block에서 forkserver가 시작하는 반면에 garbage-collected python을 통해서만 가능하다. AFL++의 uniconafl은 API의 low-level을 추가해서 AFL++과 direct로 상호작용이 가능하다. unicorn은 page mapping, read/w memory/register 등의 기능을 설정할 수 있는 API를 이미 포함하고 있다.

AFL++ 전용 API를 사용하면 하네스가 언제든지 빠른 persistent mode로 시작할 수 있고 충돌을 감지하기 위해 multiple exits와 post-fuzzing handler를 설정할 수 있다.

uc_afl_forkserver_start : 특정 시점에 fork server를 시작하기 위해 호출, 

-> fuzzing이 시작하기 전에 현재 상태를 멈추고 AFL++에게 input 생성을 시작하라고 말함.

uc_afl_fuzz : 각 testcase를 직접 읽는 on-stop-shop과 같은 구조로 persistent mode를 지원

타겟 펌웨어는 parent process에서 같은 state를 유지해야하고, 각 test case는 emulator의 fork된 copy에 대해 실행

forkserver에는 unicorn's jit를 위한 캐싱 메커니즘을 포함하고 있다.

block을 direct하게 instrumentation을 넣기 때문에 indrect jump의 필요가 없어서 QEMU모드에서의 block liking을 다시 활성화시키는 기능 가능

-> step은 다음과 같다.

1. laod the current input

2. call place_input_callback : 하네스는 적절한 위치의 emulator memory에 input write

-> persistent모드일 때 에뮬레이터는 추가적인 상태 변화를 reset해야함

3. exit에 도달해서 hook에 의해 exec()이 취소되거나 잘못된 상태에 도달할 때까지 emulate.

4. Unicorn return을 확인하고 crash_validation_callback 호출 (충돌을 발견하기 위한 추가 처리 가능)

5. back to step3 (persistent mode일 경우)

 

* QBDI

LLVM을 이용해서 안드로이드 라이브러리와 closed-source 라이브러리에 complier instrumentation 가능

-> QBDI라는 android native library를 위한 프레임워크를 지원하기 때문에 가능

 

* Platform Support

GNU/Linux(Win mode - Win32), Android, iOS, macOS, FreeBSD, OpenBSD, NetBSD, Debian, Ubuntu, NixOS, Arch Linux, Free BSD, Kali Linux

- libdislocator : AFL allocator에서 memory error catch (여러 다른 OS에 이식 & 지원되지 않는 루틴 확장)

 

* Snapshot LKM

AFL은 fork()를 기반으로 state-restore 메커니즘을 구현 (bottleneck)

-> AFL++은 Linux Kernel Module과 통합 (Perfuzz의 프로세스 스냅샷과 restore의 경량화된 메커니즘에 영감)

-> 스냅샷을 사용할 경우 recompile 불필요 & 드라이버를 한 번 로드되면 모듈이 자동 감지됨

 

* Usecase 평가

- Default AFL setup, MOpt, Ngram, RedQueen, Ngram4&Rare, MOpt&RedQueen

- RedQueen : 레드퀸은 roadblock을 우회할 수 있었는데 모든 대상에 대해서 가능하는 것은 아니다.

(a)처럼 RedQueen만으로 성능이 좋을 수 있지만, (g)를 보면 RedQueen만으로는 모든 종류의 깊이를 도달할 수 없었고, MOpt를 통해 적용 범위를 추가로 늘리는 것이 도움이 됐다.

- MOpt : 종종 매우 효과적이지만 그렇지 않으면, 중간이 없이 성능이 매우 나쁘다.

- RedQueen & MOpt : (b), (d), (e), (g)를 보면, 시간이 걸리더라도 RedQueen과 MOpt의 조합은 유용하다.

또 (i)를 보면 RedQueen의 긍정적인 효과가 MOpt의 부정적인 영향을 상쇄하는 것을 확인할 수 있다.

- Ngram : (i)와 (c)를 보면 좋은 성능을 보인다.

 

* Future Work

- Scaling :  AFL++의 multiple thread로의 확장 개선

- Collision-Free instrumentation : AFL의 hash 방식은 충돌 발생, 속도와 정확성 사이의 trade-off

- Static Analysis for Optimal Fuzz Settings : 타겟에 대한 정적 분석을 우선 수행하여 최적의 솔루션 조합을 파악

- Plug-in System : 스케쥴러 + executor + queue 까지 플러그인 방식으로 추가/변경

 

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