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

01 Twenty-two states are not twenty-two rows

PACKING LAB /etc/demo/** r, audit deny @{HOME}/.ssh/** rw, /usr/bin/[a-z]* ix, 22 states one row per state, 256 columns 22 × 256 = 5632 cells what the kernel holds 277 slots under most slides: a lab on the tables the parser wrote for people who work on the compiler, and for anyone asking what the kernel trusts in these arrays
Three file rules compile into 22 states; a grid of 22 rows and 256 columns would hold 5632 cells, while the kernel's next and check arrays for this machine have 277 slots

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 the policy entries the kernel exports; nothing was loaded into a kernel.
  • The lab's data file is built by tools/packing-demo.py in the map's repository. It unpacks the tables as the kernel does, compares them with the parser's -D compressed-dfa dump, and replays the packer: a port of insert_state gives 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

02 The table nobody stores

THE TABLE NOBODY STORES \0 / a z \xff 0 1 18 19 20 21 one row per state, one column per byte value: 22 × 256 = 5632 cells dark: 4825 cells lead to state 0, where no rule can match any more grey: states 19 to 21, where nearly every byte leads to an accepting loop orange: the 49 cells that differ from the rest of their row below: point at any cell
The full table of the 22 states drawn from the real data: 22 rows of 256 cells, 4825 of them leading to state 0, three rows near the bottom that lead to an accepting loop, and 49 marked cells that differ from the rest of their row

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] if check[pos] == state, else default[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): a to z lead 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 the policy entries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.

Read more

03 One default per row

ONE DEFAULT PER ROW the row of state 19, after /etc/demo/ 256 cells, nearly all of them: state 21 default[19] = 21 \0 / 2 exceptions: \0 leads to 0, and / leads to 0 5632 cells − 5583 defaults = 49 most states: 1 exception state 19: 2 state 18: 26, a to z below: strip the defaults, then read the list
The row of state 19 is 256 cells that all lead to state 21 except two; stored as a default of 21 and two exceptions. Across the machine, 5632 cells minus 5583 defaults leave 49 exceptions

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 otherwise state, "the default state for transitions not in trans" (hfa.h:296); the table's default is that otherwise, 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 (a to z); 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 the policy entries the kernel exports; nothing was loaded into a kernel.

Read more

04 A row is a comb

A ROW IS A COMB slotchecknext 44 45 46 47 48 49 50 51 52 one shared array,slots 44 to 52 of it / state 1: one tooth, at /base 0, slot 47 12 / state 7 has a / tooth toobase 0: slot 47 is taken / base 1: slot 48 is free 79 check: who owns the slot · next: where it leads · base: how far the comb slid below: the comb of each state is yours to slide
Slots 44 to 52 of the shared array. The comb of state 1 has one tooth, at slash, and takes slot 47 at base 0. The comb of state 7 also has a slash tooth: at base 0 it collides, at base 1 it takes slot 48. The check row records the owner of each slot, the next row the target

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, and fits_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-small sorts 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 the policy entries the kernel exports; nothing was loaded into a kernel.

Read more

05 Your turn: pack it

YOUR TURN 0 47 98 143 276 next and check as the parser packed them, one mark per slot in use First fit Place Place the rest Undo from the highest base, 21, a lookup can reach 255 slots further 21 + 256 = 277 slots 50 slots in use the rest: the tail, and gaps that no row reaches
The packed array of the example with its 50 slots in use marked, a bracket from the highest base 21 to slot 276, and the sum 21 plus 256 equals 277 slots

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 + 255 stays inside (chfa.cc:268-287); the kernel rejects a table where it does not, with AppArmor 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 50 is 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 the policy entries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.

Read more

06 Whose slot is this?

WHOSE SLOT IS THIS? /etc/demo/motd the path the matching deck walks state 17 reads / (byte 47) base[17] = 4 4 + 47 = 51 check[51] = 17 ours next[51] = 19 state 19 reads m (byte 109) base[19] = 5 5 + 109 = 114 check[114] = 6 the r of /usr default[19] = 21 full table: 1 read a row of 256 per state packed: 3 reads base, check, then next or default an empty slot holds 0 in check: only state 0 can match it below: step through the whole path, or type your own
Two lookups on the packed arrays of the example. State 17 reading a slash: base 4 plus 47 is slot 51, check holds 17, so next gives state 19. State 19 reading m: base 5 plus 109 is slot 114, check holds 6, so the default gives state 21

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_char is at match.c:443-455; the offset is the low 24 bits of the base entry (match.c:23).
  • /etc/demo/motd on 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. m in state 19 lands on slot 114, which state 6 (/us) owns for r. In state 21, whose base is 1, o lands on the empty slot 112, t on slot 117, which state 2 owns for u, and d on slot 101, which state 2 owns for e. 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 the policy entries the kernel exports; nothing was loaded into a kernel. Kernel statements are read from the kernel source and were not run.

Read more

07 Bytes that behave alike

-O equiv class bytes 1 / 2 e 3-13 u t s c r d b i m n o 14 a f g h j k l p q v w x y z 15 \0 0 the other 228 bytes 256 columns become 16 22 × 16 = 352 cells by byte: 277 slots by class: 288 slots every comb now has its teeth in columns 1 to 15: more collisions, higher bases the 256-slot tail stays, and the policy carries a 256-byte class table off by default
With -O equiv the 256 byte values of the example fall into 16 classes, so the full table would have 352 cells; but the packed array grows from 277 to 288 slots because the entries crowd into the first columns

-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 /; 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 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 -S output 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 equiv out of band transitions are dropped, so xattrs= conditions cannot match; see Minimisation.
  • Tree run with -O equiv -D equiv, feature set with the kernel's policy entries. 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

LIKE THAT STATE, EXCEPT /srv/**x?? r,a second profile, one rule, 14 states state 6: \0 → 0, x → 7 state 10: the same entries, plus r state 7: \0 → 0, / → 6, x → 9 state 11: the same entries, plus r state 8: \0 → 0, / → 6, x → 11 state 12: the same entries, plus r state 9: \0 → 0, / → 6, x → 13 state 13: the same entries, plus r default = 6, flag default = 7, flag default = 8, flag default = 9, flag stores nothing a miss in a flagged state: go to its default and try the same byte again 264 slots become 260 · 28 in use become 17 below: switch it on and off, and watch a lookup take two hops
The rule /srv/**x?? gives 14 states. States 10 to 13 have the entries of states 6 to 9 and also carry the r permission. With diff encoding each stores nothing and names its twin as its default; the array shrinks from 264 to 260 slots

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 positive diff_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 is 0x80000000, 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_ENCODE continues in default[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/demo and /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 policy entries. 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

WHAT MAKES A TABLE LONG three abstractions: 1695 states, 2476 slots 97 % full up to the last used slot: first fit leaves almost no holes slots ≈ stored entries + 256 ** 2 entriesthe rest is the default [a-z] 26 entriesone slot per byte a mirrored state 0 entrieswith diff encoding x???... about 3 a stateand the states double below: seven real tables, drawn to one scale
The packed array of a profile with three abstractions is 97 percent full up to its last used slot, so its length is about the stored entries plus 256; a wildcard costs 2 entries, the class a to z costs 26, a mirrored state none with diff encoding, and each state of the x question mark family about 3

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 policy entries:
ProfileStatesFull tableEntriesSlotsIn useDiff encoded
the three-rule example22563249277500
/srv/**x?? r, with -O no-diff-encode1435842726428-
/srv/**x?? r,14358416260174
/srv/**x?????? r, with -O no-diff-encode13434304387625388-
/srv/**x?????? r,1343430419644019764
base, nameservice, user-tmp and one rule, -O no-diff-encode1695433920298231982983-
the same with diff encoding1695433920225624762257395
  • 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 / and a.
  • 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

10 Where to go from here

ROADS default, base, next, check Table compressionthe reference for all of this How the kernel checks an accessa whole request on such a machine Minimisationwhere the 22 states came from The binary policy formatwhere the arrays end up Matching at run timethe kernel's loop and its checks
Roads from this deck: table compression, how the kernel checks an access, minimisation, the binary policy format and matching at run time

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

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,
}
WhatValueBasis
states of the file DFA22tree
cells of a full table, 22 × 2565632derived
cells that lead to state 04825derived
cells equal to their row's default5583derived
stored entries49derived
slots in next and in check277tree
slots in use50: the 49 entries and slot 0derived
highest base21tree

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

StateRead so farDefaultBaseEntries
0no match00none; slot 0 is placed by hand
1start00/ to 2
2/00e to 3, u to 4
3/e00t to 5
4/u00s to 6
5/et00c to 7
6/us00r to 8
7/etc01/ to 9
8/usr02/ to 10
9/etc/00d to 11
10/usr/00b to 12
11/etc/d01e to 13
12/usr/b00i to 14
13/etc/de00m to 15
14/usr/bi00n to 16
15/etc/dem00o to 17
16/usr/bin03/ to 18
17/etc/demo04/ to 19
18/usr/bin/021a to z, all to 20
19/etc/demo/215NUL to 0, / to 0
20/usr/bin/ and a lower-case letter206NUL to 0, / to 0
21/etc/demo/ and one more byte211NUL 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 + 255 is 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.py in 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):

StateByteSlotcheckResult
1/471next: 2
2e1012next: 3
3t1163next: 5
5c995next: 7
7/487next: 9
9d1009next: 11
11e10211next: 13
13m10913next: 15
15o11115next: 17
17/5117next: 19
19m1146default: 21
21o1120default: 21
21t1172default: 21
21d1012default: 21

Equivalence classes on the example

by bytewith -O equiv
columns of a full table25616 (classes 0 to 15)
cells of a full table5632352
stored entries4936
highest base2132
slots277288
-S output of the profile5009 bytes5905 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,

StateRead so faracceptWithout: default, entriesWith: default, entries
6/srv/06; NUL to 0, x to 7the same
7/srv/x08; NUL to 0, / to 6, x to 9the same
8/srv/x and one byte010; NUL to 0, / to 6, x to 11the same
9/srv/xx012; NUL to 0, / to 6, x to 13the same
10/srv/x and two bytes26; NUL to 0, x to 76, flag; none
11/srv/x, a byte, x28; NUL to 0, / to 6, x to 97, flag; none
12/srv/xx and a byte210; NUL to 0, / to 6, x to 118, flag; none
13/srv/xxx212; NUL to 0, / to 6, x to 139, 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

ProfileStatesFull tableEntriesPer stateSlotsFull to the last used slotDiff encoded
the three-rule example225632492.2327735 %0
/srv/**x?? r,, -O no-diff-encode143584271.9326422 %-
/srv/**x?? r,143584161.1426014 %4
/srv/**x?????? r,, -O no-diff-encode134343043872.8962579 %-
/srv/**x?????? r,134343041961.4644065 %64
base, nameservice, user-tmp and one rule, -O no-diff-encode169543392029821.76319898 %-
the same169543392022561.33247697 %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-small on these tables.
  • Whether -O equiv reduces 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

IN THE KERNEL

THE DFA ENGINE · libapparmor_re