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