← Back to branch summary

~ubuntu-branches/ubuntu/wily/apparmor/wily

« back to all changes in this revision

Viewing changes to parser/libapparmor_re/README

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2011-04-27 10:38:07 UTC
  • mfrom: (5.1.118 natty)
  • Revision ID: james.westby@ubuntu.com-20110427103807-ym3rhwys6o84ith0
Tags: 2.6.1-2
debian/copyright: clarify for some full organization names.

Show diffs side-by-side

added added

removed removed

Lines of Context:
parser/libapparmor_re/README
 
1
Regular Expression Scanner Generator
 
2
====================================
 
3
 
 
4
Notes in the scanner File Format
 
5
--------------------------------
 
6
 
 
7
The file format used is based on the GNU flex table file format
 
8
(--tables-file option; see Table File Format in the flex info pages and
 
9
the flex sources for documentation). The magic number used in the header
 
10
is set to 0x1B5E783D insted of 0xF13C57B1 though, which is meant to
 
11
indicate that the file format logically is not the same: the YY_ID_CHK
 
12
(check) and YY_ID_DEF (default) tables are used differently.
 
13
 
 
14
Flex uses state compression to store only the differences between states
 
15
for states that are similar. The amount of compresion influences the parse
 
16
speed.
 
17
 
 
18
The following two states could be stored as in the tables outlined
 
19
below:
 
20
 
 
21
States and transitions on specific characters to next states
 
22
------------------------------------------------------------
 
23
 1: ('a' => 2, 'b' => 3, 'c' => 4)
 
24
 2: ('a' => 2, 'b' => 3, 'd' => 5)
 
25
 
 
26
Flex-like table format
 
27
----------------------
 
28
index: (default, base)
 
29
    0: (      0,    0)  <== dummy state (nonmatching)
 
30
    1: (      0,    0)
 
31
    2: (      1,  256)
 
32
 
 
33
  index: (next, check)
 
34
      0: (   0,     0)  <== unused entry
 
35
         (   0,     1)  <== ord('a') identical entries
 
36
  0+'a': (   2,     1)
 
37
  0+'b': (   3,     1)
 
38
  0+'c': (   4,     1)
 
39
         (   0,     1)  <== (255 - ord('c')) identical entries
 
40
256+'c': (   0,     2)
 
41
256+'d': (   5,     2)
 
42
 
 
43
Here, state 2 is described as ('c' => 0, 'd' => 5), and everything else
 
44
as in state 1. The matching algorithm is as follows.
 
45
 
 
46
Flex-like scanner algorithm
 
47
---------------------------
 
48
  /* current state is in <state>, input character <c> */
 
49
  while (check[base[state] + c] != state)
 
50
    state = default[state];
 
51
  state = next[state];
 
52
  /* continue with the next input character */
 
53
 
 
54
This state compression algorithm performs well, except when there are
 
55
many inverted or wildcard matches ("[^x]", "."). Each input character
 
56
may cause several iterations in the while loop.
 
57
 
 
58
 
 
59
We will have many inverted character classes ("[^/]") that wouldn't
 
60
compress very well. Therefore, the regexp matcher uses no state
 
61
compression, and uses the check and default tables differently. The
 
62
above states could be stored as follows:
 
63
 
 
64
Regexp table format
 
65
-------------------
 
66
 
 
67
index: (default, base)
 
68
    0: (      0,    0)  <== dummy state (nonmatching)
 
69
    1: (      0,    0)
 
70
    2: (      1,    3)
 
71
 
 
72
  index: (next, check)
 
73
      0: (   0,     0)  <== unused entry
 
74
         (   0,     0)  <== ord('a') identical, unused entries
 
75
  0+'a': (   2,     1)
 
76
  0+'b': (   3,     1)
 
77
  0+'c': (   4,     1)
 
78
  3+'a': (   2,     2)
 
79
  3+'b': (   3,     2)
 
80
  3+'c': (   0,     0)  <== entry is unused
 
81
  3+'d': (   5,     2)
 
82
         (   0,     0)  <== (255 - ord('d')) identical, unused entries
 
83
 
 
84
All the entries with 0 in check (except the first entry, which is
 
85
deliberately reserved) are still available for other states that
 
86
fit in there.
 
87
 
 
88
Regexp scanner algorithm
 
89
------------------------
 
90
  /* current state is in <state>, matching character <c> */
 
91
  if (check[base[state] + c] == state)
 
92
    state = next[state];
 
93
  else
 
94
    state = default[state];
 
95
  /* continue with the next input character */
 
96
 
 
97
This representation and algorithm allows states which match more
 
98
characters than they do not match to be represented as their inverse. 
 
99
For example, a third state that accepts everything other than 'a' can
 
100
be added to the tables as one entry in (default, base) and one entry in
 
101
(next, check):
 
102
 
 
103
State
 
104
-----
 
105
 3: ('a' => 0, everything else => 5)
 
106
 
 
107
Regexp tables
 
108
-------------
 
109
index: (default, base)
 
110
    0: (      0,    0)  <== dummy state (nonmatching)
 
111
    1: (      0,    0)
 
112
    2: (      1,    3)
 
113
    3: (      5,    7)
 
114
 
 
115
  index: (next, check)
 
116
      0: (   0,     0)  <== unused entry
 
117
         (   0,     0)  <== ord('a') identical, unused entries
 
118
  0+'a': (   2,     1)
 
119
  0+'b': (   3,     1)
 
120
  0+'c': (   4,     1)
 
121
  3+'a': (   2,     2)
 
122
  3+'b': (   3,     2)
 
123
  3+'c': (   0,     0)  <== entry is unused
 
124
  3+'d': (   5,     2)
 
125
  7+'a': (   0,     3)
 
126
         (   0,     0)  <== (255 - ord('a')) identical, unused entries
 
127
 
 
128
While the current code does not implement any form of state compression,
 
129
the flex state compression representation could be combined by
 
130
remembering (in a bit per state, for example) which default entries
 
131
refer to inverted matches, and which refer to parent states.