Creation of a generic Discrete Finite Automata implementation
for string matching. The transition tables have to be produced
in user-space.
This allows us to possibly support advanced string matching
patterns like regular expressions, but they need to be supported
by user-space tools.
Signed-off-by: Salvatore Mesoraca <s.mesorac...@gmail.com>
---
security/sara/Kconfig | 22 +++
security/sara/Makefile | 3 +-
security/sara/dfa.c | 335 +++++++++++++++++++++++++++++++++++++++
security/sara/dfa_test.c | 135 ++++++++++++++++
security/sara/include/dfa.h | 52 ++++++
security/sara/include/dfa_test.h | 29 ++++
security/sara/main.c | 6 +
7 files changed, 581 insertions(+), 1 deletion(-)
create mode 100644 security/sara/dfa.c
create mode 100644 security/sara/dfa_test.c
create mode 100644 security/sara/include/dfa.h
create mode 100644 security/sara/include/dfa_test.h
diff --git a/security/sara/Kconfig b/security/sara/Kconfig
index 0456220..b98cf27 100644
--- a/security/sara/Kconfig
+++ b/security/sara/Kconfig
@@ -13,6 +13,28 @@ menuconfig SECURITY_SARA
If unsure, answer N.
+config SECURITY_SARA_DFA_32BIT
+ bool "Use 32 bits instead of 16 bits for DFA states' id"
+ depends on SECURITY_SARA
+ default n
+ help
+ If you say Y here S.A.R.A. will use more memory, but you will be
+ able to configure more rules.
+ See Documentation/admin-guide/LSM/SARA.rst. for further information.
+
+ If unsure, answer N.
+
+config SECURITY_SARA_DFA_TEST
+ bool "Enable test interface for the internal DFA engine"
+ depends on SECURITY_SARA
+ default n
+ help
+ If you say Y here S.A.R.A. will enable a user-space interface
+ that can be used to test the DFA engine (e.g. via `saractl test`).
+ See Documentation/admin-guide/LSM/SARA.rst. for further information.
+
+ If unsure, answer N.
+
config SECURITY_SARA_DEFAULT_DISABLED
bool "S.A.R.A. will be disabled at boot."
depends on SECURITY_SARA
diff --git a/security/sara/Makefile b/security/sara/Makefile
index 14bf7a8..ffa1be1 100644
--- a/security/sara/Makefile
+++ b/security/sara/Makefile
@@ -1,3 +1,4 @@
obj-$(CONFIG_SECURITY_SARA) := sara.o
-sara-y := main.o securityfs.o utils.o sara_data.o
+sara-y := main.o securityfs.o utils.o sara_data.o dfa.o
+sara-$(CONFIG_SECURITY_SARA_DFA_TEST) += dfa_test.o
diff --git a/security/sara/dfa.c b/security/sara/dfa.c
new file mode 100644
index 0000000..e39b27e
--- /dev/null
+++ b/security/sara/dfa.c
@@ -0,0 +1,335 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * S.A.R.A. Linux Security Module
+ *
+ * Copyright (C) 2017 Salvatore Mesoraca <s.mesorac...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2, as
+ * published by the Free Software Foundation.
+ *
+ */
+
+#include <linux/mm.h>
+#include <linux/printk.h>
+#include <linux/ratelimit.h>
+#include <linux/slab.h>
+
+#include "include/sara.h"
+#include "include/dfa.h"
+#include "include/securityfs.h"
+
+#define DFA_MAGIC_SIZE 8
+#define DFA_MAGIC "SARADFAT"
+
+#define DFA_INPUTS 255
+
+#ifndef CONFIG_SECURITY_SARA_DFA_32BIT
+#define pr_err_dfa_size() \
+ pr_err_ratelimited("DFA: too many states. Recompile kernel with
CONFIG_SARA_DFA_32BIT.\n")
+#else
+#define pr_err_dfa_size() pr_err_ratelimited("DFA: too many states.\n")
+#endif
+
+void sara_dfa_free_tables(struct sara_dfa_tables *dfa)
+{
+ if (dfa) {
+ kvfree(dfa->output);
+ kvfree(dfa->def);
+ kvfree(dfa->base);
+ kvfree(dfa->next);
+ kvfree(dfa->check);
+ kvfree(dfa);
+ }
+}
+
+static struct sara_dfa_tables *sara_dfa_alloc_tables(sara_dfa_state states,
+ sara_dfa_state cmp_states)
+{
+ struct sara_dfa_tables *tmp = NULL;
+
+ tmp = kvzalloc(sizeof(*tmp), GFP_KERNEL_ACCOUNT);
+ if (!tmp)
+ goto err;
+ tmp->output = kvcalloc(states,
+ sizeof(*tmp->output),
+ GFP_KERNEL_ACCOUNT);
+ if (!tmp->output)
+ goto err;
+ tmp->def = kvcalloc(states,
+ sizeof(*tmp->def),
+ GFP_KERNEL_ACCOUNT);
+ if (!tmp->def)
+ goto err;
+ tmp->base = kvcalloc(states,
+ sizeof(*tmp->base),
+ GFP_KERNEL_ACCOUNT);
+ if (!tmp->base)
+ goto err;
+ tmp->next = kvcalloc(cmp_states,
+ sizeof(*tmp->next) * DFA_INPUTS,
+ GFP_KERNEL_ACCOUNT);
+ if (!tmp->next)
+ goto err;
+ tmp->check = kvcalloc(cmp_states,
+ sizeof(*tmp->check) * DFA_INPUTS,
+ GFP_KERNEL_ACCOUNT);
+ if (!tmp->check)
+ goto err;
+ tmp->states = states;
+ tmp->cmp_states = cmp_states;
+ return tmp;
+
+err:
+ sara_dfa_free_tables(tmp);
+ return ERR_PTR(-ENOMEM);
+}
+
+int sara_dfa_match(struct sara_dfa_tables *dfa,
+ const unsigned char *s,
+ sara_dfa_output *output)
+{
+ sara_dfa_state i, j;
+ sara_dfa_state c_state = 0;
+
+ /* Max s[x] value must be == DFA_INPUTS */
+ BUILD_BUG_ON((((1ULL << (sizeof(*s) * 8)) - 1) != DFA_INPUTS));
+
+ /*
+ * The DFA transition table is compressed using 5 linear arrays
+ * as shown in the Dragon Book.
+ * These arrays are: default, base, next, check and output.
+ * default, base and output have the same size and are indexed by
+ * state number.
+ * next and check tables have the same size and are indexed by
+ * the value from base for a given state and the input symbol.
+ * To match a string against this set of arrays we need to:
+ * - Use the base arrays to recover the index to use
+ * with check and next arrays for the current state and symbol.
+ * - If the value in the check array matches the current state
+ * number the next state should be retrieved from the next array,
+ * otherwise we take it from the default array.
+ * - If the next state is not valid we should return immediately
+ * - If the input sequence is over and the value in the output array
+ * is valid, the string matches, and we should return the output
+ * value.
+ */
+
+ for (i = 0; s[i]; i++) {
+ j = (dfa->base[c_state] * DFA_INPUTS) + s[i] - 1;
+ if (dfa->check[j] != c_state)
+ c_state = dfa->def[c_state];
+ else
+ c_state = dfa->next[j];
+ if (c_state == SARA_INVALID_DFA_VALUE)
+ return 0;
+ }
+
+ if (dfa->output[c_state] != SARA_INVALID_DFA_VALUE) {
+ *output = dfa->output[c_state];
+ return 1;
+ }
+ return 0;
+}
+
+struct sara_dfa_tables *sara_dfa_make_null(void)
+{
+ int i;
+ struct sara_dfa_tables *dfa = NULL;
+
+ dfa = sara_dfa_alloc_tables(1, 1);
+ if (unlikely(IS_ERR_OR_NULL(dfa)))
+ return NULL;
+ dfa->output[0] = SARA_INVALID_DFA_VALUE;
+ dfa->def[0] = SARA_INVALID_DFA_VALUE;
+ dfa->base[0] = 0;
+ for (i = 0; i < DFA_INPUTS; ++i)
+ dfa->next[i] = SARA_INVALID_DFA_VALUE;
+ for (i = 0; i < DFA_INPUTS; ++i)
+ dfa->check[i] = 0;
+ memset(dfa->hash, 0, SARA_CONFIG_HASH_LEN);
+ return dfa;
+}
+
+struct binary_dfa_header {
+ char magic[DFA_MAGIC_SIZE];
+ __le32 version;
+ __le32 states;
+ __le32 cmp_states;
+ char hash[SARA_CONFIG_HASH_LEN];
+} __packed;
+
+#define SARA_INVALID_DFA_VALUE_LOAD 0xffffffffu
+
+struct sara_dfa_tables *sara_dfa_load(const char *buf,
+ size_t buf_len,
+ bool (*is_valid)(sara_dfa_output))
+{
+ int ret;
+ struct sara_dfa_tables *dfa = NULL;
+ struct binary_dfa_header *h = (struct binary_dfa_header *) buf;
+ __le32 *p;
+ uint64_t i;
+ u32 version, states, cmp_states, tmp;
+
+ ret = -EINVAL;
+ if (unlikely(buf_len < sizeof(*h)))
+ goto out;
+
+ ret = -EINVAL;
+ if (unlikely(memcmp(h->magic, DFA_MAGIC, DFA_MAGIC_SIZE) != 0))
+ goto out;
+ version = le32_to_cpu(h->version);
+ states = le32_to_cpu(h->states);
+ cmp_states = le32_to_cpu(h->cmp_states);
+ if (unlikely(version != SARA_DFA_VERSION)) {
+ pr_err_ratelimited("DFA: unsupported version\n");
+ goto out;
+ }
+ if (unlikely(states >= SARA_INVALID_DFA_VALUE ||
+ cmp_states >= SARA_INVALID_DFA_VALUE)) {
+ pr_err_dfa_size();
+ goto out;
+ }
+ if (unlikely(states == 0 ||
+ cmp_states == 0))
+ goto out;
+ if (unlikely(((states * sizeof(u32) * 3) +
+ (cmp_states * sizeof(u32) * 2 * DFA_INPUTS) +
+ sizeof(*h)) != buf_len))
+ goto out;
+
+ ret = -ENOMEM;
+ dfa = sara_dfa_alloc_tables(h->states, h->cmp_states);
+ if (unlikely(IS_ERR_OR_NULL(dfa)))
+ goto out;
+
+ dfa->states = states;
+ dfa->cmp_states = cmp_states;
+
+ ret = -EINVAL;
+ p = (__le32 *) (buf + sizeof(*h));
+ for (i = 0; i < dfa->states; i++) {
+ tmp = le32_to_cpu(*p);
+ if (unlikely(tmp != SARA_INVALID_DFA_VALUE_LOAD &&
+ tmp >= dfa->states))
+ goto out_alloc;
+ dfa->def[i] = (sara_dfa_state) tmp;
+ ++p;
+ }
+ for (i = 0; i < dfa->states; i++) {
+ tmp = le32_to_cpu(*p);
+ if (unlikely(tmp >= dfa->cmp_states))
+ goto out_alloc;
+ dfa->base[i] = (sara_dfa_state) tmp;
+ ++p;
+ }
+ for (i = 0; i < (dfa->cmp_states * DFA_INPUTS); i++) {
+ tmp = le32_to_cpu(*p);
+ if (unlikely(tmp != SARA_INVALID_DFA_VALUE_LOAD &&
+ tmp >= dfa->states))
+ goto out_alloc;
+ dfa->next[i] = (sara_dfa_state) tmp;
+ ++p;
+ }
+ for (i = 0; i < (dfa->cmp_states * DFA_INPUTS); i++) {
+ tmp = le32_to_cpu(*p);
+ if (unlikely(tmp != SARA_INVALID_DFA_VALUE_LOAD &&
+ tmp >= dfa->states))
+ goto out_alloc;
+ dfa->check[i] = (sara_dfa_state) tmp;
+ ++p;
+ }
+ for (i = 0; i < dfa->states; i++) {
+ tmp = le32_to_cpu(*p);
+ if (unlikely(tmp != SARA_INVALID_DFA_VALUE_LOAD &&
+ !is_valid(tmp)))
+ goto out_alloc;
+ dfa->output[i] = (sara_dfa_state) tmp;
+ ++p;
+ }
+ if (unlikely((void *) p != (void *) (buf + buf_len)))
+ goto out_alloc;
+
+ BUILD_BUG_ON(sizeof(dfa->hash) != sizeof(h->hash));
+ memcpy(dfa->hash, h->hash, sizeof(dfa->hash));
+
+ return dfa;
+out_alloc:
+ sara_dfa_free_tables(dfa);
+out:
+ pr_err_ratelimited("DFA: invalid load\n");
+ return ERR_PTR(ret);
+}
+
+ssize_t sara_dfa_dump(const struct sara_dfa_tables *dfa, char **buffer)
+{
+ char *buf;
+ size_t buf_len = 0;
+ struct binary_dfa_header *h;
+ __le32 *p;
+ int i;
+
+ buf_len = sizeof(*h) +
+ dfa->states * sizeof(__le32) * 3 +
+ dfa->cmp_states * sizeof(__le32) * DFA_INPUTS * 2;
+ buf = kvmalloc(buf_len, GFP_KERNEL_ACCOUNT);
+ if (unlikely(!buf))
+ return -ENOMEM;
+
+ h = (struct binary_dfa_header *) buf;
+ memcpy(h->magic, DFA_MAGIC, DFA_MAGIC_SIZE);
+ h->version = cpu_to_le32(SARA_DFA_VERSION);
+ h->states = cpu_to_le32(dfa->states);
+ h->cmp_states = cpu_to_le32(dfa->cmp_states);
+ BUILD_BUG_ON(sizeof(dfa->hash) != sizeof(h->hash));
+ memcpy(h->hash, dfa->hash, sizeof(dfa->hash));
+
+ p = (__le32 *) (buf + sizeof(*h));
+ for (i = 0; i < dfa->states; i++) {
+ if (dfa->def[i] == SARA_INVALID_DFA_VALUE)
+ *p++ = cpu_to_le32(SARA_INVALID_DFA_VALUE_LOAD);
+ else
+ *p++ = cpu_to_le32(dfa->def[i]);
+ }
+ for (i = 0; i < dfa->states; i++) {
+ if (dfa->base[i] == SARA_INVALID_DFA_VALUE)
+ *p++ = cpu_to_le32(SARA_INVALID_DFA_VALUE_LOAD);
+ else
+ *p++ = cpu_to_le32(dfa->base[i]);
+ }
+ for (i = 0; i < (dfa->cmp_states * DFA_INPUTS); i++) {
+ if (dfa->next[i] == SARA_INVALID_DFA_VALUE)
+ *p++ = cpu_to_le32(SARA_INVALID_DFA_VALUE_LOAD);
+ else
+ *p++ = cpu_to_le32(dfa->next[i]);
+ }
+ for (i = 0; i < (dfa->cmp_states * DFA_INPUTS); i++) {
+ if (dfa->check[i] == SARA_INVALID_DFA_VALUE)
+ *p++ = cpu_to_le32(SARA_INVALID_DFA_VALUE_LOAD);
+ else
+ *p++ = cpu_to_le32(dfa->check[i]);
+ }
+ for (i = 0; i < dfa->states; i++) {
+ if (dfa->output[i] == SARA_INVALID_DFA_VALUE)
+ *p++ = cpu_to_le32(SARA_INVALID_DFA_VALUE_LOAD);
+ else
+ *p++ = cpu_to_le32(dfa->output[i]);
+ }
+
+ if (unlikely((void *) p != (void *) (buf + buf_len))) {
+ /*
+ * We can calculate the correct buffer size upfront.
+ * This should never happen.
+ */
+ kvfree(buf);
+ pr_crit("memory corruption in %s\n", __func__);
+ return 0;
+ }
+
+ *buffer = buf;
+ return buf_len;
+}
+
+#undef SARA_INVALID_DFA_VALUE_LOAD
diff --git a/security/sara/dfa_test.c b/security/sara/dfa_test.c
new file mode 100644
index 0000000..9c06414
--- /dev/null
+++ b/security/sara/dfa_test.c
@@ -0,0 +1,135 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * S.A.R.A. Linux Security Module
+ *
+ * Copyright (C) 2017 Salvatore Mesoraca <s.mesorac...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2, as
+ * published by the Free Software Foundation.
+ *
+ */
+
+#include "include/dfa.h"
+#include "include/securityfs.h"
+#include <linux/lsm_hooks.h>
+#include <linux/mutex.h>
+#include <linux/slab.h>
+
+#define SARA_DFA_MAX_RES_SIZE 20
+
+struct sara_dfa_tables *table;
+
+static DEFINE_MUTEX(test_lock);
+static sara_dfa_output result;
+
+static bool is_valid_output(sara_dfa_output output)
+{
+ return true;
+}
+
+static int config_load(const char *buf, size_t buf_len)
+{
+ struct sara_dfa_tables *dfa, *tmp;
+
+ dfa = sara_dfa_load(buf, buf_len, is_valid_output);
+ if (unlikely(IS_ERR_OR_NULL(dfa))) {
+ if (unlikely(dfa == NULL))
+ return -EINVAL;
+ else
+ return PTR_ERR(dfa);
+ }
+ mutex_lock(&test_lock);
+ tmp = table;
+ table = dfa;
+ mutex_unlock(&test_lock);
+ sara_dfa_free_tables(tmp);
+ return 0;
+}
+
+static int config_load_str(const char *buf, size_t buf_len)
+{
+ char *s;
+
+ s = kmalloc(buf_len+1, GFP_KERNEL_ACCOUNT);
+ if (unlikely(s == NULL))
+ return -ENOMEM;
+ s[buf_len] = '\0';
+ memcpy(s, buf, buf_len);
+
+ mutex_lock(&test_lock);
+ result = SARA_INVALID_DFA_VALUE;
+ sara_dfa_match(table, s, &result);
+ mutex_unlock(&test_lock);
+
+ kfree(s);
+
+ return 0;
+}
+
+static ssize_t config_dump_result(char **buf)
+{
+ char *s;
+
+ s = kzalloc(SARA_DFA_MAX_RES_SIZE, GFP_KERNEL_ACCOUNT);
+ if (unlikely(s == NULL))
+ return -ENOMEM;
+ mutex_lock(&test_lock);
+ if (result == SARA_INVALID_DFA_VALUE)
+ snprintf(s, SARA_DFA_MAX_RES_SIZE, "%u\n", 0xffffffff);
+ else
+ snprintf(s,
+ SARA_DFA_MAX_RES_SIZE,
+ "%u\n",
+ (unsigned int) result);
+ mutex_unlock(&test_lock);
+ *buf = s;
+ return strlen(s);
+}
+
+static struct sara_secfs_fptrs fptrs __lsm_ro_after_init = {
+ .load = config_load,
+};
+
+static struct sara_secfs_fptrs teststr __lsm_ro_after_init = {
+ .load = config_load_str,
+ .dump = config_dump_result,
+};
+
+static const struct sara_secfs_node dfa_test_fs[] __initconst = {
+ {
+ .name = ".load",
+ .type = SARA_SECFS_CONFIG_LOAD,
+ .data = &fptrs,
+ },
+ {
+ .name = "test",
+ .type = SARA_SECFS_CONFIG_LOAD,
+ .data = &teststr,
+ },
+ {
+ .name = "result",
+ .type = SARA_SECFS_CONFIG_DUMP,
+ .data = &teststr,
+ },
+};
+
+int __init sara_dfa_test_init(void)
+{
+ int ret;
+
+ table = sara_dfa_make_null();
+ if (unlikely(!table))
+ return -ENOMEM;
+ ret = sara_secfs_subtree_register("dfa_test",
+ dfa_test_fs,
+ ARRAY_SIZE(dfa_test_fs));
+ if (unlikely(ret))
+ goto out_fail;
+ return 0;
+
+out_fail:
+ sara_dfa_free_tables(table);
+ return ret;
+}
diff --git a/security/sara/include/dfa.h b/security/sara/include/dfa.h
new file mode 100644
index 0000000..a536b60
--- /dev/null
+++ b/security/sara/include/dfa.h
@@ -0,0 +1,52 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+/*
+ * S.A.R.A. Linux Security Module
+ *
+ * Copyright (C) 2017 Salvatore Mesoraca <s.mesorac...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2, as
+ * published by the Free Software Foundation.
+ *
+ */
+
+#ifndef __SARA_DFA_H
+#define __SARA_DFA_H
+
+#include "securityfs.h"
+
+#ifdef CONFIG_SARA_DFA_32BIT
+typedef uint32_t sara_dfa_state;
+typedef uint32_t sara_dfa_output;
+#define SARA_INVALID_DFA_VALUE 0xffffffffu
+#else
+typedef uint16_t sara_dfa_state;
+typedef uint16_t sara_dfa_output;
+#define SARA_INVALID_DFA_VALUE 0xffffu
+#endif
+
+#define SARA_DFA_VERSION 2
+
+struct sara_dfa_tables {
+ sara_dfa_state states;
+ sara_dfa_state cmp_states;
+ sara_dfa_output *output;
+ sara_dfa_state *def;
+ sara_dfa_state *base;
+ sara_dfa_state *next;
+ sara_dfa_state *check;
+ char hash[SARA_CONFIG_HASH_LEN];
+};
+
+int sara_dfa_match(struct sara_dfa_tables *dfa,
+ const unsigned char *s,
+ sara_dfa_output *output);
+struct sara_dfa_tables *sara_dfa_make_null(void);
+struct sara_dfa_tables *sara_dfa_load(const char *buf,
+ size_t buf_len,
+ bool (*is_valid)(sara_dfa_output));
+ssize_t sara_dfa_dump(const struct sara_dfa_tables *dfa, char **buffer);
+void sara_dfa_free_tables(struct sara_dfa_tables *dfa);
+
+#endif /* __SARA_DFA_H */
diff --git a/security/sara/include/dfa_test.h b/security/sara/include/dfa_test.h
new file mode 100644
index 0000000..f10f78a
--- /dev/null
+++ b/security/sara/include/dfa_test.h
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+/*
+ * S.A.R.A. Linux Security Module
+ *
+ * Copyright (C) 2017 Salvatore Mesoraca <s.mesorac...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2, as
+ * published by the Free Software Foundation.
+ *
+ */
+
+#ifndef __SARA_DFA_TEST_H
+#define __SARA_DFA_TEST_H
+
+#ifdef CONFIG_SECURITY_SARA_DFA_TEST
+
+#include <linux/init.h>
+int sara_dfa_test_init(void) __init;
+
+#else /* CONFIG_SECURITY_SARA_DFA_TEST */
+inline int sara_dfa_test_init(void)
+{
+ return 0;
+}
+#endif /* CONFIG_SECURITY_SARA_DFA_TEST */
+
+#endif /* __SARA_DFA_TEST_H */
diff --git a/security/sara/main.c b/security/sara/main.c
index dc5dda4..6b09500 100644
--- a/security/sara/main.c
+++ b/security/sara/main.c
@@ -17,6 +17,7 @@
#include <linux/module.h>
#include <linux/printk.h>
+#include "include/dfa_test.h"
#include "include/sara.h"
#include "include/sara_data.h"
#include "include/securityfs.h"
@@ -99,6 +100,11 @@ static int __init sara_init(void)
goto error;
}
+ if (sara_dfa_test_init()) {
+ pr_crit("impossible to initialize DFA test interface.\n");
+ goto error;
+ }
+
pr_debug("initialized.\n");
if (sara_enabled)
--
1.9.1
