Table compression
diff-encode, comb for AppArmor developers for security researchers
Each state keeps a default and a few explicit transitions. The packer slides those sparse rows into two shared arrays - next and check - and records each row's offset in base. Diff encoding stores a state as its differences from another. The tables are written big-endian as a table set with the header string notflex. The kernel's feature set decides which of these forms the parser may use.
On the map: the dfa engine
▶ Watch this deck — 10 scenes, ~8 min
Worth seeing first
- Minimisation — the twenty-two states left to pack
Part of journeys
- From profile text to kernel tables, step 11 of 13 · previous: Minimisation · next: The binary policy format
01 Twenty-two rows of 256, mostly the same
22 states: about 50 explicit transitions, packed into 277 next/check slots plus a base and a default entry per state. -D compress-stats prints Compressed trans table: states 22, next/check 277, optimal next/check 50 ....
Minimization left twenty-two states. The kernel has to answer, for any state and any of two hundred and fifty-six byte values: where next? Written out in full that's five thousand six hundred entries, and nearly all of them say the same thing: the row's default, usually state zero. Only about fifty entries in the whole machine are explicit transitions. Table compression stores those, plus one default per row, in a way the kernel can still index in constant time. For our example the result is two arrays of two hundred and seventy-seven slots, and two of twenty-two. The stats line calls that eighty-nine percent compression against full rows.
Details and sources
Details
-D compress-statsprints the line on the slide (chfa.cc:201-208).optimal next/checkis 2 plus the explicit transitions of every state except the start state and the non-matching state (chfa.cc:91-98): 2 + 48 = 50 for the file DFA, which stores 49.compression X/YcomparesX = 4*N + 6*Sbytes (1240 for N = 277 slots and S = 22 states) withY = 512*S(11264), the size of a full row of 256 16-bit numbers per state.- The three lines of the example, for the attachment, file and policydb DFAs:
Compressed trans table: states 15, next/check 258, optimal next/check 14 avg/state 17.20, compression 1122/7680 = 85.39 % Compressed trans table: states 22, next/check 277, optimal next/check 50 avg/state 12.59, compression 1240/11264 = 88.99 % Compressed trans table: states 5, next/check 257, optimal next/check 4 avg/state 51.40, compression 1058/2560 = 58.67 %
- Run with the parser built from the AppArmor tree, nothing loaded into a kernel; the lines are the same with the tree's
abi/5.0feature set and with one that has the kernel'spolicyentries. - The marks on the slide are the entries of the packed dump of the file DFA, drawn at (state, byte).
- Seen the machine walked? How the kernel checks an access, scene "Four arrays", does the lookup on a 34-state machine.
Read more
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
- Minimisation, How the kernel checks an access.
02 Sliding the rows together
CHFA::insert_state (chfa.cc:238-317) places each state's explicit transitions at the first base where all of them land on free slots. In the example five / transitions sit in slots 47 to 51, from bases 0 to 4.
Picture each state's row as a comb with most teeth missing. A tooth is an explicit transition, at the position of its byte. The packer takes one at a time and slides it along a shared array until none of its teeth lands on a tooth that's already there. The distance it slid is the state's base. State one has a single tooth, at slash, byte forty-seven. It goes in at base zero and takes slot forty-seven. The next state with a slash tooth can't use that slot, so its base is one and it takes forty-eight, and so on up to fifty-one. The state for the bin directory has twenty-six teeth, a to z, and fits at base twenty-one.
Details and sources
Details
CHFA::CHFA(chfa.cc:62-209, declared at chfa.h:46-47) builds the tables;insert_state(chfa.cc:238-317) places one state, usingfits_in(chfa.cc:214-233).- State 0 is placed by hand with one entry at slot 0, and state 1 is the start state (chfa.cc:111-114, chfa.cc:144-146). The other states follow the DFA's state list; with
-O compress-smallthey are sorted by number of transitions, most first, then by span (chfa.cc:99-108, chfa.cc:150-199). next_checkstarts withmax(2 + number of transitions, max_range)slots and a doubly linked free list (chfa.cc:43-53, chfa.cc:138-142). A state without transitions gets base 0 and no slots (chfa.cc:251-252).- The dump line format of
-D compressed-dfa:slot: (next, check) {owner label} -> {target label}: byte. The numbers in parentheses are packed state numbers, the numbers in braces are the labels from subset construction: packed 1 is {1}, 7 is {11} (/etc), 8 is {14} (/usr), 16 is {28} (/usr/bin), 17 is {29} (/etc/demo), 18 is {31} (/usr/bin/). - The dump is from the three-rule example, parser of the AppArmor tree; it is the same with the tree's
abi/5.0feature set and with one that has the kernel'spolicyentries. The complete dump is in the reference under the deck. -O compress-smallon a profile with three abstractions: 2465 slots against 2476, and 42873 bytes of-Sagainst 42905 (kernel featuresabi/5.0plusdiff-encode).- Not determined: whether
compress-smallever gives more than that 0.4 %.
03 check: who owns this slot?
Lookup for state s and byte c: pos = base[s] + c; if check[pos] == s take next[pos], else default[s]. State 19: / hits its own slot 52; x lands on slot 125, owned by state 18, and falls to default 21.
If rows overlap, how does a lookup know a slot is really its own? That's the check array. Alongside every next entry it stores the number of the state that owns the slot. Take state nineteen, where the demo directory and its slash have been matched. Its base is five, its default is twenty-one. A slash: five plus forty-seven is slot fifty-two. Check says nineteen, that's us, so next applies: state zero. Now an x: five plus one twenty is slot one twenty-five. Check says eighteen. Not ours, so the default applies: state twenty-one, the accepting loop. And an empty slot holds state zero as its owner, so nobody but state zero matches it.
Details and sources
Details
- The lines of the
-D compressed-dfadump used on the slide:52: (0, 19) {32} -> {0}: /,5: (0, 19) {32} -> {0}: \x0,125: (20, 18) {31} -> {34}: h. There is no entry for slot 14. - The state line
19: (0, 121, 5) {32} -> {35}is accept 0, accept2 1, default 21, base 5: the dump prints accept2 and the default state without a separator. Known discrepancy, by title: "Debug dumps with malformed output". - Slot 125 is
21 + 104, thehof state 18, and slot 14 is empty: both are derived from the dump and agree with the check table decoded from the-Soutput (check[125] = 18, check[14] = 0). - Slot 0 always belongs to state 0 and empty slots hold owner 0, so a state other than 0 never matches an empty slot (chfa.cc:111-114).
- The kernel's lookup is the macro
match_char(match.c:443). - Kernel statements are read from the kernel source and were not run.
Read more
- How the kernel checks an access, scene "Four arrays"; Matching at run time.
04 The base word: an offset and two flags
Base entry: low 24 bits offset, 0x80000000 diff encoded, 0x20000000 out of band transition (chfa.h:35-38). The next/check arrays are at least the highest base plus 256 long: 277 = 21 + 256.
The base entry is a thirty-two bit word, but only the low twenty-four bits are the offset. The top byte is for flags, and two are in use. The top bit says: this state is diff encoded, which we'll come to. Another says: this state has an out of band transition, stored one slot below the base. Why two hundred and seventy-seven slots for forty-nine entries? The kernel wants to add any byte to any base without checking bounds, so it requires base plus two fifty-five to be inside the table for every state. The highest base in our machine is twenty-one. Twenty-one plus two fifty-six is two seventy-seven. A small DFA is mostly this tail.
Details and sources
Details
- The kernel's flag names are
MATCH_FLAG_DIFF_ENCODEandMATCH_FLAG_OOB_TRANSITION(match.h:196); the parser's are in chfa.h:35-38. The kernel masks the offset with 0xffffff (match.c:23). - An out of band transition is stored at
base - 1, and the kernel requires the offset of such a state to be at leastmax_oob(match.c:178). - The parser grows the array so that
base + 255stays inside it (chfa.cc:255-287) and sets the flags at chfa.cc:303-315; the kernel's test is at match.c:188. - The table set header has matching flags,
YYTH_FLAG_DIFF_ENCODEandYYTH_FLAG_OOB_TRANS(chfa.cc:71-75). - The bases of the example come from its
-D compressed-dfadump (the same with both feature sets): highest base 21 for the file DFA (state 18), 2 for xmatch, 1 for policydb. - Kernel statements are read from the kernel source and were not run.
- Known discrepancy: the base offset is not checked against 24 bits on the writer side (chfa.cc:289, chfa.cc:303-316, chfa.cc:440-444); it would need a table of more than 2^24 slots.
- Known discrepancy:
-D compressed-dfaprints the base with its flag bits in decimal (536870915,2147483648) and an out of band entry as\xff. - Known discrepancy: the kernel's
verify_dfaleavesMARK_DIFF_ENCODE_VERIFIEDset in the base table; no effect was found.
Read more
- Building the DFA, scene "One input that is not a byte"; Matching at run time.
- wiki: TechnicalDoc_HFA_Layout.
05 Diff encoding: "same as that state, except"
DFA::diff_encode (hfa.cc:1014-1113): a state keeps only transitions that differ from a shallower state and points its default at it. Three abstractions: 395 of 1695 states encoded, 3198 to 2476 slots. Matching takes at most 2m lookups for m bytes.
Comb packing exploits rows that are mostly default. Diff encoding exploits rows that are mostly like another row. This rule gives fourteen states, and four of them, ten to thirteen, have exactly the transitions of six to nine, but carry the r permission, so minimization can't merge them. With diff encoding each one stores nothing of its own: its base word is just the flag, and its default names its twin. On a failed check in a flagged state, the kernel moves to that state and tries the same byte again. On a profile with three abstractions, about a quarter of the states are, and the table shrinks by a fifth.
Details and sources
Details
- The dumps on this slide are from the rule
/srv/**x?? r,(14 states), not from the three-rule example, and were made with the tree'sabi/5.0feature set plus adiff-encodeentry (-D diff-stats -D diff-encode -D compressed-dfa):
Diff encode states: 4 of 14 reached @ depth 9. 11 trans removed
{6} <- {10}
{7} <- {11}
{8} <- {12}
{9} <- {13}
...
6: (0, 16, 1) {6} -> {6}
7: (0, 18, 2) {7} -> {8}
...
10: (2, 16, 2147483648) {10} -> {6}
11: (2, 17, 2147483648) {11} -> {7}
- For the three-rule example the parser prints
Diff encode states: 0 of 22 reached @ depth 12. 0 trans removed(feature set with the kernel'spolicyentries). For a profile with three abstractions:Diff encode states: 395 of 1695 reached @ depth 49. 726 trans removed. DFA::diff_encode(hfa.cc:1014-1113), in five steps:- breadth-first numbering from the start state gives each state a depth and its shallower parents (hfa.cc:1031-1047);
- the candidates of a state are the parents of its
otherwisetarget and of each transition target (hfa.cc:1054-1067); diff_weight(hfa.cc:128-219) adds 1 for each identical transition and subtracts for each transition that would have to be masked; a candidate must be shallower, or relative to a shallower state (hfa.cc:136-144);- the best candidate with a positive weight is chosen (hfa.cc:969-972, hfa.cc:1074-1078);
- from the last state backwards,
make_relativeerases identical transitions, adds masking transitions, sets the flag and makesotherwisethe chosen state (hfa.cc:228-268, hfa.cc:1088-1094). - The bound of 2m lookups for m bytes is argued in the comment at hfa.cc:985-1012.
- Stats:
Diff encode states: D of T reached @ depth N. X trans removed(hfa.cc:1096-1099). The self-check messagesDiff encode error: actual savings A != expected BandDiff encode error: actual count ...go to stderr without failing the compile (hfa.cc:1101-1107). -D dfa-compressed-statesshows a diff encoded state as its remaining transitions and[] -> {rel}.- In the kernel,
match_charloops while the base entry hasMATCH_FLAG_DIFF_ENCODE(match.c:443);verify_dfarequires the header flag when any state has the bit and rejects a chain that loops (match.c:172, match.c:201). - Kernel statements are read from the kernel source and were not run.
- Known discrepancy: diff encoding against a state that has an out of band transition changes the transition on byte 0xff. It needs
xattrs=, both kernel features, and a state with an explicit 0xff transition. - Known discrepancy: the self-check prints a mismatch for
profile de1 /x{*,*y/z} xattrs=(user.a=1) { }while the tables are correct. - Known discrepancy:
diff_weightandmake_relativereadbegin()of a possibly empty map. - Known discrepancy:
flatten_relativeandundiff_encodeare dead code. - Known discrepancy:
-D diff-encodeprintschains: 0andaverage chain size: infor-nan. - Not determined: the match-time cost in the kernel.
06 Sixteen-bit state numbers, unless you ask
CHFA::flex_table (chfa.cc:514-535): 16-bit entries up to 65534 states; with -O state32 and more than 65535 states, 32-bit entries up to 16777214. Otherwise Too many states (N) for type state_t, exit status 1.
Three of the arrays hold state numbers, and by default those are sixteen bits wide. That puts a ceiling on a single DFA: sixty-five thousand five hundred and thirty-four states. The exploding pattern from the DFA deck, with fifteen question marks, needs eight more than that, and the parser stops with "too many states" and exit status one. The message doesn't mention the way out: the state32 optimisation flag. Then a DFA that needs it gets thirty-two bit entries, up to about sixteen million states, and the others in the same profile stay at sixteen. The flag is off by default, and it's silently cleared when the kernel's feature set has no state32 entry.
Details and sources
Details
CHFA::flex_tablechooses the width (chfa.cc:514-535): 16-bit entries, or 32-bit entries whenstate32is set and the DFA has more than 65535 states.-D state32prints which one was used (chfa.cc:524-525, chfa.cc:532-533).- The limit test for 16 bits is
size >= 65535. Errors:Too many states (N) for type state_t(chfa.cc:435-439) andToo many transitions (N) for type trans_t(chfa.cc:440-444); both end the parser withexit(1). - The run with 15 question marks was made with the parser of the AppArmor tree and the
abi/5.0feature set. - A separate flags table is commented out (chfa.cc:518-523). With
-O flags-tableand 16-bit states the parser printsFlags table specified when using 16 bit stateand exits (chfa.cc:528-531). state32is off by default (parser_common.c:123-129) and cleared withoutpolicy/state32;flags-tableis cleared withoutpolicy/flags_tableor without state32 (parser_main.c:1795-1801).- The kernel exports
state32(apparmorfs.c:2640) and noflags_tableentry; it keeps all state tables as 32 bit in memory (match.c:411). - Kernel statements are read from the kernel source and were not run.
- Known discrepancy: with
-O state32a DFA of exactly 65535 states is refused, because the 32-bit branch needssize > 65535. Not reproduced. - Not determined: whether any shipped kernel advertises
policy/flags_table.
Read more
- Building the DFA, scene "Which rules make a profile big"; The backend pipeline, scene "What a compile costs".
- apparmor_parser(8) O n optimize n.
07 What the accept table holds
accept: a permission table index, or the accept1 word in the old encoding. accept2: 1 on file DFA states with table version 3, the accept2 word in the old encoding, absent otherwise (chfa.cc:118-137, 155-164).
There's one more per-state array, accept, and what it holds depends on how permissions are encoded. For the file DFA of our example, compiled for a kernel with the permission table, each accept entry is a row number. State twenty, the exec state, says six. State twenty-one, the state with the r permission, says four. Next to it, accept2 has a one for every state except zero and one: that tells the kernel the row comes as an owner and other pair. The attachment DFA is always written the old way. Its accept table holds the permission word itself, which is one, exec, for the single state that ends demo's path. policydb uses row numbers and has no accept2 table.
Details and sources
Details
- The tables of one DFA (chfa.cc:118-137, chfa.cc:155-164, chfa.cc:450-470; ids in flex-tables.h:25-34):
| Table | Id | Entry | One per | Content |
|---|---|---|---|---|
| accept | 1 | 32 bit | state | permission table index, or the accept1 word |
| accept2 | 7 | 32 bit | state | 1 on file DFA states with permission table version 3; the accept2 word in the old encoding; absent otherwise |
| equivalence classes | 5 | 8 bit | 256 inputs | class per byte, only with -O equiv |
| base | 2 | 32 bit | state | offset into next/check plus flag bits |
| default | 4 | 16 or 32 bit | state | state used when check fails |
| next | 8 | 16 or 32 bit | slot | target state |
| check | 3 | 16 or 32 bit | slot | owner state |
- The kernel subtracts 1 from the ids (match.c:43, match.h:54).
- The values on the slide were decoded from the
-Soutput of the three-rule example, made with a feature set that has the kernel'spolicyentries: file DFA accept is 6 for state 20 and 4 for state 21, accept2 is 1 on states 2 to 21; xmatch accept is 1 for state 14 and accept2 is all 0; policydb accept is 1 for states 2 and 3 and there is no accept2 table. - xmatch is built with
permstable32_version-1 (parser_regex.c:618), so it always uses the old encoding. - In the kernel: accept and accept2 must have the entry size the unpack flags allow, base must be 32 bit, and default, next and check may be 16 or 32 bit (match.c:373, match.c:277). Sizes are cross-checked: accept, accept2 and default as long as base; check as long as next; an equivalence table exactly 256 (match.c:104). The accept2 table is zero-filled by the kernel when a permission table is present and the policy has none (policy_unpack.c:1049).
- Kernel statements are read from the kernel source and were not run.
Read more
- Permissions in the DFA: the scenes on the old words and on the permission table.
- wiki: TechnicalDoc_HFA_permissions; Unpacking and verifying policy.
08 The table set: "notflex"
Table set: header (magic 0x1B5E783D, th_hsize 24, th_ssize, th_flags, notflex), then accept, accept2, [equivalence classes], base, default, next, check; each table td_id, td_flags (entry size), td_hilen, td_lolen, entries, padding to 8. Big-endian.
The format is called a table set, and it's borrowed, loosely, from the tables that the flex scanner generator writes. Hence the version string in the header: notflex. The header is twenty-four bytes. Then the tables, each with a twelve byte header of its own: an id, the entry size, and the number of entries. Each is padded to a multiple of eight. For our file DFA that's one thousand five hundred and twenty-eight bytes, most of them next and check. Everything in here is big-endian, even though the stream around it is little-endian. The kernel checks the magic, takes the flags, and skips the rest of the header.
Details and sources
Details
struct table_set_headerand the per-table header are in flex-tables.h:6-23 and flex-tables.h:42-49; the writer isflex_table_serializeand its callers (chfa.cc:393-512); the order of the tables is at chfa.cc:500-511.- A comment calls the format "partly reverse engineered from the flex sources" (chfa.cc:368-373); flex cannot use these tables.
- The file DFA's table set in the 5009-byte
-Soutput of the example (feature set with the kernel'spolicyentries):
| Offset | What | Bytes |
|---|---|---|
| 0x0d98 | header: 1b5e783d 00000018 000005f8 0000 6e6f74666c657800 0000 | 24 |
| 0x0db0 | accept: 0001 0004 00000000 00000016, 22 entries of 4 bytes, padding | 104 |
| 0x0e18 | accept2 | 104 |
| 0x0e80 | base | 104 |
| 0x0ee8 | default: 22 entries of 2 bytes, padding | 56 |
| 0x0f20 | next: 277 entries of 2 bytes, padding | 568 |
| 0x1158 | check | 568 |
| 0x1390 | end |
- For comparison, the xmatch table set of the same file begins
1b5e783d 00000018 00000540 0000 6e6f74666c657800 0000. - A TODO notes that the highest out of band number is not written (chfa.cc:473); the kernel assumes 1 (match.c:348).
- The kernel's
aa_dfa_unpack(match.c:333) checks the magic, rejects unknown header flags and then takes tables until the blob ends (match.c:365). - Kernel statements are read from the kernel source and were not run.
Read more
- wiki: TechnicalDoc_HFA_Layout; parser/libapparmor_re/flex-tables.h.
- The binary policy format: the blob and its alignment. Unpacking and verifying policy.
09 The kernel's feature set picks the form
get_kernel_features (parser/parser_main.c:1726-1804): policy/diff-encode, policy/state32, policy/outofband, policy/permstable32_version gate the table forms. The kernel's checks of the tables at load (verify_dfa) are in the binary policy deck.
The parser doesn't choose these forms freely. Before it compiles anything it loads the kernel's feature set, or the feature file you gave it, and four entries under policy each unlock one thing: diff encode, state32, out of band for the attribute conditions, and the permission table version. A missing entry means the older form, mostly without a word of warning. That matters when you compare dumps: the feature file shipped in the tree for abi/5.0 has no diff encode entry, so anything compiled against it has no diff encoded states. What the kernel checks in these tables when it loads them is in the binary policy deck.
Details and sources
Details
get_kernel_features(parser_main.c:1726-1804):
| Feature entry | Parser variable | Effect when absent |
|---|---|---|
policy/diff_encode or policy/diff-encode | kernel_supports_diff_encode | diff-encode cleared (parser_main.c:1750-1753, parser_main.c:1791-1793) |
policy/state32 | kernel_supports_state32 | state32 cleared (parser_main.c:1754-1755, parser_main.c:1795-1796) |
policy/flags_table | kernel_supports_flags_table | flags-table cleared (parser_main.c:1756-1757, parser_main.c:1797-1801) |
policy/outofband | kernel_supports_oob | xattr attachment conditions dropped with a warning (parser_main.c:1758-1759, parser_regex.c:549-553) |
policy/permstable32 and policy/permstable32_version/0x000002 or 0x000003 | kernel_supports_permstable32_version | the old accept encoding; version 1 or no version counts as absent (parser_main.c:1769-1785) |
- The two spellings of diff-encode: the comment at parser_main.c:1746-1749 says the kernel renamed the entry so that older user space would not send diff encoded tables.
policy/set_loadandpolicy/compressed_loadbelong to The binary policy format.- The kernel's entries are in
aa_sfs_entry_policy(apparmorfs.c:2632). verify_dfa(match.c:154) runs whenaa_g_paranoid_loadis set (policy_unpack.c:458, lsm.c:2006). Its checks: default state below the state count (match.c:164); no invalid flags (match.c:168); the header flag for diff encoding (match.c:172); the out of band offset and header flag (match.c:178); the base bound (match.c:188); next and check entries below the state count (match.c:194); diff chains (match.c:201).- Its header comment says it does not validate accept table values (match.c:150);
verify_dfa_accept_indexdoes that for the file and policydb DFAs, see The binary policy format. - Kernel statements are read from the kernel source and were not run.
- Known discrepancy: with the tree's
abi/5.0(andabi/5.0-interface) as kernel features the parser also computes kernel ABI 5: the feature lookup ofpolicy/versions/v7matches the end ofnotify_versions. See The binary policy format. - Not determined: whether the missing
diff-encodeentry inabi/5.0is intended.
10 Where to go from here
Next: the binary policy format. The walk: how the kernel checks an access, matching at run time. Back: permissions in the DFA, minimisation, the backend pipeline.
A default per state, the exceptions slid into shared arrays, an owner recorded for every slot, two flag bits in the base word, an optional layer of "same as that state", and all of it written big-endian behind a header that says notflex. The binary policy deck wraps these table sets, three per profile, into the stream that's written to the kernel. And when you want to see the arrays used, the deck on how the kernel checks an access walks a machine like this byte by byte.
Details and sources
Details
- The stage in six lines: a default per state; explicit transitions packed into next and check at the state's base; check records the owner of each slot; the base word has 24 bits of offset and two flags; diff encoding stores a state as its differences from another; the arrays are written big-endian as a table set.
- The example: 22 states, 277 next/check slots, highest base 21, 0 states diff encoded, 1528 bytes.
- The binary policy format: the stream the table set is written into. Matching at run time and How the kernel checks an access: the lookup. Unpacking and verifying policy.
- Permissions in the DFA, Minimisation, Building the DFA, The backend pipeline, Kernel features and the policy ABI.
- 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, or -S), with nothing loaded into a kernel. The packed dump of the three-rule example is the same with the tree's abi/5.0 file as kernel features and with a feature set that has the policy entries the kernel exports; the byte offsets of its table set are from the second; the diff encoding dumps were made with abi/5.0 plus a diff-encode entry; the state32 run 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.
The lookup
- For state s and byte c:
pos = base[s] + c; ifcheck[pos] == sthe next state isnext[pos], otherwisedefault[s](code: match.c:443). - State 0 is the non-matching state; slot 0 belongs to it, and every empty slot has owner 0 (code).
- With diff encoding, a failed check in a flagged state continues in
default[s]with the same byte (code).
Tables
| Table | Id | Entry | One per | Content |
|---|---|---|---|---|
| accept | 1 | 32 bit | state | permission table index, or the accept1 word |
| accept2 | 7 | 32 bit | state | 1 on file DFA states with permission table version 3; the accept2 word in the old encoding; absent otherwise |
| equivalence classes | 5 | 8 bit | 256 inputs | class per byte, only with -O equiv |
| base | 2 | 32 bit | state | offset into next/check plus flag bits |
| default | 4 | 16 or 32 bit | state | state used when check fails |
| next | 8 | 16 or 32 bit | slot | target state |
| check | 3 | 16 or 32 bit | slot | owner state |
Code: chfa.cc:118-137, chfa.cc:450-470, flex-tables.h:25-34.
The base word
| Bits | Meaning |
|---|---|
| 0-23 | offset into next and check |
29 (0x20000000) | the state has an out of band transition, stored at base - 1 |
31 (0x80000000) | the state is diff encoded |
The table set header carries YYTH_FLAG_DIFF_ENCODE and YYTH_FLAG_OOB_TRANS when any state has the bit (chfa.cc:71-75) (code).
Comb packing
- State 0 by hand at slot 0; then each state at the first base where all its explicit transitions land on free slots (chfa.cc:238-317) (code).
- Order: the DFA's state list, or with
-O compress-smallmost transitions first (chfa.cc:99-108) (code). - The arrays are at least the highest base plus 256 long (chfa.cc:255-287) (code).
- Stats:
Compressed trans table: states S, next/check N, optimal next/check O avg/state A, compression X/Y = P %, withO= 2 plus the explicit transitions of every state except the start and non-matching states (chfa.cc:91-98),X = 4*N + 6*S,Y = 512*S(code).
Diff encoding
- A state is stored relative to a shallower state when that saves transitions; it keeps the transitions that differ, and its default names the other state (hfa.cc:1014-1113) (code).
- Bound: at most 2m lookups for m input bytes (source comment).
- Stats:
Diff encode states: D of T reached @ depth N. X trans removed. Self-check:Diff encode error: actual savings A != expected B,Diff encode error: actual count ...; printed without failing the compile (code). - Measured (tree):
/srv/**x?? r,4 of 14 states, 264 to 260 slots; three abstractions 395 of 1695 states, 3198 to 2476 slots; the three-rule example 0 of 22.
State number width
| Case | Result |
|---|---|
| fewer than 65535 states | 16-bit default, next, check |
more than 65535 states with -O state32 and policy/state32 | 32-bit entries, up to 16777214 states |
| 65535 states or more otherwise | Too many states (N) for type state_t, exit status 1 |
Code: chfa.cc:514-535, chfa.cc:435-444. The error was seen with 65542 states (tree).
Table set layout
header (24 bytes, big-endian) u32 th_magic 0x1B5E783D u32 th_hsize 24 u32 th_ssize size of the whole table set u16 th_flags char th_version[] "notflex", NUL, padding table (repeated) u16 td_id u16 td_flags entry size in bytes: 1, 2 or 4 u32 td_hilen 0 u32 td_lolen number of entries entries, then padding to a multiple of 8
Order: accept, accept2, equivalence classes, base, default, next, check (chfa.cc:500-511) (code). The file DFA of the example (tree):
Offset in the -S output | Table | Bytes |
|---|---|---|
| 0x0d98 | header | 24 |
| 0x0db0 | accept | 104 |
| 0x0e18 | accept2 | 104 |
| 0x0e80 | base | 104 |
| 0x0ee8 | default | 56 |
| 0x0f20 | next | 568 |
| 0x1158 | check | 568 |
The running example, packed
-D compressed-dfa, file DFA (tree). The first number of a state line is the packed state number, the label in braces is the one from subset construction. A state line is (accept, accept2 and default run together, base).
Perms Table size: 8
(allow/deny/prompt//audit/quiet//xindex)
(0x200/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x200/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x200/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x200/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x244/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x244/0x0/0x0//0x0/0x0//0)accept1: 0x, accept2: 0x
(0x10201/0x0/0x0//0x0/0x0//i0)accept1: 0x, accept2: 0x
(0x10201/0x0/0x0//0x0/0x0//i0)accept1: 0x, accept2: 0x
size=22 (accept, accept2, default, base): {state} -> {default state}
0: (0, 00, 0) {0} -> {0}
1: (0, 00, 0) {1} -> {0}
2: (0, 10, 0) {2} -> {0}
3: (0, 10, 0) {3} -> {0}
4: (0, 10, 0) {6} -> {0}
5: (0, 10, 0) {7} -> {0}
6: (0, 10, 0) {10} -> {0}
7: (0, 10, 1) {11} -> {0}
8: (0, 10, 2) {14} -> {0}
9: (0, 10, 0) {15} -> {0}
10: (0, 10, 0) {18} -> {0}
11: (0, 10, 1) {19} -> {0}
12: (0, 10, 0) {22} -> {0}
13: (0, 10, 0) {23} -> {0}
14: (0, 10, 0) {25} -> {0}
15: (0, 10, 0) {26} -> {0}
16: (0, 10, 3) {28} -> {0}
17: (0, 10, 4) {29} -> {0}
18: (0, 10, 21) {31} -> {0}
19: (0, 121, 5) {32} -> {35}
20: (6, 120, 6) {34} -> {34}
21: (4, 121, 1) {35} -> {35}
size=277 (next, check): {check state} -> {next state} : offset from base
0: (0, 0) {0} -> {0}: \x0
1: (0, 21) {35} -> {0}: \x0
5: (0, 19) {32} -> {0}: \x0
6: (0, 20) {34} -> {0}: \x0
47: (2, 1) {1} -> {2}: /
48: (9, 7) {11} -> {15}: /
49: (10, 8) {14} -> {18}: /
50: (18, 16) {28} -> {31}: /
51: (19, 17) {29} -> {32}: /
52: (0, 19) {32} -> {0}: /
53: (0, 20) {34} -> {0}: /
98: (12, 10) {18} -> {22}: b
99: (7, 5) {7} -> {11}: c
100: (11, 9) {15} -> {19}: d
101: (3, 2) {2} -> {3}: e
102: (13, 11) {19} -> {23}: e
105: (14, 12) {22} -> {25}: i
109: (15, 13) {23} -> {26}: m
110: (16, 14) {25} -> {28}: n
111: (17, 15) {26} -> {29}: o
114: (8, 6) {10} -> {14}: r
115: (6, 4) {6} -> {10}: s
116: (5, 3) {3} -> {7}: t
117: (4, 2) {2} -> {6}: u
118: (20, 18) {31} -> {34}: a
119: (20, 18) {31} -> {34}: b
120: (20, 18) {31} -> {34}: c
121: (20, 18) {31} -> {34}: d
122: (20, 18) {31} -> {34}: e
123: (20, 18) {31} -> {34}: f
124: (20, 18) {31} -> {34}: g
125: (20, 18) {31} -> {34}: h
126: (20, 18) {31} -> {34}: i
127: (20, 18) {31} -> {34}: j
128: (20, 18) {31} -> {34}: k
129: (20, 18) {31} -> {34}: l
130: (20, 18) {31} -> {34}: m
131: (20, 18) {31} -> {34}: n
132: (20, 18) {31} -> {34}: o
133: (20, 18) {31} -> {34}: p
134: (20, 18) {31} -> {34}: q
135: (20, 18) {31} -> {34}: r
136: (20, 18) {31} -> {34}: s
137: (20, 18) {31} -> {34}: t
138: (20, 18) {31} -> {34}: u
139: (20, 18) {31} -> {34}: v
140: (20, 18) {31} -> {34}: w
141: (20, 18) {31} -> {34}: x
142: (20, 18) {31} -> {34}: y
143: (20, 18) {31} -> {34}: zKernel feature gating
| Feature entry | Effect when absent |
|---|---|
policy/diff_encode or policy/diff-encode | no diff encoding |
policy/state32 | -O state32 cleared |
policy/flags_table | -O flags-table cleared |
policy/outofband | xattr attachment conditions dropped with a warning |
policy/permstable32_version 2 or 3 | the old accept encoding |
Code: parser_main.c:1726-1804.
Dumps
| Option | Shows |
|---|---|
compressed-dfa | the permission table, the state lines and the next/check entries |
dfa-compressed-states | the state dump with packed numbers, after diff encoding |
diff-encode | one line per chain, {base} <- {relative}, and a summary |
diff-stats, compress-stats, state32 | the statistics lines quoted above |
Errors
| Message | Effect |
|---|---|
Too many states (N) for type state_t | exit status 1 |
Too many transitions (N) for type trans_t | exit status 1 |
Flags table specified when using 16 bit state | the parser exits |
Diff encode error: actual savings A != expected B | printed, compile continues |
Diff encode error: actual count ... | printed, compile continues |
Known discrepancies
- Diff encoding against a state that has an out of band transition changes the transition on byte 0xff (tree; needs
xattrs=, both kernel features and an explicit 0xff transition). - The diff encoding self-check prints a mismatch for a profile whose tables are correct (tree).
diff_weightandmake_relativereadbegin()of a possibly empty map (code; no failure reproduced).flatten_relativeandundiff_encodeare dead code (code).-D diff-encodeprintschains: 0andaverage chain size: infor-nan(tree).-D compressed-dfaprints an out of band entry as\xffand the base with its flag bits in decimal (tree).- The base offset is not checked against 24 bits (code; latent).
- With
-O state32a DFA of exactly 65535 states is refused (code; not reproduced). - Kernel:
verify_dfaleavesMARK_DIFF_ENCODE_VERIFIEDset in the base table (code; no effect found).
Not determined
- Whether any shipped kernel advertises
policy/flags_table. - The match-time cost of diff encoding in the kernel.
- Whether
compress-smallever gives more than the 0.4 % seen here.
Roads from here
START HERE
- How the kernel checks an access — the lookup done by the kernel on a real machine
RUNNING THE PARSER
- Kernel features and the policy ABI — the feature entries that gate each table form
IN THE KERNEL
- Matching at run time — the kernel loop and its verification of the tables
- Unpacking and verifying policy (no slides yet) — how the kernel reads a table set
THE DFA ENGINE · libapparmor_re
- How the tables are packed — pack the same 22 rows yourself in an interactive lab
- Minimisation — the 22 states that are packed here
- Permissions in the DFA — what the accept table points at
- The binary policy format — the stream the table set is written into
- Building the DFA — default transitions and out of band transitions
- The backend pipeline — the stage list and the default options