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