nfsim: “Untested code is buggy code”

Jeremy Kerr IBM LTC (OzLabs)

Rusty Russell IBM LTC (OzLabs)

Topics

Time Better Spent...

The Old Testsuite, a New Incentive

A New Framework

Coverage: Those Hard-to-reach Places

Results

Future

Time Better Spent...

Try the following:

valgrind

talloc

findstatic.pl

Time Worse Spent...

Do NOT try the following:

Wesnoth

The Old Testsuite & A New Incentive

Testing original netfilter code circa 1999

Shell scripts placed in subdirectories

C helpers:

gen_ip <src> <dst> <len> <prot> ...

rcv_ip <wait time> <num expected>

gen_err <src> <type> <code>

drop_invalid.o

The Old Testsuite & A New Incentive

#! /bin/sh

# ICMP error test.

set -m

load_module tools/drop_invalid hook=0

pkt=”TAP0NET.2 $TAP1NET.2 100 6 1024 1025 SYN”

tools/gen_ip $pkt > /dev/tap0

tools/rcv_ip 2 1 < /dev/tap0 > $TMPFILE &

sleep 1

tools/gen_ip $pkt | tools/gen_err $TAP1NET.2 3 0 > /dev/tap1

if wait %tools/rcv_ip; then :

else

echo ICMP rcv failed; exit 1

fi

A New Incentive

The NAT code has one FIXME too many...

Itching to do the Great Rewrite

New Testsuite Wishlist

Trivial to run

Easy to write new tests

Written in a language the developers understand

Should encourage the use of modern debugging tools

Reasonable and measurable coverage

Must make developers want to use it

Trivial To Run

cd nfsim-testsuite

./test-kernel-source ~/devel/kernel/linux-2.6.11

Kernel source does not need to be already built.

Do not need to run as root

Copies .config (filtered) if available.

Demonstration...

Easy To Write New Tests

# XFAIL:linux:<2.6.0

# expect to see “rcv:eth0” as output the next time we run gen_ip

expect gen_ip rcv:eth0

# also expect “send:LOCAL ...”

expect gen_ip send:LOCAL {IPv4 192.168.0.2 192.168.0.1 0 17 3 4}

# generate the packet

# - arriving on eth0

# - addressed to the local machine, udp port 4

# - from 192.168.0.2, udp port 3

gen_ip IF=eth0 192.168.0.2 192.168.0.1 0 udp 3 4

Written in a Familiar Language

C

One True Brace Style

Modern Debugging Tools

./test-kernel-source --valgrind ~/devel/kernel/linux-2.6.11

Reasonable And Measurable Coverage

gcov is your friend

More on coverage later...

Making Developers Want To Use It

FIXME: Say something nice here about fellow developers.

How It Works

How It Works: nfsim

Testsuite is wrapper around nfsim program

Implements kernel API in userspace, plus command-line interface.

Process:

Import ipv4/netfilter/* from a kernel tree

Create symlink farm from .../include/linux/* to nfsim/kernelenv.h

Compile nfsim

Feed *.sim scripts to “nfsim -e” until one fails.

Run *.sh scripts

Reimplement or Import?

Reimplementation

+ Greater control, debugging checks

- More code to maintain

- May differ from kernel implementation

Invalid test results?

Importing

+ Identical behaviour to kernel

- May require other code to be imported or reimplemented.

nfsim: Framework Diagram

We drew the line at the netfilter hook boundary:

nf_register_hook, nf_register_sockopt etc.

Supporting External Tools

Typical user interaction with netfilter code is through iptables

nfsim has to implement an “iptables” command

Import or reimplement?

Neither

Supporting External Tools

Use an unmodified iptables

Intercept calls to kernel

sockopt and /proc interfaces

Divert these to nfsim

Shared library provides the 'fake' calls

LD_PRELOAD=fakesockopt.so /sbin/iptables -L

Superuser privileges not required

Increasing Coverage

From ip_tables.c:

counters = vmalloc(tmp.num_counters *

sizeof(struct ipt_counters));

if (!counters) {

ret = -ENOMEM;

goto free_newinfo;

}

Increasing Coverage

From ip_tables.c:

counters = vmalloc(tmp.num_counters *

sizeof(struct ipt_counters));

if (!counters) {

ret = -ENOMEM;

goto free_newinfo;

}

Increasing Coverage

Need to cover both cases – vmalloc() success & failure

Many of these “decision points” per operation

Other risky functions:

all memory allocations

copy_to_user & copy_from_user

proc registration functions

down_interruptible on semaphores

Results in a binary tree of possible execution paths

Combinatorial explosion!

Increasing Coverage

Failure cases are implemented using should_i_fail():

/* nfsim implementation of vmalloc() */

void *vmalloc(unsigned long size)

{

void *ptr;

if (should_i_fail(__func__))

return NULL;

if (!(ptr = malloc(size)))

barf(“malloc failure”);

return ptr;

}

Exhaustive Error Testing – The Implementation

Based on fork()

fork() when we reach an error-prone function

Child executes failure condition

Parent executes success condition

Creates a tree of processes mirroring the tree of decisions

Reproducing errors

If we see a failure, print the path to this case and exit

Path can be replayed with the --failpattern argument

Unix fork() semantics do the hard work for us

Two Types of Errors

In the failure condition we can't expect a test to pass

eg. dropping a packet due to an allocation failure

We divide errors into two cases

Test failures

eg. expected output is not seen

Code failures

SEGV, resource leaks

Ignore test failures when the path includes a failure case

However, the failure case is expected to complete gracefully

Combinatorial Explosion

Doesn't happen

Failing an operation causes test to fail almost immediately

eg. expecting to see packet come out other side will fail.

We warn if we're still going after three failures

This actually improved our testsuite...

Combinatorial Explosion

Usually explode because a test is expecting failure, but too imprecise about how it will fail:

# --tcp-reset needs -p tcp
expect iptables iptables: command failed
iptables -A INPUT -j REJECT --reject-with tcp-reset

In this case, kernel will return -EINVAL: check for it

strace
expect iptables setsockopt -> -EINVAL
expect iptables iptables: command failed
iptables -A INPUT -j REJECT --reject-with tcp-reset

Failure Testing with External Programs

Communicating with iptables during a failure test

Both parent and child hold a pipe to the same iptables process

boom!

At present:

Record the messages exchanged with the iptables process

On fork:

spawn a new iptables

replay the recorded session

In progress:

Fork iptables with nfsim

Demonstration: Failure

...

Results

Coverage increase isn't large:

Full regression test: 61%

With --failtest: 65%

However, we're now testing the hard-to-reach places without writing new tests!

Results

Each failure case may double the previous testing time

Full regression test: 5 seconds

Results

Each failure case may double the previous testing time

Full regression test: 5 seconds

With --failtest: 7½ minutes

Results

Each failure case may double the previous testing time

Full regression test: 5 seconds

With --failtest: 7½ minutes

With --valgrind: 3 minutes

Results: The Great Big Hammer

./test-kernel-source --valgrind --failtest

Results: The Great Big Hammer

./test-kernel-source --valgrind --failtest

18½ hours later...

How nfsim Has Helped

Results: How nfsim Has Helped

--- linux/net/ipv4/netfilter/ip_nat_core.c

+++ linux/net/ipv4/netfilter/ip_nat_core.c

@@ -466,7 +466,7 @@

struct iphdr *iph;

(*pskb)->nfcache |= NFC_ALTERED;

-	if (!skb_ip_make_writable(pskb, iphdroff+sizeof(iph)))

+	if (!skb_ip_make_writable(pskb, iphdroff+sizeof(*iph)))

return 0;

iph = (void *)(*pskb)->data + iphdroff;

Results: How nfsim Has Helped

--- linux/net/ipv4/netfilter/ip_conntrack_standalone.c

+++ linux/net/ipv4/netfilter/ip_conntrack_standalone.c

@@ -741,6 +741,7 @@

goto cleanup_nothing;

#ifdef CONFIG_PROC_FS

+	ret = -ENOMEM;

proc = proc_net_fops_create("ip_conntrack", 0440, &ct_file_ops);

if (!proc) goto cleanup_init;

Where to now: nfsim ideas?

vampire script which runs on your machine

Writes nfsim commands to reflect your machine's environment

Interfaces, routes, firewall rules

Allows testing and diagnosis of problems

GUI based on nfsim?

Multiple nfsim machines in a virtual network for testing?

Firewall writing/testing based on what traffic should be allowed

nfsim-like interface for real (qemu?) machines

Run same testsuite on real machine

Controlling time will be difficult on real machine

Where to now: kernsim?

Expand nfsim to cover other areas of the kernel

Provide 'blocks' of functionality

SCSI, VFS, block layer, IPv4 routing code

Modified for instrumentation & testing

A simulator build consists of imported parts and simulated parts

Issues

Need to create clean divisions of functionality

Which parts require reimplementing?

Antipathy to testing?

Legal Stuff

This work represents the view of the authors and does not necessarily represent the view of IBM.

Linux is a registered trademark of Linus Torvalds.

Other company, product, and service names may be trademarks or service marks of others.

IB

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Mention the greater confidence in updates & rewrites

Introductory demo:

./configure

import from standard kernel tree

make

./simulator

show inits

help

ifconfig, route, proc

info hooks

gen_ip

ifconfig again? info rcache?

“code in red (and possibly free_newinfo) will never be tested unless vmalloc fails”

This isn't genuine nfsim(tm) code!

Explain wait()ing here?

mention should_i_fail_once() ?

mention should_i_fail_once() ?

mention should_i_fail_once() ?

mention should_i_fail_once() ?

nfsim - Untested code is buggy code

Sheila Harnett

2003-04-09T12:23:22