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

Part of journeys

01 From three rules to thirty-eight states

BUILDING THE DFA /etc/demo/** r,audit deny @{HOME}/.ssh/** rw,/usr/bin/[a-z]* ix, one tree 0 1 38 states Created dfa: states 38 ... apparmor_parser -D dfa-stats one scene here is for people who write profiles: which rule shapes make this number explode
Three rules become one tree and the tree becomes 38 states; apparmor_parser -D dfa-stats prints the number

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 one Created dfa line per state machine of the profile; the second line is the one for the file rules. The count is the same with the tree's abi/5.0 feature set and with one that has the kernel's policy entries.
  • 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,
}

02 A state is a set of positions for AppArmor developers for security researchers

POSITIONS deny group / home/[^/]* root /.ssh/... exec group /usr/bin/[a-z]... read group /etc/demo/... / / / {1} start: firstpos three positions h r u e followpos of the three slashes {2} after one slash: four positions {0} the empty set: no match nonmatching = add_new_state(empty) start = add_new_state(firstpos) the kernel uses the same numbers: 0 for no match, 1 for start
The leaves of the three groups drawn as chains of positions; the start state is the set of the three first slashes; after one slash the state is the set of the four positions h, r, u and e; the empty set is state 0

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 in anodes_cache and nnodes_cache, and maps the pair to a state through node_map (hfa.h:246-273, hfa.h:373-406).
  • The kernel's constants are DFA_NOMATCH 0 and DFA_START 1 (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=4 in the -D dfa-stats line agrees with the four-position set.
  • Known discrepancy: -D dfa-node-map prints 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

-D dfa-states-initial 1 2 3 4 5 6 ... the work queue update_state_transitions(state) {1} perms: none/ 0x2f -> {2}{2} perms: nonee 0x65 -> {3}h 0x68 -> {4}r 0x72 -> {5}u 0x75 -> {6} 1 / 2 e3 h4 r5 u6 /etc/demo/ /home/*/.ssh/ /root/.ssh/ /usr/bin/ Created dfa: states 38 first in, first out, until the queue is empty
The first lines of the -D dfa-states-initial dump next to the graph they describe: state 1 goes to state 2 on a slash, state 2 splits on e, h, r and u into four chains; states wait in a queue until all 38 are built

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.
  • follow per node kind (expr-tree.h:571-581, expr-tree.h:620-632, expr-tree.h:689-709, expr-tree.h:763-773): a CharNode or CharSetNode adds its followpos to the entries of its characters, seeding a new entry from the current otherwise set; a NotCharSetNode or AnyCharNode adds to otherwise and 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.0 feature set and with one that has the kernel's policy entries. 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-progress prints a status line (hfa.cc:446-454); -D dfa-graph writes Graphviz (hfa.cc:1246-1294).

for AppArmor developers for security researchers

Read more

04 One default and a few exceptions for AppArmor developers for security researchers

otherwise 32 /etc/demo/ 35 0 otherwise 254 byte values \x00 / explicit transitions {32} perms: none[^\x0/] -> {35} (0x 10004/0//0/0/0) the dump prints the default, with its exceptions to state 0, as a negated set {20} perms: none/ 0x2f -> {21}[^\x0] -> {20} /home/ and a star: the slash leaves the loop, so it is not listed as excluded State::next(c): trans.find(c), else otherwise
State 32 has one default transition, otherwise, to the accepting state 35 for 254 byte values, and two explicit transitions on NUL and slash to state 0; the dump prints this as one negated set

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

  • StateTrans is std::map<transchar, State *> (hfa.h:43); a State has trans and otherwise (hfa.h:362-363), and State::next looks in trans first (hfa.h:319-334).
  • In update_state_transitions, cases.otherwise becomes the state's otherwise, and each entry of cases becomes an explicit transition unless its target equals otherwise (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 after 0x and 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

ACCEPT 1 2 /etc/demo/ /usr/bin/ /home/*/.ssh/ /root/.ssh/ 35 [^\x0] {35}(0x 10004/0//0/0/0) read 34 [^\x0/] {34}(0x 904241/0//0/0/0) exec, inherit, mmap 37 [^\x0] {37}(0x 0/3800e//0/0/0) nothing allowed; write, read, append denied Unique Permission sets: dfa (4)allow:0 ... allow:0 deny:3800e ... allow:10004 ... allow:904241 ... 16 of the 38 states exist only for the deny rule
The machine of the three rules as four chains from states 1 and 2 that end in three accepting states: 35 with read, 34 with exec, inherit and mmap, and 37 with write, read and append denied; four distinct permission sets; 16 of the 38 states exist only for the deny rule

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-initial dump 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)
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 policy entries; the slide shortens the four lines to one.
  • A state is accepting when any of its five masks is non-zero (hfa.h:56).
  • 0x904241 is 0x804201 (exec and inherit, for owner and for other) plus the implied mmap bit 0x40 in both halves.
  • A State computes its permissions in its constructor (hfa.h:305-309), and add_new_state builds 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-build dump has 97 "Building Perms" blocks, 76 of them for the same accept node (run with the abi/5.0 feature 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 profile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*) { ... } a different profile 0x00 0xff 256 byte values -1 out of band 10 x 11 [^\x0/] -0x1 12 0x0 13 on to the xattr values {11} perms: (0x 1/0//0/0/0)-0x1 -> {12}[^\x0/] -> {11} (0x 1/0//0/0/0) negated sets and . do not match it the kernel takes it with aa_dfa_outofband_transition max_range = 257: the packed table flags a state that has such a transition
The input alphabet is the 256 byte values plus one out of band character, -1; in the attachment machine of a profile with xattrs conditions, the accepting state 11 has a transition on -1 into the states that match the attribute values

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-states dump, attachment machine (parser of the AppArmor tree, abi/5.0 feature 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}

for AppArmor developers for security researchers

Read more

07 Which rules make a profile big

MEASURED $ apparmor_parser -Q -K -D dfa-stats profile -> Created dfa: states N /srv/a r,8 100 rules /srv/file100 ... /srv/file19914 /srv/** r,8 /srv/{a,b,c}/{d,e,f}/{g,h,i} r,12 /srv/**x followed by question marks x??14 x????38 x??????134 x????????518 x + 10 ?2054 x + 14 ?32774 x + 15 ?65542 Too many states (65542) for type state_t base + nameservice + user-tmp: 2387 states most of a real profile comes from its abstractions four overlapping globs under /srv/**: 23 states with one permission, 30 with four (16 and 29 after merging)
Measured state counts: literal paths and a plain double star cost 8 to 14 states; a double star followed by x and a fixed number of question marks doubles with every question mark, from 14 states for two to 65542 for fifteen, where the parser fails with Too many states

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 FILE prints three Created dfa: states N lines 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's abi/5.0 feature set, nothing loaded into a kernel).
RulesStates createdAfter merging
/srv/a r,88
10 rules /srv/file0 to /srv/file91212
100 rules /srv/file100 to /srv/file1991414
/srv/** r,88
/srv/**/data r,1313
5 rules /srv/**/{data,cache,state,logs,tmp} r,, written separately2525
the same 5 with w, plus /srv/**/*.conf r,3131
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r,2316
the same four paths with r, w, rw, k3029
/**/a/**/b/**/c r,2014
/srv/{a,b,c}/{d,e,f}/{g,h,i} r,1212
/srv/**x?? r,1414
/srv/**x???? r,3838
/srv/**x?????? r,134134
/srv/**x???????? r,518518
/srv/**x?????????? r,20542054
/srv/**x and 14 ?3277432774
/srv/**x and 15 ?6554265542, 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, nameservice and user-tmp abstractions 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 state32 lifts the limit to 16777214 states when the kernel's features list policy/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.

for AppArmor developers for security researchers

In the code

08 Why the tail doubles the states for AppArmor developers for security researchers

/srv/**x?? /srv/[^/][^\x0]*x?? accept [^\x0]* always live the last bytes of the input positions that may match next ...aax{*, x, ?1}an x just now ...axb{*, x, ?2}an x one byte ago ...xxb{*, x, ?2, accept}two of them every pattern of x in the last three bytes is a different set 2^(k+1) k = 2: 14 4: 38 6: 134 8: 518 10: 2054 14: 32774 15: 65542 Created dfa: states 14 proto { cache: size=14 dups=24 longest=5 avg=2 }, nnodes { ... }, anodes { ... } distinct sets lookups that found one largest set {*, x, ?1, ?2, accept} minimization cannot help: the states really differ (134 before and after for six question marks)
The positions of /srv/**x??: the star position is live in every later state, so the set of live positions records which of the last three bytes were an x; each pattern gives a different set and so a different state, about 2 to the power k plus 1 for k question marks

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-stats line (hfa.cc:525-535, counters at hfa.cc:44-58): Created dfa: states N proto { cache: size= dups= longest= avg= }, nnodes { ... }, anodes { ... }. proto counts the pairs of sets that identify a state, nnodes the sets of non-accept nodes and anodes the sets of accept nodes. size is the number of distinct entries, dups the number of insertions that found an existing entry, longest and avg the size of the sets. Many dups with a small size means 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=5 is the set {*, x, ?1, ?2, accept}, reached after three x in a row. The 38-state member of the family, /srv/**x????, prints size=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 then Dfa minimization no states removed: partitions 65542 init 3 (accept 1) (abi/5.0 feature 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 of x are in every state once the star has started, and ?1, ?2 and the accept node join when an x was seen one, two or three bytes back.
  • Not determined: memory per state and peak memory.

for AppArmor developers for security researchers

Read more

09 Where to go from here

ROADS Permissions in the DFAwhat an accepting state may do Minimisation38 states become 22 Table compressiondefault plus exceptions, packed Globbing (AARE)for profile authors Choosing abstractionswhere the states come from How the kernel checks an accessa machine like this, walked
Roads from this deck: permissions in the DFA, minimisation, table compression, globbing and choosing abstractions for profile authors, and how the kernel checks an access

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

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

RulesStates createdAfter merging
/srv/a r,88
10 rules /srv/file0 to /srv/file91212
100 rules /srv/file100 to /srv/file1991414
/srv/** r,88
/srv/**/data r,1313
5 rules /srv/**/{data,cache,state,logs,tmp} r,, written separately2525
the same 5 with w, plus /srv/**/*.conf r,3131
/srv/** r, /srv/**.log r, /srv/**.sock r, /srv/**/lock r,2316
the same four paths with r, w, rw, k3029
/**/a/**/b/**/c r,2014
/srv/{a,b,c}/{d,e,f}/{g,h,i} r,1212
/srv/**x?? r,1414
/srv/**x???? r,3838
/srv/**x?????? r,134134
/srv/**x???????? r,518518
/srv/**x?????????? r,20542054
/srv/**x and 14 ?3277432774
/srv/**x and 15 ?6554265542, then the error
base, nameservice, user-tmp abstractions and one rule23871695
  • Above 65534 states the parser prints Too many states (N) for type state_t and exits with status 1 (tree). The message names no profile.
  • -O state32 lifts the limit when the kernel's features list policy/state32 (code).

for AppArmor developers for security researchers

Subset construction

StepWhere
clear position data of shared accept nodeshfa.cc:481-487
compute_pos: nullable, firstpos, lastpos, followposhfa.cc:489-494, rules at expr-tree.h:305-334
state 0 from the empty set, state 1 from the root's firstposhfa.cc:489-497
work queue: update_state_transitions per statehfa.cc:441-465, hfa.cc:373-427
add_new_state: intern the node sets, find or create the statehfa.cc:329-371
statisticshfa.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

FieldMeaning
labelthe number printed as {n} in dumps
transexplicit transitions, a map from input character to state
otherwisethe default target for every character not in trans
permsallow, deny, prompt, audit, quiet masks; computed in the constructor
  • State::next(c) looks in trans and falls back to otherwise (hfa.h:319-334) (code).
  • State 0 is the non-matching state and state 1 the start; the kernel's DFA_NOMATCH and DFA_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 transchar with 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_range 257 when one is present (hfa.cc:511-514) (code).
  • Kernel: aa_dfa_outofband_transition (match.c:581), which needs MATCH_FLAG_OOB_TRANSITION on the state's base entry (code).
  • Warning: xattr attachment conditional ignored when the kernel lacks policy/outofband or 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 { ... }

FieldMeaning
statesstates created, including state 0
protopairs (non-accept set, accept set) that identify a state
nnodessets of non-accept nodes
anodessets of accept nodes
sizedistinct entries
dupsinsertions that found an existing entry
longest, avgsize 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-map prints 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 equiv out 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< compares audit twice (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

FILE ACCESS

PROFILE HEAD

IN PRACTICE · general-purpose apps

IN THE KERNEL

THE DFA ENGINE · libapparmor_re