[apparmor] priorities for DFA improvements

[John Johansen]

On 02/25/2011 10:27 AM, John Johansen wrote:
> 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
> 
> 
So I seemed to have left out a few things


12.  Abstracted Permissions

This abstracts out the permission code from the dfa, making it so the caller
supplies call backs to handle the details.  Not only does this provide
better flexibility, but is also needed to support some of the features we
would like to have in the future (global policy analysis, x dominance,
extended conditionals, rule ordering).

The big drivers here are global policy analysis, and x dominance.  Global
policy analysis will be useful in analysis potential threats from profile
interactions and also help in profile development (eg. automatically being
able to find and group common overlaps that could be pulled into abstractions).
The x dominance is for allowing conflicting overlapping exec modifier priority.
  eg.
      /** ix,
      /bin/foo px,



13. Set operations on dfas.
This will allow for set manipulations on two dfas (ie. intersect, union,
subtract).  This is needed for the proposed rule extensions
  {*^foo} and {**^foo}

It could also be useful in speeding up compilation and reducing memory usage
when it is detected the state explosion will occur.  The rules are split built
into N minimized dfas, which are then combined and minimized.  Since the total
number of redundant states is controlled by splitting into smaller sets.
The total number of redundant states created, and then removed is reduced.

Set operations will also be needed to do analysis on #11 (hybrid fa), but not
needed to actually build it.




14. Extentions to globbing syntax

The following are proposed additions to the current file globbing and are not currently implemented:
{*^} - a glob similar to * with an alternation style list of things it is not allowed to match.
eg. /etc/{*^shadow} is the same as allowing everything /etc/* matches except /etc/shadow
eg. /etc/{*^shadow,passwd} is the same as /etc/* - /etc/{shadow,passwd}
eg. /etc/{*^*shadow} is the same as /etc/* - /etc/*shadow
note that an empty alternation entry is not allowed ie. {*^shadow,}
{**^} - a glob similar to ** with an alternation style list of things is is not allowed to match eg. /etc/{**^shadow} is the same as /etc/** matches - /etc/shadow
eg. /etc/{**^shadow,passwd} is the same as /etc/** - /etc/{shadow,passwd}
eg. /etc/{**^*shadow} is the same as /etc/** - /etc/*shadow
note that an empty alternation entry is not allowed ie. {**^shadow,}



15. Reduced peak memory use during compile

There are still more improvement to be had on peak memory use during compile.
Just how important is it we get this down, verses adding new features,
speeding up the compile, reducing runtime usage.