The expression tree

simplify and factor for AppArmor developers for security researchers

Each path pattern becomes a regular expression string and then a tree of nodes. Rules are grouped by permission and each group is flattened and factored on its own. The groups are joined into one tree whose leaves end in accept nodes. That tree is the input of the DFA construction.

On the map: the dfa engine

▶ Watch this deck — 9 scenes, ~7 min

Worth seeing first

Part of journeys

01 Before there are states, there is a tree

THE EXPRESSION TREE /etc/demo/** r,audit deny @{HOME}/.ssh/** rw,/usr/bin/[a-z]* ix, regular expression string regular expression string regular expression string | one tree, accept nodes at the leaves DFA construction followed through this deck: the three rules of demo for people who work on parser/libapparmor_re
Three rules of the demo profile each become a regular expression string; the strings are parsed and joined into one tree with three branches that each end in an accept node; the tree is the input of the DFA construction

Patterns become regular expression strings, strings become node trees, trees are grouped by permission, simplified, and joined into the one tree that subset construction starts from.

In the pipeline deck, the first box said tree. This is that box. The backend doesn't go from rules to states directly. It first turns every pattern into a regular expression, parses that into a small tree, sorts the trees into groups, tidies each group, and joins them into one tree. Only then does state building start, and how big that gets depends a good deal on the shape of this tree. We'll follow demo's three rules all the way. This deck is for people who work on the parser's code, or who want to know exactly which bytes a pattern matches.

Details and sources

Details

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,
}
  • All dumps in this deck come from the parser built from the AppArmor tree, with nothing loaded into a kernel. The dumps of the three-rule profile are the same with the tree's abi/5.0 feature set and with a feature set that has the kernel's policy entries; the dumps of the two other profiles used in this deck were made with abi/5.0.
  • Seen the machine walked? That is How the kernel checks an access.

Read more

02 A glob becomes a regular expression

-D rule-exprs aare: /etc/demo/** -> /etc/demo/[^/\x00][^\x00]* one character, not a slash then anything aare: /usr/bin/[a-z]* -> /usr/bin/[a-z][^/\x00]* the class is copied; this * is not a whole component aare: {/home/*,/root}/.ssh/** -> (/home/[^/\x00]*|/root)/\.ssh/[^/\x00][^\x00]* @{HOME} was expanded before the backend saw it; { , } becomes ( | ); the dot is escaped *[^/\x00]* **[^\x00]* ?[^/\x00] so /etc/demo/** does not match /etc/demo/
The three patterns of the demo profile rewritten as regular expressions as printed by -D rule-exprs, and the translation of star, double star and question mark into character classes that exclude NUL

* is [^/\x00]*, ** is [^\x00]*, ? is [^/\x00]. A * or ** that is a whole path component gets [^/\x00] in front. -D rule-exprs prints each rewrite.

Look at the first rule. Its two stars are a whole path component, so the parser puts one mandatory character in front, one that isn't a slash, and then anything. In the second rule the class a to z is simply copied. In the third, the @{HOME} variable is already gone, expanded to an alternation by the front end. In general, a single star is any run of characters except slash and the NUL byte, a double star is anything except NUL, and a question mark is one character that isn't a slash. And that mandatory character is why the first rule doesn't match the directory name with its slash.

Details and sources

Details

  • pattern_t convert_aaregex_to_pcre(const char *aare, int anchor, int glob, std::string& pcre, int *first_re_pos) (parser_regex.c:118-119); the translation is at parser_regex.c:149-405.
  • * gives [^/\x00]*, ** gives [^\x00]*, ? gives [^/\x00]. A run of * that follows / and is followed by / or the end of the pattern gets [^/\x00] inserted first (parser_regex.c:178-205).
  • So /etc/demo/* does not match /etc/demo/, while /etc/demo* does match /etc/demo.
  • {a,b} gives (a|b), nested up to 50 levels (MAX_ALT_DEPTH, parser_regex.c:122, parser_regex.c:293). [...] is copied; {, } and , are literal inside it. A negated class such as [^a] in a profile is copied as written and can match /.
  • ., +, |, (, ) are always escaped; ^ and $ are escaped outside a class (parser_regex.c:358-380).
  • The return value classifies the pattern: pattern_t::Basic (no glob), TailGlob (only a final **), Regex, or Invalid; *first_re_pos is the offset of the first glob (parser_regex.c:121, parser_regex.c:213).
  • anchor adds ^ and $ (parser_regex.c:145-147, parser_regex.c:425-427); every caller in parser_regex.c passes 0.
  • xattr values use another glob set (glob_null): * is [^/]*, ** is .*, ? is [^/], so a value may contain NUL (parser_regex.c:204, parser_regex.c:220, parser_regex.c:225, parser_regex.c:582-584).
  • @{HOME} is @{HOMEDIRS}/*/ /root/ in profiles/apparmor.d/tunables/home, line 21; the front end expands it before the backend sees the pattern.
  • Errors, as in the source: Regex grouping error: Invalid close ], no matching open [ detected (parser_regex.c:275), Regex grouping error: Exceeded maximum nesting of {} (parser_regex.c:295), Regex grouping error: Invalid number of items between {} (parser_regex.c:317), Regex grouping error: Invalid close }, no matching open { detected (parser_regex.c:323), Regex grouping error: Unclosed grouping or character class, expecting close } (parser_regex.c:414), Regex error: trailing '\' escape character (parser_regex.c:421), Unable to parse input line '%s' (parser_regex.c:430).
  • Warning, as in the source: Character %c was quotedunnecessarily, dropped preceding quote ('\') character (parser_regex.c:396-399).
  • Known discrepancy: the missing blank between "quoted" and "unnecessarily" in that warning.
  • Known discrepancy, by title: "Character classes: \^ loses its escape, and * or ? inside [...] are expanded".

03 The string becomes nodes

parse.y /etc/demo/[^/\x00][^\x00]* CatNode /etc/demo/ CharNode x 10 [^\x0/] NotCharSetNode StarNode [^\x0] NotCharSetNode rule: /etc/demo/[^/\x00][^\x00]* -> /etc/demo/[^\x0/]([^\x0])* priority=0 (0x10004/0)< 0x10004> the tree, printed back no ? operator, no anchors, + exists; a one-member class becomes a CharNode
The regular expression for /etc/demo/** parsed into a CatNode with ten CharNode children, a NotCharSetNode and a StarNode over another NotCharSetNode, and the same tree printed back by -D rule-exprs

regex_parse (parser/libapparmor_re/parse.y:85-161) builds CharNode, CharSetNode, NotCharSetNode, AnyCharNode, StarNode, PlusNode, CatNode and AltNode. The rule: line of -D rule-exprs shows the tree printed back.

Step two is a real parser, but a tiny one: a page of yacc in parse.y. Our string becomes a CatNode, a sequence, with ten character nodes for the literal part, then a negated set, then a star over another negated set. The second half of the rule-exprs line is this tree printed back. The grammar knows characters, the dot, classes and their negation, star, plus, the bar and parentheses. There's no question mark operator, and there are no anchors. And a class with a single member is turned into a plain character node, so it can be factored with its neighbours later.

Details and sources

Details

regex:  /* empty */ | expr
expr:   terms | expr '|' terms0 | '|' terms0
terms:  qterm | terms qterm
qterm:  term | term '*' | term '+'
term:   '.' | regex_char | '[' charset ']' | '[' '^' charset ']'
        | '[' '^' '^' cset_chars ']' | '(' regex ')'
  • The lexer (parse.y:167-195) returns the bytes * + . | ^ - [ ] ( ) as themselves and everything else as CHAR. A backslash is decoded by str_escseq with the extra set *+.|^$-[](){}.
  • Escapes decoded by strn_escseq (lib.c:155-213): up to three octal digits; \d plus up to three decimal digits; \x plus up to two hex digits; \a \e \f \n \r \t; \\; \". Example: the class marker \d21 parses to the single byte 0x15 (rule: \d21 -> \x15).
  • A class with one member becomes a CharNode (parse.y:109-114). An empty alternative is the shared epsnode (parse.y:85-94).
  • On a syntax error regex_error prints nothing (parse.y:197-202) and add_rule_vec returns false (aare_rules.cc:81-82).
  • An invalid escape is kept as a literal backslash followed by the character, with a TODO for an error message (parse.y:181-191). The grammar's own FIXME lists [--], [---] and [^^-x] as not parsed (parse.y:81-83).
  • Dump quirk: a non-printing byte prints as \x plus unpadded hex (expr-tree.cc:78-79), so [^\x0/] is "not NUL and not slash", and NUL followed by 1 prints as \x01.
  • Node kinds (expr-tree.h:243-269 for node_type_t):
ClassMatchesexpr-tree.h lines
EpsNodethe empty string; one static instance epsnode512-537
CharNodeone transchar568-611
CharSetNodeany of a set614-680
NotCharSetNodeany byte not in the set; never an out of band character683-757
AnyCharNodeany byte (.)760-775
StarNode, PlusNode, OptionalNoderepetition of one child778-861
CatNode, AltNodesequence and alternation with a vector of children963-1103
SharedTreeNodea subtree referenced from several places880-960
MatchFlag, ExactMatchFlag, DenyMatchFlag, PromptMatchFlagnothing; mark an accepting position1150-1205

Read more

04 One group per accept node

expr_map /etc/demo/[^\x0/]([^\x0])* /usr/bin/[a-z]([^\x0/])* (/home/...|/root)/\.ssh/... key: priority, mode, exact, perms, audit < 0x10004>allow: read, owner + other/etc/demo/... < 0x804201>allow: exec + inherit/usr/bin/[a-z]... < 0x3800e>deny: write, read, append(/home/...|/root)/\.ssh/... /etc/other r, | /etc/other expr_map[accept] = AltNode(old, tree) same key: it joins the first group behind a | exact = no star, plus, any-char or negated class: /usr/bin/demo r, would get a group of its own
Three rule trees filed into three groups, each under its own accept node: read 0x10004, exec and inherit 0x804201, and the deny node 0x3800e; a fourth read rule joins the first group behind an alternation

add_rule_vec files each rule under the accept node for its (priority, mode, exact, perms, audit) (aare_rules.h:39-59, aare_rules.cc:53-62). Simplification later runs inside one group only.

Now the grouping, which decides what can be simplified with what. Every rule comes with a priority, a kind, allow or deny or prompt, a permission mask and an audit mask. The backend keeps exactly one accept node for each distinct combination, and files every rule under its accept node. Our three rules have three different permissions, so there are three groups. Add a fourth rule with plain read, and it joins the first group behind a bar. One more field is in the key: whether the rule is exact, meaning its tree has no star, no plus, no dot and no negated class. That matters for exec rules; the permissions deck picks it up.

Details and sources

Details

  • Signatures (aare_rules.h:137-141): bool add_rule(const char *rule, int priority, rule_mode_t mode, perm32_t perms, perm32_t audit, optflags const &opts) and bool add_rule_vec(int priority, rule_mode_t mode, perm32_t perms, perm32_t audit, int count, const char **rulev, optflags const &opts, bool oob).
  • The key is UniquePerm: priority, mode, exact, perms, audit (aare_rules.h:39-59). unique_perms.insert returns the one accept node for a key; its class is chosen by testing in the order DenyMatchFlag, PromptMatchFlag, ExactMatchFlag, MatchFlag (aare_rules.h:78-101). So a deny rule is never exact.
  • exact_match is 1 unless the tree contains a star, a plus, an any-char or a negated set (aare_rules.cc:98-105): /usr/bin/[a-z] is exact, /usr/bin/? is not (? is a negated set).
  • add_to_rules stores expr_map[accept] = AltNode(old, tree) (aare_rules.cc:53-62).
  • Multi-part rules are joined with CharNode(0), or with the out of band character when oob is true (aare_rules.cc:64-72, aare_rules.cc:83-91). A link pair is link \x00 target (parser_regex.c:692-716); change_profile builds up to three vectors (parser_regex.c:765-784); mount rules use NUL-separated fields (mount.cc:836). Only the xattr tail uses oob = true (parser_regex.c:597-601).
  • The masks (immunix.h:25-44): 0x10004 is read for owner (0x4) and for other (0x4 shifted left by 14); 0x804201 is exec (0x1) and inherit (0x200) for owner and the same two bits shifted by 14 for other; 0x3800e is write, read and append (0xe) for both halves.
  • The map is keyed by the address of the accept node (aare_rules.h:104), so the order of the groups in a dump changes between runs. The -S output was identical in four runs.
  • Known discrepancy: reverse is applied twice (aare_rules.cc:107-108, aare_rules.cc:55-56); no caller sets it.

05 Factoring inside a group

simplify_tree /etc/demo/a.conf r,/etc/demo/b.conf r,/etc/demo/sub/a.conf r,/etc/other r,/etc/demo/a.conf w, a second profile: four read rules and one write rule merged with the first rule into another group (rw) before ((/etc/demo/sub/a\.conf|/etc/demo/b\.conf)|/etc/other)< 0x10004> right first: common endings after /etc/(demo/(b|sub/a)\.conf|other)< 0x10004> then left: common beginnings expr tree: c 46 ... cat 43 -> simplified expr tree: c 26 ... cat 4 -D expr-stats Created dfa: states 37 -> states 32 after minimize: 32 both ways in the three-rule example: /(home/...|root)
A second profile with four read rules: before simplification the group is three paths side by side; after factoring common endings and beginnings it is /etc/(demo/(b|sub/a)\.conf|other); character nodes drop from 46 to 26 and created states from 37 to 32

simplify_tree flattens, merges single characters, removes duplicate alternatives and factors suffixes, then prefixes: ab|ac to a(b|c). Five rules: 46 character nodes to 26; 37 created states to 32.

Inside a group the simplifier goes to work. To see it, give demo a few more configuration files: this is a second profile, with four read rules and one write rule. Before simplifying, the group is just the paths side by side. The simplifier flattens nested sequences and alternations, sorts the alternatives, drops exact duplicates, and then factors. First the common endings, so .conf appears once. Then the common beginnings. Forty-six character nodes become twenty-six. What does that buy? Subset construction creates thirty-two states instead of thirty-seven. After minimization it's thirty-two either way. So simplification doesn't change the final machine here. It makes the expensive step in the middle smaller.

Details and sources

Details

  • The profile on this slide is not the three-rule example. It has five rules: /etc/demo/a.conf r,, /etc/demo/b.conf r,, /etc/demo/sub/a.conf r,, /etc/other r, and /etc/demo/a.conf w,. The front end's rule-merge joins the two rules for /etc/demo/a.conf into one rw rule (< 0x3800e>) before the backend sees them. That is why the read group on the slide has three paths and the dump has a second group.
  • Run with the parser of the AppArmor tree, abi/5.0 feature set, -D expr-tree -D expr-stats:
-O no-expr-simplify:
(((/etc/demo/sub/a\.conf|/etc/demo/b\.conf)|/etc/other)< 0x10004>|/etc/demo/a\.conf< 0x3800e>)
Created dfa: states 37
Minimized dfa: final partitions 32 (accept 2)	init 4 (accept 2)

default:
expr tree: c 46, [] 0, [^] 0, | 2, + 0, * 0, . 0, cat 43
expr-vector: flattened 42, eps 0, chars 0, dups 0, collapsed 3, factored 3
simplified expr tree: c 26, [] 0, [^] 0, | 2, + 0, * 0, . 0, cat 4
(/etc/(demo/(b|sub/a)\.conf|other)< 0x10004>|/etc/demo/a\.conf< 0x3800e>)
Created dfa: states 32
Dfa minimization no states removed: partitions 32	init 4 (accept 2)
  • With -O no-rule-merge the tree is (/etc/demo/a\.conf< 0x2800a>|/etc/(demo(/b|([]|/sub)/a)\.conf|other)< 0x10004>); [] is the empty alternative.
  • The passes of simplify_tree (expr-tree.cc:1019-1044, vector code at expr-tree.cc:572-978):
  • flatten_node: a Cat inside a Cat, or an Alt inside an Alt, is spliced into its parent (expr-tree.cc:606-626);
  • simplify_vec_cat: removes epsnode children and collapses a one-child Cat (expr-tree.cc:676-699);
  • merge_alt_chars: a|b|[cd] becomes [abcd] (expr-tree.cc:705-734);
  • simplify_vec_alt: sorts the alternatives, drops adjacent equals, then factors (expr-tree.cc:909-935);
  • factor_alt and factor_run (expr-tree.cc:818-906); the header comment gives ab | ac -> a(b | c), ba | ca -> (b | c)a and a | ab -> a(E | b).
  • The right (suffix) pass runs first; -O expr-left-simplify swaps the order (expr-tree.cc:967-970).
  • The expr-vector: line counts flattened, eps, chars, dups, collapsed, factored (expr-tree.cc:973-976). -D expr-stats prints one block per group, because simplification runs per group. The three blocks of the three-rule example:
expr tree: c 17, [] 0, [^] 3, | 1, + 0, * 2, . 0, cat 18
expr-vector: flattened 16, eps 0, chars 0, dups 0, collapsed 1, factored 1
simplified expr tree: c 16, [] 0, [^] 3, | 1, + 0, * 2, . 0, cat 3
expr tree: c 9, [] 1, [^] 1, | 0, + 0, * 1, . 0, cat 10
expr-vector: flattened 9, eps 0, chars 0, dups 0, collapsed 0, factored 0
simplified expr tree: c 9, [] 1, [^] 1, | 0, + 0, * 1, . 0, cat 1
expr tree: c 10, [] 0, [^] 2, | 0, + 0, * 1, . 0, cat 11
expr-vector: flattened 10, eps 0, chars 0, dups 0, collapsed 0, factored 0
simplified expr tree: c 10, [] 0, [^] 2, | 0, + 0, * 1, . 0, cat 1
  • Not determined: the cost of simplification on large profiles; whether the two simplifiers can give different final DFAs.

Read more

06 Two simplifiers, and why right comes first for AppArmor developers

-O no-expr-vector expr-vector (default)(/etc/(demo/(b|sub/a)\.conf|other)< 0x10004>|/etc/demo/a\.conf< 0x3800e>) -O no-expr-vector(/etc/(demo/(sub/a|b)\.conf|other)< 0x10004>|/etc/demo/a\.conf< 0x3800e>)normalize by rotation, factor pairwise both: Created dfa: states 32 -O no-expr-vector -O no-expr-normalize(((/etc/demo/sub/a|/etc/demo/b)\.conf|/etc/other)< 0x10004>|...)only the ending is factored simplify_tree_old: direction 1 (right), then 0 (left) source comment: about 7 thousand states against about 1.25 million in one test
The same five rules simplified three ways: the default vector simplifier, the older simplifier with -O no-expr-vector, and the older one without normalization, where only the ending is factored; all three create 32 states

expr-vector (default) and the older rotate-and-factor simplifier (-O no-expr-vector). Both factor suffixes first; the comment at expr-tree.cc:991-996 gives about 7 thousand against about 1.25 million states for one test.

There are two simplifiers in the tree. The default works on nodes that hold a vector of children, which is what you just saw. The older one works on strictly binary trees: it rotates them into a normal form and factors neighbours pairwise. You get it back by switching expr-vector off. On our five rules both arrive at the same thirty-two states, with the alternatives in a different order. Turn normalization off as well and only the common ending gets factored. Both simplifiers do the right-hand side first, and a comment in the old one says why: in one test it was the difference between seven thousand states and one and a quarter million.

Details and sources

Details

  • simplify_tree_old runs normalize(dir) (when expr-normalize is set) and simplify_tree_base until nothing changes, for direction 1 and then 0 (expr-tree.cc:984-1017). MAX_PASSES is 1 (expr-tree.cc:983).
  • Its pieces are merge_charset (expr-tree.cc:313), basic_alt_factor (expr-tree.cc:337) and basic_simplify (expr-tree.cc:391). The simplifier is selected at expr-tree.cc:1030-1033.
  • The comment on the order of the two directions: expr-tree.cc:991-996.
  • The three trees on the slide come from the five-rule profile of the previous scene, run with the parser of the AppArmor tree and the abi/5.0 feature set. All three variants create 32 states; the third is (((/etc/demo/sub/a|/etc/demo/b)\.conf|/etc/other)< 0x10004>|/etc/demo/a\.conf< 0x3800e>) in full.
  • Known discrepancy: -O no-expr-normalize is accepted with the default simplifier and does nothing; the vector simplifier never calls normalize (expr-tree.cc:1004-1005, common_optarg.c:95-96).

07 One tree for the whole DFA

-D expr-tree ((/(home/([^\x0/])*|root)/\.ssh/[^\x0/]([^\x0])*< 0x3800e>|/usr/bin/[abcdefghijklmnopqrstuvwxyz]([^\x0/])*< 0x804201>)|/etc/demo/[^\x0/]([^\x0])*< 0x10004>) | AltNode | AltNode /(home/..|root)/\.ssh/.. /usr/bin/[a-z].. /etc/demo/.. < 0x3800e> < 0x804201> < 0x10004> Cat(group, accept) factored inside the group not shared: three positions for the first slash group order follows pointer values and changes between runs; the compiled output does not
The -D expr-tree dump of the three rules and its shape: a root alternation, a second alternation under it, and three groups that each end in an accept node with the masks 0x3800e, 0x804201 and 0x10004

build_tree (aare_rules.cc:162-187): per group Cat(simplified group, accept node), joined left to right by binary AltNode. -D expr-tree prints the result; group order varies between runs.

For each group the backend builds a sequence, the group and then its accept node, and joins those sequences with plain binary alternations. Here's the real dump for our three rules: the deny group, the exec group, the read group, each ending in angle brackets with its permission mask. Inside the deny group, home and root share their slash. Across groups nothing is shared: there are three separate nodes for the first slash. That's fine, because the next stage builds states out of sets of positions, and those three slashes fall into the same set straight away. One caution when you compare dumps: the group order follows memory addresses, so it can change between runs.

Details and sources

Details

  • Node *build_tree(optflags const &opts, SharedTreeNode *tail, int *min_match_len) (aare_rules.h:120-121). For each group it simplifies, computes min_match_len, builds Cat(group, accept) and joins the groups left to right with binary AltNode (aare_rules.cc:162-187).
  • The whole-tree simplification is commented out (aare_rules.cc:249), so -D expr-tree already shows the simplified tree unless -O no-expr-simplify is given (comment at aare_rules.cc:230-234). label_nodes numbers the nodes for dumps (aare_rules.cc:235).
  • The complete dump for the file DFA of the three rules, from the parser of the AppArmor tree with a feature set that has the kernel's policy entries (the tree's abi/5.0 gives the same line):
DFA: Expression Tree
((/(home/([^\x0/])*|root)/\.ssh/[^\x0/]([^\x0])*< 0x3800e>|/usr/bin/[abcdefghijklmnopqrstuvwxyz]([^\x0/])*< 0x804201>)|/etc/demo/[^\x0/]([^\x0])*< 0x10004>)

Read more

08 A shared tail for attachment conditions

SharedTreeNode profile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*) { ... } a different profile /usr/bin/x([^\x0/])* the attachment < 0x1> accept at once \d-1 \x0 tw([^/])* [] \d-1 \x0 one < 0x1> the tail, built once out of band: no input byte can produce it /usr/bin/x([^\x0/])*(< 0x1>|\d-1\x0tw([^/])*([]|\d-1\x0one)< 0x1>) -D expr-tree user.b first: the values are in reverse order one tail, a reference from every group; the simplifier treats it as opaque
A profile with xattrs conditions: the attachment pattern ends in a choice between accepting at once and an out of band character followed by the tail that matches the attribute values, which itself ends in an accept node

With a tail, each group ends in Alt(accept, tail); the tail is one SharedTreeNode prefixed by the out of band character -1 (aare_rules.cc:203-221, 179-180). Only xattr attachment conditions use it.

A profile can say: attach to this path, but only if the file has these extended attributes. The attribute values are compiled as their own little rule set, the tail. The backend builds the tail once, puts a separator in front, and wraps it in a shared tree node. Every attachment group then ends in a choice: accept right here, or take the separator and go on into the tail. The separator isn't a NUL byte, because attribute values may contain NULs. It's an out of band character, number minus one, that the kernel feeds in between the path and the values. In the dump it prints as \d-1.

Details and sources

Details

  • The profile on this slide is profile xa /usr/bin/x* xattrs=(user.a=one user.b=tw*), not the three-rule example. Run with the parser of the AppArmor tree, abi/5.0 feature set, -D rule-exprs -D expr-tree:
aare: tw*   ->   \x00tw[^/]*
aare: one   ->   \x00one
rule: \x00tw[^/]*\-x01\x00one  ->  \x0tw([^/])*\d-1\x0one priority=0 (0x1/0)< 0x1>
DFA: Expression Tree
/usr/bin/x([^\x0/])*(< 0x1>|\d-1\x0tw([^/])*([]|\d-1\x0one)< 0x1>)
  • The tail tree is built once, prefixed with its separator and wrapped in a SharedTreeNode (aare_rules.cc:203-221); each group ends in Alt(accept, tail) (aare_rules.cc:179-180). [] is the empty alternative.
  • Its positions are computed once and reused (expr-tree.h:907-924); simplification treats it as opaque (expr-tree.cc:945-946).
  • create_chfa returns NULL when the two rule sets use different accept node caches or either is reversed (aare_rules.cc:207-209); flip_tree must not be used on a tree with a shared tail (expr-tree.h:877-878).
  • Why the separator is out of band: the comment at expr-tree.h:61-87.
  • The xattr name array in the binary policy is written from the same list (parser_interface.c:473-475), so names and values agree.
  • The condition is dropped with xattr attachment conditional ignored when the kernel lacks domain/attach_conditions/xattr or policy/outofband (parser_regex.c:549-553).
  • Not determined: why the list is in reverse order.
  • Known discrepancies, by title: "NotCharSetNode::contains_oob() is inverted, so xmatch_len stops at the first wildcard"; "Without an abi rule, xattrs= is dropped silently and change_profile -> &x is refused "by the kernel"".
  • Kernel statements are read from the kernel source and were not run.

09 Where to go from here

ROADS | Building the DFApositions become states Permissions in the DFAwhat the squares carry Globbing (AARE)every wildcard From AARE to regular expressionswhere the patterns came from The backend pipelinethis stage in its place
Roads from the expression tree: building the DFA, permissions in the DFA, globbing, from AARE to regular expressions, the backend pipeline and how the kernel checks an access

Next: building the DFA (states from positions), permissions in the DFA (accept nodes). Back: globbing, from AARE to regular expressions, the backend pipeline.

So that's the tree: strings, nodes, groups, factoring, and one alternation with an accept node at the end of every branch. The deck on building the DFA turns the positions in this tree into states. The permissions deck looks inside those little squares, the accept nodes, and at what happens when two of them meet in one state. If you came for the wildcard rules themselves, the globbing deck has every one. And the pipeline deck puts this stage back in its place.

Details and sources

Details

Read more

Basis of the statements on this page: "tree" means the parser built from the AppArmor commit 836052d21 (6.0.0~alpha2) was run (-Q -K with the -D and -O options shown), with nothing loaded into a kernel. The dumps of the three-rule profile are the same with the tree's abi/5.0 feature set and with a feature set that has the kernel's policy entries; the other dumps were made with abi/5.0. "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.

Glob translation

GlobIn a pathIn an xattr value (glob_null)
*[^/\x00]*[^/]*
**[^\x00]*.*
?[^/\x00][^/]
{a,b}`(ab)`, up to 50 levelsthe same
[...]copiedcopied
  • A run of * that follows / and is followed by / or the end gets [^/\x00] (or [^/]) in front: /etc/demo/* does not match /etc/demo/ (code, tree).
  • ., +, |, (, ) are always escaped; ^ and $ outside a class (code).
  • convert_aaregex_to_pcre returns pattern_t::Basic (no glob), TailGlob (only a final **), Regex or Invalid (parser_regex.c:118-121) (code).

The regular expression grammar

regex:  /* empty */ | expr
expr:   terms | expr '|' terms0 | '|' terms0
terms:  qterm | terms qterm
qterm:  term | term '*' | term '+'
term:   '.' | regex_char | '[' charset ']' | '[' '^' charset ']'
        | '[' '^' '^' cset_chars ']' | '(' regex ')'
  • Source: parse.y:85-161; lexer parse.y:167-195 (code).
  • Escapes (lib.c:155-213): up to three octal digits, \d plus up to three decimal digits, \x plus up to two hex digits, \a \e \f \n \r \t, \\, \" (code).
  • Absent: a ? operator and anchors. + exists (code).

Node kinds

ClassMatchesexpr-tree.h lines
EpsNodethe empty string512-537
CharNodeone transchar568-611
CharSetNodeany of a set614-680
NotCharSetNodeany byte not in the set; never an out of band character683-757
AnyCharNodeany byte760-775
StarNode, PlusNode, OptionalNoderepetition of one child778-861
CatNode, AltNodesequence, alternation963-1103
SharedTreeNodea subtree referenced from several places880-960
MatchFlag, ExactMatchFlag, DenyMatchFlag, PromptMatchFlagnothing; mark an accepting position1150-1205

transchar holds a short; 0 to 255 are bytes, negative values are out of band, only -1 is used (expr-tree.h:89-112) (code).

Grouping

  • Key: (priority, mode, exact, perms, audit) (aare_rules.h:39-59) (code).
  • Accept node class, tested in this order: deny gives DenyMatchFlag, prompt gives PromptMatchFlag, exact gives ExactMatchFlag, otherwise MatchFlag (aare_rules.h:78-101) (code).
  • Exact: the rule's tree has no star, plus, any-char or negated set (aare_rules.cc:98-105) (code).
  • Multi-part rules: parts joined with NUL, or with the out of band character -1 for the xattr tail (aare_rules.cc:64-91) (code).

The vector simplifier

PassWhat it doesexpr-tree.cc lines
flatten_nodesplices a Cat in a Cat, an Alt in an Alt606-626
simplify_vec_catremoves empty children, collapses a one-child Cat676-699
merge_alt_chars`ab[cd] to [abcd]`705-734
simplify_vec_altsorts alternatives, drops duplicates, factors909-935
factor_alt, factor_run`abac to a(bc), baca to (bc)a`818-906

Right (suffix) pass first, then left; -O expr-left-simplify swaps them. The expr-vector: line counts flattened, eps, chars, dups, collapsed, factored (code).

The older simplifier

  • -O no-expr-vector selects simplify_tree_old (expr-tree.cc:980-1017): normalize(dir) when expr-normalize is set, then simplify_tree_base, for direction 1 and then 0 (code).
  • Pieces: merge_charset, basic_alt_factor, basic_simplify (expr-tree.cc:204-520) (code).

Dumps

OptionLine format
-D rule-exprsaare: <pattern> -> <regex> and `rule: <regex> -> <tree> priority=N [denyprompt] (0x<perms>/<audit>)<accept>`
-D expr-stats`expr tree: c .., [] .., [^] ..,.., + .., * .., . .., cat .., the expr-vector: counters, simplified expr tree: ...`
-D expr-treeDFA: Expression Tree and the tree on one line

The three-rule example, file DFA (tree):

aare: /etc/demo/**   ->   /etc/demo/[^/\x00][^\x00]*
rule: /etc/demo/[^/\x00][^\x00]*  ->  /etc/demo/[^\x0/]([^\x0])* priority=0 (0x10004/0)< 0x10004>

aare: /usr/bin/[a-z]*   ->   /usr/bin/[a-z][^/\x00]*
rule: /usr/bin/[a-z][^/\x00]*  ->  /usr/bin/[abcdefghijklmnopqrstuvwxyz]([^\x0/])* priority=0 (0x804201/0)< 0x804201>

aare: {/home/*,/root}/.ssh/**   ->   (/home/[^/\x00]*|/root)/\.ssh/[^/\x00][^\x00]*
rule: (/home/[^/\x00]*|/root)/\.ssh/[^/\x00][^\x00]*  ->  (/home/([^\x0/])*|/root)/\.ssh/[^\x0/]([^\x0])* priority=0 deny (0x3800e/0)< 0x3800e>

DFA: Expression Tree
((/(home/([^\x0/])*|root)/\.ssh/[^\x0/]([^\x0])*< 0x3800e>|/usr/bin/[abcdefghijklmnopqrstuvwxyz]([^\x0/])*< 0x804201>)|/etc/demo/[^\x0/]([^\x0])*< 0x10004>)

The five-rule profile under each option set (tree, abi/5.0):

OptionsTreeStates created
-O no-expr-simplify`(((/etc/demo/sub/a\.conf/etc/demo/b\.conf)/etc/other)< 0x10004>/etc/demo/a\.conf< 0x3800e>)`37
default`(/etc/(demo/(bsub/a)\.confother)< 0x10004>/etc/demo/a\.conf< 0x3800e>)`32
-O no-expr-vector`(/etc/(demo/(sub/ab)\.confother)< 0x10004>/etc/demo/a\.conf< 0x3800e>)`32
-O no-expr-vector -O no-expr-normalize`(((/etc/demo/sub/a/etc/demo/b)\.conf/etc/other)< 0x10004>/etc/demo/a\.conf< 0x3800e>)`32

Errors and warnings

Messageparser_regex.c line
Regex grouping error: Invalid close ], no matching open [ detected275
Regex grouping error: Exceeded maximum nesting of {}295
Regex grouping error: Invalid number of items between {}317
Regex grouping error: Invalid close }, no matching open { detected323
Regex grouping error: Unclosed grouping or character class, expecting close }414
Regex error: trailing '\' escape character421
Unable to parse input line '%s'430
warning: Character %c was quotedunnecessarily, dropped preceding quote ('\') character396-399

All rows: code.

Known discrepancies

  • -D expr-tree and -D expr-simplified print the same tree (aare_rules.cc:236-255) (tree).
  • reverse is applied twice; no caller sets it (aare_rules.cc:107-108, aare_rules.cc:55-56) (code).
  • The warning about an unnecessary quote lacks a blank between "quoted" and "unnecessarily" (code).
  • -O no-expr-normalize does nothing with the default simplifier (code).
  • By title: "Character classes: \^ loses its escape, and * or ? inside [...] are expanded"; "NotCharSetNode::contains_oob() is inverted, so xmatch_len stops at the first wildcard"; "Without an abi rule, xattrs= is dropped silently and change_profile -> &x is refused "by the kernel"".

Not determined

  • Why the xattr list is in the reverse order of the profile text.
  • Whether the vector and the old simplifier can produce different final DFAs for some input; on the examples here both give the same state count.
  • The cost of simplification itself on large profiles.

Roads from here

START HERE

FILE ACCESS

PREAMBLE AND REUSE

  • Variables — where the home variable was expanded

PROFILE HEAD

INSIDE THE PARSER

THE DFA ENGINE · libapparmor_re