Building the DFA
and state explosion for AppArmor developers for security researchers for application developers for administrators
Subset construction turns the expression tree into states. Each state is a set of tree positions with one default transition and a few exceptions. Literal rules cost almost nothing. A wildcard followed by a fixed-length tail doubles the state count with every extra character - 38 states for four and 65542 for fifteen.
On the map: the dfa engine
▶ Watch this deck — 9 scenes, ~7 min
Worth seeing first
- The expression tree — the joined tree whose positions become states
- How the kernel checks an access — a finished machine of states and edges, walked
Part of journeys
- From profile text to kernel tables, step 8 of 13 · previous: The expression tree · next: Permissions in the DFA
01 From three rules to thirty-eight states
The parser builds the states of the machine from the rules: 38 for the three-rule example. apparmor_parser -D dfa-stats prints the count.
The deck on how the kernel checks an access showed you a finished machine. This deck is about how the parser builds one. The parser first joins the rules into one tree. From that tree it makes a set of states and the transitions between them. For demo's three rules, that's thirty-eight states. The number is worth caring about, because compile time, memory and the size of the loaded profile all follow it. Most of this deck is for people who work on the parser's code. But if you write profiles, stay for one scene: it shows, with measured numbers, which kinds of rules are cheap, and which kind doubles the machine with every character you add.
Details and sources
Details
- The number comes from
apparmor_parser -Q -K -D dfa-stats demo3.sd, run with the parser built from the AppArmor tree; nothing was loaded into a kernel. The command prints oneCreated dfaline per state machine of the profile; the second line is the one for the file rules. The count is the same with the tree'sabi/5.0feature set and with one that has the kernel'spolicyentries. - The three rules are from this profile (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,
}
- Two states have fixed numbers: state 0 means "no match", state 1 is the start.
- Seen the machine walked? That is How the kernel checks an access.
02 A state is a set of positions for AppArmor developers for security researchers
DFA::DFA computes followpos for every leaf, makes state 0 from the empty set and state 1 from the root's firstpos (hfa.cc:489-497). A state is a set of tree positions.
Number every leaf of the tree: each character node, each set, each accept node. Those are positions. For each position the constructor works out followpos, the positions that can come next. A state, then, is simply a set of positions: all the places in all the rules where the match could be right now. The start state is the root's firstpos: the first slash of each of our three groups. Feed it a slash, take the union of what follows those three positions, and you get the next state: h and r from the deny group, u, and e. The empty set is state zero, the non- matching state.
Details and sources
for AppArmor developers for security researchers
Details
DFA(Node *root, optflags const &flags, bool filedfa)(hfa.h:441); the constructor is at hfa.cc:470-543.- Position data is cleared first, because accept nodes are shared between trees (hfa.cc:481-487). Then
root->compute_pos(firstpos, lastpos)computes nullable, firstpos, lastpos and followpos (hfa.cc:489-494); the rules are in the comment at expr-tree.h:305-334, after the Dragon Book, section 3.9.2. - State 0 is made from the empty set and state 1 from the root's firstpos (hfa.cc:489-497).
add_new_state(hfa.cc:329-371) splits the node set into accept and non-accept nodes, interns both inanodes_cacheandnnodes_cache, and maps the pair to a state throughnode_map(hfa.h:246-273, hfa.h:373-406).- The kernel's constants are
DFA_NOMATCH0 andDFA_START1 (match.h:17). - The position sets drawn on the slide are derived from the tree dump of the three rules; no dump prints them in a usable form.
longest=4in the-D dfa-statsline agrees with the four-position set. - Known discrepancy:
-D dfa-node-mapprints addresses, not node labels (hfa.cc:60-69, hfa.cc:438), so it cannot be related to the tree dump. - Kernel statements are read from the kernel source and were not run.
for AppArmor developers for security researchers
Read more
03 A work queue of states for AppArmor developers for security researchers
update_state_transitions calls follow() on each position of a state and creates a state for each new target set (hfa.cc:373-427, 441-465). -D dfa-states-initial prints the result.
The construction is a loop over a work queue. Take a state, and ask each position in it which characters it accepts and what follows. Every distinct set that comes out is looked up, and if it's new, it becomes a state and joins the queue. Here's the real dump for our rules. State one has one transition, slash, to state two. State two splits four ways, on e, h, r and u, because that's where the four paths part. From there each branch is a chain, one state per character. Rules that share a beginning share states, without any help from the simplifier. When the queue is empty there are thirty-eight states.
Details and sources
for AppArmor developers for security researchers
Details
- The work queue: hfa.cc:441-465 and hfa.cc:509-510.
update_state_transitions(hfa.cc:373-427) collects, per input character, the union of the followpos sets of the positions that accept it. followper node kind (expr-tree.h:571-581, expr-tree.h:620-632, expr-tree.h:689-709, expr-tree.h:763-773): aCharNodeorCharSetNodeadds its followpos to the entries of its characters, seeding a new entry from the currentotherwiseset; aNotCharSetNodeorAnyCharNodeadds tootherwiseand to every existing entry it matches.- The dump format (
DFA::dump, hfa.cc:1174-1241): first the start state and every accepting state, then per state the explicit transitions that do not lead to state 0. A state with nothing but transitions to state 0 is not listed. - The 38 states of the example: 0 and 1, the chains for the four paths, and three accepting states. The slide shows the first seven lines of the dump; it was made with the parser of the AppArmor tree and is the same with the tree's
abi/5.0feature set and with one that has the kernel'spolicyentries. The complete dump is in the reference under the deck. - An exception from the permission computation is passed up after
cleanup()(hfa.cc:339-348). - A comment notes that breadth-first construction costs peak memory (hfa.cc:504-508).
-D dfa-progressprints a status line (hfa.cc:446-454);-D dfa-graphwrites Graphviz (hfa.cc:1246-1294).
for AppArmor developers for security researchers
Read more
- wiki: TechnicalDoc_HFA.
- Minimisation: what happens to these 38.
04 One default and a few exceptions for AppArmor developers for security researchers
State has trans (explicit transitions) and otherwise (hfa.h:362-363). [^\x0/] -> {35} in a dump is otherwise = {35} plus explicit transitions on NUL and / to state 0.
A state doesn't hold two hundred and fifty-six transitions. It holds a map of explicit ones and a single default, called otherwise. Look at state thirty-two, where the path so far is the demo directory and its slash. The next character can be anything but a slash or a NUL. So the default points at state thirty-five, the accepting loop, and there are just two explicit transitions, NUL and slash, both to state zero. The dump folds that into one line: not NUL, not slash, goes to thirty-five. And an explicit transition that happens to equal the default is simply not stored. The packed tables keep exactly this shape, as the default table.
Details and sources
for AppArmor developers for security researchers
Details
StateTransisstd::map<transchar, State *>(hfa.h:43); aStatehastransandotherwise(hfa.h:362-363), andState::nextlooks intransfirst (hfa.h:319-334).- In
update_state_transitions,cases.otherwisebecomes the state'sotherwise, and each entry ofcasesbecomes an explicit transition unless its target equalsotherwise(hfa.cc:394-399, hfa.cc:418-425). - The dump lists only the exclusions that go to state 0 (hfa.cc:1216-1238). That is why state {20} prints
[^\x0]: its/transition leads to {21} and is listed on its own line. - The default table of the packed form is this field (chfa.cc:241-250, chfa.cc:316); see Table compression.
- The representation is not canonical.
[\x01-.0-\xff](254 explicit transitions, default state 0) and[^/\x00](default the target, two explicit transitions) behave the same and are stored differently. A comment in the minimizer states that it "will fail to fully minimize" in that case; see Minimisation. - Dump quirk: the permission tuple prints as
(0x 10004/0//0/0/0), with a blank after0xand a doubled slash; the fields are allow/deny/prompt/audit/quiet. Known discrepancy, by title: "Debug dumps with malformed output". - The two dump fragments on the slide are from the three-rule example, made with the parser of the AppArmor tree.
for AppArmor developers for security researchers
Read more
05 Where a rule ends, a state accepts for AppArmor developers for security researchers
Accepting states of the example: {34} allow 0x904241, {35} allow 0x10004, {37} deny 0x3800e. -D dfa-uniq-perms lists the distinct sets; a State computes its permissions in its constructor (hfa.h:305-309).
A state's set can contain accept nodes, the little squares at the end of each group. When it does, the state is accepting, and its constructor computes its permissions from those nodes right away. In our machine three states accept. Thirty-five, the loop at the end of the demo directory, with the r permission. Thirty-four, after a lower-case letter in the bin directory, with exec, inherit, and the mmap bit that inherit implies. And thirty-seven, where both SSH paths end up, with nothing allowed and three permissions in its deny mask. Counting the empty one, that makes four distinct permission sets. Notice how much of the machine belongs to the deny rule: sixteen of thirty-eight states.
Details and sources
for AppArmor developers for security researchers
Details
- The head of the
-D dfa-states-initialdump lists the start state and the accepting states:
{1} <== (allow/deny/prompt/audit/quiet)
{34}(0x 904241/0//0/0/0)
{35}(0x 10004/0//0/0/0)
{37}(0x 0/3800e//0/0/0)
-D dfa-uniq-perms(hfa.cc:571-580) prints, for the file DFA:
Unique Permission sets: dfa (4) ---------------------- allow:0 deny:0 audit:0 quiet:0 prompt:0 allow:0 deny:3800e audit:0 quiet:0 prompt:0 allow:10004 deny:0 audit:0 quiet:0 prompt:0 allow:904241 deny:0 audit:0 quiet:0 prompt:0
- Both dumps were made with the parser of the AppArmor tree and a feature set that has the kernel's
policyentries; the slide shortens the four lines to one. - A state is accepting when any of its five masks is non-zero (hfa.h:56).
0x904241is0x804201(exec and inherit, for owner and for other) plus the implied mmap bit 0x40 in both halves.- A
Statecomputes its permissions in its constructor (hfa.h:305-309), andadd_new_statebuilds the state for every transition target before it checks for a duplicate (hfa.cc:340, hfa.cc:349-351). On the profile/etc/demo/** rw, deny /etc/demo/*.conf w, priority=10 allow /etc/demo/override.conf w,the-D dfa-perms-builddump has 97 "Building Perms" blocks, 76 of them for the same accept node (run with theabi/5.0feature set). - The 16 deny-only states: {4} {5} {8} {9} {12} {13} {16} {17} {20} {21} {24} {27} {30} {33} {36} {37}.
for AppArmor developers for security researchers
Read more
06 One input that is not a byte for AppArmor developers for security researchers
Out of band character -1: created only for xattr attachment conditions, never matched by a negated set or ., taken in the kernel by aa_dfa_outofband_transition (linux:security/apparmor/match.c:581-597).
Everything so far ran on bytes. There is one extra input. A profile with extended attribute conditions has to match the path and then the attribute values, and a value can hold any byte, NUL included, so no byte can serve as the separator. The answer is a character outside the byte range, number minus one. In the dump for this profile, state eleven accepts the path, and has one more transition, on minus one, into the states for the values. No wildcard matches it: negated sets and the dot skip it explicitly. Only the kernel can take that edge, with a dedicated function, between the path and the first value.
Details and sources
for AppArmor developers for security researchers
Details
- The profile on this slide is
profile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*), not the three-rule example. From its-D dfa-statesdump, attachment machine (parser of the AppArmor tree,abi/5.0feature set):
{10} perms: none
x 0x78 -> {11} (0x 1/0//0/0/0)
{11} perms: (0x 1/0//0/0/0)
-0x1 -> {12}
[^\x0/] -> {11} (0x 1/0//0/0/0)
{12} perms: none
0x0 -> {13}
- A
transcharwith a negative value is out of band; only -1 is used (expr-tree.h:89-91). The header comment gives the reason: a NUL separator cannot separate data that may contain NUL (expr-tree.h:61-87). - It is created only by
cat_with_oob_separatorand for the tail separator (aare_rules.cc:69-72, aare_rules.cc:215-216); the only user is the xattr part of xmatch (parser_regex.c:597-601, parser_regex.c:615-619). oob_rangerecords the largest out of band number seen (hfa.cc:423-424);max_rangebecomes 257 andord_range9 (hfa.cc:473-476, hfa.cc:511-514).ord_rangeis used only as a shift in thecompress-smallsort key (chfa.cc:105).- Negated classes and
.never match it (expr-tree.h:704-707, expr-tree.h:770-772). - In the kernel,
aa_dfa_outofband_transitionreturnsDFA_NOMATCHunless the state's base entry hasMATCH_FLAG_OOB_TRANSITION, then looks up offset -1 (match.c:581); it is called fromaa_xattrs_match(domain.c:330, domain.c:356). - The parser warns
xattr attachment conditional ignoredand drops the condition withoutpolicy/outofbandor the xattr attachment feature (parser_regex.c:472-476, parser_regex.c:549-553). - Kernel statements are read from the kernel source and were not run.
- Known discrepancy: with
-O equivthe out of band transitions are dropped (hfa.cc:1395-1402); the option is off by default. - Known discrepancy: diff encoding against a state that has an out of band transition changes its transition on byte 0xff (hfa.cc:239-262).
- Known discrepancy:
-D compressed-dfaprints an out of band entry as\xff.
for AppArmor developers for security researchers
Read more
07 Which rules make a profile big
States created: 100 literal rules 14; /srv/**x plus 2, 4, 6, 8, 10, 14, 15 ?: 14, 38, 134, 518, 2054, 32774, 65542. Above 65534 states the parser exits with Too many states (N) for type state_t.
You can measure this yourself: the dfa-stats dump prints how many states each machine has. And the results aren't what counting rules would suggest. One literal path: eight states. A hundred literal paths that differ in three digits: fourteen. A plain double star is free as well. The expensive shape is a wildcard followed by a tail of fixed length: a double star, an x, and then question marks. With two question marks, fourteen states. Four, thirty-eight. Six, a hundred and thirty-four. Every extra question mark doubles it, and fifteen of them reach sixty-five thousand states, where the parser stops with "too many states". And in a real profile, most states come from its abstractions.
Details and sources
Details
apparmor_parser -Q -K -D dfa-stats FILEprints threeCreated dfa: states Nlines per profile, in the order attachment, file rules, other rule classes. The numbers here are for the file rules of profiles without an attachment, one profile per row, measured with the parser built from the AppArmor tree (the tree'sabi/5.0feature set, nothing loaded into a kernel).
| Rules | States created | After merging |
|---|---|---|
/srv/a r, | 8 | 8 |
10 rules /srv/file0 to /srv/file9 | 12 | 12 |
100 rules /srv/file100 to /srv/file199 | 14 | 14 |
/srv/** r, | 8 | 8 |
/srv/**/data r, | 13 | 13 |
5 rules /srv/**/{data,cache,state,logs,tmp} r,, written separately | 25 | 25 |
the same 5 with w, plus /srv/**/*.conf r, | 31 | 31 |
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r, | 23 | 16 |
the same four paths with r, w, rw, k | 30 | 29 |
/**/a/**/b/**/c r, | 20 | 14 |
/srv/{a,b,c}/{d,e,f}/{g,h,i} r, | 12 | 12 |
/srv/**x?? r, | 14 | 14 |
/srv/**x???? r, | 38 | 38 |
/srv/**x?????? r, | 134 | 134 |
/srv/**x???????? r, | 518 | 518 |
/srv/**x?????????? r, | 2054 | 2054 |
/srv/**x and 14 ? | 32774 | 32774 |
/srv/**x and 15 ? | 65542 | 65542, then the error |
- The
x???family grows as about 2^(k+1) for k question marks, and merging removes none of it. - A profile that includes the
base,nameserviceanduser-tmpabstractions and has one rule of its own: 2387 states created, 1695 after merging. - The profile with 15 question marks took a couple of seconds before the error (about 1.5 s without the start-up of the run). The message is
Too many states (65542) for type state_t, the exit status is 1, and the message names no profile. -O state32lifts the limit to 16777214 states when the kernel's features listpolicy/state32.- What to do instead (derived from the numbers, not from a tool): anchor the tail with a literal separator such as
/, or drop the fixed-length tail.
Read more
- apparmor_parser(8) D n dump n.
- Globbing (AARE), Choosing abstractions.
- The backend pipeline: compile time and the cache. The policy cache.
for AppArmor developers for security researchers
In the code
- The limit is tested when the tables are written: chfa.cc:435-439, and the 32-bit variant at chfa.cc:514-535.
08 Why the tail doubles the states for AppArmor developers for security researchers
A position that stays live (**) combined with a fixed-length tail makes every combination of tail positions a distinct state: about 2^(k+1). In -D dfa-stats, size is distinct node sets, dups is repeated lookups and longest is the largest set.
Think in sets of positions. Once the double star has started, its position is in every later state, because the star can always swallow one more byte. And every x in the input might be the x of the pattern, so after an x the first question mark joins the set, one byte later the second, and so on. The state therefore records, for each of the last few bytes, whether it was an x. With k question marks that's two to the k plus one sets, and each set is a state. The stats line counts them as size. Minimization won't rescue you here, because these states really do behave differently.
Details and sources
for AppArmor developers for security researchers
Details
- The
-D dfa-statsline (hfa.cc:525-535, counters at hfa.cc:44-58):Created dfa: states N proto { cache: size= dups= longest= avg= }, nnodes { ... }, anodes { ... }.protocounts the pairs of sets that identify a state,nnodesthe sets of non-accept nodes andanodesthe sets of accept nodes.sizeis the number of distinct entries,dupsthe number of insertions that found an existing entry,longestandavgthe size of the sets. Manydupswith a smallsizemeans the rules share structure. - The line on the slide is the file DFA of the rule in the kicker,
/srv/**x?? r,alone in a profile:Created dfa: states 14 proto { cache: size=14 dups=24 longest=5 avg=2 }, nnodes { ... }, anodes { ... }.longest=5is the set {*, x, ?1, ?2, accept}, reached after threexin a row. The 38-state member of the family,/srv/**x????, printssize=38 dups=96 longest=7 avg=3. - Minimization does not help the family:
/srv/**x??????has 134 states before and after.
The stats lines of the three-rule example
- The same with both feature sets, in the order attachment, file rules, other rule classes:
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 }
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 }
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 }
- For 15 question marks the parser prints
Created dfa: states 65542 ...and thenDfa minimization no states removed: partitions 65542 init 3 (accept 1)(abi/5.0feature set). - Literal paths: the cost is about the number of distinct characters along the paths, whatever the tree looks like. One fixed suffix after
**adds a few states. Different permissions on overlapping globs keep states apart: 30 against 23 created, 29 against 16 kept. - The sets on the slide are derived from the pattern, not dumped: a state is the set of positions that may match the next byte, the positions of
**and ofxare in every state once the star has started, and?1,?2and the accept node join when anxwas seen one, two or three bytes back. - Not determined: memory per state and peak memory.
for AppArmor developers for security researchers
Read more
- wiki: TechnicalDoc_HFA.
- Minimisation; The backend pipeline, scene "Where the time goes".
09 Where to go from here
Next: permissions in the DFA, minimisation, table compression. For profile authors: globbing, choosing abstractions. The walk: how the kernel checks an access.
One number decides what a profile costs to compile: its states. You've seen where that number is printed, and the one rule shape to keep an eye on. From here, the permissions deck takes the accepting states apart. Minimization merges states that behave alike. Table compression packs what's left. If you write profiles, the globbing deck and the abstractions deck are your roads. And the deck on how the kernel checks an access shows a machine like this one being walked.
Details and sources
Details
- Three things to take away: a state is a set of positions in the rules; each state stores one default transition and its exceptions; the number of states, not the number of rules, is what a profile costs.
- Permissions in the DFA: how an accepting state gets its permissions. Minimisation: merging the states this stage creates. Table compression: how the default transition is stored.
- Globbing (AARE): the wildcards whose shapes matter here. Choosing abstractions: where most states of a real profile come from. Extended attribute conditions.
- The expression tree, The backend pipeline, How the kernel checks an access, Matching at run time.
- Sources for this deck: AppArmor 836052d21 and Linux 97d73c825.
Read more
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 options shown), with nothing loaded into a kernel. The measured state counts were made with the tree's abi/5.0 file as the kernel feature set; the dumps of the three-rule profile are the same with that file and with a feature set that has the kernel's policy entries. "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.
Measured state counts
apparmor_parser -Q -K -D dfa-stats FILE prints Created dfa: states N for each state machine of a profile: attachment, file rules, other rule classes. One profile per row, no attachment, the file-rule machine (tree).
| Rules | States created | After merging |
|---|---|---|
/srv/a r, | 8 | 8 |
10 rules /srv/file0 to /srv/file9 | 12 | 12 |
100 rules /srv/file100 to /srv/file199 | 14 | 14 |
/srv/** r, | 8 | 8 |
/srv/**/data r, | 13 | 13 |
5 rules /srv/**/{data,cache,state,logs,tmp} r,, written separately | 25 | 25 |
the same 5 with w, plus /srv/**/*.conf r, | 31 | 31 |
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r, | 23 | 16 |
the same four paths with r, w, rw, k | 30 | 29 |
/**/a/**/b/**/c r, | 20 | 14 |
/srv/{a,b,c}/{d,e,f}/{g,h,i} r, | 12 | 12 |
/srv/**x?? r, | 14 | 14 |
/srv/**x???? r, | 38 | 38 |
/srv/**x?????? r, | 134 | 134 |
/srv/**x???????? r, | 518 | 518 |
/srv/**x?????????? r, | 2054 | 2054 |
/srv/**x and 14 ? | 32774 | 32774 |
/srv/**x and 15 ? | 65542 | 65542, then the error |
base, nameservice, user-tmp abstractions and one rule | 2387 | 1695 |
- Above 65534 states the parser prints
Too many states (N) for type state_tand exits with status 1 (tree). The message names no profile. -O state32lifts the limit when the kernel's features listpolicy/state32(code).
for AppArmor developers for security researchers
Subset construction
| Step | Where |
|---|---|
| clear position data of shared accept nodes | hfa.cc:481-487 |
compute_pos: nullable, firstpos, lastpos, followpos | hfa.cc:489-494, rules at expr-tree.h:305-334 |
| state 0 from the empty set, state 1 from the root's firstpos | hfa.cc:489-497 |
work queue: update_state_transitions per state | hfa.cc:441-465, hfa.cc:373-427 |
add_new_state: intern the node sets, find or create the state | hfa.cc:329-371 |
| statistics | hfa.cc:522-535 |
follow per node kind (code): a CharNode or CharSetNode adds its followpos to the entries of its characters; a NotCharSetNode or AnyCharNode adds to otherwise and to every existing entry it matches.
for AppArmor developers for security researchers
State
| Field | Meaning |
|---|---|
label | the number printed as {n} in dumps |
trans | explicit transitions, a map from input character to state |
otherwise | the default target for every character not in trans |
perms | allow, deny, prompt, audit, quiet masks; computed in the constructor |
State::next(c)looks intransand falls back tootherwise(hfa.h:319-334) (code).- State 0 is the non-matching state and state 1 the start; the kernel's
DFA_NOMATCHandDFA_START(match.h:17) (code). - A state is accepting when any of its five masks is non-zero (hfa.h:56) (code).
for AppArmor developers for security researchers
Out of band transitions
- Representation: a
transcharwith a negative value; only -1 is used (expr-tree.h:89-91) (code). - Created only for the xattr tail of the attachment machine (aare_rules.cc:69-72, aare_rules.cc:215-216) (code).
- Input range:
max_range257 when one is present (hfa.cc:511-514) (code). - Kernel:
aa_dfa_outofband_transition(match.c:581), which needsMATCH_FLAG_OOB_TRANSITIONon the state's base entry (code). - Warning:
xattr attachment conditional ignoredwhen the kernel lackspolicy/outofbandor the xattr attachment feature (code).
for AppArmor developers for security researchers
The -D dfa-stats line
Created dfa: states N proto { cache: size= dups= longest= avg= }, nnodes { ... }, anodes { ... }
| Field | Meaning |
|---|---|
states | states created, including state 0 |
proto | pairs (non-accept set, accept set) that identify a state |
nnodes | sets of non-accept nodes |
anodes | sets of accept nodes |
size | distinct entries |
dups | insertions that found an existing entry |
longest, avg | size of the sets |
for AppArmor developers for security researchers
Dumps
-D dfa-states-initial: the start state and each accepting state with its permission tuple(allow/deny/prompt/audit/quiet), then each state with its transitions that do not lead to state 0.-D dfa-uniq-perms: the distinct permission sets.-D dfa-node-map: the state for each pair of node sets (addresses).-D dfa-graph: Graphviz.-D dfa-progress: a status line while states are built.
The complete -D dfa-states-initial dump of the file DFA of the three-rule example (tree):
{1} <== (allow/deny/prompt/audit/quiet)
{34}(0x 904241/0//0/0/0)
{35}(0x 10004/0//0/0/0)
{37}(0x 0/3800e//0/0/0)
{1} perms: none
/ 0x2f -> {2}
{2} perms: none
e 0x65 -> {3}
h 0x68 -> {4}
r 0x72 -> {5}
u 0x75 -> {6}
{3} perms: none
t 0x74 -> {7}
{4} perms: none
o 0x6f -> {8}
{5} perms: none
o 0x6f -> {9}
{6} perms: none
s 0x73 -> {10}
{7} perms: none
c 0x63 -> {11}
{8} perms: none
m 0x6d -> {12}
{9} perms: none
o 0x6f -> {13}
{10} perms: none
r 0x72 -> {14}
{11} perms: none
/ 0x2f -> {15}
{12} perms: none
e 0x65 -> {16}
{13} perms: none
t 0x74 -> {17}
{14} perms: none
/ 0x2f -> {18}
{15} perms: none
d 0x64 -> {19}
{16} perms: none
/ 0x2f -> {20}
{17} perms: none
/ 0x2f -> {21}
{18} perms: none
b 0x62 -> {22}
{19} perms: none
e 0x65 -> {23}
{20} perms: none
/ 0x2f -> {21}
[^\x0] -> {20}
{21} perms: none
\. 0x2e -> {24}
{22} perms: none
i 0x69 -> {25}
{23} perms: none
m 0x6d -> {26}
{24} perms: none
s 0x73 -> {27}
{25} perms: none
n 0x6e -> {28}
{26} perms: none
o 0x6f -> {29}
{27} perms: none
s 0x73 -> {30}
{28} perms: none
/ 0x2f -> {31}
{29} perms: none
/ 0x2f -> {32}
{30} perms: none
h 0x68 -> {33}
{31} perms: none
a 0x61 -> {34} (0x 904241/0//0/0/0)
b 0x62 -> {34} (0x 904241/0//0/0/0)
c 0x63 -> {34} (0x 904241/0//0/0/0)
d 0x64 -> {34} (0x 904241/0//0/0/0)
e 0x65 -> {34} (0x 904241/0//0/0/0)
f 0x66 -> {34} (0x 904241/0//0/0/0)
g 0x67 -> {34} (0x 904241/0//0/0/0)
h 0x68 -> {34} (0x 904241/0//0/0/0)
i 0x69 -> {34} (0x 904241/0//0/0/0)
j 0x6a -> {34} (0x 904241/0//0/0/0)
k 0x6b -> {34} (0x 904241/0//0/0/0)
l 0x6c -> {34} (0x 904241/0//0/0/0)
m 0x6d -> {34} (0x 904241/0//0/0/0)
n 0x6e -> {34} (0x 904241/0//0/0/0)
o 0x6f -> {34} (0x 904241/0//0/0/0)
p 0x70 -> {34} (0x 904241/0//0/0/0)
q 0x71 -> {34} (0x 904241/0//0/0/0)
r 0x72 -> {34} (0x 904241/0//0/0/0)
s 0x73 -> {34} (0x 904241/0//0/0/0)
t 0x74 -> {34} (0x 904241/0//0/0/0)
u 0x75 -> {34} (0x 904241/0//0/0/0)
v 0x76 -> {34} (0x 904241/0//0/0/0)
w 0x77 -> {34} (0x 904241/0//0/0/0)
x 0x78 -> {34} (0x 904241/0//0/0/0)
y 0x79 -> {34} (0x 904241/0//0/0/0)
z 0x7a -> {34} (0x 904241/0//0/0/0)
{32} perms: none
[^\x0/] -> {35} (0x 10004/0//0/0/0)
{33} perms: none
/ 0x2f -> {36}
{34} perms: (0x 904241/0//0/0/0)
[^\x0/] -> {34} (0x 904241/0//0/0/0)
{35} perms: (0x 10004/0//0/0/0)
[^\x0] -> {35} (0x 10004/0//0/0/0)
{36} perms: none
[^\x0/] -> {37} (0x 0/3800e//0/0/0)
{37} perms: (0x 0/3800e//0/0/0)
[^\x0] -> {37} (0x 0/3800e//0/0/0)for AppArmor developers for security researchers
Known discrepancies
-D dfa-node-mapprints addresses, not node labels (hfa.cc:60-69, hfa.cc:438) (tree).- The permission tuple prints as
(0x 904241/0//0/0/0); by title: "Debug dumps with malformed output" (tree). - With
-O equivout of band transitions are dropped (hfa.cc:1395-1402) (tree; the option is off by default). - Diff encoding against a state that has an out of band transition changes its transition on byte 0xff (hfa.cc:239-262) (code).
perms_t::operator<comparesaudittwice (hfa.h:151-154); no effect on the ordering (code).
for AppArmor developers for security researchers
Not determined
- Memory per state and peak memory for the large cases.
Roads from here
START HERE
- How the kernel checks an access — the finished machine walked by the kernel
FILE ACCESS
- Globbing (AARE) — the wildcards whose shapes matter here
PROFILE HEAD
- Extended attribute conditions — the attachment condition that needs the extra input
IN PRACTICE · general-purpose apps
- Choosing abstractions — where most states of a real profile come from
IN THE KERNEL
- Matching at run time — the kernel code for byte and out of band transitions
THE DFA ENGINE · libapparmor_re
- The expression tree — the tree whose positions become states
- Permissions in the DFA — how an accepting state gets its permissions
- Minimisation — merging the states this stage creates
- Table compression — how a default transition is stored
- The backend pipeline — the stage list and what a compile costs