주요 내용으로 건너뛰기

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 3

앞의 포스팅 : [논문리뷰] Fuzzing: Art, Science, and Engineering - Part 2 

Preprocess

어떤 퍼저들은 첫 번째 fuzz iteration을 수행하기 전에 fuzz configuration의 초기 설정을 수정하기도 한다. 이러한 전처리 작업(pre-processing)은 보통 PUT을 Instrumentation 기법을 사용하기 위해서, 또는 Seed Selection이나Seed trimming을 위해서 사용된다. 

1. Instrumentation

블랙박스 퍼저는 논외로 하고, 화이트 또는 그레이 박스 퍼저들은 PUT이 fuzz run 된 Evaluation 결과에 대한 정보를 피드백하여 instrumentation 하거나, 실행 중인 메모리 정보들을 이용해 퍼징 할 수 있다. Process trace 나 System call trace를 사용하여 PUT 내부의 정보를 얻는 방법도 있지만, instrumentation 기법을 사용하는 이유는 그중 보다 유의미한 정보만을 취득하기 위해 사용된다. 이 기법은 정적(static) 또는 동적(dynamic)으로 구분되는데, 정적 분석은 PUT을 수행하기 전의 상태를 토대로 파악하는 것이고 동적 분석은 PUT이 수행되는 동안의 정보를 수집한다. 이 때문에 정적분 석보다 동적 분석이 훨씬 더 많은 runtime overhead를 유발한다. 정적 분석은 컴파일 타임에 소스코드 또는 중간 언어 코드를 대상으로 이루어지며, 만약 PUT이 의존하는 라이브러리가 있는 경우 이를 적절히 분리시켜서 확인하여야 한다. source-based instrumentation 뿐만 아니라 binary-level static instrumentation을 수행하는 도구도 있다. 동적 분석은 오버헤드가 크긴 하지만, dynamically linked library에 대하여 더욱 폭넓게 조사하기 용이하다는 장점이 있다. 잘 알려진 dynamic instrumentation tool로는 DynInst, DynamoRIO, Pin, Valgrind, QEMU 등이 있다. 사실 엄밀히 따지면 dynamic instrumentation은 실행 과정에서 발생하므로 InputEvaluation 단계에 속하는 것이 더 정확하나, 독자의 편의를 위하여 본 단락에서 정적 분석과 병행하여 설명하였다. 
퍼저가 사용할 수 있는 instrumentation 기법은 꼭 한 종류뿐만은 아니다. 예를 들어 AFL은 static instrumentation을 소스코드 레벨에서 적용하기 위해 특수한 컴파일러를 사용하며, 바이너리 레벨에서 dynamic instrumentation을 하기 위해 QEMU를 이용한다. AFL이 dynamic instrumentation을 할 때에는 PUT 자체의 실행 가능한 코드 정보를 사용하거나(이것이 기본 설정임) 또는 AFL_INST-LIBS옵션을 사용하면 PUT과 기타 다른 외부 라이브러리들을 같이 instrument 한다. 이 경우 사실상 마주하는 모든 코드에 대해 instrumentation을 하는 것인데, code와 library에 대한 조금 더 포괄적인 coverage 정보를 얻을 수 있다.  

1) Execution Feedback

Grey box 퍼저는 통상적으로 execution feedback을 input으로 하여 test case를 진보시킨다. AFL과 그 계통을 따르는 퍼저들은 PUT의 모든 branch instruction에 대하여 instrument를 수행하여 branch coverage를 계산한다. 하지만 이 branch coverage information 값들은 bit vector 형식으로 저장되기 때문에 path 충돌(collision)을 야기할 수 있다. CollAFL과 같은 도구는 path-sensitive 한 hash fuction을 통해 이러한 문제에 대한 대안을 제시하였다. 반면 LibFuzzer나 Syzkaller와 같은 퍼저들은 node coverage를 사용하기도 하고, Honggfuzz는 사용자로 하여금 어떤 execution feedback을 사용할 것인지 선택할 수 있도록 한다. 

2) In-Memory Fuzzing

규모가 큰 프로그램에 대하여 퍼징을 수행할 때, 각각의 fuzz iteration 마다 매번 프로세스를 재수행하는 방식으로 점검하게 된다면 오버헤드가 굉장히 부담되게 된다(특히 GUI 등). 대신 PUT에서 퍼징에 필요한 부분만을 추출하여 테스트할 수 있다면 좋을 것이다. 이를 위해서 GUI 등의 기타 환경들이 모두 초기화된 후에 PUT의 상태를 스냅샷(snapshot)으로 저장해 두고, 새로운 테스트 케이스를 수행할 때에는 종전의 메모리 스냅샷을 복원한 후 즉시 이용할 수 있도록 하는 것이다. 이와 유사한 방식은 네트워크 애플리케이션이 서버와 클라이언트 사이에서 과중한 통신이 수행되는 상황에서도 활용할 수 있다. 이를 In-memory fuzzing이라고 정의한다. 예를 들어 GRR(https://github.com/trailofbits/grr)은 bytes 형식 입력이 수행되기 전에 스냅숏을 저장함으로써 불필요한 초기 수행 코드를 건너뛸 수 있도록 하고 있다. AFL 역시 fork server라는 개념을 채택하였는데 process의 start up 코드를 건너뛰기 위함이다. 
어떤 퍼저들은 각 fuzz iteration에서 PUT의 상태를 복원시키지는 않는 방식으로 in-memory fuzzing을 수행하기도 한다. 이러한 방식을 in-memory API fuzzing이라고 정의하였다. 예를 들어 AFL의 persistent mode는 프로세스를 재수행시키지 않으면서도 in-memory에서 API 퍼징을 반복적으로 수행한다. 단 이러한 경우 동일한 execution에서 한 함수가 다수 호출되는 잠재적인 부작용이 있을 수 있는데, AFL은 이를 감수한다. 

in-memory API fuzzing의 유용성에도 불구하고, 이 방식은 종종 부정확한 결과를 가져다주기도 한다. 발견된 버그(또는 crash)를 reproduce 하지 못하는 경우가 있을 수 있다는 것이다. 이는 첫째로 해당 함수가 호출되는 문맥을 정확히 재연하는 것이 불가능할 수 있기 때문이며 두 번째 이유로는 동시다발적으로 호출되는 함수들을 모두 포착할 수 없으므로 발생하는 부작용 때문이다. 이 때문에 in-memory API fuzzing의 정확성은 각 함수의 entry point에 따라 결정되는데 이러한 것을 발견해내는 것은 굉장히 challenging 한 문제이다. 

3) Thread Scheduling 

경쟁조건(Race condition) 버그는 드물게 발생하는 비결정론적 행동에 기반하기 때문에 이를 유발하기가 어렵다. 하지만 instrumentation 기법을 사용하면 각 스레드들이 어떻게 스케쥴링되는지를 명시적으로 제어함으로써 서로 다른 비결정론적 프로그램 동작을 재현시킬 수 있다. [Effective Random Testing of Concurrent Programs] 논문에 따르면 스레드를 임의로 스케쥴링하는 방법조차도 Race condition bug를 유발하는데 효과적일 수 있다는 사실을 보였다. 

2. Seed Selection

퍼저가 받아들이는 fuzz configuration에 따라 퍼징 알고리즘 동작이 규정되는 상황을 생각해보자. 불행히도 mutation기반 퍼저들의 seed와 같이, fuzz config 중 일부 파라미터들은 그 입력값의 범위가 지나치게 넓다. 예를 들어 MP3 형식의 파일을 읽어 들이는 플레이어 프로그램을 퍼징 한다고 생각해보자. 이때 ‘유효한’ MP3 파일로 간주되는 범위는 한계가 없이 넓다. 그렇다면 보다 근본적인 질문을 갖게 된다. 도대체 어떤 seed를 사용하여 퍼징을 해야 한단 말인가? 이러한 문제를 일컬어 seed selection problem이라고 한다. 
이러한 문제를 다룬 [Optimizing Seed Selection for Fuzzing] 등의 논문을 참고하면 좋으며, 결국 coverage metric를 최대화하는 seed의 최소 집합을 찾는 것으로 귀결되며 이러한 작업을 ‘minset 찾기’라고 부를 수 있다. Charlie Miller는 2008년 CanSecWest에서 [Fuzz by Number: More Data about Fuzzing than You Ever Wanted to Know]라는 주제로 발표하며 1%의 code coverage 가 증가했을 때 버그 발견율은 92% 상승했다는 결과를 보였다. 
본 단계는 ConfUpdate의 한 단계로 포함될 수도 있다. 
퍼저들은 다양한 coverage metric을 선별하는 데에는 실용적인 다양한 방법이 존재한다. AFL의 minset은 branch coverage이고, Honggfuzz는 수행된 명령어, 분기, unique block 등의 숫자를 기준으로 coverage를 계산하곤 하는데 이를 통해 DoS 취약점이나 성능 이슈를 발견하기 쉽도록 한다. 

3. Seed Trimming

Seed의 크기가 작으면 작을수록 소모하는 메모리 용량도 적고 처리효율도 좋다. 그러므로 어떤 퍼저들은 퍼징을 시작하기에 앞서 먼저 seed의 크기를 줄이려는 작업을 수행하기도 하는데 이를 seed trimming이라고 한다. Seed trimming은 Preprocess에 앞서 수행되거나 ConfUpdate의 일부분으로 수행되곤 한다. 대표적으로 AFL은 code coverage instrumentation을 사용하여, 동일한 coverage인 경우에 대해 시드의 일부를 반복적으로 제거한다. 한편, [Optimizing Seed Selection for Fuzzing] 논문에 따르면 크기가 더 작은 seed에 더 높은 우선순위를 부여하여 선택하는 것이 무작위로 seed를 선택하는 것에 비해 unique bug를 더욱 적게 찾는다는 것을 발견하여 해당 size minset algorithm이 문제점을 지적하였다. 

4. Preparing a Driver Application

PUT을 직접적으로 퍼징 하기가 곤란한 경우, 퍼징을 위한 중간 드라이버 프로그램을 준비하는 것이 합리적이다. 이는 fuzzing campaign이 시작되는 시점에 단 한번 수행하면 되는 것인데 그럼에도 불구하고 실무적으로 굉장히 많은 많은 수작업이 요구될 수 있다. 예를 들어 퍼징 하고자 하는 대상이 라이브러리인 경우, 해당 라이브러리 내부의 함수를 호출하는 드라이버 프로그램을 만들어야 한다. 이와 유사하게, 커널 퍼징 도구들은 userland app들을 퍼징함으로써 커널을 점검한다. 또한 IoTFuzzer는 해당 스마트폰 애플리케이션을 드라이버로 하여 IoT Device를 퍼징 한다. 

Scheduling

퍼징에서 스케쥴링이란, 다음 fuzz run을 위해 fuzz configuration을 선택하는 것을 의미한다. 각 configuration 들은 퍼저의 종류에 따라 결정되는데, 아주 단순한 퍼 저인 zzuf를 예로 들자면, 스케쥴링이 별로 복잡할 것도 없다. 단지 PUT과 다른 매개변수를 위한 기본 값만을 지정해주는 단 하나의 config 만 필요하기 때문에 별로 추가적인 결정을 내릴 것이 없기 때문이다. 하지만 BFF나 AFLFast 등 보다 진보적인 방식의 퍼저들은 스케쥴링 알고리즘에 혁신을 가함으로써 놀라운 성공을 이루어냈다. 

1. The Fuzz Configuration Scheduling (FCS) Problem

Fuzz configuration에 대하여 현재 이용 가능한 정보들을 분석하여 가장 유리한 결과를 이루어낼 가능성이 높은 것을 선택하는 것이 스케쥴링의 목적이다. 예를 들어 unique bugs의 숫자를 가장 크게 하는 방법이라던지, 생성된 입력값 집합의 coverage를 최대화하는 것 등이다. 

근본적으로 모든 스케줄 알고리즘은 exploration과 exploitation이라는 측면에서 상충되는 문제를 겪게 된다. explore는 보다 향후의 결정을 위해 보다 정확한 정보를 수집하는데 시간을 할애하는 반면 exploit은 현재 가장 유리한 결과물을 얻는 데에 최선을 다하는 것이다. [Scheduling Black-box Mutational Fuzzing] 논문에서는 이러한 점을 일명 Fuzz Configuration Scheduling(FCS) 문제라고 정의하였다. 

2. Black-box FCS Algorithms

블랙박스 퍼징의 상황에서 FCS 알고리즘이 사용할 수 있는 유일한 정보는 특정 configuration을 넣었을 때에 대한 결괏값뿐이다. 이와 관련한 최초의 연구는 [Probability-Based Parameter Selection for Black-Box Fuzz Testing.]이고 이후 [Scheduling Black-box Mutational Fuzzing.]에서 보다 수학적인 모델링을 통하여 BFF 퍼저의 unique bugs 발견 횟수를 1.5배 향상시켰다.

3. Grey-box FCS Algorithms

그레이 박스 퍼징에서, FCS 알고리즘은 fuzz configuration의 coverage 범위 등과 같은 정보의 집합을 이용한다. AFL 이 이 분야에서 선두주자라고 할 수 있는데, 유전 알고리즘을 사용하여 fitness(적당한) 값을 유지하는 config을 구성한다. Evolutionary algorithm을 통해 fit config를 선택하고 이를 genetic 변환(mutation, recombination을통해 변이 된 자손들을 만들어서 new config로 사용)한다. 이렇게 진행했을 경우 생성된 config가 향후에도 더욱 fit 할 가능성이 높다는 것을 가정으로 한다.  

EA의 관점에서 FCS를 적용한다면, 먼저는 config를 fit 하게 무엇인지를 알아야 하고, 그 config를 어떻게 선택할 것인지, 그리고 그렇게 선택된 config를 어떻게 사용할 것인지를 명확히 해야 한다. AFL은 이를 통칭 "favorite"라는 용어로 fit을 정의하는데 대략 가장 fastest 하면서도 smallest 한 config를 채택한다. AFL은 config queue를 원형으로 구성하여 다음 fit focnfig를 찾도록 하는데, 한번 선택되면 일정한 횟수만큼 수행되도록 한다. FCS의 관점에서 보면 fast config를 채택한 것은 black-box 방식과 유사하다고 볼 수 있다. 

2016년 [Coverage-based Greybox Fuzzing as Markov Chain] 논문에서 발표된 일명 AFLFast는 "favorite"의 판정 기준에 least config와 least exercised path를 포함시키고, next fit을 고를 때에도 단순 Round-robin이 아닌 우선순위 기반의 fit 선정을 하는 방식을 사용하였다. 또한 power schedule이라는 개념을 도입하였는데 이는 "energy"라는 이름의 값을 설정하여 exploration과 exploitation을 조정한 것이다. 이러한 변화의 결과는 상당히 유의미하였는데, 24시간 동안 수행했을 때 AFL 이 기존 찾지 못했던 3개의 버그를 AFLFast는 더 찾을 수 있었으며, 동일한 버그에 대해서는 AFl보다 7배 빠른 시간에 찾아내었다. 

이를 토대로 2017년에는 [Directed Greybox Fuzzing.]라는 논문을 통해 AFLGo라는 또 하나의 변형 기법을 제안하였는데, AFLFast의 Priority 값을 변경함으로써 특정 프로그램에 대한 퍼징 결과를 더욱 향상했다. 또한 QTEP은 정적 분석을 사용하여 바이너리의 어느 부분이 더 결함이 있는지 파악하고, 이를 포괄하는 Config의 priority를 결정한다. 

4. White-box FCS Algorithms

화이트 박스 퍼저를 스케쥴링하는 것은 심볼릭 익스큐션 등 굉장히 복잡한 설정이 필요하므로 본 논문에서는 자세한 설명을 생략하며, 보다 자세한 내용은 [Billions and Billions of Constraints: Whitebox Fuzz Testing in Production]를 참고하기 바란다. 



To be continued .. 

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 1

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 2

[논문리뷰] Fuzzing: Art, Science, and Engineering - Part 3

.

.


Software Security Engineer

CPUU 님의 창작활동을 응원하고 싶으세요?

댓글

SNS 계정으로 간편하게 로그인하고 댓글을 남겨주세요.