[apparmor] [PATCH 1/4] switch away from doing an individual accept node for each perm bit
John Johansen
john.johansen at canonical.com
Mon Jun 22 17:59:59 UTC 2015
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 <john.johansen at canonical.com>
---
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
More information about the AppArmor
mailing list