linux/security/apparmor/match.c
<<
>>
Prefs
   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 */
  35static 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
  76out:
  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;
  83fail:
  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 */
  98static 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;
 157out:
 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 */
 167static 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 */
 184void 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 */
 202struct 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
 277fail:
 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 */
 299unsigned 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 */
 349unsigned 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 */
 397unsigned 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}
 428
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.