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/lib.h"
24 #include "include/match.h"
25
26 #define base_idx(X) ((X) & 0xffffff)
27
28 static char nulldfa_src[] = {
29 #include "nulldfa.in"
30 };
31 struct aa_dfa *nulldfa;
32
aa_setup_dfa_engine(void)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
aa_teardown_dfa_engine(void)49 void aa_teardown_dfa_engine(void)
50 {
51 aa_put_dfa(nulldfa);
52 nulldfa = NULL;
53 }
54
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 *
62 * NOTE: must be freed by kvfree (not kfree)
63 */
unpack_table(char * blob,size_t bsize)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 */
76 th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1;
77 if (th.td_id > YYTD_ID_MAX)
78 goto out;
79 th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
80 th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8));
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
91 table = kvzalloc(tsize, GFP_KERNEL);
92 if (table) {
93 table->td_id = th.td_id;
94 table->td_flags = th.td_flags;
95 table->td_lolen = th.td_lolen;
96 if (th.td_flags == YYTD_DATA8)
97 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
98 u8, u8, byte_to_byte);
99 else if (th.td_flags == YYTD_DATA16)
100 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
101 u16, __be16, be16_to_cpu);
102 else if (th.td_flags == YYTD_DATA32)
103 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
104 u32, __be32, be32_to_cpu);
105 else
106 goto fail;
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();
112 }
113
114 out:
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 */
verify_dfa(struct aa_dfa * dfa,int flags)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;
173 if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
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 */
dfa_free(struct aa_dfa * dfa)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 */
aa_dfa_free_kref(struct kref * kref)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
229 * format look in Documentation/admin-guide/LSM/apparmor.rst
230 * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
231 *
232 * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
233 */
aa_dfa_unpack(void * blob,size_t size,int flags)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
252 if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
253 goto fail;
254
255 hsize = ntohl(*(__be32 *) (data + 4));
256 if (size < hsize)
257 goto fail;
258
259 dfa->flags = ntohs(*(__be16 *) (data + 12));
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 */
aa_dfa_match_len(struct aa_dfa * dfa,unsigned int start,const char * str,int len)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--) {
349 pos = base_idx(base[state]) + equiv[(u8) *str++];
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--) {
358 pos = base_idx(base[state]) + (u8) *str++;
359 if (check[pos] == state)
360 state = next[pos];
361 else
362 state = def[state];
363 }
364 }
365
366 return state;
367 }
368
369 /**
370 * aa_dfa_match - traverse @dfa to find state @str stops at
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 *
375 * aa_dfa_match will match @str against the dfa and return the state it
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 */
aa_dfa_match(struct aa_dfa * dfa,unsigned int start,const char * str)381 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
382 const char *str)
383 {
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) {
399 pos = base_idx(base[state]) + equiv[(u8) *str++];
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) {
408 pos = base_idx(base[state]) + (u8) *str++;
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 */
aa_dfa_next(struct aa_dfa * dfa,unsigned int state,const char c)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
444 pos = base_idx(base[state]) + equiv[(u8) c];
445 if (check[pos] == state)
446 state = next[pos];
447 else
448 state = def[state];
449 } else {
450 /* default is direct to next state */
451 pos = base_idx(base[state]) + (u8) c;
452 if (check[pos] == state)
453 state = next[pos];
454 else
455 state = def[state];
456 }
457
458 return state;
459 }
460