ebpf overlow bug

.gitignore

ebpf-bug
venv
ebpf-bug-kern.o
ebpf-bug-ebpf.c
bpf_helpers.h
bpf.h

ebpf-bug-kern.c

#include <stdint.h>

#include "bpf.h"
#include "bpf_helpers.h"

struct bpf_map_def stats SEC("maps") = {
	.type = BPF_MAP_TYPE_ARRAY,
	.key_size = sizeof(uint32_t),
	.value_size = sizeof(uint64_t),
	.max_entries = 128,
};

static inline void store_stat(int no, uint64_t v)
{
	uint64_t *value = bpf_map_lookup_elem(&stats, &no);
	if (value) {
		*value = v;
	}
}

SEC("socket1")
int bpf_prog1()
{
	uint64_t a = bpf_ktime_get_ns();
	uint64_t b = bpf_ktime_get_ns();
	uint64_t delta = b - a;
	if ((int64_t)delta > 0) {
		store_stat(0, 0);
	} else {
		store_stat(0, 1);
	}
	store_stat(1, a);
	store_stat(2, b);
	store_stat(3, delta);

	return SK_PASS;
}

ebpf-bug.c

#include <arpa/inet.h>
#include <linux/bpf.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#include "tbpf.h"

#define ERRORF(x...) fprintf(stderr, x)
#define PFATAL(x...)                                                           \
	do {                                                                   \
		ERRORF("[-] SYSTEM ERROR : " x);                               \
		ERRORF("\n\tLocation : %s(), %s:%u\n", __FUNCTION__, __FILE__, \
		       __LINE__);                                              \
		perror("      OS message ");                                   \
		ERRORF("\n");                                                  \
		exit(EXIT_FAILURE);                                            \
	} while (0)

extern size_t bpf_insn_socket1_cnt;
extern struct bpf_insn bpf_insn_socket1[];
extern struct tbpf_reloc bpf_reloc_socket1[];

char payload[] = {0xde, 0xad, 0x01, 0x20, 0x00, 0x01, 0x00, 0x00,
		  0x00, 0x00, 0x00, 0x00, 0x0a, 0x63, 0x6c, 0x6f,
		  0x75, 0x64, 0x66, 0x6c, 0x61, 0x72, 0x65, 0x03,
		  0x63, 0x6f, 0x6d, 0x00, 0x00, 0x01, 0x00, 0x01};

int main()
{
	int stats = tbpf_create_map(BPF_MAP_TYPE_ARRAY, sizeof(uint32_t),
				       sizeof(uint64_t), 128, 0);
	if (stats < 0) {
		PFATAL("bpf(BPF_MAP_CREATE, BPF_MAP_TYPE_ARRAY)");
	}

	tbpf_fill_symbol(bpf_insn_socket1, bpf_reloc_socket1,
			 "stats", stats);

	char log_buf[16 * 1024];
	int bpf_prog = tbpf_load_program(
		BPF_PROG_TYPE_SOCKET_FILTER, bpf_insn_socket1,
		bpf_insn_socket1_cnt, "Dual BSD/GPL",
		KERNEL_VERSION(4, 4, 0), log_buf, sizeof(log_buf));
	if (bpf_prog < 0) {
		PFATAL("Bpf Log:\n%s\n bpf(BPF_PROG_LOAD)", log_buf);
	}

	struct sockaddr_in sin = {
		.sin_family = AF_INET,
		.sin_port = htons(53),
		.sin_addr = {0x01010101},
	};

	int sd = socket(sin.sin_family, SOCK_DGRAM, 0);
	if (sd < 0) {
		PFATAL("socket()");
	}

	int r = setsockopt(sd, SOL_SOCKET, SO_ATTACH_BPF, &bpf_prog, sizeof(bpf_prog));
	if (r < 0){
		PFATAL("setsockopt(SO_ATTACH_BPF)");
	}

	r = connect(sd, (struct sockaddr *)&sin, sizeof(sin));
	if (r < 0) {
		PFATAL("connect()");
		return -1;
	}

	write(sd, payload, sizeof(payload));
	char buf[1024];
	read(sd, buf, sizeof(buf));

	uint32_t key = 0;
	for (key = 0; key < 4; key ++ ){
		uint64_t value = 0;
		r = tbpf_map_lookup_elem(stats, &key, &value);
		if (r < 0) {
			PFATAL("bpf_map_lookup_elem");
		}
		printf("%d -> %20lu 0x%016lx\n", key, value, value);
	}

	close(sd);
	close(bpf_prog);
	close(stats);
	return 0;
}

Makefile

.PHONY: all
all: venv/.ok bpf.h bpf_helpers.h
	clang -Wall -Wextra -g -ggdb \
		-O2 -emit-llvm \
		-c ebpf-bug-kern.c \
		-S -o - \
		| llc -march=bpf -filetype=obj \
		-o  ebpf-bug-kern.o
	cat ebpf-bug-kern.o \
		| ./venv/bin/python3 tbpf-decode-elf.py /dev/stdin \
			socket1 \
		> ebpf-bug-ebpf.c

	clang -g -Wall -Wextra -O2 \
		tbpf.c \
		ebpf-bug-ebpf.c \
		ebpf-bug.c \
		-o ebpf-bug

	llvm-objdump --source --disassemble ebpf-bug-kern.o \
		| head -n 20


venv/.ok:
	virtualenv venv --python=python3
	./venv/bin/pip3 install pyelftools
	touch $@

bpf.h:
	wget https://raw.githubusercontent.com/torvalds/linux/master/include/uapi/linux/bpf.h
bpf_helpers.h:
	wget https://raw.githubusercontent.com/torvalds/linux/master/tools/testing/selftests/bpf/bpf_helpers.h

tbpf-decode-elf.py

from elftools.elf.elffile import ELFFile
import io
import struct
import sys

bpf_insn_template = """\
{
\t\t.code    = 0x%x,
\t\t.dst_reg = BPF_REG_%d,
\t\t.src_reg = BPF_REG_%d,
\t\t.off     = %d,
\t\t.imm     = %d\t/*%s*/
\t}\
"""

def parse_bpf(bytecode):
    list_of_insns = []
    for b_offset in range(0, len(bytecode), 8):
        instruction = bytecode[b_offset : b_offset + 8]
        opcode, src_and_dst, offset, imm = struct.unpack("BBhi", instruction[0:8])
        dst_reg, src_reg = src_and_dst & 0x0F, (src_and_dst & 0xF0) >> 4
        list_of_insns.append( (opcode, dst_reg, src_reg, offset, imm) )
    return list_of_insns

def process_file(f, section):
    elffile = ELFFile(f)

    symtab = elffile.get_section_by_name(".symtab")
    symtab_syms = list(symtab.iter_symbols())

    s = elffile.get_section_by_name(section)
    list_of_insns = parse_bpf(s.data())

    reladyn = elffile.get_section_by_name('.rel' + section)

    list_of_relocs = []
    if reladyn:
        for reloc in reladyn.iter_relocations():
            s = symtab_syms[reloc['r_info_sym']]
            list_of_relocs.append( (reloc['r_info_type'], reloc['r_offset'], s.name) )

    return list_of_insns, list_of_relocs

filename = sys.argv[1]
f = io.BytesIO(open(filename, 'rb').read())

print('''\
/* AUTOGENERATED DO NOT EDIT */
#include <linux/bpf.h>
#include <stddef.h>
#include <stdint.h>

#include "tbpf.h"
''')

for section in sys.argv[2:]:
    list_of_insns, list_of_relocs = process_file(f, section)

    insns = []
    for i, (opcode, dst_reg, src_reg, offset, imm) in enumerate(list_of_insns):
        r = ''
        for t, o, n in list_of_relocs:
            if o / 8 == i:
                r = ' relocation for %s ' % (n,)
        s = bpf_insn_template % (opcode, dst_reg, src_reg, offset, imm, r)
        insns.append( s )


    print('''\
size_t bpf_insn_%s_cnt = %s;

struct bpf_insn bpf_insn_%s[] = {
\t%s};\
''' % (section, len(insns), section, ', '.join(insns)))

    reloc_template = '''\
{
\t\t.name = %s,
\t\t.type = %d,
\t\t.offset = %d
\t}\
'''
    relocs = []
    for t, o, n in list_of_relocs + [(False, 0, 0)]:
        s = reloc_template % ('"' + n + '"' if n else 'NULL', t, o / 8)
        relocs.append(s)

    print('''

struct tbpf_reloc bpf_reloc_%s[] = {
\t%s};
''' % (section, ', '.join(relocs)))

tbpf.c

/*
 * This code is based on bpf.c from:
 * https://github.com/torvalds/linux/blob/master/tools/lib/bpf/bpf.c
 *
 * but as opposed to bpf.c or libbpf.c it does not have a dependency
 * on libelf.
 */
#include <linux/bpf.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/syscall.h>
#include <unistd.h>

#include "tbpf.h"

static inline int sys_bpf(enum bpf_cmd cmd, union bpf_attr *attr,
			  unsigned int size)
{
	return syscall(__NR_bpf, cmd, attr, size);
}

/* Fixup a relocation in ebpf bpf_insn table. */
int tbpf_fill_symbol(struct bpf_insn *insns, struct tbpf_reloc *relocs,
		     const char *symbol, int32_t value)
{
	int c = 0;
	while (relocs && relocs->name && relocs->name[0] != '\x00') {
		if (strcmp(relocs->name, symbol) == 0) {
			switch (relocs->type) {
			case 1:
				insns[relocs->offset].src_reg = 1;
				insns[relocs->offset].imm = value;
				c += 1;
				break;
			default:
				fprintf(stderr,
					"FATAL: unknown relocation %d\n",
					relocs->type);
				abort();
			}
		}
		relocs++;
	}
	return c;
}

int tbpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
		    int max_entries, uint32_t map_flags)
{
	union bpf_attr attr = {};

	attr.map_type = map_type;
	attr.key_size = key_size;
	attr.value_size = value_size;
	attr.max_entries = max_entries;
	attr.map_flags = map_flags;
	return sys_bpf(BPF_MAP_CREATE, &attr, sizeof(attr));
}

int tbpf_load_program(enum bpf_prog_type prog_type,
		      const struct bpf_insn *insns, size_t insns_cnt,
		      const char *license, uint32_t kern_version, char *log_buf,
		      size_t log_buf_sz)
{
	union bpf_attr attr = {};

	attr.prog_type = prog_type;
	attr.insns = (uint64_t)insns;
	attr.insn_cnt = insns_cnt;
	attr.license = (uint64_t)license;
	attr.log_buf = (uint64_t)NULL;
	attr.log_size = 0;
	attr.log_level = 0;
	attr.kern_version = kern_version;

	int fd = sys_bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
	if (fd >= 0 || !log_buf || !log_buf_sz)
		return fd;

	/* Try again with log */
	attr.log_buf = (uint64_t)log_buf;
	attr.log_size = log_buf_sz;
	attr.log_level = 1;
	log_buf[0] = 0;
	return sys_bpf(BPF_PROG_LOAD, &attr, sizeof(attr));
}

int tbpf_prog_attach(int prog_fd, int target_fd, enum bpf_attach_type type,
		     unsigned int flags)
{
	union bpf_attr attr = {};

	attr.target_fd = target_fd;
	attr.attach_bpf_fd = prog_fd;
	attr.attach_type = type;
	attr.attach_flags = flags;

	return sys_bpf(BPF_PROG_ATTACH, &attr, sizeof(attr));
}

int tbpf_map_update_elem(int fd, const void *key, const void *value,
			 uint64_t flags)
{
	union bpf_attr attr = {};

	attr.map_fd = fd;
	attr.key = (uint64_t)key;
	attr.value = (uint64_t)value;
	attr.flags = flags;

	return sys_bpf(BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
}

int tbpf_map_delete_elem(int fd, const void *key)
{
	union bpf_attr attr = {};

	attr.map_fd = fd;
	attr.key = (uint64_t)key;

	return sys_bpf(BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
}

int tbpf_map_lookup_elem(int fd, const void *key, void *value)
{
	union bpf_attr attr = {};

	attr.map_fd = fd;
	attr.key = (uint64_t)key;
	attr.value = (uint64_t)value;

	return sys_bpf(BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
}

tbpf.h

#define KERNEL_VERSION(a, b, c) ((a)*65536 + (b)*256 + (c))

/* tbpf.c */

/* See https://lkml.org/lkml/2014/8/13/116 and
 * https://patchwork.ozlabs.org/patch/930413/ for the reocation type
 * BPF_PSEUDO_MAP_FD or R_BPF_MAP_FD with value 1 */

/* Relocations, as exposed in format consumeable by C */
struct tbpf_reloc {
	char *name; /* Name of the symbol */
	int type;   /* Type of relocation, expected 1 */
	int offset; /* Offset: ebpf instruction number */
};

int tbpf_fill_symbol(struct bpf_insn *insns, struct tbpf_reloc *relocs,
		     const char *symbol, int32_t value);

int tbpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
		    int max_entries, uint32_t map_flags);
int tbpf_load_program(enum bpf_prog_type prog_type,
		      const struct bpf_insn *insns, size_t insns_cnt,
		      const char *license, uint32_t kern_version, char *log_buf,
		      size_t log_buf_sz);
int tbpf_prog_attach(int prog_fd, int target_fd, enum bpf_attach_type type,
		     unsigned int flags);
int tbpf_map_update_elem(int fd, const void *key, const void *value,
			 uint64_t flags);
int tbpf_map_delete_elem(int fd, const void *key);
int tbpf_map_lookup_elem(int fd, const void *key, void *value);

Workaround - https://gist.github.com/jsitnicki/b97d2f8cd6a2dc8d3b86a11eeeeebf2d/revisions.