[apparmor] [PATCH 08/11] Fix infinite loop bug in normalization.

[Steve Beattie]

On Wed, Mar 07, 2012 at 06:17:27AM -0800, John Johansen wrote:
> There are some rare occassions, when lots of alternations are used that
> tree simplification can result in an expression of
>   (E | (E | E)) or (E . (E . E))   where E is the epsnode
> 
> both of these expressions will lead to an inifinite loop in normalize_tree
> as the epsnode test
>        if ((&epsnode == t->child[dir]) &&
>        	      (&epsnode != t->child[!dir]) &&
> 	      		    dynamic_cast<TwoChildNode *>(t)) {
> 
> and the tree node rotation test
>     	} else if ((dynamic_cast<AltNode *>(t) &&
> 	           dynamic_cast<AltNode *>(t->child[dir])) ||
> 		   (dynamic_cast<CatNode *>(t) &&
> 		   dynamic_cast<CatNode *>(t->child[dir]))) {
> 
> end up undoing each others work, ie.
> 
>                 eps flip                 rotate
>   (E | (E | E)) --------> ((E | E) | E) -------> (E | (E | E))
> 
> Signed-off-by: John Johansen <john.johansen at canonical.com>

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

> ---
>  parser/libapparmor_re/expr-tree.cc |   20 ++++++++++++++------
>  1 files changed, 14 insertions(+), 6 deletions(-)
> 
> diff --git a/parser/libapparmor_re/expr-tree.cc b/parser/libapparmor_re/expr-tree.cc
> index cf6f2d6..a8938ef 100644
> --- a/parser/libapparmor_re/expr-tree.cc
> +++ b/parser/libapparmor_re/expr-tree.cc
> @@ -187,14 +187,22 @@ void normalize_tree(Node *t, int dir)
>  		return;
>  
>  	for (;;) {
> -		if ((&epsnode == t->child[dir]) &&
> -		    (&epsnode != t->child[!dir]) &&
> -		    dynamic_cast<TwoChildNode *>(t)) {
> +		if (dynamic_cast<TwoChildNode *>(t) &&
> +		    (&epsnode == t->child[dir]) &&
> +		    (&epsnode != t->child[!dir])) {
>  			// (E | a) -> (a | E)
>  			// Ea -> aE
> -			Node *c = t->child[dir];
> -			t->child[dir] = t->child[!dir];
> -			t->child[!dir] = c;
> +			// Test for E | (E | E) and E . (E . E) which will
> +			// result in an infinite loop
> +			Node *c = t->child[!dir];
> +			if (dynamic_cast<TwoChildNode *>(c) &&
> +			    &epsnode == c->child[dir] &&
> +			    &epsnode == c->child[!dir]) {
> +				c->release();
> +				c = &epsnode;
> +			}
> +			t->child[dir] = c;
> +			t->child[!dir] = &epsnode;
>  			// Don't break here as 'a' may be a tree that
>  			// can be pulled up.
>  		} else if ((dynamic_cast<AltNode *>(t) &&
> -- 
> 1.7.9
> 
> 
> -- 
> 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/20120308/164b8599/attachment.pgp>