Minimisation
fewer states for AppArmor developers for security researchers
After the deny masks are folded away the minimizer puts states with equal permissions into partitions and splits them until every member of a partition behaves alike. One state per partition survives - 22 of 38 for the example. Two further passes are off by default. One removes unreachable states and one maps bytes to equivalence classes.
On the map: the dfa engine
▶ Watch this deck — 9 scenes, ~7 min
Worth seeing first
- Building the DFA — the thirty-eight states this deck reduces
- Permissions in the DFA — the five masks that decide which states may merge
Part of journeys
- From profile text to kernel tables, step 10 of 13 · previous: Permissions in the DFA · next: Table compression
01 Thirty-eight states, twenty-two needed
Filter deny, then minimize (on by default): 38 states become 22. remove-unreachable and equiv exist and are off by default.
The deck on building the DFA left us with thirty-eight states for three rules. The compiled profile has twenty-two. This deck is about the sixteen that went, and about the general method: merging states that nobody could tell apart from outside. It comes as one main pass, partition refinement, with a preparation step in front of it, filter deny, that turns out to do most of the work for our example. Then there are two more passes that the parser has but doesn't run unless you ask: removing unreachable states, and equivalence classes. The deck on how the kernel checks an access showed a machine where nothing could be merged. Here's one where a lot can.
Details and sources
Details
-D statsprintsMinimized dfa: final partitions N (accept A) init I (accept B)(hfa.cc:896-900): N states are left, A of them accepting; refinement started from I partitions, B of them with permissions.- The order in
create_chfa: filter deny, minimize, remove unreachable, equivalence classes (aare_rules.cc:273-308). - Defaults (parser_common.c:123-129):
filter-denyandminimizeare on;remove-unreachableandequivare off. - The numbers are for the file DFA of the three-rule profile
demo3.sd, from the parser built from the AppArmor tree with nothing loaded into a kernel. They are the same with the tree'sabi/5.0feature set and with one that has the kernel'spolicyentries. - Seen the machine walked? That is How the kernel checks an access.
Read more
- wiki: TechnicalDoc_HFA on minimization by partition. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
- Building the DFA, How the kernel checks an access.
02 First, forget the deny masks
DFA::apply_and_clear_deny runs before minimize when filter-deny is set or the DFA has no extended permissions (aare_rules.cc:273-278). Without it the example keeps all 38 states.
The minimizer may only merge states with identical permissions. Straight out of the construction, state thirty-seven, where the SSH paths end, has a deny mask, so it's different from everything else. But the permissions deck showed what filter deny does: subtract deny from allow, then zero the deny mask. Our audit deny rule allowed nothing and has no quiet bits, so after the filter, state thirty-seven has no permissions at all. And since it only loops to itself, it now behaves exactly like state zero: nothing allowed, no way out. Switch the filter off and the minimizer finds nothing to remove: thirty-eight partitions for thirty-eight states.
Details and sources
Details
int DFA::apply_and_clear_deny(void)(hfa.cc:685-693) calls the per-state function (hfa.h:349-356), which works on the permission set (hfa.h:106-130):allow &= ~deny; prompt &= ~deny; deny = 0.auditandquietare left as computed. A plaindenyhas quiet bits, so its state stays accepting and does not merge into state 0; anaudit deny, as in the example, has none.- A state whose masks all become zero lands in the starting partition of the states without permissions.
- The call is made when
permstable32_version < 2orfilter-denyis set (aare_rules.cc:273-278); the flag is on by default, with a TODO to remove it (parser_common.c:125-129). - The dumps are from the three-rule example with
-D dfa-states-initialand-D dfa-states-post-filter, parser of the AppArmor tree, feature set with the kernel'spolicyentries. The line for-O no-filter-denywas recorded with the tree'sabi/5.0feature set. - Known discrepancy: a deny rule cannot be told from "no rule" in the permission table, with or without
filter-deny; with-O no-filter-denythe 16 extra states are kept and the table rows still carry no deny bit.
Read more
- Permissions in the DFA, scene "What becomes of a deny rule".
- allow and deny.
03 Start: one partition per permission set
Starting partitions: the start state alone, every other state by the content of its perms_t (hfa.cc:742-768). Example: 4 partitions, init 4 (accept 2).
Partition refinement starts optimistic: assume as many states as possible are the same, then split where that's wrong. But one thing isn't negotiable. Two states with different permissions give different answers, so they start in different partitions. Here's the real starting position for our example. Partition zero holds state zero and every other state without permissions, thirty-five in all, including the whole former deny chain. Partition one is the start state on its own: it's kept apart on purpose and isn't merged with anything. And the two accepting states that survived the filter get a partition each. Four partitions. The first state listed in each is its representative.
Details and sources
Details
void DFA::minimize(optflags const &flags)(hfa.cc:732-936). The starting partitions are made with aPermMapkeyed throughderef_less_than_perms(hfa.cc:729, hfa.cc:742-768): the start state alone, every other state by the content of its permission set. The non-matching state shares a partition with every other state without permissions.- The dump is printed by hfa.cc:711-727, called at hfa.cc:770-771. The slide shortens the first line; the dump is from the three-rule example, parser of the AppArmor tree, feature set with the kernel's
policyentries. The addresses change from run to run. The complete dump is in the reference under the deck. -D dfa-minimize-uniq-permsprints the permission sets seen by the minimizer (aare_rules.cc:281-282).- Known discrepancy:
-D dfa-minimize-partitionsprints the address of the permission set (hfa.cc:720): aperms_t *is passed where the printer takes a reference. - Known discrepancy:
perms_t::operator<comparesaudittwice (hfa.h:151-154); no effect on the ordering.
Read more
04 Split until nothing splits
Refinement (hfa.cc:791-827): members that differ from the representative under same_mappings move out into a new partition, which is refined in turn; repeat until a pass makes no split. Example: 4 partitions become 22; 16 states join state 0.
Now the refining. Go through each partition, and compare every member with the representative. Two states stay together only if, for every input, they lead into the same partition. State zero's default leads to partition zero. State thirty-two's default leads to state thirty-five, which is in another partition. Different, so thirty-two moves out. State thirty-seven loops to itself, and itself is still in partition zero. Same, so it stays. The states next to the accepting ones leave first, then the states that lead to those, back along the two live chains. At the end, partition zero holds state zero and the sixteen states of the deny chain, and every other state is alone.
Details and sources
Details
- The pass (hfa.cc:791-827): for each partition, every member is compared with the first member, the representative; members that differ move to one new partition inserted after the current one. The loop repeats until a pass makes no new partition.
same_mappings(s1, s2)(hfa.cc:643-683) returns false at once when theotherwisetargets are in different partitions. Otherwise it walks the two sorted transition maps and compares the partition of each target, using the other state'sotherwisewhere one of them has no explicit entry.- If the number of partitions equals the number of states, the function stops and prints
Dfa minimization no states removed: partitions N ...(hfa.cc:829-836). - The two comparison cards and the order in which states leave partition 0 are derived from the state dump and the loop; the parser prints only the starting position and the "Pre-remap" position. The last line of the slide is a shortened form of the "Pre-remap" dump, which is in the reference under the deck.
- Why the deny chain stays with state 0 (derived): {37} has no permissions and its only target is itself; {36} leads only to {37}; and so on back to {4} and {5}. None of them can reach a state outside the partition.
- Not determined: whether the loop can be quadratic on real profiles (2387 states take well under a second).
Read more
05 Keep one state per partition
Remap (hfa.cc:849-927): transitions go to representatives, a transition equal to otherwise is erased, non-representatives are deleted. Survivors of the example: {0} {1} {2} {3} {6} {7} {10} {11} {14} {15} {18} {19} {22} {23} {25} {26} {28} {29} {31} {32} {34} {35}.
The result is applied in one sweep. In each partition the representative survives, and its transitions are pointed at the representatives of wherever they used to go. State two used to have explicit transitions on h and on r, into the deny chain. Those states are now state zero, and state zero is already state two's default. A transition that equals the default isn't stored, so it's erased. State two is left with e and u. The other members of each partition are deleted, the non-matching and start pointers are re-aimed, and the stats line reports twenty-two final partitions, two of them accepting. The survivors keep their old labels, with gaps.
Details and sources
Details
- Remap (hfa.cc:849-867): the first state of each partition is kept; its transitions are redirected to representatives, and a transition that now equals
otherwiseis erased. - The other members get label -1 and are deleted (hfa.cc:871-874, hfa.cc:920-927);
nonmatchingandstartare re-pointed (hfa.cc:904-914). The stats line is printed at hfa.cc:896-900. - The before and after of state {2} is derived from the initial state dump and the packed dump, where state 2 has entries for
eanduonly. - Label to row number in the packed tables: {0} 0, {1} 1, {2} 2, {3} 3, {6} 4, {7} 5, {10} 6, {11} 7, {14} 8, {15} 9, {18} 10, {19} 11, {22} 12, {23} 13, {25} 14, {26} 15, {28} 16, {29} 17, {31} 18, {32} 19, {34} 20, {35} 21.
- Error:
Minimization different permissions in same partion, astd::runtime_error(hfa.cc:881-883); the comment says it cannot happen at present. - Known discrepancy: that
std::runtime_erroris not caught by thecatch (int)ofcreate_chfa. -D dfa-states-post-minimizeprints the states after this step.parser/tst/minimize.shchecks state counts for small profiles.
Read more
06 What will not merge
Not merged: states with different permission sets (30 created, 29 kept), and equivalent states whose otherwise targets are in different partitions (hfa.cc:645-651; 7 states where 6 would do). States that really differ, like those of the x??? family, stay as well.
Two limits are worth knowing. First, permissions. Take four overlapping wildcard rules that all say read, and twenty-three states shrink to sixteen. Give the same four paths four different permissions, and thirty states only go down to twenty-nine, because states that answer differently start apart and stay apart. Second, a limit of this implementation. The comparison gives up as soon as two states' defaults differ. So a class written as a long positive list, and the same class written as anything but slash, give states that behave the same and are stored differently, and they stay separate. It costs table space, not correctness.
Details and sources
Details
- The rows were measured with the parser built from the AppArmor tree,
abi/5.0feature set, one profile each (-D dfa-statsand-D stats): states created and states kept, file DFA. same_mappingsreturns false at once when theotherwisetargets of the two states are in different partitions (hfa.cc:650-651); the comment at hfa.cc:645-649 says the function "will fail to fully minimize" in that case.- The two representations:
[\x01-.0-\xff]is 254 explicit transitions withotherwiseleading to state 0;[^/\x00], which is what?becomes, isotherwiseleading to the target with two explicit transitions to state 0. Both accept the same bytes. - Effect: larger tables for profiles that use wide positive character classes. Matching is not affected.
- The start state is never merged with another state (hfa.cc:742-768).
- Known discrepancy: minimization leaves equivalent states apart when their
otherwisetargets differ, so the result is not always minimal.
Read more
- Building the DFA: the scenes on
otherwiseand on which rules make a profile big. - wiki: TechnicalDoc_HFA.
07 Remove unreachable: a pass with nothing to do for AppArmor developers
DFA::remove_unreachable (hfa.cc:590-640), only with -O remove-unreachable. On the example it changes nothing: 38 states with -O remove-unreachable -O no-minimize.
The second pass is short. remove_unreachable begins at the start state, follows every default and every explicit transition, marks what it reaches, and deletes the rest. State zero is always kept. You turn it on with the remove-unreachable optimisation flag. On our example it removes nothing, and that's what you'd expect. Subset construction only ever creates a state because some transition leads to it, and minimization keeps one state per partition and re-points everything. So in the pipeline as it stands there's nothing unreachable to find, and the pass is off by default.
Details and sources
Details
void DFA::remove_unreachable(optflags const &flags)(hfa.cc:590-640): a work queue fromstartoverotherwiseand explicit transitions;nonmatchingis always kept; unreached states are erased and deleted.- It is called only with
-O remove-unreachable(aare_rules.cc:287-291), which is off by default (parser_common.c:123-129). - When it removes something it prints
DFA: states N removed C unreachable states(hfa.cc:636-638).-D dfa-unreachableand-D dfa-states-post-unreachableshow the result. - On the three-rule example the option changes nothing: 38 states with
-O remove-unreachable -O no-minimize(parser of the AppArmor tree,abi/5.0feature set). - Known discrepancy: the
<==start marker in thedfa-unreachabledump cannot print, since the start state is always reachable (hfa.cc:623-624).
Read more
08 Equivalence classes: fewer columns
DFA::equivalence_classes and apply_equivalence_classes (hfa.cc:1300-1361, 1389-1404), only with -O equiv. The class table is a 256-byte YYTD_ID_EC table; the kernel maps each byte through it (linux:security/apparmor/match.c:486-494).
The third pass doesn't remove states, it narrows them. Most of the two hundred and fifty-six byte values are treated identically by every state: no rule mentions a tilde, say. The equiv option groups bytes that always lead to the same place into classes, numbers them from one, and rewrites every transition to use the class number. Bytes that no rule names fall into class zero. The mapping is written into the policy as a two hundred and fifty-six byte table, and the kernel translates each input byte through it before the lookup. In the one real-sized profile measured, seventeen hundred states, the table came out a little larger with it than without. It's off by default.
Details and sources
Details
map<transchar, transchar> DFA::equivalence_classes(optflags const &flags)(hfa.cc:1300-1361) andvoid DFA::apply_equivalence_classes(map<transchar, transchar> &eq)(hfa.cc:1389-1404).- Classes are numbered from 1. For each state the characters that lead to the same target are grouped, and a class is split when only part of it is used by a group (hfa.cc:1305-1355). Out of band characters are skipped (hfa.cc:1309-1310). Bytes that no rule names have no class and map to 0.
- Stats:
Equiv class reduces to N classes(hfa.cc:1357-1359). - The table is written as a 256-byte
YYTD_ID_ECtable (chfa.cc:450-456, chfa.cc:505-507) and applied by the kernel per byte (match.c:486). - The dump on the slide is from
profile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*)with-O equiv -D equiv, parser of the AppArmor tree,abi/5.0feature set. - Measured on a profile with the
base,nameserviceanduser-tmpabstractions (1695 states, kernel featuresabi/5.0plusdiff-encode): 2495 next/check slots with-O equivagainst 2476 without, and 44009 bytes of-Soutput against 42905. One profile was measured. - Kernel statements are read from the kernel source and were not run.
- Known discrepancy:
apply_equivalence_classesre-inserts only transitions with a non-negative character (hfa.cc:1395-1402), so out of band transitions are lost. For thexaprofile the default compile has2: (12, 11) {11} -> {12}and base 536870915 for state 11; with-O equivstate 11 has base 10 and no entry to state 12. The kernel returnsDFA_NOMATCHfor a state without the flag (match.c:590). The option is off by default. - Measured on two profiles, and the arrays grew on both: the three-rule example from 277 to 288 next/check slots, and the 1695-state profile from 2476 to 2495. In the example the 256-slot tail past the highest base stays, and with every entry in columns 1 to 15 the combs collide more, so the highest base rises from 21 to 32; see How the tables are packed. Not determined: whether any profile gets shorter arrays with the option.
09 Where to go from here
Next: table compression. Back: permissions in the DFA, building the DFA, the backend pipeline. Tests: testing AppArmor.
So: fold deny away, start with one partition per permission set and the start state alone, split until a pass changes nothing, and keep one state per partition. Thirty-eight became twenty-two, and all sixteen that went belonged to a deny rule that overlapped nothing. The two extra passes are there if you want to experiment. The table compression deck takes these twenty-two states and packs their transitions into the arrays the kernel walks. And the permissions deck is the place to go back to if the starting partitions weren't clear.
Details and sources
Details
- The algorithm in four lines: zero the deny masks; put the start state alone and group every other state by its permission set; split each partition by comparing members with its representative until a pass splits nothing; keep the representative of each partition.
- The example: 38 states, 4 starting partitions, 22 final partitions; the 16 states that went are the deny rule's.
- Table compression: the next stage. Permissions in the DFA, Building the DFA, The backend pipeline.
- allow and deny: why a deny rule can cost no states at all. Testing AppArmor:
minimize.sh. Matching at run time: where the kernel applies an equivalence class table. - Sources for this deck: AppArmor 836052d21 and Linux 97d73c825.
Read more
Basis of the statements on this page: "tree" means the parser built from the AppArmor commit 836052d21 (6.0.0~alpha2) was run (-Q -K with the -D and -O options shown), with nothing loaded into a kernel. The dumps of the three-rule profile were made with a feature set that has the policy entries the kernel exports, and its state counts are the same with the tree's abi/5.0 file; the other measurements were made with abi/5.0. "code" means the parser source, or the kernel source, was read and not run; "derived" means the result was reasoned from that code. Nothing here was observed on a running kernel.
Stage order
| Stage | Call in create_chfa | Runs when |
|---|---|---|
| filter deny | dfa.apply_and_clear_deny() (aare_rules.cc:273-278) | permstable32_version < 2, or filter-deny (default on) |
| minimize | dfa.minimize(opts) (aare_rules.cc:279-285) | minimize (default on) |
| remove unreachable | dfa.remove_unreachable(opts) (aare_rules.cc:287-291) | remove-unreachable (default off) |
| equivalence classes | dfa.equivalence_classes, apply_equivalence_classes (aare_rules.cc:298-308) | equiv (default off) |
All rows: code.
Filter deny
allow &= ~deny; prompt &= ~deny; deny = 0; audit and quiet are kept (hfa.h:106-130) (code).- The example: with it 22 states, with
-O no-filter-deny38 (Dfa minimization no states removed: partitions 38 init 5 (accept 3)) (tree).
Partition refinement
- Starting partitions: the start state alone; every other state by the content of its permission set (hfa.cc:742-768) (code).
same_mappings(s1, s2): false when theotherwisetargets are in different partitions; otherwise the partitions of the targets of all explicit transitions are compared (hfa.cc:643-683) (code).- One pass: members that differ from the representative move to one new partition; passes repeat until one makes no partition (hfa.cc:791-827) (code).
- Stop: no merging when the number of partitions equals the number of states (hfa.cc:829-836) (code).
- Remap: keep the representative, redirect transitions, erase a transition equal to
otherwise, delete the rest (hfa.cc:849-927) (code).
| Stats line | Fields |
|---|---|
Minimized dfa: final partitions N (accept A) init I (accept B) | N states left, A accepting; I starting partitions, B with permissions |
Dfa minimization no states removed: partitions N init I (accept B) | nothing merged |
The example
-D dfa-minimize-partitions, file DFA of the three rules (tree; the addresses change from run to run; blank lines removed):
Dumping Minimization partition mapping: Initial
[0] 0x6488b88ea3d0: {0} : {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17}, {18}, {19}, {20}, {21}, {22}, {23}, {24}, {25}, {26}, {27}, {28}, {29}, {30}, {31}, {32}, {33}, {36}, {37},
[1] 0x6488b88ea3d0: {1} :
[2] 0x6488b89064c0: {34} :
[3] 0x6488b8906660: {35} :
Dumping Minimization partition mapping: Pre-remap
[0] 0x6488b88ea3d0: {0} : {4}, {5}, {8}, {9}, {12}, {13}, {16}, {17}, {20}, {21}, {24}, {27}, {30}, {33}, {36}, {37},
[1] 0x6488b88ea3d0: {2} :
[2] 0x6488b88ea3d0: {3} :
[3] 0x6488b88ea3d0: {6} :
[4] 0x6488b88ea3d0: {7} :
[5] 0x6488b88ea3d0: {10} :
[6] 0x6488b88ea3d0: {11} :
[7] 0x6488b88ea3d0: {14} :
[8] 0x6488b88ea3d0: {15} :
[9] 0x6488b88ea3d0: {18} :
[10] 0x6488b88ea3d0: {19} :
[11] 0x6488b88ea3d0: {22} :
[12] 0x6488b88ea3d0: {23} :
[13] 0x6488b88ea3d0: {25} :
[14] 0x6488b88ea3d0: {26} :
[15] 0x6488b88ea3d0: {28} :
[16] 0x6488b88ea3d0: {29} :
[17] 0x6488b88ea3d0: {31} :
[18] 0x6488b88ea3d0: {32} :
[19] 0x6488b88ea3d0: {1} :
[20] 0x6488b89064c0: {34} :
[21] 0x6488b8906660: {35} :
Partitions after minimization
{0} : {4}, {5}, {8}, {9}, {12}, {13}, {16}, {17}, {20}, {21}, {24}, {27}, {30}, {33}, {36}, {37},
{2} :
{3} :
{6} :
{7} :
{10} :
{11} :
{14} :
{15} :
{18} :
{19} :
{22} :
{23} :
{25} :
{26} :
{28} :
{29} :
{31} :
{32} :
{1} :
{34} :
{35} :
{1} <== (allow/deny/prompt/audit/quiet)
{2}(0x 4/0//0/0/0)
{3}(0x 4/0//0/0/0)
{4}(0x 4/0//0/0/0)
{1} perms: none
0x2 -> {2} (0x 4/0//0/0/0)
\a 0x7 -> {2} (0x 4/0//0/0/0)
\t 0x9 -> {2} (0x 4/0//0/0/0)
\n 0xa -> {2} (0x 4/0//0/0/0)
0xe -> {2} (0x 4/0//0/0/0)
0xf -> {3} (0x 4/0//0/0/0)
0x11 -> {2} (0x 4/0//0/0/0)
0x15 -> {4} (0x 4/0//0/0/0)
0x16 -> {4} (0x 4/0//0/0/0)
\ 0x20 -> {2} (0x 4/0//0/0/0)
{3} perms: (0x 4/0//0/0/0)
0x0 -> {5}
{5} perms: none
1 0x31 -> {2} (0x 4/0//0/0/0)
Dumping Minimization partition mapping: Initial
[0] 0x6488b88fec40: {0} : {5},
[1] 0x6488b88fec40: {1} :
[2] 0x6488b88fde50: {2} : {3}, {4},
Dumping Minimization partition mapping: Pre-remap
[0] 0x6488b88fec40: {0} :
[1] 0x6488b88fec40: {5} :
[2] 0x6488b88fec40: {1} :
[3] 0x6488b88fde50: {2} : {4},
[4] 0x6488b88fde50: {3} :
| Label | Row in the packed tables | Path so far |
|---|---|---|
| {0} | 0 | no match; also the 16 states of the deny rule |
| {1} | 1 | start |
| {2} | 2 | / |
| {3} {7} {11} {15} {19} {23} {26} {29} | 3 5 7 9 11 13 15 17 | /e to /etc/demo |
| {32} | 19 | /etc/demo/ |
| {35} | 21 | /etc/demo/ plus one or more characters |
| {6} {10} {14} {18} {22} {25} {28} | 4 6 8 10 12 14 16 | /u to /usr/bin |
| {31} | 18 | /usr/bin/ |
| {34} | 20 | /usr/bin/ plus a lower-case letter and any non-slash characters |
Measured
| Rules | Created | Kept |
|---|---|---|
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r, | 23 | 16 |
the same four paths with r, w, rw, k | 30 | 29 |
/**/a/**/b/**/c r, | 20 | 14 |
base, nameservice, user-tmp abstractions and one rule | 2387 | 1695 |
/srv/**x?????? r, | 134 | 134 |
100 rules /srv/file100 to /srv/file199 | 14 | 14 |
/a[\x01-.0-\xff]z r, and /b?z r, | 7 | |
/a?z r, and /b?z r, | 6 |
Tree, abi/5.0.
remove_unreachable
- A work queue from the start state over
otherwiseand explicit transitions; state 0 is always kept; the rest is erased (hfa.cc:590-640) (code). - Option
-O remove-unreachable; statsDFA: states N removed C unreachable states(code). On the example it removes nothing (tree).
Equivalence classes
- Bytes that every state treats alike get one class number, from 1; bytes no rule names map to 0 (hfa.cc:1300-1361) (code).
- Written as a 256-byte
YYTD_ID_ECtable; the kernel maps every input byte through it (match.c:486) (code). - Dump,
-O equiv -D equiv, forprofile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*)(tree):
DFA equivalence class (eq): 1: / 2: u ... 9: \x0
- Measured on the 1695-state profile: 2495 next/check slots against 2476 without, 44009 bytes of
-Sagainst 42905 (tree,abi/5.0plusdiff-encode).
Dumps
| Option | Shows |
|---|---|
dfa-states-post-filter | the states after filter deny |
dfa-states-post-minimize | the states after the remap |
dfa-states-post-unreachable | the states after remove_unreachable |
dfa-minimize-partitions | Initial, Pre-remap, Partitions after minimization |
dfa-minimize-uniq-perms | the permission sets seen by the minimizer |
dfa-unreachable | the states that were removed |
equiv, equiv-stats | the class table and the number of classes |
Errors
Minimization different permissions in same partion: astd::runtime_error(hfa.cc:881-883); the source comment says it cannot happen at present (code).
Known discrepancies
- Equivalent states whose
otherwisetargets differ are not merged (hfa.cc:645-651) (tree). - With
-O equivout of band transitions are dropped (hfa.cc:1395-1402) (tree). -D dfa-minimize-partitionsprints addresses of permission sets (hfa.cc:720) (tree).perms_t::operator<comparesaudittwice (hfa.h:151-154) (code).-D dfa-minimizeis accepted and has no effect (code).- The start marker of the
dfa-unreachabledump cannot print (hfa.cc:623-624) (code).
Not determined
- Whether
-O equivreduces the table of any profile. Measured on two profiles, and the arrays grew on both: the three-rule example from 277 to 288 next/check slots, and the 1695-state profile from 2476 to 2495. In the example the 256-slot tail past the highest base stays, and with every entry in columns 1 to 15 the combs collide more, so the highest base rises from 21 to 32; see How the tables are packed. - Whether the refinement loop can be quadratic on real profiles.
Roads from here
START HERE
- How the kernel checks an access — a machine where nothing could be merged
QUALIFIERS
- allow and deny — why a deny rule can cost no states at all
IN THE KERNEL
- Matching at run time — where the kernel applies an equivalence class table
THE DFA ENGINE · libapparmor_re
- Building the DFA — where the 38 states came from
- Permissions in the DFA — the masks that decide the starting partitions
- Table compression — the next stage where the surviving rows are packed
- How the tables are packed — an interactive lab on packing the 22 states and on what equivalence classes cost
- The backend pipeline — the stage list and the default options
TESTING
- Testing AppArmor (no slides yet) — minimize.sh and its expected state counts