[논문 정리] The Art, Science, and Engineering of Fuzzing: A Survey

서론

AFL/AFL++를 쓰면서도 용어가 헷갈리고, 어떤 알고리즘으로 퍼징이 돌아가는지 정확히는 모르고있었다. 그래서 AFL++의 공식 Document를 읽어봤는데 개념에 대해 생략된 부분이 많이 있어 이해하기가 어려웠다.

 

따라서 퍼징에 대한 용어와 전반적인 원리 이해를 위해 해당 논문을 읽고 정리해보았다.

 

논문을 제대로 읽는건 처음이라 초반에 논문 선택에 어려움이 좀 있었지만 어쨋든 다 읽어서 기분이 좋다.

 

그럼 시작하겠다.

원문 : https://arxiv.org/abs/1812.00140

The Art, Science, and Engineering of Fuzzing: A Survey

 

Abstract

오늘날에는 여러 소프트웨어 테스트 기술이 많이 있지만, 퍼징은 그 개념적 단순함, 낮은 장벽의 배포, 그리고 실전성을 입증하는 다양한 증거들로 인해여전히 많은 인기를 누리고있다.

 

하지만 최근 몇 년 동안 급증한 퍼징에 대한 연구로 인해 퍼징에 대한 이해와 일관적인 시각을 얻기가 힘들다.

 

따라서 이 논문에서는 현대 퍼징의 계보와 함께 통합되고, 범용적인 퍼징 모델에 대해서 얘기한다.

퍼징이란?

1990년대에 소개된 퍼징이라는 기법은 소프트웨어의 정확성과 안정성을 테스트할 수 있는 가장 광범위하게 배포된 방법이다.

큰 틀에서 봤을 때, 퍼징은 문법적, 또는 의미적으로 정상적이지 않은 인풋을 생성해 반복적으로 프로그램을 실행시킨다.

 

어도비, 시스코, 구글, 마이크로소트와 같은 주요 기업들이 그들의 보안 개발 관행을 위해 이 퍼징을 채택하고있다.

용어 정리

• PUT(Program Under Test): 퍼징의 대상이 되는 프로그램
• Fuzzing: PUT가 기대하는 input space를 벗어난 입력값으로 실행하는 것
• Fuzz Testing: PUT가 정확성 정책을 위반하는지 확인하기 위해 테스트에 퍼징을 사용하는 것
• Fuzzer: PUT에 퍼징을 수행하는 프로그램
• Fuzz Campaign: 특정 정확성 정책을 바탕으로 PUT에 대해 퍼저를 실행하는 구체적인 과정
• Bug Oracle: 퍼저로 PUT를 실행했을 때 그 결과가 특정 정확성 정책을 위반했는지 결정하는 프로그램으로, 퍼저의 일부분일 수 있다.
• Fuzz configureation: 퍼즈 알고리즘의 파라미터, 설정값. 이 설정값은 퍼저의 동작방식에 따라 달라진다. Queue에 쌓인 시드, 실행 속도, 발견한 커버리지 정보같은 메타데이터, 스케줄링의 대상 등을 말한다.

퍼저의 종류

• Black-box fuzzer
  • 프로그램의 내부 로직은 무시하고 입력과 출력 행동만을 관찰하는 퍼저.
  • Peach, funfuzz 등 전통적인 퍼저들이 대부분 여기에 속하고, 프로그램을 직접 분석하는 대신 입력값의 구조적인 정보를 활용하여 더 의미있는 테스트 케이스를 생성한다.
• White-box fuzzer
  • 주로 DSE(Dynamic Symbolic Execution)이나 Concolic 테스팅 기법을 사용하여 프로그램을 탐색하는 퍼저.
  • 프로그램의 내부 세만틱을 추론할 수 있어 깊은 로직까지 파악할 수 있지만, 동적 instrumentation과 SMT solver로 인해 블랙박스보다 오버헤드가 높다.
• Grey-box fuzzer
  • 화이트박스처럼 전체 세만틱을 분석하지는 않지만, 정적 분석을 수행하거나 code coverage와 같은 동적 정보를 수집한다.
  • 완벽하지는 않아도 근사화된 정보를 활용하여 화이트박스보다 더 빠른 속도로 많은 입력을 테스트할 수 있다.
  • AFL이 대표적인 grey-box fuzzer이다.

DSE란?

프로그램의 변수를 10, 20같은 숫자가 아니라 x, y같은 기호로 변환해, 분기가 나올때마다 계산식을 업데이트하며 조건 공식을 구한다.

void function(int x) {
    int y = x + 10;
    if (y > 20) {           
        if (x < 15) {       
            // 버그 발생 지점
        }
    }
}

예를 들어, 위의 코드에서 첫 번째 if문을 만나면 내부적으로 $x + 10 > 20$ 이라는 조건을 기록하고 두 번째 if문을 만나면 앞의 조건에 $x < 15$ 라는 조건을 쌓는다.

 

두 번째 조건문을 통과하려면 $10 < x < 15$ 라는 공식을 해결하는 x를 찾아야하는데, 이때 SMT solver를 사용한다.

Concolic이란?

concrete와 symbolic의 합성어로, 실제 값(concrete)와 상징 값(symbolic) 분석을 동시에 진행하는 것을 의미한다.

 

상징적 분석만으로는 계산하기 복잡한 부분에서 실제 값을 참조하여 식을 단순화 하는 방법이다.

Fuzz Testing Algorithm

일반적인 퍼즈 테스팅 알고리즘

퍼즈 테스팅은 일반적으로 다음과 같은 절차로 진행되며, black-, grey-, white-box 퍼징에 대해서 모두 적용된다.

해당 알고리즘은 퍼징 구성들의 집합인 $C$와 제한 시간인 $t_{limit}$을 입력으로 받아 버거의 집합인 B를 출력한다.

Preprocess

사용자로부터 입력받은 퍼징 구성 집합을 입력값으로 받아 수정될 수 있는 퍼징 구성 집합을 반환한다.

여기서 퍼징 알고리즘에 따라 Preprocess 과정에서는 PUT에 instrumentation 코드를 삽입하거나 시드 파일의 실행 속도를 측정하는 동작을 수행할 수 있다.

Schedule

사용자로부터 입력받은 $C$와 $t_{limit}$, 그리고 현재 시간인 $t_{elapsed}$를 입력값으로 받아 현재 퍼징 반복에 사용될 퍼징 구성(conf)을 반환한다.

InputGen

conf을 입력값으로 받아 구체적인 test cases인 $tcs$를 반환한다.

해당 과정에서 tcs를 생성할 때 conf값을 사용하는 퍼저도 있고, 또는 모델이나 문법을 파라미터로 사용하는 퍼저도 있다.

InputEval

conf, tcs, 그리고 버그 오라클 $O_{bug}$를 입력값으로 받아 tcs를 입력값으로 PUT를 실행해 $O_{bug}$을 이용하여 정확성 정책을 위반하는지 확인한다.

이 때 반환값으로 찾아낸 버그 $B'$와 퍼징에 실행된 정보 execinfos를 반환한다.

ConfUpdate

$C$와 conf, execinfos를 입력값으로 받아 다음 실행에 사용될 업데이트된 $C$을 반환한다.

AFL와 같은 많은 grey-box 퍼저는 execinfos를 기반으로 한 퍼징 구성을 도출한다.

Continue

ConfUpdate에서 반환받은 $C$를 입력값으로 하여 새롭게 퍼징 반복을 해야하는지 나타내는 boolean값을 결과값으로 반환한다.

Preprocess

전처리 과정에서는 다음과 같은 작업을 수행한다.

• PUT에 instrument코드 삽입
• Seed selection
• Seed trimming
• 드라이버 프로그램을 생성

또한 InputGen 단계에서도 모델을 만들 때 사용되기도 한다.

Instrumentation

블랙박스 퍼저와는 다르게 그레이, 화이트박스 퍼저는 실행 피드백을 수집하기 위해
PUT에 instrument 코드를 삽입한다.

 

instrumentation는 static, dynamic 두 종류가 있다.

Static instrumentation

보통 컴파일 단계에서 수행되며 dynamic instrumentation보다 런타임 오버헤드가 적다.

만약 PUT가 외부 라이브러리를 사용한다면, 해당 라이브러리도 따로 instrument해야한다.

dynamic instrumenation

입력 평가(InputEval)단계에서 수행되며, 런타임중에 동적으로 컴파일 단계에서 수행되는 dynamic instrumentation보다 오버헤드는 심하지만 런타임중에 수행되어 관련된 라이브러리를 쉽게 instrument할 수 있다는 장점이 있다.

 

주요 dynamic instrumentation 도구:

• DynInst
• DynamoRIO
• Pin
• Valgrind
• QEMU (AFL이 사용함)

퍼저는 static, dynamic 둘 다 사용할 수 있다.

 

grey-box 퍼저는 실행 피드백을 인풋값으로 사용하여 더 나은 TCS를 생성하는데, AFL의 경우에는 그 방법으로 branch coverage를 사용한다.

 

이렇게 수집된 branch coverage 정보는 compact bit vector형태로 저장되는데, 서로 다른 경로가 같은 위치에 기록되는 path collisions가 발생할 수 있어 부정확해질 수 있다.

 

그래서 CollAFL는 path-sensitive hash function을 도입하여 이런 문제를 해결했다.

 

Race condition은 프로그램의 Non-deterministic한 동작에 의존하기 때문에 발생 빈도가 낮고, 일반적으로는 테스트하기 힘들다. → instrumentation을 사용하면 스레드의 실행순서를 정할 수 있어 해당 상황을 재현할 수 있다. 또한 스레드를 무작위로 스케줄링하는것이 race condition 버그를 찾는데 효과적이라는 연구 결과가 있다.

In-memory Fuzzing

GUI나 네트워크 프로그램같은 대규모 프로그램에 대해 퍼징할 때 프로세스를 매번 새로 생성하는건 오버헤드가 크다.

 

이에 대한 해결책중 하나는 프로그램이 실행되고 난 직후의 메모리 상태를 복사하는거다.

 

TCS에 대해서 퍼징을 진행하고, 끝나면 복사한 메모리를 다시 복구하여 실행 오버헤드 없이 다시 퍼징을 진행하는 방법으로 GRR이 이 방식을 쓴다.

 

AFL은 메모리를 복사하는 대신 fork server를 사용한다.

In-memory API Fuzzing

In-memory Fuzzing이 한 프로세스를 종료하고 다시 시작하는거라면 In-memory API Fuzzing은 프로세스를 종료하지 않고 루프 내에서 특정 함수만 반복해서 퍼징하는 기술이다.

 

AFL은 이를 persistent mode라고 부른다.

 

이 방식은 다음과 같은 기술적 한계가 있다.

• 재현 불가 문제
  • 대상 함수에 대한 유효한 호출 컨텍스트(calling context)를 구성하는 것이 항상 가능하지 않다.
  • 여러 차례의 함수 호출 과정에서 캡처되지 않은 부작용(전역 변수 상태 변경 등)이 누적될 수 있다.

In-memory API fuzzing은 함수를 시작하기 좋은 진입점을 찾아야하는데, 이는 굉장히 어렵다.

Seed Selection

퍼징 configuration중 하나인 시드(입력값)는 그 범위가 매우 넓고 많다. 그 시드들을 모두 테스트할 수 없으니 초기 시드 풀의 크기를 효율적으로 줄이는 문제가 Seed Selection Problem이다.

 

그 방법은 다음과 같다.

• Minset: 코드 커버리지를 최소화하는 최소한의 시드 집합을 찾는다.
  • 시드 $s_1$이 주소 ${10, 20}$를 커버하고, $s_2$가 주소 ${20, 30}$을 커버할 때, 주소 ${10, 20, 30}$을 모두 커버하는 $s_3$가 있다면 $s_3$를 사용하는 것이 실행 시간 측면에서 유리하다.
• Miller의 보고서에 따르면 code coverage가 1% 증가할때마다 버그를 찾을 확률이 0.92% 증가한다.

이 작업은 ConfUpdate 과정에서도 진행된다.

 

AFL의 경우 각 브랜치에 대해서 logarithmic counter로 branch coverage를 측정하여 Minset을 만드는데, 그 이유는 동일한 분기가 10번, 11번 실행될 경우 모두 다른 경우로 취급하면 시드가 충분히 줄어들지 않기 때문에, 유의미한 실행 패턴 변화만을 저장하기 위해 로그 카운터를 사용한다.

Seed Trimming

시드의 크기가 작을수록 메모리 소비가 적고 Throughput이 커진다. 따라서 퍼징 시작 전이나 과정 중에 시드 크기를 줄이는 시드 트리밍을 수행한다.

 

AFL의 경우 동일 커버리지를 유지하는 선에서 시드를 반복적으로 일부분 제거하는 방식을 사용한다.

 

하지만 시드 크기에 우선순위를 부여하는 알고리즘이 무작위로 시드를 선택하는것보다 오히려 unique bug를 발견할 가능성이 적다는 연구 결과도 있다.

Scheduling

스케줄링은 다음 퍼징에 사용할 퍼징 구성을 선택하는 과정이다. BFF나 AFLFast의 경우 스케줄링 알고리즘이 주된 성능 향상의 원인이다.

 

화이트박스 퍼저는 그레이, 블랙박스와 다르게 더 복잡한 설정이 필요하다.

The Fuzz Configuration Scheduling(FCS) Problem

스케줄링은 현재 정보를 분석해서 unique bug 발견을 극대화하거나, 커버리지를 최대화하는 Fuzz Configuration을 선택하는 방법이다.

 

모든 스케줄링 알고리즘은 탐색 (Exploration)과 활용 (Exploitation) 둘 중에 어느것에 비중을 둘지를 선택해야한다.

• 탐색: 더 나은 결정을 내리기 위해 각 구성에 대한 정확한 정보를 수집하는데 시간을 투자.
• 활용: 현재 가장 좋은 결과를 낼 수 있다고 믿어지는 퍼징 구성에 대해 퍼징을 수행.

해당 과정에서 사용되는 정보는 다음과 같다.

1. 현재 퍼징 구성 $C$
2. 현재 시간 $t_{elapsed}$
3. 제한 시간 $t_{limit}$

Schedule 단계에서는 어떤 Configuration을 선택할지 결정만 내리고, 실질적인 데이터는 Preprocess*와 *ConfUpdate 단계에서 이루어진다.

Black-box FCS Algorithms

블랙박스 퍼저는 오직 configuration별 퍼징 결과(발견된 크래시/버그 수, 소요 시간) 정보만 사용할 수 있다.

• Householder와 Foote는 블랙박스 변이 퍼징을 베르누이 실행의 반복이라고 보고 성공확률($\frac{\text{#unique crashes}}{\text{#runs}}$)이 높은 구성에 가중치를 두었다.
• Woo는 이를 더 발전시켰다.
  • 기존 베르누이 시행 모델에서 Weighted Coupon Collector’s Problem with Unkown Weights (WCCP/UW) 모델로 재정의했다.
    • WCCP/UW: 매 시도마다 성공 확률이 점점 낮아진다는 수학적 모델
  • 퍼징에 MAB 알고리즘을 적용시켰다
    • MAB: 탐색, 활용 중 어떤 것에 자원을 더 할당할건지 선택하는 머신러닝 모델
  • 퍼징 구성에 대한 성공 확률 시간에 따라 정규화해서, 더 빠른 구성에 우선순위를 부여함.
  • 퍼징 반복을 고정된 퍼징 수행 횟수로 보는게 아니라, 고정된 수행 시간으로 재정의하여 더 느린 퍼징 구성에 대한 우선순위를 낮췄다.

Grey-box FCS Algorithms

그레이박스 환경에서는 코드 커버리지와 같은 정보를 사용한다.

• AFL
  • AFL은 유전 알고리즘 (evolutionary algorithm, EA)를 도입한 퍼저이다.
  • 여러 개의 구성으로 이루어진 population을 유지하며 각 구성은 고유한 적합도 (fitness)를 가진다.
  • mutation이나 recombination과 같은 유전적 변형으로 적합한 구성을 선택한다.
  • 이렇게 선택된 자손 구성들은 부모보다 더 높은 적합도를 가질 가능성이 크며, 다음 퍼징 반복에 사용된다.

AFL은 다음 세 가지를 정의한다

• 적합도의 기준: 특정 control-flow edge를 실행하는 여러 구성 중, 가장 빠르고 크기가 작은 입력을 적합(favorite)하다고 판단한다.
• 구성 선택 방법: 퍼징 구성에 대해서 circular queue를 유지하며, 순차적으로 적합한 구성을 선택한다.
• 선택된 구성의 사용: 실행 속도가 빠르고 분기 커버리지가 높은 구성에 더 많은 실행 횟수를 할당한다.

AFLFast는 기존 스케줄링 방식을 모두 개선했다.

• AFLFast
  • 새로운 경로를 찾거나 드물게 실행되는 희귀 경로(Rare paths)를 탐색하는데 우선순위를 두도록 적합도 기준과 선택 알고리즘을 수정했다.
  • 선택된 구성을 몇 번이나 퍼징할지 결정하는 파워 스케줄 (power schedule) 개념을 도입했다.
    • 초기에는 실행 횟수를 적게해 탐색에 집중하고, 시간이 지날수록 유망한 구성을 지속적으로 퍼징하는 활용을 보장한다.
    • 동일한 경로를 실행하는 입력값이 많아질수록 해당 경로를 덜 실행하여, 자주 실행되지 않는 구성의 탐색을 촉진한다.

Input Generation

버그를 일으키는데 직접적으로 관련이 있는 부분으로, 퍼저에서 가장 영향력 있는 과정이다.

• Generation-based fuzzer (model-based)
  • PUT가 기대하는 입력을 설명하는 모델을 바탕으로 생성
• Mutation-based fuzzer (model-less)
  • 주어진 시드를 변형하여 생성

InputGen*은 *Preprocess 또는 ConfUpdate과정에서 얻은 퍼징 구성을 입력으로 받는다.

Model-based Fuzzers

Model-based 퍼저는 입력을 규정하는 문법 또는 실행 방식을 설명하는 모델을 사용하여 테스트 케이스를 생성한다.

이미 정의되어있는 모델을 사용하는 방식이 있으며, 이를 Predefined Model이라고 한다.

• 사용자가 직접 입력을 구성
  • Peach, PROTOS, Dharma 등은 사용자가 제공한 명세서를 입력으로 받음
  • Autodafé, Sulley, SPIKE, LibFuzzer 등은 분석가가 직접 입력 모델을 코드로 작성할 수 있는 API를 노출.
  • Tavor는 EBNF(Extended Backus-Naur Form)로 작성된 명세를 입력받아 해당 문법을 준수하는 테스트 케이스를 만듦.
• 네트워크 및 커널 등 특정 도메인 특화 모델
  • 네트워크 프로토콜: PROTOS, SNOOZE, KiF 등은 사용자로부터 프로토콜 사양을 입력받음
  • 커널 API: 시스템 콜의 인수 개수와 타입을 정의한 시스템 콜 템플릿을 모델로 사용
• Built-in Model
  • 퍼저 자체에 특정 언어나 문법에 대한 내용이 있음
  • 웹/브라우저: cross_fuzz와 DOMfuzz는 랜덤한 DOM 객체를 생성하고, jsfunfuzz는 자체 문법 모델을 바탕으로 구문론적으로 올바른 JavaScript 코드를 생성
  • 파일 형식: QuickFuzz는 파일 형식을 설명하는 기존의 Haskell 라이브러리를 활용
  • 프로토콜 전용: TLS-Attacker(TLS), llfuzzer(NFC) 등은 특정 프로토콜 모델을 내장하고있음.

문법적으로 맞는 테스트 케이스뿐만 아니라 의미적으로도 맞는 테스트케이스를 생성하는 다양한 퍼저들도 존재한다.

 

최근에는 직접 모델을 추론하는 방법도 관심을 받고있으며, 이를 Inferred Model이라고 한다.

instrumentation과 마찬가지로 모델 추론도 Preprocess와 ConfUpdate단계에서 이루어진다.

• 전처리 과정에서의 추론
  • TestMiner: PUT 내부의 리터럴(literals) 같은 데이터를 검색하여 적절한 입력을 예측.
  • IMF: 시스템 API 로그를 분석하여 커널 API 모델을 학습하고, 이를 바탕으로 API 호출 시퀀스를 포함하는 C 코드를 생성.
  • Skyfire: 시드와 문법을 바탕으로 확률적 문맥 민감 문법(probabilistic context-sensitive grammar)을 추론하여 의미론적으로 유효한 입력을 생성.
  • CodeAlchemist: 자바스크립트 코드를 code bricks로 분해한 뒤, 이들을 조립할 수 있는 제약 조건을 정적/동적 분석으로 계산하여 유효한 테스트 케이스를 생성.
  • Neural & Learn&Fuzz: 신경망을 사용하여 기존 테스트 파일로부터 모델을 학습하고 새로운 케이스를 생성.
• 구성 업데이트에서의 추론 (퍼징을 진행하면서 각 반복이 끝날 때마다 모델을 실시간으로 업데이트)
  • PULSAR: 캡처된 네트워크 패킷에서 프로토콜 모델을 자동으로 추론하며, 내부적으로 State machine을 구축하여 더 많은 상태를 커버하도록 입력을 생성.
  • Doupé et al.: I/O 동작을 관찰하여 웹 서비스의 상태 머신을 추론하고 웹 취약점을 스캔.
  • Ruiter et al.: TLS 프로토콜을 타겟으로 비슷한 상태 추론 기법을 적용
  • GLADE: I/O 샘플로부터 Context-free grammar을 합성하여 퍼징에 활용
  • go-fuzz: 시드 풀에 추가되는 각 시드마다 개별적인 모델을 구축하여 새로운 입력을 생성

위의 퍼저들이 테스트 케이스를 변형하는거라면, 프로그램 자체를 변형하는 퍼저도 있다. 이를 Encoder Model이라고 한다.

• MutaGen은 입력값이 아니라 데이터를 생성하는 인코딩 프로그램을 변이하여 내부적으로 변형된 테스트 케이스를 생성하도록 한다.
  • 인코더 프로그램의 Dynamic program slice를 계산하여 그 부분을 변형하여 실행.
  • 변형된 인코더는 정상적인 포맷에서 비정상적인 테스트 케이스를 생성하게 된다.

Model-less Fuzzers

전통적인 무작위 방식의 테스트 방법은 특정 분기분에서 효과적이지 못하다.

예를 들어 다음과 같은 조건문이 있다고 해보자

if (input == 42)

이 조건문을 무작위 테스트 케이스로 통과한다고 했을 때 인풋이 32비트 정수라면 통과할 확률이 $1/2^{32}$이다.

 

그렇기에 처음부터 정상적인 시드값에서 일부 값만 변형하여 테스트 케이스를 생성하는 방법을 사용한다.

그 값을 변형하는 방법에는 여러가지가 있다.

• Bit-flipping
  • 단순히 고정된 비트를 뒤집거나, 무작위 비트를 뒤집일수도 있다.
  • 랜덤하게 시드를 변형시키는데 사용자가 파라미터를 조절할 수 있으며, 이를 변이율 (mutation ratio)라고 부른다.
  • 변이율는 한 번의 입력 생성 과정에서 플리핑알 비트 위치의 수를 결정하는 값으로, N비트 크기의 시드에서 K개의 무작위 비트를 뒤집을 때 변이율은 $K/N$이다.

퍼징의 성능은 변이율에 민감하며, 모든 PUT에 적합한 변이율은 없다.

• Arithmetic Mutation
  • 선택한 바이트 시퀀스에 대해서 정수값이라고 간주하고 그 값에 대해서 간단한 산술연산을 수행한다.
  • 계산된 값은 그 선택한 바이트 시퀀스 자리로 대체된다.
  • 이 방법의 핵심은 변이의 효과를 작은 범위로 제한하는거다.

예를 들어, AFL의 경우 시드에서 4바이트의 값 $i$를 선택해 $i \pm r$ 을 수행한 뒤 기존 값을 대체한다.
여기서 보통 r의 값은 사용자가 정하거나 퍼저가 결정하는데, AFL에서는 기본 범위가 $0 \le r \lt 35$ 이다.

• Block-based Mutation
  • 시드 내의 연속된 바이트 시퀀스를 덩어리째 바꾸며, 6가지 방법이 있다.
    • insert: 무작위로 생성된 블록을 임의 위치에 끼워넣는다 (AFL)
    • delete: 시드에서 특정 블럭을 무작위로 제거 (AFL)
    • replace: 선택한 블록을 무작위 값으로 교체 (AFL)
    • permute: 블록들의 순서를 무작위로 섞음
    • resize: 시드 끝에 무작위 블록을 붙여 전체 길이를 늘림
    • splicing: 한 시드에서 가져온 블록을 다른 시드의 특정 부분에 넣거나 교체 (AFL)
• Dictionary-based Mutation
  • 프로그램이 처리할 때 특별한 의미를 가질 확률이 높은 미리 정의된 값을 변이에 활용한다.
    • -1, 0, 1 같은 정수값
    • 문자열 및 유니코드
    • %x, %s와 같은 포맷 스트링

화이트박스 환경에서도 Model-less와 Model-based를 모두 사용한다.

보통 Model-less는 DSE를 사용하고, Model-based는 문법과 같은 입력 모델을 활용한다.

Input Evaluation

입력 생성 후 해당 테스트 케이스에 대해 결과를 평가하는 과정은 input evaluation이다.

퍼저의 성능과 효과에 영향을 많이 미치며 많은 최적화와 설계 결정 (design decisions)이 있다.

Bug Oracles

전통적으로 segmentation fault와 같은 에러를 낼 때 버그로 간주한다.

 

운영체제가 자동으로 해당 오류를 잡기때문에 추가적인 instrumentation없어 편리하지만, 모든 메모리 취약점이 즉각적인 크래시로 이어지지는 않는다.

 

예를 들어, Stack buffer overflow가 일어나더라도 유효하지만 잘못된 주소로 포인터가 덮어씌워지면 프로그램은 오류 없이 잘못된 값을 반환할 수 있다.

 

이를 해결하기 위한 방법이 Sanitizer이다. 이는 비정상적인 동작을 감지하면 강제로 프로그램을 중단하여 감지한다.

메모리 안정성 오류는 크게 두 개로 나뉜다

• 공간적 오류 (Spatial)
  • 포인터가 의도된 객체 범위를 벗어나 역참조 될 때 OOB 발생.
• 시간적 오류 (Temporal) 포인터가 더 이상 유효하지 않은 시점에 액세스 될 때 Use-After-free(UAF) 발생

주요 탐지 도구로 ASan, MEDS, SoftBound/CETS 등이 있으며 ASan (Address Sanitizer)은 컴파일 시점에 instrumentation을 수행하는 메모리 오류 탐지기이다. shadow memory를 사용하여 한 바이트당 8개의 메모리 주소의 유효성을 확인할 수 있다.

Undefined Behavior

C와같은 언어에서는 프로그램이 어떻게 동작해야하는지 정의되지 않은 부분이 있다. 이를 UB라고 한다.

 

예를 들어 a + 1을 했을 때 a가 4바이트 정수 최댓값이고, 이에 대해 오버플로우시 wrap-around 된다고 명시하지 않는다면 컴파일러는 그냥 최적화하여 코드를 없앤다.

 

따라서 이런 오류를 잡아내는 탐지 도구가 몇 가지 있다.

• Memory Sanitizer (MSan): 초기화되지 않은 메모리 (uninitialized memory) 사용을 탐지하며, ASan처럼 shadow memory를 사용한다.
• Undefined Behavior Sanitizer (UBSan): 정렬되지 않은 포인터 사용, 0으로 나누기, 널 포인터 역참조, 정수 오버플로우 등을 탐지한다.
• Thread Sanitizer (TSan): Data race를 탐지한다. 두 개 이상의 스레드가 공유 메모리에 접근하고 그 중 하나가 write일 때 발생하는 non-deterministic한 버그를 잡아낸다.

Input Validation

XSS나 SQL injection같은 취약점은 단순히 크래시만으로 판단하기 어렵다. 따라서 다음과 같은 툴을 사용한다

• XSS 탐지 (KameleonFuzz)
  • 단순히 응답 값을 보는게 아니라, 실제 웹 브라우저로 입력을 파싱.
  • 추출된 DOM 트리를 분석하여 공격자가 의도한 패턴이 나타나는지 비교.
• SQL 인젝션 탐지 (µ4SQLi)
  • 웹, 앱과 DB 사이에서 통신을 가로채는 Database Proxy를 사용한다.
  • 입력값이 DB 쿼리 구조를 위험하게 변형시켰는지 확인.

Semantic Difference

프로그램이 정상적으로 종료되지만, 결과가 의도와 다른 경우를 말한다. 이 경우 Differential Testing 기법이 사용된다.

• 동일한 기능을 하는 서로 다른 프로그램들에 같은 입력값을 넣고 결과를 비교한다.
• 만약 프로그램끼리 결과가 다르다면 둘 중 하나 또는 둘 다 논리적인 버그가 있다고 판단한다.

Execution Optimization

퍼징은 프로그램을 수만, 수억 번 실행해야한다. 이 때 프로그램을 처음부터 로드하고 초기화하는건 시간이 많이 소요되기에 다양한 최적화를 사용한다

• Fork-server
  • AFL이 도입하였으며 프로그램을 실행해 초기화가 끝난 프로세스에서 새로운 입력값마다 fork로 실행하는 방법이다.
• In-memory Fuzzing
  • 아예 프로세스를 종료하지 않고 루프를 돌면서 특정 함수만 계속 호출하는 방식.
  • 하지만 이전 실행에서 초기화되지 않은 부분이 있는 State pollution 위험이 있다.
• 새로운 시스템 콜
  • 퍼징에 최적화된 새로운 시스템 콜로 오버헤드를 낮출 수도 있다.

Triage

crash를 유발하는 테스트 케이스를 분석하고 기록하는 과정이다.

deduplication, prioritization, minimization 세 과정으로 나뉜다.

• Deduplication
  • 크래시가 발생한 지점의 Call Stack이나 코드 경로를 비교하여 같은 원인이라면 하나로 묶는다
• Prioritization
  • 보안상 더 위험해 보이는 버그나, 더 자주 발생하는 버그에 우선순위를 부여한다.
  • 마이크로소프트의 !exploitable 랭킹 시스템의 심각도를 기준으로 우선순위를 부여.
• Minimization
  • 퍼징이 만든 입력값에서 불필요한 부분을 trimming해 파일 크기 줄인다.

Configuration Updating

현재 실행 결과로 다음 퍼징에 사용할 퍼징 집합 $C$를 수정한다.

 

블랙박스 퍼징의 경우 내부 구조를 모르기때문에 보통 $C$를 수정하지 않지만, 그레이/화이트박스 퍼저는 결과를 바탕으로 새로운 시드를 추가하거나 삭제한다.

Evolutionary Algorithm

Fitness Function으로 시드를 선별하여 다음 인풋으로 넣는다.

 

퍼징 효율을 높히기 위해 AFL은 단순히 분기를 지났는지만 보는게 아니라, 그 분기를 볓 번 통과했는지를 기록해 시드 선택에 사용한다.

 

또한 4바이트 정수값의 if문은 무작위 변위로 통과하기 힘든데, 이를 1바이트찍 여러 분기로 쪼개 하나씩 통과할때마다 시드에 넣기도 한다.

 

또 프로그램의 control-flow graph (CFG)를 분석해 도달하기 힘든 Basic block을 실행하는 시드에 가중치를 준다. 반대로 에러 핸들링에 잡히는 시드에는 음수 가중치를 준다.

Maintaing a Minset

새로운 퍼징 구성을 추가하는 과정에서 queue에 너무 많은 시드가 생길 수 있다. Preprocess 단계에서 한 것처럼 ConfUpdate단계에서도 동일하게 진행한다.

 

AFL의 경우 Minset을 유지하기 위해 시드를 삭제하기보다는 특정 edge를 가장 빠르고 작게 실행하는 시드를 Favorable로 표시해 그렇지 않은 시드보다 더 많이 시도한다.

Conclusion

이 논문의 목표는 현대 퍼징 문헌에 대한 포괄적이고 일관된 시각을 정립하는 것이었다. 이를 위해 먼저 현재 사용되는 다양한 형태의 퍼징을 설명하기 위해 범용 모델 퍼저 (general-purpose model fuzzer)를 제시했다. 그 후 퍼저들의 분류 체계를 설명했으며, 모델 퍼저의 각 단계를 탐구하며 관련 설계 결정을 논의하는 동시에 커뮤니티 전반이 이룬 수많은 성과를 보여주었다.

 

우리의 연구가 향후 연구들, 특히 용어 사용과 퍼징 알고리즘의 제시에 있어 더 많은 통일성을 가져오는 데 도움이 되기를 희망한다.

 

후기

첫 정독에는 이해가 안되서 두 세번은 더 읽은거같다. 물론 내가 잘 못 이해한 부분도 있겠지만 어느정도는 퍼징에 대한 기본적인 동작 원리에 대해 좀 흐름이 읽히는거같다. AFL가 코드 커버리지를 어떻게 사용하는지도 알았고 스케줄링, 인풋 생성에 어떤 원리가 적용되었는지 알 수 있어서 좋았다.