tests: Add 50-sim-hash_collision test

libseccomp utilizes a hash table to manage BPF blocks.  It
currently employs MurmurHash3 where the key is the hashed values
of the BPF instruction blocks, the accumulator start, and the
accumulator end.  This test was added because of a mishandled
hash collision reported by Tor in GitHub issue #148.
* https://github.com/seccomp/libseccomp/issues/148

Signed-off-by: Tom Hromatka <tom.hromatka@oracle.com>
Signed-off-by: Paul Moore <paul@paul-moore.com>

5 files changed, 184 insertions, 3 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index 6d15043..a5bc9e4 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -55,3 +55,4 @@ util.pyc
 47-live-kill_process
 48-sim-32b_args
 49-sim-64b_comparisons
+50-sim-hash_collision
diff --git a/tests/50-sim-hash_collision.c b/tests/50-sim-hash_collision.c
new file mode 100644
index 0000000..24eba19
--- /dev/null
+++ b/tests/50-sim-hash_collision.c
@@ -0,0 +1,98 @@
+/**
+ * Seccomp Library test program
+ *
+ * Copyright (c) 2019 Oracle and/or its affiliates.  All rights reserved.
+ * Author: Tom Hromatka <tom.hromatka@oracle.com>
+ */
+
+/*
+ * This library is free software; you can redistribute it and/or modify it
+ * under the terms of version 2.1 of the GNU Lesser General Public License as
+ * published by the Free Software Foundation.
+ *
+ * This library is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
+ * for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this library; if not, see <http://www.gnu.org/licenses>.
+ */
+
+#include <errno.h>
+#include <unistd.h>
+
+#include <seccomp.h>
+
+#include "util.h"
+
+int main(int argc, char *argv[])
+{
+	int rc;
+	struct util_options opts;
+	scmp_filter_ctx ctx = NULL;
+
+	rc = util_getopt(argc, argv, &opts);
+	if (rc < 0)
+		goto out;
+
+	rc = seccomp_api_set(1);
+	if (rc != 0)
+		return -rc;
+
+	ctx = seccomp_init(SCMP_ACT_ERRNO(100));
+	if (ctx == NULL)
+		return ENOMEM;
+
+	rc = seccomp_arch_remove(ctx, SCMP_ARCH_NATIVE);
+	if (rc != 0)
+		goto out;
+	rc = seccomp_arch_add(ctx, SCMP_ARCH_X86_64);
+	if (rc != 0)
+		goto out;
+
+	/* libseccomp utilizes a hash table to manage BPF blocks.  It
+	 * currently employs MurmurHash3 where the key is the hashed values
+	 * of the BPF instruction blocks, the accumulator start, and the
+	 * accumulator end.  Changes to the hash algorithm will likely affect
+	 * this test.
+	 */
+
+	/* The following rules were derived from an issue reported by Tor:
+	 * https://github.com/seccomp/libseccomp/issues/148
+	 *
+	 * In the steps below, syscall 1001 is configured similarly to how
+	 * Tor configured socket.  The fairly complex rules below led to
+	 * a hash collision with rt_sigaction (syscall 1000) in this test.
+	 */
+
+	rc = seccomp_rule_add(ctx, SCMP_ACT_ALLOW, 1001, 3,
+			      SCMP_A0(SCMP_CMP_EQ, 1),
+			      SCMP_A1(SCMP_CMP_MASKED_EQ, 0xf, 2),
+			      SCMP_A2(SCMP_CMP_EQ, 3));
+	if (rc != 0)
+		goto out;
+	rc = seccomp_rule_add(ctx, SCMP_ACT_ALLOW, 1001, 2,
+			      SCMP_A0(SCMP_CMP_EQ, 1),
+			      SCMP_A1(SCMP_CMP_MASKED_EQ, 0xf, 1));
+	if (rc != 0)
+		goto out;
+
+
+	rc = seccomp_rule_add(ctx, SCMP_ACT_ALLOW, 1000, 1,
+			      SCMP_A0(SCMP_CMP_EQ, 2));
+	if (rc != 0)
+		goto out;
+	rc = seccomp_rule_add(ctx, SCMP_ACT_ALLOW, 1000, 1,
+			      SCMP_A0(SCMP_CMP_EQ, 1));
+	if (rc != 0)
+		goto out;
+
+	rc = util_filter_output(&opts, ctx);
+	if (rc)
+		goto out;
+
+out:
+	seccomp_release(ctx);
+	return (rc < 0 ? -rc : rc);
+}
diff --git a/tests/50-sim-hash_collision.py b/tests/50-sim-hash_collision.py
new file mode 100755
index 0000000..d3c5f2f
--- /dev/null
+++ b/tests/50-sim-hash_collision.py
@@ -0,0 +1,61 @@
+#!/usr/bin/env python
+
+#
+# Seccomp Library test program
+#
+# Copyright (c) 2019 Oracle and/or its affiliates.  All rights reserved.
+# Author: Tom Hromatka <tom.hromatka@oracle.com>
+#
+
+#
+# This library is free software; you can redistribute it and/or modify it
+# under the terms of version 2.1 of the GNU Lesser General Public License as
+# published by the Free Software Foundation.
+#
+# This library is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
+# for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with this library; if not, see <http://www.gnu.org/licenses>.
+#
+
+import argparse
+import sys
+
+import util
+
+from seccomp import *
+
+def test(args):
+    set_api(1)
+    f = SyscallFilter(ERRNO(100))
+    f.remove_arch(Arch())
+    f.add_arch(Arch("x86_64"))
+
+    # libseccomp utilizes a hash table to manage BPF blocks.  It currently
+    # employs MurmurHash3 where the key is the hashed values of the BPF
+    # instruction blocks, the accumulator start, and the accumulator end.
+    # Changes to the hash algorithm will likely affect this test.
+
+    # The following rules were derived from an issue reported by Tor:
+    # https://github.com/seccomp/libseccomp/issues/148
+    #
+    # In the steps below, syscall 1001 is configured similarly to how
+    # Tor configured socket.  The fairly complex rules below led to
+    # a hash collision with rt_sigaction (syscall 1000) in this test.
+
+    f.add_rule_exactly(ALLOW, 1001, Arg(0, EQ, 1), Arg(1, MASKED_EQ, 0xf, 2),
+                       Arg(2, EQ, 3))
+    f.add_rule_exactly(ALLOW, 1001, Arg(0, EQ, 1), Arg(1, MASKED_EQ, 0xf, 1))
+    f.add_rule_exactly(ALLOW, 1000, Arg(0, EQ, 2))
+    f.add_rule_exactly(ALLOW, 1000, Arg(0, EQ, 1))
+    return f
+
+args = util.get_opt()
+ctx = test(args)
+util.filter_output(args, ctx)
+
+# kate: syntax python;
+# kate: indent-mode python; space-indent on; indent-width 4; mixedindent off;
diff --git a/tests/50-sim-hash_collision.tests b/tests/50-sim-hash_collision.tests
new file mode 100644
index 0000000..d52d807
--- /dev/null
+++ b/tests/50-sim-hash_collision.tests
@@ -0,0 +1,18 @@
+#
+# libseccomp regression test automation data
+#
+# Copyright (c) 2019 Oracle and/or its affiliates.  All rights reserved.
+# Author: Tom Hromatka <tom.hromatka@oracle.com>
+#
+
+test type: bpf-sim
+
+# Testname		Arch	Syscall		Arg0	Arg1	Arg2	Arg3	Arg4	Arg5	Result
+50-sim-hash_collision	+x86_64 1000		1	N	N	N	N	N	ALLOW
+50-sim-hash_collision	+x86_64 1000		2	N	N	N	N	N	ALLOW
+50-sim-hash_collision	+x86_64 1000		3	N	N	N	N	N	ERRNO(100)
+50-sim-hash_collision	+x86_64 1001		1	2	3	N	N	N	ALLOW
+50-sim-hash_collision	+x86_64 1001		1	1	N	N	N	N	ALLOW
+50-sim-hash_collision	+x86_64 1001		2	N	N	N	N	N	ERRNO(100)
+50-sim-hash_collision	+x86_64 1001		1	3	N	N	N	N	ERRNO(100)
+50-sim-hash_collision	+x86_64 1001		1	2	4	N	N	N	ERRNO(100)
diff --git a/tests/Makefile.am b/tests/Makefile.am
index c89fe74..eb84e14 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -88,7 +88,8 @@ check_PROGRAMS = \
 	46-sim-kill_process \
 	47-live-kill_process \
 	48-sim-32b_args \
-	49-sim-64b_comparisons
+	49-sim-64b_comparisons \
+	50-sim-hash_collision
 
 EXTRA_DIST_TESTPYTHON = \
 	util.py \
@@ -139,7 +140,8 @@ EXTRA_DIST_TESTPYTHON = \
 	46-sim-kill_process.py \
 	47-live-kill_process.py \
 	48-sim-32b_args.py \
-	49-sim-64b_comparisons.py
+	49-sim-64b_comparisons.py \
+	50-sim-hash_collision.py
 
 EXTRA_DIST_TESTCFGS = \
 	01-sim-allow.tests \
@@ -190,7 +192,8 @@ EXTRA_DIST_TESTCFGS = \
 	46-sim-kill_process.tests \
 	47-live-kill_process.tests \
 	48-sim-32b_args.tests \
-	49-sim-64b_comparisons.tests
+	49-sim-64b_comparisons.tests \
+	50-sim-hash_collision.tests
 
 EXTRA_DIST_TESTSCRIPTS = \
 	38-basic-pfc_coverage.sh 38-basic-pfc_coverage.pfc