Root/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 */
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/apparmor.txt
198 * Assumes the dfa @blob stream has been aligned on a 8 byte boundry
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_next_state - 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_next_state 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    return aa_dfa_match_len(dfa, start, str, strlen(str));
353}
354

Archive Download this file



interactive