Check in gVisor.

PiperOrigin-RevId: 194583126
Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463

9 files changed, 2150 insertions, 0 deletions

diff --git a/pkg/bpf/BUILD b/pkg/bpf/BUILD
new file mode 100644
index 000000000..d4f12f13a
--- /dev/null
+++ b/pkg/bpf/BUILD
@@ -0,0 +1,46 @@
+package(licenses = ["notice"])  # Apache 2.0
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_stateify:defs.bzl", "go_stateify")
+
+go_stateify(
+    name = "bpf_state",
+    srcs = [
+        "interpreter.go",
+    ],
+    out = "bpf_state.go",
+    package = "bpf",
+)
+
+go_library(
+    name = "bpf",
+    srcs = [
+        "bpf.go",
+        "bpf_state.go",
+        "decoder.go",
+        "input_bytes.go",
+        "interpreter.go",
+        "program_builder.go",
+    ],
+    importpath = "gvisor.googlesource.com/gvisor/pkg/bpf",
+    visibility = ["//visibility:public"],
+    deps = [
+        "//pkg/abi/linux",
+        "//pkg/state",
+    ],
+)
+
+go_test(
+    name = "bpf_test",
+    size = "small",
+    srcs = [
+        "decoder_test.go",
+        "interpreter_test.go",
+        "program_builder_test.go",
+    ],
+    embed = [":bpf"],
+    deps = [
+        "//pkg/abi/linux",
+        "//pkg/binary",
+    ],
+)
diff --git a/pkg/bpf/bpf.go b/pkg/bpf/bpf.go
new file mode 100644
index 000000000..757744090
--- /dev/null
+++ b/pkg/bpf/bpf.go
@@ -0,0 +1,129 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Package bpf provides tools for working with Berkeley Packet Filter (BPF)
+// programs. More information on BPF can be found at
+// https://www.freebsd.org/cgi/man.cgi?bpf(4)
+package bpf
+
+import "gvisor.googlesource.com/gvisor/pkg/abi/linux"
+
+const (
+	// MaxInstructions is the maximum number of instructions in a BPF program,
+	// and is equal to Linux's BPF_MAXINSNS.
+	MaxInstructions = 4096
+
+	// ScratchMemRegisters is the number of M registers in a BPF virtual machine,
+	// and is equal to Linux's BPF_MEMWORDS.
+	ScratchMemRegisters = 16
+)
+
+// Parts of a linux.BPFInstruction.OpCode. Compare to the Linux kernel's
+// include/uapi/linux/filter.h.
+//
+// In the comments below:
+//
+// - A, X, and M[] are BPF virtual machine registers.
+//
+// - K refers to the instruction field linux.BPFInstruction.K.
+//
+// - Bits are counted from the LSB position.
+const (
+	// Instruction class, stored in bits 0-2.
+	Ld                   = 0x00 // load into A
+	Ldx                  = 0x01 // load into X
+	St                   = 0x02 // store from A
+	Stx                  = 0x03 // store from X
+	Alu                  = 0x04 // arithmetic
+	Jmp                  = 0x05 // jump
+	Ret                  = 0x06 // return
+	Misc                 = 0x07
+	instructionClassMask = 0x07
+
+	// Size of a load, stored in bits 3-4.
+	W            = 0x00 // 32 bits
+	H            = 0x08 // 16 bits
+	B            = 0x10 // 8 bits
+	loadSizeMask = 0x18
+
+	// Source operand for a load, stored in bits 5-7.
+	// Address mode numbers in the comments come from Linux's
+	// Documentation/networking/filter.txt.
+	Imm          = 0x00 // immediate value K (mode 4)
+	Abs          = 0x20 // data in input at byte offset K (mode 1)
+	Ind          = 0x40 // data in input at byte offset X+K (mode 2)
+	Mem          = 0x60 // M[K] (mode 3)
+	Len          = 0x80 // length of the input in bytes ("BPF extension len")
+	Msh          = 0xa0 // 4 * lower nibble of input at byte offset K (mode 5)
+	loadModeMask = 0xe0
+
+	// Source operands for arithmetic, jump, and return instructions.
+	// Arithmetic and jump instructions can use K or X as source operands.
+	// Return instructions can use K or A as source operands.
+	K             = 0x00 // still mode 4
+	X             = 0x08 // mode 0
+	A             = 0x10 // mode 9
+	srcAluJmpMask = 0x08
+	srcRetMask    = 0x18
+
+	// Arithmetic instructions, stored in bits 4-7.
+	Add     = 0x00
+	Sub     = 0x10 // A - src
+	Mul     = 0x20
+	Div     = 0x30 // A / src
+	Or      = 0x40
+	And     = 0x50
+	Lsh     = 0x60 // A << src
+	Rsh     = 0x70 // A >> src
+	Neg     = 0x80 // -A (src ignored)
+	Mod     = 0x90 // A % src
+	Xor     = 0xa0
+	aluMask = 0xf0
+
+	// Jump instructions, stored in bits 4-7.
+	Ja      = 0x00 // unconditional (uses K for jump offset)
+	Jeq     = 0x10 // if A == src
+	Jgt     = 0x20 // if A > src
+	Jge     = 0x30 // if A >= src
+	Jset    = 0x40 // if (A & src) != 0
+	jmpMask = 0xf0
+
+	// Miscellaneous instructions, stored in bits 3-7.
+	Tax      = 0x00 // A = X
+	Txa      = 0x80 // X = A
+	miscMask = 0xf8
+
+	// Masks for bits that should be zero.
+	unusedBitsMask      = 0xff00 // all valid instructions use only bits 0-7
+	storeUnusedBitsMask = 0xf8   // stores only use instruction class
+	retUnusedBitsMask   = 0xe0   // returns only use instruction class and source operand
+)
+
+// Stmt returns a linux.BPFInstruction representing a BPF non-jump instruction.
+func Stmt(code uint16, k uint32) linux.BPFInstruction {
+	return linux.BPFInstruction{
+		OpCode: code,
+		K:      k,
+	}
+}
+
+// Jump returns a linux.BPFInstruction representing a BPF jump instruction.
+func Jump(code uint16, k uint32, jt, jf uint8) linux.BPFInstruction {
+	return linux.BPFInstruction{
+		OpCode:      code,
+		JumpIfTrue:  jt,
+		JumpIfFalse: jf,
+		K:           k,
+	}
+}
diff --git a/pkg/bpf/decoder.go b/pkg/bpf/decoder.go
new file mode 100644
index 000000000..6873ffa5c
--- /dev/null
+++ b/pkg/bpf/decoder.go
@@ -0,0 +1,248 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"bytes"
+	"fmt"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+// DecodeProgram translates an array of BPF instructions into text format.
+func DecodeProgram(program []linux.BPFInstruction) (string, error) {
+	var ret bytes.Buffer
+	for line, s := range program {
+		ret.WriteString(fmt.Sprintf("%v: ", line))
+		if err := decode(s, line, &ret); err != nil {
+			return "", err
+		}
+		ret.WriteString("\n")
+	}
+	return ret.String(), nil
+}
+
+// Decode translates BPF instruction into text format.
+func Decode(inst linux.BPFInstruction) (string, error) {
+	var ret bytes.Buffer
+	err := decode(inst, -1, &ret)
+	return ret.String(), err
+}
+
+func decode(inst linux.BPFInstruction, line int, w *bytes.Buffer) error {
+	var err error
+	switch inst.OpCode & instructionClassMask {
+	case Ld:
+		err = decodeLd(inst, w)
+	case Ldx:
+		err = decodeLdx(inst, w)
+	case St:
+		w.WriteString(fmt.Sprintf("M[%v] <- A", inst.K))
+	case Stx:
+		w.WriteString(fmt.Sprintf("M[%v] <- X", inst.K))
+	case Alu:
+		err = decodeAlu(inst, w)
+	case Jmp:
+		err = decodeJmp(inst, line, w)
+	case Ret:
+		err = decodeRet(inst, w)
+	case Misc:
+		err = decodeMisc(inst, w)
+	default:
+		return fmt.Errorf("invalid BPF instruction: %v", inst)
+	}
+	return err
+}
+
+// A <- P[k:4]
+func decodeLd(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	w.WriteString("A <- ")
+
+	switch inst.OpCode & loadModeMask {
+	case Imm:
+		w.WriteString(fmt.Sprintf("%v", inst.K))
+	case Abs:
+		w.WriteString(fmt.Sprintf("P[%v:", inst.K))
+		if err := decodeLdSize(inst, w); err != nil {
+			return err
+		}
+		w.WriteString("]")
+	case Ind:
+		w.WriteString(fmt.Sprintf("P[X+%v:", inst.K))
+		if err := decodeLdSize(inst, w); err != nil {
+			return err
+		}
+		w.WriteString("]")
+	case Mem:
+		w.WriteString(fmt.Sprintf("M[%v]", inst.K))
+	case Len:
+		w.WriteString("len")
+	default:
+		return fmt.Errorf("invalid BPF LD instruction: %v", inst)
+	}
+	return nil
+}
+
+func decodeLdSize(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	switch inst.OpCode & loadSizeMask {
+	case W:
+		w.WriteString("4")
+	case H:
+		w.WriteString("2")
+	case B:
+		w.WriteString("1")
+	default:
+		return fmt.Errorf("Invalid BPF LD size: %v", inst)
+	}
+	return nil
+}
+
+// X <- P[k:4]
+func decodeLdx(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	w.WriteString("X <- ")
+
+	switch inst.OpCode & loadModeMask {
+	case Imm:
+		w.WriteString(fmt.Sprintf("%v", inst.K))
+	case Mem:
+		w.WriteString(fmt.Sprintf("M[%v]", inst.K))
+	case Len:
+		w.WriteString("len")
+	case Msh:
+		w.WriteString(fmt.Sprintf("4*(P[%v:1]&0xf)", inst.K))
+	default:
+		return fmt.Errorf("invalid BPF LDX instruction: %v", inst)
+	}
+	return nil
+}
+
+// A <- A + k
+func decodeAlu(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	code := inst.OpCode & aluMask
+	if code == Neg {
+		w.WriteString("A <- -A")
+		return nil
+	}
+
+	w.WriteString("A <- A ")
+	switch code {
+	case Add:
+		w.WriteString("+ ")
+	case Sub:
+		w.WriteString("- ")
+	case Mul:
+		w.WriteString("* ")
+	case Div:
+		w.WriteString("/ ")
+	case Or:
+		w.WriteString("| ")
+	case And:
+		w.WriteString("& ")
+	case Lsh:
+		w.WriteString("<< ")
+	case Rsh:
+		w.WriteString(">> ")
+	case Mod:
+		w.WriteString("% ")
+	case Xor:
+		w.WriteString("^ ")
+	default:
+		return fmt.Errorf("invalid BPF ALU instruction: %v", inst)
+	}
+	if err := decodeSource(inst, w); err != nil {
+		return err
+	}
+	return nil
+}
+
+func decodeSource(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	switch inst.OpCode & srcAluJmpMask {
+	case K:
+		w.WriteString(fmt.Sprintf("%v", inst.K))
+	case X:
+		w.WriteString("X")
+	default:
+		return fmt.Errorf("invalid BPF ALU/JMP source instruction: %v", inst)
+	}
+	return nil
+}
+
+// pc += (A > k) ? jt : jf
+func decodeJmp(inst linux.BPFInstruction, line int, w *bytes.Buffer) error {
+	code := inst.OpCode & jmpMask
+
+	w.WriteString("pc += ")
+	if code == Ja {
+		w.WriteString(printJmpTarget(inst.K, line))
+	} else {
+		w.WriteString("(A ")
+		switch code {
+		case Jeq:
+			w.WriteString("== ")
+		case Jgt:
+			w.WriteString("> ")
+		case Jge:
+			w.WriteString(">= ")
+		case Jset:
+			w.WriteString("& ")
+		default:
+			return fmt.Errorf("invalid BPF ALU instruction: %v", inst)
+		}
+		if err := decodeSource(inst, w); err != nil {
+			return err
+		}
+		w.WriteString(
+			fmt.Sprintf(") ? %s : %s",
+				printJmpTarget(uint32(inst.JumpIfTrue), line),
+				printJmpTarget(uint32(inst.JumpIfFalse), line)))
+	}
+	return nil
+}
+
+func printJmpTarget(target uint32, line int) string {
+	if line == -1 {
+		return fmt.Sprintf("%v", target)
+	}
+	return fmt.Sprintf("%v [%v]", target, int(target)+line+1)
+}
+
+// ret k
+func decodeRet(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	w.WriteString("ret ")
+
+	code := inst.OpCode & srcRetMask
+	switch code {
+	case K:
+		w.WriteString(fmt.Sprintf("%v", inst.K))
+	case A:
+		w.WriteString("A")
+	default:
+		return fmt.Errorf("invalid BPF RET source instruction: %v", inst)
+	}
+	return nil
+}
+
+func decodeMisc(inst linux.BPFInstruction, w *bytes.Buffer) error {
+	code := inst.OpCode & miscMask
+	switch code {
+	case Tax:
+		w.WriteString("X <- A")
+	case Txa:
+		w.WriteString("A <- X")
+	default:
+		return fmt.Errorf("invalid BPF ALU/JMP source instruction: %v", inst)
+	}
+	return nil
+}
diff --git a/pkg/bpf/decoder_test.go b/pkg/bpf/decoder_test.go
new file mode 100644
index 000000000..18709b944
--- /dev/null
+++ b/pkg/bpf/decoder_test.go
@@ -0,0 +1,146 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"testing"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+func TestDecode(t *testing.T) {
+	for _, test := range []struct {
+		filter   linux.BPFInstruction
+		expected string
+		fail     bool
+	}{
+		{filter: Stmt(Ld+Imm, 10), expected: "A <- 10"},
+		{filter: Stmt(Ld+Abs+W, 10), expected: "A <- P[10:4]"},
+		{filter: Stmt(Ld+Ind+H, 10), expected: "A <- P[X+10:2]"},
+		{filter: Stmt(Ld+Ind+B, 10), expected: "A <- P[X+10:1]"},
+		{filter: Stmt(Ld+Mem, 10), expected: "A <- M[10]"},
+		{filter: Stmt(Ld+Len, 0), expected: "A <- len"},
+		{filter: Stmt(Ldx+Imm, 10), expected: "X <- 10"},
+		{filter: Stmt(Ldx+Mem, 10), expected: "X <- M[10]"},
+		{filter: Stmt(Ldx+Len, 0), expected: "X <- len"},
+		{filter: Stmt(Ldx+Msh, 10), expected: "X <- 4*(P[10:1]&0xf)"},
+		{filter: Stmt(St, 10), expected: "M[10] <- A"},
+		{filter: Stmt(Stx, 10), expected: "M[10] <- X"},
+		{filter: Stmt(Alu+Add+K, 10), expected: "A <- A + 10"},
+		{filter: Stmt(Alu+Sub+K, 10), expected: "A <- A - 10"},
+		{filter: Stmt(Alu+Mul+K, 10), expected: "A <- A * 10"},
+		{filter: Stmt(Alu+Div+K, 10), expected: "A <- A / 10"},
+		{filter: Stmt(Alu+Or+K, 10), expected: "A <- A | 10"},
+		{filter: Stmt(Alu+And+K, 10), expected: "A <- A & 10"},
+		{filter: Stmt(Alu+Lsh+K, 10), expected: "A <- A << 10"},
+		{filter: Stmt(Alu+Rsh+K, 10), expected: "A <- A >> 10"},
+		{filter: Stmt(Alu+Mod+K, 10), expected: "A <- A % 10"},
+		{filter: Stmt(Alu+Xor+K, 10), expected: "A <- A ^ 10"},
+		{filter: Stmt(Alu+Add+X, 0), expected: "A <- A + X"},
+		{filter: Stmt(Alu+Sub+X, 0), expected: "A <- A - X"},
+		{filter: Stmt(Alu+Mul+X, 0), expected: "A <- A * X"},
+		{filter: Stmt(Alu+Div+X, 0), expected: "A <- A / X"},
+		{filter: Stmt(Alu+Or+X, 0), expected: "A <- A | X"},
+		{filter: Stmt(Alu+And+X, 0), expected: "A <- A & X"},
+		{filter: Stmt(Alu+Lsh+X, 0), expected: "A <- A << X"},
+		{filter: Stmt(Alu+Rsh+X, 0), expected: "A <- A >> X"},
+		{filter: Stmt(Alu+Mod+X, 0), expected: "A <- A % X"},
+		{filter: Stmt(Alu+Xor+X, 0), expected: "A <- A ^ X"},
+		{filter: Stmt(Alu+Neg, 0), expected: "A <- -A"},
+		{filter: Stmt(Jmp+Ja, 10), expected: "pc += 10"},
+		{filter: Jump(Jmp+Jeq+K, 10, 2, 5), expected: "pc += (A == 10) ? 2 : 5"},
+		{filter: Jump(Jmp+Jgt+K, 10, 2, 5), expected: "pc += (A > 10) ? 2 : 5"},
+		{filter: Jump(Jmp+Jge+K, 10, 2, 5), expected: "pc += (A >= 10) ? 2 : 5"},
+		{filter: Jump(Jmp+Jset+K, 10, 2, 5), expected: "pc += (A & 10) ? 2 : 5"},
+		{filter: Jump(Jmp+Jeq+X, 0, 2, 5), expected: "pc += (A == X) ? 2 : 5"},
+		{filter: Jump(Jmp+Jgt+X, 0, 2, 5), expected: "pc += (A > X) ? 2 : 5"},
+		{filter: Jump(Jmp+Jge+X, 0, 2, 5), expected: "pc += (A >= X) ? 2 : 5"},
+		{filter: Jump(Jmp+Jset+X, 0, 2, 5), expected: "pc += (A & X) ? 2 : 5"},
+		{filter: Stmt(Ret+K, 10), expected: "ret 10"},
+		{filter: Stmt(Ret+A, 0), expected: "ret A"},
+		{filter: Stmt(Misc+Tax, 0), expected: "X <- A"},
+		{filter: Stmt(Misc+Txa, 0), expected: "A <- X"},
+		{filter: Stmt(Ld+Ind+Msh, 0), fail: true},
+	} {
+		got, err := Decode(test.filter)
+		if test.fail {
+			if err == nil {
+				t.Errorf("Decode(%v) failed, expected: 'error', got: %q", test.filter, got)
+				continue
+			}
+		} else {
+			if err != nil {
+				t.Errorf("Decode(%v) failed for test %q, error: %q", test.filter, test.expected, err)
+				continue
+			}
+			if got != test.expected {
+				t.Errorf("Decode(%v) failed, expected: %q, got: %q", test.filter, test.expected, got)
+				continue
+			}
+		}
+	}
+}
+
+func TestDecodeProgram(t *testing.T) {
+	for _, test := range []struct {
+		name     string
+		program  []linux.BPFInstruction
+		expected string
+		fail     bool
+	}{
+		{name: "basic with jump indexes",
+			program: []linux.BPFInstruction{
+				Stmt(Ld+Abs+W, 10),
+				Stmt(Ldx+Mem, 10),
+				Stmt(St, 10),
+				Stmt(Stx, 10),
+				Stmt(Alu+Add+K, 10),
+				Stmt(Jmp+Ja, 10),
+				Jump(Jmp+Jeq+K, 10, 2, 5),
+				Jump(Jmp+Jset+X, 0, 0, 5),
+				Stmt(Misc+Tax, 0),
+			},
+			expected: "0: A <- P[10:4]\n" +
+				"1: X <- M[10]\n" +
+				"2: M[10] <- A\n" +
+				"3: M[10] <- X\n" +
+				"4: A <- A + 10\n" +
+				"5: pc += 10 [16]\n" +
+				"6: pc += (A == 10) ? 2 [9] : 5 [12]\n" +
+				"7: pc += (A & X) ? 0 [8] : 5 [13]\n" +
+				"8: X <- A\n",
+		},
+		{name: "invalid instruction",
+			program: []linux.BPFInstruction{Stmt(Ld+Abs+W, 10), Stmt(Ld+Len+Mem, 0)},
+			fail:    true},
+	} {
+		got, err := DecodeProgram(test.program)
+		if test.fail {
+			if err == nil {
+				t.Errorf("%s: Decode(...) failed, expected: 'error', got: %q", test.name, got)
+				continue
+			}
+		} else {
+			if err != nil {
+				t.Errorf("%s: Decode failed: %v", test.name, err)
+				continue
+			}
+			if got != test.expected {
+				t.Errorf("%s: Decode(...) failed, expected: %q, got: %q", test.name, test.expected, got)
+				continue
+			}
+		}
+	}
+}
diff --git a/pkg/bpf/input_bytes.go b/pkg/bpf/input_bytes.go
new file mode 100644
index 000000000..74af038eb
--- /dev/null
+++ b/pkg/bpf/input_bytes.go
@@ -0,0 +1,58 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"encoding/binary"
+)
+
+// InputBytes implements the Input interface by providing access to a byte
+// slice. Unaligned loads are supported.
+type InputBytes struct {
+	// Data is the data accessed through the Input interface.
+	Data []byte
+
+	// Order is the byte order the data is accessed with.
+	Order binary.ByteOrder
+}
+
+// Load32 implements Input.Load32.
+func (i InputBytes) Load32(off uint32) (uint32, bool) {
+	if uint64(off)+4 > uint64(len(i.Data)) {
+		return 0, false
+	}
+	return i.Order.Uint32(i.Data[int(off):]), true
+}
+
+// Load16 implements Input.Load16.
+func (i InputBytes) Load16(off uint32) (uint16, bool) {
+	if uint64(off)+2 > uint64(len(i.Data)) {
+		return 0, false
+	}
+	return i.Order.Uint16(i.Data[int(off):]), true
+}
+
+// Load8 implements Input.Load8.
+func (i InputBytes) Load8(off uint32) (uint8, bool) {
+	if uint64(off)+1 > uint64(len(i.Data)) {
+		return 0, false
+	}
+	return i.Data[int(off)], true
+}
+
+// Length implements Input.Length.
+func (i InputBytes) Length() uint32 {
+	return uint32(len(i.Data))
+}
diff --git a/pkg/bpf/interpreter.go b/pkg/bpf/interpreter.go
new file mode 100644
index 000000000..b7dee86a8
--- /dev/null
+++ b/pkg/bpf/interpreter.go
@@ -0,0 +1,410 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"fmt"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+// Possible values for ProgramError.Code.
+const (
+	// DivisionByZero indicates that a program contains, or executed, a
+	// division or modulo by zero.
+	DivisionByZero = iota
+
+	// InvalidEndOfProgram indicates that the last instruction of a program is
+	// not a return.
+	InvalidEndOfProgram
+
+	// InvalidInstructionCount indicates that a program has zero instructions
+	// or more than MaxInstructions instructions.
+	InvalidInstructionCount
+
+	// InvalidJumpTarget indicates that a program contains a jump whose target
+	// is outside of the program's bounds.
+	InvalidJumpTarget
+
+	// InvalidLoad indicates that a program executed an invalid load of input
+	// data.
+	InvalidLoad
+
+	// InvalidOpcode indicates that a program contains an instruction with an
+	// invalid opcode.
+	InvalidOpcode
+
+	// InvalidRegister indicates that a program contains a load from, or store
+	// to, a non-existent M register (index >= ScratchMemRegisters).
+	InvalidRegister
+)
+
+// Error is an error encountered while compiling or executing a BPF program.
+type Error struct {
+	// Code indicates the kind of error that occurred.
+	Code int
+
+	// PC is the program counter (index into the list of instructions) at which
+	// the error occurred.
+	PC int
+}
+
+func (e Error) codeString() string {
+	switch e.Code {
+	case DivisionByZero:
+		return "division by zero"
+	case InvalidEndOfProgram:
+		return "last instruction must be a return"
+	case InvalidInstructionCount:
+		return "invalid number of instructions"
+	case InvalidJumpTarget:
+		return "jump target out of bounds"
+	case InvalidLoad:
+		return "load out of bounds or violates input alignment requirements"
+	case InvalidOpcode:
+		return "invalid instruction opcode"
+	case InvalidRegister:
+		return "invalid M register"
+	default:
+		return "unknown error"
+	}
+}
+
+// Error implements error.Error.
+func (e Error) Error() string {
+	return fmt.Sprintf("at l%d: %s", e.PC, e.codeString())
+}
+
+// Program is a BPF program that has been validated for consistency.
+type Program struct {
+	instructions []linux.BPFInstruction
+}
+
+// Length returns the number of instructions in the program.
+func (p Program) Length() int {
+	return len(p.instructions)
+}
+
+// Compile performs validation on a sequence of BPF instructions before
+// wrapping them in a Program.
+func Compile(insns []linux.BPFInstruction) (Program, error) {
+	if len(insns) == 0 || len(insns) > MaxInstructions {
+		return Program{}, Error{InvalidInstructionCount, len(insns)}
+	}
+
+	// The last instruction must be a return.
+	if last := insns[len(insns)-1]; last.OpCode != (Ret|K) && last.OpCode != (Ret|A) {
+		return Program{}, Error{InvalidEndOfProgram, len(insns) - 1}
+	}
+
+	// Validate each instruction. Note that we skip a validation Linux does:
+	// Linux additionally verifies that every load from an M register is
+	// preceded, in every path, by a store to the same M register, in order to
+	// avoid having to clear M between programs
+	// (net/core/filter.c:check_load_and_stores). We always start with a zeroed
+	// M array.
+	for pc, i := range insns {
+		if i.OpCode&unusedBitsMask != 0 {
+			return Program{}, Error{InvalidOpcode, pc}
+		}
+		switch i.OpCode & instructionClassMask {
+		case Ld:
+			mode := i.OpCode & loadModeMask
+			switch i.OpCode & loadSizeMask {
+			case W:
+				if mode != Imm && mode != Abs && mode != Ind && mode != Mem && mode != Len {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+				if mode == Mem && i.K >= ScratchMemRegisters {
+					return Program{}, Error{InvalidRegister, pc}
+				}
+			case H, B:
+				if mode != Abs && mode != Ind {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+			default:
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		case Ldx:
+			mode := i.OpCode & loadModeMask
+			switch i.OpCode & loadSizeMask {
+			case W:
+				if mode != Imm && mode != Mem && mode != Len {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+				if mode == Mem && i.K >= ScratchMemRegisters {
+					return Program{}, Error{InvalidRegister, pc}
+				}
+			case B:
+				if mode != Msh {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+			default:
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		case St, Stx:
+			if i.OpCode&storeUnusedBitsMask != 0 {
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+			if i.K >= ScratchMemRegisters {
+				return Program{}, Error{InvalidRegister, pc}
+			}
+		case Alu:
+			switch i.OpCode & aluMask {
+			case Add, Sub, Mul, Or, And, Lsh, Rsh, Xor:
+				break
+			case Div, Mod:
+				if src := i.OpCode & srcAluJmpMask; src == K && i.K == 0 {
+					return Program{}, Error{DivisionByZero, pc}
+				}
+			case Neg:
+				// Negation doesn't take a source operand.
+				if i.OpCode&srcAluJmpMask != 0 {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+			default:
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		case Jmp:
+			switch i.OpCode & jmpMask {
+			case Ja:
+				// Unconditional jump doesn't take a source operand.
+				if i.OpCode&srcAluJmpMask != 0 {
+					return Program{}, Error{InvalidOpcode, pc}
+				}
+				// Do the comparison in 64 bits to avoid the possibility of
+				// overflow from a very large i.K.
+				if uint64(pc)+uint64(i.K)+1 >= uint64(len(insns)) {
+					return Program{}, Error{InvalidJumpTarget, pc}
+				}
+			case Jeq, Jgt, Jge, Jset:
+				// jt and jf are uint16s, so there's no threat of overflow.
+				if pc+int(i.JumpIfTrue)+1 >= len(insns) {
+					return Program{}, Error{InvalidJumpTarget, pc}
+				}
+				if pc+int(i.JumpIfFalse)+1 >= len(insns) {
+					return Program{}, Error{InvalidJumpTarget, pc}
+				}
+			default:
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		case Ret:
+			if i.OpCode&retUnusedBitsMask != 0 {
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+			if src := i.OpCode & srcRetMask; src != K && src != A {
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		case Misc:
+			if misc := i.OpCode & miscMask; misc != Tax && misc != Txa {
+				return Program{}, Error{InvalidOpcode, pc}
+			}
+		}
+	}
+
+	return Program{insns}, nil
+}
+
+// Input represents a source of input data for a BPF program. (BPF
+// documentation sometimes refers to the input data as the "packet" due to its
+// origins as a packet processing DSL.)
+//
+// For all of Input's Load methods:
+//
+// - The second (bool) return value is true if the load succeeded and false
+// otherwise.
+//
+// - Inputs should not assume that the loaded range falls within the input
+// data's length. Inputs should return false if the load falls outside of the
+// input data.
+//
+// - Inputs should not assume that the offset is correctly aligned. Inputs may
+// choose to service or reject loads to unaligned addresses.
+type Input interface {
+	// Load32 reads 32 bits from the input starting at the given byte offset.
+	Load32(off uint32) (uint32, bool)
+
+	// Load16 reads 16 bits from the input starting at the given byte offset.
+	Load16(off uint32) (uint16, bool)
+
+	// Load8 reads 8 bits from the input starting at the given byte offset.
+	Load8(off uint32) (uint8, bool)
+
+	// Length returns the length of the input in bytes.
+	Length() uint32
+}
+
+// machine represents the state of a BPF virtual machine.
+type machine struct {
+	A uint32
+	X uint32
+	M [ScratchMemRegisters]uint32
+}
+
+func conditionalJumpOffset(insn linux.BPFInstruction, cond bool) int {
+	if cond {
+		return int(insn.JumpIfTrue)
+	}
+	return int(insn.JumpIfFalse)
+}
+
+// Exec executes a BPF program over the given input and returns its return
+// value.
+func Exec(p Program, in Input) (uint32, error) {
+	var m machine
+	var pc int
+	for ; pc < len(p.instructions); pc++ {
+		i := p.instructions[pc]
+		switch i.OpCode {
+		case Ld | Imm | W:
+			m.A = i.K
+		case Ld | Abs | W:
+			val, ok := in.Load32(i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = val
+		case Ld | Abs | H:
+			val, ok := in.Load16(i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = uint32(val)
+		case Ld | Abs | B:
+			val, ok := in.Load8(i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = uint32(val)
+		case Ld | Ind | W:
+			val, ok := in.Load32(m.X + i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = val
+		case Ld | Ind | H:
+			val, ok := in.Load16(m.X + i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = uint32(val)
+		case Ld | Ind | B:
+			val, ok := in.Load8(m.X + i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.A = uint32(val)
+		case Ld | Mem | W:
+			m.A = m.M[int(i.K)]
+		case Ld | Len | W:
+			m.A = in.Length()
+		case Ldx | Imm | W:
+			m.X = i.K
+		case Ldx | Mem | W:
+			m.X = m.M[int(i.K)]
+		case Ldx | Len | W:
+			m.X = in.Length()
+		case Ldx | Msh | B:
+			val, ok := in.Load8(i.K)
+			if !ok {
+				return 0, Error{InvalidLoad, pc}
+			}
+			m.X = 4 * uint32(val&0xf)
+		case St:
+			m.M[int(i.K)] = m.A
+		case Stx:
+			m.M[int(i.K)] = m.X
+		case Alu | Add | K:
+			m.A += i.K
+		case Alu | Add | X:
+			m.A += m.X
+		case Alu | Sub | K:
+			m.A -= i.K
+		case Alu | Sub | X:
+			m.A -= m.X
+		case Alu | Mul | K:
+			m.A *= i.K
+		case Alu | Mul | X:
+			m.A *= m.X
+		case Alu | Div | K:
+			// K != 0 already checked by Compile.
+			m.A /= i.K
+		case Alu | Div | X:
+			if m.X == 0 {
+				return 0, Error{DivisionByZero, pc}
+			}
+			m.A /= m.X
+		case Alu | Or | K:
+			m.A |= i.K
+		case Alu | Or | X:
+			m.A |= m.X
+		case Alu | And | K:
+			m.A &= i.K
+		case Alu | And | X:
+			m.A &= m.X
+		case Alu | Lsh | K:
+			m.A <<= i.K
+		case Alu | Lsh | X:
+			m.A <<= m.X
+		case Alu | Rsh | K:
+			m.A >>= i.K
+		case Alu | Rsh | X:
+			m.A >>= m.X
+		case Alu | Neg:
+			m.A = uint32(-int32(m.A))
+		case Alu | Mod | K:
+			// K != 0 already checked by Compile.
+			m.A %= i.K
+		case Alu | Mod | X:
+			if m.X == 0 {
+				return 0, Error{DivisionByZero, pc}
+			}
+			m.A %= m.X
+		case Alu | Xor | K:
+			m.A ^= i.K
+		case Alu | Xor | X:
+			m.A ^= m.X
+		case Jmp | Ja:
+			pc += int(i.K)
+		case Jmp | Jeq | K:
+			pc += conditionalJumpOffset(i, m.A == i.K)
+		case Jmp | Jeq | X:
+			pc += conditionalJumpOffset(i, m.A == m.X)
+		case Jmp | Jgt | K:
+			pc += conditionalJumpOffset(i, m.A > i.K)
+		case Jmp | Jgt | X:
+			pc += conditionalJumpOffset(i, m.A > m.X)
+		case Jmp | Jge | K:
+			pc += conditionalJumpOffset(i, m.A >= i.K)
+		case Jmp | Jge | X:
+			pc += conditionalJumpOffset(i, m.A >= m.X)
+		case Jmp | Jset | K:
+			pc += conditionalJumpOffset(i, (m.A&i.K) != 0)
+		case Jmp | Jset | X:
+			pc += conditionalJumpOffset(i, (m.A&m.X) != 0)
+		case Ret | K:
+			return i.K, nil
+		case Ret | A:
+			return m.A, nil
+		case Misc | Tax:
+			m.A = m.X
+		case Misc | Txa:
+			m.X = m.A
+		default:
+			return 0, Error{InvalidOpcode, pc}
+		}
+	}
+	return 0, Error{InvalidEndOfProgram, pc}
+}
diff --git a/pkg/bpf/interpreter_test.go b/pkg/bpf/interpreter_test.go
new file mode 100644
index 000000000..9e5e33228
--- /dev/null
+++ b/pkg/bpf/interpreter_test.go
@@ -0,0 +1,797 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"testing"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+	"gvisor.googlesource.com/gvisor/pkg/binary"
+)
+
+func TestCompilationErrors(t *testing.T) {
+	for _, test := range []struct {
+		// desc is the test's description.
+		desc string
+
+		// insns is the BPF instructions to be compiled.
+		insns []linux.BPFInstruction
+
+		// expectedErr is the expected compilation error.
+		expectedErr error
+	}{
+		{
+			desc:        "Instructions must not be nil",
+			expectedErr: Error{InvalidInstructionCount, 0},
+		},
+		{
+			desc:        "Instructions must not be empty",
+			insns:       []linux.BPFInstruction{},
+			expectedErr: Error{InvalidInstructionCount, 0},
+		},
+		{
+			desc:        "A program must end with a return",
+			insns:       make([]linux.BPFInstruction, MaxInstructions),
+			expectedErr: Error{InvalidEndOfProgram, MaxInstructions - 1},
+		},
+		{
+			desc:        "A program must have MaxInstructions or fewer instructions",
+			insns:       append(make([]linux.BPFInstruction, MaxInstructions), Stmt(Ret|K, 0)),
+			expectedErr: Error{InvalidInstructionCount, MaxInstructions + 1},
+		},
+		{
+			desc: "A load from an invalid M register is a compilation error",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Mem|W, ScratchMemRegisters), // A = M[16]
+				Stmt(Ret|K, 0),                      // return 0
+			},
+			expectedErr: Error{InvalidRegister, 0},
+		},
+		{
+			desc: "A store to an invalid M register is a compilation error",
+			insns: []linux.BPFInstruction{
+				Stmt(St, ScratchMemRegisters), // M[16] = A
+				Stmt(Ret|K, 0),                // return 0
+			},
+			expectedErr: Error{InvalidRegister, 0},
+		},
+		{
+			desc: "Division by literal zero is a compilation error",
+			insns: []linux.BPFInstruction{
+				Stmt(Alu|Div|K, 0), // A /= 0
+				Stmt(Ret|K, 0),     // return 0
+			},
+			expectedErr: Error{DivisionByZero, 0},
+		},
+		{
+			desc: "An unconditional jump outside of the program is a compilation error",
+			insns: []linux.BPFInstruction{
+				Jump(Jmp|Ja, 1, 0, 0), // jmp nextpc+1
+				Stmt(Ret|K, 0),        // return 0
+			},
+			expectedErr: Error{InvalidJumpTarget, 0},
+		},
+		{
+			desc: "A conditional jump outside of the program in the true case is a compilation error",
+			insns: []linux.BPFInstruction{
+				Jump(Jmp|Jeq|K, 0, 1, 0), // if (A == K) jmp nextpc+1
+				Stmt(Ret|K, 0),           // return 0
+			},
+			expectedErr: Error{InvalidJumpTarget, 0},
+		},
+		{
+			desc: "A conditional jump outside of the program in the false case is a compilation error",
+			insns: []linux.BPFInstruction{
+				Jump(Jmp|Jeq|K, 0, 0, 1), // if (A != K) jmp nextpc+1
+				Stmt(Ret|K, 0),           // return 0
+			},
+			expectedErr: Error{InvalidJumpTarget, 0},
+		},
+	} {
+		_, err := Compile(test.insns)
+		if err != test.expectedErr {
+			t.Errorf("%s: expected error %q, got error %q", test.desc, test.expectedErr, err)
+		}
+	}
+}
+
+func TestExecErrors(t *testing.T) {
+	for _, test := range []struct {
+		// desc is the test's description.
+		desc string
+
+		// insns is the BPF instructions to be executed.
+		insns []linux.BPFInstruction
+
+		// expectedErr is the expected execution error.
+		expectedErr error
+	}{
+		{
+			desc: "An out-of-bounds load of input data is an execution error",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Abs|B, 0), // A = input[0]
+				Stmt(Ret|K, 0),    // return 0
+			},
+			expectedErr: Error{InvalidLoad, 0},
+		},
+		{
+			desc: "Division by zero at runtime is an execution error",
+			insns: []linux.BPFInstruction{
+				Stmt(Alu|Div|X, 0), // A /= X
+				Stmt(Ret|K, 0),     // return 0
+			},
+			expectedErr: Error{DivisionByZero, 0},
+		},
+		{
+			desc: "Modulo zero at runtime is an execution error",
+			insns: []linux.BPFInstruction{
+				Stmt(Alu|Mod|X, 0), // A %= X
+				Stmt(Ret|K, 0),     // return 0
+			},
+			expectedErr: Error{DivisionByZero, 0},
+		},
+	} {
+		p, err := Compile(test.insns)
+		if err != nil {
+			t.Errorf("%s: unexpected compilation error: %v", test.desc, err)
+			continue
+		}
+		ret, err := Exec(p, InputBytes{nil, binary.BigEndian})
+		if err != test.expectedErr {
+			t.Errorf("%s: expected execution error %q, got (%d, %v)", test.desc, test.expectedErr, ret, err)
+		}
+	}
+}
+
+func TestValidInstructions(t *testing.T) {
+	for _, test := range []struct {
+		// desc is the test's description.
+		desc string
+
+		// insns is the BPF instructions to be compiled.
+		insns []linux.BPFInstruction
+
+		// input is the input data. Note that input will be read as big-endian.
+		input []byte
+
+		// expectedRet is the expected return value of the BPF program.
+		expectedRet uint32
+	}{
+		{
+			desc: "Return of immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ret|K, 42), // return 42
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Load of immediate into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42), // A = 42
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Load of immediate into X and copying of X into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Imm|W, 42), // X = 42
+				Stmt(Misc|Tax, 0),   // A = X
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Copying of A into X and back",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42), // A = 42
+				Stmt(Misc|Txa, 0),  // X = A
+				Stmt(Ld|Imm|W, 0),  // A = 0
+				Stmt(Misc|Tax, 0),  // A = X
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Load of 32-bit input by absolute offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Abs|W, 1), // A = input[1..4]
+				Stmt(Ret|A, 0),    // return A
+			},
+			input:       []byte{0x00, 0x11, 0x22, 0x33, 0x44},
+			expectedRet: 0x11223344,
+		},
+		{
+			desc: "Load of 16-bit input by absolute offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Abs|H, 1), // A = input[1..2]
+				Stmt(Ret|A, 0),    // return A
+			},
+			input:       []byte{0x00, 0x11, 0x22},
+			expectedRet: 0x1122,
+		},
+		{
+			desc: "Load of 8-bit input by absolute offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Abs|B, 1), // A = input[1]
+				Stmt(Ret|A, 0),    // return A
+			},
+			input:       []byte{0x00, 0x11},
+			expectedRet: 0x11,
+		},
+		{
+			desc: "Load of 32-bit input by relative offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Imm|W, 1), // X = 1
+				Stmt(Ld|Ind|W, 1),  // A = input[X+1..X+4]
+				Stmt(Ret|A, 0),     // return A
+			},
+			input:       []byte{0x00, 0x11, 0x22, 0x33, 0x44, 0x55},
+			expectedRet: 0x22334455,
+		},
+		{
+			desc: "Load of 16-bit input by relative offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Imm|W, 1), // X = 1
+				Stmt(Ld|Ind|H, 1),  // A = input[X+1..X+2]
+				Stmt(Ret|A, 0),     // return A
+			},
+			input:       []byte{0x00, 0x11, 0x22, 0x33},
+			expectedRet: 0x2233,
+		},
+		{
+			desc: "Load of 8-bit input by relative offset into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Imm|W, 1), // X = 1
+				Stmt(Ld|Ind|B, 1),  // A = input[X+1]
+				Stmt(Ret|A, 0),     // return A
+			},
+			input:       []byte{0x00, 0x11, 0x22},
+			expectedRet: 0x22,
+		},
+		{
+			desc: "Load/store between A and scratch memory",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42), // A = 42
+				Stmt(St, 2),        // M[2] = A
+				Stmt(Ld|Imm|W, 0),  // A = 0
+				Stmt(Ld|Mem|W, 2),  // A = M[2]
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Load/store between X and scratch memory",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Imm|W, 42), // X = 42
+				Stmt(Stx, 3),        // M[3] = X
+				Stmt(Ldx|Imm|W, 0),  // X = 0
+				Stmt(Ldx|Mem|W, 3),  // X = M[3]
+				Stmt(Misc|Tax, 0),   // A = X
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 42,
+		},
+		{
+			desc: "Load of input length into A",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Len|W, 0), // A = len(input)
+				Stmt(Ret|A, 0),    // return A
+			},
+			input:       []byte{1, 2, 3},
+			expectedRet: 3,
+		},
+		{
+			desc: "Load of input length into X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Len|W, 0), // X = len(input)
+				Stmt(Misc|Tax, 0),  // A = X
+				Stmt(Ret|A, 0),     // return A
+			},
+			input:       []byte{1, 2, 3},
+			expectedRet: 3,
+		},
+		{
+			desc: "Load of MSH (?) into X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ldx|Msh|B, 0), // X = 4*(input[0]&0xf)
+				Stmt(Misc|Tax, 0),  // A = X
+				Stmt(Ret|A, 0),     // return A
+			},
+			input:       []byte{0xf1},
+			expectedRet: 4,
+		},
+		{
+			desc: "Addition of immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),  // A = 10
+				Stmt(Alu|Add|K, 20), // A += 20
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 30,
+		},
+		{
+			desc: "Addition of X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),  // A = 10
+				Stmt(Ldx|Imm|W, 20), // X = 20
+				Stmt(Alu|Add|X, 0),  // A += X
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 30,
+		},
+		{
+			desc: "Subtraction of immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 30),  // A = 30
+				Stmt(Alu|Sub|K, 20), // A -= 20
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 10,
+		},
+		{
+			desc: "Subtraction of X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 30),  // A = 30
+				Stmt(Ldx|Imm|W, 20), // X = 20
+				Stmt(Alu|Sub|X, 0),  // A -= X
+				Stmt(Ret|A, 0),      // return A
+			},
+			expectedRet: 10,
+		},
+		{
+			desc: "Multiplication of immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 2),  // A = 2
+				Stmt(Alu|Mul|K, 3), // A *= 3
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 6,
+		},
+		{
+			desc: "Multiplication of X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 2),  // A = 2
+				Stmt(Ldx|Imm|W, 3), // X = 3
+				Stmt(Alu|Mul|X, 0), // A *= X
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 6,
+		},
+		{
+			desc: "Division by immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 6),  // A = 6
+				Stmt(Alu|Div|K, 3), // A /= 3
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Division by X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 6),  // A = 6
+				Stmt(Ldx|Imm|W, 3), // X = 3
+				Stmt(Alu|Div|X, 0), // A /= X
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Modulo immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 17), // A = 17
+				Stmt(Alu|Mod|K, 7), // A %= 7
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 3,
+		},
+		{
+			desc: "Modulo X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 17), // A = 17
+				Stmt(Ldx|Imm|W, 7), // X = 7
+				Stmt(Alu|Mod|X, 0), // A %= X
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 3,
+		},
+		{
+			desc: "Arithmetic negation",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 1), // A = 1
+				Stmt(Alu|Neg, 0),  // A = -A
+				Stmt(Ret|A, 0),    // return A
+			},
+			expectedRet: 0xffffffff,
+		},
+		{
+			desc: "Bitwise OR with immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55), // A = 0xff00aa55
+				Stmt(Alu|Or|K, 0xff0055aa), // A |= 0xff0055aa
+				Stmt(Ret|A, 0),             // return A
+			},
+			expectedRet: 0xff00ffff,
+		},
+		{
+			desc: "Bitwise OR with X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55),  // A = 0xff00aa55
+				Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa
+				Stmt(Alu|Or|X, 0),           // A |= X
+				Stmt(Ret|A, 0),              // return A
+			},
+			expectedRet: 0xff00ffff,
+		},
+		{
+			desc: "Bitwise AND with immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55),  // A = 0xff00aa55
+				Stmt(Alu|And|K, 0xff0055aa), // A &= 0xff0055aa
+				Stmt(Ret|A, 0),              // return A
+			},
+			expectedRet: 0xff000000,
+		},
+		{
+			desc: "Bitwise AND with X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55),  // A = 0xff00aa55
+				Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa
+				Stmt(Alu|And|X, 0),          // A &= X
+				Stmt(Ret|A, 0),              // return A
+			},
+			expectedRet: 0xff000000,
+		},
+		{
+			desc: "Bitwise XOR with immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55),  // A = 0xff00aa55
+				Stmt(Alu|Xor|K, 0xff0055aa), // A ^= 0xff0055aa
+				Stmt(Ret|A, 0),              // return A
+			},
+			expectedRet: 0x0000ffff,
+		},
+		{
+			desc: "Bitwise XOR with X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff00aa55),  // A = 0xff00aa55
+				Stmt(Ldx|Imm|W, 0xff0055aa), // X = 0xff0055aa
+				Stmt(Alu|Xor|X, 0),          // A ^= X
+				Stmt(Ret|A, 0),              // return A
+			},
+			expectedRet: 0x0000ffff,
+		},
+		{
+			desc: "Left shift by immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 1),  // A = 1
+				Stmt(Alu|Lsh|K, 5), // A <<= 5
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 32,
+		},
+		{
+			desc: "Left shift by X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 1),  // A = 1
+				Stmt(Ldx|Imm|W, 5), // X = 5
+				Stmt(Alu|Lsh|X, 0), // A <<= X
+				Stmt(Ret|A, 0),     // return A
+			},
+			expectedRet: 32,
+		},
+		{
+			desc: "Right shift by immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xffffffff), // A = 0xffffffff
+				Stmt(Alu|Rsh|K, 31),        // A >>= 31
+				Stmt(Ret|A, 0),             // return A
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Right shift by X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xffffffff), // A = 0xffffffff
+				Stmt(Ldx|Imm|W, 31),        // X = 31
+				Stmt(Alu|Rsh|X, 0),         // A >>= X
+				Stmt(Ret|A, 0),             // return A
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Unconditional jump",
+			insns: []linux.BPFInstruction{
+				Jump(Jmp|Ja, 1, 0, 0), // jmp nextpc+1
+				Stmt(Ret|K, 0),        // return 0
+				Stmt(Ret|K, 1),        // return 1
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A == immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42),        // A = 42
+				Jump(Jmp|Jeq|K, 42, 1, 2), // if (A == 42) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A != immediate",
+			insns: []linux.BPFInstruction{
+				Jump(Jmp|Jeq|K, 42, 1, 2), // if (A == 42) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A == X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42),       // A = 42
+				Stmt(Ldx|Imm|W, 42),      // X = 42
+				Jump(Jmp|Jeq|X, 0, 1, 2), // if (A == X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A != X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 42),       // A = 42
+				Jump(Jmp|Jeq|X, 0, 1, 2), // if (A == X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A > immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),       // A = 10
+				Jump(Jmp|Jgt|K, 9, 1, 2), // if (A > 9) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A <= immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),        // A = 10
+				Jump(Jmp|Jgt|K, 10, 1, 2), // if (A > 10) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A > X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),       // A = 10
+				Stmt(Ldx|Imm|W, 9),       // X = 9
+				Jump(Jmp|Jgt|X, 0, 1, 2), // if (A > X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A <= X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),       // A = 10
+				Stmt(Ldx|Imm|W, 10),      // X = 10
+				Jump(Jmp|Jgt|X, 0, 1, 2), // if (A > X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A >= immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),        // A = 10
+				Jump(Jmp|Jge|K, 10, 1, 2), // if (A >= 10) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A < immediate",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),        // A = 10
+				Jump(Jmp|Jge|K, 11, 1, 2), // if (A >= 11) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A >= X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),       // A = 10
+				Stmt(Ldx|Imm|W, 10),      // X = 10
+				Jump(Jmp|Jge|X, 0, 1, 2), // if (A >= X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A < X",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 10),       // A = 10
+				Stmt(Ldx|Imm|W, 11),      // X = 11
+				Jump(Jmp|Jge|X, 0, 1, 2), // if (A >= X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),           // return 0
+				Stmt(Ret|K, 1),           // return 1
+				Stmt(Ret|K, 2),           // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A & immediate != 0",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff),          // A = 0xff
+				Jump(Jmp|Jset|K, 0x101, 1, 2), // if (A & 0x101) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),                // return 0
+				Stmt(Ret|K, 1),                // return 1
+				Stmt(Ret|K, 2),                // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A & immediate == 0",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xfe),          // A = 0xfe
+				Jump(Jmp|Jset|K, 0x101, 1, 2), // if (A & 0x101) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),                // return 0
+				Stmt(Ret|K, 1),                // return 1
+				Stmt(Ret|K, 2),                // return 2
+			},
+			expectedRet: 2,
+		},
+		{
+			desc: "Jump when A & X != 0",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xff),      // A = 0xff
+				Stmt(Ldx|Imm|W, 0x101),    // X = 0x101
+				Jump(Jmp|Jset|X, 0, 1, 2), // if (A & X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 1,
+		},
+		{
+			desc: "Jump when A & X == 0",
+			insns: []linux.BPFInstruction{
+				Stmt(Ld|Imm|W, 0xfe),      // A = 0xfe
+				Stmt(Ldx|Imm|W, 0x101),    // X = 0x101
+				Jump(Jmp|Jset|X, 0, 1, 2), // if (A & X) jmp nextpc+1 else jmp nextpc+2
+				Stmt(Ret|K, 0),            // return 0
+				Stmt(Ret|K, 1),            // return 1
+				Stmt(Ret|K, 2),            // return 2
+			},
+			expectedRet: 2,
+		},
+	} {
+		p, err := Compile(test.insns)
+		if err != nil {
+			t.Errorf("%s: unexpected compilation error: %v", test.desc, err)
+			continue
+		}
+		ret, err := Exec(p, InputBytes{test.input, binary.BigEndian})
+		if err != nil {
+			t.Errorf("%s: expected return value of %d, got execution error: %v", test.desc, test.expectedRet, err)
+			continue
+		}
+		if ret != test.expectedRet {
+			t.Errorf("%s: expected return value of %d, got value %d", test.desc, test.expectedRet, ret)
+		}
+	}
+}
+
+func TestSimpleFilter(t *testing.T) {
+	// Seccomp filter example given in Linux's
+	// Documentation/networking/filter.txt, translated to bytecode using the
+	// Linux kernel tree's tools/net/bpf_asm.
+	filter := []linux.BPFInstruction{
+		{0x20, 0, 0, 0x00000004},  // ld [4]                  /* offsetof(struct seccomp_data, arch) */
+		{0x15, 0, 11, 0xc000003e}, // jne #0xc000003e, bad    /* AUDIT_ARCH_X86_64 */
+		{0x20, 0, 0, 0000000000},  // ld [0]                  /* offsetof(struct seccomp_data, nr) */
+		{0x15, 10, 0, 0x0000000f}, // jeq #15, good           /* __NR_rt_sigreturn */
+		{0x15, 9, 0, 0x000000e7},  // jeq #231, good          /* __NR_exit_group */
+		{0x15, 8, 0, 0x0000003c},  // jeq #60, good           /* __NR_exit */
+		{0x15, 7, 0, 0000000000},  // jeq #0, good            /* __NR_read */
+		{0x15, 6, 0, 0x00000001},  // jeq #1, good            /* __NR_write */
+		{0x15, 5, 0, 0x00000005},  // jeq #5, good            /* __NR_fstat */
+		{0x15, 4, 0, 0x00000009},  // jeq #9, good            /* __NR_mmap */
+		{0x15, 3, 0, 0x0000000e},  // jeq #14, good           /* __NR_rt_sigprocmask */
+		{0x15, 2, 0, 0x0000000d},  // jeq #13, good           /* __NR_rt_sigaction */
+		{0x15, 1, 0, 0x00000023},  // jeq #35, good           /* __NR_nanosleep */
+		{0x06, 0, 0, 0000000000},  // bad: ret #0             /* SECCOMP_RET_KILL */
+		{0x06, 0, 0, 0x7fff0000},  // good: ret #0x7fff0000   /* SECCOMP_RET_ALLOW */
+	}
+	p, err := Compile(filter)
+	if err != nil {
+		t.Fatalf("Unexpected compilation error: %v", err)
+	}
+
+	for _, test := range []struct {
+		// desc is the test's description.
+		desc string
+
+		// seccompData is the input data.
+		seccompData
+
+		// expectedRet is the expected return value of the BPF program.
+		expectedRet uint32
+	}{
+		{
+			desc:        "Invalid arch is rejected",
+			seccompData: seccompData{nr: 1 /* x86 exit */, arch: 0x40000003 /* AUDIT_ARCH_I386 */},
+			expectedRet: 0,
+		},
+		{
+			desc:        "Disallowed syscall is rejected",
+			seccompData: seccompData{nr: 105 /* __NR_setuid */, arch: 0xc000003e},
+			expectedRet: 0,
+		},
+		{
+			desc:        "Whitelisted syscall is allowed",
+			seccompData: seccompData{nr: 231 /* __NR_exit_group */, arch: 0xc000003e},
+			expectedRet: 0x7fff0000,
+		},
+	} {
+		ret, err := Exec(p, test.seccompData.asInput())
+		if err != nil {
+			t.Errorf("%s: expected return value of %d, got execution error: %v", test.desc, test.expectedRet, err)
+			continue
+		}
+		if ret != test.expectedRet {
+			t.Errorf("%s: expected return value of %d, got value %d", test.desc, test.expectedRet, ret)
+		}
+	}
+}
+
+// seccompData is equivalent to struct seccomp_data.
+type seccompData struct {
+	nr                 uint32
+	arch               uint32
+	instructionPointer uint64
+	args               [6]uint64
+}
+
+// asInput converts a seccompData to a bpf.Input.
+func (d *seccompData) asInput() Input {
+	return InputBytes{binary.Marshal(nil, binary.LittleEndian, d), binary.LittleEndian}
+}
diff --git a/pkg/bpf/program_builder.go b/pkg/bpf/program_builder.go
new file mode 100644
index 000000000..7554d47c1
--- /dev/null
+++ b/pkg/bpf/program_builder.go
@@ -0,0 +1,159 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"fmt"
+	"math"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+const labelTarget = math.MaxUint8
+
+// ProgramBuilder assists with building a BPF program with jump
+// labels that are resolved to their proper offsets.
+type ProgramBuilder struct {
+	// Maps label names to label objects.
+	labels map[string]*label
+
+	// Array of BPF instructions that makes up the program.
+	instructions []linux.BPFInstruction
+}
+
+// NewProgramBuilder creates a new ProgramBuilder instance.
+func NewProgramBuilder() *ProgramBuilder {
+	return &ProgramBuilder{labels: map[string]*label{}}
+}
+
+// label contains information to resolve a label to an offset.
+type label struct {
+	// List of locations that reference the label in the program.
+	sources []source
+
+	// Program line when the label is located.
+	target int
+}
+
+// source contains information about a single reference to a label.
+type source struct {
+	// Program line where the label reference is present.
+	line int
+
+	// True if label reference is in the 'jump if true' part of the jump.
+	// False if label reference is in the 'jump if false' part of the jump.
+	jt bool
+}
+
+// AddStmt adds a new statement to the program.
+func (b *ProgramBuilder) AddStmt(code uint16, k uint32) {
+	b.instructions = append(b.instructions, Stmt(code, k))
+}
+
+// AddJump adds a new jump to the program.
+func (b *ProgramBuilder) AddJump(code uint16, k uint32, jt, jf uint8) {
+	b.instructions = append(b.instructions, Jump(code, k, jt, jf))
+}
+
+// AddJumpTrueLabel adds a new jump to the program where 'jump if true' is a label.
+func (b *ProgramBuilder) AddJumpTrueLabel(code uint16, k uint32, jtLabel string, jf uint8) {
+	b.addLabelSource(jtLabel, true)
+	b.AddJump(code, k, labelTarget, jf)
+}
+
+// AddJumpFalseLabel adds a new jump to the program where 'jump if false' is a label.
+func (b *ProgramBuilder) AddJumpFalseLabel(code uint16, k uint32, jt uint8, jfLabel string) {
+	b.addLabelSource(jfLabel, false)
+	b.AddJump(code, k, jt, math.MaxUint8)
+}
+
+// AddJumpLabels adds a new jump to the program where both jump targets are labels.
+func (b *ProgramBuilder) AddJumpLabels(code uint16, k uint32, jtLabel, jfLabel string) {
+	b.addLabelSource(jtLabel, true)
+	b.addLabelSource(jfLabel, false)
+	b.AddJump(code, k, math.MaxUint8, math.MaxUint8)
+}
+
+// AddLabel sets the given label name at the current location. The next instruction is executed
+// when the any code jumps to this label. More than one label can be added to the same location.
+func (b *ProgramBuilder) AddLabel(name string) error {
+	l, ok := b.labels[name]
+	if !ok {
+		// This is done to catch jump backwards cases, but it's not strictly wrong
+		// to have unused labels.
+		return fmt.Errorf("Adding a label that hasn't been used is not allowed: %v", name)
+	}
+	if l.target != -1 {
+		return fmt.Errorf("label %q target already set: %v", name, l.target)
+	}
+	l.target = len(b.instructions)
+	return nil
+}
+
+// Instructions returns an array of BPF instructions representing the program with all labels
+// resolved. Return error in case label resolution failed due to an invalid program.
+func (b *ProgramBuilder) Instructions() ([]linux.BPFInstruction, error) {
+	if err := b.resolveLabels(); err != nil {
+		return nil, err
+	}
+	return b.instructions, nil
+}
+
+func (b *ProgramBuilder) addLabelSource(labelName string, jt bool) {
+	l, ok := b.labels[labelName]
+	if !ok {
+		l = &label{sources: make([]source, 0), target: -1}
+		b.labels[labelName] = l
+	}
+	l.sources = append(l.sources, source{line: len(b.instructions), jt: jt})
+}
+
+func (b *ProgramBuilder) resolveLabels() error {
+	for key, v := range b.labels {
+		if v.target == -1 {
+			return fmt.Errorf("label target not set: %v", key)
+		}
+		if v.target >= len(b.instructions) {
+			return fmt.Errorf("target is beyond end of ProgramBuilder")
+		}
+		for _, s := range v.sources {
+			// Finds jump instruction that references the label.
+			inst := b.instructions[s.line]
+			if s.line >= v.target {
+				return fmt.Errorf("cannot jump backwards")
+			}
+			// Calculates the jump offset from current line.
+			offset := v.target - s.line - 1
+			if offset > math.MaxUint8 {
+				return fmt.Errorf("jump offset to label '%v' is too large: %v", key, offset)
+			}
+			// Sets offset into jump instruction.
+			if s.jt {
+				if inst.JumpIfTrue != labelTarget {
+					return fmt.Errorf("jump target is not a label")
+				}
+				inst.JumpIfTrue = uint8(offset)
+			} else {
+				if inst.JumpIfFalse != labelTarget {
+					return fmt.Errorf("jump target is not a label")
+				}
+				inst.JumpIfFalse = uint8(offset)
+			}
+			b.instructions[s.line] = inst
+		}
+	}
+	b.labels = map[string]*label{}
+	return nil
+}
diff --git a/pkg/bpf/program_builder_test.go b/pkg/bpf/program_builder_test.go
new file mode 100644
index 000000000..7e4f06584
--- /dev/null
+++ b/pkg/bpf/program_builder_test.go
@@ -0,0 +1,157 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package bpf
+
+import (
+	"fmt"
+	"testing"
+
+	"gvisor.googlesource.com/gvisor/pkg/abi/linux"
+)
+
+func validate(p *ProgramBuilder, expected []linux.BPFInstruction) error {
+	instructions, err := p.Instructions()
+	if err != nil {
+		return fmt.Errorf("Instructions() failed: %v", err)
+	}
+	got, err := DecodeProgram(instructions)
+	if err != nil {
+		return fmt.Errorf("DecodeProgram('instructions') failed: %v", err)
+	}
+	expectedDecoded, err := DecodeProgram(expected)
+	if err != nil {
+		return fmt.Errorf("DecodeProgram('expected') failed: %v", err)
+	}
+	if got != expectedDecoded {
+		return fmt.Errorf("DecodeProgram() failed, expected: %q, got: %q", expectedDecoded, got)
+	}
+	return nil
+}
+
+func TestProgramBuilderSimple(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddStmt(Ld+Abs+W, 10)
+	p.AddJump(Jmp+Ja, 10, 0, 0)
+
+	expected := []linux.BPFInstruction{
+		Stmt(Ld+Abs+W, 10),
+		Jump(Jmp+Ja, 10, 0, 0),
+	}
+
+	if err := validate(p, expected); err != nil {
+		t.Errorf("Validate() failed: %v", err)
+	}
+}
+
+func TestProgramBuilderLabels(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 11, "label_1", 0)
+	p.AddJumpFalseLabel(Jmp+Jeq+K, 12, 0, "label_2")
+	p.AddJumpLabels(Jmp+Jeq+K, 13, "label_3", "label_4")
+	if err := p.AddLabel("label_1"); err != nil {
+		t.Errorf("AddLabel(label_1) failed: %v", err)
+	}
+	p.AddStmt(Ld+Abs+W, 1)
+	if err := p.AddLabel("label_3"); err != nil {
+		t.Errorf("AddLabel(label_3) failed: %v", err)
+	}
+	p.AddJumpLabels(Jmp+Jeq+K, 14, "label_4", "label_5")
+	if err := p.AddLabel("label_2"); err != nil {
+		t.Errorf("AddLabel(label_2) failed: %v", err)
+	}
+	p.AddJumpLabels(Jmp+Jeq+K, 15, "label_4", "label_6")
+	if err := p.AddLabel("label_4"); err != nil {
+		t.Errorf("AddLabel(label_4) failed: %v", err)
+	}
+	p.AddStmt(Ld+Abs+W, 4)
+	if err := p.AddLabel("label_5"); err != nil {
+		t.Errorf("AddLabel(label_5) failed: %v", err)
+	}
+	if err := p.AddLabel("label_6"); err != nil {
+		t.Errorf("AddLabel(label_6) failed: %v", err)
+	}
+	p.AddStmt(Ld+Abs+W, 5)
+
+	expected := []linux.BPFInstruction{
+		Jump(Jmp+Jeq+K, 11, 2, 0),
+		Jump(Jmp+Jeq+K, 12, 0, 3),
+		Jump(Jmp+Jeq+K, 13, 1, 3),
+		Stmt(Ld+Abs+W, 1),
+		Jump(Jmp+Jeq+K, 14, 1, 2),
+		Jump(Jmp+Jeq+K, 15, 0, 1),
+		Stmt(Ld+Abs+W, 4),
+		Stmt(Ld+Abs+W, 5),
+	}
+	if err := validate(p, expected); err != nil {
+		t.Errorf("Validate() failed: %v", err)
+	}
+	// Calling validate()=>p.Instructions() again to make sure
+	// Instructions can be called multiple times without ruining
+	// the program.
+	if err := validate(p, expected); err != nil {
+		t.Errorf("Validate() failed: %v", err)
+	}
+}
+
+func TestProgramBuilderMissingErrorTarget(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0)
+	if _, err := p.Instructions(); err == nil {
+		t.Errorf("Instructions() should have failed")
+	}
+}
+
+func TestProgramBuilderLabelWithNoInstruction(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0)
+	if err := p.AddLabel("label_1"); err != nil {
+		t.Errorf("AddLabel(label_1) failed: %v", err)
+	}
+	if _, err := p.Instructions(); err == nil {
+		t.Errorf("Instructions() should have failed")
+	}
+}
+
+func TestProgramBuilderUnusedLabel(t *testing.T) {
+	p := NewProgramBuilder()
+	if err := p.AddLabel("unused"); err == nil {
+		t.Errorf("AddLabel(unused) should have failed")
+	}
+}
+
+func TestProgramBuilderLabelAddedTwice(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0)
+	if err := p.AddLabel("label_1"); err != nil {
+		t.Errorf("AddLabel(label_1) failed: %v", err)
+	}
+	p.AddStmt(Ld+Abs+W, 0)
+	if err := p.AddLabel("label_1"); err == nil {
+		t.Errorf("AddLabel(label_1) failed: %v", err)
+	}
+}
+
+func TestProgramBuilderJumpBackwards(t *testing.T) {
+	p := NewProgramBuilder()
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0)
+	if err := p.AddLabel("label_1"); err != nil {
+		t.Errorf("AddLabel(label_1) failed: %v", err)
+	}
+	p.AddStmt(Ld+Abs+W, 0)
+	p.AddJumpTrueLabel(Jmp+Jeq+K, 10, "label_1", 0)
+	if _, err := p.Instructions(); err == nil {
+		t.Errorf("Instructions() should have failed")
+	}
+}