[apparmor] [PATCH 1/2] Fix an error in tree normalization that can result in an infinite loop

[John Johansen]

Tree normailization tries to reshape expr tree into a normal from like

               |1               |1
              / \              / \
             |2  T     ->     a   |2
            / \                  / \
           |3  c                b   |3
          / \                      / \
         a   b                    c   T

which requires rotating the alt and cat nodes, at the same time it
also tries to rotate epsnods to the same side as alt and cat nodes.

However there is a bug that results in the epsnode flipping and
node rotation reverting each others work.  If the tree is of the
follow form this will result in an infinite loop.

               |1
              / \
             e2  |3
                / \
               e3  C

epsnode flipping is not supposed to take precedence over node rotation
and there is even a test to check for an alt or cat node, unfortunately
it is wrong resulting in unnecessary swapping and the possibility for
the above infinite loop

Signed-off-by: John Johansen <john.johansen at canonical.com>
---
 parser/libapparmor_re/expr-tree.cc |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/parser/libapparmor_re/expr-tree.cc b/parser/libapparmor_re/expr-tree.cc
index e9a1275..b502d54 100644
--- a/parser/libapparmor_re/expr-tree.cc
+++ b/parser/libapparmor_re/expr-tree.cc
@@ -189,7 +189,7 @@ void normalize_tree(Node *t, int dir)
 	for (;;) {
 		if ((&epsnode == t->child[dir]) &&
 		    (&epsnode != t->child[!dir]) &&
-		    dynamic_cast<TwoChildNode *>(t)) {
+		    !dynamic_cast<TwoChildNode *>(t->child[!dir])) {
 			// (E | a) -> (a | E)
 			// Ea -> aE
 			Node *c = t->child[dir];
-- 
1.7.9