accept nodes per perm bit where done from the very begining in a false belief that they would help produce minimized dfas because a nfa states could share partial overlapping permissions.
In reality they make tree factoring harder, reduce in longer nfa state sets during dfa construction and do not result in a minimized dfa. Moving to unique permission sets, allows us to minimize the number of nodes sets, and helps reduce recreating each set type multiple times during the dfa construction. Signed-off-by: John Johansen <[email protected]> --- parser/libapparmor_re/aare_rules.cc | 167 ++++++++++++++---------------------- 1 file changed, 65 insertions(+), 102 deletions(-) diff --git a/parser/libapparmor_re/aare_rules.cc b/parser/libapparmor_re/aare_rules.cc index d13c719..0c8aa82 100644 --- a/parser/libapparmor_re/aare_rules.cc +++ b/parser/libapparmor_re/aare_rules.cc @@ -35,13 +35,75 @@ #include "../immunix.h" +class UniquePerm { +public: + bool deny; + bool exact_match; + uint32_t perms; + uint32_t audit; + + bool operator<(UniquePerm const &rhs)const + { + if (deny == rhs.deny) { + if (exact_match == rhs.exact_match) { + if (perms == rhs.perms) + return audit < rhs.audit; + return perms < rhs.perms; + } + return exact_match; + } + return deny; + } +}; + +class UniquePermsCache { +public: + typedef map<UniquePerm, Node*> UniquePermMap; + typedef UniquePermMap::iterator iterator; + UniquePermMap nodes; + + UniquePermsCache(void) { }; + ~UniquePermsCache() { clear(); } + + void clear() + { + for (iterator i = nodes.begin(); i != nodes.end(); i++) { + delete i->second; + } + nodes.clear(void); + } + + Node *insert(bool deny, uint32_t perms, uint32_t audit, + bool exact_match) + { + UniquePerm tmp = { deny, exact_match, perms, audit }; + iterator res = nodes.find(tmp); + if (res == nodes.end()) { + Node *node; + if (deny) + node = new DenyMatchFlag(perms, audit); + else if (exact_match) + node = new ExactMatchFlag(perms, audit); + else + node = new MatchFlag(perms, audit); + pair<iterator, bool> val = nodes.insert(make_pair(tmp, node)); + if (val.second == false) + return val.first->second; + return node; + } + return res->second; + } +}; + +static UniquePermsCache unique_perms; + aare_rules::~aare_rules(void) { if (root) root->release(); - aare_reset_matchflags(); + unique_perms.clear(); } bool aare_rules::add_rule(const char *rule, int deny, uint32_t perms, @@ -50,30 +112,9 @@ bool aare_rules::add_rule(const char *rule, int deny, uint32_t perms, return add_rule_vec(deny, perms, audit, 1, &rule, flags); } -#define FLAGS_WIDTH 2 -#define MATCH_FLAGS_SIZE (sizeof(uint32_t) * 8 - 1) -MatchFlag *match_flags[FLAGS_WIDTH][MATCH_FLAGS_SIZE]; -DenyMatchFlag *deny_flags[FLAGS_WIDTH][MATCH_FLAGS_SIZE]; -#define EXEC_MATCH_FLAGS_SIZE (AA_EXEC_COUNT *2 * 2 * 2) /* double for each of ix pux, unsafe x bits * u::o */ -MatchFlag *exec_match_flags[FLAGS_WIDTH][EXEC_MATCH_FLAGS_SIZE]; /* mods + unsafe + ix + pux * u::o */ -ExactMatchFlag *exact_match_flags[FLAGS_WIDTH][EXEC_MATCH_FLAGS_SIZE]; /* mods + unsafe + ix + pux *u::o */ - void aare_reset_matchflags(void) { - uint32_t i, j; -#define RESET_FLAGS(group, size) { \ - for (i = 0; i < FLAGS_WIDTH; i++) { \ - for (j = 0; j < size; j++) { \ - if ((group)[i][j]) delete (group)[i][j]; \ - (group)[i][j] = NULL; \ - } \ - } \ -} - RESET_FLAGS(match_flags, MATCH_FLAGS_SIZE); - RESET_FLAGS(deny_flags, MATCH_FLAGS_SIZE); - RESET_FLAGS(exec_match_flags, EXEC_MATCH_FLAGS_SIZE); - RESET_FLAGS(exact_match_flags, EXEC_MATCH_FLAGS_SIZE); -#undef RESET_FLAGS + unique_perms.clear(); } void aare_rules::add_to_rules(Node *tree, Node *perms) @@ -91,84 +132,6 @@ static Node *cat_with_null_seperator(Node *l, Node *r) return new CatNode(new CatNode(l, new CharNode(0)), r); } -static Node *convert_file_perms(int deny, uint32_t perms, uint32_t audit, - bool exact_match) -{ - Node *accept; - - assert(perms != 0); - -/* 0x7f == 4 bits x mods + 1 bit unsafe mask + 1 bit ix, + 1 pux after shift */ -#define EXTRACT_X_INDEX(perm, shift) (((perm) >> (shift + 7)) & 0x7f) - - - /* the permissions set is assumed to be non-empty if any audit - * bits are specified */ - accept = NULL; - for (unsigned int n = 0; perms && n < (sizeof(perms) * 8); n++) { - uint32_t mask = 1 << n; - - if (!(perms & mask)) - continue; - - int ai = audit & mask ? 1 : 0; - perms &= ~mask; - - Node *flag; - if (mask & ALL_AA_EXEC_TYPE) - /* these cases are covered by EXEC_BITS */ - continue; - if (deny) { - if (deny_flags[ai][n]) { - flag = deny_flags[ai][n]; - } else { -//fprintf(stderr, "Adding deny ai %d mask 0x%x audit 0x%x\n", ai, mask, audit & mask); - deny_flags[ai][n] = new DenyMatchFlag(mask, audit & mask); - flag = deny_flags[ai][n]; - } - } else if (mask & AA_EXEC_BITS) { - uint32_t eperm = 0; - uint32_t index = 0; - if (mask & AA_USER_EXEC) { - eperm = mask | (perms & AA_USER_EXEC_TYPE); - index = EXTRACT_X_INDEX(eperm, AA_USER_SHIFT); - } else { - eperm = mask | (perms & AA_OTHER_EXEC_TYPE); - index = EXTRACT_X_INDEX(eperm, AA_OTHER_SHIFT) + (AA_EXEC_COUNT << 2); - } -//fprintf(stderr, "index %d eperm 0x%x\n", index, eperm); - if (exact_match) { - if (exact_match_flags[ai][index]) { - flag = exact_match_flags[ai][index]; - } else { - exact_match_flags[ai][index] = new ExactMatchFlag(eperm, audit & mask); - flag = exact_match_flags[ai][index]; - } - } else { - if (exec_match_flags[ai][index]) { - flag = exec_match_flags[ai][index]; - } else { - exec_match_flags[ai][index] = new MatchFlag(eperm, audit & mask); - flag = exec_match_flags[ai][index]; - } - } - } else { - if (match_flags[ai][n]) { - flag = match_flags[ai][n]; - } else { - match_flags[ai][n] = new MatchFlag(mask, audit & mask); - flag = match_flags[ai][n]; - } - } - if (accept) - accept = new AltNode(accept, flag); - else - accept = flag; - } /* for ... */ - - return accept; -} - bool aare_rules::add_rule_vec(int deny, uint32_t perms, uint32_t audit, int count, const char **rulev, dfaflags_t flags) { @@ -202,7 +165,7 @@ bool aare_rules::add_rule_vec(int deny, uint32_t perms, uint32_t audit, if (reverse) flip_tree(tree); - accept = convert_file_perms(deny, perms, audit, exact_match); + accept = unique_perms.insert(deny, perms, audit, exact_match); if (flags & DFA_DUMP_RULE_EXPR) { cerr << "rule: "; -- 2.1.4 -- AppArmor mailing list [email protected] Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
