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