[apparmor] [PATCH 2/3] Track full permission set through all stages of DFA construction.

[John Johansen]

On 02/14/2012 11:42 AM, Kees Cook wrote:
> On Tue, Feb 14, 2012 at 09:57:27AM -0800, John Johansen wrote:
>> Previously permission information was thrown away early and permissions
>> where packed to their CHFA form at the start of DFA construction.  Because
>> of this permissions hashing to setup the initial DFA partitions was
>> required as x transition conflicts, etc. could not be resolved.
>>
>> Move the mapping of permissions to CHFA construction, and track the full
>> permission set through DFA construction.  This allows removal of the
>> perm_hashing hack, which prevented a full minimization from happening
>> in some DFAs.  It also could result in x conflicts not being correctly
>> detected, and deny rules not being fully applied in some situations.
> 
> Does this mean the big "x" collision test is useless now?
>
nope, it means its more important.  Previously permission hashing was keeping
things from colliding, but at the cost of not being able to do a full minimization.

Now we are merging states that previously were not mergeable (as they started in
separate partitions and partitions are only ever split) and so they where never
being checked for x collisions.  Under permission hashing it was theoretically
possible to construct a dfa with conflicting x rules, that had overlapping regexes
but never got merged so that the conflict test would never be run.

I say theoretically because I never managed to achieve it and I don't believe it
was actually possible with the expressions we where creating but I never sat down
and figured out how to prove it, as the time was better spent fixing it.

>> Signed-off-by: John Johansen <john.johansen at canonical.com>
> 
> Acked-by: Kees Cook <kees at ubuntu.com>
> 
>> @@ -462,6 +465,7 @@ void DFA::minimize(dfaflags_t flags)
>>  			     << partitions.size() << "\tinit " << partitions.size()
>>  			     << " (accept " << accept_count << ")\r";
>>  	}
>> +
>>  	/* perm_map is no longer needed so free the memory it is using.
>>  	 * Don't remove - doing it manually here helps reduce peak memory usage.
>>  	 */
> 
> The prior patch drops this whitespace. Probably best to decide one way or
> the other. :)
> 
hehe right