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
- How the kernel checks an access — what a state and a walk and a final state are
- How the tables are packed — where the slots of next and check come from
Part of journeys
- How a rule becomes a permission, step 11 of 12 · previous: The binary policy format · next: How a denial is logged (no slides yet)
01 From a hook to a verdict
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,inprofile 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_openlsm.c:465-507 maps the open flags to a request (aa_map_file_to_perms, file.h:112-131) and callsaa_path_permfile.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_permfile.c:233-251:if (request & ~perms->allow) e = -EACCES;thenaa_audit_file(...).- The name is built by
aa_path_namepath.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
- How the kernel checks an access, How the tables are packed, Table compression.
- match.c and file.c in the kernel tree.
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
02 One step: base, check, next, default
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;insidedo { } while (1).base_idx(X)isX & 0xffffffmatch.c:23. Thecontinueis 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
u32in the kernel whatever the stream held:aa_dfa_unpackwidens 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 isDFA_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 belowstate_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
- How the tables are packed, scene "Whose slot is this?": the same lookup, to try with any byte.
- How the kernel checks an access, scene "Four arrays".
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
03 A miss that tries again
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 0x40000000andMARK_DIFF_ENCODE_VERIFIED 0x10000000are 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_INVALIDis 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_ENCODEin 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 andxto 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
- How the tables are packed, scene "Like that state, except": switch the encoding on and off.
- Table compression, scene "Diff encoding: "same as that state, except"".
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
04 Five walkers, one step
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_transitionisaa_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 callsleftmatch_fbmatch.c:741-801: each state entered is stored in a ring ofWB_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 withaa_dfa_matchand the count stops. A final state 0 sets the count to 0. Its only caller isfind_attachdomain.c:431-433; Profile attachment explains the count.aa_dfa_match_untilandaa_dfa_matchn_untilmatch.c:612-708 return at the first state with a non-zero accept entry and report the position.aa_label_strn_splituses them onstacksplitdfato find//&label.h:322-344; that table andnulldfaare 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_untilandleftmatch_fbhave the step written out without thecontinue: 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_nextand the out-of-band step usematch_charin both. Nothing in this deck was observed through the three that differ, andaa_dfa_leftmatchon 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
- Profile attachment, scene "find_attach: one loop, four registers".
- Labels in the kernel, scene "Text out, text in".
- match.c
05 A separator that is a zero, and one that is not a byte
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;thenmatch_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_oobfails ("AppArmor DFA out of bad transition out of range"), as does a flagged state when the header lacksYYTH_FLAG_OOB_TRANS.max_oobis fixed at 1; the code that would read a larger number from the header is commented out match.c:348-360.MAX_OOB_SUPPORTEDis 1 match.h:44. - The user:
aa_xattrs_matchdomain.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 withaa_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
- Building the DFA, Extended attribute conditions, Profile attachment.
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
06 From a state to a row
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 iscurrent_fsuid()file.c:227.ACCEPT_FLAG_OWNERis 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_permsperms.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 30x200(left by the deny rule), 4 and 50x244(therrule), 6 and 70x10201with the inherit bit inxindex(theixrule). 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_fpermsmakes two rows per state andremap_dfa_accept(dfa, 2)setsaccept[state] = state * 2and the owner flag; the policydb gets one row per state.map_old_permswidens 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 whystatis 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
- Permissions in the DFA, scenes "The permission table" and "The old encoding: three words per state".
- The owner qualifier.
- wiki: TechnicalDoc_HFA_permissions (draft; the deck follows the code).
07 Every other class starts with one byte
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_policydbpolicy.h:110-120: the DFA, the permission table and its size, the string tabletrans, tags, andaa_state_t start[AA_CLASS_LAST + 1]. A profile has three:rules->policy,rules->fileandattach.xmatchpolicy.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_mediateslabel.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)andaa_label_matchfor the peer (Labels in the kernel). Ptrace starts fromstart[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 outsideaa_dfa_nextand the loop that fillsstart[](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
- Capability rules, Signal rules, Ptrace rules, Mount rules.
- The backend pipeline, scene "One profile, three DFAs".
- wiki: TechnicalDoc_PolicyDB (draft; the deck follows the code).
08 Allow, audit, quiet: the result and the record
__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_filefile.c:95-154. No error:request &= perms->audit(or0xffffwhen the profile audits everything); nothing left, no record; otherwise anAUDITrecord. An error: only the bits not in allow are reported; a bit inkillmakes itKILL;request &= ~quietunless the profile's audit mode isnoquietorall; nothing left, the error is returned silently.aa_auditaudit.c:200-237: in complain mode the type becomesALLOWEDandcomplain_errorturns-EACCESinto 0 audit.h:206-211; in kill modeDENIEDbecomesKILLand 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
denysets the same bits in quiet,audit denydoes not (Permissions in the DFA, scene "What becomes of a deny rule"). In the example the rows left by theaudit denyrule 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 inaudit; a denial returns-EACCES, or-ENOENTif all denied bits are inhide; quiet bits are dropped;aa_select_audit_typeaudit.c:143-152 givesKILLfor a bit inkill,ALLOWEDif every denied bit is incomplain, elseDENIED.aa_apply_modes_to_permslib.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 plaindenyrun used the same three rules withdenyin place ofaudit deny(profiledemoq); the complain run the same rules without the deny rule andflags=(complain)(profiledemoc), and the file it read,/etc/hostname, has no rule. A plaindenyin a complain-mode profile stays refused and silent: the denied bits are quiet, soaa_audit_filereturns 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 denyfile rule in a complain-mode profile is allowed and logged ALLOWED (the denial is not quiet, so it reaches the complain-mode branch ofaa_audit). Read from the code here; not part of this run.
Read more
- Reading a denial: every field of these lines. How a denial is logged.
- allow and deny, The audit qualifier, Profile mode flags.
- wiki: TechnicalDoc_HFA_permissions (draft; the deck follows the code).
09 Where to go from here
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
- The deck in four lines:
match_charsteps through base, check, next and default;accept[state]indexes the permission table, with an owner and an other row for file rules;start[class]begins every other class; a file request needsrequest & ~allow == 0, and audit and quiet decide the record. - How the tables are packed, Table compression, Permissions in the DFA, Building the DFA, Exec and domain transitions, Labels in the kernel, Unpacking and verifying policy, Profile attachment, Reading a denial, How the kernel checks an access.
- Sources for this deck: Linux 97d73c825 for the code, AppArmor 836052d21 for the tables of the example; one run on a Debian guest for the last scene but one.
Read more
- match.c, file.c, lib.c, policy_compat.c.
- wiki: TechnicalDoc_HFA_Layout. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
- wiki: TechnicalDoc_HFA_permissions (draft; the deck follows the code).
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
| Name | Where | What |
|---|---|---|
match_char(state, def, base, next, check, C) | match.c:443-455 | pos = 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:23 | X & 0xffffff |
DFA_NOMATCH, DFA_START | match.h:17-18 | 0 and 1 |
aa_state_t | match.h:135 | unsigned int |
DEFAULT_TABLE, BASE_TABLE, NEXT_TABLE, CHECK_TABLE, ACCEPT_TABLE, ACCEPT_TABLE2 | match.h:93-99 | u32 * views of the tables; EQUIV_TABLE is u8 * |
All code.
Flags in a base entry
| Bit | Name | Meaning |
|---|---|---|
0x80000000 | MATCH_FLAG_DIFF_ENCODE | a miss continues in the default state with the same input |
0x40000000 | MARK_DIFF_ENCODE | set and cleared by verify_dfa while it follows a chain |
0x20000000 | MATCH_FLAG_OOB_TRANSITION | the state has an out-of-band transition at slot base - 1 |
0x10000000 | MARK_DIFF_ENCODE_VERIFIED | left set by verify_dfa on a checked diff-encoded state |
0x5f000000 | MATCH_FLAGS_INVALID | every bit of the top byte except the two flags, the two marks included: set in the stream, the load fails |
0x00ffffff | the 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
| Function | Input ends | Returns | Callers |
|---|---|---|---|
aa_dfa_match(dfa, start, str) match.c:518-550 | at NUL | the state | file names, profile names in a peer label, mount strings |
aa_dfa_match_len(dfa, start, str, len) match.c:473-504 | after len bytes | the state | xattr values, : in a peer label, a class byte above AA_CLASS_LAST |
aa_dfa_next(dfa, state, c) match.c:562-579 | one byte | the state | class start states, capability and signal bytes, the null transition |
aa_dfa_outofband_transition(dfa, state) match.c:581-597 | one input, -1 | the state, or 0 without the flag | aa_xattrs_match |
aa_dfa_match_until(dfa, start, str, &pos) match.c:612-650 | at NUL or the first accepting state | the state and the position | aa_label_str_split |
aa_dfa_matchn_until(dfa, start, str, n, &pos) match.c:669-708 | after n bytes or the first accepting state | the state and the position | aa_label_strn_split |
aa_dfa_leftmatch(dfa, start, str, &count) match.c:816-824 | at NUL | the state and a count | find_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 load | Where |
|---|---|
| default, base, next and check exist; base and default have the same length, next and check too; an equivalence class table has 256 entries | match.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 states | match.c:154-199 |
a diff-encoded or out-of-band state needs the header flag; an out-of-band state needs base_idx >= 1 | match.c:172-187 |
| diff-encode chains end | match.c:201-231 |
| the start states are below states | policy_unpack.c:1034-1040 |
| accept entries, plus one for an owner pair, are inside the permission table | policy_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 table | policy_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):
| Field | When it is set (the source's comments, reworded) |
|---|---|
allow | |
deny | explicit deny, or conflict if allow also set |
subtree | allow perm on full subtree only when allow is set |
cond | only for bits neither allowed nor denied |
kill | only for bits that are not allowed, or denied |
complain | accumulates; used only for bits neither allowed nor denied |
prompt | accumulates; used only for bits neither allowed nor denied |
audit | set only when allow is set |
quiet | only for bits that are not allowed, or denied |
hide | only for bits that are not allowed, or denied |
xindex | the exec index, see Exec and domain transitions |
tag, label | string 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
| Class | Number | A hook's first step after start[class] |
|---|---|---|
| file | 2 | a DFA of its own (rules->file); the name |
| capability | 3 | byte cap >> 5; request 1 << (cap & 0x1f) |
| mount | 7 | the mount point, then NUL-separated fields |
| ptrace | 9 | reached from start[16] (label) plus the byte 9; the peer label |
| signal | 10 | the signal number; the peer label |
| net, net v9 | 14, 15 | family, type, protocol; for unix the address and peer label |
| io_uring | 22 | the 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):
| Case | Result | Record |
|---|---|---|
| every requested bit in allow, none in audit | 0 | none |
| every requested bit in allow, some in audit (or the profile audits all) | 0 | AUDIT |
| a bit missing from allow, all missing bits in quiet | -EACCES | none (unless the audit mode is noquiet or all) |
| a bit missing from allow, some not quiet | -EACCES | DENIED |
| the same in a complain-mode profile | 0 | ALLOWED |
| a missing bit in kill, or a kill-mode profile | -EACCES and a signal | KILLED 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):
| Run | Result | Record |
|---|---|---|
demo cat /etc/demo/motd | prints the file | none |
demo sh -c "echo x > /etc/demo/new" | Permission denied | apparmor="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_test | Permission denied | 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 |
the same with a plain deny rule (profile demoq) | Permission denied | none |
demo cat /etc/hostname | Permission denied | apparmor="DENIED" operation="open" ... name="/etc/hostname" ... requested_mask="r" denied_mask="r" |
the same in complain mode (profile democ) | prints the file | apparmor="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 rule | Permission denied | apparmor="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 denyfile 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_untilpair andaa_dfa_leftmatchdescribeaa_dfa_match(code; documentation only).
Not determined
- The cost of diff-encode chains in loaded policy.
aa_dfa_leftmatchon a diff-encoded attachment table on a running kernel.
Roads from here
START HERE
- How the kernel checks an access — the same walk drawn as a machine
ATTACHMENT, NAMESPACES, STACKING
- Profile attachment — what the count of the left match is for
QUALIFIERS
- The owner qualifier — the owner and other halves in a profile
RUNNING THE PARSER
- Reading a denial — every field of the log line
IN THE KERNEL
- Exec and domain transitions — the exec rule lookup and what follows it
- Labels in the kernel — matching a peer label
- Unpacking and verifying policy (no slides yet) — the checks at load that the loop relies on
- How a denial is logged (no slides yet) — how the record is built
THE DFA ENGINE · libapparmor_re
- How the tables are packed — try the lookup on the real tables
- Table compression — the base word and the table set from the packer's side
- Permissions in the DFA — how deny and audit and priority become a row
- Building the DFA — the out of band input in the parser