Park, Geon/trace_bits

Created Mon, 01 Jul 2024 12:00:00 +0900 Modified Tue, 07 Oct 2025 10:13:29 +0900
1575 Words

AFL의 눈, trace_bits는 어떻게 채워지는가?

AFL이 커버리지 기반 퍼징을 수행할 때, 프로그램의 어떤 경로가 실행되었는지의 정보를 담는 그릇이 바로 64KB 크기의 공유 메모리, 즉 trace_bits 비트맵입니다.

virgin_bits에 대한 글에서 우리는 virgin_bits를 통해 퍼저가 발견한 전체 커버리지를 누적 관리한다는 것을 배웠습니다. 반면 trace_bits는 매번의 단일 실행 (single run) 에서 어떤 엣지가 실행되었는지를 기록하는 ‘일회용 보고서’와 같습니다.

그렇다면 이 trace_bits는 언제, 어디서, 어떻게 설정되고 기록되는 것일까요?

1. Fuzzer와 Target의 공유 메모리 연결

afl-fuzz (퍼저)와 우리가 퍼징할 대상 프로그램 (Target), 이 둘은 운영체제의 공유 메모리(Shared Memory) 기능을 통해 같은 메모리 공간을 바라보게 됩니다.

  1. 퍼저의 준비 (afl-fuzz.c)

    퍼저는 먼저 공유 메모리 공간을 생성하고, 운영체제로부터 고유한 ID(shm_id)를 부여받습니다. 그 후, shmat 함수를 호출하여 자신의 프로세스에 해당 메모리를 연결하고, 이 공간을 가리키는 포인터가 바로 trace_bits가 됩니다.

    // afl-fuzz.c 에서...
shm_id = shmget(IPC_PRIVATE, MAP_SIZE, IPC_CREAT | IPC_EXCL | 0600);
...
trace_bits = shmat(shm_id, NULL, 0);

    그리고 가장 중요한 단계로, 퍼저는 이 shm_id를 **환경 변수(__AFL_SHM_ID)**에 저장한 채로 타겟 프로그램을 실행시킵니다.

  2. 타겟의 응답 (afl-llvm-rt.c)

    타겟 프로그램이 실행되는 순간, 내부에 삽입된 AFL의 런타임 코드(afl-llvm-rt.c)가 가장 먼저 깨어납니다. 이 코드는 퍼저가 남겨둔 환경 변수 __AFL_SHM_ID를 읽어 shm_id를 확인합니다.

    그리고 자신도 shmat 함수를 호출하여 퍼저와 동일한 공유 메모리 공간에 연결합니다. 이제 퍼저와 타겟은 trace_bits라는 이름의 동일한 64KB짜리 ‘공동 작업 캔버스’를 함께 보게 된 것입니다.

2. 실행과 기록

퍼저는 타겟을 실행시키고 타임아웃을 감시하며 결과를 기다립니다.

/* afl-fuzz.c 의 주석 */
/* Execute target application, monitoring for timeouts. Return status information. 
   The called program will update trace_bits[]. */

static u8 run_target(char** argv, u32 timeout) { ... }

주석이 말해주듯, trace_bits를 수정하는 주체는 퍼저가 아니라 타겟 프로그램 자신입니다. 컴파일 과정에서 AFL의 LLVM pass에 의해 타겟 코드 곳곳에는 계측 (instrumentation) 코드가 삽입되었습니다. 프로그램이 실행되다가 이 계측 코드를 만날 때마다 다음 작업이 일어납니다.

  1. 이전 기본 블록 (basic block)의 위치 (prev_loc)와 현재 위치 (cur_loc)를 가져옵니다.

  2. hash = (prev_loc >> 1) ^ cur_loc 공식을 통해 해시 값을 계산합니다.

  3. 이 해시 값을 인덱스로 사용하여 공유 메모리 trace_bits의 해당 바이트 값을 증가시킵니다.

즉, 퍼저는 캔버스를 펼쳐놓고 타겟을 실행시킨 뒤 잠시 기다릴 뿐이고, 타겟이 스스로 자신의 실행 경로를 캔버스에 그려나가는 구조입니다.

3. 예측의 한계: 실행 경로를 미리 알 수 있을까?

여기서 한 가지 흥미로운 질문이 생깁니다.

“프로그램을 실행하기 전에, trace_bits의 특정 위치(index)가 어떤 브랜치(edge)를 의미하는지 미리 알아낼 수 있을까?”

결론부터 말하면, 거의 불가능합니다.

그 이유는 해시 공식 (prev_loc >> 1) ^ cur_loc의 prev_loc 값이 실행 시점에 동적으로 결정되기 때문입니다. 예를 들어, 함수 C를 호출하는 코드가 프로그램의 여러 곳(함수 A, 함수 B)에 있다면, C의 시작 지점(cur_loc)은 같아도 C를 호출한 직전 위치(prev_loc)는 달라집니다.

  • A -> C 경로: hash_AC = (loc_A >> 1) ^ loc_C

  • B -> C 경로: hash_BC = (loc_B >> 1) ^ loc_C

따라서 hash_AC와 hash_BC는 다른 값이 되며, trace_bits의 서로 다른 위치에 기록됩니다.

이론적으로는 프로그램 코드 전체를 정적 분석하여 가능한 모든 prev_loc의 조합을 뽑아볼 수는 있겠지만, 이는 엄청나게 복잡하며 경로의 수가 기하급수적으로 늘어날수록 해시 충돌 또한 많아져 사실상 의미 있는 결과를 얻기 어렵습니다.

결국 trace_bits는 실행이 끝난 뒤에야 비로소 의미를 가지는, 철저히 동적인 실행의 산물인 셈입니다.