AFL++ 동작 원리 - 3

Dictionaries

AFL은 계측 피드백을 활용하여 입력 파일의 문법 토큰을 자동으로 선택하고, 이 토큰들이 유효한 구문을 이루는지 탐색하는 기능을 제공한다. 이는 AFL의 다양한 입력 파일 형식을 처리하는 데 중요한 역할을 하며, 특히 문법적으로 복잡한 언어와 같은 파일에서 큰 도움이 된다.

 

문법 토큰 자동 감지

AFL은 입력 파일에서 기본적인 구문 토큰을 무작위로 조합하면서, 계측 피드백을 통해 의미 없는 변형과 새로운 동작을 유발하는 변형을 구분할 수 있다. 이러한 방식으로 AFL은 점진적으로 복잡한 문법 구조를 발견하고, 이를 기반으로 퍼징을 진행한다.

 

사전의 활용

사전은 프리디파인(predefined)된 토큰이나 자동 감지(auto-detected)된 문법 요소를 이용해 퍼징 성능을 향상하는 도구이다. 이를 통해 AFL은 문법적으로 복잡한 언어의 구조를 빠르게 재구성할 수 있으며, 이는 특히 SQL이나 XML과 같은 언어에서 효과적이다.

 

자동 사전 생성

AFL은 입력 파일에서 이미 존재하는 구문 토큰을 자동으로 감지할 수 있다. 이는 특정 바이트 열을 변형했을 때 일관된 실행 경로 변경이 발생했는지 분석하여, 프로그램 코드에 내장된 사전 정의된 값과의 비교를 암시한다. 이를 통해 AFL은 자체적으로 자동 사전을 생성하여, 다른 퍼징 전략과 결합하여 퍼징 성능을 더욱 높인다.

---

De-duping crashes

크래시 중복 제거는 효과적인 퍼징 도구에서 매우 중요한 문제이다. AFL과 같은 퍼징 도구에서 이 작업이 중요한 이유는 크래시가 발생한 원인을 정확하게 분류하고, 실제 문제를 찾는 데 걸리는 시간을 줄이는 것이다. 단순한 접근 방식으로는 크래시를 잘못 분류하거나 과도한 크래시 수를 생성할 수 있다.

 

단순한 접근 방식의 문제점

• 단순히 오류 주소만을 확인하는 방식은 공통 라이브러리 함수에서 발생하는 오류(예: `strcmp`, `strcpy`)에 의해 관련 없는 이슈들이 같은 그룹으로 분류될 수 있다.
• 호출 스택(call stack) 백트레이스의 체크섬만을 계산하는 방식은 같은 문제가 여러 경로(재귀적 코드 경로 포함)를 통해 발생할 수 있는 경우 크래시 수를 과도하게 늘리게 된다.

 

afl-fuzz의 해결책

afl-fuzz는 다음 두 가지 조건 중 하나라도 충족할 경우 크래시를 고유하다고 간주한다.

1. 이전 크래시에서 보지 못한 튜플이 포함된 경우
   • 이전 크래시에서 확인되지 않은 새로운 경로가 실행되었을 때 크래시가 고유로 간주된다.
2. 이전 크래시에서 항상 존재하던 튜플이 없는 경우
   • 이전 크래시에서 항상 포함되었던 특정 경로가 생략된 크래시가 발생하면, 해당 크래시도 고유로 취급한다.

 

자기 제한 효과

이 접근 방식은 퍼징 초기에 경로 수 증가 문제가 발생할 수 있지만, 자기 제한(self-limiting) 효과를 통해 이러한 경향이 자연스럽게 조절된다. 이 방식은 AFL의 실행 경로 분석 논리와 유사하며, 초기 경로 증가 후에도 효과적으로 중복을 방지할 수 있다.

---

Investigation crashes

많은 유형의 크래시는 그 취약성이 모호할 수 있다. 이를 해결하기 위해 afl-fuzz는 크래시 탐색 모드(crash exploitation mode)를 제공하여, 이미 알려진 크래시가 발생한 테스트 케이스를 더 깊이 분석한다. 이 과정은 일반적인 퍼징 과정과 유사하지만, 크래시가 발생하지 않은 변이는 버려지도록 제한이 걸려 있다.

 

크래시 탐색 모드의 방법

• 크래시 탐색 모드는 계측 피드백을 사용하여, 크래시가 발생한 프로그램 상태를 조사하고, 애매한 크래시 조건을 넘어서 프로그램의 동작을 분석한다.
• 새로운 입력이 발견되면 해당 입력을 사람이 직접 검토할 수 있도록 격리한다.

 

크래시 입력의 다루는 방식

• 일반적인 큐 항목과는 달리, 크래시를 일으킨 입력은 트리밍되지 않는다. 이는 크래시가 발생하지 않은 부모 항목과의 비교를 쉽게 하기 위함이다. 
• 필요할 경우, afl-tmin 도구를 사용해 크래시 입력을 줄일 수 있다.

---

The fork server

퍼징 성능을 개선하기 위해 afl-fuzz는 포크 서버(fork server)를 사용한다. 이를 통해 퍼징된 프로세스는 한 번만 execve()를 호출하고, 링크 및 libc 초기화를 완료한 후 copy-on-write 기법을 활용해 정지된 프로세스 이미지에서 복제된다.

 

포크 서버는 계측 코드에 통합되어 있으며, 첫 번째 계측 함수에서 멈춰 afl-fuzz로부터의 명령을 대기한다.

 

성능 향상

• 빠른 타겟의 경우, 포크 서버는 1.5배에서 2배 정도의 성능 향상을 제공한다.

 

Manual 모드 및 Persistent 모드

• Manual ("deferred") 모드: 사용자 선택에 따라 더 큰 초기화 코드 블록을 건너뛸 수 있다. 이는 대상 프로그램에 아주 적은 코드 수정만 필요하며, 일부 타겟에서 10배 이상의 성능 향상을 가져올 수 있다.
• Persistent 모드:하나의 프로세스를 여러 입력을 시도하는 데 사용하여 반복적인 fork() 호출의 오버헤드를 크게 줄인다. 이 방식은 대상 프로그램에 약간의 코드 수정이 필요하지만, 빠른 타겟의 성능을 5배 이상 향상시킬 수 있으며, 프로세스 내부에서 퍼징 작업을 수행하는 것에 가까운 성능을 제공한다.

---

Parallelization

Parallelization은 afl-fuzz의 중요한 기능으로, 여러 CPU 코어 또는 원격 머신에서 독립적으로 실행되는 인스턴스가 생성한 큐를 주기적으로 검사하여, 로컬에서 시도했을 때 새로운 행동을 생성하는 테스트 케이스를 선택적으로 끌어오는 메커니즘이다. 이 접근 방식은 다음과 같은 장점을 제공한다.

 

특징 및 장점

• 유연한 퍼징 설정: 다양한 파서에 대해 동기화된 인스턴스를 실행할 수 있으며, 이는 공통 데이터 형식에 대해 서로 다른 접근 방식을 취하는 데 도움이 된다. 이렇게 함으로써 상호 시너지 효과를 창출할 수 있다.
• 새로운 행동 탐색: 독립적으로 실행되는 인스턴스가 생성한 테스트 케이스를 활용함으로써, 기존 퍼징 세션에서는 크게 발견되지 않은 새로운 입력 조합이나 변형을 탐색할 수 있다. 이는 퍼징의 효율성을 크게 향상할 수 있다.
• 성능 향상: 여러 인스턴스가 동시에 퍼징을 수행함으로써, 더 많은 코드 경로와 상태를 동시에 탐색할 수 있어 퍼징 속도와 커버리지를 향상시킬 수 있다.
• 상태 공유: 각 인스턴스가 서로의 큐를 주기적으로 검사하므로, 전체적인 퍼징 진행 상황을 공유할 수 있고, 효율적인 협업을 통해 더 효과적인 테스트가 가능하다.

---

Binary-only instrumentation

Binary-only instrumentation은 QEMU를 사용하여 블랙박스 및 바이너리 전용 대상을 계측하는 방법이다. 이 접근 방식은 사용자 에뮬레이션 모드에서 작동하며, 크로스 아키텍처 코드(예: ARM 바이너리를 x86에서 실행하는 것)를 실행할 수 있는 장점을 제공한다.

 

QEMU 기반 계측 과정

• 기본 블록 단위의 번역: QEMU는 기본 블록을 번역 단위로 사용하며, 이 위에 계측 기능이 구현된다. 이 계측은 컴파일 타임 후크와 유사한 모델을 따른다. 다음은 계측의 주요 코드 부분이다.

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;
}

• 이 코드에서는 블록 주소가 ELF 텍스트 세션 내에 있는지 확인한 후, 현재 위치를 계산하여 이전 위치와의 XOR 연산을 수행한다.
• 이 과정에서 명령어 정렬의 영향을 마스킹하기 위해 시프트 및 XOR 기반의 스크렘블링이 사용된다.

 

• 포크 서버 활용: QEMU의 시작 시간은 비교적 느리지만, AFL은 포크 서버를 활용하여 초기화된 프로세스를 일시 중지 상태로 복제함으로써 이 문제를 해결한다. 이를 통해 QEMU 모드는 이미 초기화된 프로세스의 복사본을 생성한다.
• 번역 캐시 관리: 새로운 기본 블록의 첫 번째 번역은 상당한 대기 시간을 수반한다. 이 문제를 해결하기 위해 AFL 포크 서버는 실행 중인 에뮬레이터와 부모 프로세스 간에 채널을 제공한다. 이 채널은 새로운 블록 주소를 부모에게 알리고, 이를 번역 캐시에 추가하여 향후 자식 프로세스에서 재사용할 수 있도록 한다.

 

성능 최적화

이 두 가지 최적화를 통해 QEMU 모드의 오버헤드는 약 2~5배 증가하는 반면, PIN과 같은 다른 바이너리 트랜스레이터의 경우는 100배 이상 증가하는 것으로 나타났다. 이러한 성능 개선 덕분에 AFL은 바이너리 전용 대상을 보다 효율적으로 계측하고 퍼징할 수 있다.

---

The afl-analyze tool

afl-analyze 도구는 파일 형식 분석기로, 이전에 논의된 최소화 알고리즘을 확장하여 구성된다. 이 도구는 no-op 블록을 제거하려는 대신 바이트 플립을 수행하고 입력 파일 내의 바이트 연속체를 주석 처리하는 기능을 갖추고 있다. 이를 통해 다양한 블록을 분류한다.

 

분류 체계

1. No-op blocks (무효 블록)
   
   • 정의: 비트 플립이 제어 흐름에 변화가 없는 구간
   • 예시: 주석 섹션, 비트맵 파일 내의 픽셀 데이터 등
2. Superficial content (표면적 콘텐츠)
   • 정의: 일부 비트 플립이 제어 흐름에 변화를 주지만, 모두가 그렇지는 않은 구간
   • 예시: 리치 문서의 문자열(예: XML, RTF) 등
3. Critical stream (중요 스트림)
   • 정의: 모든 비트 플립이 서로 다른 방식으로 제어 흐름을 변경하는 바이트 시퀀스
   • 예시: 압축 데이터,  비원자적으로 비교되는 키워드 또는 매직 값 등
4. Suspected length field (의심되는 길이 필드)
   • 정의: 작고 원자적인 정수로, 어떤 방식으로든 터치하면 프로그램 제어 흐름에 일관된 변화를 일으키는 구간
   • 예시: 실패한 길이 검사와 관련된 것으로 보임
5. Suspected checksummed block (의심되는 체크섬 블록)
   • 정의: 모든 변경이 항상 같은 새로운 실행 경로를 유발하는 긴 데이터 블록
   • 예시: 체크섬 또는 유사한 무결성 검사 실패로 인해 발생할 가능성이 높음
6. Magic value section (매직 값 섹션)
   • 정의: 변경이 앞서 설명한 바이너리 행동 유형을 유발하는 일반적인 토큰이지만, 다른 기준에 부합하지 않는 것
   • 예시: 원자적으로 비교되는 키워드 등이 포함될 수 있음