[Fuzzing] AFL (1)

* AFL(American Fuzzing Lop)

: edge coverage를 기반으로 feedback을 하는 퍼저.

(일반적인 코드 커버리지는 각각의 basic block이 실행되느냐로 측정하는데, edge code coverage는 basic block이 전화되는 것을 기반으로 측정. ex) A->B, (A,B)로 표현)

-> 더욱 사소하게 다음 실행 추적이 가능하며, 기본 코드에서 미묘한 오류 조건을 발견하는데 도움이 됨

(보안 취약점은 예상치 못한 문제 또는 새로운 basic block에 잘못되게 전환되는 경우와 연관되는 경우가 더 많기 때문)

+) AFL은 OpenSSL, PHP, MySQL 같은 유명한 소프트웨어의 취약점을 찾는데 사용되곤 했다.

 

afl-fuzz -i input_directory -o afl_out -- ./program

 

* AFL instrumentation

 

instrumentation은 컴파일 타임에 프로그램에 삽입되어, edge coverage와 hit counts를 측정한다.

(hybrid 방식으로, edge coverage와 hit counts를 결합한 maxtrix로 표시)

아래의 코드는, branch point마다 동일하게 삽입된다.

 

cur_location = <COMPILE_TIME_RANDOM>;

shared_mem[cur_location ^ prev_location]++;

prev_location = cur_location >> 1;

 

- cur_location의 값은 복잡한 프로그램을 링킹하는 프로세스를 단순화하기 위해서 무작위로 생성된다.

그리고 균일하게 xor output을 유지한다.

- shared_mem[] 은 L2 cache에 적합하게 64KB이며, 퍼저와 타겟 프로그램 사이에서 공유하는 메모리다.

- cur_lcoation ^ prev_location이 가능한 이유는, AFL은 edge coverage이기 때문에 A->B를 측정하기 때문이다.

- shared_mem의 output map에 설정된 모든 byte는 특정 branch_src, dest와 같은 튜플의 hit로 생각할 수 있다.

- map의 크기는 충돌이 거의 모든 경우에 산발적으로 발생하도록 선택하여 2K~10K 사이며, 분석할 수 있을 만큼 충분히 작아 수신 측에서 ms 만에 받아서 분석이 가능하다.

- 단순한 saturating arithmetic opcode가 없는 이유는, hit counter가 가끔 0으로 덮힐 수 있고 이럴 가능성은 굉장히 낮고 지역화된 이밴트이기 때문에 성능과의 트레이드 오프하의 절충안이다.

- afl-gcc 또는 afl-g++ 을 이용해 컴파일 타임에 instrumentation이 추가된다.

- afl-clang-fast 또는 alfg-clang-fast++ 을 사용하면, LLVM 모드에서 보다 빠르게 instrumentation code를 빌드할 수 있다. (clang: C/C++과 같은 프로그램 언어를 위한 컴파일러 프론트엔드로, LLVM은 벡엔드로 사용)

- LLVM 모드를 사용하면, ASAN 같은 data tracking과 검증에 다른 clang 기능들도 사용할 수 있다.

 

AFL의 gcc를 보면, 일반 gcc와 달리 앞 부분에 더 많은 작업을 수행한다.

우선 처음에, instrumenation이 clobber할 부분을 save 해둔다. (*clobber : 완전히 overwrite)

그리고 rcx에 <complie_time_random>을 넣고, 이 예제에서는 이 값이 0xb71e다. (cur_location에 해당)

이후, loc.__afl_maybe_log를 호출하고, 저장해놓은 레지스터를 원상복귀한다.

alf_maybe_log에는 afl_setup으로 jump하고,

afl_setup에는 loc.__afl-setup_first로 jump하는 코드를 포함하고 있다. (AFL 초기화 코드)

afl_setup 에서 초기화 한 이후에는, loc.__afl_store로 jump를 한다.

rcx = <comple_time_random>이 들어있는데, 여기서 alf_prev_loc와 xor을 한 뒤 shr 1을 하고, ++을 해준다.

즉, shared memory에서 cur ^ prev에 해당하는 값을 +1을 한 뒤, prev 로케이션을 cur >> 1로 셋팅한다는 뜻이다.

이 때 shift 연산을 해주는 이유는 튜플의 방향성을 유지하기 위함이다. (A^B와 B^A를 구별하기 위해)

 

컴파일 과정을 간단하게 정리해보면,

instrumentation이 clobber할 부분을 save 하고

-> rcx에 complie_time_random을 넣고

-> afl_maybe_log를 호출하고

-> afl_maybe_log에서 afl_setup으로 jump하고

-> afl_setup에서 afl_setup_init으로 jump해서 초기화를 한 이후

-> afl_setup에서 afl_store로 jump해서 shared_memory의 값을 +1 해주고, prev를 cur/2로 변경해준다.

-> main으로 돌아와서 저장해놓았던 레지스터를 원래되로 복구한다.

(main -> afl_maybe_log -> afl_setup(->afl_setup_init), afl_store -> main)

 

fuzzer는 target program의 모든 실행 tuple들의 집합을 유지하고 있다.

이전 실행 tuple들의 global map도 유지하고 있는데 이는, 각각의 trace랑 빠르게 비교가 가능하고, 간단한 루프를 통해서 짧은 내에 업데이트가 가능하다.

 

*trace_bits 는 instumenatino bitmap이 저장되는 shared momery이고,

virgin_bits[MAP_SIZE] 는 퍼징에서 아직 다루지 않은 영역

virgin_tmout[MAP_SIZE]는 tmouts를 보지 못한 비트

virgin_crash[MAP_SIZE]는 crash에서 보지 못한 비트 이다.

 

이 중 virgin_bits는 퍼저가 새로운 local-state를 유발하는 input이 있으면,

추후 queue에 추가하고 virgin_bit가 업데이트 된다.

 

local-state를 OR이라고 정의한다.

input 레지스터는 trace_bits 중의 new tuple에 해당하고,

input은 이전 튜플에서 보인 hit_count를 증가시킨다.

hit_count는 각 tuple들이 shared_mem[]++을 실행할 때 마다 하나씩 증가하게 된다.

hit_count의 경로 이탈을 피하기 위해서 bucket으로 나눠서 저장한다.

즉, hit_count가 다른 bucket으로 바뀔 때만 고려 된다. (같은 범위 내의 hit_count 증가인 input은 고려X)

-> 매우 세밀하고 정기적인 탐색이 가능

 

* AFL Queue

input queue는 항상 추가되서 자라는 형태 (대체 X, 삭제X, only 추가)

-> state에 변화를 주는 mutated test는 input queue에 저장되고, 추후 퍼저의 라운드의 input으로 사용

-> 점진적으로 개선시키기 때문에 blind fuzzing보다 이득

-> 프로그램의 mutually exclusive를 가능한 형태로 점진적으로 탐색 가능

-> 즉, 평균적으로 대다수의 프로그램에서 큐의 크기는 1K ~ 10K의 element

 

queue_entry의 구조체를 보면, test case의 파일 이름, 인풋 길이, fuzzing 됐는지, new coverage를 유발했는지, path depth, 그리고 *next element랑, *next_100에 대한 구조체도 포함하고 있다.

 

이렇게 dept에 따라 level이 나눠져 있고, 각 element에는 bucket으로 구분되어 있다.

level1은 blind fuzzing을 통한 결과이고, level2는 level1에서의 테스트 케이스를 시드로 사용해서 나온 결과다.

 

input queue는 추가만 되기 때문에, 가장 최신의 input으로 사용된 edge coverage는, old input에 대한 super set이 될 수 밖에 없다. fuzzing effort를 최적화하기 위해 AFL은 아래 과정을 통해 queue를 재평가한다.

-> 평가에 사용하는 알고리즘은 빠른 속도로 모든 tuple을 커버하는 더 작은 subset을 선택한다.

-> 각 queue entry의 점수는 실행 대기수랑 파일 크기에 비례하여 할당한다.

-> 각각의 튜플에 대한 점수 중 가장 낮은 점수인 테스트 케이스를 선택한다.

-> 선택된 tuple은 다음과 같은 과정로 처리된다.

 

1. temporary working set에 아직 없는 next tuple을 선택한다.

2. 해당하는 tuple의 winning queue entry에 위치시킨다.

3. working set에 있는 entry의 trace에 있는 모든 tuple을 등록한다.

4. set에서 어떤 missing tuple이 있다면 1번으로 돌아간다.

-> 이 과정을 통해 모든 winning queue entry의 위치에 favored 라고 마킹해놓는다.

(shared mem의 크기가 제한적이어서 충돌 가능하기 때문에 weighted minimum set은 favored test case 유지)

-> favored entry는 일반적으로 시작 데이터보다 5-10x 작다.

-> non-favored entry는 삭제되지는 않지만 큐에서 만났을 때 상황별 확률에 따라 건너 뛴다. 

ex. 새로운 favorite이 없고 현재의 non-favored entry가 전에 퍼징됐으면 95% 확률로 skip

-> queue 사이클링 속도와 test case의 다양성 간의 합리적인 균형 제공

-> afl-cmin을 사용하면 더 정교하지만 느린 culling 가능 (중복 엔트리 제거)

 

* AFL Mutator

Fuzzer의 mutation은 다음과 같은 challenge가 있다.

1. 만약 mutation이 너무 약하면, fuzzer는 좋은 coverage에 도달할 수 없다.

2. 반대로, mutation이 너무 공격적이면, fuzzer는 parsing 단계에서 fail될 너무 많은 testcase를 생성할 것이다.

 

AFL은 target input에 대해 우선, deterministic stage를 수행하고, 

추후, not-deterministic fuzzing으로 바꾸고, 다른 input들을 조합해서 사용한다.

 

- Deterministic stages

1. walking bit flips (with auto exrtras detcetion) //bit flip 수행

2. simple arithmetics //단순 산술연산

3. interesting integers 

 

- Not-deterministic stages (Havoc) : radom location에서 수행 (test case의 크기 변경도 가능)

1. bit flip

2. insert a interesting integer

3. random endian additions/subtractions

4. single byte set to random value

5. block deletion/duplication/memset

 

- Last resort stage (Splice) : 이전의 모든 단계에서 새로운 intersting input을 찾지 못했을 때 호출한다.

큐에서 2개의 다른 input을 재조합한다. 이 때 하나는 현재 mutating 하고 있는 current에 해당한다.

여기서 재조합된 input은 havoc stage의 input으로 들어가게 되고 보통 20%의 새 tuple을 발견한다.

ex. HTTP parser의 doble free 취약점 같은 경우 이 단계가 유일하게 효과적이다.

 

* AFL Forkserver

execve loader의 호출은 fuzzer에게 쓸모없는 오버헤드이기 때문에 AFL은 forkserver를 사용한다. (성능향상)

ELF에 작은 코드 조각이 들어가면, child process는 메인에서 멈춘 다음, 파이프를 통해 각각의 요청되는 excution을  child process로 fork한다.  (즉, execve(), linking, libc initialization 을 한 번만 수행하고, clone)

-> loading과 dynamic linking의 overhead를 피할 수 있다.

 

+ forkserver는 나중에 fork()를 할 수도 있는데, 이 경우는 퍼저가 메인 시작 루틴이나 초기화를 하지 않아도 됨.

 

* AFL mode

- Qemu mode

소스 코드가 available 하지 않을 경우, black-box 바이너리의 instrumentation의 제공용으로 빠르고 즉각적이다.

target program이 QEMU 안에서 작동할 경우, IR로 implemenation을 제공한다.

AFL의 command line에 -Q 옵션을 주면 사용 가능하다.

 

- LLVM mode

alf-gcc는 asm file안에 instrumentation code가 들어가는데, 이런 경우 컴파일러가 최적화시기키 어렵고 느리며 x86에 의존적이다. LLVM mode는 instrumentation이 LLVM IR에 적용되고, 이런 문제를 극복할 수 있다.

alf-clang-fast 컴파일러가 이 모드랑 관련 있다.

 

** 컴파일러에서 프론트엔드는 C/C++ 같은 고급 언어를 읽어서 파싱 후 IR (중간 표현)으로 바꾸고, 백엔드는 IR을 갖고 최적화 하여 최종적으로 타겟에 맞는 기계어를 바꾸는 것으로, LLVM 자체는 LLVM IR을 정의하고 이 IR을 갖고 최적화, 기계어 코드 생성 등을 수행한다. 따라서 프론트엔드는 컴파일러가 뭐가 되던 간에 거기에 맞는 LLVM IR만 만들면 된다.

 

많은 애플리케이션의 초기화 작업은 시간을 쏟는데, 이는 포크 서버에서 메인에서 멈추는 작업으로는 충분하지 않다.

LLVM mode에서는, deferred entry point를 정할 수 있다.

main 이후 target의 위치에 아래의 코드를 넣기만 하면 된다.

 

#ifdef__AFL_haVE_MANUAL_CONTROL

 __AFL_INIT();

#endif

 

- Persistent mode

fork()는 bottleneck이 걸릴 수 있고, 무겁기 때문에 persistent mode가 존재한다.

application이 stateless라면 afl-clang-fast의 persistent mode를 사용할 수 있다. (fork is heavy)

single long-lived process는 다음과 같은 형식으로 multiple input의 테스트에 재사용될 수 있다.

(각 반복에서의 상태 변경 최소화해서 사용)

 

while(__AFL_LOOP(1000)){

    read input data

    call library code to be fuzzed

    reset state

}

 

* Trimming

file 크기는 fuzzing 성능에 있어서 큰 영향을 준다. 

∵ 큰 사이즈의 파일은 target binary를 느리게 만들고, mutation이 중요한 format contrl structres를 건드릴 가능성을 줄이기 때문

 

필연적으로 trimming이 필요한 경우들이 생기기 때문에 AFL에서는 trim 기능을 제공한다. (커버리지 유지, 속도 향상)

ex. 좋은 초기 set으로 시작하는 것으로는 충분하지 않거나, 가끔 몇몇 mutation은 파일을 만들 때마다 큐에 있는 파일 크기를 반복적으로 증가시기는 경우

 

 AFL 스스로 fuzz가 시작할 때,

1. 큐에서 input을 가져온 다음 input의 일부분을 제거하고

2. instrumentation의 결과에 영향을 주는지 확인한다.

3. 만약에 삭제한 게 trace_bits checksum에 영향이 없다면, 삭제 명령을 disk로 commit한다.

-> 트리머는 정밀도와 execve() call 횟수와의 균형을 맞추기 위해 설계되었기 때문에 block 크기를 단계별로 매칭해보면서 정한다.

 

* Parallel fuzzing

AFL은 단일 코어에서 동작하기 때문에,  CPU의 모든 power를 사용하고 싶다면 여러 개의 AFL instance를 동작시켜야한다. 이렇게 한다면, 같은 input에 대해서 여러 번 fuzz가 수행될 수 있기 때문에 큐를 주기적으로 검사한다.

즉, 다른 instance 사이의 queue에서 interesting testcase의 동기화를 해준다.

이를 위해 같은 output directory를 정해주고(-o afl-out) 각 퍼저의 이름과 역할을 정해준다.

역할은 master(-M name)와 slave(-S name)가 있다.

- master instance는 모든 단계에서 수행가능하다.

- slave instance는 havoc 과 splice 단계에서만 수행된다. (deterministic stage는 불가능)

afl-fuzz -i initial_dir -o alf_out -M afl_master -- ./program

 

output directory는 다음과 같이 fuzzer의 이름으로 구분되어 있는 모습을 확인할 수 있다.

 

* afl-tmin (testcase minimization) : 퍼저 밖에서, testcase를 보다 나은 방법으로 최소화시킬 수 있다.

1. 데이터의 큰 block을 0으로 채운다. (아스키 숫자 '0')

2. binary search spirit을 통해 block deletion으로 크기를 줄인다.

3. 알파벳 정규화로, unique한 문자의 수를 세고 '0'으로 교체한다.

4. not-'0' byte의 byte-by-byte 정규화를 수행한다.

-> 처음 input의 bitmap은 유지되어야한다.

 

* afl-cmin (corpus minimization) : 큐에 있는 모든 테스트케이스들을 다양한 타입으로 최소화하는데 사용된다.

큐에서 쓸모없는 모든 testcase를 삭제한다.

afl-cmin을 실행하기 위해서는, 보통 master instance가 첫번째 싸이클을 끝낼 때까지 기다린 뒤 실행하는 것이 좋다.

(slaves instance는 한번의 master cycle이 도는 동안 여려번의 cycle을 수행)

(하나의 cycle은 큐에 있는 모든 input이 퍼징될 때까지 반복하는 것)

 

fuzzer를 멈추면, afl-cmin의 queue direcotry가 그 전에 저장되고, 옵션으로 afl-tmin을 모든 파일에 대해 수행할 수 있다. 멈춘 뒤 해당하는 큐를 초기 input 디렉토리로 다시 restart하고 싶을 때는 다음과 같은 커맨드를 사용한다.

afl-fuzz -i - -o afl_out -- ./program

 

* Dictionary

사용자는 fuzzing을 하는 동안 dictionary keyword를 사용할 수 있다.

-x 옵션을 사용하면, keyword 파일을 지정할 수 있다.

ex. HTTP parser를 퍼징하고 있다면 딕셔너리에 HTTP, GET 등을 넣어서 사용

AFL은 이런 키워드를 deterministic stage와 havoc stage에서 넣어서 사용한다.

 

* LibTokenCap

키워드에 대해 알지 못할 경우 Dictionary 기능 대신 LibTokenCap을 사용할 수 있다.

LibTokenCap은 strcmp(), memcmp()등 syntax token을 자동으로 추출하는 함수를 사용한다.

LD_PRELOAD=/.libctokencap.so 로 로드한 뒤에 AFL_TOKEN_FILE을 output file로 설정하면 된다.

 

* ASAN/MSAN

crash가 났다고 해서 보안적인 이슈라는 뜻은 아니고, 보안 이슈 역시 crash를 유발하지 않을 수 있다.

청크 메타데이터를 1byte 오버플로우하는 crash를 유발하지만,

사용가능한 메모리의 1byte를 overflow 했다면 이는 보안 이슈지만 crash는 유발하지 않는다.

이런 타입의 버그를 감지하는데 유용한 도구로 memcheck plugin of Valgrind가 있다. (비쌈)

LLVM toolchain도 이와 비슷한 기능으로 ASNA과 MASN을 제공한다.

(dynamic instrumentation 대신, complie-tile instrumentation 기반)

- ASAN(AddressSanitizer) : 빠른 메로리 error detector

- MSAN(MemorySanitizer) : 초기화되지 않은 read에 대한 detector

 

이 기능은 다음과 같은 환경설정 변수를 설정해주면 된다.

AFL_USE_ASAN=1, AFL_USE_MSAN=1

 

이 기능들은 퍼징하는데 오버헤드가 크기 때문에 ASAN의 컴파일 타겟 프로그램을 32bit로 사용하는 것을 추천한다.

 

* LibDislocator

ASAN 보다 싼 heap-based memory error detection이다. (느리고, 메모리 소모 큼)

malloc, calloc, free같은 libc function을 tokencap처럼 LD_PRELOAD를 통해 다른 libc로 교체한다.

r/w overflow를 탐지하기 위해 할당된 모든 버퍼가 메모리매핑되기 전에 대체되어야하기 때문에 느리다.

그리고 heap 카나리는, negative write로 감지될 수는 있는데 read로는 불가능하다.

 

* Smart Scheduling

coverage-guided fuzzer에서 우선 알고리즘을 구현할 수 있다.

스케쥴러의 목표는 smart test case를 선택해서 coverage와 bug 탐지를 향상시키는 것이다.

- AFLFast

더 많은 버그와 더 많은 branch를 탐지하기 위해 low-frequency path 강조.

1. fuzzer가 seed를 선택하는 순서에 관한 새로운 검색 전략 도입

2. 각 seed에서 생성된 입력량을 조절할 수 있도록 퍼징 프로세스에서 6개의 스케쥴 도입

(fast, coe, explore, quad, lin, exploit)

 

- MOpt

seed 스케쥴링의 horizontal 문제로 도입된 스케쥴링 방법으로,

mutation operator마다 다른 확률을 부여해서 가능성을 탐색

-> fuzzer 커버리지를 빠르게 발견 가능

-> 퍼징 단계를 pilot과 code module로 구분 가능

-> pilot : operator를 평가하여 효율성 기반으로 확률 할당

-> code module : pilot이 평가한 것들의 확률을 고려해서 선택한 뒤 mutation 생성

 

* Bypassing Roadblocks

string이나 checksum 같은 road block으로 인해 뒤에 있는 code를 탐색하기 어려워서 이를 우회해야한다.

- LAF-Intel

hard multibyte comparison을 우회하기 위해서, single byte comparision으로 분할해서 우회하는 방법

-> byte to byte로 각 부분에 대해 feedback을 받기 때문에 comparision 통과 가능

(integer comparision의 분할 + strcmp같은 string comparision도 가능,

string은 complie time에서 하나의 argument를 알고 있을 때)

1. >=이나 <=같은 operator는 단순하게 > 또는 < 과 ==의 체인으로 변경

2. signed integer comparision은 single only comparision과 unsigned comparision의 체인으로 변경

3. 64bit, 32bit, 16bit의 모든 unsigned integer comparision를 여러개의 8bit comparision 체인으로 분할

 

- REDQUEEN

traint tracking이나 symbolic excution 같은 무거운 기술 없이,

KAFL기반으로 hard comparision과 checksum을 우회 가능 (I2S comparision 중심)

1. input의 colorization 단계에서 엔트로피 증가

(testcase의 커버리지를 유지하면서 랜덤 데이터로 byte 변경)

-> I2S comparision의 operand를 관찰하면서 fuzzer의 입력에서의 위치의 경우의 수를 줄일 수 있음

2. comparision에서 추출한 I2S token을 대체할 수 있는 input을 mutate

3. 2의 정보를 다시 사용해서 checksum 체크 위치를 찾을 때 사용하고 패치

4. 새로 생성된 input의 checksum을 복구하기 위해서 I2S를 다시 사용

-> 만약에 실패한다면 패치된 checksum은 fals positive임으로 패치 제거

 

*** I2S(Input-To-State) : 적어도 하나의 operand에 있는 입력과 direct dependecy를 갖는지 comparision

 

* AFL Smart

PEACH를 input 모델 포맷으로 사용해서, peach로 쓰인 프로토콜 재사용 가능

처음 queue에서 뽑아온 testcase를 parse한다.

AFL Smart는 lazy하고 deferred cracking이기 때문에 parsing이 굳이 필요없이 coverage가 좋다면 AFL로 대체한다.

 

*** PEACH: black-box 퍼징 도구

 

참고: https://theromanxpl0it.github.io/articles/2019/03/29/fuzzing-talk.html

Fuzzing like the Legendary Super Saiyan · TRX

참고: https://www.usenix.org/system/files/woot20-paper-fioraldi.pdf