[apparmor] priorities for DFA improvements

[John Johansen]

So I am looking at making several improvements to the dfa that is currently
used to handle pattern matching.  I am interest hearing other peoples input
and priorities

None of the options are mutually exclusive, work has been done on all of
them in at least a research and evaluation pass so that eventually I
would like to get to a matching engine incorporating all of them.  And
yes I know I have rambled on about this before


1. Relative (delta) state compression
This improves the compression of the dfa hence reducing its size (even at
runtime), however it requires as many as 2x as many state traversals
as the current scheme.  The an n length string could take up to 2n state
transitions to result in a match.

This compression scheme can be retro fitted into the current dfa layout,
and only requires a small addition to the matching code.  The user space
compression changes are larger, requiring an extra phase, but it can
actually speed up compression by reducing the size of sparse vectors
being fit with the comb compression.

This however does not necessarily mean that there will be a 2x slow down
in matching.  While there is more processing for every input character,
so of that is parallelized on modern cpus.  Also the compression reduces
the amount of memory that needs to be traversed to do a match (improving
caching) and it also tends to improve the locality of the dfa layout
(also improving caching affects).

The net effect is a smaller dfa, which will be faster in some cases and
slower in others.



2. Bit vectors masks replacing check entries (new format)
This is another compression improvement.  Its a technique to get rid
of the current check entries (1 per non default transition).

This at best will save about 14 bits per transition assuming staying with
current entry sizes.  Which would mean a non default transition would
require about 18 bits instead of 32 bits.

However #1 reduces the number of non-default entries and this requires
breaking the current format.



3. Relative entries
Yet another form of relative entry (that can be combined with #1), the
next/check entries are stored relative to the current state.  This
allows overlapping states that have the same pattern but transition
to different states.

Their is no real extra amount of runtime processing for this as it just
changes how the indexing is done, and with careful ordering it can extend
the size of dfa that can be supported with a 16 bit entry (up to 2x the
size).

This can be retro fitted into the current format or be used with #2.



4. Fast bit vector comb search
This is just an improvement on how the current comb compression is
implemented.  It should speed up the compression fair bit, which
currently is the largest component of time for compiles of dfas of
any significant size.

Note that this is complimentary to #1, and will also benefit the current
scheme.



5. tree factoring rework
This reworks the front end tree optimization.  It will result in
small savings in most cases but should significantly help any case
where -O no-expr-tree results in a faster compile (few rules/profile
with lots of profiles).



6. Counting constraints (new format)
This would change the dfa into an extended automata that has counting
memory associated with states.  This will stop state explosions for
expressions that have counting constraints.
  eg. (in pcre syntax)
     ab.{n}y
     ab.{n,m}
     ab(cd){n}

    where n and m represent repetition counts for the previous
    expression.

The current apparmor globbing syntax does not allow for counting
constraints to be expressed however if we open up access to the pcre
style matching used underneath they will occur.

Also note counting constraints can be nice for matches done in
networking rules.  (See some snort rule sets for examples)

This change will require a new dfa format.



7. variables (new format?)
The addition of run time variables (eg. @{proc}).  I might be able
to fit it into the current format (at least in a limited form).



8. back references (new format)
The addition of pcre back references.
  eg. (abc).\1y

Current apparmor globbing can't generate them but they can be
nice to have (especially for network rules).

Note the adding variable support is half way to adding back references
as back references are variables that get defined by proceeding matches.



9. Character classes - aka alphabet reduction
This actually exists but is unused currently and even when used not
exploited to its fullest.

It allows reducing the size of the dfa, and speed up compression.
However it does require an extra lookup at runtime.  Which may or may
slow down matching depending on the match and the dfa (what classes
get generated, the affects on size, locality ..)



10. stride doubling (new format)
This allows traversing 2 input characters at a time, speeding up matching.
It relies on #1 and #9 to get the alphabet small enough to be feasible.

It is also most likely more effective on network rules which will tend to
have a more limited alphabet.



11. hybrid-finite state automata (new format)
This would convert use from using a pure dfa to a hybrid where there is
a head dfa, with boundry states and tail dfas.  This can be used to counter
state explosions caused by * and **.  Thus significantly reducing the size
of the dfa for any policy that has state explosion.

This can result in a slower match but in generally it is usually faster
because of memory and locality effects.