Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
match.c
Go to the documentation of this file.
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 
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  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 
76 out:
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;
83 fail:
84  kvfree(table);
85  return NULL;
86 }
87 
98 static 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;
157 out:
158  return error;
159 }
160 
167 static 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 
184 void 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 
202 struct 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 
277 fail:
278  kvfree(table);
279  dfa_free(dfa);
280  return ERR_PTR(error);
281 }
282 
299 unsigned 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 
349 unsigned 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 
397 unsigned 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 }
Generated on Thu Jan 10 2013 13:20:28 for Linux Kernel by   doxygen 1.8.2