← Back to branch summary

~apparmor-dev/apparmor/2.11

« back to all changes in this revision

Viewing changes to parser/libapparmor_re/expr-tree.cc

  • Committer: John Johansen
  • Date: 2015-10-13 22:39:17 UTC
  • Revision ID: john.johansen@canonical.com-20151013223917-wjak000uyb3icb8f
Add LSS presentations about apparmor security model

Show diffs side-by-side

added added

removed removed

Lines of Context:
parser/libapparmor_re/expr-tree.cc
232
232
                } else if (dynamic_cast<AltNode *>(child[dir])) {
233
233
                        // (a | b) | c -> a | (b | c)
234
234
                        rotate_node(this, dir);
235
 
                } else if (dynamic_cast<CharSetNode *>(child[dir]) &&
236
 
                           dynamic_cast<CharNode *>(child[!dir])) {
237
 
                        // [a] | b  ->  b | [a]
238
 
                        Node *c = child[dir];
239
 
                        child[dir] = child[!dir];
240
 
                        child[!dir] = c;
241
235
                } else {
242
236
                        break;
243
237
                }
252
246
//charset conversion is disabled for now,
253
247
//it hinders tree optimization in some cases, so it need to be either
254
248
//done post optimization, or have extra factoring rules added
255
 
#if 0
256
249
static Node *merge_charset(Node *a, Node *b)
257
250
{
258
 
        if (dynamic_cast<CharNode *>(a) && dynamic_cast<CharNode *>(b)) {
259
 
                Chars chars;
260
 
                chars.insert(dynamic_cast<CharNode *>(a)->c);
261
 
                chars.insert(dynamic_cast<CharNode *>(b)->c);
262
 
                CharSetNode *n = new CharSetNode(chars);
263
 
                return n;
264
 
        } else if (dynamic_cast<CharNode *>(a) &&
265
 
                   dynamic_cast<CharSetNode *>(b)) {
266
 
                Chars *chars = &dynamic_cast<CharSetNode *>(b)->chars;
267
 
                chars->insert(dynamic_cast<CharNode *>(a)->c);
268
 
                return b;
269
 
        } else if (dynamic_cast<CharSetNode *>(a) &&
270
 
                   dynamic_cast<CharSetNode *>(b)) {
271
 
                Chars *from = &dynamic_cast<CharSetNode *>(a)->chars;
272
 
                Chars *to = &dynamic_cast<CharSetNode *>(b)->chars;
273
 
                for (Chars::iterator i = from->begin(); i != from->end(); i++)
274
 
                        to->insert(*i);
275
 
                return b;
276
 
        }
277
 
        //return ???;
 
251
        Chars *from = &dynamic_cast<CharSetNode *>(b)->chars;
 
252
        Chars *to = &dynamic_cast<CharSetNode *>(a)->chars;
 
253
        for (Chars::iterator i = from->begin(); i != from->end(); i++)
 
254
                to->insert(*i);
 
255
        b->release();
 
256
        return a;
278
257
}
279
258
 
280
 
static Node *alt_to_charsets(Node *t, int dir)
281
 
{
282
 
/*
283
 
        Node *first = NULL;
284
 
        Node *p = t;
285
 
        Node *i = t;
286
 
        for (;dynamic_cast<AltNode *>(i);) {
287
 
                if (dynamic_cast<CharNode *>(i->child[dir]) ||
288
 
                    dynamic_cast<CharNodeSet *>(i->child[dir])) {
289
 
                        if (!first) {
290
 
                                first = i;
291
 
                                p = i;
292
 
                                i = i->child[!dir];
293
 
                        } else {
294
 
                                first->child[dir] = merge_charset(first->child[dir],
295
 
                                                      i->child[dir]);
296
 
                                p->child[!dir] = i->child[!dir];
297
 
                                Node *tmp = i;
298
 
                                i = tmp->child[!dir];
299
 
                                tmp->child[!dir] = NULL;
300
 
                                tmp->release();
301
 
                        }
302
 
                } else {
303
 
                        p = i;
304
 
                        i = i->child[!dir];
 
259
/* given a constructed alt vector do duplicate elimination and merging */
 
260
eliminate_dups_and_merge(vector<Node *> vec) {
 
261
        std::sort(vec->begin(), vec->end(), ???);
 
262
 
 
263
        i = vec->begin();
 
264
        if (vec->begin()->is_charset()) {
 
265
                for (j = i+1; *j->is_charset() && j != vec->end();
 
266
                     j++) {
 
267
                        merge_charset(*i, *j);
 
268
                        *j = NULL;
 
269
                        merge_count++;
305
270
                }
306
 
        }
307
 
        // last altnode of chain check other dir as well
308
 
        if (first && (dynamic_cast<charNode *>(i) ||
309
 
                      dynamic_cast<charNodeSet *>(i))) {
310
 
                
311
 
        }
312
 
*/
313
 
 
314
 
/*
315
 
                if (dynamic_cast<CharNode *>(t->child[dir]) ||
316
 
                    dynamic_cast<CharSetNode *>(t->child[dir]))
317
 
                    char_test = true;
318
 
                            (char_test &&
319
 
                             (dynamic_cast<CharNode *>(i->child[dir]) ||
320
 
                              dynamic_cast<CharSetNode *>(i->child[dir])))) {
321
 
*/
322
 
        return t;
323
 
}
324
 
#endif
 
271
                if (j != vec->end())
 
272
                        i = j;
 
273
        }
 
274
 
 
275
        /* merged charsets, now eliminate other dups */
 
276
        for (j = i + 1; ??; ???) {
 
277
 
 
278
        }
 
279
}
 
280
 
 
281
flatten_altnode(Node *t) {
 
282
        
 
283
        /* flatten tree */
 
284
        elimintated_alt_nodes++;
 
285
 
 
286
        eliminate_dups_and_merge();
 
287
}
 
288
 
 
289
flatten_catnode(Node *t) {
 
290
 
 
291
        /* flatten tree */
 
292
        eliminated_cat_nodes++;
 
293
 
 
294
        /* only elimination to be done is accept nodes */
 
295
}
 
296
 
 
297
factor() {
 
298
 
 
299
        factor everything from right, then left
 
300
 
 
301
        factor longest/most - look at both left and right, which is most?
 
302
          to determine which dir to factor first
 
303
 
 
304
        ab | abc | abcd | abcde
 
305
 
 
306
        a (b | bc | bcd | bcde)
 
307
 
 
308
        a ( b (E | c | cd | cde))
 
309
 
 
310
        a ( b (E | c (E | d | de))
 
311
 
 
312
        a ( b (E | c (E | d (E | e))))
 
313
 
 
314
        so once flattened, work top to bottom
 
315
 
 
316
        may actually want to flatten charsets into single chars in altnode
 
317
        to make it easier to factor them
 
318
 
 
319
}
325
320
 
326
321
static Node *basic_alt_factor(Node *t, int dir)
327
322
{
335
330
                t->release();
336
331
                return tmp;
337
332
        }
 
333
        if (dynamic_cast<CharSetNode *>(t->child[dir]) &&
 
334
            dynamic_cast<CharSetNode *>(t->child[!dir])) {
 
335
                Node *res = merge_charset(t->child[dir], t->child[!dir]);
 
336
                t->child[dir] = t->child[!dir] = NULL;
 
337
                t->release();
 
338
                return res;
 
339
        }
338
340
        // (ab) | (ac) -> a(b|c)
339
341
        if (dynamic_cast<CatNode *>(t->child[dir]) &&
340
342
            dynamic_cast<CatNode *>(t->child[!dir]) &&
534
536
        } else if (dynamic_cast<StarNode *>(t)) {
535
537
                counts->star++;
536
538
                count_tree_nodes(t->child[0], counts);
537
 
        } else if (dynamic_cast<CharNode *>(t)) {
538
 
                counts->charnode++;
539
539
        } else if (dynamic_cast<AnyCharNode *>(t)) {
540
540
                counts->any++;
541
541
        } else if (dynamic_cast<CharSetNode *>(t)) {
554
554
        bool update;
555
555
 
556
556
        if (flags & DFA_DUMP_TREE_STATS) {
557
 
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
557
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0 };
558
558
                count_tree_nodes(t, &counts);
559
559
                fprintf(stderr,
560
 
                        "expr tree: c %d, [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n",
561
 
                        counts.charnode, counts.charset, counts.notcharset,
 
560
                        "expr tree: [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n",
 
561
                        counts.charset, counts.notcharset,
562
562
                        counts.alt, counts.plus, counts.star, counts.any,
563
563
                        counts.cat);
564
564
        }
590
590
                }
591
591
        } while (update);
592
592
        if (flags & DFA_DUMP_TREE_STATS) {
593
 
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0, 0 };
 
593
                struct node_counts counts = { 0, 0, 0, 0, 0, 0, 0 };
594
594
                count_tree_nodes(t, &counts);
595
595
                fprintf(stderr,
596
 
                        "simplified expr tree: c %d, [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n",
597
 
                        counts.charnode, counts.charset, counts.notcharset,
 
596
                        "simplified expr tree: [] %d, [^] %d, | %d, + %d, * %d, . %d, cat %d\n",
 
597
                        counts.charset, counts.notcharset,
598
598
                        counts.alt, counts.plus, counts.star, counts.any,
599
599
                        counts.cat);
600
600
        }