SegFuzz: Segmentizing Thread Interleaving to Discover Kernel Concurrency Bugs through Fuzzing
Authors:
- 1 May 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2104-2121
Abstract
Discovering kernel concurrency bugs through fuzzing is challenging. Identifying kernel concurrency bugs, as opposed to non-concurrency bugs, necessitates an analysis of possible interleavings between two or more threads. However, because the search space of thread interleaving is vast, it is impractical to investigate all conceivable thread interleavings. To explore the vast search space, most previous approaches perform random or simple heuristic searches without having coverage for thread interleaving or with an insufficient form of coverage. As a result, they either conduct wasteful searches with redundant executions or overlook concurrent bugs that their coverage cannot address.To overcome such limitations, we propose SegFuzz, a fuzzing framework for kernel concurrency bugs. When exploring the search space of thread interleavings, SegFuzz decomposes an entire thread interleaving into a set of segments, each of which represents an interleaving of the small number of instructions, and utilizes individual segments as interleaving coverage, called interleaving segment coverage. When searching for thread interleavings, SegFuzz mutates interleavings in explored interleaving segments to construct new thread interleavings that have not yet been explored. With SegFuzz, we discover new 21 concurrency bugs in Linux kernels, and demonstrate the efficiency of SegFuzz by showing that SegFuzz can identify known bugs on average 4.1 times quickly than the state-of-the-art approaches.Keywords
Funding Information
- National Research Foundation of Korea
This publication has 43 references indexed in Scilit:
- ProRace2017
- Radius aware probabilistic testing of deadlocks with guarantees2016
- TxRace2016
- A Study of Linux File System EvolutionACM Transactions on Storage, 2014
- Multicore acceleration of priority-based schedulers for concurrency bug detection2012
- Detecting and surviving data races using complementary schedules2011
- Learning from mistakes2008
- Valgrind2007
- A Digital Signature Based on a Conventional Encryption Function1988
- Topological sorting of large networksCommunications of the ACM, 1962