[v5,04/12] S.A.R.A.: generic DFA for string matching
diff mbox series

Message ID 1562410493-8661-5-git-send-email-s.mesoraca16@gmail.com
State New
Headers show
Series
  • S.A.R.A. a new stacked LSM
Related show

Commit Message

Salvatore Mesoraca July 6, 2019, 10:54 a.m. UTC
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.mesoraca16@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

Comments

Jann Horn July 6, 2019, 6:32 p.m. UTC | #1
On Sat, Jul 6, 2019 at 12:55 PM Salvatore Mesoraca
<s.mesoraca16@gmail.com> wrote:
> 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.

AppArmor already has a DFA implementation that takes a DFA machine
from userspace and runs it against file paths; see e.g.
aa_dfa_match(). Did you look into whether you could move their DFA to
some place like lib/ and reuse it instead of adding yet another
generic rule interface to the kernel?

[...]
> +++ 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.mesoraca16@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.

Throughout the series, you are adding files that both add an SPDX
identifier and have a description of the license in the comment block
at the top. The SPDX identifier already identifies the license.
Salvatore Mesoraca July 7, 2019, 4:01 p.m. UTC | #2
Jann Horn <jannh@google.com> wrote:
>
> On Sat, Jul 6, 2019 at 12:55 PM Salvatore Mesoraca
> <s.mesoraca16@gmail.com> wrote:
> > 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.
>
> AppArmor already has a DFA implementation that takes a DFA machine
> from userspace and runs it against file paths; see e.g.
> aa_dfa_match(). Did you look into whether you could move their DFA to
> some place like lib/ and reuse it instead of adding yet another
> generic rule interface to the kernel?

Yes, using AppArmor DFA cloud be a possibility.
Though, I didn't know how AppArmor's maintainers feel about this.
I thought that was easier to just implement my own.
Anyway I understand that re-using that code would be the optimal solution.
I'm adding in CC AppArmor's maintainers, let's see what they think about this.

> > +++ 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.mesoraca16@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.
>
> Throughout the series, you are adding files that both add an SPDX
> identifier and have a description of the license in the comment block
> at the top. The SPDX identifier already identifies the license.

I added the license description because I thought it was required anyway.
IANAL, if you tell me that SPDX it's enough I'll remove the description.

Thank you for your comments.
Jann Horn July 8, 2019, 5:37 p.m. UTC | #3
On Sun, Jul 7, 2019 at 6:01 PM Salvatore Mesoraca
<s.mesoraca16@gmail.com> wrote:
> Jann Horn <jannh@google.com> wrote:
> > Throughout the series, you are adding files that both add an SPDX
> > identifier and have a description of the license in the comment block
> > at the top. The SPDX identifier already identifies the license.
>
> I added the license description because I thought it was required anyway.
> IANAL, if you tell me that SPDX it's enough I'll remove the description.

IANAL too, but Documentation/process/license-rules.rst says:

====
The common way of expressing the license of a source file is to add the
matching boilerplate text into the top comment of the file.  Due to
formatting, typos etc. these "boilerplates" are hard to validate for
tools which are used in the context of license compliance.

An alternative to boilerplate text is the use of Software Package Data
Exchange (SPDX) license identifiers in each source file.  SPDX license
identifiers are machine parsable and precise shorthands for the license
under which the content of the file is contributed.  SPDX license
identifiers are managed by the SPDX Workgroup at the Linux Foundation and
have been agreed on by partners throughout the industry, tool vendors, and
legal teams.  For further information see https://spdx.org/

The Linux kernel requires the precise SPDX identifier in all source files.
The valid identifiers used in the kernel are explained in the section
`License identifiers`_ and have been retrieved from the official SPDX
license list at https://spdx.org/licenses/ along with the license texts.
====

and there have been lots of conversion patches to replace license
boilerplate headers with SPDX identifiers, see e.g. all the "treewide:
Replace GPLv2 boilerplate/reference with SPDX" patches.

Patch
diff mbox series

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.mesoraca16@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.mesoraca16@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.mesoraca16@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.mesoraca16@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)