[PAPER REVIEW] Reinforcement Learning-based Hierarchical SeedScheduling for Greybox Fuzzing

BACKGROUND

1. Greybox Fuzzing

Fig. 1: Overview of greybox fuzzing

greybox fuzzing에서 새로운 입력은 mutation이나 crossover/splice를 통해 생성된다. (Seed Mutation)

생성된 입력은 fitness function에 의해 선택된다. (Seed Selection) 선택된 입력은 이후 mutation에서 사용하기 위해 seed pool에 넣는다. 이때 제한된 processing 능력 때문에 seed pool에 있는 아주 적은 시드만 선택되어서 다음 입력 mutation에 사용되기 위해 스케줄된다. 하나의 퍼저는 한 번에 하나의 시드만 스케줄링 할 수 있다.

fitness function은 AFL에서 가장 많이 사용되는 것이 edge coverage이다. (새로운 branch에 도달한 입력을 seed pool에 넣음) 대부분의 퍼저는 새로운 커버리지를 fitness function으로 사용하는 coverage-guided 퍼저이다. 이때 fitness function에서 중요한 것은 waypoint를 보존하는 것이다.

 

Greybox Fuzzing Algorithm

알고리즘 1

알고리즘 1은 greybox fuzzing 과정에 해당한다. 퍼징할 프로그램과 초기 seed 집합이 주어졌을 때 퍼징은 round라고 부르는 반복문의 나열로 이루어진다.

1. 각 round에서는 스케줄링 전략에 따라 다음에 퍼징할 seed를 선택한다.
2. 스케줄된 seed는 해당 round에서 몇 개의 새로운 테스트케이스를 생성하고자 하는지에 따라 power 양을 할당한다.
3. 이후 seed를 mutation하여 새로운 테스트케이스가 생성되고 새롭게 생성된 입력으로 타겟 프로그램을 실행한다. blackbox fuzzing과 whitebox fuzzing과는 다르게 퍼저는 런타임 특성을 알기 위해 계측기를 사용하며, 생성된 테스트케이스의 품질을 측정하기 위해 fitness 함수를 사용한다.
4. 만약 생성된 테스트케이스의 품질이 좋다면 seed pool에 새로운 seed로 저장된다.

 

greybox fuzzing 효율성과 효과성 결정 요인

1. 테스트케이스 측정
2. 퍼징에서 fitness 함수는 퍼저가 발견할 수 있는 프로그램 속성 종류를 결정할 수 있다. 퍼징 연구에서 다양한 fitness 함수가 제안되어왔지만 여전히 코드 커버리지가 fitness 함수로 가장 많이 사용된다. AFL은 테스트케이스의 edge coverage를 측정하는데, edge의 hash 값을 인덱스로 사용하여 edge를 hit count에 접근하는 global map을 유지함으로써 해당 map에서 몇 번 hit했는지 기록한다. 테스트케이스로 실행한 후 global map은 해당 edge을 업데이트하고, 새로운 edge가 발견되거나 한 edge의 hit count 증가 시 해당 테스트케이스가 새로운 시드로 선택된다. 그러나 edge의 순서를 고려하지 않아 새로운 edge의 해시가 기존의 edge의 해시와 충돌하는 경우 interesting한 시드를 놓칠 수 있는 한계가 있다.
3. 시드 스케줄링 전략
4. 처리 능력이 제한적이라면 시드에 우선순위를 지정하는 스케줄링이 필요하다. AFL에서는 높은 퍼징 처리량을 달성하기 위해 크기가 작고 실행 시간이 짧은 시드를 선호하고, 최소한의 시드 세트를 유지한다. AFLfast는 greybox fuzzing을 markov chain으로 모델화하고 거의 실행되지 않은 경로를 실행하는 시드에 우선순위를 준다. libfuzzer는 퍼징 과정에서 나중에 생성된 시드에 우선순위를 준다. Entropic은 더 높은 정보를 얻은 시드에 우선순위를 둔다.
5. 시드 변형 전략
6. 시드 변형 전략은 새로운 테스트케이스의 새로운 커버리지를 얻을 수 있고 새로운 시드로 선택될 가능성을 결정한다. AFL과 libfuzzer는 랜덤 mutation과 crossover를 사용한다. 최근 연구는 data-flow 분석을 기반으로 어떻게 입력의 바이트를 변형해야 하는지 식별하거나 directed searching을 사용하거나 변형 전략을 학습하는 방식으로 가능성을 개선하였다.
7. 퍼징 처리량
8. 퍼징 처리량은 퍼저가 새로운 커버리지를 얼마나 빨리 발견할 수 있는지에 대한 것이다. AFL은 forkserver와 persistent mode를 사용하여 오버헤드를 줄여서 처리량을 개선했다. FirmAFL은 증강 에뮬레이션을 사용하여 펌웨어 퍼징 속도를 높였다. 처리량과 앞선 세 가지 요소(커버리지 측정, 스케줄링 알고리즘, 변이 전략) 간 trade-off를 적절히 해야 하는데, 처리량을 신경쓰지 않으면 앞선 세 가지 요인을 개선해도 퍼징 성능이 저하될 수 있다.

 

2. Multi-Armed Bandit(MAB) Model

Multi-Armed Bandit(MAB) 모델은 불확실한 상황에서 시간이 지남에 따라 최적의 자원 할당 정책을 학습하는 알고리즘이다. 용어 “bandit”은 무작위 보상을 제공하는 슬롯머신으로부터 가장 높은 보상을 얻기 위해 슬롯머신을 플레이하는 최적의 전략을 찾는 도박 시나리오에서 유래하였다.

multi-armed bandit 문제는 튜플 $(A, R)$로 정의된다. 이때 A는 알려진 $k$개의 팔의 집합이고, $R_a(r) = P[r|a]$로 알려지지 않았지만 고정된 보상에 대한 확률 분포를 의미한다. 매 시간 스텝 $t$마다 arm $a_t$를 선택하고, reward $r_t = ~ R^{a_t}$를 관찰한다. 목표는 reward $\sum^T_{t=1}r_t$를 최대화하는 것이다. 초기에 어떤 arm에서 최대의 reward가 나올지에 대한 정보가 없어서 랜덤으로 시도하고 reward를 관찰한다. 시간이 지날수록 더 많은 정보를 갖게 되지만, reward가 최대일 때 arm을 exploitation하는 것과 더 가치 있는 것을 놓치지 않기 위해 다른 arm에서의 기대 reward에 대한 정보를 더 얻기 위한 exploration 사이 trade-off를 직면한다.

시드 스케줄링은 시드를 arm으로 간주하는 것으로 multi-armed bandit 문제로 모델화할 수 있지만, 퍼저가 이 모델로부터 코드 커버리지를 최대화하는 등의 이익을 얻으려면 seed 스케줄링에서 reward를 신중히 고려해야 한다.

 

3. multi-level coverage metrics

Sensitivity of Coverage Metrics (커버리지 지표의 민감성)

mutation-based greybox fuzzingg에서 퍼징은 초기 seed 집합으로 시작된다. 기존 seed를 변형하면서 더 많은 seed가 seed pool에 추가된다. 만약 버그 트리거한 테스트케이스를 chain의 end로 이 테스트케이스에 대한 초기 시드를 start로 간주한다면, internal 시드는 퍼저가 점차 버그를 찾기 위한 탐색 공간을 줄일 수 있는 waypoint로 간주할 수 있다.

1. 커버리지 지표가 seed 체인 만드는데 중요한 역할

퍼저에서 커버리지 지표는 이러한 chain을 만드는데 중요한 역할을 한다. 만약 버그 트리거하는 테스트케이스 도달 전 chain이 끝난다면 해당 버그는 퍼저에서 발견되지 못한다. Wang et al.은 seed chain에서 중요한 waypoint를 보존하는데 커버리지 지표의 sensitivity로 모델을 공식화했다.

예)미로 게임( maze game )→ 기호 실행의 프로그램 상태 탐색 능력을 입증하는데 많이 사용됨

Listing 1: A Simple Maze Game

• 플레이어는 각 step에서 위치를 결정하는 $(x, y)$ 쌍을 통해 미로를 탐색한다.
• 게임에서 승리하려면 퍼저는 시작 위치에서 충돌 위치까지 올바른 경로를 찾기 위해 가능한 한 많은 $(x, y)$ 쌍 나열을 시도해야 한다. 이때 edge coverage를 fitness 함수로 사용하면 모든 $(x, y)$ 쌍과 관련된 branch가 4개뿐이고 각 branch(분기)는 간단한 조건을 검사하기 때문이다. 입력이 ‘u’, ‘d’, ‘l’, ‘r’, ‘a’가 있을 때 퍼저가 프로그램 상태를 목표를 향해 도달할 수 있는 입력을 생성할 수 있어도 이러한 입력은 새로운 edge coverage를 제공하지 않아서 새 시드로 선택되지 못한다. → 결과적으로 퍼저가 edge coverage를 이용해서 게임에서 승리하기 어려움
• 퍼저가 $*(maze + y + x)$를 통해 다른 메모리에 접근하는 등 다른 x와 y 조합을 사용하면 더 쉽게 승리 지점에 도달 가능

1. 체인에서 seed 쌍 사이 간격에 커버리지 지표가 영향을 줌
   • 커버리지 지표의 민감성은 새롭게 생성되는 테스트케이스가 새 시드로 저장되는지에 대해 결정 가능Böhme et al. - 필요한 power에 따라 이웃 시드를 발견하는 최소 노력을 모델링하여, 해당 모델을 통해 민감한 커버리지 지표가 power를 적게 사용할 수 있음
   • 퍼저에서 블록 커버리지보다 edge 커버리지를 사용하는 것이 새로운 시드 발견하기 더 좋고, 32비트 정수보다 8비트 정수의 매칭을 찾는 것이 더 쉬움
   • 민감한 커버리지 지표일수록 버그 발견 가능성이 항상 높다고 할 수는 없음
   • 한 연구에 의하면 퍼저가 메모리 접근 커버리지를 통해 미로 게임에서 이길 수 있었지만, DARPA CGC 챌린지에 대해서는 제대로 수행하지 못함 → 민감한 커버리지 지표일수록 더 큰 seed pool을 만들어서 시드 스케줄링에서 다음 퍼징할 시드를 선택하는데 많은 시드 후보를 검토했기 때문. seed pool이 클수록 시드 탐색 어려움이 증가함

⇒ 민감한 커버리지 지표일수록 퍼저가 프로그램의 깊은 상태를 탐색하는 능력을 더 높일 수 있다.

---

MOTIVATION

1. 시드 폭발 문제

중간 waypoint를 보존하는 것을 커버리지 지표의 민감성으로 공식화하였는데, 더 민감한 지표는 코드 커버리지와 같은 더 많은 프로그램 상태로 이어질 수 있기 때문이다. 그러나 평가 시 민감한 커버리지 지표가 더 많은 시드를 선택하어 시드 폭발을 일으킬 수 있는 결과가 나왔다. 이는 퍼저의 스케줄링 능력을 초과하여 많은 시드가 스케줄링되지 않거나 충분한 시간이나 power 없이 스케줄링되었기 때문이다.

→ 이러한 시드 폭발 문제를 해결하기 위해 본 논문에서는 계층적 스케줄러를 도입하였다.

 

2. multi-armed bandit(MAB) 문제

multi-armed bandit 모델에서는 스케줄러가 탐색과 익스플로잇 사이 균형을 맞춘다. branch와 같이 더 민감한 커버리지에서 익스플로잇은 매직 넘버 체크와 같은 어려운 branch를 해결하는 데 초점을 두고, 탐색은 서로 다른 함수 전체를 고려할 것이다. 이때 하나의 커버리지 지표가 다른 커버리지 지표보다 더 민감하다면, 해당 민감한 커버리지 지표를 모든 중간 waypoint를 저장하는 데 사용하고, 덜 민감한 커버리지 지표를 대표성이 있는 노드에 시드를 클러스터링하고 노드 레벨에서 스케줄링하도록 하여 더 좋은 탐색이 이루어지도록 한다.

→ 퍼저를 multi-armed bandit(MAB) 문제로 모델화하고, seed pool을 multi-level tree로 구성한다. leaf node는 real seed이며, internal node는 덜 민감한 커버리지 지표에 해당한다. 노드가 leaf에 가까울수록 커버리지 측정 측면에서 더 민감함을 나타낸다. MAB 알고리즘을 탐색과 익스플로잇 사이 균형을 맞추는 데 사용한다.

 

multi-level coverage metrics 통한 seed clustering

• 다양한 시드보다 비슷한 시드에서 얻는 정보가 더 적다. 커버리지 지표가 더 세분화된 커버리지 정보(예. edge)를 측정할수록 서로 다른 시드 간 coarse-grained 다양성(예. block)을 희미하게 만들 수 있다. 시드 간 차이가 작아지게 하고, 세분화된 지표가 감지할 수 있는 시드 간의 잠재적으로 더 큰 차이를 인식하지 못하게 된다. edge coverage를 측정하는 지표는 두 시드가 서로 다른 기본 블록을 실행하는지, 아니면 동일한 기본 블록이지만 서로 다른 edge를 통해 실행되는지를 인식하지 못한다.
• ⇒ 민감한 커버리지 지표 사용 시 시드 유사성과 다양성에 더 집중해야 한다.
• 클러스터링은 비슷한 객체를 그룹화하는데 사용되는 기술이다. 같은 클러스터 내 객체는 다른 클러스터에 있는 객체보다 더 비슷하다.
• ⇒ 시드 클러스터링 제안

---

DESIGN

multi-level coverage metric 통한 seed clustering

Fig. 2: A multi-level coverage metric

• 같은 클러스터 내 시드는 비슷하고, 다른 클러스터에 있는 시드는 더 다양하다. 스케줄러가 시드의 유사성과 다양성을 사용하도록 함.
• 세분화된 지표에서 선택된 시드를 클러스터링하는데 coarse-grained coverage 사용 제안
  • 동일한 클러스터 내 시드는 동일한 coarse-grained coverage를 갖는다.
  • 2개 이상의 클러스터링을 사용 → 최상위에는 더 많은 추상화를, 하위는 더 많은 충실도를 제공할 수 있음
  ⇒ multi-level coverage metric
• multi-level coverage metric
  • top level에서는 function coverage 사용하고, mid-level에서는 edge coverage를, leaf-level에서는 비교하는 operand 사이 거리 root node는 스케줄러에서만 사용하는 가상 노드에 해당

 

테스트케이스가 새로운 커버리지(feature)를 얻을 수 있다고 평가되면 새로운 시드로 선택되고 알고리즘 2에 따라 적합한 클러스터에 넣어진다. (9~20라인) 이후 루트 노드에서 시드 클러스터링을 시작하고 child node에서 새로운 시드와 동일한 기존의 feature $M_F$ node를 찾는다. (10라인) 동일한 feature 갖는 노드가 없다면 새 $M_F$ 노드를 생성한 후, 동일한 edge coverage를 가진 $M_E$ 노드에 새 시드를 배치한다. 마지막으로 $M_E$ 노드의 하위 $M_D$ 노드를 선택하여 distance coverage에 따라 새 시드를 저장한다.

multi-level coverage metric 정의
커버리지 $C^* : (P X I) \space \rightarrow \space <\Gamma^_1, ... , \Gamma^_n>$은 커버리지 지표 $<C_1, ..., C_n>$의 나열로 구성된다. 커버리지 지표는 프로그램 $P \in \mathcal{P}$ 의 실행을 입력 $I \in \mathcal{I}$로 측정하고, 측정 $<M_1, ..., M_n>$ 의 나열을 만들어낸다.

multi-level coverage 지표는 여러 지표를 서로 다른 레벨에서 결합하여 시드를 평가한다.

• lower-level 커버리지 측정은 시드 간 사소한 차이를 보존함으로써 체인 안에 더 많은 시드가 포함되도록 한다. → 버그 트리거하는 테스트케이스 찾기 위한 검색 공간 줄일 수 있음
• 스케줄러는 상위 레벨 측정을 사용하면 시드 간 주요 차이를 식별할 수 있다.
• $n = 1$ 이면 단일 수준 커버리지 메트릭으로 축소됨

예시

• 프로그램 $P$를 퍼징한다고 할 때 효과적인 다단계 커버리지 지표 $C^n \sim\space<C_1, ..., C_n>$ 를 개발한다고 해보자.
• 증분 시드 클러스터링를 통해 계층적 시드 스케줄링 알고리즘에 의해 모든 시드는 계층적 트리에 들어간다. 상위 레벨의 노드가 하위 레벨의 여러 자식 노드를 가질 때에만 스케줄링이 가능하다. 시드 평가 시 동일한 커버리지 측정 $M_i$에서 이를 따르는 측정이 $M_{i+1}, ... , M_n$ 이라 할 때 이들이 동일한 경우를 제외한다.
• 덜 민감한 지표에서 생성된 측정값은 더 민감한 지표에서의 측정값보다 먼저 시드를 클러스터링해야 하는 것이 기본 원칙

$C_i$ 가 $C_j$보다 “더 민감하다” 를 만족하는 조건 정의
($C_i \succ_s C_j$) $C_i, C_j$: 커버리지 지표 $(i) \space \forall P \in \mathcal{P}, \forall I_1, I_2 \in \mathcal{I}, C_i(P, I_1) = C_i(P, I_2) \rightarrow C_j(P, I_1) = C_j(P, I_2), and \\ (ii) \space \exists P \in \mathcal{P}, \exists I_1,I_2 \in \mathcal{I}, C_j(P,I_1) = C_j(P,I_2) \space \wedge C_i(P,I_1) \ne C_i(P,I_2)$

동일한 $M_F$ 클러스터 내 시드는 동일한 함수 커버리지를 갖는다. $M_E$가 $M_F$보다 더 민감할 때, 시드는 서로 다른 edge 커버리지를 갖고 서로 다른 클러스터로 분류된다.

$M_F$보다 $M_E$에 시드를 우선적으로 클러스터링하도록 설정했다면, edge 커버리지가 동일한 시드는 함수 커버리지도 동일해야 하므로 다른 하위 $M_F$ 클러스터에 넣는 것이 불가능하다.

• $\succ_s$ 는 partial 순서이기 때문에 두 지표가 비교 가능하지 않는 것이 가능하다.
  • 예. 상위 레벨 지표 $C_F$가 함수 커버리지, 중간 레벨 지표 $C_E$가 edge 커버리지라 할 때, 함수는 실행 시 특성을 사용하는 런타임 특성이고, edge 커버리지는 AFL, LIBFUZZER에서 많이 사용된다. 하위 레벨 지표는 더 민감한 지표로, 하위 레벨 지표를 distance 지표 $C_D$라 가정할 때 distance 지표는 프로그램 실행의 conditional jump(예. edge)를 추적하고 두 조건의 인자에서 hamming 거리를 커버리지 feature로 계산한다. 조건부 점프에서 관찰된 새로운 거리를 새로운 커버리지로 취급한다.
  • $memory \space access$ 지표 $C_A$도 평가하는데, 이 지표는 모든 메모리 읽기와 쓰기를 추적하고 주소 접근을 추적하여 새로운 메모리 접근에 대한 인덱스를 새로운 커버리지로 간주한다.
• → 문제 해결 위해 만약 두 비교할 수 없는 커버리지 지표가 주어졌으면, 더 적은 시드를 선택하는 지표에 시드를 클러스터하도록 정의했다.

 

hierarchical seed scheduling

multi-level coverage metric을 사용해서 생성된 계층적 클러스터링을 통해 시드를 스케줄링하는 방법

1. 시드 트리에서의 스케줄링

multi-level coverage metric $C^* \sim \space <C_1, ..., C_n>$는 커버리지 지표들($M_i$)와 시드를 트리로 구성한다. 이때 각 depth $i \in \{1, ..., n\}$ 에서 노드는 클러스터 $M_i$를 나타낸다. $i+1$에 위치한 자식 노드는 하위 클러스터 $M_{i+1}$를 나타낸다. layer 0(depth 0)의 노드는 가상 노드이다.

시드 스케줄 시 스케줄러는 root node부터 leaf node로의 경로를 탐색한다.

Exploration vs. Exploitation → multi-armed bandit(MAB) 모델링하여 UCB1 알고리즘 사용

• 시드 스케줄러는 탐색(새로운 시드를 만드는 것)과 익스플로잇(더 interesting한 시드를 만날 때까지 퍼징을 계속하는 것) 사이 trade-off에 직면한다.
• 계층적 클러스터에 시드를 구성할 때 시드 탐색과 익스플로잇 관점에서 유연하게 제어 가능하다.
• 퍼저는 하나의 클러스터에서 동일한 함수를 커버하는 시드를 첫 번째 레이어에 구성하고, 두 번째 레이어에는 서로 다른 edge를 갖는 시드로 하위 클러스터를 구성할 수 있다.
• MAB 문제로 퍼징 과정을 모델링하여 MAB 알고리즘을 사용해서 탐색과 익스플로잇 사이 균형을 유지한다. 이때, 여러 MAB 알고리즘 중에서 arm에서의 탐색과 익스플로잇 사이 trade-off를 최적화한 UCB1 알고리즘을 MAB 알고리즘으로 사용하여 시드를 스케줄링하였다.
• SelectNextSeedToFuzz() root node를 시작으로 스케줄링 알고리즘은 높은 score를 가진 자식 노드를 선택한다. score는 커버리지 측정 기반으로 계산한다.
• leaf node는 실제 시드로, 이 노드는 모두 커버리지가 동일하기 때문에 round robin 방식으로 스케줄링
• 각 퍼징 round가 끝나면, 스케줄된 경로의 노드는 보상을 받는다. 이 방법으로 잘 수행한 노드의 점수는 증가시킨다.
• 초기 MAB 문제는 고정된 arm 수를 사용하지만, 노드 수는 시드가 생성됨에 따라 계속 증가하기 때문에 이를 그대로 적용하지 못한다. → 이 문제 해결 위해 노드 점수가 희귀한 것, 즉 다른 노드보다 점수가 다른 것을 다룬다.
• Ecofuzz에서 AMAB 문제에서의 민감한 지표에서 시드 폭발 문제를 EXP3 알고리즘 적용하여 해결 → UCB1 보다는 성능이 좋지 않았음

 

2. seed scoring

exploitation - 최근 잘 수행된 시드는 높은 점수를 줌

exploration - 점수 시스템은 드물게 탐색된 시드의 불확실성을 고려

UCB1 알고리즘 확장해서 exploitation과 exploration 사이 균형 유지

점수를 낼 때 시드가 3가지 측면 고려

(1) 희소성

(2) 해당 시드로부터 새로운 시드를 발견할 수 있는 용이성

(3) 불확실성

시드에게 보상 주는 값 계산 방법

• 한 번의 퍼징이 끝난 후 보상

rareness와 추정한 퍼징 성능 고려한 노드 점수

---

IMPLEMENTATION

base fuzzer: AFL++

64-bit machine with 48 cores (2 Intel(R) Xeon(R) Platinum 8260 @2.40GHz), 375GB of RAM, and Ubuntu 18.04

---

EVALUATION

DARPA CGC 챌린지→ AFL, AFLFAST와 비교했을 때 20% 더 많은 버그를 탐지하고, 180개 중 83개에서 더 높은 커버리지를 달성

Fuzzbench에서 AFL++ (Qemu)와 비교했을 때 20개의 프로젝트 중 10개가 더 높은 커버리지 달성

---

RELATED WORK

arm에서의 exploitation과 exploration 사이 trade-off를 최적화하기 위한 알고리즘

• Upper Confidence Bound(UCB) 알고리즘: bandit 알고리즘 계열로, 각 arm의 true reward를 추정하기 위해 confident interval을 구성하고 매 시간 가장 높은 UCB를 가진 arm을 선택한다. 높은 평균 reward를 가진 arm을 선택하면서 추정한 reward가 폭넓은 confidence interval을 갖기 때문에 더 적은 arm을 탐색할 수 있다.
• UCB1: 각 arm에서 초기 reward를 가져온 후, 매 시간마다 $Q(a) + C * \sqrt{log(N)\over n_a}$ 를 최대화하는 arm $a$를 선택한다. ($Q(a)$ : arm $a$로부터 얻을 수 있는 평균 reward, $C$ : predefined 상수로 $\sqrt{2}$로 주로 설정, $N$ : 선택 수, $n_a$ : arm $a$가 선택된 횟수

Ecofuzz

• adversarial multi-armed bandit(AMAB) 모델을 사용하여 시드 스케줄링 진행
• 더 민감한 커버리지 지표에서의 시드 폭발 문제 해결하지 못