이것저것/논문 리뷰

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

 https://www.usenix.org/system/files/woot20-paper-fioraldi.pdf 의 내용 정리

 

1.1. New Baseline for Fuzzing: AFL++

1.1.1. Seed Scheduling

AFL++에서는 AFLFast를 포함하고, AFLFast에서 제시한 ‘power scheduling’을 확장해 “Seed Scheduling”을 만들었다. 

 

1.1.1.1. Power Scheduling (AFLFast)

총 6개의 CPU 스케줄링 함수를 제시했다.

  • fast (the exponential schedule)
  • coe (cut-off exponential)
  • explore (the exploration-based constant schdule): default scheduling 방식이다.
  • quad (the quadratic schedule)
  • lin (the linear schedule)
  • exploit (the exploitation-based constant schedule

1.1.1.2. Seed Scheduling (AFL++)

2개의 스케줄링 함수가 추가되었다.

  • fast
  • coe
  • explore
  • quad
  • lin
  • exploit
  • mmopt : 새로운 seed가 새로 발견되는 경로를 더 깊이 탐색할 수 있도록 seed의 score를 증가하는 방식으로 작동한다.
  • rare : 실행 중인 seed는 무시하고, 오히려 다른 seed과 거의 겹치지 않는 edge가 있는 seed가 있는지 확인하고 투입할 seed의 순서를 정한다.

 

1.1.2. Mutators

1.1.2.1. Custom Mutators API

사용자가 자신에게 맞는 Mutator로 변형해서 사용할 때 편하게 mutator를 개발할 수 있도록 플러그 인 형태로 API함수들을 제공한다.

(C/C++) 아래의 함수들을 재정의하여 사용하면 된다.

void *afl_custom_init(afl_state_t *afl, unsigned int seed);
void afl_custom_deinit(void *data);

afl++가 시작되고 마칠때 호출되는 함수

unsigned int afl_custom_fuzz_count(void *data, const unsigned char *buf, size_t buf_size);

queue entry에서 입력값을 결정할 때, 해당 input을 가지고 몇 번의 fuzzing을 시도할 것인지 (그 값으로 몇 개까지의 mutation을 만들어낼 것인지)를 사용자가 직접 지정할 수 있는 함수

size_t afl_custom_fuzz(void *data, unsigned char *buf, size_t buf_size, unsigned char **out_buf, unsigned char *add_buf, size_t add_buf_size, size_t max_size);     

주어진 input 값에 대해 fuzzing을 하는 함수

  • 추가적인 testcase도 받을 수 있다.
const char *afl_custom_describe(void *data, size_t max_description_len);

가장 최근의 mutation 값에 의해 생긴 현재의 test-case의 상태를 묘사하는 함수

  • ex. crash가 발생하고 난 후, 해당 test-case에 대한 이름을 지어줄 수 있다. 
  • crash를 일으키는 mutation을 재생산할 때 도움된다.
size_t afl_custom_post_process(void *data, unsigned char *buf, size_t buf_size, unsigned char **out_buf);

입력값의 data format을 변형해 알맞게 변형하는 함수

  • 타겟에 대한 fuzzing을 시작하기 전에, mutated data의 형태가 target에 들어가야할 입력 포맷과 다른 경우, 옳은 포맷에 맞도록 변형해준다.
const char *afl_custom_describe(void *data, size_t max_description_len);

trimming 작업의 시작 부분에서 호출되는 함수;

  • 초기 버퍼의 값을 받아온다.
  • 해당 input 파일(값들)에 대해 trimming 내부 작업을 반복하는 횟수를 리턴한다.
  • trimming algorithm이 남은 step들을 셀 수 없는 상황이라면, 

→ 이 작업이 계속되는 동안 afl_custom_post_trim은 0을 리턴할 것이다.

  • 더이상 trimming 할 작업이 없다면 이 전의 리턴 값들을 더하거나 ‘0’을 리턴하겠지..?
size_t afl_custom_trim(void *data, unsigned char **out_buf);

trimming 작업을 실행할 때마다 호출되는 함수; 

  • 현재의 상태를 기억하고 반복할 때마다 reparsing steps(재준비 단계)을 저장한다.
  • trimmed input을 반환하는데, 이 때 그 길이가 초기의 input data보다 길면 안된다.
int afl_custom_post_trim(void *data, unsigned char success);

각 trimming 작업이 끝난 후 호출되는 함수;

  • trimming 이 성공적이였는지 아닌지에 대한 정보를 전달하는 것이 목적이다.
  • 다음 trim 반복 순서를 리턴한다: 0~ afl_custom_init_trim의 최대 리턴 값
size_t afl_custom_havoc_mutation(void *data, unsigned char *buf, size_t buf_size, unsigned char **out_buf, size_t max_size);

주어진 input에 대해 하나의(한번의?) mutation을 실행한다.

  • 이 mutation은 havoc 단계에 있는 다른 mutation들과 함께 쌓여있는다.
unsigned char afl_custom_havoc_mutation_probability(void *data);

조율(최적화?)을 활성화하는 havoc stage에서  custom mutation이 호출될 확률을 리턴한다.

unsigned char afl_custom_queue_get(void *data, const unsigned char *filename);

custom fuzzer가 현재의 queue entry를 퍼징해야할 지를 결정하는 콜백 함수;

  • 사용자가 input 에 대한 메타데이터를 초기화할 수있다.
void afl_custom_queue_new_entry(void *data, const unsigned char *filename_new_queue, const unsigned int *filename_orig_queue);

새로운 testcase를 큐에 추가한 후 호출되는 함수; 

  • 디스크에 메타데이터를 저장해두기에 좋은 hook를 제공한다.

 

1.1.2.2. Input-To-State Mutator

AFL++에서 REDQUEEN의 Input-to-state(I2S)를 기반으로 최적화해 구현한 muator다.

다음은 REDQUEEN의 I2S에서 확장한(최적화한) 개념 2가지이다.

  1. 색상화(colorization)
  2. 비교의 확률론적인 퍼징

3.1.2.2.1 CmpLog Instrumentation

REDQUEEN의 방식이 아니라, WEIZ 처럼 공유 테이블(shared table)을 사용한다. 

각 비교는 최근 256회 실행된 피연산자를 256MB 테이블에 기록해 fuzzer와 target(대상 바이너리)간에 공유한다. 

총 크기인 512KB는 캐시 인접성의 측면에서 효율적인 방법으로 통과할 수 있다. 비교를 사용하지 않은 경우 메타데이터는 등록하기에 충분하고, 피연산자에 해당하는 메모리에 접근할 수 없다. 

이 instrumentation (CmpLog Instrumentation)은 LLVM과 QEMU의 instrumentation에서 사용할 수 있다. 

 

1.1.2.3. MOpt Mutator

MOpt에서는 4개의 모듈을 제안했다.

  • PSO initialization Module
  • Pilot Fuzzing Module
  • Core Fuzzing Module
  • PSO Updating Moduel

AFL++에서는 MOpt의 4가지 모듈 중 “Core”와 “Pilot” 모듈을 구현했다.

MOpt에서 AFL++를 위한 패치도 제공하여, AFL++의 Input-To-State Mutator에서 이 패치를 사용할 수 있다

 

1.1.3. AFL++ Instrumentations

AFL++는 여러 종류의 instrumentation을 지원한다

  • LLVM, GCC, QEMU, Unicorn, QBDI 등

AFL++은 기존 AFL에서 instrumentation을 하면서 hit_count가 overflow되는 문제를 해결하기 위해 NeverZero와 Saturated Counters라는 방법을 제안했다.

  • Saturated Counters
    실험해보니 성능이 좋지 않아 잘 사용되지 않는다.
  • NeverZero

bitmap 엔트리에 carry flag를 추가해서 만약 edge가 한 번이라도 실행되었다면 절대 0이 될 수 없도록 한다. 즉, overflow가 발생하더라도 carry flag의 값이 있기 때문에 0으로 되돌아가지 않는다.

⇒ AFL을 coverage 및 속도 측면에서 향상시켰다.

⇒ AFL++의 default 로 지정해뒀다. (따로 정해주지 않아도 carry flag로 넘어가 overflow에 의한 0으로의 전환은 일어나지 않는다.)

1.1.3.1. LLVM

AFL++는 edge coverage + coverage metrics(수행결과)를 지원한다.

  • Context-sensitive Edge Coverage
    피호출자의 독특한(유일한) ID와 각 블록에 할당된 ID를 XOR 연산한다. 

AFL++ LLVM 모드에서는 사용자가 instrumentation에 특정 소스 모듈을 지정할 수 있다. 

 

AFL++ LLVM 모드에서는 앞서 언급된 모든 기능과 결합된 INSTRIM 패치를 구현한다.

더보기

* INSTRIM

LLVM으로 계측할 때 기본 블록을 선택하는 효율적인 방법이다. 

대부분의 target(대상 바이너리)에 대한 표준 instrumentation의 최소 절반으로 instrumented된 영역의 수를 줄여서 속도 성능의 측면에서 fuzzer를 향상시킨다. 

1.1.3.2. GCC

오래된 afl-gcc와 함께, AFL++에 GCC plugin으로 전해졌다. 이 플러그인은 연기된 초기화(deferred initialization)과 persistent mode-AFL LLVM mode-를 지원한다. 

그 외의 지원되는 기능들은 LLVM와 같지는 않다.

 

1.1.3.3. QEMU

QEMU 모드에서는 실행 시간 중에 instrumentation을 추가할 수 있도록 했다. 즉, binary-only fuzzing을 할 수 있는 듯 하다. 

  1. Compare Coverage

source 코드 수준에서와 binary 수준에서의 fuzzing의 차이를 줄이기 위해 AFL++의 QEMU 모드에서는 CompareCoverage를 이용해서 비교문들을 나눈다.

  1. Persistent Mode
    1. 함수의 주위를 계속 돈다.

2. entry와 exit 지점을 특정한다.

 

1.1.3.4. Unicorn AFL

unicorn afl에서 제공하던 몇 가지 API들을 그대로 혹은 수정해 가져왔다. AFL++ 관련 API들을 사용하면 harness가 언제든지 빠른 persistent 모드를 시작하도록 하거나 crash를 감지하도록 multiple-exit 및 사후 fuzzing 처리기를 설정할 수 있게한다.

 

1.1.3.5. QBDI

AFL++에서는 Android Library들도 LLVM을 사용한 compiler instrumentation으로 퍼징할 수 있고, closed-source library들도 측정할 수 있다.

 

1.1.4. Platform Support

AFL++는 GNU/Linux 뿐만 아니라 Android, iOS, macOS, FreeBSD, OpenBDS, NetBSD, Debian, Ubuntu, NixOS, Arch Linux, Kali Linux에서 사용할 수 있다. 

QEMU 혹은 Wine을 사용하면 GNU/Linux상에서 Win32 바이너리에 대한 퍼징도 할 수 있다.

 

1.1.5. Snapshot LKM

1.1.5.1. Background (AFL의 문제점)

AFL에서는 ‘fork()’를 기반으로 상태를 저장 및 복구하는 mechanism을 사용했다.

하지만 이 메커니즘은 타겟의 수가 많아지면 병목현상(bottleneck)이 발생한다.

 

1.1.5.2. Snapshot LKM

AFL++은 Linux Kernel Module을 통합해서, 프로세스를 포착하고 저장할 수 있는 보다 가벼운 메커니즘을 구현했다.

  • AFL의 fork()와 비교했을 때 약 2배의 이득을 볼 수 있다.
  • 여러 core에서 병렬 퍼징을 할 때 각 코어에 대한 차이가 크다.
  • fork()를 쓰다가 snapshot을 쓰려고 해도 타겟 프로그램을 재컴파일할 필요는 없다.

1.2. Future Work

AFL++은 완성된 퍼저보다는 여전히 계속 개발 중에 있으며, 계속 개선 및 발전하고 있는 fuzzer다. 

 

1.2.1. Scaling (크기 조정)

멀티 스레딩 방식으로 확장하는 것에 대한 이슈다; 아직까지는 썩 이상적인 상태는 아니다.

  • fork() → snapshot LKM (LinuxKernelMode)
  • AFL++ 코드를 완전히 thread-safe하게 바꾸는 것이 목표
  • multi-threading 지원, 병렬 퍼저들에 대한 동기화 중 오버헤드 최소화 시도

 

1.2.2. Collision-Free instrumentation

AFL 해시 방법에 의한 기존 instrumentation은 충돌을 발생한다.

하지만 이 문제를 해결하기 위해서는 ‘accuracy’(정확성)과 ‘speed’(속도) 사이에 trade-off가 발생한다. 이 문제는 해결하려고 노력중이다.

 

1.2.3. Static Analysis for Optimal Fuzz Setting

현재의 목표는 가장 보편적으로 좋은 instrumentation, mutation, scheduling기법을 기본 으로 사용하려고 하는 것이다. 하지만 최고의 성능을 내는 것은대상 바이너리에 따라 결정된다.

 

1.2.4. Plug-in System

여러가지 plug in 시스템들이 개발되었다. 

대표적으로 현재 custom mutator는 개발이 되어있다.

앞으로는 스케줄러, executor(실행자), queue까지 플러그인 방식으로 추가하거나 변경할 수 있도록 할 예정이다.

SMALL

'이것저것 > 논문 리뷰' 카테고리의 다른 글

[USENIX] Charger-Surfing: Exploiting a Power Line Side-Channel for Smartphone Information Leakage  (0) 2021.08.24
[NDSS] WINNIE: Fuzzing Windows Applicationswith Harness Synthesis and Fast Cloning  (0) 2021.08.23
[USENIX] Breaking Through Binaries: Compiler-quality Instrumentationfor Better Binary-only Fuzzing  (0) 2021.08.23

    티스토리툴바