~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/security/apparmor/match.c

Version: ~ [ linux-5.3 ] ~ [ linux-5.2.14 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.72 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.143 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.192 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.192 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.73 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp