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

Part of journeys

01 Thirty-eight states, twenty-two needed

MINIMISATION 1 2 /etc/demo/ 35 /usr/bin/ 34 /home/*/.ssh/ /root/.ssh/ 37 38 -> 22 the sixteen that went minimize on filter deny runs first remove-unreachable off equiv off Minimized dfa: final partitions 22 (accept 2) init 4 (accept 2)
The machine of the three rules with its four chains; the two chains of the deny rule and their end state can be merged away, leaving 22 of 38 states; filter deny and minimize run by default, remove-unreachable and equiv are off

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 stats prints Minimized 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-deny and minimize are on; remove-unreachable and equiv are 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's abi/5.0 feature set and with one that has the kernel's policy entries.
  • Seen the machine walked? That is How the kernel checks an access.

Read more

02 First, forget the deny masks

-D dfa-states-post-filter initial {36} perms: none[^\x0/] -> {37} (0x 0/3800e//0/0/0){37} perms: (0x 0/3800e//0/0/0)[^\x0] -> {37} (0x 0/3800e//0/0/0) allow &= ~deny; deny = 0 post-filter {36} perms: none[^\x0/] -> {37}{37} perms: none[^\x0] -> {37} 37 0 no permissions, and every path from 37 stays in 37: it now behaves exactly like state 0 -O no-filter-deny Dfa minimization no states removed: partitions 38 init 5 (accept 3)
States 36 and 37 of the deny rule before and after filter deny: the deny mask 0x3800e is gone, state 37 has no permissions and only loops to itself, so it behaves like state 0; with -O no-filter-deny the minimizer removes no states

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.
  • audit and quiet are left as computed. A plain deny has quiet bits, so its state stays accepting and does not merge into state 0; an audit 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 < 2 or filter-deny is 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-initial and -D dfa-states-post-filter, parser of the AppArmor tree, feature set with the kernel's policy entries. The line for -O no-filter-deny was recorded with the tree's abi/5.0 feature 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-deny the 16 extra states are kept and the table rows still carry no deny bit.

Read more

03 Start: one partition per permission set

-D dfa-minimize-partitions Dumping Minimization partition mapping: Initial[0] 0x6488b88ea3d0: {0} : {2}, {3}, {4}, ... {33}, {36}, {37},[1] 0x6488b88ea3d0: {1} :[2] 0x6488b89064c0: {34} :[3] 0x6488b8906660: {35} : 0 [0] no permissions: 35 states, representative 0 1 [1] the start state, always alone 34 [2] exec 35 [3] read init 4 (accept 2): four starting partitions, two of them with permissions known discrepancy: the value before the colon is the address of the permission set, not its content
The four starting partitions of the example: partition 0 with the 35 states that have no permissions, partition 1 with the start state alone, and one partition each for the accepting states 34 and 35

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 a PermMap keyed through deref_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 policy entries. The addresses change from run to run. The complete dump is in the reference under the deck.
  • -D dfa-minimize-uniq-perms prints the permission sets seen by the minimizer (aare_rules.cc:281-282).
  • Known discrepancy: -D dfa-minimize-partitions prints the address of the permission set (hfa.cc:720): a perms_t * is passed where the printer takes a reference.
  • Known discrepancy: perms_t::operator< compares audit twice (hfa.h:151-154); no effect on the ordering.

04 Split until nothing splits

REFINE 02345...293132333637 same_mappings(0, 32)? otherwise: 0 -> [0] 32 -> {35} in [3] different partitions: split same_mappings(0, 37)? otherwise: 37 -> {37}, still in [0] same: stays 31 32 first to leave: the two states whose transitions reach an accepting state they leave together and are separated in the same pass then 28 and 29, then 25 and 26, and so on back to 2: 18 states end up alone partition [0] keeps 0 4 5 8 9 12 13 16 17 20 21 24 27 30 33 36 37 Pre-remap: [0] {0} : {4}, {5}, {8}, ... {36}, {37}, [1] {2} ... [19] {1} [20] {34} [21] {35}
Partition 0 being refined: state 32 differs from the representative 0 because its default leads into another partition, so it is split off; state 37 loops to itself inside partition 0 and stays; the split works back along the two live chains until 18 states are alone and 16 states remain with state 0

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 the otherwise targets are in different partitions. Otherwise it walks the two sorted transition maps and compares the partition of each target, using the other state's otherwise where 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).

05 Keep one state per partition

REMAP 1 / 2 e 3 u 6 h 4 r 5 0 now state 0 target == otherwise: transition erased state 2 keeps e and u 0 1 2 3 6 7 10 11 14 15 18 19 22 23 25 26 28 29 31 32 34 35 the 22 survivors Minimized dfa: final partitions 22 (accept 2) init 4 (accept 2) labels keep their gaps; the packer renumbers them 0 to 21
State 2 before and after the remap: its transitions on h and r led to states 4 and 5, which are now state 0, the default of state 2, so both transitions are erased; the 22 surviving states keep their labels with gaps

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 otherwise is erased.
  • The other members get label -1 and are deleted (hfa.cc:871-874, hfa.cc:920-927); nonmatching and start are 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 e and u only.
  • 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, a std::runtime_error (hfa.cc:881-883); the comment says it cannot happen at present.
  • Known discrepancy: that std::runtime_error is not caught by the catch (int) of create_chfa.
  • -D dfa-states-post-minimize prints the states after this step. parser/tst/minimize.sh checks state counts for small profiles.

06 What will not merge

LIMITS /srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r,23 -> 16 the same four paths with r, w, rw, k30 -> 29different answers: different starting partitions source comment at same_mappings: "will fail to fully minimize" when otherwise differs /a[\x01-.0-\xff]z r, /b?z r,7 states /a?z r, /b?z r,6 statessame behaviour; in the first, one default is written as 254 explicit transitions it costs table space, not correctness
Measured limits of minimization: four overlapping globs with one permission go from 23 states to 16, with four different permissions only from 30 to 29; a wildcard with a fixed-length tail keeps all 134 states; and two rule sets with the same behaviour give 7 states or 6 depending on how a character class is written

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.0 feature set, one profile each (-D dfa-stats and -D stats): states created and states kept, file DFA.
  • same_mappings returns false at once when the otherwise targets 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 with otherwise leading to state 0; [^/\x00], which is what ? becomes, is otherwise leading 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 otherwise targets differ, so the result is not always minimal.

Read more

07 Remove unreachable: a pass with nothing to do for AppArmor developers

-O remove-unreachable 1 work queue from start: otherwise + explicit transitions ? not reached: erased 0 state 0: always kept $ apparmor_parser -Q -K -O remove-unreachable -O no-minimize -D dfa-stats demo3.sdCreated dfa: states 38 ... the example: nothing removed stats line when it finds any: DFA: states N removed C unreachable states
remove_unreachable walks from the start state over default and explicit transitions and erases states it cannot reach; state 0 is always kept; on the example nothing is removed

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 from start over otherwise and explicit transitions; nonmatching is 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-unreachable and -D dfa-states-post-unreachable show 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.0 feature set).
  • Known discrepancy: the <== start marker in the dfa-unreachable dump cannot print, since the start state is always reachable (hfa.cc:623-624).

08 Equivalence classes: fewer columns

-O equiv \x0 / u 256 byte values 0 1 2 3 4 5 6 7 8 9 classes, numbered from 1 bytes no rule names: class 0 DFA equivalence class(eq):1: /2: u...9: \x0 a different profile, -D equiv c = equiv[c] per input byte, before the table lookup; 256 bytes in the policy 1695 states: 2495 slots with equiv, 2476 without measured on one profile: no gain known discrepancy: with -O equiv out of band transitions are dropped, so xattrs= conditions cannot match
With -O equiv the 256 byte values are mapped to a few classes: slash is class 1, u is class 2, NUL is class 9 and every byte that no rule names is class 0; the kernel translates each input byte through the table before the lookup; on a 1695-state profile the table was not smaller

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) and void 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_EC table (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.0 feature set.
  • Measured on a profile with the base, nameservice and user-tmp abstractions (1695 states, kernel features abi/5.0 plus diff-encode): 2495 next/check slots with -O equiv against 2476 without, and 44009 bytes of -S output against 42905. One profile was measured.
  • Kernel statements are read from the kernel source and were not run.
  • Known discrepancy: apply_equivalence_classes re-inserts only transitions with a non-negative character (hfa.cc:1395-1402), so out of band transitions are lost. For the xa profile the default compile has 2: (12, 11) {11} -> {12} and base 536870915 for state 11; with -O equiv state 11 has base 10 and no entry to state 12. The kernel returns DFA_NOMATCH for 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

ROADS 22 states Table compression22 rows into 277 slots Permissions in the DFAthe starting partitions Building the DFAwhere the states came from Testing AppArmorminimize.sh
Roads from this deck: table compression, permissions in the DFA, building the DFA, testing AppArmor and the backend pipeline

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

StageCall in create_chfaRuns when
filter denydfa.apply_and_clear_deny() (aare_rules.cc:273-278)permstable32_version < 2, or filter-deny (default on)
minimizedfa.minimize(opts) (aare_rules.cc:279-285)minimize (default on)
remove unreachabledfa.remove_unreachable(opts) (aare_rules.cc:287-291)remove-unreachable (default off)
equivalence classesdfa.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-deny 38 (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 the otherwise targets 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 lineFields
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} :
LabelRow in the packed tablesPath so far
{0}0no match; also the 16 states of the deny rule
{1}1start
{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

RulesCreatedKept
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r,2316
the same four paths with r, w, rw, k3029
/**/a/**/b/**/c r,2014
base, nameservice, user-tmp abstractions and one rule23871695
/srv/**x?????? r,134134
100 rules /srv/file100 to /srv/file1991414
/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 otherwise and explicit transitions; state 0 is always kept; the rest is erased (hfa.cc:590-640) (code).
  • Option -O remove-unreachable; stats DFA: 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_EC table; the kernel maps every input byte through it (match.c:486) (code).
  • Dump, -O equiv -D equiv, for profile 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 -S against 42905 (tree, abi/5.0 plus diff-encode).

Dumps

OptionShows
dfa-states-post-filterthe states after filter deny
dfa-states-post-minimizethe states after the remap
dfa-states-post-unreachablethe states after remove_unreachable
dfa-minimize-partitionsInitial, Pre-remap, Partitions after minimization
dfa-minimize-uniq-permsthe permission sets seen by the minimizer
dfa-unreachablethe states that were removed
equiv, equiv-statsthe class table and the number of classes

Errors

  • Minimization different permissions in same partion: a std::runtime_error (hfa.cc:881-883); the source comment says it cannot happen at present (code).

Known discrepancies

  • Equivalent states whose otherwise targets differ are not merged (hfa.cc:645-651) (tree).
  • With -O equiv out of band transitions are dropped (hfa.cc:1395-1402) (tree).
  • -D dfa-minimize-partitions prints addresses of permission sets (hfa.cc:720) (tree).
  • perms_t::operator< compares audit twice (hfa.h:151-154) (code).
  • -D dfa-minimize is accepted and has no effect (code).
  • The start marker of the dfa-unreachable dump cannot print (hfa.cc:623-624) (code).

Not determined

  • Whether -O equiv reduces 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

QUALIFIERS

IN THE KERNEL

THE DFA ENGINE · libapparmor_re

TESTING