xref: /openbmc/linux/security/apparmor/match.c (revision 3ca9760fdfa411f7e5db54b3437fbb858d2ec825)
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  }
433