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 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 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 */ 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); 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 */ 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 */ 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 229 * format look in Documentation/security/apparmor.txt 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 */ 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 */ 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 */ 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 */ 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