StateFuzz: System Call-Based State-Aware Linux Driver Fuzzing

Bodong Zhao, Zheming Li, Shisong Qin, Zheyu Ma, Ming Yuan, Wenyu Zhu, Zhihong Tian, Chao Zhang
USENIX Security 2022

개요

Syzkaller의 코드 커버리지를 Device driver에 맞도록 최적화 시켜, Device driver fuzzing에 최적화된 퍼저를 개발하였다.

Motivation

Fuzzer는 매우 다양한 분야에서 사용된다. 그러나 State에 대한 고려없이는 커버리지가 효율적이지 못하다는 단점이 있다. 기존의 연구들은 Code-coverage centric이여서, 디바이스 드라이버처럼 State들이 복잡하게 엮여있는 Kernel의 컴포넌트는 제대로 퍼징하지 못한다는 단점이 있었다.

Main Idea

State-aware fuzzing에서는 다음의 핵심 3개의 질문에 답을 주어야 한다.

What are program state: 프로그램 State를 정의해주어야 한다. Program state에는 Variable, Instruction counts, Register states와 같이 프로그램의 모든 내용이 포함되기 때문에, 각 Application에 적합한 Program state를 정의해 주어야 한다.
How to recognize program state and track them: 그렇다면 정의된 Program state를 프로그램에서 어떻게 찾아야 하는지 정해주어야 하고, Fuzzing에서 그들의 state를 추적할지 방법을 정해야 한다. 논문에서는 State-aware fuzzing은 수동적인 Annotation이 아니라, Automatically하게 recognizing하는 것이 중요하다고 주장하고 있다.
How to utilize program states to guide fuzzing: Program state를 이용하여 새로운 Feedback을 보다 효율적인 (즉 보다 더 넓은 범위의 버그를 찾을 수 있는) 곳까지 확장하는 효율적인 방법이 있어야 한다.

Device driver의 입장에서 논문은, 위의 3가지에 대한 질문의 답을 한다.

What are program state: 우선 Critical variables를 정의한다. Critical variables은 Long lifetime, User에 의해서 update됨, 혹은 program의 control flow나 memory access pointer에 영향을 미치는 변수로 정의하였다.
How to recognize program state: Static analysis를 활용하였다. Device driver는 Rich-state program이며 여러개의 input state를 가지는 경우가 많다 (e.g., ioctl(A), ioctl(B), ...). 이러한 Multi-stage 각각의 단계는, input이 일으키는 변화는 Share variable을 이용하여 공유한다. 따라서 Static analyzer는 shared variable의 relevant를 분석하여, 중요한 Critical variable들을 선별하였다.
How to utilize program states to guide fuzzing: Program state가 정해지면, Program state가 Device driver의 Input이 보다 넓은 범위의 변화를 가져오는 방향으로 유도하도록 하였다.

Background

Device driver fuzzing의 두가지 방향: Device driver fuzzing은 2가지 방향에서 이루어진다. ioctl과 같은 System call 방향, 그리고 PIO, MMIO, DMA와 같은 하드웨어 방향에서 각각 Fuzzing을 해야 한다. System call과 같은 경우에는 ioctl이 매우 복잡한 structure와 command를 가지고 있기 때문에, fuzzing하기 힘들다고 알려져 있다.

Code-coverage만 사용하는 경우의 한계: IJON에서 소개하였듯이, Code-coverage만 사용하는 것은 한계가 명확하다. 우선 많은 버그들이 특정 조건이 만족하여야만 발생하는 경우가 많다. 그러나 새로운 path는 보통 특정 조건과 연결되는 경우는 적다. 따라서 Code-coverage만 사용하는 Fuzzing은 새로운 useless한 path를 찾는데 대부분의 시간을 소비할 위험이 있다. 또한 Code-coverage만 신경쓰면, 새로운 state변경을 가져오지만, 새로운 path는 아닌 테스트 케이스들을 놓칠 가능성이 높다. 따라서 Program의 state를 반영하여 fuzzing을 하는 것이 중요하다.

Program state의 정의: Program state는 Application이 사용하는 모든 변수, Reigster state, Program counter등 모든 State를 의미한다. 본질적으로 모든 Program state를 탐색하면 모든 버그를 찾아낼 수 있다. 그러나 State exploration때문에 이는 불가능하다고 볼수 있다. 그러나 중요한 Program state로 줄여나갈 수는 있다. Critical한 State를 정의하기 위해서 StateFuzz에서는 Device driver를 Sampling하여 조사하였다. 결과적으로 프로그램이 Critical한 Program state를 변수에 저장하는 경우가 매우 흔하다는 사실을 제시하였다. 예를 들어서 보통 디바이스 드라이버는 State machine을 나타내기 위해서 특정 변수에 현재 State의 상태를 enum형식으로 저장하는 경우가 매우 흔하였다.

Design

Program State의 정의: Prgoram state를 1. Lifetime이 긴 변수, 2. User에 의해서 변경되는 변수, 3. Program의 Control flow나 Memory access pointer를 변경시키는 것으로 State-variable을 정의하였다. 또한 모든 State variable의 조합을 고려하는 것이 아니라, 변수의 쌍이 공유하는 Control flow나 Memory access pointer가 있을 경우에만 Releveant하다고 간주, 이 경우에만 추적하였다. 또한 변수 (e.g., int는 최대 2^32승의 조합이 가능)을 추적하는 것이 아니라, 변수가 지니는 범위를 Static anslysis를 통하여 예측하여 (e.g., enum)그 변수의 범위만 Fuzzing coverage에 포함되도록 하였다.

Program state recognition: Static analysis를 통하여 Program state variable을 선별하였다. 우선 Static analysis를 통하여 Prgoram Action State를 선별하였다. 그후 Prgoram Action들이 공유하는 변수들을 찾아내었다. 만약 State variable들이 global variable이거나 아니면 structure의 field변수이면 long lifetime을 가질 것이라고 예측하여 state-variable에 추가하였다. 또한 Action과 Action사이에서 공유되는 변수들도 State variable로 추가하였다.

Inter State-variables's Value Ranges: State variable들이 가질 수 있는 변수의 범위를 측정하기 위해서, path-sensitive static symbolic execution on the abstract syntax tree (AST)를 소스코드에 적용시켜, 각각의 변수들이 사용하는 범위를 추측하였다.

Fuzzing Loop: StateFuzz는 Genetic algorithm을 적용시켜서, fuzzer가 더 많은 program state를 추측하도록 하였다. 본 추측에는 3개의 Feedback Machine, 즉, Code-coverage, Value-range, and Extreme value dimenstion이 사용되었다. Code-coverage feedback machine은 Syzkaller에 있는 것을 재사용하였다. Value-range와 같은 경우에는 StateFuzz가 추가적으로 더한 Expected value range에 있는 경우이며, Extreme의 경우는 그외의 예측하지 못한 범위의 값이 나오는 경우이다. Fuzzer는 3개의 Code coverage를 최대화 하는 방향으로 테스트 프로그램을 생성하였다.