[apparmor] [patch] Fix dfa minimization
John Johansen
john.johansen at canonical.com
Tue Dec 24 12:33:07 UTC 2013
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
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
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
---
=== 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
+ * 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",
More information about the AppArmor
mailing list