LFuzz: Exploiting Locality-Enabled Techniques for File-System Fuzzing

File systems (FSes) store crucial data. However, FS bugs can lead to data loss and security vulnerabilities. FS fuzzing is an effective technique for identifying FS bugs that may be difficult to detect through traditional regression suites and human testing. FS fuzzing involves two parts: (1) File image fuzzing often involves altering bits of an FS at random storage locations; (2) File operation fuzzing typically issues random sequences of file operations to an FS image. Since leading FS fuzzers tend to access a small set of files to encourage the exploration of deep code branches, the accessed FS image locations tend to be clustered and localized. Thus, altering bits at random FS locations is ineffective in triggering bugs, as these locations are often not referenced by file operations. Furthermore, the minimum FS image is insufficiently small for frequent image saves and restores due to performance and storage overhead. In this paper, we introduce LFuzz, which exploits the locality shown in typical FS fuzzing workloads. LFuzz tracks recently accessed image locations and nearby locations to predict which locations will soon be referenced. The scheme is adaptive to migrating file access patterns. Moreover, since modified image locations are localized, LFuzz can compactly and incrementally accumulate FS image changes so that FS states can be fuzzed from intermediary images instead of top-level seed images. LFuzz further explores the use of partially updated images to simulate corrupted FSes with mixed versions of metadata. We applied LFuzz to ext4, BTRFS, and F2FS and found 21 new bugs. Compared to JANUS, LFuzz reduced the fuzzing area by up to 8x with unique edges deviated by up to 15%.