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 33 static char stacksplitdfa_src[] = { 34 #include "stacksplitdfa.in" 35 }; 36 struct aa_dfa *stacksplitdfa; 37 38 int aa_setup_dfa_engine(void) 39 { 40 int error; 41 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); 47 nulldfa = NULL; 48 return error; 49 } 50 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)) { 56 aa_put_dfa(nulldfa); 57 nulldfa = NULL; 58 error = PTR_ERR(stacksplitdfa); 59 stacksplitdfa = NULL; 60 return error; 61 } 62 63 return 0; 64 } 65 66 void aa_teardown_dfa_engine(void) 67 { 68 aa_put_dfa(stacksplitdfa); 69 aa_put_dfa(nulldfa); 70 } 71 72 /** 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 76 * 77 * Returns: pointer to table else NULL on failure 78 * 79 * NOTE: must be freed by kvfree (not kfree) 80 */ 81 static struct table_header *unpack_table(char *blob, size_t bsize) 82 { 83 struct table_header *table = NULL; 84 struct table_header th; 85 size_t tsize; 86 87 if (bsize < sizeof(struct table_header)) 88 goto out; 89 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 92 */ 93 th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1; 94 if (th.td_id > YYTD_ID_MAX) 95 goto out; 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); 99 100 if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 || 101 th.td_flags == YYTD_DATA8)) 102 goto out; 103 104 tsize = table_size(th.td_lolen, th.td_flags); 105 if (bsize < tsize) 106 goto out; 107 108 table = kvzalloc(tsize, GFP_KERNEL); 109 if (table) { 110 table->td_id = th.td_id; 111 table->td_flags = th.td_flags; 112 table->td_lolen = th.td_lolen; 113 if (th.td_flags == YYTD_DATA8) 114 UNPACK_ARRAY(table->td_data, blob, th.td_lolen, 115 u8, u8, byte_to_byte); 116 else if (th.td_flags == YYTD_DATA16) 117 UNPACK_ARRAY(table->td_data, blob, th.td_lolen, 118 u16, __be16, be16_to_cpu); 119 else if (th.td_flags == YYTD_DATA32) 120 UNPACK_ARRAY(table->td_data, blob, th.td_lolen, 121 u32, __be32, be32_to_cpu); 122 else 123 goto fail; 124 /* if table was vmalloced make sure the page tables are synced 125 * before it is used, as it goes live to all cpus. 126 */ 127 if (is_vmalloc_addr(table)) 128 vm_unmap_aliases(); 129 } 130 131 out: 132 return table; 133 fail: 134 kvfree(table); 135 return NULL; 136 } 137 138 /** 139 * verify_dfa - verify that transitions and states in the tables are in bounds. 140 * @dfa: dfa to test (NOT NULL) 141 * @flags: flags controlling what type of accept table are acceptable 142 * 143 * Assumes dfa has gone through the first pass verification done by unpacking 144 * NOTE: this does not valid accept table values 145 * 146 * Returns: %0 else error code on failure to verify 147 */ 148 static int verify_dfa(struct aa_dfa *dfa, int flags) 149 { 150 size_t i, state_count, trans_count; 151 int error = -EPROTO; 152 153 /* check that required tables exist */ 154 if (!(dfa->tables[YYTD_ID_DEF] && 155 dfa->tables[YYTD_ID_BASE] && 156 dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK])) 157 goto out; 158 159 /* accept.size == default.size == base.size */ 160 state_count = dfa->tables[YYTD_ID_BASE]->td_lolen; 161 if (ACCEPT1_FLAGS(flags)) { 162 if (!dfa->tables[YYTD_ID_ACCEPT]) 163 goto out; 164 if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen) 165 goto out; 166 } 167 if (ACCEPT2_FLAGS(flags)) { 168 if (!dfa->tables[YYTD_ID_ACCEPT2]) 169 goto out; 170 if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen) 171 goto out; 172 } 173 if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen) 174 goto out; 175 176 /* next.size == chk.size */ 177 trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen; 178 if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen) 179 goto out; 180 181 /* if equivalence classes then its table size must be 256 */ 182 if (dfa->tables[YYTD_ID_EC] && 183 dfa->tables[YYTD_ID_EC]->td_lolen != 256) 184 goto out; 185 186 if (flags & DFA_FLAG_VERIFY_STATES) { 187 for (i = 0; i < state_count; i++) { 188 if (DEFAULT_TABLE(dfa)[i] >= state_count) 189 goto out; 190 if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) { 191 printk(KERN_ERR "AppArmor DFA next/check upper " 192 "bounds error\n"); 193 goto out; 194 } 195 } 196 197 for (i = 0; i < trans_count; i++) { 198 if (NEXT_TABLE(dfa)[i] >= state_count) 199 goto out; 200 if (CHECK_TABLE(dfa)[i] >= state_count) 201 goto out; 202 } 203 } 204 205 error = 0; 206 out: 207 return error; 208 } 209 210 /** 211 * dfa_free - free a dfa allocated by aa_dfa_unpack 212 * @dfa: the dfa to free (MAYBE NULL) 213 * 214 * Requires: reference count to dfa == 0 215 */ 216 static void dfa_free(struct aa_dfa *dfa) 217 { 218 if (dfa) { 219 int i; 220 221 for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) { 222 kvfree(dfa->tables[i]); 223 dfa->tables[i] = NULL; 224 } 225 kfree(dfa); 226 } 227 } 228 229 /** 230 * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa) 231 * @kr: kref callback for freeing of a dfa (NOT NULL) 232 */ 233 void aa_dfa_free_kref(struct kref *kref) 234 { 235 struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count); 236 dfa_free(dfa); 237 } 238 239 /** 240 * aa_dfa_unpack - unpack the binary tables of a serialized dfa 241 * @blob: aligned serialized stream of data to unpack (NOT NULL) 242 * @size: size of data to unpack 243 * @flags: flags controlling what type of accept tables are acceptable 244 * 245 * Unpack a dfa that has been serialized. To find information on the dfa 246 * format look in Documentation/admin-guide/LSM/apparmor.rst 247 * Assumes the dfa @blob stream has been aligned on a 8 byte boundary 248 * 249 * Returns: an unpacked dfa ready for matching or ERR_PTR on failure 250 */ 251 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags) 252 { 253 int hsize; 254 int error = -ENOMEM; 255 char *data = blob; 256 struct table_header *table = NULL; 257 struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL); 258 if (!dfa) 259 goto fail; 260 261 kref_init(&dfa->count); 262 263 error = -EPROTO; 264 265 /* get dfa table set header */ 266 if (size < sizeof(struct table_set_header)) 267 goto fail; 268 269 if (ntohl(*(__be32 *) data) != YYTH_MAGIC) 270 goto fail; 271 272 hsize = ntohl(*(__be32 *) (data + 4)); 273 if (size < hsize) 274 goto fail; 275 276 dfa->flags = ntohs(*(__be16 *) (data + 12)); 277 data += hsize; 278 size -= hsize; 279 280 while (size > 0) { 281 table = unpack_table(data, size); 282 if (!table) 283 goto fail; 284 285 switch (table->td_id) { 286 case YYTD_ID_ACCEPT: 287 if (!(table->td_flags & ACCEPT1_FLAGS(flags))) 288 goto fail; 289 break; 290 case YYTD_ID_ACCEPT2: 291 if (!(table->td_flags & ACCEPT2_FLAGS(flags))) 292 goto fail; 293 break; 294 case YYTD_ID_BASE: 295 if (table->td_flags != YYTD_DATA32) 296 goto fail; 297 break; 298 case YYTD_ID_DEF: 299 case YYTD_ID_NXT: 300 case YYTD_ID_CHK: 301 if (table->td_flags != YYTD_DATA16) 302 goto fail; 303 break; 304 case YYTD_ID_EC: 305 if (table->td_flags != YYTD_DATA8) 306 goto fail; 307 break; 308 default: 309 goto fail; 310 } 311 /* check for duplicate table entry */ 312 if (dfa->tables[table->td_id]) 313 goto fail; 314 dfa->tables[table->td_id] = table; 315 data += table_size(table->td_lolen, table->td_flags); 316 size -= table_size(table->td_lolen, table->td_flags); 317 table = NULL; 318 } 319 320 error = verify_dfa(dfa, flags); 321 if (error) 322 goto fail; 323 324 return dfa; 325 326 fail: 327 kvfree(table); 328 dfa_free(dfa); 329 return ERR_PTR(error); 330 } 331 332 /** 333 * aa_dfa_match_len - traverse @dfa to find state @str stops at 334 * @dfa: the dfa to match @str against (NOT NULL) 335 * @start: the state of the dfa to start matching in 336 * @str: the string of bytes to match against the dfa (NOT NULL) 337 * @len: length of the string of bytes to match 338 * 339 * aa_dfa_match_len will match @str against the dfa and return the state it 340 * finished matching in. The final state can be used to look up the accepting 341 * label, or as the start state of a continuing match. 342 * 343 * This function will happily match again the 0 byte and only finishes 344 * when @len input is consumed. 345 * 346 * Returns: final state reached after input is consumed 347 */ 348 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start, 349 const char *str, int len) 350 { 351 u16 *def = DEFAULT_TABLE(dfa); 352 u32 *base = BASE_TABLE(dfa); 353 u16 *next = NEXT_TABLE(dfa); 354 u16 *check = CHECK_TABLE(dfa); 355 unsigned int state = start, pos; 356 357 if (state == 0) 358 return 0; 359 360 /* current state is <state>, matching character *str */ 361 if (dfa->tables[YYTD_ID_EC]) { 362 /* Equivalence class table defined */ 363 u8 *equiv = EQUIV_TABLE(dfa); 364 /* default is direct to next state */ 365 for (; len; len--) { 366 pos = base_idx(base[state]) + equiv[(u8) *str++]; 367 if (check[pos] == state) 368 state = next[pos]; 369 else 370 state = def[state]; 371 } 372 } else { 373 /* default is direct to next state */ 374 for (; len; len--) { 375 pos = base_idx(base[state]) + (u8) *str++; 376 if (check[pos] == state) 377 state = next[pos]; 378 else 379 state = def[state]; 380 } 381 } 382 383 return state; 384 } 385 386 /** 387 * aa_dfa_match - traverse @dfa to find state @str stops at 388 * @dfa: the dfa to match @str against (NOT NULL) 389 * @start: the state of the dfa to start matching in 390 * @str: the null terminated string of bytes to match against the dfa (NOT NULL) 391 * 392 * aa_dfa_match will match @str against the dfa and return the state it 393 * finished matching in. The final state can be used to look up the accepting 394 * label, or as the start state of a continuing match. 395 * 396 * Returns: final state reached after input is consumed 397 */ 398 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start, 399 const char *str) 400 { 401 u16 *def = DEFAULT_TABLE(dfa); 402 u32 *base = BASE_TABLE(dfa); 403 u16 *next = NEXT_TABLE(dfa); 404 u16 *check = CHECK_TABLE(dfa); 405 unsigned int state = start, pos; 406 407 if (state == 0) 408 return 0; 409 410 /* current state is <state>, matching character *str */ 411 if (dfa->tables[YYTD_ID_EC]) { 412 /* Equivalence class table defined */ 413 u8 *equiv = EQUIV_TABLE(dfa); 414 /* default is direct to next state */ 415 while (*str) { 416 pos = base_idx(base[state]) + equiv[(u8) *str++]; 417 if (check[pos] == state) 418 state = next[pos]; 419 else 420 state = def[state]; 421 } 422 } else { 423 /* default is direct to next state */ 424 while (*str) { 425 pos = base_idx(base[state]) + (u8) *str++; 426 if (check[pos] == state) 427 state = next[pos]; 428 else 429 state = def[state]; 430 } 431 } 432 433 return state; 434 } 435 436 /** 437 * aa_dfa_next - step one character to the next state in the dfa 438 * @dfa: the dfa to tranverse (NOT NULL) 439 * @state: the state to start in 440 * @c: the input character to transition on 441 * 442 * aa_dfa_match will step through the dfa by one input character @c 443 * 444 * Returns: state reach after input @c 445 */ 446 unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state, 447 const char c) 448 { 449 u16 *def = DEFAULT_TABLE(dfa); 450 u32 *base = BASE_TABLE(dfa); 451 u16 *next = NEXT_TABLE(dfa); 452 u16 *check = CHECK_TABLE(dfa); 453 unsigned int pos; 454 455 /* current state is <state>, matching character *str */ 456 if (dfa->tables[YYTD_ID_EC]) { 457 /* Equivalence class table defined */ 458 u8 *equiv = EQUIV_TABLE(dfa); 459 /* default is direct to next state */ 460 461 pos = base_idx(base[state]) + equiv[(u8) c]; 462 if (check[pos] == state) 463 state = next[pos]; 464 else 465 state = def[state]; 466 } else { 467 /* default is direct to next state */ 468 pos = base_idx(base[state]) + (u8) c; 469 if (check[pos] == state) 470 state = next[pos]; 471 else 472 state = def[state]; 473 } 474 475 return state; 476 } 477 478 /** 479 * aa_dfa_match_until - traverse @dfa until accept state or end of input 480 * @dfa: the dfa to match @str against (NOT NULL) 481 * @start: the state of the dfa to start matching in 482 * @str: the null terminated string of bytes to match against the dfa (NOT NULL) 483 * @retpos: first character in str after match OR end of string 484 * 485 * aa_dfa_match will match @str against the dfa and return the state it 486 * finished matching in. The final state can be used to look up the accepting 487 * label, or as the start state of a continuing match. 488 * 489 * Returns: final state reached after input is consumed 490 */ 491 unsigned int aa_dfa_match_until(struct aa_dfa *dfa, unsigned int start, 492 const char *str, const char **retpos) 493 { 494 u16 *def = DEFAULT_TABLE(dfa); 495 u32 *base = BASE_TABLE(dfa); 496 u16 *next = NEXT_TABLE(dfa); 497 u16 *check = CHECK_TABLE(dfa); 498 u32 *accept = ACCEPT_TABLE(dfa); 499 unsigned int state = start, pos; 500 501 if (state == 0) 502 return 0; 503 504 /* current state is <state>, matching character *str */ 505 if (dfa->tables[YYTD_ID_EC]) { 506 /* Equivalence class table defined */ 507 u8 *equiv = EQUIV_TABLE(dfa); 508 /* default is direct to next state */ 509 while (*str) { 510 pos = base_idx(base[state]) + equiv[(u8) *str++]; 511 if (check[pos] == state) 512 state = next[pos]; 513 else 514 state = def[state]; 515 if (accept[state]) 516 break; 517 } 518 } else { 519 /* default is direct to next state */ 520 while (*str) { 521 pos = base_idx(base[state]) + (u8) *str++; 522 if (check[pos] == state) 523 state = next[pos]; 524 else 525 state = def[state]; 526 if (accept[state]) 527 break; 528 } 529 } 530 531 *retpos = str; 532 return state; 533 } 534 535 536 /** 537 * aa_dfa_matchn_until - traverse @dfa until accept or @n bytes consumed 538 * @dfa: the dfa to match @str against (NOT NULL) 539 * @start: the state of the dfa to start matching in 540 * @str: the string of bytes to match against the dfa (NOT NULL) 541 * @n: length of the string of bytes to match 542 * @retpos: first character in str after match OR str + n 543 * 544 * aa_dfa_match_len will match @str against the dfa and return the state it 545 * finished matching in. The final state can be used to look up the accepting 546 * label, or as the start state of a continuing match. 547 * 548 * This function will happily match again the 0 byte and only finishes 549 * when @n input is consumed. 550 * 551 * Returns: final state reached after input is consumed 552 */ 553 unsigned int aa_dfa_matchn_until(struct aa_dfa *dfa, unsigned int start, 554 const char *str, int n, const char **retpos) 555 { 556 u16 *def = DEFAULT_TABLE(dfa); 557 u32 *base = BASE_TABLE(dfa); 558 u16 *next = NEXT_TABLE(dfa); 559 u16 *check = CHECK_TABLE(dfa); 560 u32 *accept = ACCEPT_TABLE(dfa); 561 unsigned int state = start, pos; 562 563 *retpos = NULL; 564 if (state == 0) 565 return 0; 566 567 /* current state is <state>, matching character *str */ 568 if (dfa->tables[YYTD_ID_EC]) { 569 /* Equivalence class table defined */ 570 u8 *equiv = EQUIV_TABLE(dfa); 571 /* default is direct to next state */ 572 for (; n; n--) { 573 pos = base_idx(base[state]) + equiv[(u8) *str++]; 574 if (check[pos] == state) 575 state = next[pos]; 576 else 577 state = def[state]; 578 if (accept[state]) 579 break; 580 } 581 } else { 582 /* default is direct to next state */ 583 for (; n; n--) { 584 pos = base_idx(base[state]) + (u8) *str++; 585 if (check[pos] == state) 586 state = next[pos]; 587 else 588 state = def[state]; 589 if (accept[state]) 590 break; 591 } 592 } 593 594 *retpos = str; 595 return state; 596 } 597