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

[John Johansen]

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>
---
 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