diff --git a/libsepol/tests/libsepol-tests.c b/libsepol/tests/libsepol-tests.c
index dc8fd5ce..5ae6bedc 100644
--- a/libsepol/tests/libsepol-tests.c
+++ b/libsepol/tests/libsepol-tests.c
@@ -19,6 +19,7 @@
  */
 
 #include "test-cond.h"
+#include "test-ebitmap.h"
 #include "test-linker.h"
 #include "test-expander.h"
 #include "test-deps.h"
@@ -64,6 +65,7 @@ static bool do_tests(int interactive, int verbose)
 	if (CUE_SUCCESS != CU_initialize_registry())
 		return CU_get_error();
 
+	DECLARE_SUITE(ebitmap);
 	DECLARE_SUITE(cond);
 	DECLARE_SUITE(linker);
 	DECLARE_SUITE(expander);
diff --git a/libsepol/tests/test-ebitmap.c b/libsepol/tests/test-ebitmap.c
new file mode 100644
index 00000000..a21f18c0
--- /dev/null
+++ b/libsepol/tests/test-ebitmap.c
@@ -0,0 +1,711 @@
+#include "test-ebitmap.h"
+
+#include <stdlib.h>
+#include <time.h>
+
+#include <sepol/debug.h>
+#include <sepol/policydb/ebitmap.h>
+
+#define RANDOM_ROUNDS 10
+
+
+static int ebitmap_init_random(ebitmap_t *e, unsigned int length, int set_chance)
+{
+	unsigned int i;
+	int rc;
+
+	if (set_chance <= 0 || set_chance > 100)
+		return -EINVAL;
+
+	ebitmap_init(e);
+
+	for (i = 0; i < length; i++) {
+		if ((random() % 100) < set_chance) {
+			rc = ebitmap_set_bit(e, i, 1);
+			if (rc)
+				return rc;
+		}
+	}
+
+	return 0;
+}
+
+static void test_ebitmap_init_destroy(void)
+{
+	ebitmap_t e;
+
+	ebitmap_init(&e);
+	ebitmap_init(&e);
+	ebitmap_init(&e);
+
+	CU_ASSERT(ebitmap_is_empty(&e));
+	CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+
+	ebitmap_destroy(&e);
+	ebitmap_destroy(&e);
+	ebitmap_destroy(&e);
+
+	CU_ASSERT(ebitmap_is_empty(&e));
+	CU_ASSERT_PTR_NULL(ebitmap_startnode(&e));
+}
+
+static void test_ebitmap_cmp(void)
+{
+	ebitmap_t e1, e2;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+
+	CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+	CU_ASSERT_FALSE(ebitmap_cmp(&e1, &e2));
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 10, 1), 0);
+
+	CU_ASSERT(ebitmap_cmp(&e1, &e2));
+
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_set_and_get(void)
+{
+	ebitmap_t e;
+
+	ebitmap_init(&e);
+
+	CU_ASSERT(ebitmap_is_empty(&e));
+	CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, UINT32_MAX, 1), -EINVAL);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 1), 0);
+	CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 10);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 1);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 1), 0);
+	CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 1);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 1), 0);
+	CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 3);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 100);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 1);
+
+	{
+		ebitmap_node_t *n;
+		unsigned int bit;
+
+		ebitmap_for_each_positive_bit(&e, n, bit) {
+			CU_ASSERT(bit == 10 || bit == 50 || bit == 100);
+		}
+	}
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 100, 0), 0);
+	CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 2);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 50);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 100), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 10, 0), 0);
+	CU_ASSERT_FALSE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 1);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 50);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 10), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e, 50, 0), 0);
+	CU_ASSERT_TRUE(ebitmap_is_empty(&e));
+	CU_ASSERT_EQUAL(ebitmap_cardinality(&e), 0);
+	CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&e), 0);
+	CU_ASSERT_EQUAL(ebitmap_get_bit(&e, 50), 0);
+
+	ebitmap_destroy(&e);
+}
+
+static void test_ebitmap_or(void)
+{
+	ebitmap_t e1, e2, e3, e4;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+	ebitmap_init(&e3);
+	ebitmap_init(&e4);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e1), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e2, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e1, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e3), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e3, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_or(&dst, &e4, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	ebitmap_destroy(&e4);
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_and(void)
+{
+	ebitmap_t e1, e2, e12, e3, e4;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+	ebitmap_init(&e12);
+	ebitmap_init(&e3);
+	ebitmap_init(&e4);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 101, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e1), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e3), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e1, &e3), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e1));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e2, &e3), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e4, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_and(&dst, &e3, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	ebitmap_destroy(&e4);
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e12);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_xor(void)
+{
+	ebitmap_t e1, e2, e3, e4;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+	ebitmap_init(&e3);
+	ebitmap_init(&e4);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 1, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 3, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 5, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 6, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 9, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+
+	{
+		ebitmap_t dst1, dst2;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst1, &e1, &e1), 0);
+		CU_ASSERT(ebitmap_cmp(&dst1, &e4));
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst2, &dst1, &e1), 0);
+		CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+		ebitmap_destroy(&dst2);
+		ebitmap_destroy(&dst1);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e3, &e3), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e4, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e1, &e2), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_xor(&dst, &e2, &e4), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+		ebitmap_destroy(&dst);
+	}
+
+	ebitmap_destroy(&e4);
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_not(void)
+{
+	ebitmap_t e1, e2, e3, e4;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+	ebitmap_init(&e3);
+	ebitmap_init(&e4);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 0, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 5, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 2, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 3, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 4, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 6, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 7, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 8, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 9, 1), 0);
+
+	{
+		ebitmap_t dst1, dst2;
+
+		CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e3, 10), 0);
+		CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst1), 9);
+		CU_ASSERT_EQUAL(ebitmap_cardinality(&dst1), 10);
+
+		CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 10), 0);
+		CU_ASSERT(ebitmap_cmp(&dst2, &e3));
+
+		ebitmap_destroy(&dst2);
+		ebitmap_destroy(&dst1);
+	}
+
+	{
+		ebitmap_t dst1, dst2;
+
+		CU_ASSERT_EQUAL(ebitmap_not(&dst1, &e1, 11), 0);
+		CU_ASSERT(ebitmap_cmp(&dst1, &e2));
+		CU_ASSERT_EQUAL(ebitmap_not(&dst2, &dst1, 11), 0);
+		CU_ASSERT(ebitmap_cmp(&dst2, &e1));
+
+		ebitmap_destroy(&dst2);
+		ebitmap_destroy(&dst1);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 8), 0);
+		CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 7);
+		CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 5);
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_not(&dst, &e1, 12), 0);
+		CU_ASSERT_EQUAL(ebitmap_highest_set_bit(&dst), 11);
+		CU_ASSERT_EQUAL(ebitmap_cardinality(&dst), 8);
+
+		ebitmap_destroy(&dst);
+	}
+
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap_andnot(void)
+{
+	ebitmap_t e1, e2, e12, e3, e4;
+
+	ebitmap_init(&e1);
+	ebitmap_init(&e2);
+	ebitmap_init(&e12);
+	ebitmap_init(&e3);
+	ebitmap_init(&e4);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e1, 1013, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e2, 665, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e12, 1013, 1), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 10, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 11, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 100, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 101, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 430, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 665, 1), 0);
+	CU_ASSERT_EQUAL(ebitmap_set_bit(&e3, 1013, 1), 0);
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e1, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e2, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e2, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e12));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e3, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e1, &e3, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e2, &e12, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e2));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e4, &e4, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e4));
+
+		ebitmap_destroy(&dst);
+	}
+
+	{
+		ebitmap_t dst;
+
+		CU_ASSERT_EQUAL(ebitmap_andnot(&dst, &e3, &e4, 1024), 0);
+		CU_ASSERT(ebitmap_cmp(&dst, &e3));
+
+		ebitmap_destroy(&dst);
+	}
+
+	ebitmap_destroy(&e4);
+	ebitmap_destroy(&e3);
+	ebitmap_destroy(&e12);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap__random_impl(unsigned int length, int set_chance)
+{
+	ebitmap_t e1, e2, dst_cpy, dst_or, dst_and, dst_xor1, dst_xor2, dst_not1, dst_not2, dst_andnot;
+	unsigned int i;
+
+	CU_ASSERT_EQUAL(ebitmap_init_random(&e1, length, set_chance), 0);
+	CU_ASSERT_EQUAL(ebitmap_init_random(&e2, length, set_chance), 0);
+
+	CU_ASSERT_EQUAL(ebitmap_cpy(&dst_cpy, &e1), 0);
+	CU_ASSERT(ebitmap_cmp(&dst_cpy, &e1));
+
+	CU_ASSERT_EQUAL(ebitmap_or(&dst_or, &e1, &e2), 0);
+	for (i = 0; i < length; i++)
+		CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_or, i), ebitmap_get_bit(&e1, i) | ebitmap_get_bit(&e2, i));
+
+	CU_ASSERT_EQUAL(ebitmap_and(&dst_and, &e1, &e2), 0);
+	for (i = 0; i < length; i++)
+		CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_and, i), ebitmap_get_bit(&e1, i) & ebitmap_get_bit(&e2, i));
+
+	CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor1, &e1, &e2), 0);
+	for (i = 0; i < length; i++)
+		CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_xor1, i), ebitmap_get_bit(&e1, i) ^ ebitmap_get_bit(&e2, i));
+	CU_ASSERT_EQUAL(ebitmap_xor(&dst_xor2, &dst_xor1, &e2), 0);
+	CU_ASSERT(ebitmap_cmp(&dst_xor2, &e1));
+
+	CU_ASSERT_EQUAL(ebitmap_not(&dst_not1, &e1, length), 0);
+	for (i = 0; i < length; i++)
+		CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_not1, i), !ebitmap_get_bit(&e1, i));
+	CU_ASSERT_EQUAL(ebitmap_not(&dst_not2, &dst_not1, length), 0);
+	CU_ASSERT(ebitmap_cmp(&dst_not2, &e1));
+
+	CU_ASSERT_EQUAL(ebitmap_andnot(&dst_andnot, &e1, &e2, length), 0);
+	for (i = 0; i < length; i++)
+		CU_ASSERT_EQUAL(ebitmap_get_bit(&dst_andnot, i), ebitmap_get_bit(&e1, i) & !ebitmap_get_bit(&e2, i));
+
+	ebitmap_destroy(&dst_andnot);
+	ebitmap_destroy(&dst_not2);
+	ebitmap_destroy(&dst_not1);
+	ebitmap_destroy(&dst_xor2);
+	ebitmap_destroy(&dst_xor1);
+	ebitmap_destroy(&dst_and);
+	ebitmap_destroy(&dst_or);
+	ebitmap_destroy(&dst_cpy);
+	ebitmap_destroy(&e2);
+	ebitmap_destroy(&e1);
+}
+
+static void test_ebitmap__random(void)
+{
+	unsigned int i;
+
+	for (i = 0; i < RANDOM_ROUNDS; i++)
+		test_ebitmap__random_impl(5, 10);
+
+	for (i = 0; i < RANDOM_ROUNDS; i++)
+		test_ebitmap__random_impl(5, 90);
+
+	for (i = 0; i < RANDOM_ROUNDS; i++)
+		test_ebitmap__random_impl(1024, 50);
+
+	for (i = 0; i < RANDOM_ROUNDS; i++)
+		test_ebitmap__random_impl(8000, 5);
+
+	for (i = 0; i < RANDOM_ROUNDS; i++)
+		test_ebitmap__random_impl(8000, 95);
+}
+
+/*
+ * External hooks
+ */
+
+int ebitmap_test_init(void)
+{
+	srandom(time(NULL));
+
+	/* silence ebitmap_set_bit() failure message */
+	sepol_debug(0);
+
+	return 0;
+}
+
+int ebitmap_test_cleanup(void)
+{
+	return 0;
+}
+
+#define ADD_TEST(name) \
+	do { \
+		if (NULL == CU_add_test(suite, #name, test_##name)) { \
+			return CU_get_error(); \
+		} \
+	} while (0)
+
+int ebitmap_add_tests(CU_pSuite suite)
+{
+	ADD_TEST(ebitmap_init_destroy);
+	ADD_TEST(ebitmap_cmp);
+	ADD_TEST(ebitmap_set_and_get);
+	ADD_TEST(ebitmap_or);
+	ADD_TEST(ebitmap_and);
+	ADD_TEST(ebitmap_xor);
+	ADD_TEST(ebitmap_not);
+	ADD_TEST(ebitmap_andnot);
+	ADD_TEST(ebitmap__random);
+	return 0;
+}
diff --git a/libsepol/tests/test-ebitmap.h b/libsepol/tests/test-ebitmap.h
new file mode 100644
index 00000000..952a0421
--- /dev/null
+++ b/libsepol/tests/test-ebitmap.h
@@ -0,0 +1,10 @@
+#ifndef TEST_EBITMAP_H__
+#define TEST_EBITMAP_H__
+
+#include <CUnit/Basic.h>
+
+int ebitmap_test_init(void);
+int ebitmap_test_cleanup(void);
+int ebitmap_add_tests(CU_pSuite suite);
+
+#endif  /* TEST_EBITMAP_H__ */
