[apparmor] [PATCH 08/11] Fix infinite loop bug in normalization.
John Johansen
john.johansen at canonical.com
Wed Mar 7 14:17:27 UTC 2012
There are some rare occassions, when lots of alternations are used that
tree simplification can result in an expression of
(E | (E | E)) or (E . (E . E)) where E is the epsnode
both of these expressions will lead to an inifinite loop in normalize_tree
as the epsnode test
if ((&epsnode == t->child[dir]) &&
(&epsnode != t->child[!dir]) &&
dynamic_cast<TwoChildNode *>(t)) {
and the tree node rotation test
} else if ((dynamic_cast<AltNode *>(t) &&
dynamic_cast<AltNode *>(t->child[dir])) ||
(dynamic_cast<CatNode *>(t) &&
dynamic_cast<CatNode *>(t->child[dir]))) {
end up undoing each others work, ie.
eps flip rotate
(E | (E | E)) --------> ((E | E) | E) -------> (E | (E | E))
Signed-off-by: John Johansen <john.johansen at canonical.com>
---
parser/libapparmor_re/expr-tree.cc | 20 ++++++++++++++------
1 files changed, 14 insertions(+), 6 deletions(-)
diff --git a/parser/libapparmor_re/expr-tree.cc b/parser/libapparmor_re/expr-tree.cc
index cf6f2d6..a8938ef 100644
--- a/parser/libapparmor_re/expr-tree.cc
+++ b/parser/libapparmor_re/expr-tree.cc
@@ -187,14 +187,22 @@ void normalize_tree(Node *t, int dir)
return;
for (;;) {
- if ((&epsnode == t->child[dir]) &&
- (&epsnode != t->child[!dir]) &&
- dynamic_cast<TwoChildNode *>(t)) {
+ if (dynamic_cast<TwoChildNode *>(t) &&
+ (&epsnode == t->child[dir]) &&
+ (&epsnode != t->child[!dir])) {
// (E | a) -> (a | E)
// Ea -> aE
- Node *c = t->child[dir];
- t->child[dir] = t->child[!dir];
- t->child[!dir] = c;
+ // Test for E | (E | E) and E . (E . E) which will
+ // result in an infinite loop
+ Node *c = t->child[!dir];
+ if (dynamic_cast<TwoChildNode *>(c) &&
+ &epsnode == c->child[dir] &&
+ &epsnode == c->child[!dir]) {
+ c->release();
+ c = &epsnode;
+ }
+ t->child[dir] = c;
+ t->child[!dir] = &epsnode;
// Don't break here as 'a' may be a tree that
// can be pulled up.
} else if ((dynamic_cast<AltNode *>(t) &&
--
1.7.9
More information about the AppArmor
mailing list