← Back to branch summary

~ubuntu-branches/ubuntu/wily/apparmor/wily

« back to all changes in this revision

Viewing changes to parser/libapparmor_re/hfa.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2011-08-10 18:12:34 UTC
  • mto: This revision was merged to the branch mainline in revision 9.
  • Revision ID: james.westby@ubuntu.com-20110810181234-b6obckg60cp99crg
Tags: upstream-2.7.0~beta1+bzr1774
Import upstream version 2.7.0~beta1+bzr1774

Show diffs side-by-side

added added

removed removed

Lines of Context:
parser/libapparmor_re/hfa.h
 
1
/*
 
2
 * (C) 2006, 2007 Andreas Gruenbacher <agruen@suse.de>
 
3
 * Copyright (c) 2003-2008 Novell, Inc. (All rights reserved)
 
4
 * Copyright 2009-2010 Canonical Ltd.
 
5
 *
 
6
 * The libapparmor library is licensed under the terms of the GNU
 
7
 * Lesser General Public License, version 2.1. Please see the file
 
8
 * COPYING.LGPL.
 
9
 *
 
10
 * This library is distributed in the hope that it will be useful,
 
11
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
 * GNU Lesser General Public License for more details.
 
14
 *
 
15
 * You should have received a copy of the GNU Lesser General Public License
 
16
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
17
 *
 
18
 *
 
19
  * Base of implementation based on the Lexical Analysis chapter of:
 
20
 *   Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman:
 
21
 *   Compilers: Principles, Techniques, and Tools (The "Dragon Book"),
 
22
 *   Addison-Wesley, 1986.
 
23
 */
 
24
#ifndef __LIBAA_RE_HFA_H
 
25
#define __LIBAA_RE_HFA_H
 
26
 
 
27
#include <list>
 
28
#include <map>
 
29
#include <vector>
 
30
 
 
31
#include <stdint.h>
 
32
 
 
33
#include "expr-tree.h"
 
34
 
 
35
class State;
 
36
/**
 
37
 * State cases are identical to NodesCases except they map to State *
 
38
 * instead of NodeSet.
 
39
 * Out-edges from a state to another: we store the follow State
 
40
 * for each input character that is not a default match in  cases and
 
41
 * default matches in otherwise as well as in all matching explicit cases
 
42
 * This avoids enumerating all the explicit tranitions for default matches.
 
43
 */
 
44
typedef struct Cases {
 
45
        typedef map<uchar, State *>::iterator iterator;
 
46
        iterator begin() { return cases.begin(); }
 
47
        iterator end() { return cases.end(); }
 
48
 
 
49
        Cases(): otherwise(0) { }
 
50
 
 
51
        map<uchar, State *> cases;
 
52
        State *otherwise;
 
53
} Cases;
 
54
 
 
55
typedef list<State *> Partition;
 
56
 
 
57
uint32_t accept_perms(NodeSet *state, uint32_t *audit_ctl, int *error);
 
58
 
 
59
/*
 
60
 * State - DFA individual state information
 
61
 * label: a unique label to identify the state used for pretty printing
 
62
 *        the non-matching state is setup to have label == 0 and
 
63
 *        the start state is setup to have label == 1
 
64
 * audit: the audit permission mask for the state
 
65
 * accept: the accept permissions for the state
 
66
 * cases: set of transitions from this state
 
67
 * parition: Is a temporary work variable used during dfa minimization.
 
68
 *           it can be replaced with a map, but that is slower and uses more
 
69
 *           memory.
 
70
 * nodes: Is a temporary work variable used during dfa creation.  It can
 
71
 *        be replaced by using the nodemap, but that is slower
 
72
 */
 
73
class State {
 
74
public:
 
75
        State(): label(0), audit(0), accept(0), cases(), nodes(NULL) { };
 
76
        State(int l): label(l), audit(0), accept(0), cases(), nodes(NULL) { };
 
77
        State(int l, NodeSet * n) throw(int):
 
78
                label(l), audit(0), accept(0), cases(), nodes(n)
 
79
        {
 
80
                int error;
 
81
 
 
82
                /* Compute permissions associated with the State. */
 
83
                accept = accept_perms(nodes, &audit, &error);
 
84
                if (error) {
 
85
                        //cerr << "Failing on accept perms " << error << "\n";
 
86
                        throw error;
 
87
                }
 
88
        };
 
89
 
 
90
        int label;
 
91
        uint32_t audit, accept;
 
92
        Cases cases;
 
93
        union {
 
94
                Partition *partition;
 
95
                NodeSet *nodes;
 
96
        };
 
97
};
 
98
 
 
99
ostream &operator<<(ostream &os, const State &state);
 
100
 
 
101
typedef map<pair<unsigned long, NodeSet *>, State *, deref_less_than> NodeMap;
 
102
/* Transitions in the DFA. */
 
103
 
 
104
/* dfa_stats - structure to group various stats about dfa creation
 
105
 * duplicates - how many duplicate NodeSets where encountered and discarded
 
106
 * proto_max - maximum length of a NodeSet encountered during dfa construction
 
107
 * proto_sum - sum of NodeSet length during dfa construction.  Used to find
 
108
 *             average length.
 
109
 */
 
110
typedef struct dfa_stats {
 
111
        unsigned int duplicates, proto_max, proto_sum;
 
112
} dfa_stats_t;
 
113
 
 
114
class DFA {
 
115
        void dump_node_to_dfa(void);
 
116
        State *add_new_state(NodeMap &nodemap,
 
117
                             pair<unsigned long, NodeSet *> index,
 
118
                             NodeSet *nodes, dfa_stats_t &stats);
 
119
        void update_state_transitions(NodeMap &nodemap,
 
120
                                      list<State *> &work_queue,
 
121
                                      State *state, dfa_stats_t &stats);
 
122
        State *find_target_state(NodeMap &nodemap, list<State *> &work_queue,
 
123
                                 NodeSet *nodes, dfa_stats_t &stats);
 
124
public:
 
125
        DFA(Node *root, dfaflags_t flags);
 
126
        virtual ~DFA();
 
127
        void remove_unreachable(dfaflags_t flags);
 
128
        bool same_mappings(State *s1, State *s2);
 
129
        size_t hash_trans(State *s);
 
130
        void minimize(dfaflags_t flags);
 
131
        void dump(ostream &os);
 
132
        void dump_dot_graph(ostream &os);
 
133
        void dump_uniq_perms(const char *s);
 
134
        map<uchar, uchar> equivalence_classes(dfaflags_t flags);
 
135
        void apply_equivalence_classes(map<uchar, uchar> &eq);
 
136
        Node *root;
 
137
        State *nonmatching, *start;
 
138
        Partition states;
 
139
};
 
140
 
 
141
void dump_equivalence_classes(ostream &os, map<uchar, uchar> &eq);
 
142
 
 
143
#endif /* __LIBAA_RE_HFA_H */