« back to all changes in this revision
Viewing changes to conditional.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Russell Coker
- Date: 2004-05-20 04:32:00 UTC
- Revision ID: james.westby@ubuntu.com-20040520043200-w4lzkx37dmmc3wt9
Tags: upstream-1.10
Import upstream version 1.10
- files added:
- include
- test
added
removed
conditional.c
1
/* Authors: Karl MacMillan <kmacmillan@tresys.com>
2
* Frank Mayer <mayerf@tresys.com>
3
* David Caplan <dac@tresys.com>
4
*
5
* Copyright (C) 2003 - 2004 Tresys Technology, LLC
6
* This program is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation, version 2.
9
*/
10
11
#include "include/security.h"
12
#include "conditional.h"
13
14
15
/* move all type rules to top of t/f lists to help kernel on evaluation */
16
static void cond_optimize(cond_av_list_t **l) {
17
cond_av_list_t *top, *p,*cur;
18
19
top = p = cur = *l;
20
21
while(cur) {
22
if ((cur->node->datum.specified & AVTAB_TYPE) && (top != cur)) {
23
p->next = cur->next;
24
cur->next = top;
25
top = cur;
26
cur = p->next;
27
} else {
28
p = cur;
29
cur = cur->next;
30
}
31
}
32
*l = top;
33
}
34
35
/* reorder t/f lists for kernel */
36
void cond_optimize_lists(cond_list_t* cl) {
37
cond_list_t *n;
38
39
for (n = cl; n != NULL; n = n->next) {
40
cond_optimize(&n->true_list);
41
cond_optimize(&n->false_list);
42
}
43
}
44
45
46
static int bool_present(int target, int bools[], int num_bools) {
47
int i = 0;
48
int ret = 1;
49
50
if (num_bools > COND_MAX_BOOLS) {
51
return 0;
52
}
53
while( i < num_bools && target != bools[i]) i++;
54
if (i == num_bools) ret = 0; /* got to end w/o match */
55
return ret;
56
}
57
58
static int same_bools(cond_node_t *a, cond_node_t *b) {
59
int i, x;
60
61
x = a->nbools;
62
63
/* same number of bools? */
64
if (x != b->nbools) return 0;
65
66
/* make sure all the bools in a are also in b */
67
for(i = 0; i < x; i++) if (!bool_present(a->bool_ids[i], b->bool_ids, x)) return 0;
68
return 1;
69
}
70
71
/*
72
* Determine if two conditional expressions are equal.
73
*/
74
static int cond_expr_equal(cond_node_t *a, cond_node_t *b)
75
{
76
cond_expr_t *cur_a, *cur_b;
77
78
if (a == NULL || b == NULL)
79
return 0;
80
81
if(a->nbools != b->nbools) return 0;
82
83
/* if exprs have <= COND_MAX_BOOLS we can check the precompute values
84
* for the expressions.
85
*/
86
if (a->nbools <= COND_MAX_BOOLS && b->nbools <= COND_MAX_BOOLS)
87
{
88
if(!same_bools(a,b)) return 0;
89
return (a->expr_pre_comp == b->expr_pre_comp);
90
}
91
92
/* for long expressions we check for exactly the same expression */
93
cur_a = a->expr;
94
cur_b = b->expr;
95
while (1) {
96
if (cur_a == NULL && cur_b == NULL)
97
return 1;
98
else if (cur_a == NULL || cur_b == NULL)
99
return 0;
100
if (cur_a->expr_type != cur_b->expr_type)
101
return 0;
102
if (cur_a->expr_type == COND_BOOL) {
103
if (cur_a->bool != cur_b->bool)
104
return 0;
105
}
106
cur_a = cur_a->next;
107
cur_b = cur_b->next;
108
}
109
return 1;
110
}
111
112
/* return either a pre-existing matching node or create a new node */
113
cond_node_t *cond_node_search(policydb_t *p, cond_node_t *cn)
114
{
115
cond_node_t *list,*new;
116
int i;
117
118
list = p->cond_list;
119
120
while(list) {
121
if (cond_expr_equal(cn,list)) break;
122
list = list->next;
123
}
124
if (list) return list;
125
else {
126
new = (cond_node_t *)malloc(sizeof (cond_node_t));
127
if (!new) {
128
return NULL;
129
}
130
new->expr = cn->expr;
131
new->cur_state = cond_evaluate_expr(p, new->expr);
132
new->nbools = cn->nbools;
133
for (i = 0; i < cn->nbools; i++)
134
new->bool_ids[i] = cn->bool_ids[i];
135
new->expr_pre_comp = cn->expr_pre_comp;
136
new->true_list = NULL;
137
new->false_list = NULL;
138
/* add conditional node to policy list */
139
new->next = p->cond_list;
140
p->cond_list = new;
141
return new;
142
}
143
}
144
145
/*
146
* cond_evaluate_expr evaluates a conditional expr
147
* in reverse polish notation. It returns true (1), false (0),
148
* or undefined (-1). Undefined occurs when the expression
149
* exceeds the stack depth of COND_EXPR_MAXDEPTH.
150
*/
151
int cond_evaluate_expr(policydb_t *p, cond_expr_t *expr)
152
{
153
154
cond_expr_t *cur;
155
int s[COND_EXPR_MAXDEPTH];
156
int sp = -1;
157
158
for (cur = expr; cur != NULL; cur = cur->next) {
159
switch (cur->expr_type) {
160
case COND_BOOL:
161
if (sp == (COND_EXPR_MAXDEPTH - 1))
162
return -1;
163
sp++;
164
s[sp] = p->bool_val_to_struct[cur->bool - 1]->state;
165
break;
166
case COND_NOT:
167
if (sp < 0)
168
return -1;
169
s[sp] = !s[sp];
170
break;
171
case COND_OR:
172
if (sp < 1)
173
return -1;
174
sp--;
175
s[sp] |= s[sp + 1];
176
break;
177
case COND_AND:
178
if (sp < 1)
179
return -1;
180
sp--;
181
s[sp] &= s[sp + 1];
182
break;
183
case COND_XOR:
184
if (sp < 1)
185
return -1;
186
sp--;
187
s[sp] ^= s[sp + 1];
188
break;
189
case COND_EQ:
190
if (sp < 1)
191
return -1;
192
sp--;
193
s[sp] = (s[sp] == s[sp + 1]);
194
break;
195
case COND_NEQ:
196
if (sp < 1)
197
return -1;
198
sp--;
199
s[sp] = (s[sp] != s[sp + 1]);
200
break;
201
default:
202
return -1;
203
}
204
}
205
return s[0];
206
}
207
208
/*
209
* evaluate_cond_node evaluates the conditional stored in
210
* a cond_node_t and if the result is different than the
211
* current state of the node it sets the rules in the true/false
212
* list appropriately. If the result of the expression is undefined
213
* all of the rules are disabled for safety.
214
*/
215
static int evaluate_cond_node(policydb_t *p, cond_node_t *node)
216
{
217
int new_state;
218
cond_av_list_t* cur;
219
220
new_state = cond_evaluate_expr(p, node->expr);
221
if (new_state != node->cur_state) {
222
node->cur_state = new_state;
223
if (new_state == -1)
224
printk("expression result was undefined - disabling all rules.\n");
225
/* turn the rules on or off */
226
for (cur = node->true_list; cur != NULL; cur = cur->next) {
227
if (new_state <= 0) {
228
cur->node->datum.specified &= ~AVTAB_ENABLED;
229
} else {
230
cur->node->datum.specified |= AVTAB_ENABLED;
231
}
232
}
233
234
for (cur = node->false_list; cur != NULL; cur = cur->next) {
235
/* -1 or 1 */
236
if (new_state) {
237
cur->node->datum.specified &= ~AVTAB_ENABLED;
238
} else {
239
cur->node->datum.specified |= AVTAB_ENABLED;
240
}
241
}
242
}
243
return 0;
244
}
245
246
/* precompute and simplify an expression if possible. If left with !expression, change
247
* to expression and switch t and f. precompute expression for expressions with limited
248
* number of bools.
249
*/
250
int normalize_expr(policydb_t *p, cond_node_t *cn)
251
{
252
cond_expr_t *ne,*e;
253
cond_av_list_t *tmp;
254
int i, j, k, orig_value[COND_MAX_BOOLS];
255
__u32 test = 0x0;
256
257
258
cn->nbools = 0;
259
260
memset(cn->bool_ids, 0,sizeof(cn->bool_ids) );
261
cn->expr_pre_comp = 0x0;
262
263
/* take care of !expr case */
264
ne = NULL;
265
e = cn->expr;
266
267
/* becuase it's RPN look at last element */
268
while(e->next != NULL) {
269
ne = e; e = e->next;
270
}
271
if (e->expr_type == COND_NOT) {
272
if (ne) {
273
ne->next = NULL;
274
} else { /* ne should never be NULL */
275
printk("Found expr with no bools and only a ! - this should never happen.\n");
276
return -1;
277
}
278
/* swap the true and false lists */
279
tmp = cn->true_list;
280
cn->true_list = cn->false_list;
281
cn->false_list = tmp;
282
/* free the "not" node in the list */
283
free(e);
284
}
285
286
/* find all the bools in the expression */
287
for(e = cn->expr; e != NULL; e = e->next) {
288
switch(e->expr_type) {
289
case COND_BOOL:
290
i = 0;
291
/* see if we've already seen this bool */
292
if (!bool_present(e->bool, cn->bool_ids, cn->nbools)) {
293
/* count em all but only record up to COND_MAX_BOOLS */
294
if (cn->nbools < COND_MAX_BOOLS)
295
cn->bool_ids[cn->nbools++] = e->bool;
296
else
297
cn->nbools++;
298
}
299
break;
300
default:
301
break;
302
}
303
}
304
305
/* only precompute for exprs with <= COND_AX_BOOLS */
306
if (cn->nbools <= COND_MAX_BOOLS) {
307
/* save the default values for the bools so we can play with them */
308
for(i = 0; i < cn->nbools; i++) {
309
orig_value[i] = p->bool_val_to_struct[cn->bool_ids[i] - 1]->state;
310
}
311
312
/* loop through all possible combinations of values for bools in expression */
313
for(test = 0x0; test < (0x1 << cn->nbools) ; test++) {
314
/* temporarily set the value for all the bools in the
315
* expression using the corr. bit in test */
316
for(j = 0; j < cn->nbools; j++) {
317
p->bool_val_to_struct[cn->bool_ids[j] - 1]->state =
318
( test & (0x1 << j) ) ? 1 : 0;
319
}
320
k = cond_evaluate_expr(p, cn->expr);
321
if (k == -1) {
322
printk("While testing expression, expression result "
323
"was undefined - this should never happen.\n");
324
return -1;
325
}
326
/* set the bit if expression evaluates true */
327
if (k) cn->expr_pre_comp |= 0x1 << test;
328
}
329
330
/* restore bool default values */
331
for(i = 0; i < cn->nbools; i++)
332
p->bool_val_to_struct[cn->bool_ids[i] - 1]->state = orig_value[i] ;
333
}
334
return 0;
335
}
336
337
int evaluate_conds(policydb_t *p)
338
{
339
int ret;
340
cond_node_t *cur;
341
342
for (cur = p->cond_list; cur != NULL; cur = cur->next) {
343
ret = evaluate_cond_node(p, cur);
344
if (ret)
345
return ret;
346
}
347
return 0;
348
}
349
350
int cond_policydb_init(policydb_t *p)
351
{
352
p->bool_val_to_struct = NULL;
353
p->cond_list = NULL;
354
if (avtab_init(&p->te_cond_avtab))
355
return -1;
356
357
return 0;
358
}
359
360
static void cond_av_list_destroy(cond_av_list_t *list)
361
{
362
cond_av_list_t *cur, *next;
363
for (cur = list; cur != NULL; cur = next) {
364
next = cur->next;
365
/* the avtab_ptr_t node is destroy by the avtab */
366
kfree(cur);
367
}
368
}
369
370
static void cond_node_destroy(cond_node_t *node)
371
{
372
cond_expr_t *cur_expr, *next_expr;
373
374
if (!node)
375
return;
376
377
for (cur_expr = node->expr; cur_expr != NULL; cur_expr = next_expr) {
378
next_expr = cur_expr->next;
379
kfree(cur_expr);
380
}
381
cond_av_list_destroy(node->true_list);
382
cond_av_list_destroy(node->false_list);
383
kfree(node);
384
}
385
386
static void cond_list_destroy(cond_list_t *list)
387
{
388
cond_node_t *next, *cur;
389
390
if (list == NULL)
391
return;
392
393
for (cur = list; cur != NULL; cur = next) {
394
next = cur->next;
395
cond_node_destroy(cur);
396
}
397
}
398
399
void cond_policydb_destroy(policydb_t *p)
400
{
401
if (p->bool_val_to_struct != NULL)
402
kfree(p->bool_val_to_struct);
403
avtab_destroy(&p->te_cond_avtab);
404
cond_list_destroy(p->cond_list);
405
}
406
407
int cond_init_bool_indexes(policydb_t *p)
408
{
409
if (p->bool_val_to_struct)
410
kfree(p->bool_val_to_struct);
411
p->bool_val_to_struct = (cond_bool_datum_t**)
412
kmalloc(p->p_bools.nprim * sizeof(cond_bool_datum_t*), GFP_KERNEL);
413
if (!p->bool_val_to_struct)
414
return -1;
415
return 0;
416
}
417
418
int cond_destroy_bool(hashtab_key_t key, hashtab_datum_t datum, void *p)
419
{
420
if (key)
421
kfree(key);
422
kfree(datum);
423
return 0;
424
}
425
426
int cond_index_bool(hashtab_key_t key, hashtab_datum_t datum, void *datap)
427
{
428
policydb_t *p;
429
cond_bool_datum_t *booldatum;
430
431
booldatum = datum;
432
p = datap;
433
434
if (!booldatum->value || booldatum->value > p->p_bools.nprim)
435
return -EINVAL;
436
437
p->p_bool_val_to_name[booldatum->value - 1] = key;
438
p->bool_val_to_struct[booldatum->value -1] = booldatum;
439
440
return 0;
441
}
442
443
int bool_isvalid(cond_bool_datum_t *b)
444
{
445
if (!(b->state == 0 || b->state == 1))
446
return 0;
447
return 1;
448
}
449
450
int cond_read_bool(policydb_t *p, hashtab_t h, struct policy_file *fp)
451
{
452
char *key = 0;
453
cond_bool_datum_t *booldatum;
454
__u32 *buf, len;
455
456
booldatum = kmalloc(sizeof(cond_bool_datum_t), GFP_KERNEL);
457
if (!booldatum)
458
return -1;
459
memset(booldatum, 0, sizeof(cond_bool_datum_t));
460
461
buf = next_entry(fp, sizeof(__u32) * 3);
462
if (!buf)
463
goto err;
464
465
booldatum->value = le32_to_cpu(buf[0]);
466
booldatum->state = le32_to_cpu(buf[1]);
467
468
if (!bool_isvalid(booldatum))
469
goto err;
470
471
len = le32_to_cpu(buf[2]);
472
473
buf = next_entry(fp, len);
474
if (!buf)
475
goto err;
476
key = kmalloc(len + 1, GFP_KERNEL);
477
if (!key)
478
goto err;
479
memcpy(key, buf, len);
480
key[len] = 0;
481
if (hashtab_insert(h, key, booldatum))
482
goto err;
483
484
return 0;
485
err:
486
cond_destroy_bool(key, booldatum, 0);
487
return -1;
488
}
489
490
static int cond_read_av_list(policydb_t *p, void *fp, cond_av_list_t **ret_list, cond_av_list_t *other)
491
{
492
cond_av_list_t *list, *last = NULL, *cur;
493
avtab_key_t key;
494
avtab_datum_t datum;
495
avtab_ptr_t node_ptr;
496
int len, i;
497
__u32 *buf;
498
__u8 found;
499
500
*ret_list = NULL;
501
502
len = 0;
503
buf = next_entry(fp, sizeof(__u32));
504
if (!buf)
505
return -1;
506
507
len = le32_to_cpu(buf[0]);
508
if (len == 0) {
509
return 0;
510
}
511
512
for (i = 0; i < len; i++) {
513
if (avtab_read_item(fp, &datum, &key))
514
goto err;
515
516
/*
517
* For type rules we have to make certain there aren't any
518
* conflicting rules by searching the te_avtab and the
519
* cond_te_avtab.
520
*/
521
if (datum.specified & AVTAB_TYPE) {
522
if (avtab_search(&p->te_avtab, &key, AVTAB_TYPE)) {
523
printk("security: type rule already exists outside of a conditional.");
524
goto err;
525
}
526
/*
527
* If we are reading the false list other will be a pointer to
528
* the true list. We can have duplicate entries if there is only
529
* 1 other entry and it is in our true list.
530
*
531
* If we are reading the true list (other == NULL) there shouldn't
532
* be any other entries.
533
*/
534
if (other) {
535
node_ptr = avtab_search_node(&p->te_cond_avtab, &key, AVTAB_TYPE);
536
if (node_ptr) {
537
if (avtab_search_node_next(node_ptr, AVTAB_TYPE)) {
538
printk("security: too many conflicting type rules.");
539
goto err;
540
}
541
found = 0;
542
for (cur = other; cur != NULL; cur = cur->next) {
543
if (cur->node == node_ptr) {
544
found = 1;
545
break;
546
}
547
}
548
if (!found) {
549
printk("security: conflicting type rules.\n");
550
goto err;
551
}
552
}
553
} else {
554
if (avtab_search(&p->te_cond_avtab, &key, AVTAB_TYPE)) {
555
printk("security: conflicting type rules when adding type rule for true.\n");
556
goto err;
557
}
558
}
559
}
560
node_ptr = avtab_insert_nonunique(&p->te_cond_avtab, &key, &datum);
561
if (!node_ptr) {
562
printk("security: could not insert rule.");
563
goto err;
564
}
565
566
list = kmalloc(sizeof(cond_av_list_t), GFP_KERNEL);
567
if (!list)
568
goto err;
569
memset(list, 0, sizeof(cond_av_list_t));
570
571
list->node = node_ptr;
572
if (i == 0)
573
*ret_list = list;
574
else
575
last->next = list;
576
last = list;
577
578
}
579
580
return 0;
581
err:
582
cond_av_list_destroy(*ret_list);
583
*ret_list = NULL;
584
return -1;
585
}
586
587
static int expr_isvalid(policydb_t *p, cond_expr_t *expr)
588
{
589
if (expr->expr_type <= 0 || expr->expr_type > COND_LAST) {
590
printk("security: conditional expressions uses unknown operator.\n");
591
return 0;
592
}
593
594
if (expr->bool > p->p_bools.nprim) {
595
printk("security: conditional expressions uses unknown bool.\n");
596
return 0;
597
}
598
return 1;
599
}
600
601
static int cond_read_node(policydb_t *p, cond_node_t *node, void *fp)
602
{
603
__u32 *buf;
604
int len, i;
605
cond_expr_t *expr = NULL, *last = NULL;
606
607
buf = next_entry(fp, sizeof(__u32));
608
if (!buf)
609
return -1;
610
611
node->cur_state = le32_to_cpu(buf[0]);
612
613
len = 0;
614
buf = next_entry(fp, sizeof(__u32));
615
if (!buf)
616
return -1;
617
618
/* expr */
619
len = le32_to_cpu(buf[0]);
620
621
for (i = 0; i < len; i++ ) {
622
buf = next_entry(fp, sizeof(__u32) * 2);
623
if (!buf)
624
goto err;
625
626
expr = kmalloc(sizeof(cond_expr_t), GFP_KERNEL);
627
if (!expr) {
628
goto err;
629
}
630
memset(expr, 0, sizeof(cond_expr_t));
631
632
expr->expr_type = le32_to_cpu(buf[0]);
633
expr->bool = le32_to_cpu(buf[1]);
634
635
if (!expr_isvalid(p, expr))
636
goto err;
637
638
if (i == 0) {
639
node->expr = expr;
640
} else {
641
last->next = expr;
642
}
643
last = expr;
644
}
645
646
if (cond_read_av_list(p, fp, &node->true_list, NULL) != 0)
647
goto err;
648
if (cond_read_av_list(p, fp, &node->false_list, node->true_list) != 0)
649
goto err;
650
return 0;
651
err:
652
cond_node_destroy(node);
653
return -1;
654
}
655
656
int cond_read_list(policydb_t *p, void *fp)
657
{
658
cond_node_t *node, *last = NULL;
659
__u32 *buf;
660
int i, len;
661
662
buf = next_entry(fp, sizeof(__u32));
663
if (!buf)
664
return -1;
665
666
len = le32_to_cpu(buf[0]);
667
668
for (i = 0; i < len; i++) {
669
node = kmalloc(sizeof(cond_node_t), GFP_KERNEL);
670
if (!node)
671
goto err;
672
memset(node, 0, sizeof(cond_node_t));
673
674
if (cond_read_node(p, node, fp) != 0)
675
goto err;
676
677
if (i == 0) {
678
p->cond_list = node;
679
} else {
680
last->next = node;
681
}
682
last = node;
683
}
684
return 0;
685
err:
686
return -1;
687
}
688
689
/* Determine whether additional permissions are granted by the conditional
690
* av table, and if so, add them to the result
691
*/
692
void cond_compute_av(avtab_t *ctab, avtab_key_t *key, struct av_decision *avd)
693
{
694
avtab_ptr_t node;
695
696
if(!ctab || !key || !avd)
697
return;
698
699
for(node = avtab_search_node(ctab, key, AVTAB_AV); node != NULL;
700
node = avtab_search_node_next(node, AVTAB_AV)) {
701
if ( (__u32) (AVTAB_ALLOWED|AVTAB_ENABLED) ==
702
(node->datum.specified & (AVTAB_ALLOWED|AVTAB_ENABLED)))
703
avd->allowed |= avtab_allowed(&node->datum);
704
if ( (__u32) (AVTAB_AUDITDENY|AVTAB_ENABLED) ==
705
(node->datum.specified & (AVTAB_AUDITDENY|AVTAB_ENABLED)))
706
/* Since a '0' in an auditdeny mask represents a
707
* permission we do NOT want to audit (dontaudit), we use
708
* the '&' operand to ensure that all '0's in the mask
709
* are retained (much unlike the allow and auditallow cases).
710
*/
711
avd->auditdeny &= avtab_auditdeny(&node->datum);
712
if ( (__u32) (AVTAB_AUDITALLOW|AVTAB_ENABLED) ==
713
(node->datum.specified & (AVTAB_AUDITALLOW|AVTAB_ENABLED)))
714
avd->auditallow |= avtab_auditallow(&node->datum);
715
}
716
return;
717
}
718
Loggerhead is a web-based interface for Breezy
Version: 2.0.1