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

[John Johansen]

On 02/16/2012 03:34 PM, Steve Beattie wrote:
> 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?
yes and no.

I can trivially trigger it, patching the parser but you can't easily trigger
it yet, with the way rules are currently exposed.  Mount rules on the other
hand where trivially triggering this.

This was the fast fix that got the problem out of the way, but well it has
its own issues.

however the improvement is dramatic with out it infinite loop, with it
things complete :)

>
> 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?
>
sigh yes this does break that

well it can be the root of a * or + expression but they can't be pulled
up.

basically this was the quick fix, and while it doesn't break things, it
does make the simplification less effective and I think we can do better
I will take another pass at it.

> (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;
>
yeah, we used to not use a single shared epsnode, and the code hasn't
been cleaned up for it, mostly because I have been completely rewriting
the tree simplification.

> 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.)
>
hehe yeah

> It *really* would be nice if we had some unit tests for this code.
>
yep that is badly needed