보안

[Fuzzer] AFL/AFL++이란?

pumisj 2026. 3. 31. 11:52

서론

fuzzer의 전반적인 내용을 익혔기에 이번엔 AFL에 대해서 집중적으로 알아보고자 한다.

 

맨 처음에 잘 못 읽었던 논문 "AFL++: Combining Incremental Steps of Fuzzing Research"와 AFL의 Whitepaper을 읽으면서 배운 내용을 정리해보았다.

 

그럼 시작하겠다.

 

참고 자료

  • Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse, "AFL++: Combining Incremental Steps of Fuzzing Research," in Proceedings of the 14th USENIX Workshop on Offensive Technologies (WOOT 20), 2020.
  • Valentin J.M. Manès et al., "The Art, Science, and Engineering of Fuzzing: A Survey," IEEE Transactions on Software Engineering, vol. 47, no. 11, pp. 2312-2331, 2019.
  • https://github.com/google/AFL/tree/master/docs

AFL

AFL은 대표적인 Grey-box fuzzer로 정적, 동적 정보를 바탕으로 퍼징을 진행한다.

퍼징은 다음과 같은 작업을 반복 수행하는 것을 말한다.

  1. Preprocessing
  2. Scheduling
  3. mutation
  4. configure update
  5. evaluation

AFL은 Minset관리나 스케줄링같은 주요 작업에 코드 커버리지를 사용한다.

 

이 커버리지를 측정하기 위해서 afl-gcc, afl-clang이나 afl-clang-lto 등의 컴파일러를 사용하는데, 컴파일시에 기계어로 직접 커버리지 측정 코드를 삽입한다.

 

해당 커버리지 코드는 논리적으로 다음과 같다.

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
  • cur_location
    • 복잡한 프로젝트를 링크하는 과정을 단순화하며, XOR 출력값이 균등하게 분포되도록 컴파일시에 무작위로 정해진다.
  • shared_mem
    • 64kB의 shared memory 구역. instrumentated binary (실행파일)를 실행하면서 이 출력 맵에 특정 튜플 (branch_src, branch_dst)이 실행되었음을 기록한다.

분기 개수별 충돌 확률

 

이렇게 실행 경로를 기록했을 때 다음과 같은 실행 추적을 구별할 수 있다.

  • A -> B -> C -> D -> E (튜플: AB, BC, CD, DE)
  • A -> B -> D -> C -> E (튜플: AB, BD, DC, CE)

마지막 비트 시프트 연산을 하는 이유는 튜플의 순서를 구분하기 위해서이다.

  • 시프트를 하지 않으면 (A → B) 와 (B → A) 를 구분할 수 없다.

또 경로를 튜플의 집합으로 보기때문에 전체적인 프로세스로는 고유해보일지라도 고유한 경로로 취급하지 않는 경우도 있다.

  1. A -> B -> C -> D -> E
  2. A -> B -> C -> A -> E
  3. A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E

이 경우 2번까지 처리된 뒤 3번 경로를 보면 모두 비트맵에 저장되어있는 경로이다.

따라서 3번은 고유 경로로 취급하지 않는다.

 

또한 튜플의 hit count를 고려하여 같은 튜플이라 할지라도 다른 버킷에 담는다.

  • 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+ (지수적으로 증가)

예를 들어 프로그램이 종료되고 (A, B) 튜플이 10번 실행되었고, 해당 버킷의 비트가 0이라면 새로운 경로를 찾은걸로 판단하여 비트맵에 저장한다.

 

이렇게 hit count별로 경로를 다르게 기록한다면 다음과 같은 장점이 있다.

  • 컴파일시에 랜덤으로 부여한 위치값이 겹쳐 서로 다른 튜플이 같은 비트맵 칸에 충돌하더라도, 두 엣지의 실행 횟수가 서로 다르다면 어느정도 구별이 가능하다.
  • 만약 프로그램이 설정한 타임아웃값을 넘어갈 경우, 그 시드가 커버리지를 늘린다고 하더라도 queue에 추가하지 않는다. 이로 인해 tarpit에 빠져들지 않는다.

두 방법 모두 path explosion을 피하기 위한 방법이다.

 

 

이런식으로 선별된 테스트 케이스들은 입력 큐에 추가되어 다른 유망한 테스트 케이스를 만드는데에 사용된다. (Scheduling)

 

AFL은 테스트 케이스를 변형할 때 현재까지 확인한 모든 튜플을 커버하면서도 실행 시간이 빠르고 크기가 작은 테스트 케이스를 선택하는 알고리즘을 사용하여 주기적으로 큐를 재평가한다.

 

이 알고리즘은 각 튜플마다 실행 시간과 파일 사이즈에 비례하여 점수를 매긴다.

그런 뒤 튜플은 다음과 같은 순서로 처리된다.

  1. temporary working set에 없는 튜플을 찾는다.
  2. 이 튜플에 대해서 승리한 큐 항목을 찾는다.
  3. 해당 항목의 모든 튜플을 temporary working set에 추가한다.
  4. 누락된 튜플이 있으면 다시 반복한다.

이런 과정으로 선별된 corpus는 일반적으로 처음 시작한 시드보다 5~10배 더 작으며, 다른 시드보다 더 많이 실행된다.

 

 

다음으로 테스트 케이스의 크기를 줄이는 작업을 한다 (Trimming).

 

해당 작업은 전체 코드 커버리지를 줄이지 않는 선에서 파일 크기를 줄여 실행 시간을 단축하고 중요한 형식 제어 구조를 건들일 확률을 높힌다.

 

AFL의 기본 trimmer는 가변적으로 데이터 블럭을 삭제하고 trace map에 영향을 미치지 않는다면 그대로 삭제한다.

 

afl-tmin은 더 철저하고 반복적인 알고리즘을 사용하며, trmming된 파일에 대해 알파벳 정규화를 시도한다.

  1. 처음엔 크게 데이터 블록을 0으로 채운다
  2. binary search 스타일로 블록 크기와 스텝오버를 줄여가며 블록을 삭제한다.
  3. 고유한 문자를 세고 각각을 0으로 바꿔 알파벳 정규화를 수행한다
  4. 0이 아닌 바이트에 대해 바이트 단위 정규화를 수행한다.

AFL은 instrumentation으로 받은 피드백을 통해서 다양한 파일 유형에서 똑같이 잘 작동하도록 매개변수를 최적화한다.

 

초기에는 순차적인 bit/byte flip, Arthmetic, known integer 등 변형이 deterministic하게 이루어지지만, 나중에는 무작위 bit/byte flip, test case splicing의 작업을 하면서 non-deterministic하게 새로운 테스트 케이스를 만든다.

 

PUT에 적용하는 모든 시드값이 핵심적인 로직을 실행하는건 아니다. 오히려 무작위로 변형을 진행하다보면 문법 검증 단계에서 막히는데, AFL에서는 이에 대해 두 가지 방법을 제시한다.

  1. 사전 정의된 dictionary terms를 제공함으로써 PUT가 기대하는 입력 검증을 통과할 수 있다.

실제로 SQLite의 키워드 목록을 AFL에 제공했을 때 다음과 같은 유효한 SQL 구문을 생성한다.

  • select sum(1) LIMIT (select sum(1) LIMIT -1, 1);
  • select round(-1)````;
  • select group_concat(DISTINCT + 1) | 1;
  • select length(?) in (hex(1) +++ 1, 1);
  • select abs(+0 + hex(1) - NOT + 1) t1;
  • select DISTINCT "Y", "b", (1) "Y", "b", (1);
  • select - (1) AND "a", "b";
  • select ?1 in (CURRENT_DATE, 1, 1);
  • select - "a" LIMIT - /* / / /- / / / */-1;
  • select strftime(1, sqlite_source_id());
  1. 자동으로 토큰을 식별하는 알고리즘을 적용한다.

예를 들어, PNG 파일의 경우에는 섹션을 시작할 때 사람이 읽을 수 있도록 4바이트의 magic value를 사용한다.

89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 | .PNG........IHDR
00 00 00 20 00 00 00 20 02 03 00 00 00 0e 14 92 | ................

만약 deterministic bit flipping 과정에서 특정 비트를 뒤집었을 때

  1. 해당 구간을 건드렸을 때 다른 인접한 구역을 건들였을 때와 다를 때나
  2. 해당 바이트 전체를 건들이는동안 발생하는 변화가 일관적일 때

afl에서는 이를 syntax token으로 간주하고 딕셔너리에 추가한다.

 

 

다음으로 찾아낸 크래시의 중복을 제거하는 과정을 거친다. (De-duping crashes)

 

다음 두 조건 중 하나가 충족되면 unique하다고 간주한다.

  • 크래시 추적이 이전에 없던 튜플이 보인경우.
  • 크래시 추적에 이전에 항상 있던 튜플이 사라진경우.

이 방식은 초기에 path count가 크게 늘어나지만, 나중에는 self-limiting 효과를 가져 새로운 경로가 늘어나지 않는다.

 

 

발견된 크래시가 실제로 보안적으로 위협이 되는지 판단하는 작업도 진행한다. (Investigating crashes)

 

가장 흔하게 발생되는 이슈는 Null pointer dereference나 BOF인데, 이는 단순히 무해한 버그일 수도 있고 근본적인 취약점이 발생하는 원인이 될 수도 있다.

 

이런 발견들을 분류하기 위해서 afl에서는 crash exploration mode를 제공한다.

  • crash를 일으키는 테스트 케이스에 대해서 crash exploration mode로 퍼징을 진행하면 피드백 메커니즘과 EA을 그대로 사용하면서 기존의 crash는 유지할 수 있다.
  • 그러면서도 instrumentation된 코드 내부에서 얼마나 더 멀리 갈 수 있는지 확인한다.
  • 이 과정에서 crash를 일으키지 않는 변이는 버려지며, path를 유의미하게 바꾸지 못하는 변이도 버려진다.

이렇게 만들어진 많은 corpus들은 기존 crash 테스트 케이스와 비교했을 때 살짝 다른 연관된 테스트 케이스이다. 이를 통해 해당 crash에 대해 어느정도의 제어를 가질 수 있다.

 

또한 이런 변형으로 OOB를 통과할 수 있는지 확인하고, 만약 가능하다면 그 다음에 어떤 일이 발생하는지 확인할 수 있다.

예를 들어, 다음은 일반 모드로 발견한 crash 테스트 케이스이다.

unrtf[7942]: segfault at 450 ip 0805062b sp bf957e60 error 4 in unrtf[8048000+1c000]

이 테스트 케이스는 segmentation fault를 유발하는데, crash exploration mode를 통해 파일을 조작했을 때 임의의 주소에서 결함을 유도할 수 있다는걸 발견할 수 있다.

unrtf[28809]: segfault at 88077782 ip 0805062b sp bff00210 error 4 in unrtf[8048000+1c000]
unrtf[26656]: segfault at 7271250 ip 0805062b sp bf957e60 error 4 in unrtf[8048000+1c000]

검증하는 과정에서 입력은 trimming되지 않는다는 점에서 기존 퍼징과 다르다.

 

 

Fork server

다른 퍼저는 성능을 향상시키기 위해 초기화 한 직후의 메모리를 복사해 퍼징을 반복할때마다 메모리를 다시 복구하는 방식을 사용하여 프로그램을 초기화하는 오버헤드를 줄인다 . (in-memory)

 

AFL은 fork server를 채용해 초기화 오버헤드를 줄인다.

 

LD_PRELOAD, PTRACE_POKETEXT, ELF 바이너리 또는 instrumentation 단계에서 fork server을 실행하는 코드가 삽입되어 프로그램의 초기화 과정이 끝난 뒤 실행한다.

 

실행 과정은 다음과 같다.

  • 프로그램의 지정된 지점에 도달
  • 퍼저의 명령에 의해 fork()를 호출해 새로운 프로세스를 생성.
  • 해당 프로세스가 대신 퍼징을 진행하고 결과를 부모에 전달

이 과정을 반복하여 초기화 오버헤드를 줄였으며, 일반적인 이미지 라이브러리의 퍼징 속도를 2배 이상 높혔다.

 

 

Parallelization

AFL은 병렬화를 지원한다.

 

기본적으로 AFL은 하나의 코어에 하나의 인스턴스를 지원하여 멀티 코어로 퍼징을 할 수 있다.

하지만 하나의 PUT에 여러 퍼저를 사용하면 각 인스턴스끼리 테스트 케이스를 공유할 수 없다.

 

이를 해결하기 위해 AFL에서는 테스트 케이스를 실시간으로 동기화하는 방법을 사용한다.

  • Single-system parallelization
    • 로컬 시스템에서 멀티 코어로 작업을 병렬화할 때는 공유 디렉토리를 만들어 인스턴스끼리 queue를 공유한다.
    • 인스턴스는 Master와 Secondary로 나뉜다.
      • Master: deterministic한 작업을 수행한다.
      • Secondary: non-deterministic (havoc)한 작업을 수행한다.
  • Multi-system parallelization
    • 기본 원리는 single-system parallelization과 비슷하지만 공유 파일 동기화에서 차이가 난다.
      • 로컬(메인) 컴퓨터의 output 디렉토리의 queue를 다른 모든 머신과 동기화한다.
      • 동기화는 30분 간격으로 진행

Binary-only instrumentation

AFL은 바이너리 파일에 대해서도 커버리지를 측정할 수 있도록 QEMU의 user emulation mode를 변형하여 사용한다.

 

QEMU는 Basic block를 translation unit으로 하여 instrumentation을 할 때 다음과 같은 코드를 삽입한다.

if (block_address > elf_text_start && block_address < elf_text_end) {
    cur_location = (block_address >> 4) ^ (block_address << 8);
    shared_mem[cur_location ^ prev_location]++; 
    prev_location = cur_location >> 1;
  }

이는 소스코드가 있는 파일의 instrumentation과 같은 기능을 수행한다.

 

에뮬레이터로 바이너리 파일을 번역하다보니 새로운 BB를 발견할때마다 번역하는 시간이 오래걸린다.

 

이를 해결하기 위해서 AFL의 부모 프로세스와 QEMU 사이에 채널을 만들어, 새롭게 번역된 블록을 translation cache에 저장해 나중에 다른 프로세스가 같은 블럭을 실행할 때 번역 시간을 단축시킨다.

 

 

afl-analyze tool

trimming 알고리즘을 응용해서 파일의 어느 부분을 변형하면 어떤 결과가 예측된다는 주석을 달아주는 도구이다.

 

AFL++

AFL++는 기존 AFL을 토대로 파생된 다른 알고리즘이나 퍼저를 합쳐 성능 향상과 편의성을 추가한 퍼저이다.

Scheduling

AFL은 튜플별로 점수를 매겨 favored 시드를 선정해 해당 시드에 대해 실행을 더 많이했다.

AFL++에서는 여기서 더 세분화된 AFLFast를 기반으로 다양한 스케줄링을 추가했다.

  • AFLFast
    • 새로운 경로를 찾거나 드물게 실행되는 희귀 경로(Rare paths)를 탐색하는데 우선순위를 두도록 적합도 기준과 선택 알고리즘을 수정함.
    • 선택된 구성을 몇 번이나 퍼징할지 결정하는 파워 스케줄 (power schedule) 개념을 도입했다.
      • 초기에는 실행 횟수를 적게해 탐색에 집중하고, 시간이 지날수록 유망한 구성을 지속적으로 퍼징하는 활용을 보장한다.
      • 동일한 경로를 실행하는 입력값이 많아질수록 해당 경로를 덜 실행하여, 자주 실행되지 않는 구성의 탐색을 촉진한다.
    • 이 과정에서 마르코프 체인 모델을 사용함.

스케줄링 종류

  • fast - 발견 빈도에 반비례해서 에너지 지수적 증가.
  • coe - 발견 빈도가 낮은 시도에 더 많은 에너지 할당.
  • explore - 모든 시드에 대해 일정하게 낮은 에너지를 할당. 초기 탐색에 유리.
  • quad - 시드 선택 횟수의 제곱에 비례하며 경로 발견 빈도에 반비례하게 에너지 할당.
  • lin - 시드 선택 횟수에 비례하며 경로 발견 빈도에 반비례하게 에너지 할당.
  • exploit - 모든 시드에 대해 일정하게 높은 에너지를 할당.

여기에 추가적으로 두 개의 스케줄링을 추가했다

  • mmopt - 새롭게 발견된 path를 더 깊게 탐색하기 위한 시드에 가중치 부여
  • rare - 시드의 실행 속도와 관계 없이 다른 시드에서 발견되지 않은 path에 가중치 부여

Mutator

AFL++는 커스텀 스케줄링, 뮤테이션, 최소화를 할 수 있도록 다양한 Custom Mutator API를 제공한다.

또한 REDQUEEN 연구를 기반으로 한 Input-To-State (I2S) mutator와, MOpt의 Pilot, Core 모드를 구현했다.

Instrumentation

기존 AFL에는 튜플의 hit count가 255에서 0으로 오버플로우되는 문제가 있었는데, AFL++에서 오버플로우시 최소 1의 값은 유지하도록 하는 NeverZero를 구현했다.

instrumentation을 위해 LLVM, QEMU, UNICORN 등 다양한 환경을 제공한다

 

AFL에서 더 발전하여 LLVM은 Ngram/Cix coverage를 통해 단순히 어떤 엣지를 지나왔는지 뿐만 아니라 함수가 어디서 호출됐는지 또는 현재 블록에서부터 N개의 블록 순서를 기록하여 경로를 기록하는 방법도 제공한다.

Multi-thread의 한계

현재 AFL++는 multi-thread를 완벽히 지원하지 않는다. 그 이유는 다음과 같다.

  • LLVM이 아닌 다른 백엔드 (QEMU, UNICORN 등)에서는 테스트 케이스를 전달할 때 파일시스템을 사용.
  • 특정 타겟의 경우 fork() system call에 의존함.

이렇기에 커널에서 낭비되는 시간이 많아 생각보다 효율이 나오지 않는다.

 

이에 대한 해결 방법으로 Snapshot LKM을 개발하여 fork()를 호출할 때 발생하는 커널 락의 영향을 최소화 시켰다.

 

이를 통해 현재 AFL++는 thread-safe하며, 앞으로는 병렬 퍼저 사이의 동기화 오버헤드를 최소화면서 multi-threading을 지원하는 것이 과제이다.

 

후기

Documentation까지 읽는건 처음인데 좀 어렵긴 하다.

근데 내가 원래 유전 알고리즘에 관심이 있고 그게 퍼징에 어떻게 적용되는지 알 수 있어서 재밌었다.

 

다음은 White fuzzer의 Symbolic execution에 대해서 공부해야한다. 어려울수록 재미를 느끼기에 굉장히 좋다  

'보안' 카테고리의 다른 글

[SE] Symbolic Execution & CDCL  (2) 2026.04.14

'보안'의 다른글

  • 현재글[Fuzzer] AFL/AFL++이란?

관련글

티스토리툴바