[최종 정리] AFL의 특징과 AFL++의 개선방안

AFL 로직

[출처] https://wogh8732.tistory.com/272

./afl-fuzz -i input -o output -- path/to/objdump -x @@

 

1. afl-fuzz에서 objdump를 실행한다.

2. objdump가 처음으로 실행되면서 afl-fuzz와 pipe로 통신하며 forkserver를 만들고, 새로운 타겟 인스턴스(??)를 fork call()로 실행한다.

3. input 파일이 fuzz 대상 프로그램(objdump)으로 전달된다.

4. 실행된 결과를 공유 메모리에 기록하여 실행을 완료한다.

5. afl-fuzz는 공유메모리에서 fuzz 대상(objdump)이 남긴 기록을 읽고 이전 항목을 변경하여 새로운 입력을 만든다.

6. 새롭게 만든 입력은 다시 프로그램에 들어가서 실행된다.

 

[**]- 처음에 binutils를 afl-gcc로 컴파일할 때 forkserver 관련 코드가 삽입되고, 실행되면 해당 프로그램(objdump)에서 forkserver를 만든다.    + 이때 instrumentation code로 삽입된다. 

---

정리

	AFL	AFL++
power scheduling ( scheduling 목적 : smart testcase selection을 통해 전반적인 coverage와 bug detection을 개선하기 위함 )	- power scheduling은 없다.  - A modern coverage-guided fuzzer may implement different prioritization algorithms to schedule various elements in the fuzzing pipeline.	- AFLFast(fast, coe, explore, quad, lin, exploit) - MOpt(core, pilot) - mmopt, rare, seek
mutator	- deterministic - havoc	- deterministic - havoc - Custom Mutator API - Input-To-State mutator(I2S) → AFL++에서 RedQueen의 I2S를 기반으로 mutator 구현 - MOpt mutator → AFL++은 MOpt의 core와 pilot mode를 구현한다. MOpt는 AFL++에 패치되었으므로 I2S mutator와 결합될 수 있다.
instrumentation	(문제점) instrumentation할 때 hitcount 매커니즘이 overflow되는 문제	neverzero, saturated counters 방법으로 개선. - LLVM - GCC - QEMU - Unicornafl - QBDI
execve 성능 경량화	forkserver	snapshot LKM

---

[ 추가 ]

AFL의 roadblock 문제점을 해결한 RedQueen

coverage 기반 퍼저는 roadblock이라는 문제에 시달린다. _AFL의 문제점

( roadblock : 특정 장벽 너머의 코드를 탐색하기 어려워지는 상황. 일반적으로 대규모 비교연산이 이에 해당한다. )

 

↓ 해결

 

RedQueen

• taint tracking이나 symbolic execution 같은 비싼 기술없이 hard comparison과 checksum checks를 우회하기 위한 가능성을 탐색했다.
• 이 퍼저는 적어도 하나의 피연산자에서 input과 직접적인 의존성을 갖는 비교유형인 I2S로 정의된 comparison에 집중한다. 

 

MOpt

• Optimized Mutation Scheduling for Fuzzer
• mutation-based fuzzing은 one of the most popular vulnerablility discovery solutions
• 이것의 interesting testcases를 생성하는 성능은 mutation scheduling strategies에 의존한다.
• (하지만 문제점 존재)
  • 기존 fuzzer는 일반적으로 특정한 분포(distribution)를 따라 mutation operator를 선택하므로 일반 프로그램의 취약점을 찾는데 비효율적이다.
• (해결)
  • MOpt는 새로운 mutation scheduling scheme이다.
  • 이는 mutation-based 퍼저가 취약점을 더 효율적으로 발견할 수 있도록 한다. 

---

결과적으로 어떤 조합이 가장 optimal하다고 결론내릴 수는 없다. 

---

AFL++ 개발 개요

• 퍼징 기술을 결합(integrate)하는데 문제 발생
• 이때 base로 AFL Fuzzer를 선택했다. 
• 즉, 최근 퍼징 연구들을 통합해 하나의 사용가능한 도구로써 AFL++을 개발했다. 

AFL의 특징 및 한계

• mutations
  • deterministic stage : testcase의 content에 single deterministic mutations(bit fip, addition, substitution...)를 포함한다.
  • havoc stage : mutations are randomly stacked and include also changes to the size of the testcase.
  • splicing stage : merge two test cases into one and apply havoc
  • A common issue for fuzzers : parsing stage 이후 프로그램의 상태를 inaccessible하게 만들고 invalid inputs을 생성해야 한다는 것이다.
    • 이 문제를 해결하기 위해 효과적이고 효율적인 input을 생성하는 모델링 기술 : AFLSmart
• forkserver
  • execve()의 overhead를 줄이기 위함
  • fuzzer는 target에 forkserver를 inject한다.
  • AFL이 test case를 실행해야 할 때마다 AFL이 input을 쓰고(write), target에게 스스로 fork하라고 명령한다.
  • child가 test case를 실행하고, parent process는 기다린다.
  • forkserver는 또한 target에서 나중에 fork할 수도 있다. 
• persistent mode
  • fork를 지속적으로 사용하는 것 역시 bottleneck. 이에 대한 개선 방법

AFL++이 어떻게 해결했는가

• Seed scheduling
  • AFL++의 seed scheduling은 AFLFast 논문의 방법을 기반으로 한다.
  • AFLFast의 모든 스케줄을 포함한다. (fast, coe, explore, quad, lin, exploit)
  •  그 외에도 mmopt, rare, seek라는 추가적인 스케줄 방식도 제공된다. 
    • mmopt : 새롭게 발견된 path를 더 자세히 조사하기위해 newest seeds의 score을 증가시킨다.
    • rare : 다른 모든 schedule과 다르게 runtime of the seed를 무시한다. 그리고 추가적으로 seeds with edges that are rarely covered by other seeds에 집중한다. 
• muators
  • deterministic, havoc
  • custom mutator API
    • AFL++은 new research를 위해 쉽게 확장될 수 있고 취약점 발견을 위해 특정한 타겟에 맞게 조정될 수 있다 . 이를 위해 ever-growing(계속 늘어나는) API를 제공한다. 현재 상태는 아래와 같다.  
    • 퍼징 연구가 AFL++의 최상단에서 novel scheduling, mutation, minimization을 build할 수 있도록 한다. (현재 tool과 마찬가지로)
    • with the current API, for instance, AFLSmart can be rewritten completely as an AFL++ plugin.
    • 한 마디로, AFL++은 새로운 AFL 연구 진행시 쉽게 채택할 수 있도록 일종의 플러그인 형태로 개발하는 방안을 구상했다.
  • input-to-state mutator
    • AFL++은 RedQueen의 Input-To-State를 기반으로 mutator를 구현했으며 약간의 최적화까지 추가했다.
    • colorization은 input의 bytes의 entropy를 증가시키는데 매우 효과적으로 보이지만 fuzzer를 많이 slow down 할 수 있다. (문제점)
    • 우리는 coverage bitmap의 해시값이 동일할 때 뿐만아니라 실행속도가 2배 이상 느릴때 mutated regions를 유지하기 위해서 colorization을 확장했다.
    • 이 개선방안은 Redqueen을 위한 pathological target의 차이를 만드는 것으로 보인다. 
  • MOpt mutator
    • AFL++ implements the Core and the Pilot mode of MOpt.
    • 추가적으로 MOpt는 AFL++을 위해 패치되며 Input-To-State mutator로 결합될 수 있다. 
    • On top, AFL++ supports interleaving of MOpt with the standard mutation modes.
• Instrumentations
  • AFL++은 instrumentation을 위해 LLVM, GCC, QEMU, Unicornafl, QBDI를 지원한다.
  • 기존 AFL에서 instrumentation을 할 때 hitcount 매커니즘이 overflow되는 문제가 있었다. 
  • AFL++에서 이를 개선하기 위한 방법으로 NeverZero와 Saturated Counters라는 방법을 제안했는데 실험해보니 NeverAero가 효과가 좋았다. 때문에 NeverZero를 default로 적용해둔 상태이다.
• Snapshot LKM
  • AFL이 사용하는 fork() 방식은 성능 차원에서 bottleneck의 원인이 될 수 있다.
  • 때문에 AFL++은 LKM(Linux Kernel Module)을 integrate했다. (inspired by Perffuzz)
    • Perffuzz는 프로세스 snapshot과 restore에 대해 경량화 매커니즘을 구현했다.
    • 실제로 fork에 비해 2배 성능 차이 존재