[apparmor] [patch] Fix dfa minimization
Tyler Hicks
tyhicks at canonical.com
Tue Dec 24 17:06:02 UTC 2013
This patch doesn't seem to be against trunk. It applies with fuzz and
needs this additional change to build:
diff --git a/parser/parser_common.c b/parser/parser_common.c
index 53a3e70..8d780e0 100644
--- a/parser/parser_common.c
+++ b/parser/parser_common.c
@@ -34,7 +34,7 @@ int names_only = 0;
int current_lineno = 1;
int option = OPTION_ADD;
-dfaflags_t dfaflags = (dfaflags_t)(DFA_CONTROL_TREE_NORMAL | DFA_CONTROL_TREE_SIMPLE | DFA_CONTROL_MINIMIZE | DFA_CONTROL_MINIMIZE_HASH_TRANS);
+dfaflags_t dfaflags = (dfaflags_t)(DFA_CONTROL_TREE_NORMAL | DFA_CONTROL_TREE_SIMPLE | DFA_CONTROL_MINIMIZE);
char *subdomainbase = NULL;
const char *progname = __FILE__;
On 2013-12-24 04:33:07, John Johansen wrote:
> So DFA minimization has a bug and feature that keeps it from minimizing
> some dfas completely. This feature/bug did not result in incorrect dfas,
> it just fails to result in full minimization.
>
> The same mappings comparison is wrong. Or more correctly it is right when
> transitions are not remapped to minimization partitions, but it may be
> wrong when states are remapped. This means it will cause excess
> partitioning (not removing all the states it should).
>
> The trans hashing does a "guess" at partition splitting as a performance
> enhancement. Basically it leverages the information that states that have
> different transitions or transitions on different characters are not the
> same. However this isn't always the case, because minimization can cause
> some of those transitions to be altered. In previous testing this was
> always a win, with only a few extra states being added some times. However
> this changes with when the same mappings are fixed, as the hashing that was
> done was based on the same flawed mapping as the broken same mappings.
>
> If the same mappings are fixed and the hashing is not removed then there
> is little to no change. However with both changes applied some dfas see
> significant improvements. These improvements often result in performance
> improvements despite minimization doing more work, because it means less
> work to be done in the chfa comb compression
>
> eg. test case that raised the issue (thanks tyler)
> /t { mount fstype=ext2, mount, }
>
> used to be minimized to
> {1} <== (allow/deny/audit/quiet)
> {6} (0x 2/0/0/0)
>
> {1} -> {2}: 0x7
> {2} -> {3}: 0x0
> {2} -> {2}: []
> {3} -> {4}: 0x0
> {3} -> {3}: []
> {4} -> {6}: 0x0
> {4} -> {7}: 0x65 e
> {4} -> {5}: []
> {5} -> {6}: 0x0
> {5} -> {5}: []
> {6} (0x 2/0/0/0) -> {6}: [^\0x0]
> {7} -> {6}: 0x0
> {7} -> {8}: 0x78 x
> {7} -> {5}: []
> {8} -> {6}: 0x0
> {8} -> {5}: 0x74 t
> {8} -> {5}: []
>
> with the patch it is now properly minimized to
> {1} <== (allow/deny/audit/quiet)
> {6} (0x 2/0/0/0)
>
> {1} -> {2}: 0x7
> {2} -> {3}: 0x0
> {2} -> {2}: []
> {3} -> {4}: 0x0
> {3} -> {3}: []
> {4} -> {6}: 0x0
> {4} -> {4}: []
> {6} (0x 2/0/0/0) -> {6}: [^\0x0]
>
>
> The evince profile set sees some significant improvements picking a couple
> example from its "minimized" dfas (it has 12) we see a reduction from 9720
> states to 6232 states, and 6537 states to 3653 states. All told seeing the
> performance/profile size going from
> 2.8 parser: 4.607s 1007267 bytes
> dev head: 3.48s 1007267 bytes
> min fix: 2.68s 549603 bytes
Nice!
>
> of course evince is an extreme example so a few more
>
> firefox
> 2.066s 404549 bytes
> to
> 1.336s 250585 bytes
>
>
> cupsd
> 0.365s 90834 bytes
> to
> 0.293s 58855 bytes
>
> dnsmasq
> 0.118s 35689 bytes
> to
> 0.112s 27992 bytes
>
>
> smbd
> 0.187s 40897 bytes
> to
> 0.162s 33665 bytes
>
>
> weather applet profile from ubuntu touch
> 0.618s 105673 bytes
> to
> 0.432s 89300 bytes
The deltas will be even larger on ARM. I expect this change to make a
considerable difference there.
>
> I have not seen a case where the parser regresses on performance but it is
> possible. This patch will not cause a regression on generated policy size,
> at worst it will result in policy that is the same size
>
> ---
Acked-by: Tyler Hicks <tyhicks at canonical.com>
I have to admit to not being very familiar with this area of the parser.
The changes look sane to me, but I don't really understand everything
that is going on.
That said, I've tested it and I'll try to add some equality.sh tests
today.
There's one minor spelling change that I pointed out below.
Tyler
>
> === modified file 'parser/libapparmor_re/apparmor_re.h'
> --- parser/libapparmor_re/apparmor_re.h 2013-12-24 11:29:52 +0000
> +++ parser/libapparmor_re/apparmor_re.h 2013-12-24 11:34:56 +0000
> @@ -27,7 +27,6 @@
> #define DFA_CONTROL_TREE_SIMPLE (1 << 2)
> #define DFA_CONTROL_TREE_LEFT (1 << 3)
> #define DFA_CONTROL_MINIMIZE (1 << 4)
> -#define DFA_CONTROL_MINIMIZE_HASH_TRANS (1 << 5)
> #define DFA_CONTROL_FILTER_DENY (1 << 6)
> #define DFA_CONTROL_REMOVE_UNREACHABLE (1 << 7)
> #define DFA_CONTROL_TRANS_HIGH (1 << 8)
>
> === modified file 'parser/libapparmor_re/hfa.cc'
> --- parser/libapparmor_re/hfa.cc 2013-12-24 11:29:52 +0000
> +++ parser/libapparmor_re/hfa.cc 2013-12-24 11:34:30 +0000
> @@ -550,50 +550,46 @@
> /* test if two states have the same transitions under partition_map */
> bool DFA::same_mappings(State *s1, State *s2)
> {
> + /* assumes otherwise is set to best choice, if there are multiple
> + * otherwise choises this will fail to fully minimize the dfa
spelling change: choices
> + * if we are not careful. Make sure in cases with multiple
> + * equiv otherwise we always choose the same otherwise to avoid
> + */
> if (s1->otherwise->partition != s2->otherwise->partition)
> return false;
>
> - if (s1->trans.size() != s2->trans.size())
> - return false;
> -
> - for (StateTrans::iterator j1 = s1->trans.begin(); j1 != s1->trans.end(); j1++) {
> - StateTrans::iterator j2 = s2->trans.find(j1->first);
> - if (j2 == s2->trans.end())
> + StateTrans::iterator j1;
> + StateTrans::iterator j2;
> + for (j1 = s1->trans.begin(), j2 = s2->trans.begin();
> + j1 != s1->trans.end() && j2 != s2->trans.end();
> + /*inc inline*/) {
> + if (j1->first < j2->first) {
> + if (j1->second->partition != s2->otherwise->partition)
> + return false;
> + j1++;
> + } else if (j1->first == j2->first) {
> + if (j1->second->partition != j2->second->partition)
> + return false;
> + j1++;
> + j2++;
> + } else {
> + if (s1->otherwise->partition != j2->second->partition)
> + return false;
> + j2++;
> + }
> + }
> + for ( ; j1 != s1->trans.end(); j1++) {
> + if (j1->second->partition != s2->otherwise->partition)
> return false;
> - if (j1->second->partition != j2->second->partition)
> + }
> + for ( ; j2 != s2->trans.end(); j2++) {
> + if (j2->second->partition != s1->otherwise->partition)
> return false;
> }
>
> return true;
> }
>
> -/* Do simple djb2 hashing against a States transition cases
> - * this provides a rough initial guess at state equivalence as if a state
> - * has a different number of transitions or has transitions on different
> - * trans they will never be equivalent.
> - * Note: this only hashes based off of the alphabet (not destination)
> - * as different destinations could end up being equiv
> - */
> -size_t DFA::hash_trans(State *s)
> -{
> - unsigned long hash = 5381;
> -
> - for (StateTrans::iterator j = s->trans.begin(); j != s->trans.end(); j++) {
> - hash = ((hash << 5) + hash) + j->first;
> - State *k = j->second;
> - hash = ((hash << 5) + hash) + k->trans.size();
> - }
> -
> - if (s->otherwise != nonmatching) {
> - hash = ((hash << 5) + hash) + 5381;
> - State *k = s->otherwise;
> - hash = ((hash << 5) + hash) + k->trans.size();
> - }
> -
> - hash = (hash << 8) | s->trans.size();
> - return hash;
> -}
> -
> int DFA::apply_and_clear_deny(void)
> {
> int c = 0;
> @@ -624,8 +620,6 @@
> for (Partition::iterator i = states.begin(); i != states.end(); i++) {
> size_t hash = 0;
> 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);
> 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()) {
> @@ -730,9 +724,14 @@
> /* update representative state's transitions */
> rep->otherwise = *rep->otherwise->partition->begin();
>
> - for (StateTrans::iterator c = rep->trans.begin(); c != rep->trans.end(); c++) {
> + for (StateTrans::iterator c = rep->trans.begin(); c != rep->trans.end(); ) {
> Partition *partition = c->second->partition;
> - c->second = *partition->begin();
> + if (rep->otherwise != *partition->begin()) {
> + c->second = *partition->begin();
> + c++;
> + } else
> + /* transition is now covered by otherwise */
> + c = rep->trans.erase(c);
> }
>
> //if ((*p)->size() > 1)
>
> === modified file 'parser/libapparmor_re/hfa.h'
> --- parser/libapparmor_re/hfa.h 2013-12-24 11:29:52 +0000
> +++ parser/libapparmor_re/hfa.h 2013-12-24 11:34:41 +0000
> @@ -488,7 +488,6 @@
>
> void remove_unreachable(dfaflags_t flags);
> bool same_mappings(State *s1, State *s2);
> - size_t hash_trans(State *s);
> void minimize(dfaflags_t flags);
> int apply_and_clear_deny(void);
>
>
> === modified file 'parser/parser_main.c'
> --- parser/parser_main.c 2013-12-24 11:29:52 +0000
> +++ parser/parser_main.c 2013-12-24 11:35:31 +0000
> @@ -247,8 +247,6 @@
> { 2, "expr-right-simplify", "right simplification first",
> DFA_CONTROL_TREE_LEFT },
> { 1, "minimize", "dfa state minimization", DFA_CONTROL_MINIMIZE },
> - { 1, "hash-trans", "minimization - hash transitions during setup",
> - DFA_CONTROL_MINIMIZE_HASH_TRANS },
> { 1, "filter-deny", "filter out deny information from final dfa",
> DFA_CONTROL_FILTER_DENY },
> { 1, "remove-unreachable", "dfa unreachable state removal",
>
>
>
> --
> AppArmor mailing list
> AppArmor at lists.ubuntu.com
> Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
-------------- 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/20131224/b45f4171/attachment.pgp>
More information about the AppArmor
mailing list