Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial
[linux-3.10.git] / security / apparmor / match.c
1 /*
2  * AppArmor security module
3  *
4  * This file contains AppArmor dfa based regular expression matching engine
5  *
6  * Copyright (C) 1998-2008 Novell/SUSE
7  * Copyright 2009-2010 Canonical Ltd.
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License as
11  * published by the Free Software Foundation, version 2 of the
12  * License.
13  */
14
15 #include <linux/errno.h>
16 #include <linux/kernel.h>
17 #include <linux/mm.h>
18 #include <linux/slab.h>
19 #include <linux/vmalloc.h>
20 #include <linux/err.h>
21 #include <linux/kref.h>
22
23 #include "include/apparmor.h"
24 #include "include/match.h"
25
26 /**
27  * unpack_table - unpack a dfa table (one of accept, default, base, next check)
28  * @blob: data to unpack (NOT NULL)
29  * @bsize: size of blob
30  *
31  * Returns: pointer to table else NULL on failure
32  *
33  * NOTE: must be freed by kvfree (not kmalloc)
34  */
35 static struct table_header *unpack_table(char *blob, size_t bsize)
36 {
37         struct table_header *table = NULL;
38         struct table_header th;
39         size_t tsize;
40
41         if (bsize < sizeof(struct table_header))
42                 goto out;
43
44         /* loaded td_id's start at 1, subtract 1 now to avoid doing
45          * it every time we use td_id as an index
46          */
47         th.td_id = be16_to_cpu(*(u16 *) (blob)) - 1;
48         th.td_flags = be16_to_cpu(*(u16 *) (blob + 2));
49         th.td_lolen = be32_to_cpu(*(u32 *) (blob + 8));
50         blob += sizeof(struct table_header);
51
52         if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
53               th.td_flags == YYTD_DATA8))
54                 goto out;
55
56         tsize = table_size(th.td_lolen, th.td_flags);
57         if (bsize < tsize)
58                 goto out;
59
60         table = kvmalloc(tsize);
61         if (table) {
62                 *table = th;
63                 if (th.td_flags == YYTD_DATA8)
64                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
65                                      u8, byte_to_byte);
66                 else if (th.td_flags == YYTD_DATA16)
67                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
68                                      u16, be16_to_cpu);
69                 else if (th.td_flags == YYTD_DATA32)
70                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
71                                      u32, be32_to_cpu);
72                 else
73                         goto fail;
74         }
75
76 out:
77         /* if table was vmalloced make sure the page tables are synced
78          * before it is used, as it goes live to all cpus.
79          */
80         if (is_vmalloc_addr(table))
81                 vm_unmap_aliases();
82         return table;
83 fail:
84         kvfree(table);
85         return NULL;
86 }
87
88 /**
89  * verify_dfa - verify that transitions and states in the tables are in bounds.
90  * @dfa: dfa to test  (NOT NULL)
91  * @flags: flags controlling what type of accept table are acceptable
92  *
93  * Assumes dfa has gone through the first pass verification done by unpacking
94  * NOTE: this does not valid accept table values
95  *
96  * Returns: %0 else error code on failure to verify
97  */
98 static int verify_dfa(struct aa_dfa *dfa, int flags)
99 {
100         size_t i, state_count, trans_count;
101         int error = -EPROTO;
102
103         /* check that required tables exist */
104         if (!(dfa->tables[YYTD_ID_DEF] &&
105               dfa->tables[YYTD_ID_BASE] &&
106               dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK]))
107                 goto out;
108
109         /* accept.size == default.size == base.size */
110         state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
111         if (ACCEPT1_FLAGS(flags)) {
112                 if (!dfa->tables[YYTD_ID_ACCEPT])
113                         goto out;
114                 if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen)
115                         goto out;
116         }
117         if (ACCEPT2_FLAGS(flags)) {
118                 if (!dfa->tables[YYTD_ID_ACCEPT2])
119                         goto out;
120                 if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen)
121                         goto out;
122         }
123         if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen)
124                 goto out;
125
126         /* next.size == chk.size */
127         trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
128         if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen)
129                 goto out;
130
131         /* if equivalence classes then its table size must be 256 */
132         if (dfa->tables[YYTD_ID_EC] &&
133             dfa->tables[YYTD_ID_EC]->td_lolen != 256)
134                 goto out;
135
136         if (flags & DFA_FLAG_VERIFY_STATES) {
137                 for (i = 0; i < state_count; i++) {
138                         if (DEFAULT_TABLE(dfa)[i] >= state_count)
139                                 goto out;
140                         /* TODO: do check that DEF state recursion terminates */
141                         if (BASE_TABLE(dfa)[i] + 255 >= trans_count) {
142                                 printk(KERN_ERR "AppArmor DFA next/check upper "
143                                        "bounds error\n");
144                                 goto out;
145                         }
146                 }
147
148                 for (i = 0; i < trans_count; i++) {
149                         if (NEXT_TABLE(dfa)[i] >= state_count)
150                                 goto out;
151                         if (CHECK_TABLE(dfa)[i] >= state_count)
152                                 goto out;
153                 }
154         }
155
156         error = 0;
157 out:
158         return error;
159 }
160
161 /**
162  * dfa_free - free a dfa allocated by aa_dfa_unpack
163  * @dfa: the dfa to free  (MAYBE NULL)
164  *
165  * Requires: reference count to dfa == 0
166  */
167 static void dfa_free(struct aa_dfa *dfa)
168 {
169         if (dfa) {
170                 int i;
171
172                 for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
173                         kvfree(dfa->tables[i]);
174                         dfa->tables[i] = NULL;
175                 }
176                 kfree(dfa);
177         }
178 }
179
180 /**
181  * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
182  * @kr: kref callback for freeing of a dfa  (NOT NULL)
183  */
184 void aa_dfa_free_kref(struct kref *kref)
185 {
186         struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
187         dfa_free(dfa);
188 }
189
190 /**
191  * aa_dfa_unpack - unpack the binary tables of a serialized dfa
192  * @blob: aligned serialized stream of data to unpack  (NOT NULL)
193  * @size: size of data to unpack
194  * @flags: flags controlling what type of accept tables are acceptable
195  *
196  * Unpack a dfa that has been serialized.  To find information on the dfa
197  * format look in Documentation/apparmor.txt
198  * Assumes the dfa @blob stream has been aligned on a 8 byte boundry
199  *
200  * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
201  */
202 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
203 {
204         int hsize;
205         int error = -ENOMEM;
206         char *data = blob;
207         struct table_header *table = NULL;
208         struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
209         if (!dfa)
210                 goto fail;
211
212         kref_init(&dfa->count);
213
214         error = -EPROTO;
215
216         /* get dfa table set header */
217         if (size < sizeof(struct table_set_header))
218                 goto fail;
219
220         if (ntohl(*(u32 *) data) != YYTH_MAGIC)
221                 goto fail;
222
223         hsize = ntohl(*(u32 *) (data + 4));
224         if (size < hsize)
225                 goto fail;
226
227         dfa->flags = ntohs(*(u16 *) (data + 12));
228         data += hsize;
229         size -= hsize;
230
231         while (size > 0) {
232                 table = unpack_table(data, size);
233                 if (!table)
234                         goto fail;
235
236                 switch (table->td_id) {
237                 case YYTD_ID_ACCEPT:
238                         if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
239                                 goto fail;
240                         break;
241                 case YYTD_ID_ACCEPT2:
242                         if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
243                                 goto fail;
244                         break;
245                 case YYTD_ID_BASE:
246                         if (table->td_flags != YYTD_DATA32)
247                                 goto fail;
248                         break;
249                 case YYTD_ID_DEF:
250                 case YYTD_ID_NXT:
251                 case YYTD_ID_CHK:
252                         if (table->td_flags != YYTD_DATA16)
253                                 goto fail;
254                         break;
255                 case YYTD_ID_EC:
256                         if (table->td_flags != YYTD_DATA8)
257                                 goto fail;
258                         break;
259                 default:
260                         goto fail;
261                 }
262                 /* check for duplicate table entry */
263                 if (dfa->tables[table->td_id])
264                         goto fail;
265                 dfa->tables[table->td_id] = table;
266                 data += table_size(table->td_lolen, table->td_flags);
267                 size -= table_size(table->td_lolen, table->td_flags);
268                 table = NULL;
269         }
270
271         error = verify_dfa(dfa, flags);
272         if (error)
273                 goto fail;
274
275         return dfa;
276
277 fail:
278         kvfree(table);
279         dfa_free(dfa);
280         return ERR_PTR(error);
281 }
282
283 /**
284  * aa_dfa_match_len - traverse @dfa to find state @str stops at
285  * @dfa: the dfa to match @str against  (NOT NULL)
286  * @start: the state of the dfa to start matching in
287  * @str: the string of bytes to match against the dfa  (NOT NULL)
288  * @len: length of the string of bytes to match
289  *
290  * aa_dfa_match_len will match @str against the dfa and return the state it
291  * finished matching in. The final state can be used to look up the accepting
292  * label, or as the start state of a continuing match.
293  *
294  * This function will happily match again the 0 byte and only finishes
295  * when @len input is consumed.
296  *
297  * Returns: final state reached after input is consumed
298  */
299 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
300                               const char *str, int len)
301 {
302         u16 *def = DEFAULT_TABLE(dfa);
303         u32 *base = BASE_TABLE(dfa);
304         u16 *next = NEXT_TABLE(dfa);
305         u16 *check = CHECK_TABLE(dfa);
306         unsigned int state = start, pos;
307
308         if (state == 0)
309                 return 0;
310
311         /* current state is <state>, matching character *str */
312         if (dfa->tables[YYTD_ID_EC]) {
313                 /* Equivalence class table defined */
314                 u8 *equiv = EQUIV_TABLE(dfa);
315                 /* default is direct to next state */
316                 for (; len; len--) {
317                         pos = base[state] + equiv[(u8) *str++];
318                         if (check[pos] == state)
319                                 state = next[pos];
320                         else
321                                 state = def[state];
322                 }
323         } else {
324                 /* default is direct to next state */
325                 for (; len; len--) {
326                         pos = base[state] + (u8) *str++;
327                         if (check[pos] == state)
328                                 state = next[pos];
329                         else
330                                 state = def[state];
331                 }
332         }
333
334         return state;
335 }
336
337 /**
338  * aa_dfa_next_state - traverse @dfa to find state @str stops at
339  * @dfa: the dfa to match @str against  (NOT NULL)
340  * @start: the state of the dfa to start matching in
341  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
342  *
343  * aa_dfa_next_state will match @str against the dfa and return the state it
344  * finished matching in. The final state can be used to look up the accepting
345  * label, or as the start state of a continuing match.
346  *
347  * Returns: final state reached after input is consumed
348  */
349 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
350                           const char *str)
351 {
352         return aa_dfa_match_len(dfa, start, str, strlen(str));
353 }