I’ve been thinking about what would be the best way to fuzz-test a Linux kernel module, for example a filesystem. Of course this can be done in the context of a live kernel, but for a variety of reasons I’d prefer to run the LKM in user space. At the source level, the interface to an LKM seems a little hairy, but at the object level they are really simple. So, a reasonable approach would seem to be to write a user-space loader for compiled LKMs and then just call the object code directly. At that point it would become necessary to write a set of shims to support each class of device driver and then fuzzing could start.
Anyway, I’m curious to see what people think about this idea before I go off and hack. I did some random web searching and didn’t turn up an existing implementation of this idea, though of course there are plenty of resources on testing various parts of Linux.
11 responses to “Fuzzing Linux Kernel Modules?”
I’ve never thought of the kernel’s object ABI (symbols exported to modules) as really simple. The interface is big and changes often, though the changes wouldn’t affect you if you only need to target one version of a driver.
I think I’d start with User-Mode Linux. It should take care of the ABI while giving you the flexibility of user space. In particular, the ability to fork, try some fuzz, then just exit and go back to the fork when something fails is pretty appealing.
There’s definitely some prior work in checking file systems using model checking: Junfeng Yang (with Dawson Engler) got a best paper award for it at OSDI04. There’s at least a bit of overlap between fuzz testing and model checking.
Have you fuzz tested any drivers before? I have, for BlueStripe. One lesson you learn pretty quickly is that drivers have a long initialization phase, and if you fuzz test the whole driver source uniformly, you’ll usually never make it through initialization. So we ended up setting separate fault rates for initialization and steady state.
I’ll be interested to hear how this turns out.
For filesystems, I would suggest writing a fuzz module for device-mapper, wrap it around a filesystem, and mount it with a normal kernel. You’d probably want to run the kernel in some kind of virtual machine (or UML) in order to capture as much useful information as possible when things go wrong (I have no doubts they will).
The networking stack should be fairly simple to fuzz test using raw sockets (or regular sockets to test only the higher levels).
Device drivers could perhaps be tested by running in an emulator (e.g. qemu) modified to corrupt accesses. Although it would not accurately emulate genuinely broken hardware, it should still prove interesting. At this level the question arises of just how robust a driver should be expected to be. If the hardware is actually broken, you probably have bigger problems.
Hi Patrick, thanks for the comments and good to hear from you.
The UML idea has appeal, but doesn’t help with unit-testing of drivers, which is what I’m after here.
I’ve fuzzed drivers but it was a while ago, and using some source-level scaffolding that I found cumbersome. Also, much more recently I’ve done some fuzzing at the system call level and found it pretty frustrating — very hard to drive execution into interesting dark corners.
Re the ksyms being big, sure — but here let’s look at the subset used by a single network driver:
regehr@home:~/linux/drivers/net$ nm -g 3c507.ko
U __dynamic_pr_debug
U __gcov_init
U __gcov_merge_add
U __netif_schedule
U __raw_spin_lock_init
U __release_region
U __request_region
00000000 D __this_module
U _raw_spin_lock
U _raw_spin_lock_irqsave
U _raw_spin_unlock
U _raw_spin_unlock_irqrestore
U alloc_etherdev_mqs
00000000 T cleanup_module
U consume_skb
U dev_alloc_skb
0000061a T el16_probe
U eth_change_mtu
U eth_mac_addr
U eth_type_trans
U eth_validate_addr
U free_irq
U free_netdev
00000834 T init_module
U ioport_resource
U ioremap_nocache
U iounmap
U jiffies
U mcount
U netdev_boot_setup_check
U netif_rx
U netpoll_trap
U param_ops_int
U printk
U register_netdev
U request_threaded_irq
U skb_put
U sprintf
U strcpy
U unregister_netdev
U warn_slowpath_null
Just at a glance this doesn’t look bad.
Hmm, some of the fs modules have a lot of entry/exit points. What would XFS be doing with almost 2000 external symbols?
regehr@home:~/linux/fs$ for file in $( find . -name ‘*.ko’ ); do echo -n $file ; echo -n ‘ ‘ ; nm -g $file | wc -l; done
./xfs/xfs.ko 1991
./ubifs/ubifs.ko 414
./ufs/ufs.ko 161
./sysv/sysv.ko 126
./nls/nls_euc-jp.ko 10
./nls/nls_iso8859-2.ko 8
./nls/nls_utf8.ko 10
./nls/nls_iso8859-14.ko 8
./nls/nls_cp865.ko 8
./nls/nls_cp869.ko 8
./nls/nls_cp950.ko 8
./nls/nls_iso8859-7.ko 8
./nls/nls_cp857.ko 8
./nls/nls_cp863.ko 8
./nls/nls_cp866.ko 8
./nls/nls_cp864.ko 8
./nls/nls_cp1255.ko 8
./nls/nls_iso8859-13.ko 8
./nls/nls_koi8-ru.ko 10
./nls/nls_cp437.ko 8
./nls/nls_cp1251.ko 8
./nls/nls_cp860.ko 8
./nls/nls_cp874.ko 8
./nls/nls_iso8859-6.ko 8
./nls/nls_cp932.ko 8
./nls/nls_iso8859-15.ko 8
./nls/nls_cp850.ko 8
./nls/nls_koi8-r.ko 8
./nls/nls_iso8859-3.ko 8
./nls/nls_ascii.ko 8
./nls/nls_cp936.ko 8
./nls/nls_cp862.ko 8
./nls/nls_iso8859-4.ko 8
./nls/nls_cp1250.ko 8
./nls/nls_cp861.ko 8
./nls/nls_iso8859-1.ko 8
./nls/nls_koi8-u.ko 8
./nls/nls_iso8859-5.ko 8
./nls/nls_cp855.ko 8
./nls/nls_cp775.ko 8
./nls/nls_cp949.ko 8
./nls/nls_iso8859-9.ko 8
./nls/nls_cp852.ko 8
./nls/nls_cp737.ko 8
./cifs/cifs.ko 551
./coda/coda.ko 166
./jbd/jbd.ko 237
./minix/minix.ko 130
./afs/kafs.ko 359
./binfmt_misc.ko 63
./ceph/ceph.ko 387
./binfmt_aout.ko 33
./gfs2/gfs2.ko 523
./btrfs/btrfs.ko 1058
./omfs/omfs.ko 91
./nfs_common/nfs_acl.ko 17
./autofs4/autofs4.ko 131
./affs/affs.ko 150
./9p/9p.ko 268
./freevxfs/freevxfs.ko 67
./fuse/fuse.ko 291
./fuse/cuse.ko 55
./udf/udf.ko 198
./ext3/ext3.ko 416
./efs/efs.ko 54
./nfsd/nfsd.ko 489
./fscache/fscache.ko 306
./nfs/objlayout/objlayoutdriver.ko 91
./nfs/nfs.ko 868
./nfs/blocklayout/blocklayoutdriver.ko 94
./nfs/nfs_layout_nfsv41_files.ko 85
./bfs/bfs.ko 73
./qnx4/qnx4.ko 57
./hfsplus/hfsplus.ko 213
./ocfs2/ocfs2.ko 1056
./ocfs2/ocfs2_stackglue.ko 74
./ocfs2/ocfs2_stack_user.ko 32
./ocfs2/dlm/ocfs2_dlm.ko 216
./ocfs2/dlmfs/ocfs2_dlmfs.ko 86
./ocfs2/ocfs2_stack_o2cb.ko 28
./ocfs2/cluster/ocfs2_nodemanager.ko 241
./cachefiles/cachefiles.ko 174
./ext2/ext2.ko 270
./romfs/romfs.ko 44
./dlm/dlm.ko 302
./mbcache.ko 49
./logfs/logfs.ko 236
./adfs/adfs.ko 79
./nilfs2/nilfs2.ko 440
./jfs/jfs.ko 369
./hfs/hfs.ko 187
./isofs/isofs.ko 99
./ext4/ext4.ko 667
./squashfs/squashfs.ko 115
./reiserfs/reiserfs.ko 420
./befs/befs.ko 73
./exofs/exofs.ko 164
./exofs/ore.ko 60
./ecryptfs/ecryptfs.ko 286
./lockd/lockd.ko 210
./cramfs/cramfs.ko 45
./jffs2/jffs2.ko 319
./hpfs/hpfs.ko 166
./fat/vfat.ko 54
./fat/fat.ko 190
./fat/msdos.ko 39
./ntfs/ntfs.ko 269
./quota/quota_v1.ko 13
./quota/quota_tree.ko 25
./quota/quota_v2.ko 21
./configfs/configfs.ko 144
./ncpfs/ncpfs.ko 206
./jbd2/jbd2.ko 277
First, I second the suggestion to build such a system on top of UML, which will give you all of the convenience of developing the fuzzer and running it in user space, with the utility of running unmodified kernel modules. Second, have you looked at DDT[1] as a possible basis for this work? If memory serves, DDT uses selective symbolic execution to exercise many driver paths and looks for abnormal behavior. It works on binary-only drivers, so no source is required. It would be interesting to see if fuzzing could find additional bugs beyond those found by their selective symbolic execution.
[1] V. Kuznetsov, V. Chipounov, and G. Candea. Testing Closed-Source Binary Device Drivers with DDT. In USENIX Annual Technical Conference, 2010
Have you heard of LinSched? It is not for fuzz testing, but the idea seems similar. LinSched hosts Linux scheduling subsystem in the user mode.
http://www.cs.unc.edu/~jmc/linsched/
Hi Seo, thanks for the link, I hadn’t sen this.
However I built something similar to debug schedulers about 10-12 years ago. I’d never have gotten some of the multiprocessor stuff debugged without this. Fuzzing schedulers is super useful, actually.
Would be interesting to runs tests using fuzzed virtualized hardware, i.e. injecting errors and non-spec behaviors from the device.
Actually, we did something similar together with Cadence a couple of years ago, where we used virtual platforms to control the hardware side of things and a test runner to control the user-code calling into the driver. With some directed random testing from Incisive ISX.
If you use a virtual platform, you gain two things:
* Control over hardware that lets you inject faults, control latencies (making a device really fast or really slow reveals bad driver code real easy, see for example http://jakob.engbloms.se/archives/337 )
* Use checkpoints to restart tests from a known state with a loaded driver in no time at all, and save progress points as you keep on testing
The big question is just what to fuzz, and at which end of the driver.
See: http://www2.dac.com/46th//proceedings/slides/03U_3.pdf ,
I
Jakob, thanks for the links, this looks great.
> I’ve been thinking about what would be the best way to fuzz-test
> a Linux kernel module, for example a filesystem.
Linus Torvalds appears to discard conventional wisdom of using tools such as GCC’s static analyzer to help detect possible errors [1]. Perhaps the first step would be to compile a kernel with warnings turned on to help select targets.
JW, Baltimore, MD, US
[1] http://linux.derkeiler.com/Mailing-Lists/Kernel/2006-11/msg08325.html