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

[Steve Beattie]

On Thu, Feb 16, 2012 at 12:25:05PM -0800, Kees Cook wrote:
> 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?

I feel similarly, though I think I see the logic. Does the fixed
check invalidate the comment that follows the child swap:

		// Don't break here as 'a' may be a tree that
		// can be pulled up.

or can 'a' still be a tree even if it's not a TwoChildNode?

(Also, the swap code could be simplified or at least made to be
consistent with the comment; since t->child[dir] is known to point
&epsnode, I think you could do:

		t->child[dir] = t->child[!dir];
		t->child[!dir] = &epsnode;

or if you wanted to indicate that you're swapping positions, this may be
more consistent with the comments referring to a

		Node *a = t->child[!dir];
		t->child[!dir] = t->child[dir];
		t->child[dir] = a;

because the temporary behavior would match up with a.)

It *really* would be nice if we had some unit tests for this code.

-- 
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/20120216/8e115048/attachment.pgp>