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