퍼징 도구 AFL의 이해와 코드 분석
1. AFL 개요
AFL은 American Fuzzy Lop의 약자로, 프로그램에 다양한 입력값을
자동으로 넣어보면서 취약점이나 비정상 동작을 찾는 퍼징 도구이다.
AFL의 가장 큰 특징은 단순히 무작위 데이터를 넣는 것이 아니라,
프로그램이 어떤 코드 경로를 실행했는지 확인하면서 입력값을 발전시킨다는 점이다.
일반적인 랜덤 퍼징은 다음과 같이 동작한다.
1
2
3
랜덤 입력 생성
→ 프로그램 실행
→ 크래시 발생 여부 확인
하지만 AFL은 다음과 같이 동작한다.
1
2
3
4
5
6
초기 입력값 준비
→ 입력값 변형
→ 프로그램 실행
→ coverage 확인
→ 새로운 실행 경로 발견 시 저장
→ 저장된 입력을 다시 변형
즉 AFL은 단순히 크래시만 찾는 도구가 아니라, 프로그램 내부의 새로운 실행 경로를 계속 탐색하는 도구이다.
AFL의 핵심 목표는 다음과 같다.
1
2
3
4
더 많은 코드 경로 실행
더 깊은 분기 조건 통과
비정상 종료 유발
숨겨진 취약점 발견
2. AFL의 핵심 구성 요소
AFL은 크게 네 가지 핵심 요소로 구성된다.
1
2
3
4
1. Instrumentation
2. Coverage
3. Fork Server
4. Mutation
각각의 역할은 다음과 같다.
2-1. Instrumentation
Instrumentation은 프로그램 안에 실행 추적 코드를 삽입하는 과정이다.
AFL은 컴파일 과정에서 프로그램의 각 basic block 근처에 coverage 기록 코드를 삽입한다.
이 코드를 통해 AFL은 프로그램이 어떤 경로를 실행했는지 알 수 있다.
2-2. Coverage
Coverage는 프로그램의 어느 부분이 실행되었는지를 의미한다.
AFL은 단순히 함수가 실행되었는지만 보는 것이 아니라, 이전 위치에서 현재 위치로 이동한 흐름을 추적한다.
이것을 edge coverage라고 한다.
2-3. Fork Server
Fork Server는 타깃 프로그램을 빠르게 반복 실행하기 위한 구조이다.
퍼징에서는 프로그램을 수천 번, 수만 번, 수백만 번 실행해야 한다.
매번 프로그램을 처음부터 실행하면 너무 느리기 때문에 AFL은 fork server를 사용한다.
2-4. Mutation
Mutation은 기존 입력값을 변형하는 과정이다.
AFL은 완전히 랜덤한 데이터를 만드는 것이 아니라, 기존 seed input을 기반으로 조금씩 변형한다.
그리고 새로운 coverage를 만든 입력값을 다시 queue에 저장한다.
3. AFL 주요 파일 구조
AFL 원본 저장소에서 중요한 파일은 다음과 같다.
1
2
3
4
5
6
7
8
afl-fuzz.c
afl-as.c
afl-gcc.c
afl-clang.c
afl-showmap.c
config.h
types.h
debug.h
3-1. afl-fuzz.c
afl-fuzz.c는 AFL의 메인 퍼징 엔진이다.
가장 중요한 파일이며 이 파일에는 다음 기능이 들어 있다.
1
2
3
4
5
6
7
8
입력 큐 관리
mutation 수행
타깃 프로그램 실행
fork server 통신
coverage bitmap 분석
crash 저장
hang 저장
퍼징 상태 출력
즉 AFL의 실제 동작 대부분은 afl-fuzz.c에서 처리된다.
3-2. afl-as.c
afl-as.c는 instrumentation 삽입을 담당한다.
AFL은 컴파일 중 생성되는 assembly 코드에 coverage 기록 코드를 삽입한다.
즉 소스코드를 직접 수정하는 것이 아니라, assembly 단계에서 코드를 추가한다.
3-3. afl-gcc.c
afl-gcc.c는 gcc wrapper이다.
사용자가 다음과 같이 컴파일하면,
1
afl-gcc -o target target.c
실제로는 일반 gcc가 바로 실행되는 것이 아니라, AFL wrapper가 중간에서 컴파일 과정을 제어한다.
그 결과 컴파일 중에 afl-as가 사용되고, instrumentation이 삽입된 바이너리가 만들어진다.
3-4. config.h
config.h에는 AFL의 주요 설정값이 들어 있다.
예를 들어 coverage bitmap 크기, timeout 관련 설정, fork server 관련 설정 등이 정의되어 있다.
대표적으로 중요한 값은 다음과 같다.
1
#define MAP_SIZE_POW2 16
이 값은 coverage bitmap 크기와 관련 있다.
2^16 = 65536이므로 AFL의 기본 bitmap 크기는 64KB이다.
4. AFL 전체 동작 흐름
AFL의 전체 흐름은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1. 사용자가 afl-gcc로 타깃 프로그램을 컴파일한다.
2. 컴파일 과정에서 instrumentation 코드가 삽입된다.
3. 사용자가 afl-fuzz를 실행한다.
4. afl-fuzz가 seed input을 읽는다.
5. seed input을 queue에 등록한다.
6. dry run으로 초기 입력이 정상 실행되는지 확인한다.
7. fork server를 초기화한다.
8. queue에서 입력값을 하나 선택한다.
9. mutation을 수행한다.
10. 변형된 입력값으로 타깃 프로그램을 실행한다.
11. coverage bitmap을 확인한다.
12. 새로운 coverage가 있으면 queue에 저장한다.
13. crash가 발생하면 crashes 디렉터리에 저장한다.
14. hang이 발생하면 hangs 디렉터리에 저장한다.
15. 이 과정을 계속 반복한다.
그림으로 표현하면 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[Seed Input]
↓
[Queue 등록]
↓
[Mutation]
↓
[Target 실행]
↓
[Coverage 확인]
↓
┌──────────────────┐
│ 새로운 경로인가? │
└──────────────────┘
↓ Yes
[Queue에 추가]
↓
[다시 Mutation 대상]
5. Instrumentation 상세 분석
5-1. Instrumentation이 필요한 이유
퍼징을 할 때 단순히 프로그램이 죽었는지만 확인하면 효율이 낮다.
예를 들어 다음 코드가 있다고 하자.
1
2
3
4
5
6
7
if (buf[0] == 'A') {
if (buf[1] == 'F') {
if (buf[2] == 'L') {
crash();
}
}
}
입력값이 다음과 같다면,
1
XXXX
아무 분기도 통과하지 못한다.
입력값이 다음과 같다면,
1
AXXX
첫 번째 분기는 통과한다.
입력값이 다음과 같다면,
1
AFXX
두 번째 분기까지 통과한다.
입력값이 다음과 같다면,
1
AFLX
세 번째 분기까지 통과하고 crash가 발생할 수 있다.
AFL은 “AXXX”나 “AFXX” 같은 입력도 중요하게 본다.
왜냐하면 이 입력들은 crash를 발생시키지는 않았지만, 더 깊은 코드 경로에 도달했기 때문이다.
이런 입력을 저장하고 다시 변형하면 eventually “AFLX” 같은 입력을 만들 가능성이 높아진다.
따라서 AFL은 프로그램이 어떤 경로를 실행했는지 알아야 한다.
이를 위해 instrumentation을 삽입한다.
5-2. AFL의 instrumentation 방식
AFL 원본은 기본적으로 compile-time instrumentation 방식을 사용한다.
즉 실행 중에 바이너리를 분석하는 것이 아니라, 컴파일할 때 추적 코드를 삽입한다.
흐름은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
source.c
↓
afl-gcc
↓
gcc가 assembly 생성
↓
afl-as가 assembly 수정
↓
coverage 기록 코드 삽입
↓
최종 바이너리 생성
AFL은 LLVM pass 방식이 아니라 assembly level에서 instrumentation을 삽입한다.
이 점이 AFL++나 최신 LLVM 기반 퍼저들과 구분되는 부분이다.
5-3. Basic Block과 Edge
AFL이 추적하는 대상은 단순한 line coverage가 아니다.
AFL은 basic block 간의 이동을 추적한다.
Basic block은 중간에 분기 없이 순차적으로 실행되는 코드 묶음이다.
예를 들어 다음 코드가 있다고 하자.
1
2
3
4
5
6
if (x > 10) {
foo();
} else {
bar();
}
baz();
이 코드는 대략 다음 basic block으로 나눌 수 있다.
1
2
3
4
Block A: x > 10 비교
Block B: foo()
Block C: bar()
Block D: baz()
실행 흐름은 두 가지가 가능하다.
1
2
A → B → D
A → C → D
단순 block coverage만 보면 B 또는 C가 실행되었는지 정도는 알 수 있다.
하지만 AFL은 더 정확한 흐름을 보기 위해 edge coverage를 사용한다.
Edge coverage는 다음과 같은 이동 관계를 추적한다.
1
2
3
4
A → B
B → D
A → C
C → D
이렇게 하면 같은 block이 실행되어도 어떤 경로로 도달했는지를 더 잘 구분할 수 있다.
6. Coverage Bitmap 분석
6-1. Coverage Bitmap이란?
AFL은 coverage 정보를 bitmap에 저장한다.
기본 크기는 64KB이다.
개념적으로는 다음과 같다.
1
unsigned char trace_bits[65536];
프로그램이 특정 edge를 실행하면 bitmap의 특정 위치 값을 증가시킨다.
1
trace_bits[index]++;
여기서 index는 현재 위치와 이전 위치를 조합하여 만든 값이다.
6-2. Shared Memory 사용 이유
afl-fuzz와 타깃 프로그램은 서로 다른 프로세스이다.
그러므로 일반 변수로 coverage 정보를 공유할 수 없다.
그래서 AFL은 shared memory를 사용한다.
흐름은 다음과 같다.
1
2
3
4
5
afl-fuzz가 shared memory 생성
→ shared memory ID를 환경변수로 타깃에 전달
→ 타깃 프로그램이 shared memory에 attach
→ instrumentation 코드가 trace_bits에 coverage 기록
→ afl-fuzz가 실행 후 trace_bits 분석
AFL에서 중요한 환경변수는 다음과 같다.
1
__AFL_SHM_ID
이 값은 타깃 프로그램이 어떤 shared memory를 사용해야 하는지 알려준다.
6-3. Coverage 기록 방식
AFL의 coverage 기록 방식은 개념적으로 다음과 같다.
1
2
3
4
cur_location = RANDOM_ID;
index = cur_location ^ prev_location;
trace_bits[index]++;
prev_location = cur_location >> 1;
여기서 중요한 변수는 두 개이다.
1
2
cur_location
prev_location
cur_location은 현재 basic block에 부여된 랜덤 ID이다.
prev_location은 직전에 실행된 위치이다.
AFL은 이 둘을 XOR해서 bitmap index를 만든다.
1
index = cur_location ^ prev_location;
이 방식으로 현재 위치 자체가 아니라 이전 위치에서 현재 위치로 넘어온 edge를 기록한다.
6-4. 왜 XOR을 사용하는가
AFL은 빠른 속도가 중요하다.
퍼징은 매우 많은 실행을 반복해야 하기 때문에 coverage 계산이 복잡하면 전체 속도가 느려진다.
XOR은 매우 빠른 연산이다.
또한 이전 위치와 현재 위치를 조합하여 edge 정보를 간단히 표현할 수 있다.
예를 들어 다음 흐름이 있다고 하자.
1
2
A → B
A → C
각 block에 ID가 있다고 하면,
1
2
3
A = 100
B = 200
C = 300
AFL은 다음과 같이 index를 만든다.
1
2
A → B: A ^ B
A → C: A ^ C
서로 다른 값이 나오므로 다른 edge로 기록된다.
6-5. prev_location을 shift하는 이유
AFL은 다음과 같이 prev_location을 저장한다.
1
prev_location = cur_location >> 1;
그냥 prev_location = cur_location으로 저장하지 않는다.
그 이유는 XOR의 대칭성 때문이다.
XOR은 다음 성질을 가진다.
1
A ^ B == B ^ A
만약 shift를 하지 않으면 다음 두 경로가 같은 값으로 기록될 수 있다.
1
2
A → B
B → A
둘 다 A ^ B가 되기 때문이다.
이를 완화하기 위해 AFL은 현재 위치를 오른쪽으로 1비트 shift한 값을 prev_location에 저장한다.
이렇게 하면 방향성이 어느 정도 반영된다.
7. afl-fuzz.c 상세 흐름
afl-fuzz.c는 AFL의 핵심 엔진이다.
전체 코드를 처음부터 끝까지 읽기에는 크기가 크기 때문에 큰 흐름 중심으로 봐야 한다.
중요한 흐름은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
main()
→ setup_shm()
→ setup_dirs_fds()
→ read_testcases()
→ perform_dry_run()
→ init_forkserver()
→ fuzz_one()
→ run_target()
→ has_new_bits()
→ save_if_interesting()
7-1. main()
main()은 AFL 실행의 시작점이다.
여기서 명령행 옵션을 파싱하고, 퍼징 환경을 초기화한다.
사용자가 다음과 같이 실행한다고 하자.
1
afl-fuzz -i in -o out ./target @@
main()에서는 다음 정보를 처리한다.
1
2
3
4
5
6
7
입력 디렉터리: in
출력 디렉터리: out
타깃 프로그램 경로: ./target
@@ 위치
timeout 설정
memory limit 설정
dictionary 사용 여부
@@는 AFL에서 특별한 의미를 가진다.
타깃 프로그램이 파일 입력을 받는 경우, AFL이 생성한 테스트케이스 파일 경로가 @@ 위치에 들어간다.
예를 들어 명령이 다음과 같으면,
1
afl-fuzz -i in -o out ./parser @@
실제 실행은 다음과 비슷하게 된다.
1
./parser out/.cur_input
7-2. setup_shm()
setup_shm()은 coverage bitmap을 위한 shared memory를 준비한다.
흐름은 다음과 같다.
1
2
3
shared memory 생성
trace_bits 포인터 연결
환경변수 __AFL_SHM_ID 설정
이후 타깃 프로그램은 이 shared memory에 coverage 정보를 기록한다.
7-3. setup_dirs_fds()
setup_dirs_fds()는 출력 디렉터리 구조를 준비한다.
AFL 실행 후 output 디렉터리를 보면 다음과 같은 구조가 생긴다.
1
2
3
4
5
6
out/
├── queue/
├── crashes/
├── hangs/
├── fuzzer_stats
└── plot_data
각 디렉터리의 의미는 다음과 같다.
1
2
3
4
5
queue : 새로운 coverage를 만든 입력값 저장
crashes : crash를 유발한 입력값 저장
hangs : timeout을 유발한 입력값 저장
fuzzer_stats: 퍼징 통계 정보
plot_data : 시각화용 데이터
7-4. read_testcases()
read_testcases()는 입력 디렉터리에 있는 seed 파일을 읽는다.
예를 들어 입력 디렉터리가 다음과 같다고 하자.
1
2
3
in/
├── seed1
└── seed2
AFL은 이 파일들을 queue에 등록한다.
AFL의 queue는 단순 파일 목록이 아니다.
각 입력값은 queue_entry 구조체로 관리된다.
개념적으로 다음 정보를 가진다.
1
2
3
4
5
6
7
8
파일 경로
입력 크기
실행 시간
coverage 크기
depth
favored 여부
checksum
deterministic stage 완료 여부
즉 AFL은 각 입력값에 대해 다양한 메타데이터를 관리한다.
7-5. perform_dry_run()
perform_dry_run()은 초기 seed input을 대상으로 테스트 실행을 수행한다.
목적은 다음과 같다.
1
2
3
4
5
타깃 프로그램이 정상 실행되는지 확인
seed input이 crash를 내는지 확인
timeout 여부 확인
instrumentation이 정상 동작하는지 확인
coverage가 수집되는지 확인
만약 dry run 단계에서 모든 입력이 timeout되거나 coverage가 전혀 수집되지 않으면 퍼징을 제대로 진행할 수 없다.
따라서 dry run은 AFL이 본격적인 퍼징을 시작하기 전의 검증 단계라고 볼 수 있다.
8. Fork Server 상세 분석
8-1. 왜 Fork Server가 필요한가
퍼징에서는 타깃 프로그램을 매우 많이 실행한다.
일반적인 실행 방식은 다음과 같다.
1
2
3
4
5
afl-fuzz
→ fork
→ execve
→ target 실행
→ 종료
하지만 매번 execve()를 호출하면 비용이 크다.
프로그램 실행에는 다음 비용이 포함된다.
1
2
3
4
5
바이너리 로딩
동적 라이브러리 로딩
초기화 루틴 실행
메모리 매핑
런타임 초기화
이 작업을 수십만 번 반복하면 매우 느려진다.
AFL은 이를 줄이기 위해 fork server를 사용한다.
8-2. Fork Server 동작 방식
Fork server는 타깃 프로그램을 한 번 실행한 후, 그 상태에서 계속 fork를 수행하는 구조이다.
흐름은 다음과 같다.
1
2
3
4
5
6
7
8
1. afl-fuzz가 타깃 프로그램을 실행한다.
2. 타깃 내부의 instrumentation 코드가 fork server를 시작한다.
3. afl-fuzz가 fork server에게 실행 요청을 보낸다.
4. fork server가 child process를 생성한다.
5. child process가 실제 입력값을 처리한다.
6. child process가 종료된다.
7. fork server가 종료 상태를 afl-fuzz에게 전달한다.
8. afl-fuzz는 다음 입력값을 보낸다.
이 방식의 장점은 다음과 같다.
1
2
3
4
execve 호출 감소
초기화 비용 절감
초당 실행 횟수 증가
퍼징 효율 향상
8-3. Fork Server 통신
AFL의 fork server는 pipe를 통해 afl-fuzz와 통신한다.
개념적으로는 다음과 같다.
1
afl-fuzz ←→ fork server
afl-fuzz가 실행 명령을 보내면 fork server가 child를 생성한다.
child 실행이 끝나면 fork server가 status를 다시 보낸다.
AFL은 이 status를 보고 다음을 판단한다.
1
2
3
4
정상 종료
crash
timeout
실행 실패
9. run_target() 분석
run_target()은 AFL에서 매우 중요한 함수이다.
이 함수는 실제로 타깃 프로그램을 실행하고 결과를 판단한다.
역할은 다음과 같다.
1
2
3
4
5
6
7
coverage bitmap 초기화
fork server에 실행 요청
타깃 프로그램 실행 대기
timeout 감시
종료 상태 확인
crash 여부 판단
coverage 결과 유지
실행 전에는 coverage bitmap을 초기화한다.
1
memset(trace_bits, 0, MAP_SIZE);
이유는 이전 입력값의 실행 결과가 남아 있으면 현재 입력값의 coverage를 정확히 판단할 수 없기 때문이다.
즉 매 입력 실행마다 bitmap을 비우고 새로 기록한다.
10. has_new_bits() 분석
has_new_bits()는 AFL의 핵심 판단 함수이다.
이 함수는 현재 실행에서 얻은 coverage가 이전에 본 적 없는 coverage인지 확인한다.
개념은 다음과 같다.
1
2
3
현재 trace_bits
vs
전체 virgin_bits
여기서 trace_bits는 현재 실행의 coverage이다.
virgin_bits는 아직 발견되지 않은 coverage 정보를 나타낸다.
새로운 coverage가 있으면 AFL은 해당 입력값을 흥미로운 입력으로 판단한다.
그 결과 queue에 저장될 수 있다.
10-1. 새로운 입력을 저장하는 기준
AFL은 모든 입력값을 저장하지 않는다.
저장 기준은 다음과 같다.
1
2
3
새로운 coverage를 만들었는가?
새로운 crash를 만들었는가?
새로운 hang을 만들었는가?
이 기준을 만족하지 못하면 입력값은 버려진다.
이 방식 덕분에 AFL은 의미 있는 입력값 중심으로 탐색을 계속할 수 있다.
11. Mutation 상세 분석
Mutation은 AFL이 입력값을 변형하는 과정이다.
AFL은 크게 다음 단계를 사용한다.
1
2
3
1. Deterministic Stage
2. Havoc Stage
3. Splicing Stage
11-1. Deterministic Stage
Deterministic stage는 정해진 규칙에 따라 입력값을 체계적으로 변형하는 단계이다.
대표적인 변형 방식은 다음과 같다.
1
2
3
4
5
bitflip
byteflip
arithmetic mutation
interesting value insertion
dictionary insertion
11-2. Bitflip
Bitflip은 입력값의 특정 bit를 뒤집는 방식이다.
예를 들어 1바이트가 다음과 같다고 하자.
1
00000000
1비트를 뒤집으면 다음과 같다.
1
00000001
AFL은 1bit, 2bit, 4bit 단위로 bitflip을 수행한다.
이 방식은 작은 변화로 분기 조건을 통과할 수 있는지 확인하는 데 유용하다.
예를 들어 입력값이 다음과 같을 때,
1
@BCD
한 비트를 뒤집으면 다음이 될 수 있다.
1
ABCD
이런 작은 변화로 새로운 경로가 열릴 수 있다.
11-3. Byteflip
Byteflip은 바이트 단위로 값을 변경하는 방식이다.
예를 들어 다음 입력이 있다고 하자.
1
41 42 43 44
이를 변형하면 다음과 같을 수 있다.
1
41 FF 43 44
문자열로 보면 다음과 같은 변화이다.
1
2
3
ABCD
→
A\xFFCD
Byteflip은 특정 문자가 바뀌었을 때 프로그램이 다른 경로로 들어가는지 확인하는 데 사용된다.
11-4. Arithmetic Mutation
Arithmetic mutation은 숫자 값을 증가시키거나 감소시키는 방식이다.
예를 들어 입력 안에 다음 값이 있다고 하자.
1
100
AFL은 이를 다음처럼 바꿀 수 있다.
1
2
99
101
또는 바이너리 값 기준으로 정수 값을 조작할 수도 있다.
이 방식은 다음과 같은 버그를 찾는 데 유용하다.
1
2
3
4
5
정수 오버플로우
정수 언더플로우
배열 인덱스 오류
길이 검증 오류
경계값 오류
11-5. Interesting Values
AFL은 취약점 탐지에 자주 사용되는 특수한 값들을 넣어본다.
대표적인 값은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0
1
-1
16
32
64
100
127
128
255
256
32767
32768
65535
65536
INT_MAX
INT_MIN
이 값들이 중요한 이유는 많은 버그가 경계값 근처에서 발생하기 때문이다.
예를 들어 다음 코드가 있다고 하자.
1
2
3
4
5
char buf[128];
if (len <= 128) {
memcpy(buf, input, len);
}
여기서 len이 128일 때와 129일 때의 동작은 매우 중요하다.
또한 signed/unsigned 변환 문제도 이런 값에서 자주 발생한다.
11-6. Dictionary Mutation
AFL은 사용자가 dictionary를 제공하면 해당 토큰을 입력값에 삽입하거나 덮어쓴다.
예를 들어 HTTP parser를 퍼징한다면 dictionary에 다음 값을 넣을 수 있다.
1
2
3
4
5
GET
POST
Host:
Content-Length:
Transfer-Encoding:
XML parser라면 다음 값이 유용할 수 있다.
1
2
3
4
<tag>
</tag>
<!DOCTYPE
CDATA
Dictionary mutation은 포맷이 있는 입력을 퍼징할 때 매우 효과적이다.
완전 랜덤 mutation만으로는 의미 있는 문법을 만들기 어렵기 때문이다.
11-7. Havoc Stage
Havoc stage는 랜덤성이 강한 변형 단계이다.
Deterministic stage가 체계적인 탐색이라면, havoc은 공격적인 무작위 조합이다.
Havoc stage에서는 다음과 같은 변형이 섞인다.
1
2
3
4
5
6
7
8
랜덤 bit flip
랜덤 byte 변경
랜덤 블록 삭제
랜덤 블록 삽입
랜덤 블록 복사
랜덤 위치 덮어쓰기
interesting value 삽입
dictionary token 삽입
예를 들어 원본 입력이 다음과 같다고 하자.
1
GET /index.html HTTP/1.1
Havoc을 거치면 다음과 같은 입력이 만들어질 수 있다.
1
GET /../../../../etc/passwd HTTP/1.1
또는 다음처럼 깨진 입력이 될 수도 있다.
1
G\x00T /AAAAAAA HTTP/9999
Havoc stage는 예측하기 어려운 조합을 많이 만들어내기 때문에, 복잡한 버그를 찾는 데 유용하다.
11-8. Splicing Stage
Splicing은 두 개의 queue 입력값을 섞는 방식이다.
예를 들어 다음 두 입력값이 있다고 하자.
1
2
input1 = ABCDEFGH
input2 = 12345678
AFL은 특정 지점을 기준으로 두 입력을 조합할 수 있다.
1
ABCD5678
Splicing의 목적은 이미 의미 있는 coverage를 만든 입력값끼리 조합하여 더 깊은 경로를 찾는 것이다.
즉 좋은 입력과 좋은 입력을 섞어서 더 좋은 입력을 만들려는 전략이다.
12. Queue 관리
AFL의 queue는 매우 중요하다.
AFL은 새로운 coverage를 만든 입력값을 queue에 저장한다.
그리고 queue에 저장된 입력값을 다시 mutation 대상으로 사용한다.
이 과정은 다음과 같다.
1
2
3
4
5
6
7
seed input
→ mutation
→ new coverage 발견
→ queue 저장
→ 다시 mutation
→ 더 깊은 coverage 발견
→ queue 저장
이 구조 때문에 AFL은 genetic algorithm 기반 퍼저라고 볼 수 있다.
12-1. queue_entry 구조
AFL은 각 입력값을 queue_entry 구조로 관리한다.
주요 정보는 다음과 같다.
1
2
3
4
5
6
7
8
9
파일명
입력 길이
실행 시간
coverage 크기
checksum
depth
favored 여부
calibration 여부
deterministic 완료 여부
여기서 depth는 해당 입력이 얼마나 많은 변형을 거쳐 만들어졌는지를 나타낸다.
예를 들어 초기 seed는 depth가 낮고, 여러 번 변형되어 나온 입력은 depth가 높다.
12-2. Favored Input
AFL은 모든 queue entry를 동일하게 취급하지 않는다.
특정 coverage를 가장 효율적으로 대표하는 입력값을 favored로 표시한다.
favored input은 퍼징 우선순위가 높다.
이유는 간단하다.
모든 입력을 똑같이 많이 변형하면 시간이 낭비된다.
AFL은 더 짧고, 더 빠르고, 더 좋은 coverage를 가진 입력을 우선적으로 사용한다.
12-3. cull_queue()
cull_queue()는 queue를 정리하는 역할을 한다.
많은 입력값이 같은 coverage를 만든다면, 그중 가장 효율적인 입력을 선택한다.
이 과정을 통해 AFL은 퍼징 시간을 더 가치 있는 입력에 집중한다.
13. Crash 처리
AFL은 타깃 프로그램이 비정상 종료되면 crash로 판단한다.
대표적인 crash 신호는 다음과 같다.
1
2
3
4
5
SIGSEGV
SIGABRT
SIGILL
SIGFPE
SIGBUS
Crash가 발생하면 AFL은 해당 입력값을 crashes 디렉터리에 저장한다.
예시:
1
out/crashes/id:000000,sig:11,src:000001,op:havoc,...
파일명에는 다음 정보가 포함될 수 있다.
1
2
3
4
5
id
signal
source input
mutation 방식
발견 시간
Crash input은 취약점 분석에서 매우 중요하다.
이 입력을 다시 타깃 프로그램에 넣으면 같은 crash를 재현할 수 있다.
14. Hang 처리
Hang은 프로그램이 제한 시간 안에 종료되지 않는 경우이다.
예를 들어 다음 코드가 있다고 하자.
1
2
while (1) {
}
특정 입력으로 이 코드에 도달하면 프로그램이 끝나지 않는다.
AFL은 timeout을 기준으로 hang을 판단한다.
Hang input은 다음 디렉터리에 저장된다.
1
out/hangs/
Hang도 서비스 거부 공격, 즉 DoS 취약점으로 이어질 수 있다.
15. AFL 출력 디렉터리 구조
AFL을 실행하면 output 디렉터리에 여러 파일과 디렉터리가 생성된다.
1
2
3
4
5
6
7
out/
├── queue/
├── crashes/
├── hangs/
├── fuzzer_stats
├── plot_data
└── .cur_input
각 항목의 의미는 다음과 같다.
queue
새로운 coverage를 만든 입력값이 저장된다.
1
out/queue/
이 디렉터리에 있는 파일들은 AFL이 의미 있다고 판단한 입력이다.
crashes
Crash를 유발한 입력값이 저장된다.
1
out/crashes/
취약점 분석 시 가장 먼저 확인해야 하는 디렉터리이다.
hangs
Timeout을 유발한 입력값이 저장된다.
1
out/hangs/
무한 루프나 성능 문제를 분석할 때 사용한다.
fuzzer_stats
현재 퍼징 상태가 기록된다.
예를 들어 다음과 같은 정보가 포함된다.
1
2
3
4
5
6
실행 횟수
초당 실행 수
발견한 path 수
crash 수
hang 수
실행 시간
.cur_input
현재 타깃 프로그램에 전달되는 입력 파일이다.
@@를 사용하는 경우 이 파일 경로가 타깃 프로그램 인자로 들어간다.
16. AFL 실행 예시
간단한 예제 코드를 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
char buf[4] = {0};
if (argc < 2) {
return 0;
}
FILE* fp = fopen(argv[1], "rb");
if (!fp) {
return 0;
}
fread(buf, 1, 3, fp);
fclose(fp);
if (buf[0] == 'A') {
if (buf[1] == 'F') {
if (buf[2] == 'L') {
abort();
}
}
}
return 0;
}
이 프로그램은 입력 파일의 앞 세 글자가 AFL이면 abort()를 호출한다.
컴파일:
1
afl-gcc -o target target.c
입력 디렉터리 생성:
1
2
mkdir in out
echo "aaa" > in/seed
퍼징 실행:
1
afl-fuzz -i in -o out ./target @@
AFL은 처음에 aaa를 입력으로 사용한다.
그리고 mutation을 통해 다음과 같은 입력들을 만들어본다.
1
2
3
4
baa
Aaa
AFa
AFL
결국 AFL을 만들면 프로그램은 abort()를 호출하고 crash가 발생한다.
AFL은 해당 입력을 out/crashes에 저장한다.
17. AFL과 BugBounty의 관계
AFL은 웹 취약점을 직접 찾는 도구라기보다는, 네이티브 프로그램이나 라이브러리의 입력 처리 취약점을 찾는 데 강하다.
BugBounty에서 AFL이 유용한 대상은 다음과 같다.
1
2
3
4
5
6
7
8
이미지 파서
압축 파일 파서
PDF 파서
문서 파일 파서
미디어 코덱
CLI 도구
C/C++ 기반 오픈소스 프로그램
프로토콜 파서
예를 들어 어떤 서비스가 내부적으로 이미지 파일을 처리한다면, 그 이미지 처리 라이브러리를 AFL로 퍼징할 수 있다.
또는 서버가 특정 파일 포맷을 업로드 받아 처리한다면, 해당 파일 파서를 AFL로 테스트할 수 있다.
18. AFL로 찾을 수 있는 취약점
AFL은 특히 메모리 관련 취약점 탐지에 강하다.
대표적으로 다음 취약점을 찾을 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
Buffer Overflow
Heap Overflow
Stack Overflow
Out-of-Bounds Read
Out-of-Bounds Write
Use After Free
Double Free
Integer Overflow
Integer Underflow
Null Pointer Dereference
Assertion Failure
Denial of Service
특히 C/C++ 프로그램은 메모리 안전성이 보장되지 않기 때문에 AFL과 같은 퍼저가 매우 효과적이다.
19. AFL 코드 읽는 추천 순서
AFL 코드를 처음 읽을 때는 무작정 위에서 아래로 읽으면 어렵다.
다음 순서로 읽는 것이 좋다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. config.h
2. afl-gcc.c
3. afl-as.c
4. afl-fuzz.c의 main()
5. setup_shm()
6. read_testcases()
7. perform_dry_run()
8. init_forkserver()
9. run_target()
10. has_new_bits()
11. save_if_interesting()
12. fuzz_one()
13. mutation stage
14. cull_queue()
이 순서로 보면 AFL의 흐름을 이해하기 쉽다.
먼저 설정과 컴파일 구조를 보고, 그다음 실제 퍼징 엔진을 보는 방식이다.
20. 핵심 함수 요약
AFL을 분석할 때 특히 중요한 함수들은 다음과 같다.
1
2
3
4
5
6
7
8
9
10
setup_shm()
read_testcases()
perform_dry_run()
init_forkserver()
run_target()
has_new_bits()
save_if_interesting()
fuzz_one()
cull_queue()
write_to_testcase()
각 함수의 역할은 다음과 같다.
setup_shm()
coverage bitmap을 위한 shared memory를 생성한다.
read_testcases()
초기 seed input을 읽어서 queue에 등록한다.
perform_dry_run()
초기 입력값들이 정상적으로 실행되는지 확인한다.
init_forkserver()
fork server를 초기화한다.
run_target()
타깃 프로그램을 실행하고 결과를 확인한다.
has_new_bits()
새로운 coverage가 있는지 확인한다.
save_if_interesting()
새로운 coverage, crash, hang 여부를 보고 입력값을 저장할지 결정한다.
fuzz_one()
queue entry 하나를 선택해서 mutation을 수행한다.
cull_queue()
효율적인 queue entry를 선택하고 favored 상태를 관리한다.
write_to_testcase()
변형된 입력값을 실제 테스트케이스 파일로 기록한다.
21. AFL의 설계상 장점
AFL의 장점은 다음과 같다.
1
2
3
4
5
6
구조가 단순하지만 효과적이다.
coverage feedback을 이용해 효율적으로 탐색한다.
fork server로 실행 속도가 빠르다.
mutation 전략이 다양하다.
crash와 hang을 자동으로 분류한다.
재현 가능한 입력값을 저장한다.
AFL은 단순히 랜덤 입력을 넣는 도구가 아니라, 새로운 실행 경로를 찾는 입력을 계속 발전시키는 구조를 가지고 있다.
22. AFL의 한계
AFL에도 한계는 있다.
22-1. 복잡한 입력 포맷에 약할 수 있음
AFL은 mutation 기반 퍼저이기 때문에, 매우 복잡한 문법을 가진 파일 포맷에서는 유효한 입력을 만들기 어려울 수 있다.
예를 들어 PDF, JavaScript, XML, 이미지 포맷처럼 구조가 복잡한 경우
완전 랜덤 mutation만으로는 깊은 파서 로직까지 도달하기 어렵다.
이때는 좋은 seed corpus와 dictionary가 중요하다.
22-2. checksum 검증에 막힐 수 있음
파일 포맷에 checksum이 있으면 mutation 후 checksum이 깨진다.
그러면 프로그램이 초반 검증에서 입력을 버릴 수 있다.
이 경우 AFL은 깊은 로직까지 도달하지 못한다.
22-3. 암호화된 입력에 약함
입력이 암호화되어 있거나 압축되어 있으면 작은 mutation이 내부 의미 구조를 완전히 깨버린다.
이 경우 퍼징 효율이 떨어진다.
22-4. 특정 비교문 통과가 어려움
예를 들어 다음과 같은 코드가 있다고 하자.
1
2
3
if (strcmp(input, "VerySecretMagicValue123") == 0) {
crash();
}
AFL이 순수 mutation만으로 이 문자열을 정확히 만드는 것은 쉽지 않다.
이런 문제를 해결하기 위해 dictionary, cmp-log, laf-intel 같은 기법들이 사용되지만, 이는 AFL++ 쪽에서 더 많이 확장된 부분이다.
원본 AFL에서는 이런 부분이 상대적으로 약하다.
23. AFL을 공부할 때 중요한 관점
AFL을 공부할 때 단순히 사용법만 익히면 부족하다.
중요한 것은 다음 질문에 답할 수 있어야 한다.
1
2
3
4
5
6
7
8
9
AFL은 왜 instrumentation을 사용하는가?
왜 coverage bitmap을 사용하는가?
왜 shared memory가 필요한가?
왜 fork server가 빠른가?
왜 edge coverage를 사용하는가?
왜 queue를 관리하는가?
왜 모든 입력을 저장하지 않는가?
mutation은 어떤 순서로 진행되는가?
crash와 hang은 어떻게 구분되는가?
이 질문들에 답할 수 있으면 AFL의 핵심 구조를 이해했다고 볼 수 있다.
24. 최종 정리
AFL은 coverage-guided fuzzing의 대표적인 도구이다.
AFL의 핵심 흐름은 다음과 같다.
1
2
3
4
5
6
7
Instrumentation으로 실행 경로를 기록한다.
Shared memory bitmap에 coverage를 저장한다.
Fork server로 타깃 프로그램을 빠르게 반복 실행한다.
Mutation으로 입력값을 계속 변형한다.
새로운 coverage를 만든 입력값은 queue에 저장한다.
Crash와 hang을 자동으로 분류한다.
Queue를 기반으로 입력값을 계속 발전시킨다.
AFL의 핵심은 단순 랜덤이 아니라 feedback이다.
입력값을 넣고 끝나는 것이 아니라, 그 입력값이 프로그램 내부에서 어떤 변화를 만들었는지 확인한다.
그리고 의미 있는 변화를 만든 입력값을 다시 변형한다.
이 구조 덕분에 AFL은 효율적으로 깊은 코드 경로를 탐색할 수 있다.
결국 AFL은 다음 네 가지가 결합된 퍼저라고 볼 수 있다.
1
2
3
4
빠른 실행 구조
정확한 coverage 추적
효율적인 입력 변형
의미 있는 입력값 선별
따라서 AFL 코드를 분석하는 것은 단순히 하나의 퍼징 도구를 공부하는 것이 아니라,
현대 coverage-guided fuzzing의 기본 원리를 이해하는 과정이라고 할 수 있다.