virgin_bits: 새로운 엣지 커버리지를 추적하는 AFL의 메모리

AFL은 퍼징을 통해 프로그램의 새로운 경로를 효율적으로 탐색합니다. 이때 virgin_bits라는 전역 비트맵(bitmap)을 사용하여 아직 발견되지 않은 새로운 엣지 (edge) 커버리지를 기록하고 관리합니다.

• AFL 공식 문서에서는 branch coverage라고 부릅니다.

AFL에서 virgin_bits의 크기는 64kB

config.h:#define MAP_SIZE_POW2       16
config.h:#define MAP_SIZE            (1 << MAP_SIZE_POW2)
afl-fuzz.c:EXP_ST u8  virgin_bits[MAP_SIZE]
	/* Regions yet untouched by fuzzing */

• u8 = 1B
• 1«16B = 64kB

엣지(Edge)와 비트맵의 1바이트 매핑

virgin_bits 배열의 각 바이트 (Byte)는 프로그램 제어 흐름 그래프 (CFG)의 특정 엣지 (한 기본 블록에서 다른 기본 블록으로의 전환) 를 나타냅니다. AFL의 계측 (instrumentation) 코드는 각 엣지를 다음과 같은 방식으로 virgin_bits의 특정 위치 (인덱스)에 매핑합니다.

1. 컴파일 시점에 CFG의 각 기본 블록 (노드)에 랜덤한 숫자를 부여합니다.
2. 프로그램이 실행될 때, 이전 블록의 위치 값과 현재 블록의 위치 값을 조합하여 해시 (hash)를 계산합니다. (hash = (prev_loc >> 1) ^ cur_loc)
3. 이 해시 값을 virgin_bits 배열의 인덱스로 사용하여 해당 엣지의 방문 여부를 기록합니다.

AFL이 사용하는 afl-llvm-pass.so.cc의 경우, edge간 해시 충돌이 날 수 있습니다. 이를 감안해 1 « 16이라는 크기가 정해졌습니다.

방문 횟수(Hit Count) 기록: 단순한 0/1이 아닌 버킷(Bucket) 시스템

virgin_bits는 퍼저가 시작될 때 모든 비트가 1로 설정된 상태(0xFF)로 초기화됩니다. 이는 ‘아직 아무 엣지도 방문하지 않았다’는 의미입니다.

• 설정 위치: 함수 setup_shm 중, if (!in_bitmap) memset(virgin_bits, 255, MAP_SIZE);

AFL은 단순히 엣지를 방문했는지 (0/1)만 기록하는 것이 아니라, 몇 번 방문했는지도 대략적으로 추적합니다.

• 1회 방문: …1111 1111 -> …1111 1110
• 2회 방문: …1111 1110 -> …1111 1100
• 3회 방문: …1111 1100 -> …1111 1000
• 4-7회 방문: …1111 1000 -> …1111 0000

이처럼 방문 횟수가 특정 구간 (bucket)에 도달할 때마다 비트가 0으로 채워집니다. 이를 통해 AFL은 루프를 더 많이 실행시키는 등 흥미로운 동작을 유발하는 입력을 구별해낼 수 있습니다.

새로운 커버리지 발견 검사

AFL은 has_new_bits() 함수를 통해 새로운 엣지를 발견했는지 검사합니다. 이 과정에서 두 개의 비트맵이 사용됩니다.

• virgin_bits (vir): 전체 퍼징 과정 동안의 모든 커버리지를 누적 기록합니다. 0xFF는 ‘아직 발견된 적 없음’ 을 의미합니다.
• trace_bits (cur): 단일 실행에서 기록된 커버리지 정보입니다. 대상 프로그램의 매 실행 전 0으로 초기화되며, 엣지를 방문하면 해당 위치의 값이 변경됩니다. (참고: trace_bits)
• 즉, virgin_bits는 평생에 한 번이라도 만족한 커버리지에 해당하는 비트를 0으로 두고, 반대로 trace_bits는 이번 실행에 만족한 커버리지에 해당하는 비트를 1로 둡니다.

아래 코드는 trace_bits와 virgin_bits를 비교하여 새로운 커버리지를 찾는 로직의 일부입니다. 짧게 하기 위해 vir, cur 등을 쓰지 않았습니다.

// has_new_bits() 함수의 핵심 로직 (단순화)
u8 ret = 0;
for (i = 0; i < MAP_SIZE; i++) {
  if (trace_bits[i] & virgin_bits[i]) { // (1)
    // 새로운 커버리지 발견!
    ret = 1;
    virgin_bits[i] &= ~(trace_bits[i]); // (2)
  }
}
return ret;

• (1)은 “평생에 한 번도 만족되지 않은 커버리지 중, 이번 실행에서 만족한 커버리지가 있는가"를 검사합니다. (1)은 한 바이트에 있는 8개의 비트를 한 번에 검사합니다.
• (2)는 virgin_bits에서 해당 커버리지에 해당하는 비트를 0으로 만들어 주어, 방문을 표시합니다.

커버리지 해시 충돌(Hash Collision)과 그 의미

AFL은 빠른 속도를 위해 모든 엣지에 고유한 ID를 부여하는 대신, 해시(hash)를 통해 64KB 크기의 비트맵에 엣지 정보를 압축하여 기록합니다. 이 과정에서 서로 다른 엣지가 동일한 해시 값을 갖게 되는 해시 충돌 (Hash Collision) 이 발생할 수 있습니다.

AFL 공식 문서에 따르면, 10,000개의 브랜치(엣지)를 가진 프로그램에서 약 7%의 ‘충돌 튜플 (Collision Tuples)’ 이 발생한다고 합니다.

![[AFL에서 hash collision의 비율.png|AFL에서 hash collision의 비율.png]]

[!QUESTION] ‘충돌 튜플 7%‘의 정확한 의미는 무엇일까요?

이는 **“전체 10,000개의 엣지 중 약 7%에 해당하는 700여 개의 엣지가, 비트맵의 동일한 공간을 공유하게 된다”**는 의미입니다.

다시 말해, 비트맵의 특정 인덱스 하나가 두 개 이상의 다른 엣지를 동시에 대표하게 되는 것입니다. 이는 마치 ‘생일 문제 (Birthday Problem)‘처럼, 제한된 공간 (65,536개 인덱스)에 여러 데이터 (10,000개 엣지)를 무작위로 할당할 때 일부가 겹치게 되는 것과 유사합니다.

이로 인한 영향:

해시 충돌이 발생하면 퍼저는 충돌한 엣지들을 서로 구분하지 못합니다. 예를 들어 A->B 엣지와 X->Y 엣지가 같은 인덱스에 매핑되었다면, 퍼저는 둘 중 어느 엣지를 방문했는지 알 수 없습니다. 이는 커버리지 측정의 정밀도를 약간 떨어뜨리지만, AFL은 전반적인 퍼징 속도와 효율을 위해 이 정도의 손실은 감수하는 전략을 취하고 있습니다.

해시 충돌률 계산 공식은 아래를 참고해 주세요.

해시 충돌률 계산 공식

기본 아이디어는 “전체 엣지 수에서, 충돌 없이 고유한 공간을 차지할 것으로 기대되는 엣지의 수를 뺀 값” 을 구하는 것입니다.

충돌에 연루되는 엣지의 수를 구하는 공식은 다음과 같습니다. $$ \text{예상 출동 엣지 수} \approx k - n \times (1 - e^{-k/n})$$

• \(k\) : 해싱할 아이템(엣지)의 수 (10,000개)
• \(n\) : 해시 테이블의 전체 공간(슬롯)의 수 (65,536개)

1. \(k/n\) (Load Factor)
   • 10000 / 65536 ≈ 0.1526
   • 해시 테이블의 각 공간(슬롯)에 평균적으로 몇 개의 엣지가 들어가는지를 나타내는 ‘밀도’입니다.
2. \(e^{-k/n}\) (특정 공간이 비어 있을 확률)
   • e^(-0.1526) ≈ 0.8585
   • 푸아송 분포 근사를 통해, 10,000개의 엣지를 무작위로 던졌을 때 특정 한 공간이 텅 비어 있을 확률을 계산한 것입니다. 즉, 약 85.85%의 확률로 특정 공간은 아무에게도 선택받지 못합니다.
3. \(1 - e^{-k/n}\) (특정 공간이 채워져 있을 확률)
   • 1 - 0.8585 = 0.1415
   • 반대로, 특정 공간에 적어도 하나 이상의 엣지가 들어와 채워져 있을 확률입니다.
4. \(n \times (1 - e^{-k/n})\) (채워진 공간의 총 개수)
   • 65536 * 0.1415 ≈ 9274
   • 전체 공간의 수 (\(n\))에 공간이 채워져 있을 확률을 곱하면, 10,000개의 엣지가 모두 들어왔을 때 사용될 것으로 예상되는 총 공간의 수가 나옵니다. 즉, 10,000개의 엣지는 약 9,274개의 고유한 공간에 나뉘어 들어갑니다.
5. \(k - n \times (1 - e^{-k/n})\) (최종 충돌 엣지 수)
   • 10000 - 9274 = 726
   • 총 10,000개의 엣지를 넣었는데, 실제 사용된 공간은 9,274개뿐입니다. 이 차이 (726개)가 바로 자신만의 고유한 공간을 찾지 못하고 이미 다른 엣지가 차지한 공간에 들어간, 즉 ‘충돌한’ 엣지의 수입니다.

따라서 약 7% 의 충돌률을 도출할 수 있습니다.