security/apparmor/match.c

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