[PATCH 3/3] KVM: x86 emulator: fuzz tester

[Avi Kivity <avi@redhat.com>]

The x86 emulator is directly exposed to guest code; therefore it is part
of the directly exposed attack surface.  To reduce the risk of
vulnerabilities, this patch adds a fuzz test that runs random instructions
through the emulator.  A vulnerability will usually result in an oops.

One way to run the test is via KVM itself:

  qemu -enable-kvm -smp 4 -serial stdio -kernel bzImage \
      -append 'console=ttyS0 test_emulator.iterations=1000000000'

this requires that the test module be built into the kernel.

Signed-off-by: Avi Kivity <avi@redhat.com>
---
 arch/x86/Kbuild              |    1 +
 arch/x86/kvm/Kconfig         |   11 +
 arch/x86/kvm/Makefile        |    1 +
 arch/x86/kvm/test-emulator.c |  533 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 546 insertions(+), 0 deletions(-)
 create mode 100644 arch/x86/kvm/test-emulator.c

diff --git a/arch/x86/Kbuild b/arch/x86/Kbuild
index 0e9dec6..0d80e6f 100644
--- a/arch/x86/Kbuild
+++ b/arch/x86/Kbuild
@@ -1,5 +1,6 @@
 
 obj-$(CONFIG_KVM) += kvm/
+obj-$(CONFIG_KVM_EMULATOR_TEST) += kvm/
 
 # Xen paravirtualization support
 obj-$(CONFIG_XEN) += xen/
diff --git a/arch/x86/kvm/Kconfig b/arch/x86/kvm/Kconfig
index ff5790d..9ffc30a 100644
--- a/arch/x86/kvm/Kconfig
+++ b/arch/x86/kvm/Kconfig
@@ -76,6 +76,17 @@ config KVM_MMU_AUDIT
 	 This option adds a R/W kVM module parameter 'mmu_audit', which allows
 	 audit  KVM MMU at runtime.
 
+config KVM_EMULATOR_TEST
+        tristate "KVM emulator self test"
+	depends on KVM
+	---help---
+	 Build test code that checks the x86 emulator during boot or module
+         insertion.  If built as a module, it will be called test-emulator.ko.
+
+	 The emulator test will run for as many iterations as are specified by
+         the emulator_test.iterations parameter; all processors will be
+         utilized.  When the test is complete, results are reported in dmesg.
+
 # OK, it's a little counter-intuitive to do this, but it puts it neatly under
 # the virtualization menu.
 source drivers/vhost/Kconfig
diff --git a/arch/x86/kvm/Makefile b/arch/x86/kvm/Makefile
index f15501f..fc4a9e2 100644
--- a/arch/x86/kvm/Makefile
+++ b/arch/x86/kvm/Makefile
@@ -19,3 +19,4 @@ kvm-amd-y		+= svm.o
 obj-$(CONFIG_KVM)	+= kvm.o
 obj-$(CONFIG_KVM_INTEL)	+= kvm-intel.o
 obj-$(CONFIG_KVM_AMD)	+= kvm-amd.o
+obj-$(CONFIG_KVM_EMULATOR_TEST) += test-emulator.o
diff --git a/arch/x86/kvm/test-emulator.c b/arch/x86/kvm/test-emulator.c
new file mode 100644
index 0000000..1e3a22f
--- /dev/null
+++ b/arch/x86/kvm/test-emulator.c
@@ -0,0 +1,533 @@
+/*
+ * x86 instruction emulator test
+ *
+ * Copyright 2011 Red Hat, Inc. and/or its affiliates.
+ *
+ * Authors:
+ *   Avi Kivity   <avi@redhat.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/random.h>
+#include <asm/kvm_host.h>
+#include <asm/kvm_emulate.h>
+#include <asm/i387.h>
+
+static ulong iterations = 0;
+module_param(iterations, ulong, S_IRUGO);
+
+struct test_context {
+	struct work_struct work;
+	struct completion completion;
+	struct x86_emulate_ctxt ctxt;
+	struct test_context *next;
+	bool failed;
+	u8 insn[15];
+	bool insn_base_valid;
+	ulong insn_base;
+	struct test_seg {
+		u16 selector;
+		struct desc_struct desc;
+		u32 base3;
+		bool valid;
+	} segs[8];
+	ulong iterations;
+	ulong completed;
+	ulong decoded;
+	ulong emulated;
+	ulong nofault;
+	ulong failures;
+};
+
+static u64 random64(void)
+{
+	return random32() | ((u64)random32() << 32);
+}
+
+static ulong randlong(void)
+{
+	if (sizeof(ulong) == sizeof(u32))
+		return random32();
+	else
+		return random64();
+}
+
+static struct test_context *to_test(struct x86_emulate_ctxt *ctxt)
+{
+	return container_of(ctxt, struct test_context, ctxt);
+}
+
+static void fail(struct x86_emulate_ctxt *ctxt, const char *msg, ...)
+	__attribute__((format(printf, 2, 3)));
+
+static void fail(struct x86_emulate_ctxt *ctxt, const char *msg, ...)
+{
+	va_list args;
+	char s[200];
+
+	va_start(args, msg);
+	vsnprintf(s, sizeof(s), msg, args);
+	va_end(args);
+	printk("emulator test failure: %s\n", s);
+	to_test(ctxt)->failed = true;
+}
+
+static int test_fill_exception(struct x86_exception *ex)
+{
+	if (random32() % 4 == 0) {
+		if (ex) {
+			ex->vector = random32();
+			ex->error_code_valid = random32();
+			ex->error_code = random32();
+			ex->nested_page_fault = random32();
+			ex->address = random64();
+		}
+		return X86EMUL_PROPAGATE_FAULT;
+	}
+	return X86EMUL_CONTINUE;
+}
+
+static int rand_error(void)
+{
+	switch (random32() % 8) {
+	case 0: return X86EMUL_UNHANDLEABLE;
+	case 1: return X86EMUL_IO_NEEDED;
+	default: return X86EMUL_CONTINUE;
+	}
+}
+
+static int test_read(struct x86_emulate_ctxt *ctxt,
+		     unsigned long addr, void *val,
+		     unsigned int bytes,
+		     struct x86_exception *fault)
+{
+	unsigned i;
+
+	if (bytes > 32 || bytes == 0)
+		fail(ctxt, "read %x bytes", bytes);
+
+	for (i = 0; i < bytes; ++i)
+		*(u8 *)(val + i) = random32();
+
+	return test_fill_exception(fault);
+}
+
+static int test_write(struct x86_emulate_ctxt *ctxt,
+		      unsigned long addr, const void *val, unsigned int bytes,
+		      struct x86_exception *fault)
+{
+	if (bytes > 32 || bytes == 0)
+		fail(ctxt, "write %x bytes", bytes);
+
+	return test_fill_exception(fault);
+}
+
+static int test_fetch(struct x86_emulate_ctxt *ctxt,
+		      unsigned long addr, void *val,
+		      unsigned int bytes,
+		      struct x86_exception *fault)
+{
+	struct test_context *test = to_test(ctxt);
+
+	if (bytes > 15 || bytes == 0)
+		fail(ctxt, "fetch %x bytes", bytes);
+
+	if (!test->insn_base_valid) {
+		test->insn_base_valid = true;
+		test->insn_base = addr;
+	}
+	addr -= test->insn_base;
+	if (addr >= 15 || addr + bytes > 15)
+		fail(ctxt, "fetch %x from %lx vs %lx",
+		     bytes, addr + test->insn_base, test->insn_base);
+	else
+		memcpy(val, test->insn + addr, bytes);
+
+	return test_fill_exception(fault);
+}
+
+static int test_cmpxchg(struct x86_emulate_ctxt *ctxt,
+			unsigned long addr,
+			const void *old,
+			const void *new,
+			unsigned int bytes,
+			struct x86_exception *fault)
+{
+	if (bytes > 16 || bytes == 0 || hweight32(bytes) != 1)
+		fail(ctxt, "cmpxchg %x bytes", bytes);
+
+	return test_fill_exception(fault);
+}
+
+static void test_invlpg(struct x86_emulate_ctxt *ctxt, ulong addr)
+{
+}
+
+static int test_pio_in(struct x86_emulate_ctxt *ctxt,
+		       int size, unsigned short port, void *val,
+		       unsigned int count)
+{
+	if ((size != 1 && size != 2 && size != 4)
+	    || (count == 0 || count * size > 4096))
+		fail(ctxt, "pio_in_emulated: size %x count %x\n", size, count);
+
+	return rand_error();
+}
+
+static int test_pio_out(struct x86_emulate_ctxt *ctxt,
+			int size, unsigned short port, const void *val,
+			unsigned int count)
+{
+	if ((size != 1 && size != 2 && size != 4)
+	    || (count == 0 || count * size > 4096))
+		fail(ctxt, "pio_out_emulated: size %x count %x\n", size, count);
+
+	return rand_error();
+}
+
+static bool test_get_segment(struct x86_emulate_ctxt *ctxt, u16 *selector,
+			     struct desc_struct *desc, u32 *base3, int seg)
+{
+	struct test_context *test = to_test(ctxt);
+	struct test_seg *s = &test->segs[seg];
+
+	if (seg < 0 || seg > 7)
+		fail(ctxt, "bad segment %d\n", seg);
+
+	if (!s->valid) {
+		s->valid = true;
+		s->selector = random32();
+		s->desc.a = random32();
+		s->desc.b = random32();
+		s->base3 = random32();
+	}
+
+	*selector = s->selector;
+	desc->a = s->desc.a;
+	desc->b = s->desc.b;
+	if (base3)
+		*base3 = s->base3;
+
+	return random32() & 1;
+}
+
+static void test_set_segment(struct x86_emulate_ctxt *ctxt, u16 selector,
+			     struct desc_struct *desc, u32 base3, int seg)
+{
+	if (seg < 0 || seg > 5)
+		fail(ctxt, "bad segment %d\n", seg);
+}
+
+static ulong segment_base(struct x86_emulate_ctxt *ctxt,
+			  struct desc_struct *d, u32 base3)
+{
+	unsigned long v;
+
+	v = get_desc_base(d);
+	if (ctxt->mode == X86EMUL_MODE_PROT64
+	    && d->s == 0 && (d->type == 2 || d->type == 9 || d->type == 11))
+		v |= (u64)base3 << 32;
+	return v;
+}
+
+static unsigned long test_get_cached_segment_base(struct x86_emulate_ctxt *ctxt,
+						  int seg)
+{
+	u16 selector;
+	struct desc_struct desc;
+	u32 base3;
+
+	test_get_segment(ctxt, &selector, &desc, &base3, seg);
+	return segment_base(ctxt, &desc, base3);
+}
+
+static void test_get_desc_table(struct x86_emulate_ctxt *ctxt,
+				struct desc_ptr *dt)
+{
+	dt->size = random32();
+	dt->address = randlong();
+}
+
+static void test_set_desc_table(struct x86_emulate_ctxt *ctxt,
+				struct desc_ptr *dt)
+{
+}
+
+static bool valid_cr[] = {
+	[0] = true, [2] = true, [3] = true, [4] = true, [8] = true,
+};
+
+static void check_cr(struct x86_emulate_ctxt *ctxt, int cr)
+{
+	if (cr < 0 || cr > ARRAY_SIZE(valid_cr) || !valid_cr[cr])
+		fail(ctxt, "bad cr %d\n", cr);
+}
+
+static ulong test_get_cr(struct x86_emulate_ctxt *ctxt, int cr)
+{
+	check_cr(ctxt, cr);
+	return randlong();
+}
+
+static int test_set_cr(struct x86_emulate_ctxt *ctxt, int cr, ulong val)
+{
+	check_cr(ctxt, cr);
+	return random32() & 1;
+}
+
+static int test_cpl(struct x86_emulate_ctxt *ctxt)
+{
+	return random32() & 3;
+}
+
+static void check_dr(struct x86_emulate_ctxt *ctxt, int dr)
+{
+	if (dr < 0 || dr > 7)
+		fail(ctxt, "bad dr %d\n", dr);
+}
+
+static int test_get_dr(struct x86_emulate_ctxt *ctxt, int dr, ulong *dest)
+{
+	check_dr(ctxt, dr);
+	*dest = randlong();
+	return random32() & 1;
+}
+
+static int test_set_dr(struct x86_emulate_ctxt *ctxt, int dr, ulong value)
+{
+	check_dr(ctxt, dr);
+	return random32() & 1;
+}
+
+static int test_set_msr(struct x86_emulate_ctxt *ctxt, u32 msr_index, u64 data)
+{
+	return random32() & 1;
+}
+
+static int test_get_msr(struct x86_emulate_ctxt *ctxt, u32 msr_index,
+			u64 *pdata)
+{
+	*pdata = random64();
+	return random32() & 1;
+}
+
+static void test_halt(struct x86_emulate_ctxt *ctxt)
+{
+}
+
+static void test_wbinvd(struct x86_emulate_ctxt *ctxt)
+{
+}
+
+static int test_fix_hypercall(struct x86_emulate_ctxt *ctxt)
+{
+	return rand_error();
+}
+
+static void test_get_fpu(struct x86_emulate_ctxt *ctxt)
+{
+	kernel_fpu_begin();
+	/* FIXME: randomize state? */
+}
+
+static void test_put_fpu(struct x86_emulate_ctxt *ctxt)
+{
+	kernel_fpu_end();
+}
+
+static int test_intercept(struct x86_emulate_ctxt *ctxt,
+			  struct x86_instruction_info *info,
+			  enum x86_intercept_stage stage)
+{
+	return X86EMUL_CONTINUE;
+}
+
+static struct x86_emulate_ops test_ops = {
+	.read_std = test_read,
+	.write_std = test_write,
+	.fetch = test_fetch,
+	.read_emulated = test_read,
+	.write_emulated = test_write,
+	.cmpxchg_emulated = test_cmpxchg,
+	.invlpg = test_invlpg,
+	.pio_in_emulated = test_pio_in,
+	.pio_out_emulated = test_pio_out,
+	.get_segment = test_get_segment,
+	.set_segment = test_set_segment,
+	.get_cached_segment_base = test_get_cached_segment_base,
+	.get_gdt = test_get_desc_table,
+	.get_idt = test_get_desc_table,
+	.set_gdt = test_set_desc_table,
+	.set_idt = test_set_desc_table,
+	.get_cr = test_get_cr,
+	.set_cr = test_set_cr,
+	.cpl = test_cpl,
+	.get_dr = test_get_dr,
+	.set_dr = test_set_dr,
+	.set_msr = test_set_msr,
+	.get_msr = test_get_msr,
+	.halt = test_halt,
+	.wbinvd = test_wbinvd,
+	.fix_hypercall = test_fix_hypercall,
+	.get_fpu = test_get_fpu,
+	.put_fpu = test_put_fpu,
+	.intercept = test_intercept,
+};
+
+static int modes[] = {
+	X86EMUL_MODE_REAL,
+	X86EMUL_MODE_VM86,
+	X86EMUL_MODE_PROT16,
+	X86EMUL_MODE_PROT32,
+	X86EMUL_MODE_PROT64,
+};
+
+static int test_emulator_one(struct test_context *test)
+{
+	struct x86_emulate_ctxt *ctxt = &test->ctxt;
+	unsigned i;
+	int r;
+
+	test->failed = false;
+	i = 0;
+	if (random32() & 1)
+		test->insn[i++] = 0x0f;
+	for (; i < 15; ++i)
+		test->insn[i++] = random32();
+	test->insn_base_valid = false;
+	ctxt->ops = &test_ops;
+	ctxt->eflags = randlong();
+	ctxt->eip = randlong();
+	ctxt->mode = modes[random32() % ARRAY_SIZE(modes)];
+	ctxt->guest_mode = random32() % 16 == 0;
+	ctxt->perm_ok = random32() % 16 == 0;
+	ctxt->only_vendor_specific_insn = random32() % 64 == 0;
+	memset(&ctxt->twobyte, 0,
+	       (void *)&ctxt->regs - (void *)&ctxt->twobyte);
+	for (i = 0; i < NR_VCPU_REGS; ++i)
+		ctxt->regs[i] = randlong();
+	r = x86_decode_insn(ctxt, NULL, 0);
+	if (r == EMULATION_OK) {
+		++test->decoded;
+		r = x86_emulate_insn(ctxt);
+		if (r == EMULATION_OK) {
+			++test->emulated;
+			if (!ctxt->have_exception)
+				++test->nofault;
+		}
+	}
+
+	++test->completed;
+
+	return test->failed ? -EINVAL : 0;
+}
+
+static const char *regnames[] = {
+	[VCPU_REGS_RAX] = "rax",
+	[VCPU_REGS_RBX] = "rbx",
+	[VCPU_REGS_RCX] = "rcx",
+	[VCPU_REGS_RDX] = "rdx",
+	[VCPU_REGS_RSI] = "rsi",
+	[VCPU_REGS_RDI] = "rdi",
+	[VCPU_REGS_RSP] = "rsp",
+	[VCPU_REGS_RBP] = "rbp",
+	[VCPU_REGS_R8] = "r8",
+	[VCPU_REGS_R9] = "r9",
+	[VCPU_REGS_R10] = "r10",
+	[VCPU_REGS_R11] = "r11",
+	[VCPU_REGS_R12] = "r12",
+	[VCPU_REGS_R13] = "r13",
+	[VCPU_REGS_R14] = "r14",
+	[VCPU_REGS_R15] = "r15",
+	[VCPU_REGS_RIP] = "rip",
+};
+
+static void dump_test_context(struct test_context *test)
+{
+	unsigned i;
+
+	printk("instruction: %02x %02x %02x %02x %02x %02x %02x %02x"
+	       " %02x %02x %02x %02x %02x %02x %02x\n",
+	       test->insn[0], test->insn[1], test->insn[2], test->insn[3],
+	       test->insn[4], test->insn[5], test->insn[6], test->insn[7],
+	       test->insn[8], test->insn[9], test->insn[10], test->insn[11],
+	       test->insn[12], test->insn[13], test->insn[14]);
+	for (i = 0; i < NR_VCPU_REGS; ++i)
+		printk("  %s: %016llx\n", regnames[i], (u64)test->ctxt.regs[i]);
+}
+
+static void test_emulator_thread(struct work_struct *work)
+{
+	int i, ret;
+	struct test_context *test
+		= container_of(work, struct test_context, work);
+
+	for (i = 0, ret = 0; i < test->iterations && ret == 0; ++i) {
+		ret = test_emulator_one(test);
+		cond_resched();
+	}
+
+	if (ret) {
+		++test->failures;
+		printk("test failure in instruction %i\n", i);
+		dump_test_context(test);
+	}
+
+	complete(&test->completion);
+}
+
+static __init int test_emulator(void)
+{
+	int r, cpu, remain;
+	struct test_context *test = NULL, *tmp;
+	ulong completed = 0, decoded = 0, emulated = 0, nofault = 0;
+	ulong failures = 0;
+
+	if (!iterations)
+		return 0;
+
+	pr_info("starting emulator test\n");
+	remain = num_online_cpus();
+	for_each_online_cpu(cpu) {
+		tmp = kzalloc(sizeof(*tmp), GFP_KERNEL);
+		r = -ENOMEM;
+		if (!tmp)
+			break;
+		tmp->next = test;
+		test = tmp;
+		test->iterations = iterations / remain--;
+		iterations -= test->iterations;
+		INIT_WORK(&test->work, test_emulator_thread);
+		init_completion(&test->completion);
+		schedule_work_on(cpu, &test->work);
+	}
+	while (test) {
+		wait_for_completion(&test->completion);
+		completed += test->completed;
+		decoded += test->decoded;
+		emulated += test->emulated;
+		nofault += test->nofault;
+		failures += test->failures;
+		tmp = test;
+		test = test->next;
+		kfree(tmp);
+	}
+	pr_info("emulator fuzz test results\n");
+	pr_info("  instructions:   %12ld\n", completed);
+	pr_info("  decoded:        %12ld\n", decoded);
+	pr_info("  emulated:       %12ld\n", emulated);
+	pr_info("  nofault:        %12ld\n", nofault);
+	pr_info("  failures:       %12ld\n", failures);
+	if (failures || remain)
+		pr_err("emulator test: FAIL\n");
+	else
+		pr_info("emulator test: PASS\n");
+	return 0;
+}
+
+module_init(test_emulator)
-- 
1.7.5.3