GNU Linux-libre 4.14.324-gnu1
[releases.git] / 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-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/lib.h"
24 #include "include/match.h"
25
26 #define base_idx(X) ((X) & 0xffffff)
27
28 static char nulldfa_src[] = {
29         #include "nulldfa.in"
30 };
31 struct aa_dfa *nulldfa;
32
33 int aa_setup_dfa_engine(void)
34 {
35         int error;
36
37         nulldfa = aa_dfa_unpack(nulldfa_src, sizeof(nulldfa_src),
38                                 TO_ACCEPT1_FLAG(YYTD_DATA32) |
39                                 TO_ACCEPT2_FLAG(YYTD_DATA32));
40         if (!IS_ERR(nulldfa))
41                 return 0;
42
43         error = PTR_ERR(nulldfa);
44         nulldfa = NULL;
45
46         return error;
47 }
48
49 void aa_teardown_dfa_engine(void)
50 {
51         aa_put_dfa(nulldfa);
52         nulldfa = NULL;
53 }
54
55 /**
56  * unpack_table - unpack a dfa table (one of accept, default, base, next check)
57  * @blob: data to unpack (NOT NULL)
58  * @bsize: size of blob
59  *
60  * Returns: pointer to table else NULL on failure
61  *
62  * NOTE: must be freed by kvfree (not kfree)
63  */
64 static struct table_header *unpack_table(char *blob, size_t bsize)
65 {
66         struct table_header *table = NULL;
67         struct table_header th;
68         size_t tsize;
69
70         if (bsize < sizeof(struct table_header))
71                 goto out;
72
73         /* loaded td_id's start at 1, subtract 1 now to avoid doing
74          * it every time we use td_id as an index
75          */
76         th.td_id = be16_to_cpu(*(__be16 *) (blob)) - 1;
77         if (th.td_id > YYTD_ID_MAX)
78                 goto out;
79         th.td_flags = be16_to_cpu(*(__be16 *) (blob + 2));
80         th.td_lolen = be32_to_cpu(*(__be32 *) (blob + 8));
81         blob += sizeof(struct table_header);
82
83         if (!(th.td_flags == YYTD_DATA16 || th.td_flags == YYTD_DATA32 ||
84               th.td_flags == YYTD_DATA8))
85                 goto out;
86
87         tsize = table_size(th.td_lolen, th.td_flags);
88         if (bsize < tsize)
89                 goto out;
90
91         table = kvzalloc(tsize, GFP_KERNEL);
92         if (table) {
93                 table->td_id = th.td_id;
94                 table->td_flags = th.td_flags;
95                 table->td_lolen = th.td_lolen;
96                 if (th.td_flags == YYTD_DATA8)
97                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
98                                      u8, u8, byte_to_byte);
99                 else if (th.td_flags == YYTD_DATA16)
100                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
101                                      u16, __be16, be16_to_cpu);
102                 else if (th.td_flags == YYTD_DATA32)
103                         UNPACK_ARRAY(table->td_data, blob, th.td_lolen,
104                                      u32, __be32, be32_to_cpu);
105                 else
106                         goto fail;
107                 /* if table was vmalloced make sure the page tables are synced
108                  * before it is used, as it goes live to all cpus.
109                  */
110                 if (is_vmalloc_addr(table))
111                         vm_unmap_aliases();
112         }
113
114 out:
115         return table;
116 fail:
117         kvfree(table);
118         return NULL;
119 }
120
121 /**
122  * verify_dfa - verify that transitions and states in the tables are in bounds.
123  * @dfa: dfa to test  (NOT NULL)
124  * @flags: flags controlling what type of accept table are acceptable
125  *
126  * Assumes dfa has gone through the first pass verification done by unpacking
127  * NOTE: this does not valid accept table values
128  *
129  * Returns: %0 else error code on failure to verify
130  */
131 static int verify_dfa(struct aa_dfa *dfa, int flags)
132 {
133         size_t i, state_count, trans_count;
134         int error = -EPROTO;
135
136         /* check that required tables exist */
137         if (!(dfa->tables[YYTD_ID_DEF] &&
138               dfa->tables[YYTD_ID_BASE] &&
139               dfa->tables[YYTD_ID_NXT] && dfa->tables[YYTD_ID_CHK]))
140                 goto out;
141
142         /* accept.size == default.size == base.size */
143         state_count = dfa->tables[YYTD_ID_BASE]->td_lolen;
144         if (ACCEPT1_FLAGS(flags)) {
145                 if (!dfa->tables[YYTD_ID_ACCEPT])
146                         goto out;
147                 if (state_count != dfa->tables[YYTD_ID_ACCEPT]->td_lolen)
148                         goto out;
149         }
150         if (ACCEPT2_FLAGS(flags)) {
151                 if (!dfa->tables[YYTD_ID_ACCEPT2])
152                         goto out;
153                 if (state_count != dfa->tables[YYTD_ID_ACCEPT2]->td_lolen)
154                         goto out;
155         }
156         if (state_count != dfa->tables[YYTD_ID_DEF]->td_lolen)
157                 goto out;
158
159         /* next.size == chk.size */
160         trans_count = dfa->tables[YYTD_ID_NXT]->td_lolen;
161         if (trans_count != dfa->tables[YYTD_ID_CHK]->td_lolen)
162                 goto out;
163
164         /* if equivalence classes then its table size must be 256 */
165         if (dfa->tables[YYTD_ID_EC] &&
166             dfa->tables[YYTD_ID_EC]->td_lolen != 256)
167                 goto out;
168
169         if (flags & DFA_FLAG_VERIFY_STATES) {
170                 for (i = 0; i < state_count; i++) {
171                         if (DEFAULT_TABLE(dfa)[i] >= state_count)
172                                 goto out;
173                         if (base_idx(BASE_TABLE(dfa)[i]) + 255 >= trans_count) {
174                                 printk(KERN_ERR "AppArmor DFA next/check upper "
175                                        "bounds error\n");
176                                 goto out;
177                         }
178                 }
179
180                 for (i = 0; i < trans_count; i++) {
181                         if (NEXT_TABLE(dfa)[i] >= state_count)
182                                 goto out;
183                         if (CHECK_TABLE(dfa)[i] >= state_count)
184                                 goto out;
185                 }
186         }
187
188         error = 0;
189 out:
190         return error;
191 }
192
193 /**
194  * dfa_free - free a dfa allocated by aa_dfa_unpack
195  * @dfa: the dfa to free  (MAYBE NULL)
196  *
197  * Requires: reference count to dfa == 0
198  */
199 static void dfa_free(struct aa_dfa *dfa)
200 {
201         if (dfa) {
202                 int i;
203
204                 for (i = 0; i < ARRAY_SIZE(dfa->tables); i++) {
205                         kvfree(dfa->tables[i]);
206                         dfa->tables[i] = NULL;
207                 }
208                 kfree(dfa);
209         }
210 }
211
212 /**
213  * aa_dfa_free_kref - free aa_dfa by kref (called by aa_put_dfa)
214  * @kr: kref callback for freeing of a dfa  (NOT NULL)
215  */
216 void aa_dfa_free_kref(struct kref *kref)
217 {
218         struct aa_dfa *dfa = container_of(kref, struct aa_dfa, count);
219         dfa_free(dfa);
220 }
221
222 /**
223  * aa_dfa_unpack - unpack the binary tables of a serialized dfa
224  * @blob: aligned serialized stream of data to unpack  (NOT NULL)
225  * @size: size of data to unpack
226  * @flags: flags controlling what type of accept tables are acceptable
227  *
228  * Unpack a dfa that has been serialized.  To find information on the dfa
229  * format look in Documentation/admin-guide/LSM/apparmor.rst
230  * Assumes the dfa @blob stream has been aligned on a 8 byte boundary
231  *
232  * Returns: an unpacked dfa ready for matching or ERR_PTR on failure
233  */
234 struct aa_dfa *aa_dfa_unpack(void *blob, size_t size, int flags)
235 {
236         int hsize;
237         int error = -ENOMEM;
238         char *data = blob;
239         struct table_header *table = NULL;
240         struct aa_dfa *dfa = kzalloc(sizeof(struct aa_dfa), GFP_KERNEL);
241         if (!dfa)
242                 goto fail;
243
244         kref_init(&dfa->count);
245
246         error = -EPROTO;
247
248         /* get dfa table set header */
249         if (size < sizeof(struct table_set_header))
250                 goto fail;
251
252         if (ntohl(*(__be32 *) data) != YYTH_MAGIC)
253                 goto fail;
254
255         hsize = ntohl(*(__be32 *) (data + 4));
256         if (size < hsize)
257                 goto fail;
258
259         dfa->flags = ntohs(*(__be16 *) (data + 12));
260         data += hsize;
261         size -= hsize;
262
263         while (size > 0) {
264                 table = unpack_table(data, size);
265                 if (!table)
266                         goto fail;
267
268                 switch (table->td_id) {
269                 case YYTD_ID_ACCEPT:
270                         if (!(table->td_flags & ACCEPT1_FLAGS(flags)))
271                                 goto fail;
272                         break;
273                 case YYTD_ID_ACCEPT2:
274                         if (!(table->td_flags & ACCEPT2_FLAGS(flags)))
275                                 goto fail;
276                         break;
277                 case YYTD_ID_BASE:
278                         if (table->td_flags != YYTD_DATA32)
279                                 goto fail;
280                         break;
281                 case YYTD_ID_DEF:
282                 case YYTD_ID_NXT:
283                 case YYTD_ID_CHK:
284                         if (table->td_flags != YYTD_DATA16)
285                                 goto fail;
286                         break;
287                 case YYTD_ID_EC:
288                         if (table->td_flags != YYTD_DATA8)
289                                 goto fail;
290                         break;
291                 default:
292                         goto fail;
293                 }
294                 /* check for duplicate table entry */
295                 if (dfa->tables[table->td_id])
296                         goto fail;
297                 dfa->tables[table->td_id] = table;
298                 data += table_size(table->td_lolen, table->td_flags);
299                 size -= table_size(table->td_lolen, table->td_flags);
300                 table = NULL;
301         }
302
303         error = verify_dfa(dfa, flags);
304         if (error)
305                 goto fail;
306
307         return dfa;
308
309 fail:
310         kvfree(table);
311         dfa_free(dfa);
312         return ERR_PTR(error);
313 }
314
315 /**
316  * aa_dfa_match_len - traverse @dfa to find state @str stops at
317  * @dfa: the dfa to match @str against  (NOT NULL)
318  * @start: the state of the dfa to start matching in
319  * @str: the string of bytes to match against the dfa  (NOT NULL)
320  * @len: length of the string of bytes to match
321  *
322  * aa_dfa_match_len will match @str against the dfa and return the state it
323  * finished matching in. The final state can be used to look up the accepting
324  * label, or as the start state of a continuing match.
325  *
326  * This function will happily match again the 0 byte and only finishes
327  * when @len input is consumed.
328  *
329  * Returns: final state reached after input is consumed
330  */
331 unsigned int aa_dfa_match_len(struct aa_dfa *dfa, unsigned int start,
332                               const char *str, int len)
333 {
334         u16 *def = DEFAULT_TABLE(dfa);
335         u32 *base = BASE_TABLE(dfa);
336         u16 *next = NEXT_TABLE(dfa);
337         u16 *check = CHECK_TABLE(dfa);
338         unsigned int state = start, pos;
339
340         if (state == 0)
341                 return 0;
342
343         /* current state is <state>, matching character *str */
344         if (dfa->tables[YYTD_ID_EC]) {
345                 /* Equivalence class table defined */
346                 u8 *equiv = EQUIV_TABLE(dfa);
347                 /* default is direct to next state */
348                 for (; len; len--) {
349                         pos = base_idx(base[state]) + equiv[(u8) *str++];
350                         if (check[pos] == state)
351                                 state = next[pos];
352                         else
353                                 state = def[state];
354                 }
355         } else {
356                 /* default is direct to next state */
357                 for (; len; len--) {
358                         pos = base_idx(base[state]) + (u8) *str++;
359                         if (check[pos] == state)
360                                 state = next[pos];
361                         else
362                                 state = def[state];
363                 }
364         }
365
366         return state;
367 }
368
369 /**
370  * aa_dfa_match - traverse @dfa to find state @str stops at
371  * @dfa: the dfa to match @str against  (NOT NULL)
372  * @start: the state of the dfa to start matching in
373  * @str: the null terminated string of bytes to match against the dfa (NOT NULL)
374  *
375  * aa_dfa_match will match @str against the dfa and return the state it
376  * finished matching in. The final state can be used to look up the accepting
377  * label, or as the start state of a continuing match.
378  *
379  * Returns: final state reached after input is consumed
380  */
381 unsigned int aa_dfa_match(struct aa_dfa *dfa, unsigned int start,
382                           const char *str)
383 {
384         u16 *def = DEFAULT_TABLE(dfa);
385         u32 *base = BASE_TABLE(dfa);
386         u16 *next = NEXT_TABLE(dfa);
387         u16 *check = CHECK_TABLE(dfa);
388         unsigned int state = start, pos;
389
390         if (state == 0)
391                 return 0;
392
393         /* current state is <state>, matching character *str */
394         if (dfa->tables[YYTD_ID_EC]) {
395                 /* Equivalence class table defined */
396                 u8 *equiv = EQUIV_TABLE(dfa);
397                 /* default is direct to next state */
398                 while (*str) {
399                         pos = base_idx(base[state]) + equiv[(u8) *str++];
400                         if (check[pos] == state)
401                                 state = next[pos];
402                         else
403                                 state = def[state];
404                 }
405         } else {
406                 /* default is direct to next state */
407                 while (*str) {
408                         pos = base_idx(base[state]) + (u8) *str++;
409                         if (check[pos] == state)
410                                 state = next[pos];
411                         else
412                                 state = def[state];
413                 }
414         }
415
416         return state;
417 }
418
419 /**
420  * aa_dfa_next - step one character to the next state in the dfa
421  * @dfa: the dfa to tranverse (NOT NULL)
422  * @state: the state to start in
423  * @c: the input character to transition on
424  *
425  * aa_dfa_match will step through the dfa by one input character @c
426  *
427  * Returns: state reach after input @c
428  */
429 unsigned int aa_dfa_next(struct aa_dfa *dfa, unsigned int state,
430                           const char c)
431 {
432         u16 *def = DEFAULT_TABLE(dfa);
433         u32 *base = BASE_TABLE(dfa);
434         u16 *next = NEXT_TABLE(dfa);
435         u16 *check = CHECK_TABLE(dfa);
436         unsigned int pos;
437
438         /* current state is <state>, matching character *str */
439         if (dfa->tables[YYTD_ID_EC]) {
440                 /* Equivalence class table defined */
441                 u8 *equiv = EQUIV_TABLE(dfa);
442                 /* default is direct to next state */
443
444                 pos = base_idx(base[state]) + equiv[(u8) c];
445                 if (check[pos] == state)
446                         state = next[pos];
447                 else
448                         state = def[state];
449         } else {
450                 /* default is direct to next state */
451                 pos = base_idx(base[state]) + (u8) c;
452                 if (check[pos] == state)
453                         state = next[pos];
454                 else
455                         state = def[state];
456         }
457
458         return state;
459 }