Branch data Line data Source code
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-2012 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 : : #define base_idx(X) ((X) & 0xffffff)
27 : :
28 : : /**
29 : : * unpack_table - unpack a dfa table (one of accept, default, base, next check)
30 : : * @blob: data to unpack (NOT NULL)
31 : : * @bsize: size of blob
32 : : *
33 : : * Returns: pointer to table else NULL on failure
34 : : *
35 : : * NOTE: must be freed by kvfree (not kfree)
36 : : */
37 : 0 : static struct table_header *unpack_table(char *blob, size_t bsize)
38 : : {
39 : : struct table_header *table = NULL;
40 : : struct table_header th;
41 : : size_t tsize;
42 : :
43 [ # # ]: 0 : if (bsize < sizeof(struct table_header))
44 : : goto out;
45 : :
46 : : /* loaded td_id's start at 1, subtract 1 now to avoid doing
47 : : * it every time we use td_id as an index
48 : : */
49 [ # # ]: 0 : th.td_id = be16_to_cpu(*(u16 *) (blob)) - 1;
50 [ # # ]: 0 : th.td_flags = be16_to_cpu(*(u16 *) (blob + 2));
51 [ # # ]: 0 : th.td_lolen = be32_to_cpu(*(u32 *) (blob + 8));
52 : 0 : blob += sizeof(struct table_header);
53 : :
54 [ # # ][ # # ]: 0 : if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
55 : : th.td_flags == YYTD_DATA8))
56 : : goto out;
57 : :
58 : 0 : tsize = table_size(th.td_lolen, th.td_flags);
59 [ # # ]: 0 : if (bsize < tsize)
60 : : goto out;
61 : :
62 : : table = kvzalloc(tsize);
63 [ # # ]: 0 : if (table) {
64 : 0 : *table = th;
65 [ # # ]: 0 : if (th.td_flags == YYTD_DATA8)
66 [ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
67 : : u8, byte_to_byte);
68 [ # # ]: 0 : else if (th.td_flags == YYTD_DATA16)
69 [ # # ][ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
70 : : u16, be16_to_cpu);
71 [ # # ]: 0 : else if (th.td_flags == YYTD_DATA32)
72 [ # # ][ # # ]: 0 : UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
73 : : u32, be32_to_cpu);
74 : : else
75 : : goto fail;
76 : : }
77 : :
78 : : out:
79 : : /* if table was vmalloced make sure the page tables are synced
80 : : * before it is used, as it goes live to all cpus.
81 : : */
82 [ # # ]: 0 : if (is_vmalloc_addr(table))
83 : 0 : vm_unmap_aliases();
84 : 0 : return table;
85 : : fail:
86 : 0 : kvfree(table);
87 : 0 : return NULL;
88 : : }
89 : :
90 : : /**
91 : : * verify_dfa - verify that transitions and states in the tables are in bounds.
92 : : * @dfa: dfa to test (NOT NULL)
93 : : * @flags: flags controlling what type of accept table are acceptable
94 : : *
95 : : * Assumes dfa has gone through the first pass verification done by unpacking
96 : : * NOTE: this does not valid accept table values
97 : : *
98 : : * Returns: %0 else error code on failure to verify
99 : : */
100 : 0 : static int verify_dfa(struct aa_dfa *dfa, int flags)
101 : : {
102 : : size_t i, state_count, trans_count;
103 : : int error = -EPROTO;
104 : :
105 : : /* check that required tables exist */
106 [ # # ][ # # ]: 0 : if (!(dfa->tables[YYTD_ID_DEF] &&
[ # # ]
107 [ # # ]: 0 : dfa->tables[YYTD_ID_BASE] &&
108 : 0 : dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK]))
109 : : goto out;
110 : :
111 : : /* accept.size == default.size == base.size */
112 : 0 : state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
113 [ # # ]: 0 : if (ACCEPT1_FLAGS(flags)) {
114 [ # # ]: 0 : if (!dfa->tables[YYTD_ID_ACCEPT])
115 : : goto out;
116 [ # # ]: 0 : if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen)
117 : : goto out;
118 : : }
119 [ # # ]: 0 : if (ACCEPT2_FLAGS(flags)) {
120 [ # # ]: 0 : if (!dfa->tables[YYTD_ID_ACCEPT2])
121 : : goto out;
122 [ # # ]: 0 : if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen)
123 : : goto out;
124 : : }
125 [ # # ]: 0 : if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen)
126 : : goto out;
127 : :
128 : : /* next.size == chk.size */
129 : 0 : trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
130 [ # # ]: 0 : if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen)
131 : : goto out;
132 : :
133 : : /* if equivalence classes then its table size must be 256 */
134 [ # # ][ # # ]: 0 : if (dfa->tables[YYTD_ID_EC] &&
135 : 0 : dfa->tables[YYTD_ID_EC]->td_lolen != 256)
136 : : goto out;
137 : :
138 [ # # ]: 0 : if (flags & DFA_FLAG_VERIFY_STATES) {
139 [ # # ]: 0 : for (i = 0; i < state_count; i++) {
140 [ # # ]: 0 : if (DEFAULT_TABLE(dfa)[i] >= state_count)
141 : : goto out;
142 [ # # ]: 0 : if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
143 : 0 : printk(KERN_ERR "AppArmor DFA next/check upper "
144 : : "bounds error\n");
145 : 0 : goto out;
146 : : }
147 : : }
148 : :
149 [ # # ]: 0 : for (i = 0; i < trans_count; i++) {
150 [ # # ]: 0 : if (NEXT_TABLE(dfa)[i] >= state_count)
151 : : goto out;
152 [ # # ]: 0 : if (CHECK_TABLE(dfa)[i] >= state_count)
153 : : goto out;
154 : : }
155 : : }
156 : :
157 : : error = 0;
158 : : out:
159 : 0 : return error;
160 : : }
161 : :
162 : : /**
163 : : * dfa_free - free a dfa allocated by aa_dfa_unpack
164 : : * @dfa: the dfa to free (MAYBE NULL)
165 : : *
166 : : * Requires: reference count to dfa == 0
167 : : */
168 : 0 : static void dfa_free(struct aa_dfa *dfa)
169 : : {
170 [ # # ]: 0 : if (dfa) {
171 : : int i;
172 : :
173 [ # # ]: 0 : for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
174 : 0 : kvfree(dfa->tables[i]);
175 : 0 : dfa->tables[i] = NULL;
176 : : }
177 : 0 : kfree(dfa);
178 : : }
179 : 0 : }
180 : :
181 : : /**
182 : : * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
183 : : * @kr: kref callback for freeing of a dfa (NOT NULL)
184 : : */
185 : 0 : void aa_dfa_free_kref(struct kref *kref)
186 : : {
187 : : struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
188 : 0 : dfa_free(dfa);
189 : 0 : }
190 : :
191 : : /**
192 : : * aa_dfa_unpack - unpack the binary tables of a serialized dfa
193 : : * @blob: aligned serialized stream of data to unpack (NOT NULL)
194 : : * @size: size of data to unpack
195 : : * @flags: flags controlling what type of accept tables are acceptable
196 : : *
197 : : * Unpack a dfa that has been serialized. To find information on the dfa
198 : : * format look in Documentation/security/apparmor.txt
199 : : * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
200 : : *
201 : : * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
202 : : */
203 : 0 : struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
204 : : {
205 : : int hsize;
206 : : int error = -ENOMEM;
207 : : char *data = blob;
208 : : struct table_header *table = NULL;
209 : : struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
210 [ # # ]: 0 : if (!dfa)
211 : : goto fail;
212 : :
213 : : kref_init(&dfa->count);
214 : :
215 : : error = -EPROTO;
216 : :
217 : : /* get dfa table set header */
218 [ # # ]: 0 : if (size < sizeof(struct table_set_header))
219 : : goto fail;
220 : :
221 [ # # ][ # # ]: 0 : if (ntohl(*(u32 *) data) != YYTH_MAGIC)
222 : : goto fail;
223 : :
224 [ # # ]: 0 : hsize = ntohl(*(u32 *) (data + 4));
225 [ # # ]: 0 : if (size < hsize)
226 : : goto fail;
227 : :
228 [ # # ]: 0 : dfa->flags = ntohs(*(u16 *) (data + 12));
229 : 0 : data += hsize;
230 : 0 : size -= hsize;
231 : :
232 [ # # ]: 0 : while (size > 0) {
233 : 0 : table = unpack_table(data, size);
234 [ # # ]: 0 : if (!table)
235 : : goto fail;
236 : :
237 [ # # # # : 0 : switch (table->td_id) {
# # ]
238 : : case YYTD_ID_ACCEPT:
239 [ # # ]: 0 : if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
240 : : goto fail;
241 : : break;
242 : : case YYTD_ID_ACCEPT2:
243 [ # # ]: 0 : if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
244 : : goto fail;
245 : : break;
246 : : case YYTD_ID_BASE:
247 [ # # ]: 0 : if (table->td_flags != YYTD_DATA32)
248 : : goto fail;
249 : : break;
250 : : case YYTD_ID_DEF:
251 : : case YYTD_ID_NXT:
252 : : case YYTD_ID_CHK:
253 [ # # ]: 0 : if (table->td_flags != YYTD_DATA16)
254 : : goto fail;
255 : : break;
256 : : case YYTD_ID_EC:
257 [ # # ]: 0 : if (table->td_flags != YYTD_DATA8)
258 : : goto fail;
259 : : break;
260 : : default:
261 : : goto fail;
262 : : }
263 : : /* check for duplicate table entry */
264 [ # # ]: 0 : if (dfa->tables[table->td_id])
265 : : goto fail;
266 : 0 : dfa->tables[table->td_id] = table;
267 : 0 : data += table_size(table->td_lolen, table->td_flags);
268 : 0 : size -= table_size(table->td_lolen, table->td_flags);
269 : : table = NULL;
270 : : }
271 : :
272 : 0 : error = verify_dfa(dfa, flags);
273 [ # # ]: 0 : if (error)
274 : : goto fail;
275 : :
276 : : return dfa;
277 : :
278 : : fail:
279 : 0 : kvfree(table);
280 : 0 : dfa_free(dfa);
281 : 0 : return ERR_PTR(error);
282 : : }
283 : :
284 : : /**
285 : : * aa_dfa_match_len - traverse @dfa to find state @str stops at
286 : : * @dfa: the dfa to match @str against (NOT NULL)
287 : : * @start: the state of the dfa to start matching in
288 : : * @str: the string of bytes to match against the dfa (NOT NULL)
289 : : * @len: length of the string of bytes to match
290 : : *
291 : : * aa_dfa_match_len will match @str against the dfa and return the state it
292 : : * finished matching in. The final state can be used to look up the accepting
293 : : * label, or as the start state of a continuing match.
294 : : *
295 : : * This function will happily match again the 0 byte and only finishes
296 : : * when @len input is consumed.
297 : : *
298 : : * Returns: final state reached after input is consumed
299 : : */
300 : 0 : unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
301 : : const char *str, int len)
302 : : {
303 : 0 : u16 *def = DEFAULT_TABLE(dfa);
304 : 0 : u32 *base = BASE_TABLE(dfa);
305 : 0 : u16 *next = NEXT_TABLE(dfa);
306 : 0 : u16 *check = CHECK_TABLE(dfa);
307 : : unsigned int state = start, pos;
308 : :
309 [ # # ]: 0 : if (state == 0)
310 : : return 0;
311 : :
312 : : /* current state is <state>, matching character *str */
313 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
314 : : /* Equivalence class table defined */
315 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
316 : : /* default is direct to next state */
317 [ # # ]: 0 : for (; len; len--) {
318 : 0 : pos = base_idx(base[state]) + equiv[(u8) *str++];
319 [ # # ]: 0 : if (check[pos] == state)
320 : 0 : state = next[pos];
321 : : else
322 : 0 : state = def[state];
323 : : }
324 : : } else {
325 : : /* default is direct to next state */
326 [ # # ]: 0 : for (; len; len--) {
327 : 0 : pos = base_idx(base[state]) + (u8) *str++;
328 [ # # ]: 0 : if (check[pos] == state)
329 : 0 : state = next[pos];
330 : : else
331 : 0 : state = def[state];
332 : : }
333 : : }
334 : :
335 : 0 : return state;
336 : : }
337 : :
338 : : /**
339 : : * aa_dfa_match - traverse @dfa to find state @str stops at
340 : : * @dfa: the dfa to match @str against (NOT NULL)
341 : : * @start: the state of the dfa to start matching in
342 : : * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
343 : : *
344 : : * aa_dfa_match will match @str against the dfa and return the state it
345 : : * finished matching in. The final state can be used to look up the accepting
346 : : * label, or as the start state of a continuing match.
347 : : *
348 : : * Returns: final state reached after input is consumed
349 : : */
350 : 0 : unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
351 : : const char *str)
352 : : {
353 : 0 : u16 *def = DEFAULT_TABLE(dfa);
354 : 0 : u32 *base = BASE_TABLE(dfa);
355 : 0 : u16 *next = NEXT_TABLE(dfa);
356 : 0 : u16 *check = CHECK_TABLE(dfa);
357 : : unsigned int state = start, pos;
358 : :
359 [ # # ]: 0 : if (state == 0)
360 : : return 0;
361 : :
362 : : /* current state is <state>, matching character *str */
363 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
364 : : /* Equivalence class table defined */
365 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
366 : : /* default is direct to next state */
367 [ # # ]: 0 : while (*str) {
368 : 0 : pos = base_idx(base[state]) + equiv[(u8) *str++];
369 [ # # ]: 0 : if (check[pos] == state)
370 : 0 : state = next[pos];
371 : : else
372 : 0 : state = def[state];
373 : : }
374 : : } else {
375 : : /* default is direct to next state */
376 [ # # ]: 0 : while (*str) {
377 : 0 : pos = base_idx(base[state]) + (u8) *str++;
378 [ # # ]: 0 : if (check[pos] == state)
379 : 0 : state = next[pos];
380 : : else
381 : 0 : state = def[state];
382 : : }
383 : : }
384 : :
385 : 0 : return state;
386 : : }
387 : :
388 : : /**
389 : : * aa_dfa_next - step one character to the next state in the dfa
390 : : * @dfa: the dfa to tranverse (NOT NULL)
391 : : * @state: the state to start in
392 : : * @c: the input character to transition on
393 : : *
394 : : * aa_dfa_match will step through the dfa by one input character @c
395 : : *
396 : : * Returns: state reach after input @c
397 : : */
398 : 0 : unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
399 : : const char c)
400 : : {
401 : 0 : u16 *def = DEFAULT_TABLE(dfa);
402 : 0 : u32 *base = BASE_TABLE(dfa);
403 : 0 : u16 *next = NEXT_TABLE(dfa);
404 : 0 : u16 *check = CHECK_TABLE(dfa);
405 : : unsigned int pos;
406 : :
407 : : /* current state is <state>, matching character *str */
408 [ # # ]: 0 : if (dfa->tables[YYTD_ID_EC]) {
409 : : /* Equivalence class table defined */
410 : 0 : u8 *equiv = EQUIV_TABLE(dfa);
411 : : /* default is direct to next state */
412 : :
413 : 0 : pos = base_idx(base[state]) + equiv[(u8) c];
414 [ # # ]: 0 : if (check[pos] == state)
415 : 0 : state = next[pos];
416 : : else
417 : 0 : state = def[state];
418 : : } else {
419 : : /* default is direct to next state */
420 : 0 : pos = base_idx(base[state]) + (u8) c;
421 [ # # ]: 0 : if (check[pos] == state)
422 : 0 : state = next[pos];
423 : : else
424 : 0 : state = def[state];
425 : : }
426 : :
427 : 0 : return state;
428 : : }
|
