[apparmor] [PATCH 17/32] apparmor: add support for default differential encoding.

[John Johansen]

On 01/24/2013 07:22 PM, Seth Arnold wrote:
> On Wed, Jan 16, 2013 at 01:28:46PM -0800, John Johansen wrote:
>> Default differential encoding stores the current state's transitions as
>> the difference of the default state's transitions.  So for the current
>> match (state and pos) if the state is diffentially encoded, transition to
>> the default state without incrementing pos;
>>
>> Signed-off-by: John Johansen <john.johansen at canonical.com>
> Acked-by: Seth Arnold <seth.arnold at canonical.com>
> 
>> @@ -154,6 +154,8 @@ static int verify_dfa(struct aa_dfa *dfa, int flags)
>>  		}
>>  	}
>>  
>> +	/* TODO: verify diff encode terminates */
>> +
> 
> TODO: solve halting problem :)
> 
> Though some kind of sanity checks would be nice..
> 
hehe, thankfully this isn't the halting problem, nor do you even have to
check every state. A rough description is that the compression creates a
DAG of the states and only ancestors are used as part of the diff encode
(its a little more than that). This allows us to set a bounds on the number
of states that will be used to traverse the differential encode, both for
a match and for the verify.

The verify can actually of a bounds M, where M is the number of states.
While the match worst case is is 2N+1 state traversals (iirc) where N is
the length of the string being matched. However we don't require every
state to be differential encoded so our average length is much closer to
the optimal traversal of N states, while it gives us an average of about
50% more compression and actually even improving match speed is some
cases because of hot paths and cacheline reuse.