[논문 정리] AFL++: Combining Incremental Steps of Fuzzing Research

Abstract

AFL++ 특징

• 최신 퍼징 연구 incorporate

본 연구의 목표

• AFL++이 a new baseline tool이 되길
• 새로운 technique를 빨리 테스트해 볼 수 있길
• single technique과 state-of-the-art technique의 effectiveness(기술 효과)와 combination with other technique를 평가할 수 있길

---

Introduction

• 퍼징에 대해 증가하는 관심
• 퍼징을 개선하는데 필요한 기술이 많아지고 있다. 
  • fuzzing techniques are often developed orthogonally and independently
  • so, combining them can be a long process
• fuzzing tech를 결합하는데 부정적인 의견..을 AFL++이 해결하겠다
  • 광범위하게 이용 가능하고 연구 지원을 받는 퍼징의 기준을 높이고 연구자들에게 구축할 수 있는 확장 가능한 API를 제공함으로써 이런 문제를 해결하려고 한다.
  • 새로운 퍼징 프레임워크 AFL++ 제안
  • AFL++에서 이미 구현된 최신의 orthogonal feature로 그들의 proposal의 combination을 평가할 수 있다.
  • 최첨단 연구를 통해 채택된 사용하기 쉬운 다양한 기능을 industry 전문가들에게 제공하여 fuzzing campaign의 결과를 크게 개선할 수 있다.
• AFL이 base로 채택된 이유
  • unmaintained for 18months while at the same time a lot of community patches and academic forks were available.

Contributions

• AFL++이 recent fuzzing research를 one usable tool로 통합할 것이다.
• 미래 연구를 implement하고 combine하기 위한 접근 가능하고 보장된 방법인 Custom Mutator API(AFL++의 새로운..)를 제안한다.
• AFL++을 사용하면 a selection of incorporated technologies and features 각각을 against, with로 평가한다. 
  • 우리는 각 technology가 얼마나 target-의존적인지 보여준다. 

---

State-of-the-Art

AFL

• mutational, coverage guided fuzzer
• 프로그램에서 previously unexplored points에 도달하기 위해 a set of testcases를 mutate한다.
• when this happend, new coverage를 트리거하는 testcase는 testcase queue의 부분으로써 저장된다.
• coverage guided feedback
  • AFL의 coverage guided feedback은 hybrid metric이고, one run에서 각각의 edge가 시행된 횟수와 edge coverage를 결합(combine)한다. (??)
  • coverage feedback을 사용하는 AFL은 trimming 단계에서 온전한 coverage를 유지하면서 queue의 각 testcase에 대해 testcase를 줄이고 target seed를 개선하려고 노력한다. 
• mutations
  • AFL의 mutation은 두 가지로 나뉜다.
  • deterministic
    • testcase의 content에 single deterministic mutations(bit flip, addition, substitution..)를 포함한다.
  • havoc
    
    • In havoc, mutations are randomly stacked and include also changes to the size of the test case. (??)
  • 이후 단계에서는(splicing stage) AFL은 two test case를 하나로 merge하고 havoc을 적용할 것이다.
• forkserver
  • execve()의 overhead를 줄이기 위해서 AFL은 forkserver를 이용한다.
  • 1. fuzzer injects a forkserver(controlled through an IPC mechanism) into the target.
  • 2. AFL이 test case를 실행해야할 때마다 AFL writes the input
  • 3. then tell the target to fork itself
    • child : execute the test case
    • parent : waits for this time 
  • 이 경우, fuzzer does not pay the cost of running the expensive initialization and startup routines each time.
• persistent mode
  • persistent mode는 performance를 greatly 개선할 수 있다. 
  • fork()가 bottleneck(성능 저하)으로 알려져있기 때문에 Persistent Mode의 경우 target은 각 test case에 대해 fork하지 않는다.

Smart Scheduling

• modern coverage-guided fuzzer는 fuzzing pipeline에서 다양한 elements를 schedule하기 위해 다른 prioritization algorithm을 구현한다.
• schedular의 목표
  • smart test case selection을 통해 전반적인 coverage와 bug detection을 개선하기 위함
• AFLFast
  • AFLFast는 더 많은 branch를 explore하고 더 많은 버그를 찾기 위해 low-frequency path를 강조할 필요가 있음을 보여준다. 
  • 이들이 강조한 두 문제점
    • low-frequency path를 강조하기 위해 퍼저가 seed를 고르는 순서는?
      • 본 논문에서는 a set of novel search strategies로 해결했다. 
    • 각 seed에서 생성되는 input의 양을 조절할 수 있나?
      • by introducing six power schedules to compute the energy from parameters collected during the fuzzing process.. 로 해결했다. (??)
• MOpt
  • Optimized Mutation Scheduling for Fuzzers
  • As a horizontal problem of seed scheduling, MOpt는 mutation scheduling을 소개했다.
  • 이 최적화는 coverage를 빨리 발견하는 퍼저의 능력을 향상시킨다.
  • In their patch to AFL, 본 논문은 fuzzing stages를 두 모듈로 나눴다. 
    • Pilot
      • operators를 평가하는 모듈
      • effectiveness에 기반해 probabilities 할당
    • Code
      • Pilot중에 발견된 probabilities를 고려하여 mutation 생성하는 모듈

Bypassing Roadblocks

• 전통적으로 coverage guided fuzzer는 그들 뒤에서 explore code를 막는 장애물로 고통받는다.(??)
  • 전형적인 장애물은 larger comparisons, checksum checks
• 이 문제를 해결하기 위해 광범위한 연구가 진행되었다. 
• LAF-Intel
  • 위의 roadblock을 해결하는 방안인듯..?? 제대로 이해 못함ㅠ 
  • multiple single-byte 비교로 split해서 hard multi-byte comparisons로 bypass하는 것을 목표로 한다.
• RedQueen
  • 최근 RedQueen은 hard comparisons과 checksum checks를 bypass하기 위한 possibility를 explore했다. taint tracking이나 symbolic execution같은 비싼 기술없이.
  • 이 부분은 생략해도 될 듯................ 필요하면 돌아오는 걸로

Mutate Structured Inputs

• fuzzer의 공통된 이슈는 그들이 대부분의 invalid input을 생성하여 parsing stages 이후 프로그램 상태를 inaccessible하게 만들 수 있다는 점이다.
  • 이를 해결하는 방법은 generated inputs의 space를 효과적으로 줄이는 input model의 사용이다.
  • 이것은 feedback-based fuzzer이 프로그램에서 deep path를 explore하는 것을 허락한다. 
• AFLSmart
  • AFL에 structured fuzzing이 소개됐다.
  • 위에서 제기한 문제의 해결 방안이겠지..? 일단 넘어간다...

---

A New Baseline for Fuzzing

• AFL++의 engineering background를 설명할 것이다.
• core of AFL++ == forked version of AFL
• Seed Scheduling
  • seed scheduling은 AFLFast 논문의 방법을 기반으로 한다. 
    • Markov Chain을 이용해 coverage 기반의 grey-box fuzzing을 제시했다.
    • AFLFast의 모든 schedules를 포함한다. (fast, coe, explore, quad, lin, exploit)
    • 이 중 기본이 되는 것은 explore이다. 
    • 뿐만아니라 AFL++에는 mmopt, rare, seek라는 추가적인 스케줄 방식도 제공된다.
• Mutators
  • AFL++은 전통적인 deterministic, havoc pipeline 보다 더 많은 mutator를 포함한다.
  • Custom Mutator API
    • AFL++은 학계에서 새로운 AFL 관련 연구를 진행할 때 이를 손쉽게 채택할 수 있도록 일종의 플러그인 형태로 개발하는 방안을 구상했다.
    • 예를 들어 AFLSmart를 제안한 사람이 이러한 API를 잘 활용한다면 AFL++의 플러그인 형태로 만들 수 있는 것이다. 
  • Input-To-State Mutator
    • AFL++은 RedQueen의 Input-To-State를 기반으로 한 mutator를 구현했으며 약간의 최적화까지 추가했다.
  • MOpt Mutator
    • AFL++에는 core와 pilot이 구현되어있다. 
    • 뿐만아니라 MOpt의 개발자가 AFL++을 위해 패치를 제공했다. 
    • 그래서 AFL++의 Input-To-State Mutator에서 이를 사용할 수도 있다. 
• Instrumentations
  • AFL++은 instrumentation을 위해 LLVM, GCC, QEMU, Unicornafl, QBDI를 지원한다.
  • 기존 AFL에서 instrumentation을 할 때 hitcount 매커니즘이 overflow되는 문제가 있었다. 
  • AFL++에서 이를 개선하기 위한 방법으로 NeverZero와 Saturated Counters라는 방법을 제안했는데 실험해보니 NeverAero가 효과가 좋았다. 때문에 NeverZero를 default로 적용해둔 상태이다. 
• Platform Support
  • AFL++은 GNU/Linux 뿐만아니라 Android, iOS, macOS, FreeBSD, OpenBDS, NetBSD를 지원한다.
  • 운영체제 기준으로는 Debian, Ubuntu, NixOS, Arch Linux, FreeBSD, Kali Linux 에서 사용 가능하다. 또한 QEMU 를 사용하거나 Wine을 사용하면 GNU/Linux 상에서 Win32 바이너리에 대한 퍼징도 가능하다.
• Snapshot LKM
  • AFL이 사용하는 fork() 방식은 성능 차원에서 bottleneck의 원인이 된다는 점이 익히 알려져 있다. 
  • 때문에 AFL++은 Linux Kernel Module을 integrate했다. (inspired by Perffuzz) 
    • Perffuzz는 프로세스 snapshot과 restore(복원)에 대해 경량화 매커니즘을 구현했다.
    • 실제로 fork 방식에 비해 2배의 성능 차이가 있었다. Plugin systemcore of AFL++ == forked version of AF

---

Future Work

1. Scaling
2. Collision-Free instrumentation
   • AFL의 해시방식은 충돌이 발생하는데 이걸 바꾸면 속도와 정확성 사이의 trade-off가 생긴다. 뭐가 나을지 최적화 방법 고민중
3. Static Analysis for Optimal Fuzz Settings 
4. Plugin system

---