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