Generation of bpf program

The build binary creates the bpf filter based on the syscalls defined in
struct bpf_call. E.g:
  ./build test.bpf

First, a table with the filtered syscalls is built in ascending order of
syscall number and including the amount of syscalls of that type.
After, the BPF filter with a binary search tree is constructed with:
  1. the nodes for the tree search
  2. the leaves with all the syscall numbers
  3. every syscall arguments if present

Then, the BPF instructions are written in the input file.

Signed-off-by: Alice Frosi <afrosi@redhat.com>

4 files changed, 342 insertions, 91 deletions

diff --git a/Makefile b/Makefile
index 7fbd88b..eb409f7 100644
--- a/Makefile
+++ b/Makefile
@@ -20,8 +20,8 @@ bpf.out: qemu_filter build
 t.out: qemu_filter build
 	./build
 
-build: build.c filter.h numbers.h transform.h
-	$(CC) $(CFLAGS) -o build build.c
+build: build.c filter.c filter.h numbers.h
+	$(CC) $(CFLAGS) -o build filter.c build.c
 
 seitan-loader: loader.c
 	$(CC) $(CFLAGS) -o seitan-loader loader.c
diff --git a/build.c b/build.c
index 9695b5e..f99dc97 100644
--- a/build.c
+++ b/build.c
@@ -1,102 +1,32 @@
-// SPDX-License-Identifier: AGPL-3.0-or-later
-
-/* SEITAN - Syscall Expressive Interpreter, Transformer and Notifier
- *
- * build.c - Build BPF program and transformation table blobs
- *
- * Copyright (c) 2022 Red Hat GmbH
- * Author: Stefano Brivio <sbrivio@redhat.com>
- */
-
-#include <stdio.h>
+#define _GNU_SOURCE
+#include <stdbool.h>
 #include <stddef.h>
+#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <fcntl.h>
 #include <unistd.h>
 
-#include <linux/audit.h>
-#include <linux/filter.h>
-#include <linux/seccomp.h>
-
-struct syscall_numbers {
-	char name[1024];
-	long number;
-};
-
-enum transform {
-	NONE,
-	FD1_UNIX,
-	FDRET_SRC,
-	DEV_CHECK,
-};
-
 #include "filter.h"
-#include "numbers.h"
 
-struct table {
-	enum transform type;
-	long number;
-
-	char arg[6][1024];
+struct bpf_call calls[] = {
+	{
+		.name = "connect",
+		.args = { 0, 111, 0, 0, 0, 0 },
+		.check_arg = { false, false, false, false, false, false },
+	},
 };
 
-static struct table t[16];
-
-int main(void)
+int main(int argc, char **argv)
 {
-	struct table *tp = t;
-	char buf[BUFSIZ];
-	FILE *fp;
-	int fd;
-
-	fd = open(BUILD_BPF_OUT, O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC,
-		  S_IRUSR | S_IWUSR);
-	write(fd, BUILD_PROFILE, sizeof(BUILD_PROFILE));
-	close(fd);
-
-	fp = fopen(BUILD_IN, "r");
-	while (fgets(buf, BUFSIZ, fp)) {
-		char name[1024];
-		char type[1024];
-		unsigned i;
-
-		if (*buf == '\n' || *buf == '#')
-			continue;
-		if (sscanf(buf, "%s %s " /* syscall, type */
-				"%s %s %s %s %s %s", name, type,
-				tp->arg[0], tp->arg[1], tp->arg[2],
-				tp->arg[3], tp->arg[4], tp->arg[5]) < 3)
-			continue;
-
-		for (i = 0; i < sizeof(numbers) / sizeof(numbers[0]); i++) {
-			if (!strcmp(name, numbers[i].name))
-				break;
-		}
-
-		if (i == sizeof(numbers))
-			continue;
-
-		if (!strcmp(type, "fd1_unix"))
-			tp->type = 1;
-		else if (!strcmp(type, "fdret_src"))
-			tp->type = 2;
-		else if (!strcmp(type, "dev_check"))
-			tp->type = 3;
-		else
-			continue;
-
-		tp->number = numbers[i].number;
-
-		tp++;
+	int ret;
+	if (argc < 2) {
+		perror("missing input file");
+		exit(EXIT_FAILURE);
+	}
+	ret = convert_bpf(argv[1], calls, sizeof(calls) / sizeof(calls[0]));
+	if (ret < 0) {
+		perror("converting bpf program");
+		exit(EXIT_FAILURE);
 	}
-	fclose(fp);
-
-	fd = open(BUILD_TRANSFORM_OUT,
-		  O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC, S_IRUSR | S_IWUSR);
-
-	write(fd, t, sizeof(t));
-	close(fd);
-
 	return 0;
 }
diff --git a/filter.c b/filter.c
new file mode 100644
index 0000000..f8b782d
--- /dev/null
+++ b/filter.c
@@ -0,0 +1,282 @@
+#define _GNU_SOURCE
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "numbers.h"
+#include "filter.h"
+
+#define N_SYSCALL sizeof(numbers) / sizeof(numbers[0])
+
+static int compare_key(const void *key, const void *base)
+{
+	return strcmp((const char *)key,
+		      ((struct syscall_numbers *)base)->name);
+}
+
+int compare_bpf_call_names(const void *a, const void *b)
+{
+	return strcmp(((struct bpf_call *)a)->name,
+		      ((struct bpf_call *)b)->name);
+}
+
+static int compare_table_nr(const void *a, const void *b)
+{
+	return (((struct syscall_entry *)a)->nr -
+		((struct syscall_entry *)b)->nr);
+}
+
+static unsigned int count_shift_right(unsigned int n)
+{
+	unsigned int i = 0;
+	for (; n > 0; i++) {
+		n = n >> 1;
+	}
+	return i;
+}
+
+static void insert_pair(int jumps[], int arr[], unsigned int level)
+{
+	unsigned int i_a, i;
+	for (i = 0; i < level; i++) {
+		i_a = 2 * i + 1;
+		if (arr[i_a] == EMPTY) {
+			jumps[i] = arr[i_a - 1];
+		} else {
+			jumps[i] = arr[i_a];
+		}
+	}
+}
+
+unsigned int left_child(unsigned int parent_index)
+{
+	unsigned int level = count_shift_right(parent_index + 1);
+	/* 2^(level) -1 gives the beginning of the next interval */
+	unsigned int next_interval = (1 << level) - 1;
+	/* 2^(level -1) -1  gives the beginning of the current interval */
+	unsigned begin = (1 << (level - 1)) - 1;
+	unsigned i = parent_index - begin;
+	return next_interval + 2 * i;
+}
+
+unsigned int right_child(unsigned int parent_index)
+{
+	return left_child(parent_index) + 1;
+}
+
+void create_lookup_nodes(int jumps[], unsigned int n)
+{
+	unsigned int i, index;
+	unsigned int old_interval, interval;
+
+	for (i = 0; i < MAX_JUMPS; i++)
+		jumps[i] = EMPTY;
+
+	if (n < 2) {
+		jumps[0] = 0;
+		return;
+	}
+	old_interval = 1 << count_shift_right(n - 1);
+	interval = old_interval >> 1;
+
+	/* first scan populate the last level of jumps */
+	for (i = interval - 1, index = 1; index < old_interval && index < n;
+	     i++, index += 2) {
+		jumps[i] = index;
+	}
+	if (n % 2 == 1) {
+		jumps[i] = index - 1;
+	}
+	for (old_interval = interval, interval = interval / 2; interval > 0;
+	     old_interval = interval, interval = interval / 2) {
+		insert_pair(&jumps[interval - 1], &jumps[old_interval - 1],
+			    interval);
+	}
+}
+
+long resolve_syscall_nr(const char *name)
+{
+	struct syscall_numbers *p;
+	p = (struct syscall_numbers *)bsearch(
+		name, numbers, sizeof(numbers) / sizeof(numbers[0]),
+		sizeof(numbers[0]), compare_key);
+	if (p == NULL)
+		return -1;
+	return p->number;
+}
+
+/*
+ * Construct a syscall tables ordered by increasing syscall number
+ * @returns number of syscall entries in the table
+ */
+int construct_table(const struct bpf_call *entries, int n,
+		    struct syscall_entry *table)
+{
+	long nr;
+	unsigned int tn;
+	int i;
+
+	tn = 0;
+	for (i = 0; i < n; i++) {
+		table[i].count = 0;
+		table[i].entry = NULL;
+	}
+
+	for (i = 0; i < n; i++) {
+		if (tn > N_SYSCALL - 1)
+			return -1;
+		if (i > 0) {
+			if (strcmp((entries[i]).name, (entries[i - 1]).name) ==
+			    0) {
+				table[tn - 1].count++;
+				continue;
+			}
+		}
+		nr = resolve_syscall_nr((entries[i]).name);
+		if (nr < 0) {
+			fprintf(stderr, "wrong syscall number for %s\n",
+				(entries[i]).name);
+			continue;
+		}
+		table[tn].entry = &entries[i];
+		table[tn].count++;
+		table[tn].nr = nr;
+		tn++;
+	}
+	qsort(table, tn, sizeof(struct syscall_entry), compare_table_nr);
+
+	return tn;
+}
+
+static unsigned get_n_args(const struct syscall_entry *table)
+{
+	unsigned i, k, n;
+	n = 0;
+	for (i = 0; i < table->count; i++)
+		for (k = 0; k < 6; k++)
+			if ((table->entry + i)->check_arg[k])
+				n++;
+	return n;
+}
+
+static unsigned int get_total_args(const struct syscall_entry table[],
+				   unsigned int n_syscall)
+{
+	unsigned int i, n;
+	n = 0;
+	for (i = 0; i < n_syscall; i++) {
+		n += get_n_args(&table[i]);
+	}
+	return n;
+}
+
+unsigned int create_bfp_program(struct syscall_entry table[],
+				struct sock_filter filter[],
+				unsigned int n_syscall)
+{
+	unsigned int offset_left, offset_right;
+	unsigned int n_args, n_nodes;
+	unsigned int notify, accept;
+	unsigned int i, j, k, size;
+	unsigned int next_offset;
+	int nodes[MAX_JUMPS];
+
+	create_lookup_nodes(nodes, n_syscall);
+
+	size = 3;
+	/* No nodes if there is a single syscall */
+	n_nodes = (1 << count_shift_right(n_syscall - 1)) - 1;
+
+	n_args = get_total_args(table, n_syscall);
+
+	accept = 2 + n_nodes + 2 * n_syscall + n_args + 1;
+	notify = 2 + n_nodes + 2 * n_syscall + n_args + 2;
+
+	/* Pre */
+	/* cppcheck-suppress badBitmaskCheck */
+	filter[0] = (struct sock_filter)BPF_STMT(
+		BPF_LD | BPF_W | BPF_ABS,
+		(offsetof(struct seccomp_data, arch)));
+	filter[1] = (struct sock_filter)BPF_JUMP(
+		BPF_JMP | BPF_JEQ | BPF_K, SEITAN_AUDIT_ARCH, 0, accept - 2);
+	/* cppcheck-suppress badBitmaskCheck */
+	filter[2] = (struct sock_filter)BPF_STMT(
+		BPF_LD | BPF_W | BPF_ABS, (offsetof(struct seccomp_data, nr)));
+
+	/* Insert nodes */
+	for (i = 0; i < n_nodes; i++) {
+		if (nodes[i] == EMPTY) {
+			filter[size++] =
+				(struct sock_filter)JUMPA(accept - size);
+		} else {
+			offset_left = left_child(i) - i - 1;
+			offset_right = right_child(i) - i - 1;
+			filter[size++] = (struct sock_filter)JGE(
+				table[nodes[i]].nr, offset_right, offset_left);
+		}
+	}
+
+	next_offset = n_syscall - 1;
+	/* Insert leaves */
+	for (i = 0; i < n_syscall; i++) {
+		filter[size++] = (struct sock_filter)EQ(
+			table[i].nr, next_offset, accept - size);
+		next_offset += get_n_args(&table[i]);
+	}
+
+	/*
+	 * Insert args. Evaluate every args, if it doesn't match continue with
+	 * the following, otherwise notify.
+	 */
+	for (i = 0; i < n_syscall; i++) {
+		for (j = 0; j < (table[i]).count; j++) {
+			for (k = 0; k < 6; k++)
+				if ((table[i].entry + j)->check_arg[k]) {
+					filter[size++] = (struct sock_filter)EQ(
+						(table[i].entry + j)->args[k],
+						notify - size, 0);
+				}
+		}
+		filter[size++] = (struct sock_filter)JUMPA(accept - size);
+	}
+
+	/* Seccomp accept and notify instruction */
+	filter[size++] = (struct sock_filter)BPF_STMT(BPF_RET | BPF_K,
+						      SECCOMP_RET_ALLOW);
+	filter[size++] = (struct sock_filter)BPF_STMT(BPF_RET | BPF_K,
+						      SECCOMP_RET_USER_NOTIF);
+	return size;
+}
+
+static int compare_names(const void *a, const void *b)
+{
+	return strcmp(((struct syscall_numbers *)a)->name,
+		      ((struct syscall_numbers *)b)->name);
+}
+
+int convert_bpf(char *file, struct bpf_call *entries, int n)
+{
+	int nt, fd, fsize;
+	struct syscall_entry table[N_SYSCALL];
+	struct sock_filter filter[MAX_FILTER];
+
+	qsort(numbers, sizeof(numbers) / sizeof(numbers[0]), sizeof(numbers[0]),
+	      compare_names);
+
+	qsort(entries, n, sizeof(struct bpf_call), compare_bpf_call_names);
+	nt = construct_table(entries, n, table);
+
+	fsize = create_bfp_program(table, filter, nt);
+
+	fd = open(file, O_WRONLY | O_CREAT | O_TRUNC | O_CLOEXEC,
+		  S_IRUSR | S_IWUSR);
+	write(fd, filter, sizeof(struct sock_filter) * fsize);
+
+	close(fd);
+
+	return 0;
+}
diff --git a/filter.h b/filter.h
new file mode 100644
index 0000000..134a16b
--- /dev/null
+++ b/filter.h
@@ -0,0 +1,39 @@
+#ifndef FILTER_H_
+#define FILTER_H_
+
+#include <linux/filter.h>
+#include <linux/audit.h>
+#include <linux/seccomp.h>
+
+#define JGE(nr, right, left) \
+	BPF_JUMP(BPF_JMP | BPF_JGE | BPF_K, (nr), (right), (left))
+#define JUMPA(jump) BPF_JUMP(BPF_JMP | BPF_JA, (jump), 0, 0)
+#define EQ(nr, a1, a2) BPF_JUMP(BPF_JMP | BPF_JEQ | BPF_K, (nr), (a1), (a2))
+
+#define MAX_FILTER 1024
+
+#define MAX_JUMPS 128
+#define EMPTY -1
+
+struct bpf_call {
+	char *name;
+	int args[6];
+	bool check_arg[6];
+};
+
+struct syscall_entry {
+	unsigned int count;
+	long nr;
+	const struct bpf_call *entry;
+};
+
+void create_lookup_nodes(int jumps[], unsigned int n);
+unsigned int left_child(unsigned int parent_index);
+unsigned int right_child(unsigned int parent_index);
+
+unsigned int create_bfp_program(struct syscall_entry table[],
+				struct sock_filter filter[],
+				unsigned int n_syscall);
+int convert_bpf(char *file, struct bpf_call *entries, int n);
+
+#endif