Reproducible Kernel Fuzzer for Concurrency Bugs through Deterministic Scheduling

Abstract

커널 퍼져들이 최근 몇 년간 발전해오면서 퍼져에 의해 보고되는 버그들의 수가 늘어났다. 커널 개발자들이 이런 버그들을 모두 분석할 수 없기 때문에 이런 상황은 디버깅 정보를 제공해줄 수 있는 버그 재현의 중요성을 더욱 중요하게 만든다. 불행 히도, 퍼져는 종종 버그 재현에 실패하는데 재현이 힘든 버그 중 하나가 바로 동시성 버그다. 동시성 버그는 여러 스레드 사이의 특정한 조건을 만족할때 발생하는데 커 널 스케쥴링의 비결정적인 스레드 간섭은 동시성 버그의 재현을 막는다. 그 결과, 일부 동시성 버그들은 버그의 재현에 실패한 뒤 고쳐지지 않은채 버려진다.

이 논문에서는, 퍼져에 의해 발견된 버그를 결정적으로 재현할 수 있도록 도와주 는 REPFUZZER 를 소개한다. 이는 선택적 스레드 추적과 결정적 스케쥴러를 통해 문 제를 해결한다. 선택적 스레드 추적을 통해 REPFUZZER 는 퍼져에 있어서 흥미로운 스레드에만 집중할 수 있도록 한다. 그리고 REPFUZZER 는 결정적 스케쥴러를 통해 선택된 스레드를 스케쥴 해주며 결정적인 스레드 간섭을 만들어 낸다. 퍼징 단계와 재현 단계 모두에서 REPFUZZER 를 사용함으로써 퍼져는 찾아낸 버그를 재현해낼 수 있게 된다. 결과적으로 REPFUZZER 는 15개의 실제 동시성 버그를 재현하면서 효율성을 보여줬으며, 버그 중 일부는 비결정적인 커널 스케쥴링으로 재현해내기 위해 엄청난 시간을 필요로 했다.

As kernel fuzzer has been studied and becomes better for years, the number of reported bugs from the fuzzer increased. Since kernel developers could not analyze all of the bugs, the situation emphasizes the importance of bug reproduce which can provide debug information. Unfortunately, the fuzzer often fails to reproduce bug, and one of the most difficult bug type is concurrency bug. The concurrency bug requires certain conditions between several threads, and non-deterministic thread interleavings from kernel scheduling prevent reproducing. As a result, some concurrency bugs are left unpatched after failures of reproduce.

In this thesis, we presents REPFUZZER which enables deterministic reproduce for bugs found by fuzzer. It solves the problem with selective thread tracing and deterministic scheduler. With selective thread tracing, REPFUZZER can focus on only interesting thread in fuzzing context. Then REPFUZZER schedules the selected threads with deterministic scheduler and produces deterministic thread interleavings. Using REPFUZZERs scheduling at both fuzzing and reproduce phase, the fuzzer can reproduce bugs found at fuzzing phase. As a result, REPFUZZER shows its effectiveness for reproducing concurrency bugs with 15 real-world bugs, and some of the bugs require enormous times to be reproduced with non-deterministic kernel scheduling.