File System Mutation Tool

Overview

This tool exists to find bugs in filesystem code by "fuzzing" (overwriting) blocks on the filesystem to see how the file system code reacts. Unlike earlier versions of this tool that would mutate any block (metadata or data), this version aims only to hit metadata with a somewhat cheesy heuristic.

How it Works

First, the heuristic for finding metadata blocks. It occurred to me that with a few exceptions (ZFS), most file systems do nothing to validate data blocks on the disk; thus the filesystem is not likely to notice data corruption! So we set up a simple heuristic--all data files must contain zeroes. When we compare two generations of a filesystem image, we can then find the metadata blocks that were modified simply by diffing all blocks in images A and B where the block in B is not all zeroes.

There are three key components to fs_mutate--bddiff, bdmutate, and smash_$FS. bddiff compares blocks in two files per the heuristic above and prints out a list of changed blocks. The block numbers _should_ correspond to metadata blocks, though an expert might want to check this first. Typical usage:

$ bddiff 512 ext2_image.0 ext2_image.1

bdmutate has the actual duty of mutating blocks in a filesystem image. This is its command-line syntax:

bdmutate $blocksize $file $probability $corruption

$blocksize is generally 512, because disks usually have 512 byte sectors; $file is the file that is to be corrupted. $probability is a floating point number establishing the likelihood that a particular metadata block will be destroyed. Empirical testing shows that a probability of about 0.2 wreaks plenty of havoc.

The last parameter, $corruption, is the sort of corruption that should be done. "zero" and "one" are simple--the whole block is overwritten with zeroes or ones, respectively. "garbage" will write a block's worth of random data. However, "bitflip" is the most interesting operation--it flips an arbitrary bit in the block. This is quite useful for corrupting inodes and indirect blocks, as it is now quite possible to cross-link files, link in nonexistent data blocks, change metadata, corrupt extended attributes, etc. "revert" is the fifth option; given an "old" file, it will copy blocks from the old file into the file that is being corrupted.

The program takes a list of blocks that are eligible for corruption as input.

The final program, smash_$FS, ties together bddiff and bdmutate. Generally, this should be a shell script that creates the filesystem image and enters a loop wherein the current generation of the image is compared against the previous version, the current image is then mutated and tested, and then modified via regular filesystem operations. smash_ext2 is a short example for the ext2 filesystem.

bddump, incidentally, takes a list of block numbers and dumps the corresponding blocks from a file.

Download the source here: fs_mutate-0.52.tar.gz (11K).