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

[Kees Cook]

On Thu, Feb 16, 2012 at 08:26:09AM -0800, John Johansen wrote:
> 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];

I don't understand this area well enough to be comfortable to ACK it, but
if you say it's needed, that's good enough for me. ;) That said, is there
a simple test-case that can be used to show the before/after of this
change?

-Kees

-- 
Kees Cook