Root/
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 | */ |
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 | |
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 | */ |
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 | |
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 | */ |
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 | |
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 | */ |
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 | |
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 | */ |
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 | |
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 | */ |
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 | |
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 | */ |
349 | unsigned 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 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9