기본적인 fuzz testing algorithm 이해하기 + AFLFast

AFL을 어떻게 사용하는지, 어떤 특징이 있는지는 알겠지만 자세히 이해하고 싶어졌다. 

하지만 검색 실력의 부족인지.. AFL의 동작을 세세히 분석한 것은 없었고, fuzz testing algorithm을 분석 정리한 포스트를 찾았다.

이를 읽으면서 AFL을 사용한 것을 함께 떠올렸다. 

 

< 틀린 부분이 있다면 알려주세요 >

들어가기

./afl-fuzz -i input -o output -- objdump -x @@

이 명령어로 이해해보겠다. 

 

용어 정리

PUT : test할 프로그램 -> objdump

fuzz input : PUT가 예상하지 못할 input

fuzzing : fuzz input을 사용해 PUT(Program Under Test)를 실행하는 것. crash같은 보안 관련 버그 탐색 목적

fuzz testing : fuzzing 기술을 사용한 소프트웨어 검사 기술. fuzzing 기술을 사용해 PUT가 보안 정책에 어긋나는지 검사한다. -> objdump라는 소프트웨어를 검사하고싶은 거니까 AFL 퍼저를 사용하는 것은 fuzz testing을 하기 위함이라고 이해할 수 있다.

fuzzer : PUT에 fuzz testing을 수행하는 프로그램

fuzz campaign : 특정 보안 정책을 갖는 PUT에 대한 fuzzer의 특정 실행(specific execution)

bug oracle : 제공된 PUT의 실행이 특정 보안 정책에 어긋나는지 구분하는 프로그램

fuzz algorithm : fuzzer에 구현된 알고리즘. PUT의 몇 가지 파라미터에 의존하며 그 파라미터에 대한 설정을 fuzz configuration이라고 부른다.

fuzz configuration : fuzz algorithm을 제어하는 파라미터 값들로 이루어져 있다. fuzz configuration은 fuzz algorithm 종류에 따라 달라진다. fuzz configuration을 fuzzing이 진행됨에 따라 발전시키는 fuzzer도 있고, fuzz configuration을 처음부터 끝까지 동일한 내용으로 유지하는 fuzzer도 있다. 

seed : test case를 만들기 위해 사용되는 PUT의 input -> -i input이라고 이해했다. input 디렉터리 안의 모든 파일들..

coverage-guided fuzzer : coverage라는 실행 정보를 저장해 각 configuration의 발전을 기록한다. AFL이 coverage-guided fuzzer이죠..

 

---

fuzz testing algorithm

fuzz testing의 보편적인 알고리즘으로 이해하면 되겠다.

black, grey, white box의 기초가 되는 알고리즘

1. Preprocess

2. Schedule

3. InputGen

4. InputEval

5. ConfUpdate

6. Continue

 

2, 3, 4, 5, 6 함수를 loop로 실행한다.

fuzz iteration : 한 번의 loop 실행

fuzz run : InputEval 단계에서 실제로 PUT가 실행되는 것

 

 

fuzz configuration -> input 디렉터리

↓

[Preprocess] fuzz configuration(input/) 수정후 반환. PUT(objdump)에 instrumentation code 삽입..

↓

수정된 fuzz configuration(수정된 input/) + current time, timeout

↓

[Schedule] 현재 iteration에 적용시킬 configuration 선택(수정된 input에서 선택)

↓

수정된 후 선택된 configuration

↓

[InputGen] fuzz configuration을 인풋으로 받아 testcase 생성

↓

testcase(tcs) + fuzz configuration, bug oracle

↓

[InputEval] testcase가 PUT의 보안 정책에 어긋나는 행동을 유발하는지 검사(무작위로 변조된 input이 objdump의 보안 정책에 어긋나는 행동을 유발하는지 검사)

↓

set of bugs(InputEval에서 반환은 되지만 ConfUpdate의 인풋으로 사용되지는 않는다.), execinfo(fuzz run에 대한 정보) + set of fuzz configuration, current configuration

↓

[ConfUpdate] set of fuzz configuration을 수정한다. grey-box fuzzer들은 execinfo를 통해 set of fuzz configuration의 개수를 줄이는 작업을 한다. -> preprocess와 schedule을 통해 선택된 fuzz configuration을 평가하고 더 적합한 conf를 만들기 위한 작업

↓

set of fuzz configuration

↓

[Continue] 다음 iteration의 실행여부 결정

↓

loop 반복

---

Preprocess

1. PUT에 대한 instrumentation 적용
2. 쓸모없는 configuration 제거
3. seed trimming
   1. 크기가 작은 seed일수록 메모리 소모량이 낮고, 높은 throughput을 갖는다.
   2. AFL의 경우 seed가 동일한 coverage를 갖는 범위에서 서서히 seed의 일부를 삭제한다. 
4. driver app 생성

Scheduling

• 다음 iteration에 적용할 fuzz configuration을 정하는 것을 의미한다.
• 퍼저의 종류에 따라 configuration의 내용이 달라진다. 
• 하나의 configuration만을 사용해서 이 단계가 없는 퍼저도 있다.
  • 하지만 AFLFast처럼 잘 짜여진 스케줄링으로 성공한 사례도 있다. 
• AFL은 Greybox FCS algorithm 중 진화 알고리즘을 사용한다. 
  • 각 configuration마다 fitness라는 값을 갖고, 진화 알고리즘이 적절한 configuration을 mutation, recombination해서 자식을 만든다. 
  • 이렇게 만들어진 자식들 중 부모보다 fit한 놈이 있을거란 가정하에 진행된다. 
  • AFL은 configuration을 원형 큐로 관리하며 다음으로 fit한 configuration을 가져와서 고정된 횟수만큼 실행한다. 
• AFLFast는 아래 3가지 아이디어를 통해 만들어졌다. 
  • 선호하는 input
    • 특정 control flow edge를 수행하는 configuration 중 선택을 가장 적게 받은 configuration을 선호해 exploration 증가
    • 만약 선택받은 횟수가 같은 configuration들이 있다면 가장 적게 실행된 path를 갖는 configuration을 선호해 희귀 path 탐색에 대한 exploration 증가
  • round robin 선택 방식을 버리고 fit configuration의 우선순위를 사용해 다음 configuration 선택
  • power schedule에 의해 정해진 횟수만큼 선택된 configuration을 실행
    • 처음엔 작은 값으로 시작해서 점점 빠르고 큰 폭으로 상승하는 energy값 사용
    • path를 탐색하는 input의 수를 energy 값으로 정규화해서 적게 퍼징된 configuration이 선택되도록 장려

InputGen

• 퍼저는 input generation에 사용되는 기술로 크게 generation-base, mutation-base 두 개로 나눌 수 있다.
  • generation-based : PUT의 expected input에 대한 model을 통해 input 생성.. model based fuzzer라고 부른다.
  • mutation-based : 제공된 seed를 mutate시켜 input 생성. seed가 expected input space를 대표할 수 없기 때문에 model-less fuzzer라고 부른다. -> AFL이 mutational하다는 특징이 있으니까 mutation-based fuzzer이겟죠?
    • mutation-based model에서 seed를 mutate하는 방법 : bit flipping, arithmetic mutation, block-based mutation, dictionary-based mutation

InputEval

• input을 생성한뒤 퍼저는 그 인풋으로 PUT를 실행하고, 실행 결과를 두고 어떤 행동을 할 지 결정하는 과정을 InputEval이라고 한다. 

 

---

궁금한 점

fuzz configuration이 input/가 맞는지..

preprocess 단계에서 fuzz configuration을 수정하고 반환한 conf와 InputGen에서 fuzz configuration을 토대로 만들어진 testcase와의 차이는 뭔지... 같다고 봐도 무방한가??

 

---

출처

https://hackyboiz.github.io/2021/08/08/fabu1ous/fuzz-1/

hackyboiz

https://hackyboiz.github.io/2021/10/03/fabu1ous/fuzz-2/

hackyboiz

https://hackyboiz.github.io/2021/10/24/fabu1ous/fuzz-3/

hackyboiz

https://hackyboiz.github.io/2022/01/16/fabu1ous/fuzz-4/

hackyboiz