2 * AppArmor security module
4 * This file contains AppArmor dfa based regular expression matching engine
6 * Copyright (C) 1998-2008 Novell/SUSE
7 * Copyright 2009-2012 Canonical Ltd.
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
15 #include <linux/errno.h>
16 #include <linux/kernel.h>
18 #include <linux/slab.h>
19 #include <linux/vmalloc.h>
20 #include <linux/err.h>
21 #include <linux/kref.h>
23 #include "include/lib.h"
24 #include "include/match.h"
26 #define base_idx(X) ((X) & 0xffffff)
28 static char nulldfa_src[] = {
31 struct aa_dfa *nulldfa;
33 static char stacksplitdfa_src[] = {
34 #include "stacksplitdfa.in"
36 struct aa_dfa *stacksplitdfa;
38 int aa_setup_dfa_engine(void)
42 nulldfa = aa_dfa_unpack(nulldfa_src, sizeof(nulldfa_src),
43 TO_ACCEPT1_FLAG(YYTD_DATA32) |
44 TO_ACCEPT2_FLAG(YYTD_DATA32));
45 if (IS_ERR(nulldfa)) {
46 error = PTR_ERR(nulldfa);
51 stacksplitdfa = aa_dfa_unpack(stacksplitdfa_src,
52 sizeof(stacksplitdfa_src),
53 TO_ACCEPT1_FLAG(YYTD_DATA32) |
54 TO_ACCEPT2_FLAG(YYTD_DATA32));
55 if (IS_ERR(stacksplitdfa)) {
58 error = PTR_ERR(stacksplitdfa);
66 void aa_teardown_dfa_engine(void)
68 aa_put_dfa(stacksplitdfa);
73 * unpack_table - unpack a dfa table (one of accept, default, base, next check)
74 * @blob: data to unpack (NOT NULL)
75 * @bsize: size of blob
77 * Returns: pointer to table else NULL on failure
79 * NOTE: must be freed by kvfree (not kfree)
81 static struct table_header *unpack_table(char *blob, size_t bsize)
83 struct table_header *table = NULL;
84 struct table_header th;
87 if (bsize < sizeof(struct table_header))
90 /* loaded td_id's start at 1, subtract 1 now to avoid doing
91 * it every time we use td_id as an index
93 th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1;
94 if (th.td_id > YYTD_ID_MAX)
96 th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
97 th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8));
98 blob += sizeof(struct table_header);
100 if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
101 th.td_flags == YYTD_DATA8))
104 /* if we have a table it must have some entries */
105 if (th.td_lolen == 0)
107 tsize = table_size(th.td_lolen, th.td_flags);
111 table = kvzalloc(tsize, GFP_KERNEL);
113 table->td_id = th.td_id;
114 table->td_flags = th.td_flags;
115 table->td_lolen = th.td_lolen;
116 if (th.td_flags == YYTD_DATA8)
117 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
118 u8, u8, byte_to_byte);
119 else if (th.td_flags == YYTD_DATA16)
120 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
121 u16, __be16, be16_to_cpu);
122 else if (th.td_flags == YYTD_DATA32)
123 UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
124 u32, __be32, be32_to_cpu);
127 /* if table was vmalloced make sure the page tables are synced
128 * before it is used, as it goes live to all cpus.
130 if (is_vmalloc_addr(table))
142 * verify_table_headers - verify that the tables headers are as expected
143 * @tables - array of dfa tables to check (NOT NULL)
144 * @flags: flags controlling what type of accept table are acceptable
146 * Assumes dfa has gone through the first pass verification done by unpacking
147 * NOTE: this does not valid accept table values
149 * Returns: %0 else error code on failure to verify
151 static int verify_table_headers(struct table_header **tables, int flags)
153 size_t state_count, trans_count;
156 /* check that required tables exist */
157 if (!(tables[YYTD_ID_DEF] && tables[YYTD_ID_BASE] &&
158 tables[YYTD_ID_NXT] && tables[YYTD_ID_CHK]))
161 /* accept.size == default.size == base.size */
162 state_count = tables[YYTD_ID_BASE]->td_lolen;
163 if (ACCEPT1_FLAGS(flags)) {
164 if (!tables[YYTD_ID_ACCEPT])
166 if (state_count != tables[YYTD_ID_ACCEPT]->td_lolen)
169 if (ACCEPT2_FLAGS(flags)) {
170 if (!tables[YYTD_ID_ACCEPT2])
172 if (state_count != tables[YYTD_ID_ACCEPT2]->td_lolen)
175 if (state_count != tables[YYTD_ID_DEF]->td_lolen)
178 /* next.size == chk.size */
179 trans_count = tables[YYTD_ID_NXT]->td_lolen;
180 if (trans_count != tables[YYTD_ID_CHK]->td_lolen)
183 /* if equivalence classes then its table size must be 256 */
184 if (tables[YYTD_ID_EC] && tables[YYTD_ID_EC]->td_lolen != 256)
193 * verify_dfa - verify that transitions and states in the tables are in bounds.
194 * @dfa: dfa to test (NOT NULL)
196 * Assumes dfa has gone through the first pass verification done by unpacking
197 * NOTE: this does not valid accept table values
199 * Returns: %0 else error code on failure to verify
201 static int verify_dfa(struct aa_dfa *dfa)
203 size_t i, state_count, trans_count;
206 state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
207 trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
208 if (state_count == 0)
210 for (i = 0; i < state_count; i++) {
211 if (!(BASE_TABLE(dfa)[i] & MATCH_FLAG_DIFF_ENCODE) &&
212 (DEFAULT_TABLE(dfa)[i] >= state_count))
214 if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
215 pr_err("AppArmor DFA next/check upper bounds error\n");
220 for (i = 0; i < trans_count; i++) {
221 if (NEXT_TABLE(dfa)[i] >= state_count)
223 if (CHECK_TABLE(dfa)[i] >= state_count)
227 /* Now that all the other tables are verified, verify diffencoding */
228 for (i = 0; i < state_count; i++) {
232 (BASE_TABLE(dfa)[j] & MATCH_FLAG_DIFF_ENCODE) &&
233 !(BASE_TABLE(dfa)[j] & MARK_DIFF_ENCODE);
235 k = DEFAULT_TABLE(dfa)[j];
239 break; /* already verified */
240 BASE_TABLE(dfa)[j] |= MARK_DIFF_ENCODE;
250 * dfa_free - free a dfa allocated by aa_dfa_unpack
251 * @dfa: the dfa to free (MAYBE NULL)
253 * Requires: reference count to dfa == 0
255 static void dfa_free(struct aa_dfa *dfa)
260 for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
261 kvfree(dfa->tables[i]);
262 dfa->tables[i] = NULL;
269 * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
270 * @kr: kref callback for freeing of a dfa (NOT NULL)
272 void aa_dfa_free_kref(struct kref *kref)
274 struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
279 * aa_dfa_unpack - unpack the binary tables of a serialized dfa
280 * @blob: aligned serialized stream of data to unpack (NOT NULL)
281 * @size: size of data to unpack
282 * @flags: flags controlling what type of accept tables are acceptable
284 * Unpack a dfa that has been serialized. To find information on the dfa
285 * format look in Documentation/admin-guide/LSM/apparmor.rst
286 * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
288 * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
290 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
295 struct table_header *table = NULL;
296 struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
300 kref_init(&dfa->count);
304 /* get dfa table set header */
305 if (size < sizeof(struct table_set_header))
308 if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
311 hsize = ntohl(*(__be32 *) (data + 4));
315 dfa->flags = ntohs(*(__be16 *) (data + 12));
316 if (dfa->flags != 0 && dfa->flags != YYTH_FLAG_DIFF_ENCODE)
323 table = unpack_table(data, size);
327 switch (table->td_id) {
329 if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
332 case YYTD_ID_ACCEPT2:
333 if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
337 if (table->td_flags != YYTD_DATA32)
343 if (table->td_flags != YYTD_DATA16)
347 if (table->td_flags != YYTD_DATA8)
353 /* check for duplicate table entry */
354 if (dfa->tables[table->td_id])
356 dfa->tables[table->td_id] = table;
357 data += table_size(table->td_lolen, table->td_flags);
358 size -= table_size(table->td_lolen, table->td_flags);
361 error = verify_table_headers(dfa->tables, flags);
365 if (flags & DFA_FLAG_VERIFY_STATES) {
366 error = verify_dfa(dfa);
376 return ERR_PTR(error);
379 #define match_char(state, def, base, next, check, C) \
381 u32 b = (base)[(state)]; \
382 unsigned int pos = base_idx(b) + (C); \
383 if ((check)[pos] != (state)) { \
384 (state) = (def)[(state)]; \
385 if (b & MATCH_FLAG_DIFF_ENCODE) \
389 (state) = (next)[pos]; \
394 * aa_dfa_match_len - traverse @dfa to find state @str stops at
395 * @dfa: the dfa to match @str against (NOT NULL)
396 * @start: the state of the dfa to start matching in
397 * @str: the string of bytes to match against the dfa (NOT NULL)
398 * @len: length of the string of bytes to match
400 * aa_dfa_match_len will match @str against the dfa and return the state it
401 * finished matching in. The final state can be used to look up the accepting
402 * label, or as the start state of a continuing match.
404 * This function will happily match again the 0 byte and only finishes
405 * when @len input is consumed.
407 * Returns: final state reached after input is consumed
409 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
410 const char *str, int len)
412 u16 *def = DEFAULT_TABLE(dfa);
413 u32 *base = BASE_TABLE(dfa);
414 u16 *next = NEXT_TABLE(dfa);
415 u16 *check = CHECK_TABLE(dfa);
416 unsigned int state = start;
421 /* current state is <state>, matching character *str */
422 if (dfa->tables[YYTD_ID_EC]) {
423 /* Equivalence class table defined */
424 u8 *equiv = EQUIV_TABLE(dfa);
426 match_char(state, def, base, next, check,
429 /* default is direct to next state */
431 match_char(state, def, base, next, check, (u8) *str++);
438 * aa_dfa_match - traverse @dfa to find state @str stops at
439 * @dfa: the dfa to match @str against (NOT NULL)
440 * @start: the state of the dfa to start matching in
441 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
443 * aa_dfa_match will match @str against the dfa and return the state it
444 * finished matching in. The final state can be used to look up the accepting
445 * label, or as the start state of a continuing match.
447 * Returns: final state reached after input is consumed
449 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
452 u16 *def = DEFAULT_TABLE(dfa);
453 u32 *base = BASE_TABLE(dfa);
454 u16 *next = NEXT_TABLE(dfa);
455 u16 *check = CHECK_TABLE(dfa);
456 unsigned int state = start;
461 /* current state is <state>, matching character *str */
462 if (dfa->tables[YYTD_ID_EC]) {
463 /* Equivalence class table defined */
464 u8 *equiv = EQUIV_TABLE(dfa);
465 /* default is direct to next state */
467 match_char(state, def, base, next, check,
470 /* default is direct to next state */
472 match_char(state, def, base, next, check, (u8) *str++);
479 * aa_dfa_next - step one character to the next state in the dfa
480 * @dfa: the dfa to traverse (NOT NULL)
481 * @state: the state to start in
482 * @c: the input character to transition on
484 * aa_dfa_match will step through the dfa by one input character @c
486 * Returns: state reach after input @c
488 unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
491 u16 *def = DEFAULT_TABLE(dfa);
492 u32 *base = BASE_TABLE(dfa);
493 u16 *next = NEXT_TABLE(dfa);
494 u16 *check = CHECK_TABLE(dfa);
496 /* current state is <state>, matching character *str */
497 if (dfa->tables[YYTD_ID_EC]) {
498 /* Equivalence class table defined */
499 u8 *equiv = EQUIV_TABLE(dfa);
500 match_char(state, def, base, next, check, equiv[(u8) c]);
502 match_char(state, def, base, next, check, (u8) c);
508 * aa_dfa_match_until - traverse @dfa until accept state or end of input
509 * @dfa: the dfa to match @str against (NOT NULL)
510 * @start: the state of the dfa to start matching in
511 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
512 * @retpos: first character in str after match OR end of string
514 * aa_dfa_match will match @str against the dfa and return the state it
515 * finished matching in. The final state can be used to look up the accepting
516 * label, or as the start state of a continuing match.
518 * Returns: final state reached after input is consumed
520 unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start,
521 const char *str, const char **retpos)
523 u16 *def = DEFAULT_TABLE(dfa);
524 u32 *base = BASE_TABLE(dfa);
525 u16 *next = NEXT_TABLE(dfa);
526 u16 *check = CHECK_TABLE(dfa);
527 u32 *accept = ACCEPT_TABLE(dfa);
528 unsigned int state = start, pos;
533 /* current state is <state>, matching character *str */
534 if (dfa->tables[YYTD_ID_EC]) {
535 /* Equivalence class table defined */
536 u8 *equiv = EQUIV_TABLE(dfa);
537 /* default is direct to next state */
539 pos = base_idx(base[state]) + equiv[(u8) *str++];
540 if (check[pos] == state)
548 /* default is direct to next state */
550 pos = base_idx(base[state]) + (u8) *str++;
551 if (check[pos] == state)
565 * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed
566 * @dfa: the dfa to match @str against (NOT NULL)
567 * @start: the state of the dfa to start matching in
568 * @str: the string of bytes to match against the dfa (NOT NULL)
569 * @n: length of the string of bytes to match
570 * @retpos: first character in str after match OR str + n
572 * aa_dfa_match_len will match @str against the dfa and return the state it
573 * finished matching in. The final state can be used to look up the accepting
574 * label, or as the start state of a continuing match.
576 * This function will happily match again the 0 byte and only finishes
577 * when @n input is consumed.
579 * Returns: final state reached after input is consumed
581 unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start,
582 const char *str, int n, const char **retpos)
584 u16 *def = DEFAULT_TABLE(dfa);
585 u32 *base = BASE_TABLE(dfa);
586 u16 *next = NEXT_TABLE(dfa);
587 u16 *check = CHECK_TABLE(dfa);
588 u32 *accept = ACCEPT_TABLE(dfa);
589 unsigned int state = start, pos;
595 /* current state is <state>, matching character *str */
596 if (dfa->tables[YYTD_ID_EC]) {
597 /* Equivalence class table defined */
598 u8 *equiv = EQUIV_TABLE(dfa);
599 /* default is direct to next state */
601 pos = base_idx(base[state]) + equiv[(u8) *str++];
602 if (check[pos] == state)
610 /* default is direct to next state */
612 pos = base_idx(base[state]) + (u8) *str++;
613 if (check[pos] == state)
626 #define inc_wb_pos(wb) \
628 wb->pos = (wb->pos + 1) & (wb->size - 1); \
629 wb->len = (wb->len + 1) & (wb->size - 1); \
632 /* For DFAs that don't support extended tagging of states */
633 static bool is_loop(struct match_workbuf *wb, unsigned int state,
634 unsigned int *adjust)
636 unsigned int pos = wb->pos;
639 if (wb->history[pos] < state)
642 for (i = 0; i <= wb->len; i++) {
643 if (wb->history[pos] == state) {
656 static unsigned int leftmatch_fb(struct aa_dfa *dfa, unsigned int start,
657 const char *str, struct match_workbuf *wb,
660 u16 *def = DEFAULT_TABLE(dfa);
661 u32 *base = BASE_TABLE(dfa);
662 u16 *next = NEXT_TABLE(dfa);
663 u16 *check = CHECK_TABLE(dfa);
664 unsigned int state = start, pos;
675 /* current state is <state>, matching character *str */
676 if (dfa->tables[YYTD_ID_EC]) {
677 /* Equivalence class table defined */
678 u8 *equiv = EQUIV_TABLE(dfa);
679 /* default is direct to next state */
683 wb->history[wb->pos] = state;
684 pos = base_idx(base[state]) + equiv[(u8) *str++];
685 if (check[pos] == state)
689 if (is_loop(wb, state, &adjust)) {
690 state = aa_dfa_match(dfa, state, str);
698 /* default is direct to next state */
702 wb->history[wb->pos] = state;
703 pos = base_idx(base[state]) + (u8) *str++;
704 if (check[pos] == state)
708 if (is_loop(wb, state, &adjust)) {
709 state = aa_dfa_match(dfa, state, str);
725 * aa_dfa_leftmatch - traverse @dfa to find state @str stops at
726 * @dfa: the dfa to match @str against (NOT NULL)
727 * @start: the state of the dfa to start matching in
728 * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
729 * @count: current count of longest left.
731 * aa_dfa_match will match @str against the dfa and return the state it
732 * finished matching in. The final state can be used to look up the accepting
733 * label, or as the start state of a continuing match.
735 * Returns: final state reached after input is consumed
737 unsigned int aa_dfa_leftmatch(struct aa_dfa *dfa, unsigned int start,
738 const char *str, unsigned int *count)
742 /* TODO: match for extended state dfas */
744 return leftmatch_fb(dfa, start, str, &wb, count);