[apparmor] [PATCH 2/6] Fix dfa minimization around the nonmatching state

[Steve Beattie]

On Wed, Mar 21, 2012 at 06:02:21AM -0700, John Johansen wrote:
> The same mappings routine had two bugs in it, that in practice haven't
> manifested because of partition ordering during minimization.  The
> result is that some states may fail comparison and split, resulting
> in them not being eliminated when they could be.
> 
> The first is that direct comparison to the nonmatching state should
> not be done as it is a candiate for elimination, instead its partion
> should be compared against.  This simplifies the first test
> 
> 
> The other error is the comparison
>   if (rep->otherwise != nonmatching)
> 
> again this is wrong because nomatching should not be directly
> compared against.  And again can result in the current rep->otherwise
> not being eliminated/replaced by the partion.  Again resulting in
> extra trap states.
> 
> These tests where original done the way they were because
>  ->otherwise could be null, which was used to represent nonmatching.
> The code was cleaned up a while ago to remove this, ->otherwise is
> always a valid pointer now.
> 
> Signed-off-by: John Johansen <john.johansen at canonical.com>

Acked-By: Steve Beattie <sbeattie at ubuntu.com>

> ---
>  parser/libapparmor_re/hfa.cc |   21 +++++----------------
>  1 files changed, 5 insertions(+), 16 deletions(-)
> 
> diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
> index d043e75..3e796ad 100644
> --- a/parser/libapparmor_re/hfa.cc
> +++ b/parser/libapparmor_re/hfa.cc
> @@ -360,26 +360,17 @@ void DFA::remove_unreachable(dfaflags_t flags)
>  /* test if two states have the same transitions under partition_map */
>  bool DFA::same_mappings(State *s1, State *s2)
>  {
> -	if (s1->otherwise != nonmatching) {
> -		if (s2->otherwise == nonmatching)
> -			return false;
> -		Partition *p1 = s1->otherwise->partition;
> -		Partition *p2 = s2->otherwise->partition;
> -		if (p1 != p2)
> -			return false;
> -	} else if (s2->otherwise != nonmatching) {
> +	if (s1->otherwise->partition != s2->otherwise->partition)
>  		return false;
> -	}
>  
>  	if (s1->trans.size() != s2->trans.size())
>  		return false;
> +
>  	for (StateTrans::iterator j1 = s1->trans.begin(); j1 != s1->trans.end(); j1++) {
>  		StateTrans::iterator j2 = s2->trans.find(j1->first);
>  		if (j2 == s2->trans.end())
>  			return false;
> -		Partition *p1 = j1->second->partition;
> -		Partition *p2 = j2->second->partition;
> -		if (p1 != p2)
> +		if (j1->second->partition != j2->second->partition)
>  			return false;
>  	}
>  
> @@ -547,10 +538,8 @@ void DFA::minimize(dfaflags_t flags)
>  			cerr << *rep << " : ";
>  
>  		/* update representative state's transitions */
> -		if (rep->otherwise != nonmatching) {
> -			Partition *partition = rep->otherwise->partition;
> -			rep->otherwise = *partition->begin();
> -		}
> +		rep->otherwise = *rep->otherwise->partition->begin();
> +
>  		for (StateTrans::iterator c = rep->trans.begin(); c != rep->trans.end(); c++) {
>  			Partition *partition = c->second->partition;
>  			c->second = *partition->begin();
> -- 
> 1.7.9.1
> 
> 
> -- 
> AppArmor mailing list
> AppArmor at lists.ubuntu.com
> Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor

-- 
Steve Beattie
<sbeattie at ubuntu.com>
http://NxNW.org/~steve/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <https://lists.ubuntu.com/archives/apparmor/attachments/20120321/de2c1ee3/attachment.pgp>