[Paper Reading] “SegFuzz: Segmentizing Thread Interleaving to Discover Kernel Concurrency Bugs through Fuzzing”

서론

이번 글에서는 스레드 인터리빙을 커버리지 지표로 다룬 SegFuzz를 읽어보겠습니다. KAIST와 서울대가 IEEE S&P 2023에 발표한 논문입니다.

원문: [SegFuzz: Segmentizing Thread Interleaving to Discover Kernel Concurrency Bugs through Fuzzing](https://lifeasageek.github.io/papers/jeong-segfuzz.pdf) (IEEE S&P 2023)

코드: https://github.com/casys-kaist/segfuzz

논문은 스레드 인터리빙(thread interleaving)을 메모리 접근 명령어 네 개 이하 단위인 interleaving segment로 분할하고, 이 segment들의 집합을 새로운 커버리지 지표인 interleaving segment coverage로 사용합니다. 여기에 이미 관측된 segment 내부의 실행 순서를 반전시키는 mutation으로 미탐색 인터리빙을 사전에 도출하고, 이를 하이퍼바이저 계층에서 강제 실행합니다.

그 결과 Linux 5.19-rc2부터 6.2까지에서 신규 동시성 버그 21개를 발견했고, 알려진 버그의 재현 속도는 기존 최신 기법 대비 평균 4.1배 빨랐습니다.

Background

Syzkaller로 대표되는 커버리지 기반 커널 퍼징은 시스템 콜 시퀀스를 무작위로 생성·실행하고, branch coverage 같은 코드 커버리지로 해당 입력이 새로운 실행 경로에 도달했는지를 판정합니다. 문제는 이 방식이 단일 스레드가 통과한 경로만 측정한다는 점입니다. 두 스레드가 어떤 순서로 교차했는지를 나타내는 concurrent aspect는 커버리지에 반영되지 않기 때문에 동일한 코드 경로를 수천 번 실행하더라도 버그를 발현시키는 특정 인터리빙은 끝내 탐색되지 않을 수 있습니다.

thread interleaving: 여러 스레드의 명령어가 서로 얽혀 실행되는 순서
**interleaving coverage: 그 인터리빙의 고유한 패턴을 추적하는 커버리지 지표
**표기: X ⇒ Y는 X가 Y보다 먼저 실행됐다는 뜻입니다. 뒤에 나오는 X → Y는 이와 달리 alias coverage가 기록하는 write→read 쌍을 가리킵니다.

선행 연구의 접근

같은 문제의식에서 출발한 동시성 퍼저가 이미 몇 가지 제안돼 있습니다. 이들은 크게 두 가지 측면에서 서로 다른 선택을 합니다.

인터리빙 탐색 방법. Razzer와 Snowboard는 매 실행마다 명령어 쌍 하나를 선택해 그 둘의 실행 순서만 강제합니다. KRACE는 런타임에 랜덤 딜레이를 주입해 무작위 스케줄링을 유도하고, Conzzer는 함수 두 개를 지정해 동시에 실행합니다.

인터리빙 커버리지 지표. KRACE의 alias coverage가 대표적입니다. 명령어 두 개의 실행 순서, 정확히는 IR이 IW가 기록한 값을 읽는 IW → IR 형태의 directed-instruction pair를 추적합니다. Conzzer는 이보다 굵은 단위로, 동시에 실행된 함수 쌍(concurrent call pair)을 지표로 씁니다.

Motivation: CVE-2017-17712

논문은 CVE-2017-17712를 예로 기존 접근의 한계를 짚고, 거기서 설계 목표를 끌어냅니다.

그림 1. CVE-2017-17712의 코드 스니펫. 두 컬럼의 세로 위치는 지면 배치일 뿐 실행 순서를 뜻하지 않으며, 레이블이 붉게 찍힌 A2·A4·B1이 버그 발현에 관여하는 접근이다. (논문 Fig. 1)

inet->hdrincl의 초기값이 1이면 thread A는 A2에서 이 값을 읽고 조건이 거짓이 되어 rfv를 초기화하지 않습니다. 그런데 A2와 A4 사이에 thread B의 B1이 선점해 값을 0으로 갱신하면 A4의 조건이 참이 되고, A5는 초기화되지 않은 rfv를 그대로 전달합니다. 이 지점에서 uninitialized stack pointer가 발생하며, 논문은 여기에 전용 공격 기법을 얹으면 공격자가 root 권한까지 획득할 수 있다고 설명합니다.

버그가 발현하려면 A2 ⇒ B1 ⇒ A4라는 세 개 명령어의 순서가 정확히 성립해야 합니다. 논문은 여기서 두 가지 design goal을 도출합니다.

Design goal 1: informative interleaving coverage.

아래 두 인터리빙을 비교해보겠습니다.

(a) B1 ⇒ A2 ⇒ A4 — 미발현
(b) A2 ⇒ B1 ⇒ A4 — 발현

그림 2. 버그가 발현하지 않는 인터리빙 (a)와 발현하는 인터리빙 (b). 버그와 무관한 접근 A6·B2는 생략돼 있다. (논문 Fig. 2)

커버리지 지표는 이 둘을 반드시 구분해야 합니다. 그러나 alias coverage 기준으로는, (a)를 먼저 실행할 때 (B1 → A2)와 (B1 → A4) 두 쌍이 기록됩니다. 이어서 (b)를 실행하면 (B1 → A4)는 이미 관측된 쌍이므로 새로운 커버리지가 전혀 발생하지 않습니다. 퍼저는 이 입력에서 더 얻을 것이 없다고 판정하고 다른 입력으로 넘어갑니다. 하지만 버그는 해당 인터리빙에 실재합니다. concurrent call pair도 한계가 같습니다. 두 인터리빙 모두 raw_sendmsg()와 do_ip_setsockopt() 내부에서 발생하므로 함수 단위로는 구분되지 않습니다.

물론 추적 명령어 수를 늘리는 것이 항상 이득은 아닙니다. 수천 개를 추적하면 커버리지 공간이 폭발해 탐색 복잡도를 감당할 수 없습니다. 결국 버그 탐지 능력과 탐색 복잡도 사이의 균형점을 잡는 것이 설계 문제의 핵심입니다.

Design goal 2: 추측적(speculative) 인터리빙 탐색.

(a)를 실행한 시점에서 우리는 B1, A2, A4 세 명령어가 동일한 메모리 객체에 접근했고 그 순서로 실행됐다는 사실을 확보합니다. 그렇다면 B1과 A2의 순서를 반전시키면 (b)가 된다는 것도 실행 이전에 도출할 수 있습니다. 따라서 무작위 실행을 수천 번 반복하는 대신, 관측된 실행으로부터 다음에 시도할 인터리빙을 역산해 곧바로 실행할 수 있습니다.

앞 절에서 본 네 도구는 모두 이 두 번째 목표에 미달합니다. Razzer와 Snowboard는 인터리빙 커버리지를 아예 쓰지 않고(coverage-oblivious) 휴리스틱에 의존하고, KRACE는 커버리지를 갖고 있어도 해당 입력을 계속 실행할지 판단하는 데에만 쓸 뿐 스케줄링은 무작위로 남겨둡니다. Conzzer는 함수 단위까지만 통제해 그 내부 명령어 순서는 고려하지 않습니다. 논문은 이를 "기존 접근은 인터리빙을 체계적으로 탐색하지 않으며 중복된 인터리빙을 반복 실행한다"고 정리합니다.

Methodology

0. System Overview

그림 3. SegFuzz의 전체 구조. 왼쪽이 single-thread fuzzing, 오른쪽이 multi-thread fuzzing이다. (논문 Fig. 7)

SegFuzz는 퍼징을 두 단계로 나눕니다.

Single-thread fuzzing: 기존 퍼저와 동일하게 시스템 콜 시퀀스를 생성·실행하며 branch coverage로 실행 경로를 확장합니다. 동시에 메모리 접근을 타임스탬프와 함께 기록하고, 동시 실행 시 새로운 interleaving segment가 발생할 가능성이 높은 시스템 콜 쌍을 선별합니다.
Multi-thread fuzzing: 전달받은 입력을 두 스레드로 분할하고, 인터리빙을 변형해 가며 반복 실행해 interleaving segment coverage를 축적합니다.

핵심 기여는 두 번째 단계에 있고, 세 스텝으로 구성됩니다.

관측한 인터리빙을 segment로 분해
각 segment 내부의 순서를 mutate해 미탐색 인터리빙 생성
mutate된 segment들을 recompose해 실제 스케줄로 변환

1. Multi-thread Fuzzing: 입력 변환과 버그 판정

single-thread fuzzing이 시스템 콜 쌍 (Si, Sj)를 골라 넘기면, multi-thread generator가 단일 스레드 입력 I_ST를 멀티스레드 입력 I_MT로 변환합니다. 분할 규칙은 단순합니다. 첫 시스템 콜부터 Si까지를 한 스레드에, 나머지를 다른 스레드에 배정하고, Si와 Sj를 제외한 콜은 I_ST와 동일한 순서로 실행합니다. 동시 실행 대상으로 지정되는 것은 Si와 Sj 두 개뿐입니다. 앞의 CVE 예제라면 socket(), setsockopt(), sendmsg() 세 콜로 이루어진 시퀀스가 socketsetsockopt를 맡는 스레드와 sendmsg를 맡는 스레드로 나뉘고, setsockopt와 sendmsg만 동시에 실행되는 것입니다.

버그 판정은 퍼저가 직접 하지 않고 커널의 타 도구에 위임합니다. multi-thread executor는 실행 중 lockdep, kernel watchdog, sanitizer가 memory corruption이나 deadlock을 보고하는지 확인하고, 보고가 있으면 해당 보고와 함께 I_MT, 실행된 인터리빙을 기록합니다. use-after-free나 hang처럼 이들 도구가 잡아내는 유형이 이 경로로 수집됩니다. 보고가 없으면 이번 실행에서 나온 segment graph 집합(이하 G')을 계산해 커버리지에 반영하고, 이를 generator로 돌려보내 다음 인터리빙 탐색에 씁니다.

G'가 어떻게 계산되고 generator가 그것으로 다음 스케줄을 어떻게 만드는지는 아래에서 다루겠습니다.

2. Interleaving Segment: 인터리빙 분할

논문은 지수적으로 커지는 탐색 공간을 문제 분할(decomposition)로 감당합니다.

segment 크기는 기존 서베이 연구를 근거로 합니다. 서베이 연구에 따르면 동시성 버그 105개 중 92.4%(97개)가 공유 메모리에 대한 접근 네 개 이하의 실행 순서로 발현됩니다. 저자들은 이 수치가 최신 커널에서도 유효한지 직접 검증했습니다. 최근 동시성 버그 패치 15개를 분석한 결과 14개가 메모리 접근 네 개 이하로 트리거됐고, 두 개 이하로 발현하는 것은 6개에 그쳤습니다. alias coverage가 명령어 두 개만 추적하는 것이 왜 불충분한지가 이 수치에서 드러납니다.

그래서 interleaving segment는 최대 네 개의 메모리 접근 명령어에 대한 인터리빙으로 정의됩니다. 앞의 CVE 예제에서 A2, A4, B1은 버그에 관여하지만 A6, B2는 무관합니다. 분할을 수행하면 버그에 관여하는 세 접근만 포함한 segment가 별도로 생성됩니다. 무관한 접근이 섞인 segment도 함께 생성되지만, "네 개를 초과하는 접근과 그 순서는 발현에 유의미하게 기여하지 않는다"는 전제 아래 문제 크기를 잘라내는 설계입니다.

그림 4. 실행 하나 (a)에서 추출되는 interleaving segment (b). 붉은 원이 버그 트리거에 관여하는 명령어다. (논문 Fig. 3)

그림 4에서 보듯 실행 하나로부터 Segment #1(B1, A2, A4), #2(B1, A2, A6, B2), #3(B1, A4, A6, B2) 세 개가 추출됩니다.

3. Interleaving Segment Coverage

3-1) 인터리빙을 그래프로 표현하기

먼저 실행된 인터리빙 전체를 DAG로 표현합니다. 정점은 메모리 접근 명령어, 간선은 실행 순서입니다. 간선은 두 종류입니다.

program-order edge: 동일 스레드 내 접근들의 순서. 인접 쌍만이 아니라 타임스탬프 기준 모든 순서쌍에 부여됩니다 (예: A2 ⇒ A4, A2 ⇒ A6)
interleaving-order edge: ①동일한 데이터에 접근하고 ②최소 하나가 write이며 ③서로 다른 스레드에서 실행된 두 명령어 사이의 순서 (예: B1 ⇒ A2)

read-read 쌍은 조건 ②를 만족하지 못해 제외됩니다. 뒤에서 segment graph를 고를 때 기준이 되는 것도, mutation의 대상이 되는 것도 이 interleaving-order edge입니다.

3-2) segment graph 추출

그림 5. 인터리빙 전체를 나타낸 DAG (a)와 거기서 추출한 Segment #1의 segment graph (b). 점선이 program-order edge, 실선이 interleaving-order edge다. (논문 Fig. 4)

DAG에서 interleaving-order edge 두 개를 선택하고, 해당 간선이 연결하는 정점들을 모은 뒤, 그 정점 사이의 모든 간선을 포함시키면 segment graph 하나가 만들어집니다. 예제에서 (B1 ⇒ A2)와 (B1 ⇒ A4)를 선택하면 정점 세 개가 모이고, 여기에 (A2 ⇒ A4)가 더해져 Segment #1이 됩니다.

간선을 하필 두 개 고르는 이유는 앞서 본 "접근 네 개 이하" 관찰에 있습니다. 간선 두 개가 연결하는 정점은 최대 네 개이므로, 두 개를 고르는 규칙 자체가 정점 네 개 제한을 구현하는 장치이며, 논문도 이를 서베이 결과를 반영한 설계라고 밝힙니다.

3-3) 커버리지로 쓰기: 그래프 해싱

이렇게 수집한 segment graph 집합이 곧 interleaving segment coverage입니다. 새로운 segment graph가 계속 발생하면 해당 입력에 컴퓨팅 자원을 더 투입할 가치가 있다는 신호이고, 발생하지 않으면 소진된 것으로 판정합니다.

문제는 메모리 사용량입니다. 그래프 하나의 크기는 작지만 개수가 많아, 논문은 각 segment graph를 해싱해 해시 테이블로 관리합니다. 다만 일반적인 해시로는 부족한데, 정점 집합이 같고 간선 방향만 다른 그래프를 반드시 구분해야 하기 때문입니다. 이를 위해 Merkle 해싱을 사용합니다.

hash(v) = H(v.label ++ o1.label ++ ... ++ om.label) // o1..om은 v의 out-going 이웃

hash(G) = XOR of hash(v) for all v in V

H는 비암호학적 해시인 FNV입니다. B1 ⇒ A2 ⇒ A4에서는 hash(B1) = H(B1++A2++A4)가 되지만, A2와 B1의 방향이 반전된 그래프에서는 hash(B1) = H(B1++A4)가 됩니다. out-going 간선을 해시에 반영하니 방향 차이가 해시값에 그대로 드러납니다.

4. Mutation 기반 인터리빙 탐색

4-1) 간선 방향 반전

그림 6. segment graph의 mutation. 탐색된 (a)에서 (b)·(c)·(d)가 파생되고, loop가 생기는 (d)는 폐기된다. (논문 Fig. 5)

mutation은 interleaving-order edge의 방향을 반전시키는 연산으로, 동일 메모리에 접근하는 두 명령어의 실행 순서를 바꿉니다.

탐색된 그래프 (a) B1 ⇒ A2 ⇒ A4에서 (B1 ⇒ A2)만 반전시키면 (b) A2 ⇒ B1 ⇒ A4, 즉 목표 인터리빙이 됩니다. 두 간선을 모두 반전시키면 (c)라는 또 다른 인터리빙이 나옵니다. 반면 (B1 ⇒ A4)만 반전시킨 (d)는 B1 ⇒ A2 ⇒ A4 ⇒ B1이라는 loop를 만들어, 실행 불가능한 순서이므로 폐기합니다. 이미 커버리지에 해시가 등록된 그래프도 함께 제외합니다. 이 과정으로 미탐색 mutated segment 집합 G_mutated가 구성됩니다.

4-2) recompose: 다시 병합하기

G_mutated를 하나씩 테스트하면 필요한 실행 횟수가 지나치게 많아집니다. 그래서 여러 개를 선택해 하나의 큰 그래프로 병합한 뒤, 한 번의 실행으로 여러 segment를 동시에 검증합니다.

병합 단계의 제약 역시 loop입니다. 빈 그래프에서 시작해 `G_mutated`를 순회하며 각 segment graph의 간선을 하나씩 넣어보고 BFS로 loop 발생 여부를 확인합니다. 간선 하나라도 loop를 만들면 그 segment graph는 이번 회차에서 통째로 보류되고, 전부 통과해야 간선이 모두 반영됩니다. 보류된 그래프는 `G_mutated`에 남아 다음 회차 후보가 되고, 집합에서 빠지는 것은 병합에 성공한 그래프뿐입니다.\

4-3) scheduling point 도출

그림 7. mutated segment (a)를 병합한 그래프 (b)와, topological sort로 얻은 명령어 시퀀스 (c). (논문 Fig. 6)

병합된 그래프에 topological sort를 적용하면 명령어 시퀀스가 산출됩니다. 여기서 선점(preemption)이 발생해야 하는 지점을 추출한 것이 scheduling point입니다. 각 scheduling point는 어느 명령어에서 정지하고 다음에 어느 스레드를 실행할지를 담습니다. 각 시스템 콜의 종료 지점도 scheduling point에 포함됩니다.

5. 커널 instrumentation

위 과정을 수행하려면 코드 커버리지용 basic block과 인터리빙 커버리지용 메모리 접근을 시스템 콜 단위로 기록해야 합니다. 메모리 접근에는 타임스탬프가 함께 붙습니다.

LLVM 컴파일러 패스가 basic block 진입점과 전역 메모리 객체 접근 명령어 앞에 각각 콜백을 삽입합니다. 전자는 해당 블록의 시작 주소를, 후자는 (메모리 객체 주소, 명령어 주소, 접근 크기, 접근 타입, 타임스탬프)의 5-튜플을 기록하며, 두 기록은 서로 다른 per-thread 영역에 쌓입니다. 두 영역 모두 mmap으로 유저스페이스와 공유되므로, 스레드는 시스템 콜 실행이 끝난 뒤 해당 영역을 읽어 자신이 지나간 basic block과 메모리 접근을 파악합니다.

6. Execution Engine: 스케줄 강제

계산된 스케줄을 실제로 강제하는 부분은 커널 실행에 개입하지 않기 위해 하이퍼바이저 계층에 구현돼 있습니다.

그림 8. execution engine의 동작 흐름. (논문 Fig. 8)

1. 퍼저 프로세스가 스레드를 생성하고, 각 스레드에 실행할 시스템 콜과 scheduling point를 배정합니다.

2. 각 스레드가 hcall_sched() 하이퍼콜로 scheduling point를 engine에 전달합니다. 이때 두 번째 인자로 scheduling point의 순서를 함께 넘깁니다.

3. engine이 해당 명령어에 브레이크포인트를 설치합니다.

4. 모든 스레드가 hcall_ready()로 집결합니다.

5. 시스템 콜을 실행합니다.

실행 중에는 항상 스레드 하나만 동작하도록 유지하며, 브레이크포인트가 히트되면 선점을 수행합니다.

선점 방식. Intel CPU의 하드웨어 브레이크포인트를 사용합니다. 브레이크포인트가 히트되면 레지스터 컨텍스트를 하이퍼바이저 메모리에 저장하고, PC를 cond_resched()를 무한 호출하는 trampoline으로 치환합니다. 해당 스레드는 CPU를 계속 양보하며 진행이 정지된 상태로 유지됩니다. 재개 시에는 저장한 레지스터를 복원합니다.

브레이크포인트 개수 제한. Intel은 동시에 네 개까지만 설치할 수 있으나 scheduling point는 그보다 많이 필요한 경우가 있습니다. scheduling point에 순서가 존재한다는 점을 이용해, 선행 네 개만 설치하고 하나가 히트될 때마다 다음 지점으로 재배치합니다.

미도달 지점 처리. 커널 내부 상태에 따라 제어 흐름이 달라져 특정 scheduling point를 통과하지 않을 수 있습니다. 이 경우 순서가 어긋나지 않도록, 히트된 지점보다 앞선 지점은 모두 무시하고 그 이후만 계속 강제합니다.

VMI(Virtual Machine Introspection). 두 가지 이유로 커널 내부를 조회합니다. 첫째, 브레이크포인트만으로는 어느 스레드가 히트했는지 구분할 수 없으므로 task_struct와 per-cpu preempt_count로 실행 컨텍스트를 판별합니다(무관한 스레드나 인터럽트 핸들러의 히트는 무시). 둘째, 락을 보유한 스레드를 정지시킨 상태에서 다른 스레드가 동일한 락을 요청하면 전체가 교착되므로, lock_acquire()lock_release() 같은 lockdep 함수를 후킹해 진행 불가 상황을 탐지하고 사전에 제어권을 이양합니다.

구현은 Syzkaller 기반 Go 3,334줄 + C++ 341줄, LLVM 12.0.1 컴파일러 패스 C++ 323줄, 커널 콜백 C 265줄, QEMU 6.0.0 위의 execution engine C 1,662줄로 이루어져 있습니다. KVM 하드웨어 가속은 그대로 활용합니다.

Performance Analysis

실험 환경은 Xeon E5-2683 v4(32코어)에 512GB RAM, VM 32대(각 4 vCPU / 8GB)입니다. 커널 설정은 Syzkaller가 쓰는 것을 그대로 사용해 동일한 서브시스템을 탐색하도록 맞췄습니다.

신규 동시성 버그 21개

평가 기간 동안 고유 크래시 83건이 발생했고(Syzkaller도 탐지하는 것 포함), 그중 21건이 신규 동시성 버그로 확인됐습니다. 대상 커널은 5.19-rc2부터 6.2까지입니다. 논문은 이 21건 중 3건이 몇 달 뒤 Syzkaller에서도 독립적으로 보고됐다고 함께 밝힙니다.

주목할 점은 분포입니다. 파일시스템에 특화된 KRACE와 달리 SegFuzz는 특정 서브시스템에 종속되지 않아, drivers/misc/vmw_vmci 같은 디바이스 드라이버부터 net/ipv4, kernel/events, mm, sound/core/oss까지 전 계층에서 버그가 나왔습니다. 심각도 역시 warning부터 use-after-free, general protection fault, invalid page fault까지 분포합니다.

특히 slip_ioctl의 UAF는 2013년부터, add_wait_queue의 GPF는 2011년부터 커널에 존재하던 버그입니다. Syzkaller가 수년간 커버해 온 서브시스템에서 이런 결과가 나왔다는 점이 이 논문의 가장 강한 근거라고 봅니다.

커버리지 지표 비교: alias coverage의 변별력

이번 실험은 Design goal 1, 즉 informative interleaving coverage가 실제로 효과적인가를 검증하는 실험입니다. 대상 버그 9개(논문 표기로 Vul #1~#9)는 선행 연구에서 이미 다뤄졌고 패치를 구할 수 있어 커널에 주입 가능한 것들로 골랐습니다. 선행 연구 ExpRace가 평가한 안드로이드 전용 CVE 두 건은 제외됐습니다. 환경을 통일하기 위해 커널은 v6.0-rc7 하나로 고정하고 해당 패치를 롤백해 버그를 되살렸으며, 각 버그를 트리거하는 멀티스레드 입력과 시스템 콜 쌍은 저자들이 수동으로 제공했습니다.

alias coverage 구현체가 파일시스템 전용이라 직접 실행할 수 없어, SegFuzz의 segment graph 정점 수를 2로 제한해 alias coverage를 에뮬레이션했습니다. 이후 커버리지가 포화될 때까지 실행하며 버그 발현 여부를 버그당 10회씩 관찰했습니다.

실험 결과, 9개 중 6개는 커버리지가 완전히 포화된 뒤에도 끝내 발견되지 않았습니다. 발견된 나머지 3개도 10회 시행 중 각각 6회, 7회, 9회만 발현해 재현이 불안정했습니다. 반면 interleaving segment coverage를 사용하면 9개 전부를 포화 이전에, 그것도 매 시행마다 발견했습니다. 저자들이 수동 분석한 결과 9개 버그 전부가 명령어 세 개 또는 네 개의 인터리빙으로 발현하는 사례였습니다.

한편 alias coverage 쪽은 빠르게 포화됐습니다. SegFuzz의 mutation 기반 탐색을 그대로 두고 지표만 바꿨을 때 평균 13.9회 실행(6~32회)이면 포화에 도달할 만큼 탐색 복잡도가 낮지만, 그만큼 탐지력이 떨어졌습니다. interleaving segment coverage는 탐색 공간이 훨씬 크되 탐지력이 높습니다.

탐색 효율 비교

그림 9. 버그 발견까지 걸린 실행 횟수(왼쪽)와 소요 시간(오른쪽). Naive는 스케줄 제어를 하지 않는 커널 기본 스케줄러다. (논문 Fig. 9)

이번 실험은 Design goal 2, 즉 추측적 인터리빙 탐색이 실제로 이득인지를 보는 실험입니다. Snowboard와 KRACE는 원본을 그대로 실행할 수 없어(KRACE는 파일시스템 전용, Snowboard는 QEMU TCG 기반이라 시간 비교가 불공정) SegFuzz의 multi-thread fuzzing 단계 위에 KRACE의 랜덤 딜레이 주입, Snowboard의 단일 인터리빙 순서 강제를 재구현했습니다. 여기에 스케줄 제어를 수행하지 않는 커널 기본 스케줄러(Naive)를 베이스라인으로 두었습니다.

실행 횟수와 소요 시간이 초기 시드와 시드 mutation 과정에 크게 좌우돼 공정한 비교를 방해할 수 있기 때문에 앞 실험에서의 수동 입력 제공 조건이 이번 실험에서도 그대로 적용되었으며, 따라서 아래 수치는 single-thread fuzzing 단계를 건너뛰고 버그 유발 입력이 이미 주어진 상태에서 인터리빙 탐색 능력만 격리해 측정한 값입니다.

† KRACE의 평균 소요 시간은 논문 표기상 "discovers them, if successful, within 329.1 runs"로, 탐지에 성공한 건만의 평균입니다. KRACE는 CVE-2019-6974와 버그 패치 커밋 69e16d01d1de를 10,000회 내에 발견하지 못했습니다.

‡ 커널 기본 스케줄러는 CVE-2019-6974, CVE-2019-11486, 커밋 69e16d01d1de를 10,000회 내에 발견하지 못했습니다. 논문은 Naive의 평균값을 제시하지 않아 소요 시간 칸은 비워뒀습니다.

### 버그 없는 입력의 소진 시간

퍼징에서 더 빈번한 상황은 버그가 없는 입력을 모두 탐색하고 넘어가는 경우입니다. 그래서 앞의 버그들을 수정하는 패치를 전부 적용한 뒤, 주어진 멀티스레드 입력의 interleaving segment coverage가 포화될 때까지 걸리는 시간을 측정했습니다. 9개 중 하나(그림 10에서 빠진 Vul #8)는 패치가 취약 서브시스템 자체를 비활성화하는 방식이라 제외됐고, 나머지 8개 입력이 대상입니다.

그림 10. 패치 적용 후 주어진 멀티스레드 입력의 인터리빙을 모두 소진하는 데 걸린 시간. (논문 Fig. 10)

Snowboard 대비 7.1배, KRACE 대비 11.1배 빠릅니다. 입력 하나당 Snowboard 대비 평균 298초를 절감하는데, 평가 기간 중 SegFuzz가 6만 개 이상의 입력을 생성했다는 점을 감안하면 이 이득은 계속 누적됩니다.

커버리지 증가와 오버헤드

100시간 퍼징 결과입니다.

스케줄 제어를 비활성화하면(=랜덤 스케줄링) 동일 기간의 interleaving segment coverage가 29.1% 적게 나옵니다. 24시간 실험을 반복해 Mann-Whitney U 검정을 수행한 p-value는 0.03으로, 무작위 변동이 아니라 실제 성능 차이로 볼 수 있습니다.
반대로 코드 커버리지는 Syzkaller보다 3.2% 낮습니다. 동일 입력을 반복 실행하는 데 컴퓨팅 자원을 쓰므로 예상되는 결과입니다. 논문도 명백한 단점이라고 인정하되, 인터리빙 탐색에서 얻는 이득을 감안하면 감수할 만한 수준이라고 덧붙입니다.

throughput 측정은 빈 시드 집합에서 시작했습니다. SegFuzz와 Syzkaller 모두 한 시간마다 VM을 재시작하는데, 측정 구간을 1시간으로 끊은 것은 재부팅이나 커널 크래시에서 오는 노이즈를 빼기 위해서입니다.

결과는 SegFuzz 4.55 exec/s로 Syzkaller(8.40)의 약 54% 수준입니다. 다만 Syzkaller에 메모리 접근 추적 instrumentation만 추가하고 활용은 하지 않은 버전이 4.74 exec/s로, SegFuzz와 4.1% 차이에 그칩니다. throughput 저하의 주 원인은 SegFuzz의 알고리즘이 아니라 메모리 접근 추적 instrumentation입니다.

입력 하나의 실행 시간 267.2ms(1만 회 실행의 평균)를 분해하면 이 점이 더 분명해집니다.

런타임 오버헤드 두 항목이 실행 시간을 거의 두 배로 만드는 반면, SegFuzz 고유의 계산 오버헤드는 26.1ms로 전체의 10% 미만입니다(논문 표기로는 약 9%). 커버리지 생성과 다음 인터리빙 계산 자체는 저렴하고, 비용은 그것을 위한 관측(90.7ms)과 스케줄 강제(42.8ms)에서 발생합니다.

Conclusion

SegFuzz는 "동시성 버그의 대부분은 메모리 접근 네 개 이하의 실행 순서로 발현한다"는 경험적 관찰에서 출발한 커널 동시성 퍼저입니다. 파이프라인은 다음과 같습니다.

1. 실행된 인터리빙을 DAG로 표현

2. interleaving-order edge 두 개를 기준으로 정점 네 개 이하의 segment graph로 분해

3. Merkle 해싱으로 간선 방향까지 구분해 커버리지로 추적

4. 간선을 반전시켜 미탐색 인터리빙을 역산

5. loop가 생기지 않는 범위에서 재조합하고 topological sort로 스케줄 산출

6. 하이퍼바이저에서 하드웨어 브레이크포인트로 그 스케줄을 강제 실행

이 구조로 최신 커널에서 신규 동시성 버그 21개를 찾았고, 그중에는 10년 넘게 남아 있던 것도 있습니다.

저자들이 스스로 짚은 한계와 적용 범위는 세 가지입니다.

크기가 4를 넘는 인터리빙. 메모리 접근 다섯 개 이상이 얽혀야 발현하는 버그(서베이 105개 중 8개)는 그 인터리빙을 커버리지로 추적하지 못합니다. 다만 추적을 못 할 뿐, 여러 segment를 재조합하는 과정에서 트리거 자체는 가능하다고 논문은 덧붙입니다.

커널 백그라운드 스레드. kworkerd 같은 스레드는 basic block과 메모리 접근을 추적할 수단이 없어 interleaving segment coverage가 적용되지 않고, 그만큼 이 영역의 버그 탐색은 비효율적입니다. 논문은 설계 문제가 아니라 추적 메커니즘의 부재라고 선을 그으며, 그 구현을 남은 숙제로 남깁니다.

double-fetch와 data race detector. 공유 데이터가 유저 메모리에 있는 double-fetch에는 효과적이지 않습니다. 유저 메모리 접근을 추적하지 않아 커널-유저 경계를 넘는 인터리빙이 잡히지 않기 때문입니다. data race detector와도 설계가 직교합니다. SegFuzz는 data race를 포함해 메모리 오염 같은 유해한 동작으로 드러나는 버그를 노리므로 CVE-2019-6974처럼 data race가 아닌 것도 잡고, detector는 거꾸로 메모리를 오염시키지 않는 의미론적 버그를 잡습니다. 논문은 두 계열 모두와 상호 보완적이라고 정리합니다.