[논문 리뷰] The Art, Science, and Engineering of Fuzzing: A Survey
원문 : https://arxiv.org/abs/1812.00140
[목차]
3. Preprocess
어떤 퍼저는 첫 번째 fuzz iteration 전에 fuzz configuration의 초기 set을 수정한다. 이러한 preprocess(전처리)는 보통 PUT를 instrument(:추론)하고, 잠재적으로 중복될 수 있는 configuration을 제거하고, 시드를 트리밍(trim)하고, driver application을 생성하는데 사용된다. 5.1.1절에서 자세히 다루겠지만, PREPROCESS는 향후 입력 생성(INPUTGEN)을 위한 모델을 준비하는데 사용될 수도 있다.
3.1 Instrumentation
블랙 박스 퍼저와 달리 그레이 박스나 화이트 박스 퍼저는 INPUTEVAL 단계에서 fuzz run을 할 때 execution feedback을 수집하거나 런타임에 메모리를 퍼징하도록 PUT를 instrument 할 수 있다. 수집되는 정보의 양에 따라 블랙 박스, 화이트 박스, 그레이 박스로 정의된다. PUT 내부 정보를 수집하는 다른 방법들(예: processor traces나 system call usage)이 있긴 하지만, instrumentation은 가장 가치 있는 피드백을 수집하는 방법을 의미한다.
프로그램 instrumentation은 정적(static)이거나 동적(dynamic)일 수 있다. 정적의 경우 PUT 실행 전에 수행하고(PREPROCESS), 동적의 경우 실제로는 PUT 실행 중(INPUTEVAL)에 수행한다. 그러나 독자의 편의를 위해 이 섹션(PREPROCESS)에서 동정과 정적 instrumentation을 모두 요약한다.
[실제로 dynamic instrumentation은 INPUTEVAL에서 이루어짐.]
- static instrument
static instrument은 종종 소스 코드나 중간 코드(intermediate code)를 컴파일할 때 수행된다. 실행시간 전에 instrument 하면, 동적 instrument보다 런타임(runtime) 오버헤드가 적다. 만약 PUT가 라이브러리를 의존하는 경우, 보통 동일한 instrumentation으로 다시 컴파일해서 별도로 instrument 한다. 소스 코드 기반 instrumentation 외에도, 바이너리 수준의 동적 instrumentation(i.e., binary rewriting) 도구를 개발한 연구들도 있다: <A platform for secure static binary instrumentation>, <PEBIL: Efficient static binary instrumentation for linux>, <Vulcan: Binary transformation in a distributed environment>.
- dynamic instrument
동적의 경우 정적 보다 오버헤드가 심하다는 단점이 있지만, instrumentation이 런타임 도중에 이뤄지기 때문에 동적으로 링크되는 라이브러리를 쉽게 instrument 할 수 있다는 장점이 있다. 여기 잘 알려진 몇 개의 동적 instrumentation 도구들을 소개한다 : DynInst, DynamoRIO, Pin, Valgrind, and QEMU.
한 퍼저가 한 가지 이상의 instrumentation 방법을 사용할 수도 있다. 예를 들어 AFL은 전용(:modified) 컴파일러를 이용해 소스 코드 수준의 정적 instrument를 하기도 하고, QEMU의 도움으로 바이너리 수준의 동적 instrument를 하기도 한다. 동적 instrumentation 방식을 사용하는 경우, AFL은 (1) 실행 가능한 코드를 PUT 내부에서 instrument 하거나(기본 설정) (2) 실행 가능한 코드를 PUT나 외부 라이브러리에서 instrument 한다(AFL_INST_LIBS 옵션). 두 번째 옵션은 실행되는(:encountered) 코드를 모두 instrument 하는 것인데, 외부 라이브러리의 코드에 대한 커버리지 정보도 포함할 수 있어서, 더 완전한 커버리지 정보를 제공한다. 이는 AFL이 외부 라이브러리 함수에서 추가적인 경로를 퍼징하도록 도와준다.
3.1.1 Execution Feedback
그레이 박스 퍼저는 보통 테스트 케이스를 evolve하기 위한 입력으로 execution feedback 정보를 사용한다.
AFL과 그 하위(AFL 계보 퍼저들)의 퍼저는 PUT의 모든 branch instruction을 instrument해서 branch coverage를 계산한다. 그러나 branch coverage 정보를 bit vector에 저장하므로 충돌쌍(path collision)이 발생할 수 있다. CollAFL은 이러한 문제를 해결하기 위해 path-sensitive hash function를 도입했다. 반면 LibFuzzer와 Syzkaller는 execution feedback을 위해 node coverage를 사용한다. Hongfuzz는 어떤 execution feedback을 사용할지 사용자가 선택할 수 있게 하였다.
3.1.2 In-Memory Fuzzing
크기가 큰 프로그램을 테스트할 때, 프로그램 실행 시 발생하는 오버헤드를 줄이기 위해 각 fuzz iteration 과정에서 프로세스를 다시 생성하지 않고, PUT의 일부분만 퍼징하는 것이 좋다.
- in-memory [link]
GUI처럼 복잡한 프로그램은 프로세스를 생성하고 입력을 전달하기까지 수 초가 소요된다. 이런 프로그램을 퍼징하기 위해 GUI 초기화가 완료된 후에 메모리 스냅샷(snapshot)을 찍는 접근 방식이 존재한다. 새로운 테스트 케이스를 퍼징하기 위해, 테스트 케이스를 메모리에 집접 쓰고 실행하기 전에, 메모리 스냅샷을 복원할 수 있다. 클라이언트-서버간의 상호 작용이 많은 네트워크 응용프로그램을 퍼징할 때도 이런 접근 방식을 사용할 수 있다.
예를 들어, GRR은 입력 바이트를 로딩하기 전에 스냅샷을 찍는다. 그러면 불필요한 초기 실행 코드를 건너뛸 수 있다. AFL은 초기 실행의 코스트를 줄이기 위해 fork server를 사용한다. fork server는 모든 fuzz iteration에 대해 새로운 프로세스를 fork 한다.
- in-memory API fuzzing
Libfuzzer나 AFL 같은 퍼저들은 각 iteration 이후 PUT의 상태를 복구하지 않으면서도 in-memory 퍼징을 수행한다. 예를 들어 AFL은 persistent mode라는 옵션을 이용해, 프로세스를 재시작하지 않고 loop에서 in-memory API fuzzing을 반복 수행한다. 이 경우, 동일한 실행에서 여러 번 호출되는 함수에서 발생 가능한 side effect를 찾지 못할 수도 있지만, AFL은 이를 감안한다.
이러한 효율성에도 불구하고, in-memory API fuzzing은 버그나 크래시가 reproducing이 안 되는 부정확한 결과를 초래하기도 한다. 그 이유는 다음과 같다.
(1) 타겟 함수를 정확하게 호출하는 calling context를 재현하지 못할 수 있다.
(2) 함수를 여러 번 호출하는 과정에서 캡쳐하지 못한 side-effect가 있을 수 있다.
in-memory API fuzzing은 entry point 함수를 정확하게 찾는 것이 중요한데, 이는 아주 어려운(:challenging) 일이다.
3.1.3 Thread Scheduling
race condition bug는 드물게 발생하는 비결정론적인 동작에 의해 발생하기 때문에 트리거 하기 어렵다. 그러나 instrumentation은 스레드가 스케줄 되는 방식을 제어해서 다른 비결정론적인 프로그램을 트리거 할 수 있다.
[이런 방식은 아래 연구들을 참고하라: <Effective random testing of concurrent programs>, <Race directed random testing of concurrent program>, <Randomized active atomicity violation detection in concurrent programs>, <A randomized dynamic program analysis technique for detecting real deadlocks>, <Detecting atomic-set serializability violations in multithreaded programs through active randomized testing>, <MagicFuzzer: Scalable deadlock detection for large-scale applications>, <Synthesizing racy tests>]
반대로 <Effective random testing of concurrent programs>에서는 스레드를 랜덤하게 스케줄링하는 것이 race condition bug를 찾는데 효과적일 수 있다는 사실을 보였다.
3.2 Seed Selection
2절에서 전술하였듯이 퍼저는 퍼징 알고리즘의 동작을 제어하는 fuzz configuration set을 전달받는다. 불행하게도 일부 fuzz configuration의 파라미터들은 그 값의 범위(:domain)가 크다. (예: 변이 기반 퍼저의 시드)
예를 들어, MP3 파일을 입력으로 받는 MP3 player를 퍼징한다고 가정해보자. 생성 가능한 MP3 파일은 무한하기 때문에 다음과 같은 질문을 떠올릴 수 있다: 퍼징에 어떤 시드를 사용해야 할까?
초기 시드 풀의 크기를 줄이는 문제를 seed selection problem이라고 한다.
seed selection 문제를 해결하는 몇 가지 접근 방식과 도구들이 있다. 일반적인 접근 방식은 node coverage 같은 coverage metric를 최대화 할 수 있는 가장 작은 seed set을 찾는 것이다. 이런 과정을 minset 계산이라고 한다.
예를 들어, 현재 configuration set C가 시드 s1, s2로 구성되어 있고, 이를 실행하면 PUT이 다음과 같은 주소를 커버한다고 가정하자: {s1 → {10, 20} , s2 → {20, 30}}. 그리고 s1과 s2만큼 빠르게 실행되는 세 번째 시드 s3가 {10, 20, 30}을 커버한다고 가정하면, s1과 s2 대신 s3를 fuzz하는게 합리적이다. (직관적으로, 실행 시간의 비용은 절반인데 더 많은 프로그램 logic을 테스트하기 때문) 코드 커버리지가 1% 증가하면 버그 발견율이 92% 증가했다는 Miller의 연구 <Fuzz by number: More data about fuzzing than you ever wanted to know>가 이런 직관을 뒷받침해 준다.
7.2절에서 다루겠지만 이 단계는 CONFUPDATE에 포함될 수 있다. 이는 캠페인 전체에 걸쳐 시드 풀에 새 시드를 추가할 수 있는 퍼저에게 유용하다.
퍼저는 실제로 다양한 coverage metric를 사용한다.
예를 들어, AFL의 minset은 각 branch에 지수적(:logarithm)인 카운터가 있는 branch coverage를 기반으로 한다. 그 이유는 branch 카운터가 몇 배 차이로 다를 때만 차이가 있다고 인지하도록 설정한 것이다.
[AFL whitepaper의 "2) Detecting new behaviors"에서 확인할 수 있다.]
Hongfuzz는 실행된 instruction, 실행된 branch, unique basic block의 수를 기반으로 커버리지를 계산한다. 이 metric은 퍼저가 minset에 대해 더 긴 실행을 추가할 수 이어서 DoS 취약점이나 성능 관련 문제를 탐지하는 데 도움이 될 수 있다.
3.3 Seed Trimming
시드가 작을수록 메모리는 더 적게 소비하고, 더 높은 throughput을 유도한다. 따라서 어떤 퍼저는 퍼징을 하기 전에 먼저 시드의 크기를 줄인다. 이런 기술을 seed trimming이라고 한다. 시드 트리밍은 PREPROCESS에서 메인 fuzzing loop을 수행하기 전에 수행되거나, CONFUPDATE의 일부분으로 수행된다.
AFL은 어떤 시드가 동일한 커버리지를 달성하도록 유지하면서, 그 시드의 일부분을 제거하는 코드 커버리지 instrumentation을 사용한다.
한편 Rebert의 연구에 따르면, 크기가 작은 시드에 더 높은 우선순위를 부여하는 minset 알고리즘은 랜덤하게 시드를 선택하는 경우보다 unique 한 버그가 더 적게 발견될 수도 있다고 한다. MoonShine은 Linux system call handler 퍼징의 특정 사례를 위해 syzkaller를 확장하여 시드 크기를 줄이면서 정적 분석을 사용하여 감지된 호출 간의 dependency를 유지한다.
3.4 Preparing a Driver Application
PUT를 직접 퍼징하는게 어려울 경우 퍼징을 위한 driver를 만들 수 있다. 이 과정은 fuzz campaign을 시작할 때 한 번만 수행되지만, 실무에서 대부분 꽤 귀찮은(:manual) 작업이다.
예를 들어 타겟이 라이브러리인 경우, 라이브러리의 함수들을 호출하는 driver 프로그램을 준비해야 한다. 이와 유사하게, 커널 퍼저는 커널을 테스트하기 위해 유저 영역의 어플리케이션(userland application)을 퍼징할 수 있다. IoTFuzzer는 퍼징을 위해 driver가 해당 스마트폰 어플리케이션과 통신할 수 있도록 준비한다.
Uploaded by Notion2Tistory v1.1.0