Matching at run time

walking the DFA for AppArmor developers for security researchers

The kernel code that answers a request from the compiled tables. One macro steps through base and check and next and default. A diff-encoded state retries a miss in another state. One input is not a byte. The final state's accept entry picks a row of the permission table - for a file the owner's or the other one. Every other rule class starts from its own state in the policydb. Then allow and audit and quiet decide the result and the log record.

On the map: in the kernel

▶ Watch this deck — 9 scenes, ~7 min

Worth seeing first

Part of journeys

01 From a hook to a verdict

MATCHING AT RUN TIME demo open("/etc/demo/motd", O_RDONLY) apparmor_file_open → aa_path_perm aa_str_perms(file rules, start, name) aa_dfa_matchwalks the name through the tables state 21 aa_lookup_condpermsturns the state into a row row 4 of the permission table request & ~allow aa_audit_file one comparison what to log for people who read the code, or who ask what the kernel checks
demo opens /etc/demo/motd. The open hook builds the name and calls aa_str_perms, which makes two calls: aa_dfa_match walks the name and returns state 21, and aa_lookup_condperms turns the state into row 4 of the permission table. Then the request is compared with the row and aa_audit_file decides what is logged

aa_str_perms (file.c:221) is aa_dfa_match plus aa_lookup_condperms; __aa_path_perm (file.c:233) compares and calls aa_audit_file. The example is the three-rule profile demo3.sd of the DFA engine decks.

Demo opens /etc/demo/motd. You know the picture from the start of the map: one machine, one step per character. This deck is that picture as kernel code, for the three-rule profile the DFA engine decks compiled. The open hook builds the file's name and hands it to aa_str_perms. That makes two calls. aa_dfa_match walks the name and returns a state: twenty-one. aa_lookup_condperms turns the state into a row of permissions. Then one comparison, and a function that decides what to log. We'll go in that order, then the other rule classes. It's for people who read the code, or who ask what the kernel checks.

Details and sources

Details

  • The profile, demo3.sd: /etc/demo/** r,, audit deny @{HOME}/.ssh/** rw,, /usr/bin/[a-z]* ix, in profile demo /usr/bin/demo. Its file DFA has 22 states in 277 slots and a permission table of 8 rows; the numbers are those of Table compression and How the tables are packed.
  • The hook: apparmor_file_open lsm.c:465-507 maps the open flags to a request (aa_map_file_to_perms, file.h:112-131) and calls aa_path_perm file.c:287-307, which asks every confined profile of the task's label (fn_for_each_confined). An exec does not come this way: its check is in the exec hook (Exec and domain transitions).
  • aa_state_t aa_str_perms(struct aa_policydb *file_rules, aa_state_t start, const char *name, struct path_cond *cond, struct aa_perms *perms) file.c:221-231.
  • __aa_path_perm file.c:233-251: if (request & ~perms->allow) e = -EACCES; then aa_audit_file(...).
  • The name is built by aa_path_name path.c:202; how a name can differ from what the program asked for is in The limits of name-based mediation.
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".
  • Seen the machine walked as a drawing? That is How the kernel checks an access, with a four-rule profile and 34 states. This deck uses the 22-state machine of the DFA engine decks.

Read more

02 One step: base, check, next, default

ONE STEP #define match_char(...)b = base[state];pos = (b & 0xffffff) + c;if (check[pos] != state)state = def[state];elsestate = next[pos]; /etc/demo read so far, then "/" state 174 + 47 = 5117next: 19 base + bytecheck then "m" state 195 + 109 = 1146def: 21 another state's slot aa_dfa_match: the same step for every byte up to the NUL no bounds test in the loop: every base, check, next and default entry was verified at load
The macro match_char: pos is the base of the state plus the byte; if check at pos holds the state, next gives the new state, otherwise default does. On the tables of the example: state 17 with a slash lands on slot 51, check holds 17, next gives 19. State 19 with an m lands on slot 114, check holds 6, so default gives 21

match_char (match.c:443-455) on the example: state 17, /: slot 51, check 17, next 19. State 19, m: slot 114, check 6, default 21. aa_dfa_match (match.c:518) runs it for every byte up to the NUL.

Here's the whole step, a macro called match_char. Take the state's entry in base and add the byte: that's a position. If check at that position holds our state number, the slot is ours, and next gives the new state. If not, default does. You tried this in the packing lab; here are the same two lookups. State seventeen gets a slash. Base four plus forty-seven is slot fifty-one. Check says seventeen, next says nineteen. Now an m: slot one fourteen, and check says six, someone else's slot. So default: twenty-one. aa_dfa_match repeats that until the string ends. The loop has no bounds test. Every index was verified at load.

Details and sources

Details

  • The macro as written match.c:443-455: u32 b = (base)[(state)]; unsigned int pos = base_idx(b) + (C); if ((check)[pos] != (state)) { (state) = (def)[(state)]; if (b & MATCH_FLAG_DIFF_ENCODE) continue; break; } (state) = (next)[pos]; break; inside do { } while (1). base_idx(X) is X & 0xffffff match.c:23. The continue is the next slide.
  • aa_state_t aa_dfa_match(const struct aa_dfa *dfa, aa_state_t start, const char *str) match.c:518-550 fetches the four table pointers once, returns 0 at once when started in state 0, and maps each byte through the equivalence class table first if the DFA has one.
  • The four arrays are u32 in the kernel whatever the stream held: aa_dfa_unpack widens 16-bit default, next and check tables at load match.c:277-305 match.c:411-421.
  • The numbers (derived from the unpacked tables of the example, as listed in the reference of How the tables are packed): state 17 has base 4, state 19 has base 5 and default 21; slot 114 belongs to state 6.
  • The start state of a file check is rules->file->start[AA_CLASS_FILE] file.c:244, which is DFA_START, 1, unless the stream says otherwise policy_unpack.c:1029-1032.
  • What "verified at load" covers match.c:154-236: default[i] < state_count; no unknown flag bits in a base entry; base_idx(base[i]) + 255 < the length of next and check; every next and check entry below state_count. The loader runs it when asked to verify states; Unpacking and verifying policy has the conditions.
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

03 A miss that tries again

A MISS THAT TRIES AGAIN base[state] bit 31: diff encoded 30 bit 29: out of band 28 … 24 bits 23 … 0: the offset /srv/**x?? r, the one-rule profile of the packing lab, 14 states state 10base 0x80000000 · default 6 byte "x": slot 120 is not its own default state 6the same byte again x state 7a hit: next[pos] verify_dfa follows every chain at load; a chain that returns to itself fails the load without the flag a miss ends in the default state; with it, the default state gets the byte
A base entry is a 32-bit word: bit 31 marks a diff-encoded state, bit 29 a state with an out-of-band transition, the low 24 bits are the offset. In the one-rule profile /srv/**x?? state 10 is diff encoded with default 6. An x in state 10 misses, the state becomes 6 and the same byte is tried again: state 6 has an entry for x, next is 7. The loader follows every chain and refuses a cycle

MATCH_FLAG_DIFF_ENCODE (0x80000000) in base[state]: a miss sets state = default[state] and repeats the lookup with the same input (match.c:447-451). verify_dfa rejects chains that loop (match.c:201-231).

One bit changes what a miss means. The top bit of a base entry marks a state as diff encoded: it stores only what differs from another state, and its default names that state. Demo's rules have none, so take the one-rule profile from the packing lab. State ten gets an x. The slot isn't its own, so we move to its default, state six. Without the flag we'd stop there. With it, the macro goes round again: same byte, new state. State six has an entry for x: seven. A chain can be longer, but it can't loop. At load, the kernel follows every chain and refuses a cycle.

Details and sources

Details

  • The flag bits of a base entry match.h:196-202: MATCH_FLAG_DIFF_ENCODE 0x80000000, MATCH_FLAG_OOB_TRANSITION 0x20000000. MARK_DIFF_ENCODE 0x40000000 and MARK_DIFF_ENCODE_VERIFIED 0x10000000 are written by the loader while it checks the chains and the second stays set afterwards. In the stream only the two flags may be set: MATCH_FLAGS_INVALID is every other bit of the top byte, the two marks included (0x5f000000), and a base entry with one of them fails the load: "AppArmor DFA state with invalid match flags" match.c:168-171.
  • A flagged state needs YYTH_FLAG_DIFF_ENCODE in the table set header match.c:172-177.
  • The chain check match.c:201-231: from each state, follow defaults while the flag is set, marking states; meeting a marked state or a state whose default is itself is an error.
  • The example is the second profile of How the tables are packed, scene "Like that state, except": states 10 to 13 have base 0x80000000 (the flag, offset 0) and the defaults 6 to 9. State 6 has the entries NUL to 0 and x to 7. The walk shown is derived from those tables.
  • The parser's comment gives the cost: at most 2m lookups for m bytes hfa.cc:985-1012. The kernel does not check that bound; it checks only that chains end.
  • The parser uses the encoding only when the kernel advertises policy/diff-encode; see Table compression.
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

04 Five walkers, one step

FIVE WALKERS, ONE STEP aa_dfa_matcha string, up to its NULpaths, profile names aa_dfa_match_lena buffer and a lengthan xattr value, binary fields aa_dfa_nextone bytea class, a signal number, a NUL aa_dfa_leftmatcha string; returns a count tooattachment only count: bytes read before the walk re-entered one of its last 32 states aa_dfa_match_untilstops at the first accepting statefinding //& in a label on stacksplitdfa, a table compiled into the kernel match_char the step inside all five
Five functions share the step. aa_dfa_match: a string up to its NUL, for paths and labels. aa_dfa_match_len: a counted buffer that may contain NUL bytes, for an xattr value. aa_dfa_next: one byte, for a class or signal number. aa_dfa_leftmatch: a string, and a count of bytes consumed before the walk re-entered one of its last 32 states, for attachment. aa_dfa_match_until: stops at the first accepting state, used to find //& in a label

aa_dfa_match, aa_dfa_match_len, aa_dfa_next, aa_dfa_leftmatch, aa_dfa_match_until and aa_dfa_matchn_until (match.c:473-824) all step with match_char.

The same step sits inside five functions. aa_dfa_match reads up to the terminating null. aa_dfa_match_len takes a length instead, so it can feed binary data, null bytes included: the value of an extended attribute, say. aa_dfa_next takes a single byte; you'll see it used for class numbers and signal numbers. aa_dfa_leftmatch also counts how far the walk got before it re-entered one of its last thirty-two states. Only attachment uses that count, to rank profiles. And the until pair stops at the first accepting state. Its one user is a tiny table built into the kernel, which finds //& in a label. All five use the same macro.

Details and sources

Details

  • aa_state_t aa_dfa_match_len(const struct aa_dfa *dfa, aa_state_t start, const char *str, int len) match.c:473-504: "will happily match again the 0 byte and only finishes when @len input is consumed". Callers: an xattr value domain.c:347-348, the : around a namespace name in a peer label label.c:1306-1308, a class number above the table policy.h:337-338.
  • aa_state_t aa_dfa_next(const struct aa_dfa *dfa, aa_state_t state, const char c) match.c:562-579. aa_dfa_null_transition is aa_dfa_next(dfa, start, 0) lib.h:139-144.
  • aa_state_t aa_dfa_leftmatch(const struct aa_dfa *dfa, aa_state_t start, const char *str, unsigned int *count) match.c:816-824 calls leftmatch_fb match.c:741-801: each state entered is stored in a ring of WB_HISTORY_SIZE (32) entries match.h:154-159; when the new state is in the ring (is_loop, match.c:720-739) the rest of the string is walked with aa_dfa_match and the count stops. A final state 0 sets the count to 0. Its only caller is find_attach domain.c:431-433; Profile attachment explains the count.
  • aa_dfa_match_until and aa_dfa_matchn_until match.c:612-708 return at the first state with a non-zero accept entry and report the position. aa_label_strn_split uses them on stacksplitdfa to find //& label.h:322-344; that table and nulldfa are compiled in and unpacked at boot lsm.c:2522-2565.
  • "All five" holds for the tree the map describes. In Linux 7.3.4, the kernel of the observed runs in this district, aa_dfa_match_until, aa_dfa_matchn_until and leftmatch_fb have the step written out without the continue: a miss in a diff-encoded state ends in its default state and the byte is not tried there. aa_dfa_match, aa_dfa_match_len, aa_dfa_next and the out-of-band step use match_char in both. Nothing in this deck was observed through the three that differ, and aa_dfa_leftmatch on a diff-encoded attachment table was not run on either kernel (findings/kernel/observed/README.md in the map's repository).
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

05 A separator that is a zero, and one that is not a byte

NOT A BYTE two names in one rule /usr/bin/demo-helper \0 sandbox an executable, then the profile to change to aa_dfa_null_transition(dfa, state) one step with byte 0 a path and its extended attributes /usr/bin/demo OOB \0 value bytes OOB not one of the 256 byte values aa_dfa_outofband_transition(dfa, state) match_char with -1: pos = base - 1 base[state]: MATCH_FLAG_OOB_TRANSITION without the flag: no such transition, state 0 checked at load: a flagged state has base ≥ 1, so base - 1 is a real slot
Rules with several parts are kept apart by two separators. The NUL byte: aa_dfa_null_transition is one step with byte 0, used between a link and its target and between an executable and a profile to change to. The out-of-band transition: the macro is called with minus one, so the slot is base minus 1; a flag in the base word marks a state that has one. Attachment uses it between the path and each xattr value

aa_dfa_null_transition (include/lib.h:139) steps with byte 0. aa_dfa_outofband_transition (match.c:581-597) needs MATCH_FLAG_OOB_TRANSITION in the base word and looks at slot base - 1. The kernel supports one out-of-band input.

A rule can have more than one part: a program and the profile to change to, a path and its extended attributes. Two separators keep the parts apart. The first is the null byte, which can't occur inside a name. aa_dfa_null_transition is one step with byte zero. The second isn't a byte. For the out of band transition the macro is called with minus one, so the slot is the one just below the state's base. A flag in the base word says the state has one, and the loader checks that its base is at least one. Attachment uses it between the path and each attribute value.

Details and sources

Details

  • aa_state_t aa_dfa_outofband_transition(const struct aa_dfa *dfa, aa_state_t state) match.c:581-597: if (!(b & MATCH_FLAG_OOB_TRANSITION)) return DFA_NOMATCH; then match_char(state, def, base, next, check, -1); with the comment "No Equivalence class remapping for outofband transitions".
  • At load match.c:178-187: a flagged state with base_idx(base) < dfa->max_oob fails ("AppArmor DFA out of bad transition out of range"), as does a flagged state when the header lacks YYTH_FLAG_OOB_TRANS. max_oob is fixed at 1; the code that would read a larger number from the header is commented out match.c:348-360. MAX_OOB_SUPPORTED is 1 match.h:44.
  • The user: aa_xattrs_match domain.c:313-375 steps out of band after the executable's name and after each attribute; for an attribute that is present it steps over a NUL and then feeds the value with aa_dfa_match_len. A missing attribute that the profile requires leaves state 0.
  • The null transition lib.h:139-144 is used for a link and its target file.c:368, for an exec name and the label of a pending change_onexec ("exec\\0change_profile", domain.c:843-849), between the fields of a mount rule mount.c:172-197 and in unix socket rules af_unix.c:80-98.
  • The parser side, where the tree gets a symbol outside the byte range: Building the DFA, scene "One input that is not a byte".
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

06 From a state to a row

FROM A STATE TO A ROW state 21 /etc/demo/motd read accept[21] = 4 an index, not permissions accept2[21] = 1 the flag: an owner pair fsuid of the task == owner of the file ? yes: perms[4] no: perms[5] aa_lookup_condperms aa_lookup_perms, for classes without an owner: perms[accept[state]] perms[4]allow 0x244deny 0audit 0quiet 0xindex 0…read 0x4 · open 0x40 · getattr 0x200 a row is thirteen 32-bit fields: allow deny subtree cond kill complain prompt audit quiet hide xindex tag label no table in the policy: the kernel builds one at load from the old accept words file DFA: two rows per state, and accept[state] becomes state × 2
The walk ends in state 21. accept[21] is 4, an index into the permission table of the same DFA. accept2[21] has the owner flag, so aa_lookup_condperms compares the task fsuid with the owner of the file: equal gives row 4, different gives row 5. Row 4 has allow 0x244: read, open and getattr. Other classes use aa_lookup_perms, which takes the row as it is. A policy without a table gets one built at load

aa_lookup_condperms (file.c:194-209): perms[accept[state]], or the next row when accept2[state] has ACCEPT_FLAG_OWNER and the fsuid is not the file's owner. aa_lookup_perms (include/policy.h:156) has no owner test. Example: state 21, rows 4 and 5, allow 0x244.

The walk leaves us in state twenty-one. What may demo do there? The accept table has one entry per state: an index into the permission table of the same DFA. State twenty-one says four. A second table, accept2, flags it as an owner pair. So aa_lookup_condperms compares the user ID demo runs as with the file's owner. Equal: row four. Different: row five. Other rule classes have no owner, and aa_lookup_perms takes the row as it is. A row is thirteen numbers: allow, deny, audit, quiet and the rest. Policy without a table gets one built at load from the old accept words, so this is the only lookup.

Details and sources

Details

  • struct aa_perms *aa_lookup_condperms(kuid_t subj_uid, struct aa_policydb *rules, aa_state_t state, struct path_cond *cond) file.c:194-209; the uid passed is current_fsuid() file.c:227. ACCEPT_FLAG_OWNER is 1 policy.h:61-63. A policydb without a table gives &default_perms, all zero file.c:182.
  • static inline struct aa_perms *aa_lookup_perms(struct aa_policydb *policy, aa_state_t state) policy.h:156-165.
  • struct aa_perms perms.h:69-88: allow, deny, subtree, cond, kill, complain, prompt, audit, quiet, hide, xindex, tag, label.
  • The example's table (tree run recorded in Permissions in the DFA): rows 0 and 1 0x200 (no match), 2 and 3 0x200 (left by the deny rule), 4 and 5 0x244 (the r rule), 6 and 7 0x10201 with the inherit bit in xindex (the ix rule). State 21 has accept 4, state 20 accept 6, every other state 0; accept2 is 1 on every state except 0 and 1.
  • Which accept tables the kernel accepts policy_unpack.c:996-1006: with a permission table, accept is an index and, from version 3 of the table format, accept2 holds flags; without one both hold packed permissions.
  • The table built at load policy_compat.c:150-172 policy_compat.c:288-333: compute_fperms makes two rows per state and remap_dfa_accept(dfa, 2) sets accept[state] = state * 2 and the owner flag; the policydb gets one row per state. map_old_perms widens the old bits: read gives getattr and open; write gives setattr, create, delete, chmod, chown and open policy_compat.c:78-98.
  • At load every accept entry, and the entry after it for an owner pair, is checked to lie inside the table policy_unpack.c:1492-1509.
  • getattr (0x200) is in every row, also the row of state 0; that is why stat is allowed on every name (What is not mediated).
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

07 Every other class starts with one byte

A CLASS IS A FIRST BYTE policydb: one DFA capabilities, signals, ptrace, mounts, network, … capabilitybyte 3 mountbyte 7 ptracebyte 9 signalbyte 10 networkbyte 15 the first byte is the class number at load: start[c] = aa_dfa_next(dfa, start[0], c) once per class, kept in an array state = RULE_MEDIATES(rules, class) 0: this profile has no say capability start[3] byte cap >> 5 row bit 1 << (cap & 31) signal start[10] byte: the signal demo//&sandbox row the peer's label, as text
The policydb is one DFA for every class other than file rules. Its first byte is the class number: 3 capability, 7 mount, 9 ptrace, 10 signal, 15 network. At load the kernel steps once per class from the start state and stores the results in start[class]. A hook reads start of its class: 0 means the profile does not mediate the class. A capability is then one byte, cap >> 5, and one bit. A signal is the signal number and then the label of the peer as text

start[class] is filled at load (policy_unpack.c:1043-1046); RULE_MEDIATES (include/policy.h:331) returns it. Capability: byte cap >> 5, bit 1 << (cap & 0x1f) (capability.c:128-146). Signal: the signal number, then the peer label (ipc.c:93-99).

File rules have their own DFA. Everything else, capabilities, signals, ptrace, mounts, network, shares one: the policydb. Its first byte is the class number. The kernel doesn't walk that byte on every request. At load it steps once per class and keeps the results in an array. So a hook begins by reading the start state of its class. Zero means this profile says nothing about the class: the hook allows the request, or falls back to an older check. Otherwise it feeds the class's own bytes. A capability is one byte, then a bit in the row. A signal is its number, then the peer's label as text.

Details and sources

Details

  • struct aa_policydb policy.h:110-120: the DFA, the permission table and its size, the string table trans, tags, and aa_state_t start[AA_CLASS_LAST + 1]. A profile has three: rules->policy, rules->file and attach.xmatch policy.h:190-219.
  • Class numbers apparmor.h:19-44: file 2, capability 3, rlimits 5, domain 6, mount 7, ptrace 9, signal 10, xmatch 11, net 14, net v9 15, label 16, posix mqueue 17, module 19, display LSM 20, ns 21, io_uring 22, x 31, dbus 32 (AA_CLASS_LAST).
  • At load policy_unpack.c:1026-1047: start[0] from the stream or 1; for (i = AA_CLASS_FILE + 1; i <= AA_CLASS_LAST; i++) pdb->start[i] = aa_dfa_next(pdb->dfa, pdb->start[0], i);.
  • RULE_MEDIATES(rules, class) policy.h:331-339. A label carries a bit per mediated class, the OR over its profiles, so that a hook can skip a label without a walk: label_mediates label.h:253-256.
  • Capability capability.c:121-150: with a state, aa_dfa_next(dfa, state, cap >> 5), request = 1 << (cap & 0x1f), aa_lookup_perms, the profile's modes, aa_check_perms; with state 0 the capability sets stored in the profile are used.
  • Signal ipc.c:78-100: state 0 returns 0, allowed; otherwise aa_dfa_next(dfa, state, ad->signal) and aa_label_match for the peer (Labels in the kernel). Ptrace starts from start[AA_CLASS_LABEL] and steps over the byte for the ptrace class lib.c:393-405.
  • The example: the parser adds a marker rule per class it mediates, ten for this profile, so its policydb (5 states, 2 rows) has start states for them although the profile has only file rules (The backend pipeline).
  • Observed, with another profile that has no capability rule: apparmor="DENIED" operation="capable" class="cap" profile="demo" comm="demo" capability=1 capname="dac_override". Observed: a Debian guest with kernel 7.3.4 in a disposable virtual machine, parser 5.0.2; capability.c, lib.c, audit.c and include/policy.h are the same in that kernel and in the tree the map describes, and match.c and policy_unpack.c differ only outside aa_dfa_next and the loop that fills start[] (findings/kernel/observed/README.md in the map's repository).
  • Kernel statements are read from the kernel source and were not run, except where a bullet says "observed".

Read more

08 Allow, audit, quiet: the result and the record

THE VERDICT request & ~perms->allow the whole test for a file; deny is already out of allow demo runs in the row result kernel log cat /etc/demo/motdr in allow, no audit bitallowednothing echo x > /etc/demo/newcreate not in allowrefusedDENIED … "c" cat /root/.ssh/id_testaudit deny: quiet clearrefusedDENIED … "r" cat /root/.ssh/id_testplain deny: quiet setrefusednothing cat /etc/hostnamecomplain mode, no ruleallowedALLOWED … "r" other classes: aa_check_perms tests request & (~allow | deny), then quiet, kill and complain observed on a 7.3 kernel whose code for these functions is the same
For a file the kernel tests whether every requested bit is in allow. Four runs of demo on a real kernel: reading /etc/demo/motd is allowed and not logged; creating a file is refused and logged as DENIED; reading the key under the audit deny rule is refused and logged, because quiet is clear; with a plain deny rule the same read is refused and nothing is logged. In complain mode a refused read is logged as ALLOWED and goes ahead

__aa_path_perm (file.c:246) tests request & ~allow; aa_audit_file (file.c:95-154) applies audit, quiet, kill and complain mode. Other classes go through aa_check_perms (lib.c:425-464), which also reads deny and hide. The five results were observed on a running kernel.

Now the decision. For a file, the kernel tests one thing: is every requested bit in allow? Deny never arrives as deny. The parser already took those bits out of allow. What a deny rule adds is quiet. So, five runs. It reads its motd: allowed, and no audit bit, so nothing is logged. It creates a file there: refused, and logged as DENIED. It reads the key that the audit deny rule covers: refused and logged, because audit deny leaves quiet clear. With a plain deny, the same read is refused and nothing is logged. In complain mode, a read with no rule is logged ALLOWED, and goes ahead.

Details and sources

Details

  • aa_audit_file file.c:95-154. No error: request &= perms->audit (or 0xffff when the profile audits everything); nothing left, no record; otherwise an AUDIT record. An error: only the bits not in allow are reported; a bit in kill makes it KILL; request &= ~quiet unless the profile's audit mode is noquiet or all; nothing left, the error is returned silently.
  • aa_audit audit.c:200-237: in complain mode the type becomes ALLOWED and complain_error turns -EACCES into 0 audit.h:206-211; in kill mode DENIED becomes KILL and the task is sent the profile's signal.
  • What the parser did before file.c:246 could be this simple: denied bits are removed from allow, a plain deny sets the same bits in quiet, audit deny does not (Permissions in the DFA, scene "What becomes of a deny rule"). In the example the rows left by the audit deny rule equal the row of state 0.
  • Other classes lib.c:425-464: denied = request & (~perms->allow | perms->deny); an allowed request is logged for bits in audit; a denial returns -EACCES, or -ENOENT if all denied bits are in hide; quiet bits are dropped; aa_select_audit_type audit.c:143-152 gives KILL for a bit in kill, ALLOWED if every denied bit is in complain, else DENIED. aa_apply_modes_to_perms lib.c:364-391 sets those masks from the profile's mode and audit mode first.
  • A stacked label: each confined profile is asked separately and one refusal is enough file.c:302-304.
  • The records as logged: apparmor="DENIED" operation="mknod" class="file" profile="demo" name="/etc/demo/new" comm="demo" requested_mask="c" denied_mask="c" fsuid=0 ouid=0; apparmor="DENIED" operation="open" class="file" profile="demo" name="/root/.ssh/id_test" comm="demo" requested_mask="r" denied_mask="r" fsuid=0 ouid=0; apparmor="ALLOWED" operation="open" class="file" profile="democ" name="/etc/hostname" comm="democ" requested_mask="r" denied_mask="r" fsuid=0 ouid=0. The plain deny run used the same three rules with deny in place of audit deny (profile demoq); the complain run the same rules without the deny rule and flags=(complain) (profile democ), and the file it read, /etc/hostname, has no rule. A plain deny in a complain-mode profile stays refused and silent: the denied bits are quiet, so aa_audit_file returns the error before the complain-mode branch (file.c:139-149); read from the code, not run.
  • Observed: a Debian guest with kernel 7.3.4 in a disposable virtual machine, parser 5.0.2. file.c, lib.c and audit.c, which decide the result and the record, are the same in that kernel and in the tree the map describes; match.c differs, but not in aa_dfa_match, the walker a file check uses (findings/kernel/observed/README.md in the map's repository).
  • Known discrepancy: an audit deny file rule in a complain-mode profile is allowed and logged ALLOWED (the denial is not quiet, so it reaches the complain-mode branch of aa_audit). Read from the code here; not part of this run.

Read more

09 Where to go from here

ROADS match_char · accept → row · start[class] · request & ~allow How the tables are packedthe slots, to try yourself Table compressionthe base word, the table set Permissions in the DFAwhere a row comes from Exec and domain transitionsthe exec row and its index Labels in the kernela peer label as input Reading a denialthe log line, field by field How the kernel checks an accessthe same walk as a drawing
Roads from this deck: How the tables are packed and Table compression for the arrays, Permissions in the DFA for the rows, Exec and domain transitions and Labels in the kernel for the two lookups that continue from here, and Reading a denial for the log line

Next: the packing lab and table compression for the arrays, permissions in the DFA for the rows, exec and domain transitions and labels in the kernel for what continues from a row, reading a denial for the record.

That's a request in kernel code: one macro for the step, an accept entry that picks a row, a start state per class, and one test against allow. From here, the packing lab lets you run that lookup on the real arrays, and table compression is the reference for the base word. Permissions in the DFA shows how deny, audit and priority became a row before the kernel ever saw it. Two lookups continue from a row: the exec index, in exec and domain transitions, and a peer's label as input, in labels in the kernel. And reading a denial takes the log line apart, field by field.

Details and sources

Details

Read more

Read more

Basis of the statements on this page: "code" means the kernel source of mainline Linux at commit 97d73c825 was read and not run; "tree" means a number comes from the parser built from the AppArmor commit 836052d21, as recorded in Table compression, Permissions in the DFA and How the tables are packed; "derived" means reasoned from those tables or that code; "observed" means seen on a Debian guest with kernel 7.3.4 in a disposable virtual machine, where the files concerned (file.c, lib.c, audit.c) are the same as in the tree the map describes. match.c is not the same: in 7.3.4 aa_dfa_match_until, aa_dfa_matchn_until and leftmatch_fb have the step written out without the retry of a diff-encoded state, where the tree uses match_char. Nothing on this page was observed through those three.

The step

NameWhereWhat
match_char(state, def, base, next, check, C)match.c:443-455pos = base_idx(base[state]) + C; check[pos] == state: state = next[pos]; else state = def[state], and again with the same C if the base entry has MATCH_FLAG_DIFF_ENCODE
base_idx(X)match.c:23X & 0xffffff
DFA_NOMATCH, DFA_STARTmatch.h:17-180 and 1
aa_state_tmatch.h:135unsigned int
DEFAULT_TABLE, BASE_TABLE, NEXT_TABLE, CHECK_TABLE, ACCEPT_TABLE, ACCEPT_TABLE2match.h:93-99u32 * views of the tables; EQUIV_TABLE is u8 *

All code.

Flags in a base entry

BitNameMeaning
0x80000000MATCH_FLAG_DIFF_ENCODEa miss continues in the default state with the same input
0x40000000MARK_DIFF_ENCODEset and cleared by verify_dfa while it follows a chain
0x20000000MATCH_FLAG_OOB_TRANSITIONthe state has an out-of-band transition at slot base - 1
0x10000000MARK_DIFF_ENCODE_VERIFIEDleft set by verify_dfa on a checked diff-encoded state
0x5f000000MATCH_FLAGS_INVALIDevery bit of the top byte except the two flags, the two marks included: set in the stream, the load fails
0x00ffffffthe offset

match.h:196-202 (code). Header flags of a table set: YYTH_FLAG_DIFF_ENCODE 1, YYTH_FLAG_OOB_TRANS 2 match.h:40-42.

The walkers

FunctionInput endsReturnsCallers
aa_dfa_match(dfa, start, str) match.c:518-550at NULthe statefile names, profile names in a peer label, mount strings
aa_dfa_match_len(dfa, start, str, len) match.c:473-504after len bytesthe statexattr values, : in a peer label, a class byte above AA_CLASS_LAST
aa_dfa_next(dfa, state, c) match.c:562-579one bytethe stateclass start states, capability and signal bytes, the null transition
aa_dfa_outofband_transition(dfa, state) match.c:581-597one input, -1the state, or 0 without the flagaa_xattrs_match
aa_dfa_match_until(dfa, start, str, &pos) match.c:612-650at NUL or the first accepting statethe state and the positionaa_label_str_split
aa_dfa_matchn_until(dfa, start, str, n, &pos) match.c:669-708after n bytes or the first accepting statethe state and the positionaa_label_strn_split
aa_dfa_leftmatch(dfa, start, str, &count) match.c:816-824at NULthe state and a countfind_attach

All code. Every one returns 0 at once for a start state of 0 except aa_dfa_next and the out-of-band step. With an equivalence class table the byte is mapped first; the out-of-band input is not.

What the loop relies on

Check at loadWhere
default, base, next and check exist; base and default have the same length, next and check too; an equivalence class table has 256 entriesmatch.c:104-143
at least 2 states; default[i] < states; no invalid flag bits; base_idx(base[i]) + 255 < slots; next[i] and check[i] below statesmatch.c:154-199
a diff-encoded or out-of-band state needs the header flag; an out-of-band state needs base_idx >= 1match.c:172-187
diff-encode chains endmatch.c:201-231
the start states are below statespolicy_unpack.c:1034-1040
accept entries, plus one for an owner pair, are inside the permission tablepolicy_unpack.c:1492-1509
a row has no bit in both allow and deny, and so on; an exec index of type table is inside the string tablepolicy_unpack.c:1511-1560

Code. When these run and what else is checked is the subject of Unpacking and verifying policy.

The permission row

struct aa_perms perms.h:69-88 (code):

FieldWhen it is set (the source's comments, reworded)
allow
denyexplicit deny, or conflict if allow also set
subtreeallow perm on full subtree only when allow is set
condonly for bits neither allowed nor denied
killonly for bits that are not allowed, or denied
complainaccumulates; used only for bits neither allowed nor denied
promptaccumulates; used only for bits neither allowed nor denied
auditset only when allow is set
quietonly for bits that are not allowed, or denied
hideonly for bits that are not allowed, or denied
xindexthe exec index, see Exec and domain transitions
tag, labelstring table indexes, if present

File permission bits perms.h:16-47 (code): exec 0x1, write 0x2, read 0x4, append 0x8, create 0x10, delete 0x20, open 0x40, rename 0x80, setattr 0x100, getattr 0x200, chmod 0x1000, chown 0x2000, lock 0x8000, exec mmap 0x10000, link 0x40000, stack 0x10000000, onexec 0x20000000, change_profile 0x40000000, change_hat 0x80000000.

The example's table (tree): rows 0 to 3 0x200; rows 4 and 5 0x244; rows 6 and 7 0x10201 with AA_X_INHERIT. States: 21 accept 4, 20 accept 6, all others 0.

Classes and start states

ClassNumberA hook's first step after start[class]
file2a DFA of its own (rules->file); the name
capability3byte cap >> 5; request 1 << (cap & 0x1f)
mount7the mount point, then NUL-separated fields
ptrace9reached from start[16] (label) plus the byte 9; the peer label
signal10the signal number; the peer label
net, net v914, 15family, type, protocol; for unix the address and peer label
io_uring22the label of the credentials to take over, when there is one

apparmor.h:19-44, policy_unpack.c:1026-1047, capability.c:121-150, ipc.c:78-100, lib.c:393-405 (code). RULE_MEDIATES(rules, class) returns start[class]; 0 means not mediated by this profile policy.h:331-339.

The verdict

For a file request, __aa_path_perm and aa_audit_file file.c:95-154 file.c:233-251 (code):

CaseResultRecord
every requested bit in allow, none in audit0none
every requested bit in allow, some in audit (or the profile audits all)0AUDIT
a bit missing from allow, all missing bits in quiet-EACCESnone (unless the audit mode is noquiet or all)
a bit missing from allow, some not quiet-EACCESDENIED
the same in a complain-mode profile0ALLOWED
a missing bit in kill, or a kill-mode profile-EACCES and a signalKILLED in the log

For the other classes, aa_apply_modes_to_perms and aa_check_perms lib.c:364-391 lib.c:425-464 (code): denied = request & (~allow | deny); -ENOENT instead of -EACCES when every denied bit is in hide; aa_select_audit_type audit.c:143-152.

Observed for the example profile on /usr/bin/demo (a static program):

RunResultRecord
demo cat /etc/demo/motdprints the filenone
demo sh -c "echo x > /etc/demo/new"Permission deniedapparmor="DENIED" operation="mknod" class="file" profile="demo" name="/etc/demo/new" comm="demo" requested_mask="c" denied_mask="c" fsuid=0 ouid=0
demo cat /root/.ssh/id_testPermission deniedapparmor="DENIED" operation="open" class="file" profile="demo" name="/root/.ssh/id_test" comm="demo" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
the same with a plain deny rule (profile demoq)Permission deniednone
demo cat /etc/hostnamePermission deniedapparmor="DENIED" operation="open" ... name="/etc/hostname" ... requested_mask="r" denied_mask="r"
the same in complain mode (profile democ)prints the fileapparmor="ALLOWED" operation="open" class="file" profile="democ" name="/etc/hostname" comm="democ" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
demo executes a program with no rulePermission deniedapparmor="DENIED" operation="exec" class="file" profile="demo" name="/usr/local/bin/nothing" comm="demo" requested_mask="x" denied_mask="x" fsuid=0 ouid=0

Known discrepancies

  • An audit deny file rule in a complain-mode profile is allowed and logged ALLOWED (code; see Bugs found while building this map).
  • The kernel-doc comments of aa_dfa_next, the _until pair and aa_dfa_leftmatch describe aa_dfa_match (code; documentation only).

Not determined

  • The cost of diff-encode chains in loaded policy.
  • aa_dfa_leftmatch on a diff-encoded attachment table on a running kernel.

Roads from here

START HERE

ATTACHMENT, NAMESPACES, STACKING

QUALIFIERS

RUNNING THE PARSER

IN THE KERNEL

THE DFA ENGINE · libapparmor_re