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

Part of journeys

01 Three rules in, three tables out

THE BACKEND profile demo /usr/bin/demo {/etc/demo/** r,audit deny @{HOME}/.ssh/** rw,/usr/bin/[a-z]* ix,} demo, cut down to three rules apparmor_parserthe backend attachment15 states file rules22 states other rule classes5 states the kernel 5009 bytes, one write This deck is the map of that work. Each stage has a deck of its own. runs once per profile, at load time, unless the cache has the result
The three-rule demo profile enters the backend of apparmor_parser, which produces three state machines with 15, 22 and 5 states for attachment, file rules and other rule classes; the kernel receives them as 5009 bytes in one write

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 from apparmor_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 the policy entries the kernel exports; the tree's own abi/5.0 file gives the same counts and the same size.
  • -Q skips the kernel load, -K skips the cache, -S writes 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

for AppArmor developers for security researchers

In the code

02 One profile, three DFAs for AppArmor developers for security researchers

THREE INPUTS profile demo /usr/bin/demo { /etc/demo/** r, audit deny @{HOME}/.ssh/** rw, /usr/bin/[a-z]* ix, } xmatchprocess_profile_name_xmatch 15 states rule: /usr/bin/demo -> ... (0x1/0)< 0x1> file DFAprocess_profile_regex 38 created, 22 kept (no other rules) policydbprocess_profile_policydb 6 created, 5 kept rule: \d2 -> \x2 priority=1001 (0x4/0)< 0x4> one marker rule per mediated class built in this order; dump lines carry no label
The head line of the demo profile feeds the xmatch DFA with 15 states, the three file rules feed the file DFA with 38 states created and 22 kept, and marker rules for each mediated class feed the policydb DFA with 6 states created and 5 kept

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

for AppArmor developers for security researchers

Read more

03 create_chfa: nine stages, one function for AppArmor developers for security researchers

aare_rules::create_chfa tree DFA build_tree DFA dfa(root, ...) filter deny minimize apply_and_clear_deny dfa.minimize unreachable equiv remove_unreachable equivalence_classes off by default diff encode perms table CHFA dfa.diff_encode compute_perms_table new CHFA(dfa, eq, ...) create_dfablob -> flex_table -> bytes a stage that fails returns NULL: the profile fails to load
The nine stages of create_chfa as a strip of boxes: tree, DFA, filter deny, minimize, unreachable, equiv, diff encode, perms table, CHFA, each with the call that performs it; unreachable and equiv are off by default; the CHFA is written as bytes by create_dfablob

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):
StageCallLinesRuns when
tailbuild the tail's tree, put a separator in frontaare_rules.cc:203-221a tail rule set is given (xattrs)
treebuild_treeaare_rules.cc:162-187, called at aare_rules.cc:223always
(numbering)label_nodes(root)aare_rules.cc:235always; for dumps
DFADFA dfa(root, opts, filedfa)aare_rules.cc:260always
filter denydfa.apply_and_clear_deny()aare_rules.cc:273-278permstable32_version < 2, or filter-deny
minimizedfa.minimize(opts)aare_rules.cc:279-285minimize
unreachabledfa.remove_unreachable(opts)aare_rules.cc:287-291remove-unreachable
equivdfa.equivalence_classes, apply_equivalence_classesaare_rules.cc:298-308equiv
diff encodedfa.diff_encode(opts)aare_rules.cc:310-315diff-encode
perms tabledfa.compute_perms_table(perms_table)aare_rules.cc:318-333permstable32_version >= 2
CHFAnew CHFA(dfa, eq, opts, permstable32_version)aare_rules.cc:334always
  • The function returns NULL when there are no rules (aare_rules.cc:227-228) or when a stage inside its try block throws an int (aare_rules.cc:340-342).
  • The message chain for conflicting exec modifiers: perms_t::perms_t prints profile has merged rule with conflicting x modifiers and throws (hfa.cc:1703-1707); the caller prints ERROR 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 the abi/5.0 feature set.
  • create_dfablob calls create_chfa, has flex_table write the table set into a stream and copies it into a malloc buffer (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_error thrown by minimize and compute_perms_table (hfa.cc:883, hfa.cc:1452-1454) is not caught by the catch (int), which is the only handler; build_tree runs before the try block. No other handler in the parser catches it. Not reproduced.
  • Known discrepancy: create_dfablob returns NULL with *size still set when malloc fails (aare_rules.cc:380-384). Not reproduced.

04 The file DFA, stage by stage for AppArmor developers for security researchers

THREE RULES THROUGH THE STRIP tree DFA filter deny minimize unreachable equiv diff encode perms table CHFA 3groups, oneper permission 38states 38states, 16 nowcarry nothing 22states 0of 22encoded 8rows 277slots,50 used Created dfa: states 38 proto { cache: size=38 dups=40 longest=4 avg=1 }, ...Minimized dfa: final partitions 22 (accept 2) init 4 (accept 2)Compressed trans table: states 22, next/check 277, optimal next/check 50 ... -D stats, the second of three blocks 1528 bytes as a table set
The file DFA of the three rules counted after each stage: 3 groups in the tree, 38 states, 38 after filter deny with 16 carrying nothing, 22 after minimize, 0 of 22 diff encoded, 8 permission rows, 277 slots with 50 used, 1528 bytes

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 the policy entries the kernel exports. The lines for the three DFAs, in the order xmatch, file, policydb (escape codes removed; the tree's abi/5.0 gives the same lines except Diff 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 dfa is 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 removed is printed when nothing merged. See Minimisation.
  • Compressed trans table: the packed size against a full table, 4*N + 6*S bytes over 512*S for N next/check slots and S states. See Table compression.
  • "16 now carry nothing": the 16 states that exist only for the audit deny rule 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-deny the second line becomes Dfa minimization no states removed: partitions 38 init 5 (accept 3) (run with the abi/5.0 feature set).
  • The three table sets are 1344, 1168 and 1528 bytes; 1528 is the file DFA's.
  • stats is a group of dump flags (common_optarg.c:37-42). The parser prints some of the lines with terminal escape codes; strip them with sed 's/\x1b\[[0-9;]*[A-Za-z]//g'.

05 A dump for every stage for AppArmor developers for security researchers

-D: A DUMP FOR EVERY STAGE tree DFA filter deny minimize unreachable equiv diff encode perms table CHFA treerule-exprs expr-tree expr-stats DFAdfa-states-initial dfa-stats dfa-perms-build filter denydfa-states-post-filter minimizedfa-minimize-partitions dfa-states-post-minimize unreachable, equivdfa-unreachable equiv diff encodediff-encode diff-stats perms table, CHFAcompressed-dfa compress-stats $ apparmor_parser -Q -K -D rule-exprs -D dfa-states demo3.sd -Q no load, -K no cache; dumps go to stderr stats and progress are groups; dfa-graph writes Graphviz
The -D dump options listed under the stage each one shows, from rule-exprs for the tree to compressed-dfa for the packed tables, and a command that prints two of them without loading the profile

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

StageOptionPrinted at
AARE to regular expression, rule to treerule-exprsparser_regex.c:142-143, parser_regex.c:441-442, aare_rules.cc:112-135
Tree statisticsexpr-statsexpr-tree.cc:972-976, expr-tree.cc:1021-1042
Treeexpr-tree, expr-simplifiedaare_rules.cc:236-240, aare_rules.cc:251-255
Permission of each statedfa-perms-buildhfa.cc:1558-1651, hfa.cc:1670-1702
Subset constructiondfa-stats, dfa-progress, dfa-node-maphfa.cc:446-454, hfa.cc:522-535
Permission setsdfa-uniq-perms, dfa-minimize-uniq-permsaare_rules.cc:261-262, aare_rules.cc:281-282
Statesdfa-states-initial, dfa-states-post-filter, dfa-states-post-minimize, dfa-states-post-unreachable, dfa-statesaare_rules.cc:264-293
Minimizationdfa-minimize-partitionshfa.cc:770-771, hfa.cc:838-839, hfa.cc:847-894
Unreachable statesdfa-unreachablehfa.cc:621-628
Graphvizdfa-graphaare_rules.cc:295-296
Equivalence classesequiv, equiv-statsaare_rules.cc:303-308, hfa.cc:1357-1359
Diff encodingdiff-encode, diff-stats, diff-progressaare_rules.cc:313-314, hfa.cc:1069-1072, hfa.cc:1096-1099
Perms table and packed tablescompressed-dfaaare_rules.cc:322-336
Packing statisticscompress-stats, compress-progresschfa.cc:201-208
States with packed numbersdfa-compressed-statesaare_rules.cc:337-338
Table widthstate32chfa.cc:524-525, chfa.cc:532-533
  • stats and progress are groups (common_optarg.c:37-42).
  • dfa-states is printed before diff encoding and dfa-compressed-states after 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-minimize is accepted and no code tests the flag (common_optarg.c:54).
  • Known discrepancy: -D expr-tree and -D expr-simplified print the same tree (aare_rules.cc:236-255).
  • Known discrepancy: the same table is flags_table with an underscore as a dump option and flags-table with 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

06 What runs by default for AppArmor developers for security researchers

-O: WHAT RUNS BY DEFAULT on expr-normalizeexpr-simplifyexpr-vectorminimizediff-encoderule-mergefilter-deny off equivremove-unreachableexpr-left-simplifycompress-smallcompress-default state32flags-tablezstd-recompress kernel features: policy/ diff-encode state32 flags_table if its entry is missing: flag cleared, no message permstable32_version < 2 filter-deny forced always for xmatch $ apparmor_parser -O no-minimize -O show known discrepancy: -O 0 leaves expr-vector, filter-deny, rule-merge and equiv as they were
Seven -O flags are on by default and eight are off; the kernel feature set clears diff-encode, state32 and flags-table when its policy entries are missing; filter-deny is forced when the permission table is not used

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 is dfaoptflag_table (common_optarg.c:87-127). -O show prints 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-encode is cleared without policy/diff_encode or policy/diff-encode; state32 without policy/state32; flags-table without policy/flags_table or 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.0 file has no diff-encode entry; the kernel advertises policy/diff-encode (apparmorfs.c:2635).
  • filter-deny is forced for any DFA built with permstable32_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-small and compress-fast are one bit with opposite sense, as are expr-left-simplify and expr-right-simplify (common_optarg.c:99-102, common_optarg.c:110-114). compress-small also selects zstd level 20 for the policy stream when no level is given (parser_main.c:494-495).
  • Known discrepancy: -O 0 clears expr-normalize, expr-simplify, minimize, remove-unreachable, diff-encode, state32 and flags-table, and leaves expr-vector, filter-deny, rule-merge and equiv as 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

07 What a compile costs, and what the cache saves

COST $ apparmor_parser -Q -K -D dfa-stats usr.bin.demo Created dfa: states 38 ... three rules: no time at all Created dfa: states 2387 ... three abstractions and one rule: well under a second Created dfa: states 65542 ... one rule: /srv/**x??????????????? Too many states (65542) for type state_t a couple of seconds, exit status 1 profile text and includes read and parsed every time /var/cache/apparmor/ hit: compile skipped the kernel miss: the profile or a file it includes is newer than the cache file -K skip the cache -W write it -j N compile N profiles at once
Three compiles with their state counts: 38 states for three rules, 2387 for a profile with three abstractions, and 65542 for one rule with a double star and fifteen question marks, which fails with Too many states; on a cache hit the profile text is still read but the compile is skipped

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-stats prints one Created dfa line 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 policy entries, 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:
ProfileStates createdAfter mergingTable slotsBytes of -STime
the three-rule demo profile38222775009none to speak of
base, nameservice, user-tmp abstractions and one rule23871695247641913well under a second
one rule /srv/**x?????????????? (14 question marks)327743277458559not measuredwell under a second
one rule /srv/**x??????????????? (15 question marks)6554265542116981errorabout 1.5 s
  • The error Too many states (65542) for type state_t names no profile and does not mention -O state32, which lifts the limit when the kernel's features list policy/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-cache prints file '%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 version marker 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).
  • -j runs 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".

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 state32 and the kernel feature are handled at chfa.cc:514-535.
  • A second, optional cache holds single DFAs: --dfa-cache-loc, compiled in only with USE_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

HOT SPOTS tree DFA filter deny minimize unreachable equiv diff encode perms table CHFA DFA add_new_state: one State per distinct node set hfa.cc:329-358 perms computed for every target, then the duplicate is deleted hfa.cc:340, 349-351 minimize rescan every partition until a pass splits nothing hfa.cc:791-827 created kept slots -S bytes default 2387 1695 2476 41913 -O no-minimize 2387 2387 3302 55081 -O 0 3160 3160 7799 84289 base + nameservice + user-tmp and one rule -O 0 also turns diff encoding off no limit and no warning before the 16-bit check when the tables are written
The DFA and minimize stages are the hot spots: one State per distinct node set, permissions computed for every target before the duplicate is deleted, and a refinement loop that rescans until nothing splits; a table of states and sizes for a profile with three abstractions under default options, no-minimize and -O 0

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 policy entries, so diff encoding is on by default (-D stats, and the size of the -S output). The profile is profile big /usr/bin/big { include <abstractions/base> include <abstractions/nameservice> include <abstractions/user-tmp> /etc/demo/** r, } after abi <abi/5.0>, and include <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 no policy/diff-encode entry such as the tree's abi/5.0) the default table has 3198 slots and the -O no-minimize table 6170.
  • add_new_state creates a State for a set of nodes and looks it up among the existing ones (hfa.cc:329-358). The State constructor 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-progress prints 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

ROADS The expression treepatterns to one tree Building the DFAthe states Permissions in the DFAwhat a state carries Minimisationthe merging Table compressionthe tables The binary policy formatthe bytes How the kernel checks an accessthe finished machine at work The policy cacheif you run the parser for a living
Roads from this deck: the six stage decks in pipeline order, from the expression tree to the binary policy format, plus how the kernel checks an access and the policy cache

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

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).

ProfileStates createdAfter mergingTable slotsBytes of -STime
the three-rule demo profile38222775009none to speak of
base, nameservice, user-tmp abstractions and one rule23871695247641913well under a second
the same with -O no-minimize23872387330255081well under a second
the same with -O 031603160779984289well under a second
one rule /srv/**x?????????????? (14 question marks)327743277458559not measuredwell under a second
one rule /srv/**x??????????????? (15 question marks)6554265542116981errorabout 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).

MessageMeaningExit status
Too many states (N) for type state_tone state machine needs more than 65534 states1
Too many transitions (N) for type state_tthe packed table has more slots than a 16-bit number can address1
  • Neither message names the profile. -O state32 lifts the limit when the kernel's features list policy/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 version marker 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).
  • -K skips the cache, -W writes it, -j N compiles N profiles at once.

for AppArmor developers for security researchers

The stages of create_chfa

StageCallLinesRuns when
treebuild_treeaare_rules.cc:162-187, aare_rules.cc:223always
DFADFA dfa(root, opts, filedfa)aare_rules.cc:260always
filter denydfa.apply_and_clear_deny()aare_rules.cc:273-278permstable32_version < 2, or filter-deny
minimizedfa.minimize(opts)aare_rules.cc:279-285minimize
unreachabledfa.remove_unreachable(opts)aare_rules.cc:287-291remove-unreachable (off by default)
equivdfa.equivalence_classes, apply_equivalence_classesaare_rules.cc:298-308equiv (off by default)
diff encodedfa.diff_encode(opts)aare_rules.cc:310-315diff-encode
perms tabledfa.compute_perms_table(perms_table)aare_rules.cc:318-333permstable32_version >= 2
CHFAnew CHFA(dfa, eq, opts, permstable32_version)aare_rules.cc:334always

All rows: code.

for AppArmor developers for security researchers

The three DFAs

DFABuilt byInputfiledfapermstable32_versionStates in the example
xmatchprocess_profile_name_xmatch (parser_regex.c:478-627)attachment or local name, alias names, xattrs as a tailfalse-115 created, 15 kept
fileprocess_profile_regex (parser_regex.c:789-808)path rules, link pairs, change_profiletruewhat the kernel supports38 created, 22 kept
policydbprocess_profile_policydb (parser_regex.c:1338-1461)every other rule class, plus one marker rule per mediated classfalsewhat the kernel supports6 created, 5 kept

Builders and arguments: code. State counts: tree, the same with both feature sets.

for AppArmor developers for security researchers

-O options

NameDefaultEffectCleared when the kernel lacks
expr-normalizeonnormalise the tree before simplification
expr-simplifyonsimplify and factor the tree
expr-vectoronflatten alternations into vectors before factoring
expr-left-simplifyofffactor from the left first (expr-right-simplify is the same bit, inverted)
minimizeonmerge equal states
filter-denyonfold deny into allow before minimizing; forced when permstable32_version < 2
remove-unreachableoffdrop states no path reaches
equivoffequivalence classes of input bytes
diff-encodeonstore a state as a difference from anotherpolicy/diff-encode (or diff_encode)
state32off32-bit state numberspolicy/state32
flags-tableoffwrite a per-state flags tablepolicy/flags_table, or state32
compress-smalloffslower, tighter packing (compress-fast is the same bit, inverted); zstd level 20 when none is given
compress-defaultoffpack using default states
rule-mergeonmerge rules in the front end
zstd-recompressoffrecompress 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

StageOption
AARE to regular expression, rule to treerule-exprs
Treeexpr-tree, expr-simplified, expr-stats
Subset constructiondfa-stats, dfa-progress, dfa-node-map, dfa-perms-build
Permission setsdfa-uniq-perms, dfa-minimize-uniq-perms
Statesdfa-states-initial, dfa-states-post-filter, dfa-states-post-minimize, dfa-states-post-unreachable, dfa-states, dfa-compressed-states
Minimizationdfa-minimize-partitions
Unreachable statesdfa-unreachable
Equivalence classesequiv, equiv-stats
Diff encodingdiff-encode, diff-stats, diff-progress
Packed tablescompressed-dfa, compress-stats, compress-progress, state32
Graphvizdfa-graph
Groupsstats, 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

MessageWhereExit status
profile has merged rule with conflicting x modifiershfa.cc:1703-1707followed by the next line
ERROR processing regexs for profile %s, failed to loadparser_regex.c:1277255 (tree, abi/5.0)
Conflicting --Optimize options: compress-default, compress-smallparser_main.c:663-667
Invalid --Optimize option %sparser_main.c:659-660
Too many states (N) for type state_tchfa.cc:435-4391 (tree, abi/5.0)

for AppArmor developers for security researchers

Known discrepancies

  • -O 0 leaves expr-vector, filter-deny, rule-merge and equiv as they were and clears state32; its help text says "no optimizations" (common_optarg.c:88-93) (code).
  • -D dfa-minimize is accepted and has no effect (common_optarg.c:54) (code).
  • std::runtime_error from minimize and compute_perms_table is not caught by the catch (int) in create_chfa (hfa.cc:883, hfa.cc:1452-1454, aare_rules.cc:340-342) (code; not reproduced).
  • create_dfablob returns NULL with *size still set when malloc fails (aare_rules.cc:380-384) (code; not reproduced).
  • With the tree's abi/5.0 file 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-merge prints.
  • Whether the missing diff-encode entry in the tree's abi/5.0 file is intended.

Roads from here

START HERE

RUNNING THE PARSER

INSIDE THE PARSER

THE DFA ENGINE · libapparmor_re

TESTING