AFL fuzzer는 사실상 표준인 fuzzer로 fuzzing과 관련된 많은 논문에서 일종의 baseline으로 다루어진다.
가장 기본이 되는 fuzzer인 만큼 후에 참고용으로 공부한 것을 기록해둔다.
afl-fuzz 요약
아래 코드는 개인적으로 afl-fuzz.c 의 실행 흐름을 분석하고, 간략하게 pseudo code 형태로 짜본 것이다.
현재 가장 빈번하게 다루어지는 퍼징의 기본적인 형태는 다음과 같다.
1. Queue 에 initial seed, 즉 input 을 넣는다.
2. 반복문에 진입한다.
3. Queue 에서 entry 하나를 가져온다.
4. 이 entry 의 특성을 고려하여, 얼마만큼 fuzzing 시킬 지 결정한다.
5. mutate
6. 만약, mutate 된 testcase가 code coverage를 증가시켰다면, Queue에 추가한다. 4번에서 결정한 횟수만큼 5~6번 과정 반복.
afl-fuzz.c 코드에서도 위의 high-level 에서의 형태를 어느정도 매칭시킬 수 있었고, 매칭되는 부분을 pseudo-code로 옮겨본 것이다.
afl 의 가장 큰 특징은 code coverage를 metric으로 삼아 input testcase를 mutate하고, 그 효과를 판단한다는 것이다.
code coverage 란 프로그램의 CFG(Control-flow graph)에서 해당 실행이 어떤 node들과 branch들을 지나쳤는지 혹은 커버했는지, 즉 path를 나타내는 지표라고 생각하면 된다.
그렇다면, 이러한 code coverage를 어떻게 측정할까?
Coverage measurements : instrumentation
afl은 타겟 프로그램의 소스코드를 컴파일할 때, 아래 코드를 각 branch 에 내부적으로 삽입하여 컴파일하고, 이를 바탕으로 branch coverage를 측정한다. 이를 instrumentation이라고 한다.
cur_location = <COMPILE_TIME_RANDOM>;
shared_mem[cur_location ^ prev_location]++;
prev_location = cur_location >> 1;
컴파일 타임에 CFG에 있는 노드들에 특정한 ID를 랜덤하게 부여한다.
그래프에서 간선이란 것은 두 개의 노드를 잇는 연결을 말한다. 필연적으로 간선은 (시작 노드, 도착 노드) 로 표현된다.
그래서 프로그램이 실행될 때, 만약 어떤 특정한 branch를 지나가게 되면 위에 코드가 이 branch를 지나갔다는 것을 shared_mem에 기록하게 된다. 기록할 때, 시작 노드와 도착 노드의 xor한 값을 인덱스로 mapping 시켜 hit count를 증가시킨다. 즉, edge도 시작 노드와 도착 노드의 xor 연산을 하는 일종의 해시 함수를 통해서 id가 부여되고, 이 id가 곧 shared_mem에서 인덱스로 활용되는 것이다.
그런데 잘 생각해보면 여기에는 hash collision의 문제가 있다. 서로 다른 엣지가 같은 인덱스에 mapping 될 수 있다는 것이다.
CFG의 간선들은 directed edge이기 때문에, A -> B와 B -> A 사이의 구분이 필요하다. 이를 위해서, 마지막 라인에 도착 노드를 오른쪽으로 한번 right shift한 값을 다음 연산에 활용한다.
(A >> 1) ^ B와 (B >> 1) ^ A 와 같이 A -> B와 B -> A를 구분하겠다는 것이다.
하지만, 이는 여전히 hash collision을 완벽히 막지는 못한다.
공식 문서를 읽으면서, '이래도 해시 충돌 나지 않나?' 하면서 의문이 들었었는데 아니나 다를까 이에 관해서 자세히 설명한 논문도 존재했다.
least significant bit만 다르고 나머지 비트가 똑같은 노드가 존재한다면, right shift를 해도 동일한 값이 될 것이다. 이런 경우 hash collision도 존재할 수 있다.
그 외에도 해시 충돌이 일어날 수 있는 부분은 많다. 아래 논문에서 인용한 사진이 이를 잘 설명해준다.
이제 AFL Fuzzer가 어떤 behavior를 "interesting"한 것으로 생각하는지 알아볼 필요가 있다.
왜냐면 위에 interesting 한 지 여부를 바탕으로 Queue 에 해당 input을 추가할 지 말 지가 결정되고, 이는 나중에 overall performance에도 영향을 주는 중요한 지표이기 때문이다.
일단, 가장 간단하게 새로운 tuple 즉 branch가 발견되었다면, 이를 interesting 한 것으로 판단한다.
아래 예시를 보자.
#1. A -> B -> C -> D -> E
#2. A -> B -> C -> A -> E (CA와 AE가 새로운 튜플이므로, 이 testcase는 interesting한 것으로 간주된다.)
#3. A -> B -> C -> A -> B -> C -> A -> B -> C -> D -> E
하지만, 3번 예시는 새로운 튜플이 추가되지 않았으므로, 눈에 띄게 다른 실행 경로를 가지고 있음에도 불구하고 not interesting 한 것으로 간주되어 버린다.
AFL fuzzer는 이러한 문제를 해결하기 위해서 각 branch 별로 logarithmic 한 bucket을 유지한다.
1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+
공식 문서에서 coarse tuple hit counts라고 표현하는 것인데, 해당 branch를 지나가면 해당 횟수를 증가시킨다. 1번과 2번 예시는 A -> B 엣지가 한번씩만 기록되었을 것이므로, 첫번째 bucket에 속한다. 하지만, 3번 예시는 A -> B를 세번 지나가므로, 세번째 bucket에 속한다. 이는 엄연히 다른 실행 경로이므로, unique하게 다루어져야 맞다.
요약하자면, 각 실행 별로 비교하여 서로 다른 bucket 간의 이동은 interesting 한 것으로 판단하고, 같은 bucket에 속하는 것은 not interesting으로 판단한다.
Mutate
마지막으로 AFL이 어떻게 input을 mutate 시키는지 볼 필요가 있다.
공식 문서에서는 처음에는 deterministic strategies를 적용한다.
이는 sequential 한 bit flips, small integers arithmetics, insertions of known interesting integers를 포함한다.
sequential하다는 것에 주목해보면, 이러한 규칙적인 변형은 non-crashing 한 input과 crashing 한 input간의 차이를 줄여주고, 컴팩트한 testcase를 만들 수 있게 해준다.
이렇게 변형을 했음에도 유의미한 발견(code coverage 증가)이 없다면, non-deterministic strategies를 적용한다.
이는 random 한 변형을 가하는 과정이다. 위에 비슷한 연산을 좀 더 rough하게 적용하는 것으로 보면 된다.
이렇게 두 과정을 통해서도 안 된다면, 최후의 수단으로 splicing을 이용한다.
현재 input과 다른 input 아무거나 고른 것을 랜덤한 offset에서 이어붙여서 새로운 input을 만드는 것이다.
아무래도 가장 큰 변화를 주는 연산이라 마지막에 고르는 것 같다.
p.s.
어떤 특정한 기술에 대해서 개인적으로 공부하고, 분석하고, 코드를 요약해본 적은 이번이 처음인 것 같은데, 어려울 것을 예상했지만 생각보다 더 어려운 것 같다.
아직 익숙하지 않아서 그런 것 같은데, 앞으로 공부해가면서 부족한 부분을 더 채워나가야겠다.
Reference:
https://github.com/google/AFL/blob/master/afl-fuzz.c
https://afl-1.readthedocs.io/en/latest/about_afl.html#how-afl-works
https://www.atlantis-press.com/proceedings/icmsse-23/125992404
※ Any feedbacks and corrections are welcome. Feel free to comment down below.
