AFL++ 동작 원리 - 1

Design statement

American Fuzzy Lop(AFL)은 퍼저 도구로서, 특정한 이론이나 원칙에 얽매이지 않고 매우 실용적인 방법으로 설계되었다. 대부분의 퍼저 도구가 원리에 기반을 두거나, 개념 증명(proof-of-concept) 도구로 기능하는 반면, AFL은 그러한 틀에서 벗어나 다양한 해킹 기법들을 모은 하나의 컬렉션이라고 할 수 있다. 실제로 테스트를 통해 효과가 입증된 기법만을 사용하여 만들어졌다.

 

AFL의 여러 기능은 경량화된 계측(instrumentation) 덕분에 가능해졌다. 이 계측은 프로그램을 실행하는 동안 발생하는 동작을 모니터링하고 분석하는 중요한 역할을 한다. 그러나 AFL에서 이러한 계측 기술은 목표를 달성하기 위한 하나의 수단일 뿐이다. 다시 말해, AFL의 진정한 목표는 '계측 자체'가 아니라, 이를 통해 더 빠르고 신뢰할 수 있는 퍼징을 구현하는 데 있다.

---

Coverage measurements

AFL의 성능을 가능하게 하는 주요 요소 중 하나는 바로 코드 커버리지 측정이다. AFL은 프로그램에 삽입된 계측 코드를 통해 분기(edge) 커버리지와 대략적인 분기 횟수를 기록하는 방식으로 작동한다. 이 계측 코드는 각 분기 지점에 삽입되며, 다음과 같은 간단한 형태의 코드로 표현할 수 있다.

cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;

여기서 `cur_location`은 난수로 생성되며, 복잡한 프로젝트를 쉽게 연결하고 XOR 출력이 고르게 분포되도록 하는 데 기여한다.

 

Shared Memory: 분기 히트 수 기록

`shared_mem[]` 배열은 64 KB 크기의 공유 메모리(SHM) 영역으로, 계측된 바이너리에 의해 호출자에게 전달된다. 이 배열의 각 바이트는 특정한 `(branch_src, branch_dst)` 튜플의 히트 횟수를 기록하는 용도로 사용된다. AFL은 이 크기의 맵을 사용 하여 분기 포인트 간 충돌이 드물게 발생하도록 설계했으며, 이는 대부분의 타겟에서 2,000개에서 10,000개의 분기 지점을 발견할 수 있음을 의미한다.

분기 간 충돌이란 서로 다른 분기 쌍 `(branch_src, branch_dst)`이 동일한 메모리 위치에 기록되는 상황을 의미한다.

 

분기 포인트 개수에 따른 충돌률

아래는 분기 포인트 개수에 따른 충돌 확률과 일부 예시 타겟이다.

Branch cnt	Colliding tuples	Example targets
1,000	0.75%	giflib, lzo
2,000	1.5%	zlib, tar, xz
5,000	3.5%	libpng, libwebp
10,000	7%	libxml
20,000	14%	sqlite
50,000	30%

 

이 맵의 크기는 L2 캐시에 손쉽게 저장될 수 있도록 설계되어, 결과 분석이 마이크로초 단위로 이루어진다. 또한, 간단한 블록 커버리지보다 훨씬 더 많은 실행 경로에 대한 정보를 제공한다.

 

커버리지를 통한 실행 경로 분석

AFL의 커버리지 측정 방식은 단순히 블록을 실행했는지 여부를 넘어서, 프로그램의 실행 경로에 대한 더 깊은 통찰을 제공한다. 예를 들어, 다음 두 가지 실행 경로를 쉽게 구분할 수 있다.

• A → B → C → D → E (생성된 튜플: AB, BC, CD, DE)
• A → B → D → C → E (생성된 튜플: AB, BD, DC, CE)

이처럼 AFL은 코드의 미묘한 상태 전환에서 발생할 수 있는 보안 취약점을 발견하는 데 큰 도움을 준다. 보안 취약점은 종종 새로운 블록에 도달하는 것보다 예상치 못한 상태 전환과 관련이 있기 때문에, 이 접근 방식은 매우 효과적이다.

 

XOR  및 Shift 연산의 이유

앞서 언급한 가상의 코드에서 마지막 줄에 사용된 시프트 연산의 이유는 튜플의 방향성을 유지하기 위함이다. 만약 이 연산이 없다면, `A ^ B`와 `B ^ A`가 동일하게 처리되어, 분기 경로의 방향을 구분할 수 없게 된다. 또한, 타이트한 루프에서 `A ^ A`가 `B ^ B`와 동일하게 처리되는 것도 방지할 수 있다.

 

히트 카운터의 제한 사항

Intel CPU에서 단순히 포화 산술(saturating arithmetic) 연산을 지원하지 않기 때문에, 히트 카운터는 간혹 0으로 돌아갈 수 있다. 하지만, 이는 매우 드물게 발생하는 문제로, 성능과의 균형을 고려할 때 수용 가능한 trade-off로 간주된다.

---

Detecting new behaviors

AFL의 핵심 기능 중 하나는 새로운 실행 경로를 탐지하는 능력이다. 퍼저는 이전 실행에서 관찰한 튜플의 전역 맵을 유지하고, 이를 개별 실행 경로와 빠르게 비교한다. 이러한 비교는 몇 개의 dword 또는 qword 명령어와 간단한 반복문을 통해 효율적으로 이루어진다.

 

새로운 튜플이 포함된 실행 경로가 발견되면, 해당 입력 파일은 보존되어 추가 처리로 이어진다. 반대로, 새로운 지역 상태 전환을 유발하지 않는 입력은, 즉 새로운 튜플이 생성되지 않는 입력은 버려진다. 이는 입력의 전체 제어 흐름이 독특하더라도 새로운 튜플이 없으면 탐지되지 않음을 의미한다. 

 

이 접근 방식은 프로그램 상태를 매우 세밀하고 장기적으로 탐색하면서도, 경로 폭발(path explosion) 문제를 피하면서 복잡한 실행 경로의 글로벌 비교를 피할 수 있다. 이는 프로그램의 상태 전이를 효과적으로 탐지하고 처리 시간을 절약하는 방법이다.

경로 폭발이란 프로그램의 실행 수가 기하급수적으로 증가하는 현상을 의미한다.

 

새로운 튜플 예시

다음 예시를 통해 AFL의 새로운 튜플 탐지 메커니즘을 이해할 수 있다.

• #1: A → B → C → D → E
• #2: A → B → C → A → E

위의 두 번째 경로는 새로운 튜플 (CA, AE)이 포함되어 있으므로, AFL은 이를 새로운 실행 경로로 간주하고 추가로 처리하게 된다.

 

반면, 다음과 같은 경로는 실행 경로가 다르더라도, 새로운 튜플이 없기 때문에 독특하지 않다고 간주된다.

• #3: A → B  → C → A → B → C → A → B → C → D → E

 

히트 카운트 및 버킷 시스템

AFL은 새로운 튜플을 탐지하는 것 외에도 히트 카운트(hit count)를 추적한다. 이 카운트는 여러 버킷으로 나누어진다.

• 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+

이 버킷 시스템은 계측 도구에서 생성된 8비트 카운터를 기반으로 퍼저가 각 튜플에 대해 이미 실행된 횟수를 추적하는 데 사용된다. 한 버킷 내의 변동은 무시되지만, 다른 버킷으로 넘어가는 행동은 흥미로운 제어 흐름 변화로 간주되며, 추가 처리로 연결된다.

 

예를 들어, 특정 코드 블록이 한 번 실행되던 것이 두 번 실행되는 것과 같은 변화는 중요한 상태 변화로 취급된다. 반면, 반복문의 실행 횟수가 47회에서 48회로 증가하는 것처럼 상대적으로 중요하지 않은 변화는 무시된다. 이 방식은 히트 카운트의 충돌 가능성을 줄여주며, 매우 높은 밀도의 추적 맵에서도 우발적인 충돌에 대한 어느 정도의 내성을 제공한다.

 

실행 시간제한

AFL은 실행 시간이 지나치게 길어지지 않도록 엄격한 메모리 및 실행 시간제한을 적용한다. 기본적으로 타임아웃은 initially-calibrated 실행 속도의 5배로 설정되며, 최소한 20ms로 반올림된다. 이러한 공격적인 타임아웃 설정은 퍼저가 극도로 느린 경로에 빠져 성능이 저하되는 것을 방지하기 위한 것이다.

 

예를 들어, 코드 커버리지를 1% 개선하지만, 100배 더 느리게 작동하는 입력이 있다면 이를 거절하고, 퍼저가 더 저렴한 경로를 찾도록 유도한다. 실험 결과, 더 관대한 시간제한을 적용하는 것은 성능 저하를 초래하기 때문에 비용 대비 효과가 없다는 것이 입증되었다.