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

Part of journeys

01 Twenty-two rows of 256, mostly the same

TABLE COMPRESSION 22 states x 256 bytes = 5632 entries the rest: the row's default explicit transitions 277 slotsnext / check base, default22 entries each Compressed trans table: states 22, next/check 277,optimal next/check 50 avg/state 12.59, compression 1240/11264 = 88.99 % -D compress-stats
The full transition table of the 22 states would have 5632 entries; only about 50 are explicit transitions, the rest are each row default; the packed form has two arrays of 277 slots and two of 22 entries

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-stats prints the line on the slide (chfa.cc:201-208). optimal next/check is 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/Y compares X = 4*N + 6*S bytes (1240 for N = 277 slots and S = 22 states) with Y = 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.0 feature set and with one that has the kernel's policy entries.
  • 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

02 Sliding the rows together

insert_state next / check: one shared array, slot 0 belongs to state 0 47 48 49 50 51 52 53 1 state 1: one tooth, at / = byte 47 base[1] = 0 -> slot 47 7 state 7 has a / too: 47 is taken base[7] = 1 -> slot 48 8 16 17 states 8, 16, 17: base 2, 3, 4 state 18: a to z, base[18] = 21, slots 118 to 143 47: (2, 1) {1} -> {2}: /48: (9, 7) {11} -> {15}: /49: (10, 8) {14} -> {18}: /50: (18, 16) {28} -> {31}: / slot: (next, check) {owner label} -> {target label}: byte
Comb packing: the single slash transition of state 1 takes slot 47 at base 0; states 7, 8, 16 and 17 also have a slash transition and take slots 48 to 51 with bases 1 to 4; the 26 transitions of state 18 fit at base 21 in slots 118 to 143

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, using fits_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-small they are sorted by number of transitions, most first, then by span (chfa.cc:99-108, chfa.cc:150-199).
  • next_check starts with max(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.0 feature set and with one that has the kernel's policy entries. The complete dump is in the reference under the deck.
  • -O compress-small on a profile with three abstractions: 2465 slots against 2476, and 42873 bytes of -S against 42905 (kernel features abi/5.0 plus diff-encode).
  • Not determined: whether compress-small ever gives more than that 0.4 %.

03 check: who owns this slot?

next / check / default state 19 (label {32}) /etc/demo/ base 5 default 21 byte / = 47: 5 + 47 = 52next 0check 19check == 19: oursnext state 0 byte x = 120: 5 + 120 = 125next 20check 18owner is state 18 (its h)default: state 21 byte 0x09: 5 + 9 = 14next 0check 0empty: owner is state 0default: state 21 19: (0, 121, 5) {32} -> {35} accept 0 | accept2 1 | default 21 | base 5 the dump prints accept2 and default without a separator the kernel's loop is in the deck on how the kernel checks an access; here: why rows may overlap
Three lookups for state 19 with base 5 and default 21: a slash lands on slot 52, which state 19 owns, so the next state is 0; an x lands on slot 125, owned by state 18, so the default 21 applies; a tab lands on the empty slot 14, owned by state 0, so the default applies again

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-dfa dump 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, the h of state 18, and slot 14 is empty: both are derived from the dump and agree with the check table decoded from the -S output (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

04 The base word: an offset and two flags

base bit 0 bit 31 offset into next / check 0x80000000 diff encoded 0x20000000 out of band transition, stored at base - 1 0 21: highest base 276 + 255 277 = 21 + 256 base + 255 < table size required for every state, so a lookup needs no bounds check xmatch: 2 + 256 = 258 slots; policydb: 1 + 256 = 257
The 32-bit base word: bits 0 to 23 are the offset into next and check, bit 31 marks a diff encoded state and bit 29 a state with an out of band transition; the arrays must extend 255 slots past the highest base, which gives 277 slots for a highest base of 21

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_ENCODE and MATCH_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 least max_oob (match.c:178).
  • The parser grows the array so that base + 255 stays 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_ENCODE and YYTH_FLAG_OOB_TRANS (chfa.cc:71-75).
  • The bases of the example come from its -D compressed-dfa dump (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-dfa prints the base with its flag bits in decimal (536870915, 2147483648) and an out of band entry as \xff.
  • Known discrepancy: the kernel's verify_dfa leaves MARK_DIFF_ENCODE_VERIFIED set in the base table; no effect was found.

Read more

05 Diff encoding: "same as that state, except"

-D diff-encode /srv/**x?? r, a different rule; kernel features with diff-encode 6 7 8 9 no permission 10 11 12 13 read same transitions, different permission: minimize cannot merge them {6} <- {10}{7} <- {11}{8} <- {12}{9} <- {13} 6: (0, 16, 1) {6} -> {6}10: (2, 16, 2147483648) {10} -> {6}11: (2, 17, 2147483648) {11} -> {7}2147483648 = 0x80000000: the flag, offset 0, no entries of its own check fails and the flag is set: go to default, same byte, try again 264 -> 260 slots here; three abstractions: 395 of 1695 states encoded, 3198 -> 2476 slots; the three-rule example: 0 of 22
For the rule /srv/**x?? states 10 to 13 have the transitions of states 6 to 9 but carry the read permission; diff encoding stores each of them as a flag and a default that names its twin; the kernel retries the same byte in that state

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's abi/5.0 feature set plus a diff-encode entry (-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's policy entries). 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 otherwise target 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_relative erases identical transitions, adds masking transitions, sets the flag and makes otherwise the 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 messages Diff encode error: actual savings A != expected B and Diff encode error: actual count ... go to stderr without failing the compile (hfa.cc:1101-1107).
  • -D dfa-compressed-states shows a diff encoded state as its remaining transitions and [] -> {rel}.
  • In the kernel, match_char loops while the base entry has MATCH_FLAG_DIFF_ENCODE (match.c:443); verify_dfa requires 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_weight and make_relative read begin() of a possibly empty map.
  • Known discrepancy: flatten_relative and undiff_encode are dead code.
  • Known discrepancy: -D diff-encode prints chains: 0 and average chain size: inf or -nan.
  • Not determined: the match-time cost in the kernel.

06 Sixteen-bit state numbers, unless you ask

state32 default16 bit next16 bit check16 bit basealways 32 bit acceptalways 32 bit /srv/**x??????????????? r, 15 question marks: 65542 states Too many states (65542) for type state_t exit status 1; limit 65534 $ apparmor_parser -O state32 -D state32 ...using 32 bit state tables, embedded flagsusing 16 bit state tables, embedded flags the file DFA policydb, same profile policy/state32 absent: the flag is cleared, no message the kernel widens 16-bit tables to 32 bits in memory either way
default, next and check hold 16-bit state numbers by default while base and accept are always 32 bits; a DFA with 65542 states fails with Too many states unless -O state32 is given and the kernel feature set has policy/state32

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_table chooses the width (chfa.cc:514-535): 16-bit entries, or 32-bit entries when state32 is set and the DFA has more than 65535 states. -D state32 prints 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) and Too many transitions (N) for type trans_t (chfa.cc:440-444); both end the parser with exit(1).
  • The run with 15 question marks was made with the parser of the AppArmor tree and the abi/5.0 feature set.
  • A separate flags table is commented out (chfa.cc:518-523). With -O flags-table and 16-bit states the parser prints Flags table specified when using 16 bit state and exits (chfa.cc:528-531).
  • state32 is off by default (parser_common.c:123-129) and cleared without policy/state32; flags-table is cleared without policy/flags_table or without state32 (parser_main.c:1795-1801).
  • The kernel exports state32 (apparmorfs.c:2640) and no flags_table entry; 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 state32 a DFA of exactly 65535 states is refused, because the 32-bit branch needs size > 65535. Not reproduced.
  • Not determined: whether any shipped kernel advertises policy/flags_table.

Read more

07 What the accept table holds

accept / accept2 file DFA permission table, version 3 accept 0000000000000000000064 accept2 0011111111111111111111 row index; + 1 for a non-owner when accept2 says so xmatch always the old encoding accept 000000000000001 accept2: all zeroes the accept1 word: bit 0 = exec, for the state that ends /usr/bin/demo policydb row index, no accept2 table accept 00110
The accept and accept2 tables of the three DFAs of the example: in the file DFA accept holds permission table row numbers, 6 for state 20 and 4 for state 21, and accept2 is 1 on every state except 0 and 1; xmatch holds the old permission word, 1 for state 14; policydb has row numbers and no accept2 table

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

TableIdEntryOne perContent
accept132 bitstatepermission table index, or the accept1 word
accept2732 bitstate1 on file DFA states with permission table version 3; the accept2 word in the old encoding; absent otherwise
equivalence classes58 bit256 inputsclass per byte, only with -O equiv
base232 bitstateoffset into next/check plus flag bits
default416 or 32 bitstatestate used when check fails
next816 or 32 bitslottarget state
check316 or 32 bitslotowner state
  • The kernel subtracts 1 from the ids (match.c:43, match.h:54).
  • The values on the slide were decoded from the -S output of the three-rule example, made with a feature set that has the kernel's policy entries: 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

08 The table set: "notflex"

flex_table_serialize header24 1b5e783d 00000018 000005f8 0000 "notflex\0" 0000 magic | header size 24 | total 1528 | flags 0 | version string | pad accept104accept2104base104 0001 0004 00000000 00000016 ... accept: id 1 | entry size 4 | 0 | 22 entries default56 default: id 4, 22 entries of 2 bytes next568check568 next, check: ids 8 and 3, 277 entries of 2 bytes each: 1136 of the 1528 bytes every table padded to a multiple of 8; all integers big-endian, inside a little-endian policy stream aa_dfa_unpack: checks the magic, takes header size and flags, skips the rest of the header the string and the total size are not used
The table set of the file DFA as a strip of blocks: a 24-byte header with the magic number and the string notflex, then accept, accept2, base, default, next and check, each with a 12-byte header and padded to 8 bytes, 1528 bytes in all, big-endian

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_header and the per-table header are in flex-tables.h:6-23 and flex-tables.h:42-49; the writer is flex_table_serialize and 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 -S output of the example (feature set with the kernel's policy entries):
OffsetWhatBytes
0x0d98header: 1b5e783d 00000018 000005f8 0000 6e6f74666c657800 000024
0x0db0accept: 0001 0004 00000000 00000016, 22 entries of 4 bytes, padding104
0x0e18accept2104
0x0e80base104
0x0ee8default: 22 entries of 2 bytes, padding56
0x0f20next: 277 entries of 2 bytes, padding568
0x1158check568
0x1390end
  • 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.

09 The kernel's feature set picks the form

policy/ diff-encodediff encoded states state3232-bit default, next, check outofbandxattr conditions keptabsent: "xattr attachment conditional ignored" permstable32_versionpermission table, version 2 or 3absent or 1: the old accept words the tree's abi/5.0 file has no diff-encode entry: a profile compiled against it gets no diff encoding what the kernel checks at load: The binary policy format
Four entries of the kernel feature set each switch one table form on: diff-encode, state32, outofband and the permission table version; the tree's abi/5.0 file has no diff-encode entry; the kernel's checks at load are in the binary policy deck

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

Feature entryParser variableEffect when absent
policy/diff_encode or policy/diff-encodekernel_supports_diff_encodediff-encode cleared (parser_main.c:1750-1753, parser_main.c:1791-1793)
policy/state32kernel_supports_state32state32 cleared (parser_main.c:1754-1755, parser_main.c:1795-1796)
policy/flags_tablekernel_supports_flags_tableflags-table cleared (parser_main.c:1756-1757, parser_main.c:1797-1801)
policy/outofbandkernel_supports_oobxattr attachment conditions dropped with a warning (parser_main.c:1758-1759, parser_regex.c:549-553)
policy/permstable32 and policy/permstable32_version/0x000002 or 0x000003kernel_supports_permstable32_versionthe 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_load and policy/compressed_load belong to The binary policy format.
  • The kernel's entries are in aa_sfs_entry_policy (apparmorfs.c:2632).
  • verify_dfa (match.c:154) runs when aa_g_paranoid_load is 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_index does 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 (and abi/5.0-interface) as kernel features the parser also computes kernel ABI 5: the feature lookup of policy/versions/v7 matches the end of notify_versions. See The binary policy format.
  • Not determined: whether the missing diff-encode entry in abi/5.0 is intended.

10 Where to go from here

ROADS a table set The binary policy formatthe stream around the table sets How the kernel checks an accesswalking these arrays Matching at run timethe kernel code Permissions in the DFAwhat accept points at
Roads from this deck: the binary policy format, matching at run time, how the kernel checks an access and permissions in the DFA

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

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; if check[pos] == s the next state is next[pos], otherwise default[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

TableIdEntryOne perContent
accept132 bitstatepermission table index, or the accept1 word
accept2732 bitstate1 on file DFA states with permission table version 3; the accept2 word in the old encoding; absent otherwise
equivalence classes58 bit256 inputsclass per byte, only with -O equiv
base232 bitstateoffset into next/check plus flag bits
default416 or 32 bitstatestate used when check fails
next816 or 32 bitslottarget state
check316 or 32 bitslotowner state

Code: chfa.cc:118-137, chfa.cc:450-470, flex-tables.h:25-34.

The base word

BitsMeaning
0-23offset 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-small most 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 %, with O = 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

CaseResult
fewer than 65535 states16-bit default, next, check
more than 65535 states with -O state32 and policy/state3232-bit entries, up to 16777214 states
65535 states or more otherwiseToo 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 outputTableBytes
0x0d98header24
0x0db0accept104
0x0e18accept2104
0x0e80base104
0x0ee8default56
0x0f20next568
0x1158check568

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}: z

Kernel feature gating

Feature entryEffect when absent
policy/diff_encode or policy/diff-encodeno diff encoding
policy/state32-O state32 cleared
policy/flags_table-O flags-table cleared
policy/outofbandxattr attachment conditions dropped with a warning
policy/permstable32_version 2 or 3the old accept encoding

Code: parser_main.c:1726-1804.

Dumps

OptionShows
compressed-dfathe permission table, the state lines and the next/check entries
dfa-compressed-statesthe state dump with packed numbers, after diff encoding
diff-encodeone line per chain, {base} <- {relative}, and a summary
diff-stats, compress-stats, state32the statistics lines quoted above

Errors

MessageEffect
Too many states (N) for type state_texit status 1
Too many transitions (N) for type trans_texit status 1
Flags table specified when using 16 bit statethe parser exits
Diff encode error: actual savings A != expected Bprinted, 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_weight and make_relative read begin() of a possibly empty map (code; no failure reproduced).
  • flatten_relative and undiff_encode are dead code (code).
  • -D diff-encode prints chains: 0 and average chain size: inf or -nan (tree).
  • -D compressed-dfa prints an out of band entry as \xff and the base with its flag bits in decimal (tree).
  • The base offset is not checked against 24 bits (code; latent).
  • With -O state32 a DFA of exactly 65535 states is refused (code; not reproduced).
  • Kernel: verify_dfa leaves MARK_DIFF_ENCODE_VERIFIED set 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-small ever gives more than the 0.4 % seen here.

Roads from here

START HERE

RUNNING THE PARSER

IN THE KERNEL

THE DFA ENGINE · libapparmor_re