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