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