The backend pipeline
three DFAs per profile for AppArmor developers for security researchers for administrators
One function turns the rules of a profile into packed tables in nine stages. A profile gets up to three state machines - for attachment and for file rules and for every other rule class. Each stage has a dump option. Compile time follows the number of states and not the number of rules.
On the map: the dfa engine
▶ Watch this deck — 9 scenes, ~7 min
Worth seeing first
- From profile text to kernel — the four stops; the backend is one of them
- How the kernel checks an access — the finished machine that the backend has to build
Part of journeys
- From profile text to kernel tables, step 6 of 13 · previous: How the kernel checks an access · next: The expression tree
01 Three rules in, three tables out
The backend turns the rules of one profile into up to three state machines and packs them into tables. For the three-rule demo profile: 15, 22 and 5 states, 5009 bytes.
This is demo's profile, cut down to three rules. The kernel doesn't get these lines. It gets tables. The part of apparmor_parser that makes those tables is called the backend. For this profile it builds three state machines: one for the attachment, one for the file rules, and one for every other rule class. Fifteen, twenty-two and five states, five thousand and nine bytes in all, handed to the kernel in one write. This deck is the map of that work, and each stage has a deck of its own. It's mostly for people who work on the parser or want to check it. One scene is about what a compile costs you when you run the parser.
Details and sources
Details
- The profile used by the seven decks of this district, complete (file
demo3.sd):
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,
}
- The state counts come from
apparmor_parser -Q -K -D stats demo3.sd, and the size fromapparmor_parser -Q -K -S demo3.sd | wc -c. Both were run with the parser built from the AppArmor tree, and nothing was loaded into a kernel. The kernel feature set given to the parser was one with thepolicyentries the kernel exports; the tree's ownabi/5.0file gives the same counts and the same size. -Qskips the kernel load,-Kskips the cache,-Swrites the binary policy to standard output.- The attachment machine answers "does this profile attach to the program being executed"; the file machine answers file and exec requests; the third machine answers every other rule class (capabilities are stored as bit masks and need no machine).
- Seen the machine walked? That is How the kernel checks an access. This deck and the six after it show how the machine is made.
Read more
- How the kernel checks an access: the finished machine being walked.
- From profile text to kernel: the whole parser run around the backend.
- apparmor_parser(8).
for AppArmor developers for security researchers
In the code
- The backend is the directory
parser/libapparmor_re/plus parser/parser_regex.c (rules in, tables out) and parser/parser_interface.c (the bytes). - wiki: TechnicalDoc_HFA describes the design. The page is marked draft by its authors; where it and the code differ, these decks follow the code.
02 One profile, three DFAs for AppArmor developers for security researchers
process_profile_rules builds xmatch, then the file DFA, then policydb. Dump lines for the three come in that order and are not labelled.
The backend runs up to three times for one profile. First, the attachment. The path on the head line becomes a tiny rule set with one permission, exec. That's the xmatch DFA: fifteen states for demo's path. Second, the file rules. That's where our three rules go: thirty-eight states at first, twenty-two at the end. Third, policydb, for every other rule class. Demo has no such rules, but it still gets one, because the parser adds a marker rule for every class the profile mediates. That lets the kernel ask whether this profile cares about signals at all. The three are built in this order, and that matters when you read a dump, because the lines aren't labelled.
Details and sources
for AppArmor developers for security researchers
Details
- Order:
process_profile_rulescalls the three builders in the order xmatch (parser_regex.c:1238), file (parser_regex.c:1258), policydb (parser_regex.c:1268). - xmatch, built by
process_profile_name_xmatch(parser_regex.c:478-627): - its input is the attachment, or the profile's local name when there is no attachment (parser_regex.c:487-494), plus alias names (parser_regex.c:531-547);
- there is no xmatch at all when the pattern has no glob and the profile has no alias, no attachment and no xattrs (parser_regex.c:511-515);
- every rule carries
AA_MAY_EXECwith priority 0 (parser_regex.c:526-527); - it is built with
filedfa=falseandpermstable32_version=-1(parser_regex.c:615-619), so it always uses the old accept tables and always has deny filtered (aare_rules.cc:273). - File DFA: rules are added by
process_dfa_entryfrom path rules, link pairs andchange_profile(parser_regex.c:648-787); it is built only whenrule_count > 0(parser_regex.c:794), withfiledfa=true(parser_regex.c:797). - policydb:
process_profile_policydbadds one marker rule\d<class>withAA_MAY_READfor each mediated class (parser_regex.c:1338-1357, parser_regex.c:1392-1453). Its priority is 1001, or -1001 for the classes that keep permissions on the class state (parser_regex.c:1372, parser_regex.c:1383). The DFA is built at parser_regex.c:1457-1461. - The ten marker rules of the example, in the order printed by
-D rule-exprs:\d21 \d2 \d7 \d32 \d10 \d9 \d14 \d15 \d15\0001 \d22. The dumps on this slide come from the parser of the AppArmor tree, run with a feature set that has thepolicyentries the kernel exports; that kernel has noipcentry, so the example has no message queue marker\d17. - Known discrepancy: with the tree's
abi/5.0file as kernel features the parser computes kernel ABI 5 and leaves out the file class marker\d2(parser_regex.c:1400-1402): the feature lookup ofpolicy/versions/v7matches the end ofnotify_versions. - When the parser is built with the optional DFA cache, xmatch and policydb are still built on a hit (parser_regex.c:1236-1239, parser_regex.c:1268).
for AppArmor developers for security researchers
Read more
- wiki: TechnicalDoc_PolicyDB: how the other rule classes are encoded.
- Rule objects, Profile attachment, Matching at run time.
03 create_chfa: nine stages, one function for AppArmor developers for security researchers
aare_rules::create_chfa (parser/libapparmor_re/aare_rules.cc:194-345): tree, DFA, filter deny, minimize, remove unreachable, equivalence classes, diff encode, perms table, CHFA.
Open aare_rules.cc and find create_chfa. Its body reads top to bottom as the pipeline. Build the tree. Construct the DFA. Fold deny into allow. Minimize. Then two optional clean-ups that are off by default. Diff encode, compute the permission table, and pack everything into a CHFA, the compressed form. One wrapper up, create_dfablob writes that out as bytes. If a stage fails, the function returns NULL and the parser reports that the profile failed to load. The other decks of this district take these boxes one or two at a time.
Details and sources
for AppArmor developers for security researchers
Details
- Signature:
CHFA *aare_rules::create_chfa(int *min_match_len, vector <aa_perms> &perms_table, optflags const &opts, bool filedfa, int permstable32_version, aare_rules *tail = NULL, bool tail_oob = true)(aare_rules.h:147-151). - The stages, in order (aare_rules.cc:194-345):
| Stage | Call | Lines | Runs when |
|---|---|---|---|
| tail | build the tail's tree, put a separator in front | aare_rules.cc:203-221 | a tail rule set is given (xattrs) |
| tree | build_tree | aare_rules.cc:162-187, called at aare_rules.cc:223 | always |
| (numbering) | label_nodes(root) | aare_rules.cc:235 | always; for dumps |
| DFA | DFA dfa(root, opts, filedfa) | aare_rules.cc:260 | always |
| filter deny | dfa.apply_and_clear_deny() | aare_rules.cc:273-278 | permstable32_version < 2, or filter-deny |
| minimize | dfa.minimize(opts) | aare_rules.cc:279-285 | minimize |
| unreachable | dfa.remove_unreachable(opts) | aare_rules.cc:287-291 | remove-unreachable |
| equiv | dfa.equivalence_classes, apply_equivalence_classes | aare_rules.cc:298-308 | equiv |
| diff encode | dfa.diff_encode(opts) | aare_rules.cc:310-315 | diff-encode |
| perms table | dfa.compute_perms_table(perms_table) | aare_rules.cc:318-333 | permstable32_version >= 2 |
| CHFA | new CHFA(dfa, eq, opts, permstable32_version) | aare_rules.cc:334 | always |
- The function returns NULL when there are no rules (aare_rules.cc:227-228) or when a stage inside its
tryblock throws anint(aare_rules.cc:340-342). - The message chain for conflicting exec modifiers:
perms_t::perms_tprintsprofile has merged rule with conflicting x modifiersand throws (hfa.cc:1703-1707); the caller printsERROR processing regexs for profile t, failed to load(parser_regex.c:1277) and the parser exits with status 255. Seen in a run of the tree's parser with theabi/5.0feature set. create_dfablobcallscreate_chfa, hasflex_tablewrite the table set into a stream and copies it into amallocbuffer (aare_rules.cc:352-388).- The whole-tree simplification is commented out (aare_rules.cc:249); simplification runs per permission group inside
build_tree(aare_rules.cc:170-171). - Known discrepancy:
std::runtime_errorthrown byminimizeandcompute_perms_table(hfa.cc:883, hfa.cc:1452-1454) is not caught by thecatch (int), which is the only handler;build_treeruns before thetryblock. No other handler in the parser catches it. Not reproduced. - Known discrepancy:
create_dfablobreturns NULL with*sizestill set whenmallocfails (aare_rules.cc:380-384). Not reproduced.
for AppArmor developers for security researchers
Read more
04 The file DFA, stage by stage for AppArmor developers for security researchers
File DFA of the example: 38 states created, 22 after filter deny and minimize, packed into 277 next/check slots, 1528 bytes. -D stats prints the counts.
Follow our three rules along the strip. Three rules with three different permissions make three groups in the tree. Subset construction makes thirty-eight states. Filter deny doesn't remove any, but sixteen of them, the ones that only existed for the deny rule, now carry nothing. That's what lets minimize merge them away: twenty-two are left. Diff encoding finds nothing worth encoding in a machine this small. The permission table gets eight rows. And the twenty-two rows pack into two hundred and seventy-seven slots, fifty of them used. As a table set that's one thousand five hundred and twenty-eight bytes. The stats dump prints these counts for any profile.
Details and sources
for AppArmor developers for security researchers
Details
apparmor_parser -Q -K -D stats demo3.sd, run with the parser of the AppArmor tree and a feature set that has thepolicyentries the kernel exports. The lines for the three DFAs, in the order xmatch, file, policydb (escape codes removed; the tree'sabi/5.0gives the same lines exceptDiff encode, which it does not print):
Created dfa: states 15 proto { cache: size=15 dups=1 longest=1 avg=0 }, nnodes { cache: size=14 dups=2 longest=1 avg=0 }, anodes { cache: size=1 dups=0 longest=1 avg=1 }
Dfa minimization no states removed: partitions 15 init 3 (accept 1)
Diff encode states: 0 of 15 reached @ depth 14. 0 trans removed
Compressed trans table: states 15, next/check 258, optimal next/check 14 avg/state 17.20, compression 1122/7680 = 85.39 %
Created dfa: states 38 proto { cache: size=38 dups=40 longest=4 avg=1 }, nnodes { cache: size=38 dups=40 longest=4 avg=1 }, anodes { cache: size=3 dups=28 longest=1 avg=1 }
Minimized dfa: final partitions 22 (accept 2) init 4 (accept 2)
Diff encode states: 0 of 22 reached @ depth 12. 0 trans removed
Compressed trans table: states 22, next/check 277, optimal next/check 50 avg/state 12.59, compression 1240/11264 = 88.99 %
Created dfa: states 6 proto { cache: size=6 dups=16 longest=3 avg=1 }, nnodes { cache: size=4 dups=18 longest=3 avg=1 }, anodes { cache: size=2 dups=17 longest=1 avg=1 }
Minimized dfa: final partitions 5 (accept 2) init 3 (accept 1)
Diff encode states: 0 of 5 reached @ depth 3. 0 trans removed
Compressed trans table: states 5, next/check 257, optimal next/check 4 avg/state 51.40, compression 1058/2560 = 58.67 %
Created dfais printed by subset construction: the number of states, and the sizes of the caches for node sets. See Building the DFA.Minimized dfa: final partitions 22 (accept 2) init 4 (accept 2): 22 states are left, 2 of them accepting; the refinement started from 4 partitions.Dfa minimization no states removedis printed when nothing merged. See Minimisation.Compressed trans table: the packed size against a full table,4*N + 6*Sbytes over512*Sfor N next/check slots and S states. See Table compression.- "16 now carry nothing": the 16 states that exist only for the
audit denyrule lose their deny and quiet bits in filter deny and are then equal to the state with no permissions. See Permissions in the DFA. - With
-O no-filter-denythe second line becomesDfa minimization no states removed: partitions 38 init 5 (accept 3)(run with theabi/5.0feature set). - The three table sets are 1344, 1168 and 1528 bytes; 1528 is the file DFA's.
statsis a group of dump flags (common_optarg.c:37-42). The parser prints some of the lines with terminal escape codes; strip them withsed 's/\x1b\[[0-9;]*[A-Za-z]//g'.
for AppArmor developers for security researchers
Read more
05 A dump for every stage for AppArmor developers for security researchers
Dump options by stage: rule-exprs, expr-tree, dfa-states-initial, dfa-states-post-filter, dfa-minimize-partitions, diff-encode, compressed-dfa. All print to stderr; stats is a group.
You don't have to take any of this on trust. Every stage can print what it made, with the dump option, capital D. rule-exprs shows each pattern as the regular expression the backend receives. expr-tree shows the tree. dfa-states-initial shows every state straight out of the construction; post-filter and post-minimize show them later. The minimize partitions dump shows the merging, and compressed-dfa shows the permission table and the packed arrays. Everything goes to standard error, so add Q and K to compile without loading anything or touching the cache. The other decks of this district quote these dumps for our three rules.
Details and sources
for AppArmor developers for security researchers
Details
- All dump options (common_optarg.c:30-85) and where each is printed:
| Stage | Option | Printed at |
|---|---|---|
| AARE to regular expression, rule to tree | rule-exprs | parser_regex.c:142-143, parser_regex.c:441-442, aare_rules.cc:112-135 |
| Tree statistics | expr-stats | expr-tree.cc:972-976, expr-tree.cc:1021-1042 |
| Tree | expr-tree, expr-simplified | aare_rules.cc:236-240, aare_rules.cc:251-255 |
| Permission of each state | dfa-perms-build | hfa.cc:1558-1651, hfa.cc:1670-1702 |
| Subset construction | dfa-stats, dfa-progress, dfa-node-map | hfa.cc:446-454, hfa.cc:522-535 |
| Permission sets | dfa-uniq-perms, dfa-minimize-uniq-perms | aare_rules.cc:261-262, aare_rules.cc:281-282 |
| States | dfa-states-initial, dfa-states-post-filter, dfa-states-post-minimize, dfa-states-post-unreachable, dfa-states | aare_rules.cc:264-293 |
| Minimization | dfa-minimize-partitions | hfa.cc:770-771, hfa.cc:838-839, hfa.cc:847-894 |
| Unreachable states | dfa-unreachable | hfa.cc:621-628 |
| Graphviz | dfa-graph | aare_rules.cc:295-296 |
| Equivalence classes | equiv, equiv-stats | aare_rules.cc:303-308, hfa.cc:1357-1359 |
| Diff encoding | diff-encode, diff-stats, diff-progress | aare_rules.cc:313-314, hfa.cc:1069-1072, hfa.cc:1096-1099 |
| Perms table and packed tables | compressed-dfa | aare_rules.cc:322-336 |
| Packing statistics | compress-stats, compress-progress | chfa.cc:201-208 |
| States with packed numbers | dfa-compressed-states | aare_rules.cc:337-338 |
| Table width | state32 | chfa.cc:524-525, chfa.cc:532-533 |
statsandprogressare groups (common_optarg.c:37-42).dfa-statesis printed before diff encoding anddfa-compressed-statesafter it (aare_rules.cc:292-293, aare_rules.cc:310, aare_rules.cc:337-338); only the second shows the transitions that diff encoding left.- The lines for the three DFAs of a profile are not labelled; they come in the order xmatch, file, policydb.
- Known discrepancy:
-D dfa-minimizeis accepted and no code tests the flag (common_optarg.c:54). - Known discrepancy:
-D expr-treeand-D expr-simplifiedprint the same tree (aare_rules.cc:236-255). - Known discrepancy: the same table is
flags_tablewith an underscore as a dump option andflags-tablewith a dash as an optimisation (common_optarg.c:82, common_optarg.c:120). - Known discrepancies, by title: "Help text for two -D dump options is copied from the wrong entries" and "Debug dumps with malformed output".
for AppArmor developers for security researchers
Read more
- apparmor_parser(8) D n dump n.
- Testing AppArmor:
parser/tst/minimize.shreads-D dfa-states.
06 What runs by default for AppArmor developers for security researchers
Default -O set: expr-normalize expr-simplify expr-vector minimize diff-encode rule-merge filter-deny. Kernel features clear diff-encode, state32 and flags-table without a message.
Which of the nine stages actually run? Seven optimisation flags are on unless you say otherwise: three for the tree, then minimize, diff encode, rule merge in the front end, and filter deny. The two outlined boxes from before, equiv and remove unreachable, are off, and so are thirty-two bit state numbers. Then the kernel has a say. If its feature set doesn't list diff encode, or state thirty-two, the parser clears the flag and tells you nothing. And filter deny is forced whenever a DFA is built without the permission table, which is always the case for xmatch. The show option prints the set you asked for.
Details and sources
for AppArmor developers for security researchers
Details
- Grammar:
-O <name>switches a flag on,-O no-<name>off. The table isdfaoptflag_table(common_optarg.c:87-127).-O showprints the current set while options are parsed, before the kernel features are read (parser_main.c:655-656). - Defaults (parser_common.c:123-129):
expr-normalize,expr-simplify,expr-vector,minimize,diff-encode,rule-merge,filter-deny. - Off by default:
equiv,remove-unreachable,expr-left-simplify,compress-small,compress-default,state32,flags-table,zstd-recompress. - Gating in
get_kernel_features(parser_main.c:1791-1801; the features are looked up at parser_main.c:1750-1757):diff-encodeis cleared withoutpolicy/diff_encodeorpolicy/diff-encode;state32withoutpolicy/state32;flags-tablewithoutpolicy/flags_tableor without state32. No message is printed. The two spellings of diff-encode are explained in the comment at parser_main.c:1746-1749. - The tree's
abi/5.0file has no diff-encode entry; the kernel advertisespolicy/diff-encode(apparmorfs.c:2635). filter-denyis forced for any DFA built withpermstable32_version < 2(aare_rules.cc:273).- Errors:
Conflicting --Optimize options: compress-default, compress-small(parser_main.c:663-667);Invalid --Optimize option %s(parser_main.c:659-660). compress-smallandcompress-fastare one bit with opposite sense, as areexpr-left-simplifyandexpr-right-simplify(common_optarg.c:99-102, common_optarg.c:110-114).compress-smallalso selects zstd level 20 for the policy stream when no level is given (parser_main.c:494-495).- Known discrepancy:
-O 0clearsexpr-normalize,expr-simplify,minimize,remove-unreachable,diff-encode,state32andflags-table, and leavesexpr-vector,filter-deny,rule-mergeandequivas they were (common_optarg.c:88-93); the help text says "no optimizations". - Kernel statements are read from the kernel source and were not run.
for AppArmor developers for security researchers
Read more
- apparmor_parser(8) O n optimize n.
- Kernel features and the policy ABI.
- Table compression has the table of features and what each switches.
07 What a compile costs, and what the cache saves
apparmor_parser -Q -K -D dfa-stats FILE prints the state count that decides compile time. A cache hit skips the compile; the profile text is still read. Too many states (N) for type state_t means one profile needs more than 65534 states.
If you run the parser, here's what the backend costs you. What matters isn't how many rules a profile has. It's how many states they turn into, and the dfa-stats dump prints that number. Demo's three rules: thirty-eight. A profile that pulls in three common abstractions: about two thousand four hundred, and still far less than a second. But one unlucky pattern, a double star followed by a fixed run of question marks, reached sixty-five thousand states, took a couple of seconds, and then stopped with "too many states". The cache keeps this off your boot path. On a hit the parser still reads the profile text, but skips the compile.
Details and sources
Details
-D dfa-statsprints oneCreated dfaline per state machine, in the order attachment, file rules, other rule classes.- Measured with the parser built from the AppArmor tree and a feature set that has the kernel's
policyentries, so diff encoding is on as it is on a running system; nothing was loaded into a kernel. Each run had just under 2 seconds of start-up in it (the three-rule profile takes 1.9 s in all), which is taken off here:
| Profile | States created | After merging | Table slots | Bytes of -S | Time |
|---|---|---|---|---|---|
the three-rule demo profile | 38 | 22 | 277 | 5009 | none to speak of |
base, nameservice, user-tmp abstractions and one rule | 2387 | 1695 | 2476 | 41913 | well under a second |
one rule /srv/**x?????????????? (14 question marks) | 32774 | 32774 | 58559 | not measured | well under a second |
one rule /srv/**x??????????????? (15 question marks) | 65542 | 65542 | 116981 | error | about 1.5 s |
- The error
Too many states (65542) for type state_tnames no profile and does not mention-O state32, which lifts the limit when the kernel's features listpolicy/state32. The exit status is 1. There is no warning before the limit. - The default cache location is
/var/cache/apparmor(parser_main.c:1864-1866). - The profile is parsed before the hit is decided (parser_main.c:1341, parser_main.c:1356-1361). A profile or include newer than the cache file forces a miss (policy_cache.c:105-119);
--debug-cacheprintsfile '%s' is newer than cache file. - What the parser checks in a cache file depends on its form. A file that is not compressed is accepted only if it starts with the 12-byte
versionmarker and the version word this parser would write now (policy_cache.c:36-69, policy_cache.c:170-176). When the kernel takes compressed policy, the cache file is an 8-byte header and one zstd frame, and the parser checks the header version, the zstd magic and the compression level instead; the version word is inside the frame and is not looked at (policy_cache.c:80-96, policy_cache.c:136-146, policy_cache.c:148-181). See The binary policy format. - No cache is used for standard input, for force-complain and for a profile in a namespace (parser_main.c:1309-1311, parser_main.c:1325, parser_main.c:1353-1354).
-jruns profiles in parallel worker processes; the number of jobs is derived from free memory (parser_main.c:1629-1660).- Known discrepancy: "Cache hit on an uncompressed cache loads the profile twice and writes the cache without -W".
Read more
- apparmor_parser(8) W write cache, apparmor_parser(8) L cache loc; wiki: Apparmorpolicycache.
- The policy cache, Running apparmor_parser.
- Building the DFA: which rule shapes are expensive. Choosing abstractions.
for AppArmor developers for security researchers
In the code
- The 16-bit limit is checked when the tables are written (chfa.cc:435-439);
-O state32and the kernel feature are handled at chfa.cc:514-535. - A second, optional cache holds single DFAs:
--dfa-cache-loc, compiled in only withUSE_DFA_CACHE(Makefile:72-73). Known discrepancies, by title: "DFA cache key leaves out the permstable32 version that its comment says it covers", "The DFA cache stores entries that its lookup always rejects", "The DFA cache renames a short file into place when the final write fails in fclose()", "The DFA cache writes through a symlink at a predictable temp name and leaks temp files", "A corrupted DFA cache entry is accepted as a hit".
08 Where the time goes for AppArmor developers for security researchers
Cost centres: add_new_state (hfa.cc:329-358), permissions per target before de-duplication (hfa.cc:340), partition refinement (hfa.cc:791-827). Three abstractions: 2387 states created, 1695 kept; 3160 with -O 0.
Subset construction makes one state object for every distinct set of tree positions, so its cost is the state count. And for every transition target it builds the state, computes its permissions, and only then finds out it already had that state and deletes it. Minimization compares the members of every partition with a representative, and goes round again until a whole pass splits nothing. On a profile with three abstractions, minimization brings two thousand four hundred states down to seventeen hundred and takes a quarter off the table. Nothing in here watches the count: the first check is the sixteen bit limit, when the tables are written.
Details and sources
for AppArmor developers for security researchers
Details
- The table was measured with the parser built from the AppArmor tree and a feature set that has the kernel's
policyentries, so diff encoding is on by default (-D stats, and the size of the-Soutput). The profile isprofile big /usr/bin/big { include <abstractions/base> include <abstractions/nameservice> include <abstractions/user-tmp> /etc/demo/** r, }afterabi <abi/5.0>,andinclude <tunables/global>. The rows are its file DFA; the bytes are the whole profile. - Diff encoding in the three runs: 395 of 1695 states encoded by default, 982 of 2387 with
-O no-minimize, none with-O 0. Without diff encoding (-O no-diff-encode, or a feature set with nopolicy/diff-encodeentry such as the tree'sabi/5.0) the default table has 3198 slots and the-O no-minimizetable 6170. add_new_statecreates aStatefor a set of nodes and looks it up among the existing ones (hfa.cc:329-358). TheStateconstructor computes the permissions (hfa.h:305-309), so the work at hfa.cc:340 is done before the duplicate is found and deleted (hfa.cc:349-351).- Partition refinement repeats over all partitions until a pass makes no split (hfa.cc:791-827).
- A comment notes that the breadth-first work queue costs peak memory (hfa.cc:504-508).
-D dfa-progressprints a status line every 1000 states (hfa.cc:446-454). - The 16-bit check: chfa.cc:435-439.
- Not measured: peak memory, and whether refinement is quadratic on real profiles (2387 states take well under a second).
for AppArmor developers for security researchers
Read more
09 Where to go from here
Next: the expression tree, building the DFA, permissions in the DFA, minimisation, table compression, the binary policy format. Around the backend: how the kernel checks an access, the pipeline, the policy cache, kernel features.
That's the backend from the air: three machines per profile, nine stages each, and a dump for every stage. Six more decks walk the same three rules through the stages one at a time: the expression tree, building the states, their permissions, the merging, the tables, the bytes. If you'd rather see the finished machine at work first, that's the deck on how the kernel checks an access. And if you run the parser for a living, the policy cache gets a later deck of its own.
Details and sources
Details
- The expression tree: the patterns of all rules become one tree.
- Building the DFA: states are built from sets of tree positions. Permissions in the DFA: what each state allows, denies and audits.
- Minimisation: filter deny, then merging equal states.
- Table compression: the rows packed into arrays. The binary policy format: the bytes written to the kernel.
- Around the backend: From profile text to kernel, From AARE to regular expressions, The policy cache, Kernel features and the policy ABI, Testing AppArmor.
- Read 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 kernel feature set given to the parser is named where it matters: the tree's abi/5.0 file, or a file with the policy entries the kernel exports. "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.
What a compile costs
Compile time follows the number of states the rules turn into, not the number of rules. apparmor_parser -Q -K -D dfa-stats FILE prints one Created dfa: states N line per state machine (tree).
| Profile | States created | After merging | Table slots | Bytes of -S | Time |
|---|---|---|---|---|---|
the three-rule demo profile | 38 | 22 | 277 | 5009 | none to speak of |
base, nameservice, user-tmp abstractions and one rule | 2387 | 1695 | 2476 | 41913 | well under a second |
the same with -O no-minimize | 2387 | 2387 | 3302 | 55081 | well under a second |
the same with -O 0 | 3160 | 3160 | 7799 | 84289 | well under a second |
one rule /srv/**x?????????????? (14 question marks) | 32774 | 32774 | 58559 | not measured | well under a second |
one rule /srv/**x??????????????? (15 question marks) | 65542 | 65542 | 116981 | error | about 1.5 s |
Measured with a feature set that has the kernel's policy entries, so diff encoding is on except with -O 0 (tree). Start-up of just under 2 seconds was taken off the times. Without diff encoding the slots are 3198 (default), 6170 (-O no-minimize), 117145 and 234039 (the two one-rule profiles).
| Message | Meaning | Exit status |
|---|---|---|
Too many states (N) for type state_t | one state machine needs more than 65534 states | 1 |
Too many transitions (N) for type state_t | the packed table has more slots than a 16-bit number can address | 1 |
- Neither message names the profile.
-O state32lifts the limit when the kernel's features listpolicy/state32(code). - A cache hit skips the compile. The profile and its includes are still read, to compare their times with the cache file's (code).
- A miss happens when the profile or any file it includes is newer than the cache file, or when the cache file fails its format check: for a file that is not compressed, the 12-byte
versionmarker and the version word this parser would write; for a compressed file, the 8-byte header (header version, zstd magic and level), with no test of the version word (code). - No cache is used for standard input, for force-complain, and for a profile in a namespace (code).
-Kskips the cache,-Wwrites it,-j Ncompiles N profiles at once.
for AppArmor developers for security researchers
The stages of create_chfa
| Stage | Call | Lines | Runs when |
|---|---|---|---|
| tree | build_tree | aare_rules.cc:162-187, aare_rules.cc:223 | always |
| DFA | DFA dfa(root, opts, filedfa) | aare_rules.cc:260 | always |
| filter deny | dfa.apply_and_clear_deny() | aare_rules.cc:273-278 | permstable32_version < 2, or filter-deny |
| minimize | dfa.minimize(opts) | aare_rules.cc:279-285 | minimize |
| unreachable | dfa.remove_unreachable(opts) | aare_rules.cc:287-291 | remove-unreachable (off by default) |
| equiv | dfa.equivalence_classes, apply_equivalence_classes | aare_rules.cc:298-308 | equiv (off by default) |
| diff encode | dfa.diff_encode(opts) | aare_rules.cc:310-315 | diff-encode |
| perms table | dfa.compute_perms_table(perms_table) | aare_rules.cc:318-333 | permstable32_version >= 2 |
| CHFA | new CHFA(dfa, eq, opts, permstable32_version) | aare_rules.cc:334 | always |
All rows: code.
for AppArmor developers for security researchers
The three DFAs
| DFA | Built by | Input | filedfa | permstable32_version | States in the example |
|---|---|---|---|---|---|
| xmatch | process_profile_name_xmatch (parser_regex.c:478-627) | attachment or local name, alias names, xattrs as a tail | false | -1 | 15 created, 15 kept |
| file | process_profile_regex (parser_regex.c:789-808) | path rules, link pairs, change_profile | true | what the kernel supports | 38 created, 22 kept |
| policydb | process_profile_policydb (parser_regex.c:1338-1461) | every other rule class, plus one marker rule per mediated class | false | what the kernel supports | 6 created, 5 kept |
Builders and arguments: code. State counts: tree, the same with both feature sets.
for AppArmor developers for security researchers
-O options
| Name | Default | Effect | Cleared when the kernel lacks |
|---|---|---|---|
expr-normalize | on | normalise the tree before simplification | |
expr-simplify | on | simplify and factor the tree | |
expr-vector | on | flatten alternations into vectors before factoring | |
expr-left-simplify | off | factor from the left first (expr-right-simplify is the same bit, inverted) | |
minimize | on | merge equal states | |
filter-deny | on | fold deny into allow before minimizing; forced when permstable32_version < 2 | |
remove-unreachable | off | drop states no path reaches | |
equiv | off | equivalence classes of input bytes | |
diff-encode | on | store a state as a difference from another | policy/diff-encode (or diff_encode) |
state32 | off | 32-bit state numbers | policy/state32 |
flags-table | off | write a per-state flags table | policy/flags_table, or state32 |
compress-small | off | slower, tighter packing (compress-fast is the same bit, inverted); zstd level 20 when none is given | |
compress-default | off | pack using default states | |
rule-merge | on | merge rules in the front end | |
zstd-recompress | off | recompress the policy stream |
Table and defaults: code (common_optarg.c:87-127, parser_common.c:123-129, parser_main.c:1791-1801). The effect column is a summary of the help text and of the stage each flag guards.
for AppArmor developers for security researchers
-D options by stage
| Stage | Option |
|---|---|
| AARE to regular expression, rule to tree | rule-exprs |
| Tree | expr-tree, expr-simplified, expr-stats |
| Subset construction | dfa-stats, dfa-progress, dfa-node-map, dfa-perms-build |
| Permission sets | dfa-uniq-perms, dfa-minimize-uniq-perms |
| States | dfa-states-initial, dfa-states-post-filter, dfa-states-post-minimize, dfa-states-post-unreachable, dfa-states, dfa-compressed-states |
| Minimization | dfa-minimize-partitions |
| Unreachable states | dfa-unreachable |
| Equivalence classes | equiv, equiv-stats |
| Diff encoding | diff-encode, diff-stats, diff-progress |
| Packed tables | compressed-dfa, compress-stats, compress-progress, state32 |
| Graphviz | dfa-graph |
| Groups | stats, progress |
Code (common_optarg.c:30-85); the lines where each is printed are in the details of the scene "A dump for every stage".
for AppArmor developers for security researchers
Messages
| Message | Where | Exit status |
|---|---|---|
profile has merged rule with conflicting x modifiers | hfa.cc:1703-1707 | followed by the next line |
ERROR processing regexs for profile %s, failed to load | parser_regex.c:1277 | 255 (tree, abi/5.0) |
Conflicting --Optimize options: compress-default, compress-small | parser_main.c:663-667 | |
Invalid --Optimize option %s | parser_main.c:659-660 | |
Too many states (N) for type state_t | chfa.cc:435-439 | 1 (tree, abi/5.0) |
for AppArmor developers for security researchers
Known discrepancies
-O 0leavesexpr-vector,filter-deny,rule-mergeandequivas they were and clearsstate32; its help text says "no optimizations" (common_optarg.c:88-93) (code).-D dfa-minimizeis accepted and has no effect (common_optarg.c:54) (code).std::runtime_errorfromminimizeandcompute_perms_tableis not caught by thecatch (int)increate_chfa(hfa.cc:883, hfa.cc:1452-1454, aare_rules.cc:340-342) (code; not reproduced).create_dfablobreturns NULL with*sizestill set whenmallocfails (aare_rules.cc:380-384) (code; not reproduced).- With the tree's
abi/5.0file as kernel features the parser compiles for kernel ABI 5: version word 5 and no file class marker in policydb (tree). - The optional DFA cache, by title: "DFA cache key leaves out the permstable32 version that its comment says it covers", "The DFA cache stores entries that its lookup always rejects", "The DFA cache renames a short file into place when the final write fails in fclose()", "The DFA cache writes through a symlink at a predictable temp name and leaks temp files", "A corrupted DFA cache entry is accepted as a hit".
for AppArmor developers for security researchers
Not determined
- Peak memory of a compile.
- What
-D rule-mergeprints. - Whether the missing
diff-encodeentry in the tree'sabi/5.0file is intended.
Roads from here
START HERE
- How the kernel checks an access — the finished machine walked by the kernel
- From profile text to kernel — the whole parser run around the backend
RUNNING THE PARSER
- The policy cache (no slides yet) — the cache that skips this work
- Kernel features and the policy ABI — the feature set that switches stages on and off
INSIDE THE PARSER
- From AARE to regular expressions — where rules are handed to the backend
THE DFA ENGINE · libapparmor_re
- The expression tree — stage one where patterns become one expression tree
- Building the DFA — stage two where states are built from the tree
- Permissions in the DFA — what each state allows
- Minimisation — filter deny and merging states
- Table compression — packing the rows into arrays
- The binary policy format — the bytes written to the kernel
TESTING
- Testing AppArmor (no slides yet) — the tests that compare state counts