2
0
mirror of https://gitlab.com/apparmor/apparmor synced 2025-08-22 01:57:43 +00:00
John Johansen 0824954b57 Merge parser: fix Normalizatin infinite loop
Expression simplification can get into an infinite loop due to eps
pairs hiding behind and alternation that can't be caught by
normalize_eps() (which exists in the first place to stop a similar
loop).

The loop in question happens in AltNode::normalize when a subtree has
the following structure.

1. elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                   alt
                   /\
                  /  \
                 /    \
               eps    alt
                      /\
                     /  \
                    /    \
                  alt    eps
                  /\
                 /  \
                /    \
               eps   eps

2. if (normalize_eps(dir)) results in

                   alt
                   /\
                  /  \
                 /    \
               alt    eps
               /\
              /  \
             /    \
           alt    eps
           /\
          /  \
         /    \
       eps   eps

3. elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                   alt
                   /\
                  /  \
                 /    \
               alt    alt
              /\        /\
             /  \      /  \
            /    \    /    \
          eps    eps eps   eps

4. elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                   alt
                   /\
                  /  \
                 /    \
               eps    alt
                      /\
                     /  \
                    /    \
                  eps    alt
                         /\
                        /  \
                       /    \
                     eps   eps

5. if (normalize_eps(dir)) results in

                  alt
                   /\
                  /  \
                 /    \
                alt   eps
                /\
               /  \
              /    \
            eps    alt
                    /\
                   /  \
                  /    \
                 eps   eps

6. elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                  alt
                   /\
                  /  \
                 /    \
                eps   alt
                       /\
                      /  \
                     /    \
                    alt  eps
                    /\
                   /  \
                  /    \
                eps   eps

back to beginning of cycle

Fix this by detecting the creation of an eps_pair in rotate_node(),
that pair can be immediately eliminated by simplifying the tree in that
step.

In the above cycle the pair creation is caught at step 3 resulting
in

3. elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                   alt
                   /\
                  /  \
                 /    \
               alt    eps
               /\
              /  \
             /    \
           eps    eps

4.  elseif (child[dir]->is_type(ALT_NODE)) rotate_node too

                   alt
                   /\
                  /  \
                 /    \
               eps   alt
                      /\
                     /  \
                    /    \
                  eps    eps

which gets reduced to

                   alt
                   /\
                  /  \
                 /    \
               eps   eps

breaking the normalization loop. The degenerate alt node will be caught
in turn when its parent is dealt with.

This needs to be backported to all releases

Closes: https://gitlab.com/apparmor/apparmor/-/issues/398
Fixes: 846cee506 ("Split out parsing and expression trees from regexp.y")
Reported-by: Christian Boltz <apparmor@cboltz.de>
Signed-off-by: John Johansen <john.johansen@canonical.com>

Closes #398
MR: https://gitlab.com/apparmor/apparmor/-/merge_requests/1252
Approved-by: Georgia Garcia <georgia.garcia@canonical.com>
Merged-by: John Johansen <john@jjmx.net>

(cherry picked from commit a6691ca53e77263edb7281df3d4d008022812745)
Signed-off-by: John Johansen <john.johansen@canonical.com>
2024-06-14 13:23:32 -07:00
..
2023-05-18 11:24:36 -05:00
2018-10-12 22:22:29 -07:00
2014-04-23 11:35:29 -07:00
2013-09-27 16:16:37 -07:00

The apparmor_parser allows you to add, replace, and remove AppArmor
policy through the use of command line options. The default is to add.
`apparmor_parser --help` shows what the command line options are.

You can also find more information at https://wiki.apparmor.net

-- The AppArmor development team