How the tables are packed
try the table packing for AppArmor developers for security researchers
An interactive deck on why the kernel tables are not 256 columns per state. Under each slide a lab works on the real tables of a compiled profile - the full grid, the defaults, the rows slid into the shared next and check arrays, one lookup, equivalence classes and diff encoding.
On the map: the dfa engine
▶ Watch this deck — 10 scenes, ~8 min
Worth seeing first
- How the kernel checks an access — what a state and a walk are
- Minimisation — the twenty-two states that are packed here
01 Twenty-two states are not twenty-two rows
22 states × 256 byte values would be 5632 cells; the packed next and check arrays of the example have 277 slots. Each lab under a slide works on tables unpacked from the compiled policy.
The three rules of our demo profile compile into a machine with twenty-two states. For every state and every possible next byte, the kernel must know the next state. The obvious way to store that is a grid: one row per state, two hundred and fifty-six columns. Five thousand six hundred and thirty-two cells. The kernel's arrays have two hundred and seventy-seven slots. This deck shows how the grid shrinks that far, and you can try each step: under most slides there's a lab working on the tables the parser wrote. It's for people who work on the compiler, and for anyone asking what the kernel trusts here.
Details and sources
Details
- The example is the three-rule profile of the DFA engine decks (
demo3.sd): 38 states after subset construction, 22 after minimization, 277 next/check slots. The statistics line of the parser:Compressed trans table: states 22, next/check 277, optimal next/check 50 avg/state 12.59, compression 1240/11264 = 88.99 %(chfa.cc:201-208). - The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel. - The lab's data file is built by
tools/packing-demo.pyin the map's repository. It unpacks the tables as the kernel does, compares them with the parser's-D compressed-dfadump, and replays the packer: a port ofinsert_stategives the same base for every state and the same two arrays. - The lab is keyboard accessible: every control is a button, a slider, a list or a radio group, and the two grids take the arrow keys when focused. A button in the caption leads from the slide to the lab, and a button at the top and the end of each lab piece leads back to the play button.
- Seen the machine walked? How the kernel checks an access walks a 34-state machine built from a four-rule profile. This deck uses the 22-state machine of Table compression, which is the reference for what is shown here.
Read more
- Table compression, Minimisation, How the kernel checks an access.
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
02 The table nobody stores
The full table of the example, drawn from the real data: 5632 cells, 4825 of them leading to state 0. Only 49 cells differ from the rest of their row.
Here's the grid nobody stores, rebuilt from the packed arrays one lookup at a time. Each row is a state, each column a byte value. Look how little is going on. The dark cells lead to state zero, where no rule can match any more: four thousand eight hundred and twenty-five of them. The grey rows at the bottom belong to the wildcards, where nearly every byte leads to a loop that accepts. The orange marks are the interesting part: a slash here, a single letter there, and one run of twenty-six for a to z. Below, point at any cell, and the lab tells you where it leads.
Details and sources
Details
- The drawing and the lab compute each cell with the kernel's lookup,
match_char(match.c:443-455):pos = base[state] + byte;next[pos]ifcheck[pos] == state, elsedefault[state]. - Counts for the 22 states (derived from the tables): 5632 cells; 4825 lead to state 0; 807 lead elsewhere; 5583 hold the same state as their row's default; 49 do not.
- The grey rows: state 19 (
/etc/demo/matched) has default 21; state 21 (the**loop) has default 21; state 20 (the[a-z]*loop of/usr/bin/) has default 20. Every other state has default 0. - The run of 26 is state 18 (
/usr/bin/matched):atozlead to state 20. - State numbers are the packed numbers, the row index in the tables. The parser's dumps also print a label in braces from subset construction; the two are listed in Table compression.
- The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.
Read more
- Building the DFA: where the states come from. Minimisation: why the deny rule has no states here.
03 One default per row
Each state keeps a default state and only the entries that differ from it. For the example that is 49 entries instead of 5632 cells: most states have one, state 19 two, state 18 twenty-six.
Most of a row says one thing. So give every row a default: the state most of its cells name. For nearly all our rows that's state zero. For state nineteen, just inside /etc/demo, it's twenty-one, the accepting loop: the first byte under two stars can be anything except a slash or the zero byte. A cell that agrees with its row's default doesn't need storing. Strip those, and of five thousand six hundred and thirty-two cells, forty-nine are left. Most states keep one exception; state eighteen keeps twenty-six, one per lower-case letter. Try the button below, then look at the list: that's the whole machine.
Details and sources
Details
- In the parser a state is a map of explicit transitions plus one
otherwisestate, "the default state for transitions not in trans" (hfa.h:296); the table's default is thatotherwise, or the non-matching state when there is none (chfa.cc:241-250). - The 49 entries by state: states 1 and 3 to 17 one each (16 entries); state 2 two (
e,u); state 18 twenty-six (atoz); states 19 and 20 two each (the NUL byte and/, both to state 0); state 21 one (the NUL byte, to state 0). State 0 has none. - State 19 follows
/etc/demo/. Its first**byte may be anything except/and NUL, which is why those two are its exceptions. - 5583 + 49 = 5632 (derived from the tables).
- The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel.
Read more
- Building the DFA: default transitions. Globbing: what
**and[a-z]match.
04 A row is a comb
CHFA::insert_state places each state's entries at the first offset, the base, where all of them land on free slots. next holds the target of a slot and check its owner.
What's left of a row is a comb with most teeth missing: one tooth per exception, at its byte's position. Combs like that can share one array. The packer takes them in order and slides each along until every tooth lands on a free slot. How far it slid is the state's base. State one has a tooth at slash, byte forty-seven: base zero, slot forty-seven. State seven has a slash tooth too. At base zero it collides, so it moves one along: base one, slot forty-eight. There are really two arrays: next holds where a slot leads, check holds who owns it. Below, each comb is yours to move.
Details and sources
Details
insert_state(chfa.cc:238-317) walks the free slots from the first one that is at least the row's first byte, andfits_in(chfa.cc:214-233) tests whether every entry of the row lands on a free slot there; a slot past the end counts as free, because the arrays grow.- Order: state 0 by hand with one entry at slot 0, then the start state, then the other states in the order of the DFA's state list (chfa.cc:111-114, chfa.cc:144-173).
-O compress-smallsorts them by number of transitions instead; the lab uses the default order. - A state without entries gets base 0 and no slots (chfa.cc:251-252).
- In the lab, First fit is a port of that code. Fed the 21 rows in order it gives the parser's bases: 0 for states 1 to 6, 9, 10 and 12 to 15; 1 for 7, 11 and 21; 2 for 8; 3 for 16; 4 for 17; 21 for 18; 5 for 19; 6 for 20.
- The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel.
Read more
- Table compression, scene "Sliding the rows together": the same step with the parser's dump lines.
- chfa.cc; wiki: TechnicalDoc_HFA_Layout.
05 Your turn: pack it
The arrays are always the highest base plus 256 slots long, because the kernel requires base + 255 to be inside for every state: 21 + 256 = 277. In the example 50 slots are in use.
Now pack the whole machine yourself. Place state one, then keep going. First fit shows what the parser would do. Or pick a worse base, and watch the array's end move. The kernel adds any byte to any base without checking bounds, so the array has to reach two hundred and fifty-five slots past the highest base. That's the bracket under the comb. In our machine the highest base is twenty-one, and twenty-one plus two fifty-six is two seventy-seven. Place every comb by first fit, and your arrays match the parser's slot for slot. Fifty slots are in use. The rest is that tail, and gaps no row reaches.
Details and sources
Details
- The parser grows the arrays so that
base + 255stays inside (chfa.cc:268-287); the kernel rejects a table where it does not, withAppArmor DFA next/check upper bounds error(match.c:188-191), a check made when paranoid load is on. - So the length is 256 plus the highest base in every table: 277 for the file DFA of the example (highest base 21), 258 for its attachment DFA (2) and 257 for its policydb DFA (1).
- 50 slots in use: the 49 entries and slot 0, which belongs to state 0. The statistics line's
optimal next/check 50is computed differently, as 2 plus the entries of every state except the start state (chfa.cc:91-98): 2 + 48. The two numbers agree whenever the start state has exactly one entry, as it has here (its/). - The lab lets a base go up to 84. When all 21 rows are placed it builds next and check from your bases and compares them with the parser's arrays.
- The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.
Read more
- Table compression, scene "The base word": the flag bits above the offset. The binary policy format: what the kernel checks at load.
06 Whose slot is this?
pos = base[s] + c; if check[pos] == s the next state is next[pos], otherwise default[s]. State 17 reading / owns slot 51; state 19 reading m lands on slot 114, owned by state 6, and takes its default.
Rows overlap, so a lookup must ask whose slot it found. Take the path from the matching deck, /etc/demo/motd. In state seventeen, a slash: base four plus forty-seven is slot fifty-one. Check says seventeen. That's us, so next applies: state nineteen. Now the m. Base five plus one hundred and nine: slot one fourteen. Check says six: that slot holds the r of /usr. Not ours, so the default applies: twenty-one. Three small reads instead of one from a huge table. An empty slot names zero as its owner, so only state zero matches it. Step through the path below, or type your own.
Details and sources
Details
match_charis at match.c:443-455; the offset is the low 24 bits of the base entry (match.c:23)./etc/demo/motdon this machine: states 1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 21, 21, 21. The first ten bytes each hit a slot their state owns.min state 19 lands on slot 114, which state 6 (/us) owns forr. In state 21, whose base is 1,olands on the empty slot 112,ton slot 117, which state 2 owns foru, anddon slot 101, which state 2 owns fore. Each is a miss, and the default, 21, applies.- How the kernel checks an access walks the same path on a different machine, built from four rules and with 34 states. Its state 17 also reads
/at slot 51; there next gives state 20. - Slot 0 is given to state 0 by hand, and a slot nobody took holds 0 in check, so no state but 0 matches it (chfa.cc:111-114).
- A walk that reaches state 0 stays there: every lookup in state 0 returns 0.
- The tables are those of the three-rule example, unpacked from the binary policy that the parser of the AppArmor tree writes with
-S, with a feature set that has thepolicyentries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.
Read more
- How the kernel checks an access, scene "Four arrays". Table compression, scene "check: who owns this slot?". Matching at run time.
07 Bytes that behave alike
-O equiv maps the 256 byte values of the example to 16 classes, so a full table would have 352 cells. Packed, the arrays grow from 277 to 288 slots, and a 256-byte class table is added. The option is off by default.
There's another way to shrink a grid: merge its columns. No rule here tells f from g, or a tilde from a percent sign. The equiv option gives bytes that behave alike one class number, and indexes the rows by class. Two hundred and fifty-six columns become sixteen, few enough to print below. But look at the packed form. Every comb has its teeth in the same few columns, so they collide and the bases climb. And the tail of two fifty-six stays. The array grows, from two seventy-seven to two eighty-eight, and the policy carries a class table too. On top of defaults and combs, classes don't pay here.
Details and sources
Details
DFA::equivalence_classes(hfa.cc:1300-1361) numbers the classes from 1; bytes that no transition names stay in class 0. For the example:Equiv class reduces to 15 classes, and 228 bytes in class 0.- The classes of the example: 1
/; 2e; 3u; 4t; 5s; 6c; 7r; 8d; 9b; 10i; 11m; 12n; 13o; 14 the other fourteen lower-case letters; 15 the NUL byte. - The kernel translates each input byte through the table before the lookup (match.c:486-494).
- Measured on the example:
Compressed trans table: states 22, next/check 288, optimal next/check 37, against 277 and 50 without the option. State 18 stores 13 entries instead of 26, but the highest base rises from 21 to 32, and the bound of 256 slots past the base does not change with the option (hfa.cc:473-474). The-Soutput grows from 5009 to 5905 bytes: each of the three DFAs of the profile gets a class table. - The option is off by default (parser_common.c:123-129).
- Known discrepancy: with
-O equivout of band transitions are dropped, soxattrs=conditions cannot match; see Minimisation. - Tree run with
-O equiv -D equiv, feature set with the kernel'spolicyentries. Kernel statements are read from the kernel source and were not run.
Read more
- Minimisation, scene "Equivalence classes: fewer columns": the algorithm and a larger measurement.
08 Like that state, except
DFA::diff_encode stores a state as its differences from a shallower state. For /srv/**x?? r, states 10 to 13 keep no entries and name 6 to 9 as their default: 264 slots become 260. The three-rule example has no state that gains from it.
A default says: this row is mostly one state. Diff encoding says: this row is mostly that other row. Our three rules have no such pair, so here's a one-rule profile: /srv, two stars, x, and two question marks. Of its fourteen states, ten to thirteen behave exactly like six to nine, but carry the r permission. Encoded, each stores nothing. Its base is just a flag, and its default names its twin. When a lookup misses in a flagged state, the kernel moves to the twin and tries the same byte again. The array drops from two sixty-four slots to two sixty. Switch it on and off below.
Details and sources
Details
DFA::diff_encode(hfa.cc:1014-1113) picks for each state the candidate with the highest positivediff_weight(hfa.cc:128-219);make_relative(hfa.cc:228-268) then erases the entries the two share and sets the flag.- The run:
Diff encode states: 4 of 14 reached @ depth 9. 11 trans removed;{6} <- {10},{7} <- {11},{8} <- {12},{9} <- {13}. Base of states 10 to 13: 2147483648, which is0x80000000, the flag with offset 0. Without the option (-O no-diff-encode): 264 slots, 28 in use; with it: 260 slots, 17 in use. - In the kernel a miss in a state whose base has
MATCH_FLAG_DIFF_ENCODEcontinues indefault[state]with the same byte (match.c:443-455). The parser's comment gives the bound: at most 2m lookups for m bytes (hfa.cc:985-1012). - Why the three-rule example has
Diff encode states: 0 of 22(derived from the code, not printed): candidates are the shallower states that lead to the same targets (hfa.cc:1049-1067). The states along/etc/demoand/usr/bin, up to states 18 and 19, each lead to a state nothing else leads to, so they have no candidate. State 20 has the candidate 18, but their defaults differ (20 and 0), so each of the 228 bytes neither state names would need a masking entry: the weight is -226. State 21 has the candidate 19: they share the entry for NUL (+1), and 21 would need an entry to mask 19's entry for/(-1). The weight is 0, and only a positive weight is taken (hfa.cc:959-975). - Diff encoding is used only when the kernel's feature set has
policy/diff-encode; see Table compression. - Tree runs with a feature set that has the kernel's
policyentries. Kernel statements are read from the kernel source and were not run.
Read more
- Table compression, scene "Diff encoding": the same case from the dump, and a profile where 395 of 1695 states are encoded.
09 What makes a table long
First fit leaves almost no holes in a large table, so the arrays are about one slot per stored entry plus 256. What varies between profiles is the number of entries per state: 2 for **, 26 for [a-z], none for a diff-encoded twin.
So what makes a table long? Not holes. On a real-sized profile, three abstractions and seventeen hundred states, first fit fills the array ninety-seven percent, up to its last used slot. The length is about one slot per stored entry, plus the tail of two fifty-six. What varies is entries per state. A wildcard is cheap: two exceptions, the rest is default. A character class pays per byte: twenty-six slots for a to z. A state that mirrors another costs nothing, with diff encoding. And x followed by question marks doubles the states each time: about three entries a state, half that with diff encoding. Compare seven real tables below.
Details and sources
Details
- The seven tables of the lab, file DFA of each profile, feature set with the kernel's
policyentries:
| Profile | States | Full table | Entries | Slots | In use | Diff encoded |
|---|---|---|---|---|---|---|
| the three-rule example | 22 | 5632 | 49 | 277 | 50 | 0 |
/srv/**x?? r, with -O no-diff-encode | 14 | 3584 | 27 | 264 | 28 | - |
/srv/**x?? r, | 14 | 3584 | 16 | 260 | 17 | 4 |
/srv/**x?????? r, with -O no-diff-encode | 134 | 34304 | 387 | 625 | 388 | - |
/srv/**x?????? r, | 134 | 34304 | 196 | 440 | 197 | 64 |
base, nameservice, user-tmp and one rule, -O no-diff-encode | 1695 | 433920 | 2982 | 3198 | 2983 | - |
| the same with diff encoding | 1695 | 433920 | 2256 | 2476 | 2257 | 395 |
- Full up to the last used slot (derived from the check arrays): 97 % and 98 % for the two large tables, 65 % and 79 % for the 134-state ones, 35 % for the example. In the small tables the free slots are mostly positions no row has an entry for, such as the bytes between
/anda. - Entries per state: 2.23 for the example; 2.89 for the six-
?rule without diff encoding and 1.46 with it; 1.76 and 1.33 for the three abstractions. - Every table is 256 plus its highest base long. The 256-slot tail is 92 % of the example's arrays, 10 % of the 2476-slot table and 8 % of the largest one here, 3198 slots.
- Not measured: profiles larger than these, and
-O compress-small, which changes the order in which rows are placed.
Read more
- The backend pipeline: compile cost of the same profiles. Building the DFA: why
xfollowed by?doubles the states. Globbing.
10 Where to go from here
Next: table compression for the reference, how the kernel checks an access for the walk, minimisation for the states, the binary policy format for the stream, matching at run time for the kernel code.
That's the packing: a default for each row, the exceptions as combs in one shared array, check to say whose slot it is, and sometimes a twin to lean on. Table compression is the reference for all of it: the flag bits in the base word, sixteen and thirty-two bit state numbers, and the written table set. How the kernel checks an access walks a machine like this one for a whole request. Minimisation is where the twenty-two states came from, and the binary policy format is where these arrays end up. Matching at run time has the kernel's own loop, and its checks of these tables at load.
Details and sources
Details
- The packing in four lines: one default per state; the other entries placed in next and check at the state's base, first fit; check records the owner of each slot; a diff-encoded state names another state as its default and keeps only what differs.
- Table compression: the base word, state number width, the table set, kernel feature gating. How the kernel checks an access. Minimisation. The binary policy format. Matching at run time. Building the DFA. The backend pipeline.
- Sources for this deck: AppArmor 836052d21 and Linux 97d73c825; the lab's data is rebuilt by
tools/packing-demo.py.
Read more
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 with -S -K -D compressed-dfa -D stats and the options shown, with a feature set that has the policy entries the kernel exports and nothing loaded into a kernel; the tables were then unpacked from the -S output. "code" means the parser source, or the kernel source, was read and not run; "derived" means the result was computed from those tables or reasoned from that code. Nothing here was observed on a running kernel. Table compression is the reference for the table formats; this page holds the numbers the lab works with.
The example, cell by cell
abi <abi/5.0>,
include <tunables/global>
profile demo /usr/bin/demo {
/etc/demo/** r,
audit deny @{HOME}/.ssh/** rw,
/usr/bin/[a-z]* ix,
}
| What | Value | Basis |
|---|---|---|
| states of the file DFA | 22 | tree |
| cells of a full table, 22 × 256 | 5632 | derived |
| cells that lead to state 0 | 4825 | derived |
| cells equal to their row's default | 5583 | derived |
| stored entries | 49 | derived |
| slots in next and in check | 277 | tree |
| slots in use | 50: the 49 entries and slot 0 | derived |
| highest base | 21 | tree |
Compressed trans table: states 22, next/check 277, optimal next/check 50 avg/state 12.59, compression 1240/11264 = 88.99 % (tree). optimal is 2 plus the entries of every state except the start state (chfa.cc:91-98): 2 + 48 (code).
Each state's default, base and entries
| State | Read so far | Default | Base | Entries |
|---|---|---|---|---|
| 0 | no match | 0 | 0 | none; slot 0 is placed by hand |
| 1 | start | 0 | 0 | / to 2 |
| 2 | / | 0 | 0 | e to 3, u to 4 |
| 3 | /e | 0 | 0 | t to 5 |
| 4 | /u | 0 | 0 | s to 6 |
| 5 | /et | 0 | 0 | c to 7 |
| 6 | /us | 0 | 0 | r to 8 |
| 7 | /etc | 0 | 1 | / to 9 |
| 8 | /usr | 0 | 2 | / to 10 |
| 9 | /etc/ | 0 | 0 | d to 11 |
| 10 | /usr/ | 0 | 0 | b to 12 |
| 11 | /etc/d | 0 | 1 | e to 13 |
| 12 | /usr/b | 0 | 0 | i to 14 |
| 13 | /etc/de | 0 | 0 | m to 15 |
| 14 | /usr/bi | 0 | 0 | n to 16 |
| 15 | /etc/dem | 0 | 0 | o to 17 |
| 16 | /usr/bin | 0 | 3 | / to 18 |
| 17 | /etc/demo | 0 | 4 | / to 19 |
| 18 | /usr/bin/ | 0 | 21 | a to z, all to 20 |
| 19 | /etc/demo/ | 21 | 5 | NUL to 0, / to 0 |
| 20 | /usr/bin/ and a lower-case letter | 20 | 6 | NUL to 0, / to 0 |
| 21 | /etc/demo/ and one more byte | 21 | 1 | NUL to 0 |
Tree; the "read so far" column is derived (the shortest input that reaches the state).
The packer
- State 0 gets slot 0 by hand; then the start state, then every other state in the order of the DFA's state list (chfa.cc:111-114, chfa.cc:144-173) (code).
- A state is placed at the first base at which every one of its entries lands on a free slot (chfa.cc:214-233, chfa.cc:238-317) (code).
- The arrays start 256 slots long and grow so that
base + 255is inside for every state (chfa.cc:138, chfa.cc:268-287) (code). In all eight tables measured the length is exactly 256 plus the highest base (tree). - A port of this code, fed each state's entries in state order, gives the parser's bases and its next and check arrays for all eight tables below (derived;
tools/packing-demo.pyin the map's repository).
The lookup
pos = base[s] + c; if check[pos] == s the next state is next[pos], otherwise default[s]; with a diff-encoded state a miss continues in default[s] with the same byte (match.c:443) (code).
/etc/demo/motd, byte by byte (derived):
| State | Byte | Slot | check | Result |
|---|---|---|---|---|
| 1 | / | 47 | 1 | next: 2 |
| 2 | e | 101 | 2 | next: 3 |
| 3 | t | 116 | 3 | next: 5 |
| 5 | c | 99 | 5 | next: 7 |
| 7 | / | 48 | 7 | next: 9 |
| 9 | d | 100 | 9 | next: 11 |
| 11 | e | 102 | 11 | next: 13 |
| 13 | m | 109 | 13 | next: 15 |
| 15 | o | 111 | 15 | next: 17 |
| 17 | / | 51 | 17 | next: 19 |
| 19 | m | 114 | 6 | default: 21 |
| 21 | o | 112 | 0 | default: 21 |
| 21 | t | 117 | 2 | default: 21 |
| 21 | d | 101 | 2 | default: 21 |
Equivalence classes on the example
| by byte | with -O equiv | |
|---|---|---|
| columns of a full table | 256 | 16 (classes 0 to 15) |
| cells of a full table | 5632 | 352 |
| stored entries | 49 | 36 |
| highest base | 21 | 32 |
| slots | 277 | 288 |
-S output of the profile | 5009 bytes | 5905 bytes |
Tree: Equiv class reduces to 15 classes; Compressed trans table: states 22, next/check 288, optimal next/check 37 .... Classes: 1 /; 2 e; 3 u; 4 t; 5 s; 6 c; 7 r; 8 d; 9 b; 10 i; 11 m; 12 n; 13 o; 14 a f g h j k l p q v w x y z; 15 NUL; 0 the other 228 bytes. The bound of 256 slots past the base is not changed by the option (hfa.cc:473-474) (code).
Diff encoding: /srv/**x?? r,
| State | Read so far | accept | Without: default, entries | With: default, entries |
|---|---|---|---|---|
| 6 | /srv/ | 0 | 6; NUL to 0, x to 7 | the same |
| 7 | /srv/x | 0 | 8; NUL to 0, / to 6, x to 9 | the same |
| 8 | /srv/x and one byte | 0 | 10; NUL to 0, / to 6, x to 11 | the same |
| 9 | /srv/xx | 0 | 12; NUL to 0, / to 6, x to 13 | the same |
| 10 | /srv/x and two bytes | 2 | 6; NUL to 0, x to 7 | 6, flag; none |
| 11 | /srv/x, a byte, x | 2 | 8; NUL to 0, / to 6, x to 9 | 7, flag; none |
| 12 | /srv/xx and a byte | 2 | 10; NUL to 0, / to 6, x to 11 | 8, flag; none |
| 13 | /srv/xxx | 2 | 12; NUL to 0, / to 6, x to 13 | 9, flag; none |
Tree: Diff encode states: 4 of 14 reached @ depth 9. 11 trans removed; 264 slots and 28 in use without (-O no-diff-encode), 260 and 17 with. The three-rule example: Diff encode states: 0 of 22 reached @ depth 12. 0 trans removed (tree); the reason is in the details of the scene "Like that state, except" (derived).
Seven tables compared
| Profile | States | Full table | Entries | Per state | Slots | Full to the last used slot | Diff encoded |
|---|---|---|---|---|---|---|---|
| the three-rule example | 22 | 5632 | 49 | 2.23 | 277 | 35 % | 0 |
/srv/**x?? r,, -O no-diff-encode | 14 | 3584 | 27 | 1.93 | 264 | 22 % | - |
/srv/**x?? r, | 14 | 3584 | 16 | 1.14 | 260 | 14 % | 4 |
/srv/**x?????? r,, -O no-diff-encode | 134 | 34304 | 387 | 2.89 | 625 | 79 % | - |
/srv/**x?????? r, | 134 | 34304 | 196 | 1.46 | 440 | 65 % | 64 |
base, nameservice, user-tmp and one rule, -O no-diff-encode | 1695 | 433920 | 2982 | 1.76 | 3198 | 98 % | - |
| the same | 1695 | 433920 | 2256 | 1.33 | 2476 | 97 % | 395 |
States, slots and diff encoded states: tree. The other columns: derived from the tables.
Not determined
- How full the arrays are for profiles larger than these.
- The effect of
-O compress-smallon these tables. - Whether
-O equivreduces the arrays of any profile; two were measured (this example, and the 1695-state profile in Minimisation), and both grew.
Roads from here
START HERE
- How the kernel checks an access — the same path walked for a whole request
IN THE KERNEL
- Matching at run time — the kernel loop and its verification of the tables
THE DFA ENGINE · libapparmor_re
- Table compression — the reference for the base word and the table set and state number width
- Minimisation — where the 22 states come from and the equivalence class pass
- Building the DFA — default transitions and why some patterns multiply states
- The binary policy format — the stream the arrays are written into
- The backend pipeline — the stage order and the compile cost of the same profiles