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 <[email protected]> > > --- > > 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
<[email protected]>
http://NxNW.org/~steve/
signature.asc
Description: Digital signature
-- AppArmor mailing list [email protected] Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
