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/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 }