Fuzzing 소개, AFL

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

Fuzzing like the Legendary Super Saiyan · TRX

 

위 ppt를 읽고 정리하였습니다.

 

1. What The Fuzz?

---

위키피디아에서, 퍼즈 테스팅, 또는 퍼징은 (자동화 또는 반 자동화된) 소프트웨어  테스트 기법으로, 컴퓨터 프로그램에 유효한 예상치 않은 무작위 데이터를 입력하는 것이다.

 

fuzzer로 할 수 있는 일: 버그를 유발하는 입력을 찾는 것, -> 손으로 생성할 수 없는 많은 테스트를 실행하는데 효과적이다.

fuzzer로 할 수 없는 일: fuzzed 소프트웨어에 (퍼징 대상) 버그가 없음을 증명하는 것.

 

parser가 있는 프로그램은 퍼징에 적합하다.

대표적으로, 이미지 라이브러리, pdf reader, compiler, 시스템 유틸리티, HTTP 서버 등이 있다.

 

 

2. Fuzzing의 종류

---

White box fuzzing

화이트박스 퍼징은 프로그램 분석을 통해 탐색하는 경로의 수를 최대회한다. -> code converage가 높다. (sage?)

일반적으로 모든 유형의 fuzzer에서 코드 커버리지가 높을 수록 좋다.

 

Black box fuzzing

블랙 박스 fuzzer은 dumb bash fuzzed나 radamsa와 같이 대상 프로그램 구조를 인식하지 못한다.

휴리스틱을 사용하는 스마트 블랙박스 fuzzer도 있다. 이는 출력과 입력을 연관짓는다. 이러한 방식으로 fuzzer은 프로그램 구조에 대한 일부 정보를 학습 가능하다.

 

Grey box fuzzing

정보를 얻기 위해 소스코드 또는 바이너리 프로그램 계측을 사용한다. 이러한 정보들은 일반적으로 code converage (coverage-guided fuzzing) 와 관련있다. 퍼저에 도움이 될만한 유용한 정보를 얻기 위해 계측기를 사용할 수 있는 다양한 분석 (e.g. taint tracking 등) 이 있다.

 

조사했던 ppt에서는 가장 인기있는 grey box fuzzer 중 하나인 American Fuzzy Lop (AFL)에 초점을 맞춘다.

 

3. 기타 퍼징 개요

---

Input Structure awareness (입력 구조 인식)

fuzzer은 입력 구조를 인식할 수 있다. 가장 유명한 인식 fuzzer중 하나는 peach이다. peach를 사용하면 XML모델을 사용하여 입력 구조를 설명해야 하며, fuzzer가 그에 딸다 테스트 케이스를 생성한다.

 

AFL의 최근 트위스트인 AFLSmart는 American Fuzzy Lop과 Peach를 결합한다.

 

기타 주목할만한 Fuzzer

다른 그레이박스 범위 퍼징은 다음과 같다.

- LLVM libFuzzer : LLVM 도구 체인에서 제공하는 fuzzer이다.

- Google hoggfuzz : 강력한 피드백 기반 fuzzer (커버리지, 명령 계산 포함) 하드웨어 기반 엔진을 사용하며, 정보를 얻기 위해 intel processer에 의해 노출된 여러 하드웨어 기능을 사용할 수 있다. 

 

 

4. American Fuzzy Lop

---

AFL은 가장 인기있는 fuzzer 중 하나이다. openSSH, PHP, MySQL, FireFox 등과 같은 매우 널리 퍼져있는 소프트웨어에서 치명적인 취약점을 발견하는데 사용되었다.

 

edge coverage를 기반으로 피드백을 사용한다.

기본 블록이 실행되는 표준 코드 커버리지 로그 (ex. ABC) edge code coverage는 기본 블록 전환 (ex. A->C, A->B)을 로그한다.

 

이러한 전환을 튜플이라고 한다. (ex. A->C = (A,C))

 

edge A -> B

 

AFL Instrumentation

AFL 백서에서 cur_location = <COMPILE_TIME_RANDOM>;

shared_mem[cur_location ^ prev_location]++;

prev_location = cur_location >> 1;

 

shared_mem은 fuzzer와 계측 대상 프로그램 간에 공유되는 64kb SHM이다.

충돌이 가능하다. .?

 

컴파일 타임에 instrumentation을 삽입하기 위해 afl-gcc 및 afl-g++을 사용하여 프로그램을 컴파일 할 수 있다.

 

사용자 정의 LLVM을  사용하면 더 빠른 instrumentation코드를 빌드하는 afl-clang-fast, afl-clang-fast++을 사용할 때 clang용 wrapper도 있다.

 

LLVM모드에서 AFL을 사용하면 ASAN과 같은 데이터 추적 및 유효성 검사를 위해 다른 clang기능도 사용할 수 있다. 모범 사례 장에서  확인 가능하다.

 

stand GCC를 썼을 때와, AFL GCC를 썼을 때의 instruction

 

 instrumentation이 망가질 레지스터를 저장하는 부분

 

rcx는 컴파일 타임에서 랜덤값으로 정해지고

afl_maybe_log를 호출한다.

...

 

AFL 휴리스틱

fuzzer는 대상의 모든 실행에서 볼 수 있는 튜플 모음을 유지한다. virgin_bits와 비교하여 입력이 새로운 로컬 상태를 트리거하는 지 알 수 있으며 그렇다면 나중에 추가 처리를 위해 대기열에 삽입되고 virgin_bits가 업데이트 된다.

 

입력은 trace_bits에 새 튜플을 등록한다. 이전에 본 튜플의 hit_count 를 증가시킨다.

hit count는 튜플을 만날 때마다 증가하며, 경로 폭발을 피하기 위해 hit_count는 버킷으로 나눈다.

 

AFL Queue

입력 대기열은 항상 증가하고 새 입력은 교체가 아니라 보완으로 추가된다.

이를 통해 프로그램의 점진적인 상호 배타적 기능을 탐색할 수 있다.

이는 평균적으로 대기열이 대부분의 프로그램에서 1k~10k 요소 사이의 크기에 도달함을 의미한다.

 

AFL Queue Evaluation

AFL은 주기적으로 대기열의 테스트케이스를 평가한다. 실행 대기 시간과 파일 크기에 비례하여 점수를 할당한다.

이후, 각 튜플에 대해 점수가 가장 낮은 테스트 케이스를 선택한다.

 

AFL Mutator

Mutator 주요 과제는 다음과  같다.

- 변이가 너무 약하면 fuzzer가 좋은 범위에 도달할  수 없다 (code coverage) 

- 변이가 공격적이면 초기 구문 분석 단계에서 실패할 많은 테스트케이스를 생성할 수 있다.

 

AFL은 대상 입력에 대해 일련의 결정적 단계를 사용한 다음 이후 단계에서 다른 입력의 비결정적 퍼징 및 재조합으로 이동한다.

 

결정적 단계는 다음과 같다.

- 워킹 비트 플립 (자동 엑스트라 감지 포함)

- 간단한 산술

- 흥미로운 정수 (0, 1, INT_MAX.. )

 

 

AFL Mutator - havoc

비 결정적 단계 (havoc)는 임의의 위치에서 이 작업을 수행한다.

- 비트 뒤집기 

- 흥미로운 정수 삽입

- 임의 엔디안 덧셈, 뺄셈

- 임의의 값으로 설정된 단일 바이트

- 블록 삭제/  복제/ memset

 

AFL Mutator - Splice

모든 단계가 새로운 흥미로운 파생 입력을 찾지 못햇을 때, 호출되는 최후의 수단이다.

적어도 두 위치가 다른 큐에서 두 개의  다른 입력 (하나는 우리가 변경하고 있는 현재)을 재결합한다.

 

재결합 후 융합된  입력은 대혼란 단계로 전달된다.

일반적으로 이것은 새 튜플의 20%를 발견한다.

 

AFL ForkServer

execve 로더 호출은 fuzzer에서 불필요한 오버헤드이다.

AFL은 이에 대해 알고 있다.

작은 코드 조각이 ELF에 주입되어 하위 프로세스가 main에서 중지된다. 요청된 각 실행은 해당 자식의 포크이다.

 

이 해킹을 통해 AFL은 로딩 및 동적 링크의 오버헤드를 방지한다.

 

AFL 사용

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

 

AFL Qemu 모드

소스코드가 없을 때, target 프로그램은 중간 표현을 계측하는 QEMU 내에서 실행될 수 있다.

 

AFL LLVM 모드

afl-gcc를 사용하면 계측 코드가 생성된 asm 파일에 삽입된다.

이 경우, 컴파일러 최적화를 적용하기 어렵기 때문에 속도가 느려진다.

afl-gcc 계측도 x86에 따라 다르다.

 

llvm 모드에서는 계측이 llvm IR에 적용되어 이 문제를 극복한다.

 

 

Trimming

파일 크기는 퍼징에  큰 영향을 미친다. 좋은 초기 세트로 시작하는걸로는 충분하지 않다. fuzzer가 큐의 파일 크기를 늘릴 수 있다.

이를 되돌리기 위해 AFL에서 입력을 퍼징하기 시작할 때, 입력의 일부를 삭제하려고 시도하고 이것이 계측 출력에 영향을 미치는지 확인한다. 삭제가 trace_bits 체크섬에 영향을 미치지 않으면 디스크에 커밋된다.

 

Parallel fuzzing

AFL은 단일 코어에서 작동한다. 

CPU에서 모든 성능을 활용하려면 여러 AFL인스턴스를 실행해야 한다.

그러나 동일 입력을 fuzzing 하는 것은 피해야한다. Master와 Slave의 역할이 있다고는 하는데..

`afl-fuzz -i initial_dir -o afl_out -M afl_master -- ./program `

 

5. 유용한 전략

---

afl-tmin

afl-tmin 도구를 사용하여 더 나은 방법으로 테스트케이스를 최소화할수 있다. 단계는 다음과 같다.

1. fill with '0'  large blocks of data

2. 이진 검색으로 크기를 줄여가며 블록 삭제 수행

3. 알파벳 정규화, 고유 문자를 세고 '0'으로 교체

4. not-'0' 바이트의 바이트별 정규화

 

이 외에도 corpus minimization 을 위해 afl-cmin등이 있다.

 

ASAN / MSAN

Valgrind의 memcheck 플러그인이 있지만 비싸고..

LLVM tool chain은 동적 계측 대신 컴파일 타임 계측을 기반으로 하는 유사한 기능을 제공한다.

메모리 오류 감지기인 ASAN과 초기화되지 않은 읽기 감지기인 MSAN이 있다.

 

AFL_USE_ASAN=1

AFL_USE_MSAN=1

env 변수를 설정하는 컴파일 중에 활성화 할 수 있다.

 

AFL 실습

---

https://thfist-1071.tistory.com/312

AFL을 통한 unegg 실습