[apparmor] [PATCH 05/11] Fix dfa minimization to deal with exec conflicts
Steve Beattie
steve at nxnw.org
Thu Mar 8 18:01:15 UTC 2012
On Wed, Mar 07, 2012 at 06:17:24AM -0800, John Johansen wrote:
> Minimization was failing because it was too agressive. It was minimizing
> as if there was only 1 accept condition. This allowed it to remove more
> states but at the cost of loosing unique permission sets, they where
> being combined into single commulative perms. This means that audit,
> deny, xtrans, ... info on one path would be applied to all other paths
> that it was combined with during minimization.
>
> This means that we need to retain the unique accept states, not allowing
> them to be combined into a single state. To do this we put each unique
> permission set into its own partition at the start of minimization.
>
> The states within a partition have the same permissions and can be combined
> within the other states in the partition as the loss of unique path
> information is will not result in a conflict.
>
> This is similar to what perm hashing used to do but deny information is
> still being correctly applied and carried.
>
> Signed-off-by: John Johansen <john.johansen at canonical.com>
Acked-By: Steve Beattie <sbeattie at ubuntu.com>
(I'll try to think about how we can improve the infrastructure for
the added testcases.)
> ---
> parser/libapparmor_re/hfa.cc | 16 +-
> parser/tst/Makefile | 7 +-
> parser/tst/minimize.sh | 208 ++++++++++++++++++++
> .../tst/simple_tests/xtrans/minimize-x-conflict.sd | 6 +-
> 4 files changed, 224 insertions(+), 13 deletions(-)
> create mode 100755 parser/tst/minimize.sh
>
> diff --git a/parser/libapparmor_re/hfa.cc b/parser/libapparmor_re/hfa.cc
> index 887b135..2c09eff 100644
> --- a/parser/libapparmor_re/hfa.cc
> +++ b/parser/libapparmor_re/hfa.cc
> @@ -431,7 +431,7 @@ int DFA::apply_and_clear_deny(void)
> /* minimize the number of dfa states */
> void DFA::minimize(dfaflags_t flags)
> {
> - map<size_t, Partition *> perm_map;
> + map<pair<uint64_t, size_t>, Partition *> perm_map;
> list<Partition *> partitions;
>
> /* Set up the initial partitions
> @@ -448,20 +448,18 @@ void DFA::minimize(dfaflags_t flags)
> int final_accept = 0;
> for (Partition::iterator i = states.begin(); i != states.end(); i++) {
> size_t hash = 0;
> - if (!(*i)->perms.is_null())
> - /* combine all states carrying accept info together
> - into an single initial parition */
> - hash = 1;
> + uint64_t permtype = ((uint64_t) (PACK_AUDIT_CTL((*i)->perms.audit, (*i)->perms.quiet & (*i)->perms.deny)) << 32) | (uint64_t) (*i)->perms.allow;
> if (flags & DFA_CONTROL_MINIMIZE_HASH_TRANS)
> - hash |= hash_trans(*i) << 1;
> - map<size_t, Partition *>::iterator p = perm_map.find(hash);
> + hash |= hash_trans(*i);
> + pair<uint64_t, size_t> group = make_pair(permtype, hash);
> + map<pair<uint64_t, size_t>, Partition *>::iterator p = perm_map.find(group);
> if (p == perm_map.end()) {
> Partition *part = new Partition();
> part->push_back(*i);
> - perm_map.insert(make_pair(hash, part));
> + perm_map.insert(make_pair(group, part));
> partitions.push_back(part);
> (*i)->partition = part;
> - if (hash & 1)
> + if (permtype)
> accept_count++;
> } else {
> (*i)->partition = p->second;
> diff --git a/parser/tst/Makefile b/parser/tst/Makefile
> index 5d05bf4..bee6745 100644
> --- a/parser/tst/Makefile
> +++ b/parser/tst/Makefile
> @@ -12,8 +12,8 @@ endif
>
> all: tests
>
> -.PHONY: tests error_output gen_xtrans parser_sanity caching
> -tests: error_output gen_xtrans parser_sanity caching
> +.PHONY: tests error_output gen_xtrans parser_sanity caching minimize
> +tests: error_output gen_xtrans parser_sanity caching minimize
>
> GEN_TRANS_DIRS=simple_tests/generated_x/ simple_tests/generated_perms_leading/ simple_tests/generated_perms_safe/
>
> @@ -41,6 +41,9 @@ parser_sanity: $(PARSER)
> caching: $(PARSER)
> LANG=C ./caching.sh
>
> +minimize: $(PARSER)
> + LANG=C ./minimize.sh
> +
> $(PARSER):
> make -C $(PARSER_DIR) $(PARSER_BIN)
>
> diff --git a/parser/tst/minimize.sh b/parser/tst/minimize.sh
> new file mode 100755
> index 0000000..e8c760a
> --- /dev/null
> +++ b/parser/tst/minimize.sh
> @@ -0,0 +1,208 @@
> +#!/bin/bash
> +
> +# Format of -D dfa-states
> +# dfa-states output is split into 2 parts:
> +# the accept state infomation
> +# {state} (allow deny audit XXX) ignore XXX for now
> +# followed by the transition table information
> +# {Y} -> {Z}: 0xXX Char #0xXX is the hex dump of Char
> +# where the start state is always shown as
> +# {1} <==
> +#
> +# Eg. echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, deny /** w, }" | ./apparmor_parser -QT -O minimize -D dfa-states --quiet
> +#
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 0/2800a/0/2800a)
> +# {4} (0x 10004/2800a/0/2800a)
> +# {7} (0x 40010/2800a/0/2800a)
> +# {8} (0x 80020/2800a/0/2800a)
> +# {9} (0x 100040/2800a/0/2800a)
> +# {c} (0x 40030/0/0/0)
> +#
> +# {1} -> {2}: 0x2f /
> +# {2} -> {4}: 0x61 a
> +# {2} -> {3}: 0x62 b
> +# {2} -> {3}: 0x63 c
> +# {2} -> {7}: 0x64 d
> +# {2} -> {8}: 0x65 e
> +# {2} -> {9}: 0x66 f
> +# {2} -> {3}: [^\0x0/]
> +# {3} -> {3}: [^\0x0]
> +# {4} -> {3}: [^\0x0]
> +# {7} -> {a}: 0x0
> +# {7} -> {3}: []
> +# {8} -> {3}: [^\0x0]
> +# {9} -> {3}: [^\0x0]
> +# {a} -> {b}: 0x2f /
> +# {b} -> {c}: [^/]
> +# {c} -> {c}: []
> +#
> +# These tests currently only look at the accept state permissions
> +#
> +# To view any of these DFAs as graphs replace --D dfa-states with -D dfa-graph
> +# strip of the test stuff around the parser command and use the the dot
> +# command to convert
> +# Eg.
> +# echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, deny /** w, }" | ./apparmor_parser -QT -O minimize -D dfa-graph --quiet 2>min.graph
> +# dot -T png -o min.png min.graph
> +# and then view min.png in your favorite viewer
> +#
> +#------------------------------------------------------------------------
> +# test to see if minimization is eliminating non-redundant accept state
> +# Test xtrans and regular perms separately. The are the same basic failure
> +# but can xtrans has an extra code path.
> +#
> +# The permission test is setup to have all the none xtrans permissions show
> +# up once on unique paths and have a global write permission that adds to
> +# it.
> +# This should result in a un-minimized dump looking like. Notice it has 6
> +# states with accept information, 1 for each rule except for the 'w'
> +# permission which is combined into a single state for /b and /**
> +#
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 2800a/0/0/0)
> +# {4} (0x 3800e/0/0/0)
> +# {5} (0x 6801a/0/0/0)
> +# {6} (0x a802a/0/0/0)
> +# {7} (0x 12804a/0/0/0)
> +# {a} (0x 40030/0/0/0)
> +# A dump of minimization that is not respecting the uniqueness of the
> +# permissions on the states looks like below. Notice it has only 3 states
> +# with accept information
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 1b806e/0/0/0)
> +# {5} (0x 6801a/0/0/0)
> +# {a} (0x 40030/0/0/0)
> +
> +echo -n "Profiles basic perms "
> +if [ `echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, /** w, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 6 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# same test as above except with audit perms added
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 2800a/0/2800a/0)
> +# {4} (0x 3800e/0/2800a/0)
> +# {7} (0x 6801a/0/2800a/0)
> +# {8} (0x a802a/0/2800a/0)
> +# {9} (0x 12804a/0/2800a/0)
> +# {c} (0x 40030/0/0/0)
> +echo -n "Profiles audit perms "
> +if [ `echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, audit /** w, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 6 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# same test as above except with deny 'w' perm added to /**, this does not
> +# elimnates the states with 'w' and 'a' because the quiet information is
> +# being carried
> +#
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 0/2800a/0/2800a)
> +# {4} (0x 10004/2800a/0/2800a)
> +# {7} (0x 40010/2800a/0/2800a)
> +# {8} (0x 80020/2800a/0/2800a)
> +# {9} (0x 100040/2800a/0/2800a)
> +# {c} (0x 40030/0/0/0)
> +
> +echo -n "Profiles deny perms "
> +if [ `echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, deny /** w, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 6 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# same test as above except with audit deny 'w' perm added to /**, with the
> +# -O filter-deny parameter this elimnates the states with 'w' and 'a' because
> +# the quiet information is NOT being carried
> +#
> +# {1} <== (allow/deny/audit/quiet)
> +# {4} (0x 10004/0/0/0)
> +# {7} (0x 40010/0/0/0)
> +# {8} (0x 80020/0/0/0)
> +# {9} (0x 100040/0/0/0)
> +# {c} (0x 40030/0/0/0)
> +
> +echo -n "Profiles audit deny perms "
> +if [ `echo "/t { /a r, /b w, /c a, /d l, /e k, /f m, audit deny /** w, }" | ../apparmor_parser -QT -O minimize -O filter-deny -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 5 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +
> +# The x transition test profile is setup so that there are 3 conflicting x
> +# permissions, two are on paths that won't collide during dfa creation. The
> +# 3rd is a generic permission that should be overriden during dfa creation.
> +#
> +# This should result in a dfa that specifies transitions on 'a' and 'b' to
> +# unique states that store the alternate accept information. However
> +# minimization can remove the unique accept permission states if x permissions
> +# are treated as a single accept state.
> +#
> +# The minimized dump should retain the 'a' and 'b' transitions accept states.
> +# notice the below dump has 3 states with accept information {3}, {4}, {5}
> +#
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 2914a45/0/0/0)
> +# {4} (0x 4115045/0/0/0)
> +# {5} (0x 2514945/0/0/0)
> +#
> +# A dump of minimization that is not respecting the uniqueness of the
> +# permissions on the states transitioned to by 'a' and 'b' looks like
> +# below. Notice that only state {3} has accept information
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 2514945/0/0/0)
> +#
> +
> +echo -n "Profiles xtrans "
> +if [ `echo "/t { /b px, /* Pixr, /a Cx -> foo, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 3 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# same test as above + audit
> +echo -n "Profiles audit xtrans "
> +if [ `echo "/t { /b px, audit /* Pixr, /a Cx -> foo, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 3 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +
> +# now try denying x and make sure perms are cleared
> +# notice that only deny and quiet information is being carried
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 0/fe17f85/0/14005)
> +
> +echo -n "Profiles deny xtrans "
> +if [ `echo "/t { /b px, deny /* xr, /a Cx -> foo, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 1 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# now try audit + denying x and make sure perms are cleared
> +# notice that the deny info is being carried, by an artifical trap state
> +# {1} <== (allow/deny/audit/quiet)
> +# {3} (0x 0/fe17f85/0/0)
> +
> +echo -n "Profiles audit deny xtrans "
> +if [ `echo "/t { /b px, audit deny /* xr, /a Cx -> foo, }" | ../apparmor_parser -QT -O minimize -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 1 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> +
> +# same thing as above with -O filter-deny to remove the artificial trap state
> +
> +echo -n "Profiles audit deny xtrans + filter-deny "
> +if [ `echo "/t { /b px, audit deny /* xr, /a Cx -> foo, }" | ../apparmor_parser -QT -O minimize -O filter-deny -D dfa-states 2>&1 | grep -v '<==' | grep '(.*)$' | wc -l` -ne 0 ] ; then
> + echo "failed"
> + exit 1;
> +fi
> +echo "ok"
> diff --git a/parser/tst/simple_tests/xtrans/minimize-x-conflict.sd b/parser/tst/simple_tests/xtrans/minimize-x-conflict.sd
> index 3df7ae0..4297956 100644
> --- a/parser/tst/simple_tests/xtrans/minimize-x-conflict.sd
> +++ b/parser/tst/simple_tests/xtrans/minimize-x-conflict.sd
> @@ -1,11 +1,13 @@
> #
> #=DESCRIPTION test for conflict resolution in minimization phase of dfa gen
> -#=EXRESULT FAIL
> +#=EXRESULT PASS
> #=TODO
> #
> /usr/bin/foo {
>
> - # need to build minimal test for this yet
> + /b px,
> + /* Pixr,
> + /a Cx -> foo,
>
> }
>
> --
> 1.7.9
>
>
> --
> AppArmor mailing list
> AppArmor at lists.ubuntu.com
> Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
--
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/20120308/3f61f328/attachment.pgp>
More information about the AppArmor
mailing list