[apparmor] [PATCH 03/10] Split out compressed dfa "transition table" compression
John Johansen
john.johansen at canonical.com
Thu Mar 10 20:35:53 UTC 2011
Split hfa into hfa and compressed_hfa files. The hfa portion focuses on
creating an manipulating hfas, while compressed_hfa is used for creating
compressed hfas that can be used/reused at run time with much less memory
usage than the full blown hfa.
Signed-off-by: John Johansen <john.johansen at canonical.com>
---
parser/libapparmor_re/Makefile | 7 +-
parser/libapparmor_re/aare_rules.cc | 7 +
parser/libapparmor_re/aare_rules.h | 4 +
parser/libapparmor_re/apparmor_re.h | 2 -
parser/libapparmor_re/compressed_hfa.cc | 424 +++++++++++++++++++++
parser/libapparmor_re/compressed_hfa.h | 56 +++
parser/libapparmor_re/expr-tree.cc | 28 ++
parser/libapparmor_re/expr-tree.h | 26 ++-
parser/libapparmor_re/hfa.cc | 614 +------------------------------
parser/libapparmor_re/hfa.h | 139 +++++++
10 files changed, 689 insertions(+), 618 deletions(-)
create mode 100644 parser/libapparmor_re/compressed_hfa.cc
create mode 100644 parser/libapparmor_re/compressed_hfa.h
create mode 100644 parser/libapparmor_re/hfa.h
diff --git a/parser/libapparmor_re/Makefile b/parser/libapparmor_re/Makefile
index de44ad7..ebbe2d2 100644
--- a/parser/libapparmor_re/Makefile
+++ b/parser/libapparmor_re/Makefile
@@ -12,18 +12,21 @@ BISON := bison
all : ${TARGET}
-libapparmor_re.a: parse.o expr-tree.o hfa.o aare_rules.o
+libapparmor_re.a: parse.o expr-tree.o hfa.o compressed_hfa.o aare_rules.o
ar ${ARFLAGS} $@ $^
expr-tree.o: expr-tree.cc expr-tree.h
$(LINK.cc) $< -c -o $@
-hfa.o: hfa.cc apparmor_re.h
+hfa.o: hfa.cc apparmor_re.h hfa.h
$(LINK.cc) $< -c -o $@
aare_rules.o: aare_rules.cc aare_rules.h
$(LINK.cc) $< -c -o $@
+compressed_hfa.o: compressed_hfa.cc compressed_hfa.h
+ $(LINK.cc) $< -c -o $@
+
parse.o : parse.cc apparmor_re.h expr-tree.h
$(LINK.cc) $< -c -o $@
diff --git a/parser/libapparmor_re/aare_rules.cc b/parser/libapparmor_re/aare_rules.cc
index 739eeb2..beeb259 100644
--- a/parser/libapparmor_re/aare_rules.cc
+++ b/parser/libapparmor_re/aare_rules.cc
@@ -19,13 +19,20 @@
* Wrapper around the dfa to convert aa rules into a dfa
*/
+#include <ostream>
+#include <iostream>
+#include <fstream>
#include <sstream>
#include <ext/stdio_filebuf.h>
+#include <assert.h>
+#include <stdlib.h>
#include "aare_rules.h"
#include "expr-tree.h"
#include "parse.h"
#include "hfa.h"
+#include "compressed_hfa.h"
+#include "../immunix.h"
struct aare_ruleset {
int reverse;
diff --git a/parser/libapparmor_re/aare_rules.h b/parser/libapparmor_re/aare_rules.h
index ddd5f44..027e21f 100644
--- a/parser/libapparmor_re/aare_rules.h
+++ b/parser/libapparmor_re/aare_rules.h
@@ -21,6 +21,10 @@
#ifndef __LIBAA_RE_RULES_H
#define __LIBAA_RE_RULES_H
+#include <stdint.h>
+
+#include "apparmor_re.h"
+
#ifdef __cplusplus
extern "C" {
#endif
diff --git a/parser/libapparmor_re/apparmor_re.h b/parser/libapparmor_re/apparmor_re.h
index 4199e82..6283fc1 100644
--- a/parser/libapparmor_re/apparmor_re.h
+++ b/parser/libapparmor_re/apparmor_re.h
@@ -10,8 +10,6 @@
#ifndef APPARMOR_RE_H
#define APPARMOR_RE_H
-#include <stdint.h>
-
typedef enum dfaflags {
DFA_CONTROL_EQUIV = 1 << 0,
DFA_CONTROL_TREE_NORMAL = 1 << 1,
diff --git a/parser/libapparmor_re/compressed_hfa.cc b/parser/libapparmor_re/compressed_hfa.cc
new file mode 100644
index 0000000..795d638
--- /dev/null
+++ b/parser/libapparmor_re/compressed_hfa.cc
@@ -0,0 +1,424 @@
+/*
+ * (C) 2006, 2007 Andreas Gruenbacher <agruen at suse.de>
+ * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
+ * Copyright 2009-2010 Canonical Ltd.
+ *
+ * The libapparmor library is licensed under the terms of the GNU
+ * Lesser General Public License, version 2.1. Please see the file
+ * COPYING.LGPL.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Create a compressed hfa from and hfa
+ */
+
+#include <map>
+#include <vector>
+#include <ostream>
+#include <iostream>
+#include <fstream>
+
+#include <arpa/inet.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "hfa.h"
+#include "compressed_hfa.h"
+
+
+void TransitionTable::init_free_list(vector <pair<size_t, size_t> > &free_list,
+ size_t prev, size_t start) {
+ for (size_t i = start; i < free_list.size(); i++) {
+ if (prev)
+ free_list[prev].second = i;
+ free_list[i].first = prev;
+ prev = i;
+ }
+ free_list[free_list.size() -1].second = 0;
+}
+
+/**
+ * new Construct the transition table.
+ */
+TransitionTable::TransitionTable(DFA& dfa, map<uchar, uchar>& eq,
+ dfaflags_t flags)
+ : eq(eq)
+{
+
+ if (flags & DFA_DUMP_TRANS_PROGRESS)
+ fprintf(stderr, "Compressing trans table:\r");
+
+
+ if (eq.empty())
+ max_eq = 255;
+ else {
+ max_eq = 0;
+ for(map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
+ if (i->second > max_eq)
+ max_eq = i->second;
+ }
+ }
+
+ /* Do initial setup adding up all the transitions and sorting by
+ * transition count.
+ */
+ size_t optimal = 2;
+ multimap <size_t, State *> order;
+ vector <pair<size_t, size_t> > free_list;
+
+ for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
+ if (*i == dfa.start || *i == dfa.nonmatching)
+ continue;
+ optimal += (*i)->cases.cases.size();
+ if (flags & DFA_CONTROL_TRANS_HIGH) {
+ size_t range = 0;
+ if ((*i)->cases.cases.size())
+ range = (*i)->cases.cases.rbegin()->first - (*i)->cases.begin()->first;
+ size_t ord = ((256 - (*i)->cases.cases.size()) << 8) |
+ (256 - range);
+ /* reverse sort by entry count, most entries first */
+ order.insert(make_pair(ord, *i));
+ }
+ }
+
+ /* Insert the dummy nonmatching transition by hand */
+ next_check.push_back(make_pair(dfa.nonmatching, dfa.nonmatching));
+ default_base.push_back(make_pair(dfa.nonmatching, 0));
+ num.insert(make_pair(dfa.nonmatching, num.size()));
+
+ accept.resize(dfa.states.size());
+ accept2.resize(dfa.states.size());
+ next_check.resize(optimal);
+ free_list.resize(optimal);
+
+ accept[0] = 0;
+ accept2[0] = 0;
+ first_free = 1;
+ init_free_list(free_list, 0, 1);
+
+ insert_state(free_list, dfa.start, dfa);
+ accept[1] = 0;
+ accept2[1] = 0;
+ num.insert(make_pair(dfa.start, num.size()));
+
+ int count = 2;
+
+ if (!(flags & DFA_CONTROL_TRANS_HIGH)) {
+ for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end();
+ i++) {
+ if (*i != dfa.nonmatching && *i != dfa.start) {
+ insert_state(free_list, *i, dfa);
+ accept[num.size()] = (*i)->accept;
+ accept2[num.size()] = (*i)->audit;
+ num.insert(make_pair(*i, num.size()));
+ }
+ if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
+ count++;
+ if (count % 100 == 0)
+ fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
+ }
+ }
+ } else {
+ for (multimap <size_t, State *>::iterator i = order.begin();
+ i != order.end(); i++) {
+ if (i->second != dfa.nonmatching && i->second != dfa.start) {
+ insert_state(free_list, i->second, dfa);
+ accept[num.size()] = i->second->accept;
+ accept2[num.size()] = i->second->audit;
+ num.insert(make_pair(i->second, num.size()));
+ }
+ if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
+ count++;
+ if (count % 100 == 0)
+ fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
+ }
+ }
+ }
+
+ if (flags & (DFA_DUMP_TRANS_STATS | DFA_DUMP_TRANS_PROGRESS)) {
+ ssize_t size = 4 * next_check.size() + 6 * dfa.states.size();
+ fprintf(stderr, "\033[2KCompressed trans table: states %ld, next/check %ld, optimal next/check %ld avg/state %.2f, compression %ld/%ld = %.2f %%\n", dfa.states.size(), next_check.size(), optimal, (float)next_check.size()/(float)dfa.states.size(), size, 512 * dfa.states.size(), 100.0 - ((float) size * 100.0 / (float)(512 * dfa.states.size())));
+ }
+}
+
+
+/**
+ * Does <cases> fit into position <base> of the transition table?
+ */
+bool TransitionTable::fits_in(vector <pair<size_t, size_t> > &free_list __attribute__((unused)),
+ size_t pos, Cases& cases)
+{
+ size_t c, base = pos - cases.begin()->first;
+ for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
+ c = base + i->first;
+ /* if it overflows the next_check array it fits in as we will
+ * resize */
+ if (c >= next_check.size())
+ return true;
+ if (next_check[c].second)
+ return false;
+ }
+
+ return true;
+}
+
+/**
+ * Insert <state> of <dfa> into the transition table.
+ */
+void TransitionTable::insert_state(vector <pair<size_t, size_t> > &free_list,
+ State *from, DFA& dfa)
+{
+ State *default_state = dfa.nonmatching;
+ size_t base = 0;
+ int resize;
+
+ Cases& cases = from->cases;
+ size_t c = cases.begin()->first;
+ size_t prev = 0;
+ size_t x = first_free;
+
+ if (cases.otherwise)
+ default_state = cases.otherwise;
+ if (cases.cases.empty())
+ goto do_insert;
+
+repeat:
+ resize = 0;
+ /* get the first free entry that won't underflow */
+ while (x && (x < c)) {
+ prev = x;
+ x = free_list[x].second;
+ }
+
+ /* try inserting until we succeed. */
+ while (x && !fits_in(free_list, x, cases)) {
+ prev = x;
+ x = free_list[x].second;
+ }
+ if (!x) {
+ resize = 256 - cases.begin()->first;
+ x = free_list.size();
+ /* set prev to last free */
+ } else if (x + 255 - cases.begin()->first >= next_check.size()) {
+ resize = (255 - cases.begin()->first - (next_check.size() - 1 - x));
+ for (size_t y = x; y; y = free_list[y].second)
+ prev = y;
+ }
+ if (resize) {
+ /* expand next_check and free_list */
+ size_t old_size = free_list.size();
+ next_check.resize(next_check.size() + resize);
+ free_list.resize(free_list.size() + resize);
+ init_free_list(free_list, prev, old_size);
+ if (!first_free)
+ first_free = old_size;;
+ if (x == old_size)
+ goto repeat;
+ }
+
+ base = x - c;
+ for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
+ next_check[base + j->first] = make_pair(j->second, from);
+ size_t prev = free_list[base + j->first].first;
+ size_t next = free_list[base + j->first].second;
+ if (prev)
+ free_list[prev].second = next;
+ if (next)
+ free_list[next].first = prev;
+ if (base + j->first == first_free)
+ first_free = next;
+ }
+
+do_insert:
+ default_base.push_back(make_pair(default_state, base));
+}
+
+/**
+ * Text-dump the transition table (for debugging).
+ */
+void TransitionTable::dump(ostream& os)
+{
+ map<size_t, const State *> st;
+ for (map<const State *, size_t>::iterator i = num.begin();
+ i != num.end();
+ i++) {
+ st.insert(make_pair(i->second, i->first));
+ }
+
+ os << "size=" << default_base.size() << " (accept, default, base): {state} -> {default state}" << endl;
+ for (size_t i = 0; i < default_base.size(); i++) {
+ os << i << ": ";
+ os << "(" << accept[i] << ", "
+ << num[default_base[i].first] << ", "
+ << default_base[i].second << ")";
+ if (st[i])
+ os << " " << *st[i];
+ if (default_base[i].first)
+ os << " -> " << *default_base[i].first;
+ os << endl;
+ }
+
+ os << "size=" << next_check.size() << " (next, check): {check state} -> {next state} : offset from base" << endl;
+ for (size_t i = 0; i < next_check.size(); i++) {
+ if (!next_check[i].second)
+ continue;
+
+ os << i << ": ";
+ if (next_check[i].second) {
+ os << "(" << num[next_check[i].first] << ", "
+ << num[next_check[i].second] << ")" << " "
+ << *next_check[i].second << " -> "
+ << *next_check[i].first << ": ";
+
+ size_t offs = i - default_base[num[next_check[i].second]].second;
+ if (eq.size())
+ os << offs;
+ else
+ os << (uchar)offs;
+ }
+ os << endl;
+ }
+}
+
+/**
+ * Create a flex-style binary dump of the DFA tables. The table format
+ * was partly reverse engineered from the flex sources and from
+ * examining the tables that flex creates with its --tables-file option.
+ * (Only the -Cf and -Ce formats are currently supported.)
+ */
+
+#include "flex-tables.h"
+#define YYTH_REGEX_MAGIC 0x1B5E783D
+
+static inline size_t pad64(size_t i)
+{
+ return (i + (size_t)7) & ~(size_t)7;
+}
+
+string fill64(size_t i)
+{
+ const char zeroes[8] = { };
+ string fill(zeroes, (i & 7) ? 8 - (i & 7) : 0);
+ return fill;
+}
+
+template<class Iter>
+size_t flex_table_size(Iter pos, Iter end)
+{
+ return pad64(sizeof(struct table_header) + sizeof(*pos) * (end - pos));
+}
+
+template<class Iter>
+void write_flex_table(ostream& os, int id, Iter pos, Iter end)
+{
+ struct table_header td = { 0, 0, 0, 0 };
+ size_t size = end - pos;
+
+ td.td_id = htons(id);
+ td.td_flags = htons(sizeof(*pos));
+ td.td_lolen = htonl(size);
+ os.write((char *)&td, sizeof(td));
+
+ for (; pos != end; ++pos) {
+ switch(sizeof(*pos)) {
+ case 4:
+ os.put((char)(*pos >> 24));
+ os.put((char)(*pos >> 16));
+ case 2:
+ os.put((char)(*pos >> 8));
+ case 1:
+ os.put((char)*pos);
+ }
+ }
+
+ os << fill64(sizeof(td) + sizeof(*pos) * size);
+}
+
+void TransitionTable::flex_table(ostream& os, const char *name)
+{
+ const char th_version[] = "notflex";
+ struct table_set_header th = { 0, 0, 0, 0 };
+
+ /**
+ * Change the following two data types to adjust the maximum flex
+ * table size.
+ */
+ typedef uint16_t state_t;
+ typedef uint32_t trans_t;
+
+ if (default_base.size() >= (state_t)-1) {
+ cerr << "Too many states (" << default_base.size() << ") for "
+ "type state_t" << endl;
+ exit(1);
+ }
+ if (next_check.size() >= (trans_t)-1) {
+ cerr << "Too many transitions (" << next_check.size() << ") for "
+ "type trans_t" << endl;
+ exit(1);
+ }
+
+ /**
+ * Create copies of the data structures so that we can dump the tables
+ * using the generic write_flex_table() routine.
+ */
+ vector<uint8_t> equiv_vec;
+ if (eq.size()) {
+ equiv_vec.resize(256);
+ for (map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
+ equiv_vec[i->first] = i->second;
+ }
+ }
+
+ vector<state_t> default_vec;
+ vector<trans_t> base_vec;
+ for (DefaultBase::iterator i = default_base.begin();
+ i != default_base.end();
+ i++) {
+ default_vec.push_back(num[i->first]);
+ base_vec.push_back(i->second);
+ }
+
+ vector<state_t> next_vec;
+ vector<state_t> check_vec;
+ for (NextCheck::iterator i = next_check.begin();
+ i != next_check.end();
+ i++) {
+ next_vec.push_back(num[i->first]);
+ check_vec.push_back(num[i->second]);
+ }
+
+ /* Write the actual flex parser table. */
+
+ size_t hsize = pad64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
+ th.th_magic = htonl(YYTH_REGEX_MAGIC);
+ th.th_hsize = htonl(hsize);
+ th.th_ssize = htonl(hsize +
+ flex_table_size(accept.begin(), accept.end()) +
+ flex_table_size(accept2.begin(), accept2.end()) +
+ (eq.size() ?
+ flex_table_size(equiv_vec.begin(), equiv_vec.end()) : 0) +
+ flex_table_size(base_vec.begin(), base_vec.end()) +
+ flex_table_size(default_vec.begin(), default_vec.end()) +
+ flex_table_size(next_vec.begin(), next_vec.end()) +
+ flex_table_size(check_vec.begin(), check_vec.end()));
+ os.write((char *)&th, sizeof(th));
+ os << th_version << (char)0 << name << (char)0;
+ os << fill64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
+
+
+ write_flex_table(os, YYTD_ID_ACCEPT, accept.begin(), accept.end());
+ write_flex_table(os, YYTD_ID_ACCEPT2, accept2.begin(), accept2.end());
+ if (eq.size())
+ write_flex_table(os, YYTD_ID_EC, equiv_vec.begin(), equiv_vec.end());
+ write_flex_table(os, YYTD_ID_BASE, base_vec.begin(), base_vec.end());
+ write_flex_table(os, YYTD_ID_DEF, default_vec.begin(), default_vec.end());
+ write_flex_table(os, YYTD_ID_NXT, next_vec.begin(), next_vec.end());
+ write_flex_table(os, YYTD_ID_CHK, check_vec.begin(), check_vec.end());
+}
diff --git a/parser/libapparmor_re/compressed_hfa.h b/parser/libapparmor_re/compressed_hfa.h
new file mode 100644
index 0000000..a3344b7
--- /dev/null
+++ b/parser/libapparmor_re/compressed_hfa.h
@@ -0,0 +1,56 @@
+/*
+ * (C) 2006, 2007 Andreas Gruenbacher <agruen at suse.de>
+ * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
+ * Copyright 2009-2010 Canonical Ltd.
+ *
+ * The libapparmor library is licensed under the terms of the GNU
+ * Lesser General Public License, version 2.1. Please see the file
+ * COPYING.LGPL.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Create a compressed hfa from and hfa
+ */
+#ifndef __LIBAA_RE_COMPRESSED_HFA_H
+#define __LIBAA_RE_COMPRESSED_HFA_H
+
+#include <map>
+#include <vector>
+
+#include "hfa.h"
+
+using namespace std;
+
+class TransitionTable {
+ typedef vector<pair<const State *, size_t> > DefaultBase;
+ typedef vector<pair<const State *, const State *> > NextCheck;
+public:
+ TransitionTable(DFA& dfa, map<uchar, uchar>& eq, dfaflags_t flags);
+ void dump(ostream& os);
+ void flex_table(ostream& os, const char *name);
+ void init_free_list(vector <pair<size_t, size_t> > &free_list, size_t prev, size_t start);
+ bool fits_in(vector <pair<size_t, size_t> > &free_list,
+ size_t base, Cases& cases);
+ void insert_state(vector <pair<size_t, size_t> > &free_list,
+ State *state, DFA& dfa);
+
+private:
+ vector<uint32_t> accept;
+ vector<uint32_t> accept2;
+ DefaultBase default_base;
+ NextCheck next_check;
+ map<const State *, size_t> num;
+ map<uchar, uchar>& eq;
+ uchar max_eq;
+ size_t first_free;
+};
+
+
+#endif /* __LIBAA_RE_COMPRESSED_HFA_H */
diff --git a/parser/libapparmor_re/expr-tree.cc b/parser/libapparmor_re/expr-tree.cc
index 2d5ca77..ef63256 100644
--- a/parser/libapparmor_re/expr-tree.cc
+++ b/parser/libapparmor_re/expr-tree.cc
@@ -574,3 +574,31 @@ Node *simplify_tree(Node *t, dfaflags_t flags)
return t;
}
+/**
+ * Flip the children of all cat nodes. This causes strings to be matched
+ * back-forth.
+ */
+void flip_tree(Node *node)
+{
+ for (depth_first_traversal i(node); i; i++) {
+ if (CatNode *cat = dynamic_cast<CatNode *>(*i)) {
+ swap(cat->child[0], cat->child[1]);
+ }
+ }
+}
+
+void dump_regexp_rec(ostream& os, Node *tree)
+{
+ if (tree->child[0])
+ dump_regexp_rec(os, tree->child[0]);
+ os << *tree;
+ if (tree->child[1])
+ dump_regexp_rec(os, tree->child[1]);
+}
+
+void dump_regexp(ostream& os, Node *tree)
+{
+ dump_regexp_rec(os, tree);
+ os << endl;
+}
+
diff --git a/parser/libapparmor_re/expr-tree.h b/parser/libapparmor_re/expr-tree.h
index 6a3ec31..c88283c 100644
--- a/parser/libapparmor_re/expr-tree.h
+++ b/parser/libapparmor_re/expr-tree.h
@@ -39,6 +39,8 @@
#include <stack>
#include <ostream>
+#include <stdint.h>
+
#include "apparmor_re.h"
using namespace std;
@@ -605,7 +607,7 @@ int debug_tree(Node *t);
Node *simplify_tree(Node *t, dfaflags_t flags);
void label_nodes(Node *root);
unsigned long hash_NodeSet(NodeSet *ns);
-
+void flip_tree(Node *node);
/* Comparison operator for sets of <NodeSet *>.
* Compare set hashes, and if the sets have the same hash
@@ -624,4 +626,26 @@ struct deref_less_than {
}
};
+class MatchFlag : public AcceptNode {
+public:
+MatchFlag(uint32_t flag, uint32_t audit) : flag(flag), audit(audit) {}
+ ostream& dump(ostream& os)
+ {
+ return os << '<' << flag << '>';
+ }
+
+ uint32_t flag;
+ uint32_t audit;
+ };
+
+class ExactMatchFlag : public MatchFlag {
+public:
+ ExactMatchFlag(uint32_t flag, uint32_t audit) : MatchFlag(flag, audit) {}
+};
+
+class DenyMatchFlag : public MatchFlag {
+public:
+ DenyMatchFlag(uint32_t flag, uint32_t quiet) : MatchFlag(flag, quiet) {}
+};
+
#endif /* __LIBAA_RE_EXPR */
diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
index 453a828..c392293 100644
--- a/parser/libapparmor_re/hfa.cc
+++ b/parser/libapparmor_re/hfa.cc
@@ -31,84 +31,12 @@
#include <iostream>
#include <fstream>
-
-#include <string.h>
-#include <getopt.h>
-#include <assert.h>
-#include <arpa/inet.h>
-
-#include <iostream>
-#include <fstream>
-
#include "expr-tree.h"
+#include "hfa.h"
#include "../immunix.h"
-
-class State;
-/**
- * State cases are identical to NodesCases except they map to State *
- * instead of NodeSet.
- * Out-edges from a state to another: we store the follow State
- * for each input character that is not a default match in cases and
- * default matches in otherwise as well as in all matching explicit cases
- * This avoids enumerating all the explicit tranitions for default matches.
- */
-typedef struct Cases {
- typedef map<uchar, State *>::iterator iterator;
- iterator begin() { return cases.begin(); }
- iterator end() { return cases.end(); }
-
- Cases() : otherwise(0) { }
- map<uchar, State *> cases;
- State *otherwise;
-} Cases;
-
-typedef list<State *> Partition;
-
-uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
-
-/*
- * State - DFA individual state information
- * label: a unique label to identify the state used for pretty printing
- * the non-matching state is setup to have label == 0 and
- * the start state is setup to have label == 1
- * audit: the audit permission mask for the state
- * accept: the accept permissions for the state
- * cases: set of transitions from this state
- * parition: Is a temporary work variable used during dfa minimization.
- * it can be replaced with a map, but that is slower and uses more
- * memory.
- * nodes: Is a temporary work variable used during dfa creation. It can
- * be replaced by using the nodemap, but that is slower
- */
-class State {
-public:
- State() : label (0), audit(0), accept(0), cases(), nodes(NULL) { };
- State(int l): label (l), audit(0), accept(0), cases(), nodes(NULL) { };
- State(int l, NodeSet *n) throw (int):
- label(l), audit(0), accept(0), cases(), nodes(n)
- {
- int error;
-
- /* Compute permissions associated with the State. */
- accept = accept_perms(nodes, &audit, &error);
- if (error) {
-cerr << "Failing on accept perms " << error << "\n";
- throw error;
- }
- };
-
- int label;
- uint32_t audit, accept;
- Cases cases;
- union {
- Partition *partition;
- NodeSet *nodes;
- };
-};
-
ostream& operator<<(ostream& os, const State& state)
{
/* dump the state label */
@@ -118,42 +46,6 @@ ostream& operator<<(ostream& os, const State& state)
return os;
}
-typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
-/* Transitions in the DFA. */
-
-/* dfa_stats - structure to group various stats about dfa creation
- * duplicates - how many duplicate NodeSets where encountered and discarded
- * proto_max - maximum length of a NodeSet encountered during dfa construction
- * proto_sum - sum of NodeSet length during dfa construction. Used to find
- * average length.
- */
-typedef struct dfa_stats {
- unsigned int duplicates, proto_max, proto_sum;
-} dfa_stats_t;
-
-class DFA {
- void dump_node_to_dfa(void);
- State* add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats);
- void update_state_transitions(NodeMap &nodemap, list <State *> &work_queue, State *state, dfa_stats_t &stats);
- State *find_target_state(NodeMap &nodemap, list <State *> &work_queue,
- NodeSet *nodes, dfa_stats_t &stats);
-public:
- DFA(Node *root, dfaflags_t flags);
- virtual ~DFA();
- void remove_unreachable(dfaflags_t flags);
- bool same_mappings(State *s1, State *s2);
- size_t hash_trans(State *s);
- void minimize(dfaflags_t flags);
- void dump(ostream& os);
- void dump_dot_graph(ostream& os);
- void dump_uniq_perms(const char *s);
- map<uchar, uchar> equivalence_classes(dfaflags_t flags);
- void apply_equivalence_classes(map<uchar, uchar>& eq);
- Node *root;
- State *nonmatching, *start;
- Partition states;
-};
-
State* DFA::add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats)
{
State *state = new State(nodemap.size(), nodes);
@@ -334,29 +226,6 @@ DFA::~DFA()
delete *i;
}
-class MatchFlag : public AcceptNode {
-public:
-MatchFlag(uint32_t flag, uint32_t audit) : flag(flag), audit(audit) {}
- ostream& dump(ostream& os)
- {
- return os << '<' << flag << '>';
- }
-
- uint32_t flag;
- uint32_t audit;
- };
-
-class ExactMatchFlag : public MatchFlag {
-public:
- ExactMatchFlag(uint32_t flag, uint32_t audit) : MatchFlag(flag, audit) {}
-};
-
-class DenyMatchFlag : public MatchFlag {
-public:
- DenyMatchFlag(uint32_t flag, uint32_t quiet) : MatchFlag(flag, quiet) {}
-};
-
-
void DFA::dump_uniq_perms(const char *s)
{
set < pair<uint32_t, uint32_t> > uniq;
@@ -871,472 +740,6 @@ void DFA::apply_equivalence_classes(map<uchar, uchar>& eq)
}
}
-/**
- * Flip the children of all cat nodes. This causes strings to be matched
- * back-forth.
- */
-void flip_tree(Node *node)
-{
- for (depth_first_traversal i(node); i; i++) {
- if (CatNode *cat = dynamic_cast<CatNode *>(*i)) {
- swap(cat->child[0], cat->child[1]);
- }
- }
-}
-
-class TransitionTable {
- typedef vector<pair<const State *, size_t> > DefaultBase;
- typedef vector<pair<const State *, const State *> > NextCheck;
-public:
- TransitionTable(DFA& dfa, map<uchar, uchar>& eq, dfaflags_t flags);
- void dump(ostream& os);
- void flex_table(ostream& os, const char *name);
- void init_free_list(vector <pair<size_t, size_t> > &free_list, size_t prev, size_t start);
- bool fits_in(vector <pair<size_t, size_t> > &free_list,
- size_t base, Cases& cases);
- void insert_state(vector <pair<size_t, size_t> > &free_list,
- State *state, DFA& dfa);
-
-private:
- vector<uint32_t> accept;
- vector<uint32_t> accept2;
- DefaultBase default_base;
- NextCheck next_check;
- map<const State *, size_t> num;
- map<uchar, uchar>& eq;
- uchar max_eq;
- size_t first_free;
-};
-
-
-void TransitionTable::init_free_list(vector <pair<size_t, size_t> > &free_list,
- size_t prev, size_t start) {
- for (size_t i = start; i < free_list.size(); i++) {
- if (prev)
- free_list[prev].second = i;
- free_list[i].first = prev;
- prev = i;
- }
- free_list[free_list.size() -1].second = 0;
-}
-
-/**
- * new Construct the transition table.
- */
-TransitionTable::TransitionTable(DFA& dfa, map<uchar, uchar>& eq,
- dfaflags_t flags)
- : eq(eq)
-{
-
- if (flags & DFA_DUMP_TRANS_PROGRESS)
- fprintf(stderr, "Compressing trans table:\r");
-
-
- if (eq.empty())
- max_eq = 255;
- else {
- max_eq = 0;
- for(map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
- if (i->second > max_eq)
- max_eq = i->second;
- }
- }
-
- /* Do initial setup adding up all the transitions and sorting by
- * transition count.
- */
- size_t optimal = 2;
- multimap <size_t, State *> order;
- vector <pair<size_t, size_t> > free_list;
-
- for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end(); i++) {
- if (*i == dfa.start || *i == dfa.nonmatching)
- continue;
- optimal += (*i)->cases.cases.size();
- if (flags & DFA_CONTROL_TRANS_HIGH) {
- size_t range = 0;
- if ((*i)->cases.cases.size())
- range = (*i)->cases.cases.rbegin()->first - (*i)->cases.begin()->first;
- size_t ord = ((256 - (*i)->cases.cases.size()) << 8) |
- (256 - range);
- /* reverse sort by entry count, most entries first */
- order.insert(make_pair(ord, *i));
- }
- }
-
- /* Insert the dummy nonmatching transition by hand */
- next_check.push_back(make_pair(dfa.nonmatching, dfa.nonmatching));
- default_base.push_back(make_pair(dfa.nonmatching, 0));
- num.insert(make_pair(dfa.nonmatching, num.size()));
-
- accept.resize(dfa.states.size());
- accept2.resize(dfa.states.size());
- next_check.resize(optimal);
- free_list.resize(optimal);
-
- accept[0] = 0;
- accept2[0] = 0;
- first_free = 1;
- init_free_list(free_list, 0, 1);
-
- insert_state(free_list, dfa.start, dfa);
- accept[1] = 0;
- accept2[1] = 0;
- num.insert(make_pair(dfa.start, num.size()));
-
- int count = 2;
-
- if (!(flags & DFA_CONTROL_TRANS_HIGH)) {
- for (Partition::iterator i = dfa.states.begin(); i != dfa.states.end();
- i++) {
- if (*i != dfa.nonmatching && *i != dfa.start) {
- insert_state(free_list, *i, dfa);
- accept[num.size()] = (*i)->accept;
- accept2[num.size()] = (*i)->audit;
- num.insert(make_pair(*i, num.size()));
- }
- if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
- count++;
- if (count % 100 == 0)
- fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
- }
- }
- } else {
- for (multimap <size_t, State *>::iterator i = order.begin();
- i != order.end(); i++) {
- if (i->second != dfa.nonmatching && i->second != dfa.start) {
- insert_state(free_list, i->second, dfa);
- accept[num.size()] = i->second->accept;
- accept2[num.size()] = i->second->audit;
- num.insert(make_pair(i->second, num.size()));
- }
- if (flags & (DFA_DUMP_TRANS_PROGRESS)) {
- count++;
- if (count % 100 == 0)
- fprintf(stderr, "\033[2KCompressing trans table: insert state: %d/%ld\r", count, dfa.states.size());
- }
- }
- }
-
- if (flags & (DFA_DUMP_TRANS_STATS | DFA_DUMP_TRANS_PROGRESS)) {
- ssize_t size = 4 * next_check.size() + 6 * dfa.states.size();
- fprintf(stderr, "\033[2KCompressed trans table: states %ld, next/check %ld, optimal next/check %ld avg/state %.2f, compression %ld/%ld = %.2f %%\n", dfa.states.size(), next_check.size(), optimal, (float)next_check.size()/(float)dfa.states.size(), size, 512 * dfa.states.size(), 100.0 - ((float) size * 100.0 / (float)(512 * dfa.states.size())));
- }
-}
-
-
-/**
- * Does <cases> fit into position <base> of the transition table?
- */
-bool TransitionTable::fits_in(vector <pair<size_t, size_t> > &free_list __attribute__((unused)),
- size_t pos, Cases& cases)
-{
- size_t c, base = pos - cases.begin()->first;
- for (Cases::iterator i = cases.begin(); i != cases.end(); i++) {
- c = base + i->first;
- /* if it overflows the next_check array it fits in as we will
- * resize */
- if (c >= next_check.size())
- return true;
- if (next_check[c].second)
- return false;
- }
-
- return true;
-}
-
-/**
- * Insert <state> of <dfa> into the transition table.
- */
-void TransitionTable::insert_state(vector <pair<size_t, size_t> > &free_list,
- State *from, DFA& dfa)
-{
- State *default_state = dfa.nonmatching;
- size_t base = 0;
- int resize;
-
- Cases& cases = from->cases;
- size_t c = cases.begin()->first;
- size_t prev = 0;
- size_t x = first_free;
-
- if (cases.otherwise)
- default_state = cases.otherwise;
- if (cases.cases.empty())
- goto do_insert;
-
-repeat:
- resize = 0;
- /* get the first free entry that won't underflow */
- while (x && (x < c)) {
- prev = x;
- x = free_list[x].second;
- }
-
- /* try inserting until we succeed. */
- while (x && !fits_in(free_list, x, cases)) {
- prev = x;
- x = free_list[x].second;
- }
- if (!x) {
- resize = 256 - cases.begin()->first;
- x = free_list.size();
- /* set prev to last free */
- } else if (x + 255 - cases.begin()->first >= next_check.size()) {
- resize = (255 - cases.begin()->first - (next_check.size() - 1 - x));
- for (size_t y = x; y; y = free_list[y].second)
- prev = y;
- }
- if (resize) {
- /* expand next_check and free_list */
- size_t old_size = free_list.size();
- next_check.resize(next_check.size() + resize);
- free_list.resize(free_list.size() + resize);
- init_free_list(free_list, prev, old_size);
- if (!first_free)
- first_free = old_size;;
- if (x == old_size)
- goto repeat;
- }
-
- base = x - c;
- for (Cases::iterator j = cases.begin(); j != cases.end(); j++) {
- next_check[base + j->first] = make_pair(j->second, from);
- size_t prev = free_list[base + j->first].first;
- size_t next = free_list[base + j->first].second;
- if (prev)
- free_list[prev].second = next;
- if (next)
- free_list[next].first = prev;
- if (base + j->first == first_free)
- first_free = next;
- }
-
-do_insert:
- default_base.push_back(make_pair(default_state, base));
-}
-
-/**
- * Text-dump the transition table (for debugging).
- */
-void TransitionTable::dump(ostream& os)
-{
- map<size_t, const State *> st;
- for (map<const State *, size_t>::iterator i = num.begin();
- i != num.end();
- i++) {
- st.insert(make_pair(i->second, i->first));
- }
-
- os << "size=" << default_base.size() << " (accept, default, base): {state} -> {default state}" << endl;
- for (size_t i = 0; i < default_base.size(); i++) {
- os << i << ": ";
- os << "(" << accept[i] << ", "
- << num[default_base[i].first] << ", "
- << default_base[i].second << ")";
- if (st[i])
- os << " " << *st[i];
- if (default_base[i].first)
- os << " -> " << *default_base[i].first;
- os << endl;
- }
-
- os << "size=" << next_check.size() << " (next, check): {check state} -> {next state} : offset from base" << endl;
- for (size_t i = 0; i < next_check.size(); i++) {
- if (!next_check[i].second)
- continue;
-
- os << i << ": ";
- if (next_check[i].second) {
- os << "(" << num[next_check[i].first] << ", "
- << num[next_check[i].second] << ")" << " "
- << *next_check[i].second << " -> "
- << *next_check[i].first << ": ";
-
- size_t offs = i - default_base[num[next_check[i].second]].second;
- if (eq.size())
- os << offs;
- else
- os << (uchar)offs;
- }
- os << endl;
- }
-}
-
-#if 0
-template<class Iter>
-class FirstIterator {
-public:
- FirstIterator(Iter pos) : pos(pos) { }
- typename Iter::value_type::first_type operator*() { return pos->first; }
- bool operator!=(FirstIterator<Iter>& i) { return pos != i.pos; }
- void operator++() { ++pos; }
- ssize_t operator-(FirstIterator<Iter> i) { return pos - i.pos; }
-private:
- Iter pos;
-};
-
-template<class Iter>
-FirstIterator<Iter> first_iterator(Iter iter)
-{
- return FirstIterator<Iter>(iter);
-}
-
-template<class Iter>
-class SecondIterator {
-public:
- SecondIterator(Iter pos) : pos(pos) { }
- typename Iter::value_type::second_type operator*() { return pos->second; }
- bool operator!=(SecondIterator<Iter>& i) { return pos != i.pos; }
- void operator++() { ++pos; }
- ssize_t operator-(SecondIterator<Iter> i) { return pos - i.pos; }
-private:
- Iter pos;
-};
-
-template<class Iter>
-SecondIterator<Iter> second_iterator(Iter iter)
-{
- return SecondIterator<Iter>(iter);
-}
-#endif
-
-/**
- * Create a flex-style binary dump of the DFA tables. The table format
- * was partly reverse engineered from the flex sources and from
- * examining the tables that flex creates with its --tables-file option.
- * (Only the -Cf and -Ce formats are currently supported.)
- */
-
-#include "flex-tables.h"
-#define YYTH_REGEX_MAGIC 0x1B5E783D
-
-static inline size_t pad64(size_t i)
-{
- return (i + (size_t)7) & ~(size_t)7;
-}
-
-string fill64(size_t i)
-{
- const char zeroes[8] = { };
- string fill(zeroes, (i & 7) ? 8 - (i & 7) : 0);
- return fill;
-}
-
-template<class Iter>
-size_t flex_table_size(Iter pos, Iter end)
-{
- return pad64(sizeof(struct table_header) + sizeof(*pos) * (end - pos));
-}
-
-template<class Iter>
-void write_flex_table(ostream& os, int id, Iter pos, Iter end)
-{
- struct table_header td = { 0, 0, 0, 0 };
- size_t size = end - pos;
-
- td.td_id = htons(id);
- td.td_flags = htons(sizeof(*pos));
- td.td_lolen = htonl(size);
- os.write((char *)&td, sizeof(td));
-
- for (; pos != end; ++pos) {
- switch(sizeof(*pos)) {
- case 4:
- os.put((char)(*pos >> 24));
- os.put((char)(*pos >> 16));
- case 2:
- os.put((char)(*pos >> 8));
- case 1:
- os.put((char)*pos);
- }
- }
-
- os << fill64(sizeof(td) + sizeof(*pos) * size);
-}
-
-void TransitionTable::flex_table(ostream& os, const char *name)
-{
- const char th_version[] = "notflex";
- struct table_set_header th = { 0, 0, 0, 0 };
-
- /**
- * Change the following two data types to adjust the maximum flex
- * table size.
- */
- typedef uint16_t state_t;
- typedef uint32_t trans_t;
-
- if (default_base.size() >= (state_t)-1) {
- cerr << "Too many states (" << default_base.size() << ") for "
- "type state_t" << endl;
- exit(1);
- }
- if (next_check.size() >= (trans_t)-1) {
- cerr << "Too many transitions (" << next_check.size() << ") for "
- "type trans_t" << endl;
- exit(1);
- }
-
- /**
- * Create copies of the data structures so that we can dump the tables
- * using the generic write_flex_table() routine.
- */
- vector<uint8_t> equiv_vec;
- if (eq.size()) {
- equiv_vec.resize(256);
- for (map<uchar, uchar>::iterator i = eq.begin(); i != eq.end(); i++) {
- equiv_vec[i->first] = i->second;
- }
- }
-
- vector<state_t> default_vec;
- vector<trans_t> base_vec;
- for (DefaultBase::iterator i = default_base.begin();
- i != default_base.end();
- i++) {
- default_vec.push_back(num[i->first]);
- base_vec.push_back(i->second);
- }
-
- vector<state_t> next_vec;
- vector<state_t> check_vec;
- for (NextCheck::iterator i = next_check.begin();
- i != next_check.end();
- i++) {
- next_vec.push_back(num[i->first]);
- check_vec.push_back(num[i->second]);
- }
-
- /* Write the actual flex parser table. */
-
- size_t hsize = pad64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
- th.th_magic = htonl(YYTH_REGEX_MAGIC);
- th.th_hsize = htonl(hsize);
- th.th_ssize = htonl(hsize +
- flex_table_size(accept.begin(), accept.end()) +
- flex_table_size(accept2.begin(), accept2.end()) +
- (eq.size() ?
- flex_table_size(equiv_vec.begin(), equiv_vec.end()) : 0) +
- flex_table_size(base_vec.begin(), base_vec.end()) +
- flex_table_size(default_vec.begin(), default_vec.end()) +
- flex_table_size(next_vec.begin(), next_vec.end()) +
- flex_table_size(check_vec.begin(), check_vec.end()));
- os.write((char *)&th, sizeof(th));
- os << th_version << (char)0 << name << (char)0;
- os << fill64(sizeof(th) + sizeof(th_version) + strlen(name) + 1);
-
-
- write_flex_table(os, YYTD_ID_ACCEPT, accept.begin(), accept.end());
- write_flex_table(os, YYTD_ID_ACCEPT2, accept2.begin(), accept2.end());
- if (eq.size())
- write_flex_table(os, YYTD_ID_EC, equiv_vec.begin(), equiv_vec.end());
- write_flex_table(os, YYTD_ID_BASE, base_vec.begin(), base_vec.end());
- write_flex_table(os, YYTD_ID_DEF, default_vec.begin(), default_vec.end());
- write_flex_table(os, YYTD_ID_NXT, next_vec.begin(), next_vec.end());
- write_flex_table(os, YYTD_ID_CHK, check_vec.begin(), check_vec.end());
-}
-
#if 0
typedef set<ImportantNode *> AcceptNodes;
map<ImportantNode *, AcceptNodes> dominance(DFA& dfa)
@@ -1368,21 +771,6 @@ map<ImportantNode *, AcceptNodes> dominance(DFA& dfa)
}
#endif
-void dump_regexp_rec(ostream& os, Node *tree)
-{
- if (tree->child[0])
- dump_regexp_rec(os, tree->child[0]);
- os << *tree;
- if (tree->child[1])
- dump_regexp_rec(os, tree->child[1]);
-}
-
-void dump_regexp(ostream& os, Node *tree)
-{
- dump_regexp_rec(os, tree);
- os << endl;
-}
-
static inline int diff_qualifiers(uint32_t perm1, uint32_t perm2)
{
diff --git a/parser/libapparmor_re/hfa.h b/parser/libapparmor_re/hfa.h
new file mode 100644
index 0000000..a017a45
--- /dev/null
+++ b/parser/libapparmor_re/hfa.h
@@ -0,0 +1,139 @@
+/*
+ * (C) 2006, 2007 Andreas Gruenbacher <agruen at suse.de>
+ * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
+ * Copyright 2009-2010 Canonical Ltd.
+ *
+ * The libapparmor library is licensed under the terms of the GNU
+ * Lesser General Public License, version 2.1. Please see the file
+ * COPYING.LGPL.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ * Base of implementation based on the Lexical Analysis chapter of:
+ * Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman:
+ * Compilers: Principles, Techniques, and Tools (The "Dragon Book"),
+ * Addison-Wesley, 1986.
+ */
+#ifndef __LIBAA_RE_HFA_H
+#define __LIBAA_RE_HFA_H
+
+#include <list>
+#include <map>
+#include <vector>
+
+#include <stdint.h>
+
+#include "expr-tree.h"
+
+class State;
+/**
+ * State cases are identical to NodesCases except they map to State *
+ * instead of NodeSet.
+ * Out-edges from a state to another: we store the follow State
+ * for each input character that is not a default match in cases and
+ * default matches in otherwise as well as in all matching explicit cases
+ * This avoids enumerating all the explicit tranitions for default matches.
+ */
+typedef struct Cases {
+ typedef map<uchar, State *>::iterator iterator;
+ iterator begin() { return cases.begin(); }
+ iterator end() { return cases.end(); }
+
+ Cases() : otherwise(0) { }
+ map<uchar, State *> cases;
+ State *otherwise;
+} Cases;
+
+typedef list<State *> Partition;
+
+
+uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
+
+/*
+ * State - DFA individual state information
+ * label: a unique label to identify the state used for pretty printing
+ * the non-matching state is setup to have label == 0 and
+ * the start state is setup to have label == 1
+ * audit: the audit permission mask for the state
+ * accept: the accept permissions for the state
+ * cases: set of transitions from this state
+ * parition: Is a temporary work variable used during dfa minimization.
+ * it can be replaced with a map, but that is slower and uses more
+ * memory.
+ * nodes: Is a temporary work variable used during dfa creation. It can
+ * be replaced by using the nodemap, but that is slower
+ */
+class State {
+public:
+ State() : label (0), audit(0), accept(0), cases(), nodes(NULL) { };
+ State(int l): label (l), audit(0), accept(0), cases(), nodes(NULL) { };
+ State(int l, NodeSet *n) throw (int):
+ label(l), audit(0), accept(0), cases(), nodes(n)
+ {
+ int error;
+
+ /* Compute permissions associated with the State. */
+ accept = accept_perms(nodes, &audit, &error);
+ if (error) {
+ //cerr << "Failing on accept perms " << error << "\n";
+ throw error;
+ }
+ };
+
+ int label;
+ uint32_t audit, accept;
+ Cases cases;
+ union {
+ Partition *partition;
+ NodeSet *nodes;
+ };
+};
+
+ostream& operator<<(ostream& os, const State& state);
+
+typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than > NodeMap;
+/* Transitions in the DFA. */
+
+/* dfa_stats - structure to group various stats about dfa creation
+ * duplicates - how many duplicate NodeSets where encountered and discarded
+ * proto_max - maximum length of a NodeSet encountered during dfa construction
+ * proto_sum - sum of NodeSet length during dfa construction. Used to find
+ * average length.
+ */
+typedef struct dfa_stats {
+ unsigned int duplicates, proto_max, proto_sum;
+} dfa_stats_t;
+
+class DFA {
+ void dump_node_to_dfa(void);
+ State* add_new_state(NodeMap &nodemap, pair <unsigned long, NodeSet *> index, NodeSet *nodes, dfa_stats_t &stats);
+ void update_state_transitions(NodeMap &nodemap, list <State *> &work_queue, State *state, dfa_stats_t &stats);
+ State *find_target_state(NodeMap &nodemap, list <State *> &work_queue,
+ NodeSet *nodes, dfa_stats_t &stats);
+public:
+ DFA(Node *root, dfaflags_t flags);
+ virtual ~DFA();
+ void remove_unreachable(dfaflags_t flags);
+ bool same_mappings(State *s1, State *s2);
+ size_t hash_trans(State *s);
+ void minimize(dfaflags_t flags);
+ void dump(ostream& os);
+ void dump_dot_graph(ostream& os);
+ void dump_uniq_perms(const char *s);
+ map<uchar, uchar> equivalence_classes(dfaflags_t flags);
+ void apply_equivalence_classes(map<uchar, uchar>& eq);
+ Node *root;
+ State *nonmatching, *start;
+ Partition states;
+};
+
+void dump_equivalence_classes(ostream& os, map<uchar, uchar>& eq);
+
+#endif /* __LIBAA_RE_HFA_H */
--
1.7.1
More information about the AppArmor
mailing list