apparmor: improve overlapping domain attachment resolution

Overlapping domain attachments using the current longest left exact
match fail in some simple cases, and with the fix to ensure consistent
behavior by failing unresolvable attachments it becomes important to
do a better job.

eg. under the current match the following are unresolvable where
the alternation is clearly a better match under the most specific
left match rule.
  /**
  /{bin/,}usr/

Use a counting match that detects when a loop in the state machine is
enter, and return the match count to provide a better specific left
match resolution.

Signed-off-by: John Johansen <john.johansen@canonical.com>

4 files changed, 158 insertions, 14 deletions

diff --git a/security/apparmor/apparmorfs.c b/security/apparmor/apparmorfs.c
index 35e6b240fb14..3dcc122234c8 100644
--- a/security/apparmor/apparmorfs.c
+++ b/security/apparmor/apparmorfs.c
@@ -2159,6 +2159,7 @@ static struct aa_sfs_entry aa_sfs_entry_domain[] = {
 	AA_SFS_FILE_BOOLEAN("stack",		1),
 	AA_SFS_FILE_BOOLEAN("fix_binfmt_elf_mmap",	1),
 	AA_SFS_FILE_BOOLEAN("post_nnp_subset",	1),
+	AA_SFS_FILE_BOOLEAN("computed_longest_left",	1),
 	AA_SFS_DIR("attach_conditions",		aa_sfs_entry_attach),
 	AA_SFS_FILE_STRING("version", "1.2"),
 	{ }
diff --git a/security/apparmor/domain.c b/security/apparmor/domain.c
index 6a1279f11fcc..57cc892e05a2 100644
--- a/security/apparmor/domain.c
+++ b/security/apparmor/domain.c
@@ -385,10 +385,13 @@ static struct aa_profile *__attach_match(const struct linux_binprm *bprm,
 					 struct list_head *head,
 					 const char **info)
 {
-	int len = 0, xattrs = 0;
+	int candidate_len = 0, candidate_xattrs = 0;
 	bool conflict = false;
 	struct aa_profile *profile, *candidate = NULL;
 
+	AA_BUG(!name);
+	AA_BUG(!head);
+
 	list_for_each_entry_rcu(profile, head, base.list) {
 		if (profile->label.flags & FLAG_NULL &&
 		    &profile->label == ns_unconfined(profile->ns))
@@ -406,19 +409,20 @@ static struct aa_profile *__attach_match(const struct linux_binprm *bprm,
 		 * match.
 		 */
 		if (profile->xmatch) {
-			unsigned int state;
+			unsigned int state, count;
 			u32 perm;
 
-			if (profile->xmatch_len < len)
-				continue;
-
-			state = aa_dfa_match(profile->xmatch,
-					     DFA_START, name);
+			state = aa_dfa_leftmatch(profile->xmatch, DFA_START,
+						 name, &count);
 			perm = dfa_user_allow(profile->xmatch, state);
 			/* any accepting state means a valid match. */
 			if (perm & MAY_EXEC) {
-				int ret = aa_xattrs_match(bprm, profile, state);
+				int ret;
+
+				if (count < candidate_len)
+					continue;
 
+				ret = aa_xattrs_match(bprm, profile, state);
 				/* Fail matching if the xattrs don't match */
 				if (ret < 0)
 					continue;
@@ -429,10 +433,10 @@ static struct aa_profile *__attach_match(const struct linux_binprm *bprm,
 				 * The new match isn't more specific
 				 * than the current best match
 				 */
-				if (profile->xmatch_len == len &&
-				    ret <= xattrs) {
+				if (count == candidate_len &&
+				    ret <= candidate_xattrs) {
 					/* Match is equivalent, so conflict */
-					if (ret == xattrs)
+					if (ret == candidate_xattrs)
 						conflict = true;
 					continue;
 				}
@@ -441,8 +445,8 @@ static struct aa_profile *__attach_match(const struct linux_binprm *bprm,
 				 * xattrs, or a longer match
 				 */
 				candidate = profile;
-				len = profile->xmatch_len;
-				xattrs = ret;
+				candidate_len = profile->xmatch_len;
+				candidate_xattrs = ret;
 				conflict = false;
 			}
 		} else if (!strcmp(profile->base.name, name))
diff --git a/security/apparmor/include/match.h b/security/apparmor/include/match.h
index e0de00bd16a8..958d2b52a7b7 100644
--- a/security/apparmor/include/match.h
+++ b/security/apparmor/include/match.h
@@ -138,6 +138,25 @@ unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
 
 void aa_dfa_free_kref(struct kref *kref);
 
+#define WB_HISTORY_SIZE 8
+struct match_workbuf {
+	unsigned int count;
+	unsigned int pos;
+	unsigned int len;
+	unsigned int size;	/* power of 2, same as history size */
+	unsigned int history[WB_HISTORY_SIZE];
+};
+#define DEFINE_MATCH_WB(N)		\
+struct match_workbuf N = {		\
+	.count = 0,			\
+	.pos = 0,			\
+	.len = 0,			\
+	.size = WB_HISTORY_SIZE,			\
+}
+
+unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
+			      const char *str, unsigned int *count);
+
 /**
  * aa_get_dfa - increment refcount on dfa @p
  * @dfa: dfa  (MAYBE NULL)
diff --git a/security/apparmor/match.c b/security/apparmor/match.c
index 7ae6ed9d69dd..dd4c995c5e25 100644
--- a/security/apparmor/match.c
+++ b/security/apparmor/match.c
@@ -556,7 +556,6 @@ unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
 	return state;
 }
 
-
 /**
  * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
  * @dfa: the dfa to match @str against  (NOT NULL)
@@ -618,3 +617,124 @@ unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
 	*retpos = str;
 	return state;
 }
+
+#define inc_wb_pos(wb)						\
+do {								\
+	wb->pos = (wb->pos + 1) & (wb->size - 1);		\
+	wb->len = (wb->len + 1) & (wb->size - 1);		\
+} while (0)
+
+/* For DFAs that don't support extended tagging of states */
+static bool is_loop(struct match_workbuf *wb, unsigned int state,
+		    unsigned int *adjust)
+{
+	unsigned int pos = wb->pos;
+	unsigned int i;
+
+	if (wb->history[pos] < state)
+		return false;
+
+	for (i = 0; i <= wb->len; i++) {
+		if (wb->history[pos] == state) {
+			*adjust = i;
+			return true;
+		}
+		if (pos == 0)
+			pos = wb->size;
+		pos--;
+	}
+
+	*adjust = i;
+	return true;
+}
+
+static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
+				 const char *str, struct match_workbuf *wb,
+				 unsigned int *count)
+{
+	u16 *def = DEFAULT_TABLE(dfa);
+	u32 *base = BASE_TABLE(dfa);
+	u16 *next = NEXT_TABLE(dfa);
+	u16 *check = CHECK_TABLE(dfa);
+	unsigned int state = start, pos;
+
+	AA_BUG(!dfa);
+	AA_BUG(!str);
+	AA_BUG(!wb);
+	AA_BUG(!count);
+
+	*count = 0;
+	if (state == 0)
+		return 0;
+
+	/* current state is <state>, matching character *str */
+	if (dfa->tables[YYTD_ID_EC]) {
+		/* Equivalence class table defined */
+		u8 *equiv = EQUIV_TABLE(dfa);
+		/* default is direct to next state */
+		while (*str) {
+			unsigned int adjust;
+
+			wb->history[wb->pos] = state;
+			pos = base_idx(base[state]) + equiv[(u8) *str++];
+			if (check[pos] == state)
+				state = next[pos];
+			else
+				state = def[state];
+			if (is_loop(wb, state, &adjust)) {
+				state = aa_dfa_match(dfa, state, str);
+				*count -= adjust;
+				goto out;
+			}
+			inc_wb_pos(wb);
+			(*count)++;
+		}
+	} else {
+		/* default is direct to next state */
+		while (*str) {
+			unsigned int adjust;
+
+			wb->history[wb->pos] = state;
+			pos = base_idx(base[state]) + (u8) *str++;
+			if (check[pos] == state)
+				state = next[pos];
+			else
+				state = def[state];
+			if (is_loop(wb, state, &adjust)) {
+				state = aa_dfa_match(dfa, state, str);
+				*count -= adjust;
+				goto out;
+			}
+			inc_wb_pos(wb);
+			(*count)++;
+		}
+	}
+
+out:
+	if (!state)
+		*count = 0;
+	return state;
+}
+
+/**
+ * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
+ * @dfa: the dfa to match @str against  (NOT NULL)
+ * @start: the state of the dfa to start matching in
+ * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
+ * @count: current count of longest left.
+ *
+ * aa_dfa_match will match @str against the dfa and return the state it
+ * finished matching in. The final state can be used to look up the accepting
+ * label, or as the start state of a continuing match.
+ *
+ * Returns: final state reached after input is consumed
+ */
+unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
+			      const char *str, unsigned int *count)
+{
+	DEFINE_MATCH_WB(wb);
+
+	/* TODO: match for extended state dfas */
+
+	return leftmatch_fb(dfa, start, str, &wb, count);
+}