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
- The backend pipeline — the nine stages; this is the first box
- Globbing (AARE) — the wildcards that become regular expressions here
Part of journeys
- From profile text to kernel tables, step 7 of 13 · previous: The backend pipeline · next: Building the DFA
01 Before there are states, there is a tree
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
- The files of this stage: parser/parser_regex.c (pattern to string), parser/libapparmor_re/parse.y (string to nodes), parser/libapparmor_re/expr-tree.h and parser/libapparmor_re/expr-tree.cc (nodes and simplifiers), parser/libapparmor_re/aare_rules.cc (grouping and
build_tree). - Three dump options show the stage:
-D rule-exprs,-D expr-tree,-D expr-stats. - The profile, complete (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,
}
- 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.0feature set and with a feature set that has the kernel'spolicyentries; the dumps of the two other profiles used in this deck were made withabi/5.0. - Seen the machine walked? That is How the kernel checks an access.
Read more
- wiki: TechnicalDoc_HFA. The page is marked draft by its authors; where it and the code differ, this deck follows the code.
- The backend pipeline: the stage list. How the kernel checks an access: the machine this tree ends up as.
02 A glob becomes a regular expression
* 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, orInvalid;*first_re_posis the offset of the first glob (parser_regex.c:121, parser_regex.c:213). anchoradds^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/inprofiles/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
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
- The grammar (parse.y:85-161):
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 asCHAR. A backslash is decoded bystr_escseqwith the extra set*+.|^$-[](){}. - Escapes decoded by
strn_escseq(lib.c:155-213): up to three octal digits;\dplus up to three decimal digits;\xplus up to two hex digits;\a \e \f \n \r \t;\\;\". Example: the class marker\d21parses 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 sharedepsnode(parse.y:85-94). - On a syntax error
regex_errorprints nothing (parse.y:197-202) andadd_rule_vecreturns 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
\xplus unpadded hex (expr-tree.cc:78-79), so[^\x0/]is "not NUL and not slash", and NUL followed by1prints as\x01. - Node kinds (expr-tree.h:243-269 for
node_type_t):
| Class | Matches | expr-tree.h lines |
|---|---|---|
EpsNode | the empty string; one static instance epsnode | 512-537 |
CharNode | one transchar | 568-611 |
CharSetNode | any of a set | 614-680 |
NotCharSetNode | any byte not in the set; never an out of band character | 683-757 |
AnyCharNode | any byte (.) | 760-775 |
StarNode, PlusNode, OptionalNode | repetition of one child | 778-861 |
CatNode, AltNode | sequence and alternation with a vector of children | 963-1103 |
SharedTreeNode | a subtree referenced from several places | 880-960 |
MatchFlag, ExactMatchFlag, DenyMatchFlag, PromptMatchFlag | nothing; mark an accepting position | 1150-1205 |
transcharholds ashort: 0 to 255 are bytes, negative values are out of band characters, and only -1 is used (expr-tree.h:89-91, expr-tree.h:105-112).OptionalNodeexists and the grammar never creates one (parse.y:102-105).min_match_len()gives the shortest match and stops at an out of band character (expr-tree.h:596-606, expr-tree.h:1039-1055); xmatch uses it.AnyCharNodedoes not override it and counts as 0 (expr-tree.h:760-775); globs never produce that node for an attachment, and no effect was found.
Read more
- parser/libapparmor_re/parse.y; wiki: TechnicalDoc_HFA.
- Building the DFA: what
followdoes on each node kind.
04 One group per accept node
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)andbool 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.insertreturns the one accept node for a key; its class is chosen by testing in the orderDenyMatchFlag,PromptMatchFlag,ExactMatchFlag,MatchFlag(aare_rules.h:78-101). So a deny rule is never exact. exact_matchis 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_rulesstoresexpr_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 whenoobis true (aare_rules.cc:64-72, aare_rules.cc:83-91). A link pair islink \x00 target(parser_regex.c:692-716);change_profilebuilds up to three vectors (parser_regex.c:765-784); mount rules use NUL-separated fields (mount.cc:836). Only the xattr tail usesoob = true(parser_regex.c:597-601). - The masks (immunix.h:25-44):
0x10004is read for owner (0x4) and for other (0x4 shifted left by 14);0x804201is exec (0x1) and inherit (0x200) for owner and the same two bits shifted by 14 for other;0x3800eis 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
-Soutput was identical in four runs. - Known discrepancy:
reverseis applied twice (aare_rules.cc:107-108, aare_rules.cc:55-56); no caller sets it.
05 Factoring inside a group
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'srule-mergejoins the two rules for/etc/demo/a.confinto onerwrule (< 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.0feature 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-mergethe 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: removesepsnodechildren 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_altandfactor_run(expr-tree.cc:818-906); the header comment givesab | ac -> a(b | c),ba | ca -> (b | c)aanda | ab -> a(E | b).- The right (suffix) pass runs first;
-O expr-left-simplifyswaps the order (expr-tree.cc:967-970). - The
expr-vector:line countsflattened, eps, chars, dups, collapsed, factored(expr-tree.cc:973-976).-D expr-statsprints 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
- wiki: TechnicalDoc_HFA on normalization and factoring; the deck follows the code where they differ.
- parser/libapparmor_re/expr-tree.cc.
- Post-processing: rule merge.
06 Two simplifiers, and why right comes first for AppArmor developers
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_oldrunsnormalize(dir)(whenexpr-normalizeis set) andsimplify_tree_baseuntil nothing changes, for direction 1 and then 0 (expr-tree.cc:984-1017).MAX_PASSESis 1 (expr-tree.cc:983).- Its pieces are
merge_charset(expr-tree.cc:313),basic_alt_factor(expr-tree.cc:337) andbasic_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.0feature 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-normalizeis accepted with the default simplifier and does nothing; the vector simplifier never callsnormalize(expr-tree.cc:1004-1005, common_optarg.c:95-96).
07 One tree for the whole DFA
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, computesmin_match_len, buildsCat(group, accept)and joins the groups left to right with binaryAltNode(aare_rules.cc:162-187).- The whole-tree simplification is commented out (aare_rules.cc:249), so
-D expr-treealready shows the simplified tree unless-O no-expr-simplifyis given (comment at aare_rules.cc:230-234).label_nodesnumbers 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
policyentries (the tree'sabi/5.0gives the same line):
DFA: Expression Tree ((/(home/([^\x0/])*|root)/\.ssh/[^\x0/]([^\x0])*< 0x3800e>|/usr/bin/[abcdefghijklmnopqrstuvwxyz]([^\x0/])*< 0x804201>)|/etc/demo/[^\x0/]([^\x0])*< 0x10004>)
- The slide wraps that one line at the group boundaries and shortens the groups in the sketch.
- Line formats:
-D rule-exprsprintsaare: <pattern> -> <regex>(parser_regex.c:142-143, parser_regex.c:441-442) andrule: <regex> -> <tree> priority=N [deny|prompt] (0x<perms>/<audit>)<accept>(aare_rules.cc:112-135);-D expr-statsprints node counts before and after (expr-tree.cc:1024-1028, expr-tree.cc:1037-1041) and the vector counters (expr-tree.cc:973-976);-D expr-treeprintsDFA: Expression Tree(aare_rules.cc:236-240). - The group map is keyed by the address of the accept node (aare_rules.h:104); the
-Soutput was identical in four runs. - Known discrepancy:
-D expr-simplifiedprints the same tree a second time (aare_rules.cc:242-255).
Read more
- Building the DFA: the first positions of this tree are the start state.
- wiki: TechnicalDoc_HFA.
09 Where to go from here
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
- The stage in four lines: each pattern is rewritten as a regular expression; the string is parsed into nodes; rules are grouped by accept node and each group is simplified; the groups are joined into one tree.
- Building the DFA: states are sets of positions of this tree. Permissions in the DFA: what the accept nodes carry and how they combine.
- Globbing (AARE) and From AARE to regular expressions: where the patterns come from. Variables: where
@{HOME}was expanded. Extended attribute conditions, Exec modes. - The backend pipeline; How the kernel checks an access.
- Read for this deck: AppArmor 836052d21 and Linux 97d73c825.
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
| Glob | In a path | In an xattr value (glob_null) | |
|---|---|---|---|
* | [^/\x00]* | [^/]* | |
** | [^\x00]* | .* | |
? | [^/\x00] | [^/] | |
{a,b} | `(a | b)`, up to 50 levels | the same |
[...] | copied | copied |
- 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_pcrereturnspattern_t::Basic(no glob),TailGlob(only a final**),RegexorInvalid(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,
\dplus up to three decimal digits,\xplus up to two hex digits,\a \e \f \n \r \t,\\,\"(code). - Absent: a
?operator and anchors.+exists (code).
Node kinds
| Class | Matches | expr-tree.h lines |
|---|---|---|
EpsNode | the empty string | 512-537 |
CharNode | one transchar | 568-611 |
CharSetNode | any of a set | 614-680 |
NotCharSetNode | any byte not in the set; never an out of band character | 683-757 |
AnyCharNode | any byte | 760-775 |
StarNode, PlusNode, OptionalNode | repetition of one child | 778-861 |
CatNode, AltNode | sequence, alternation | 963-1103 |
SharedTreeNode | a subtree referenced from several places | 880-960 |
MatchFlag, ExactMatchFlag, DenyMatchFlag, PromptMatchFlag | nothing; mark an accepting position | 1150-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 givesPromptMatchFlag, exact givesExactMatchFlag, otherwiseMatchFlag(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
| Pass | What it does | expr-tree.cc lines | ||||
|---|---|---|---|---|---|---|
flatten_node | splices a Cat in a Cat, an Alt in an Alt | 606-626 | ||||
simplify_vec_cat | removes empty children, collapses a one-child Cat | 676-699 | ||||
merge_alt_chars | `a | b | [cd] to [abcd]` | 705-734 | ||
simplify_vec_alt | sorts alternatives, drops duplicates, factors | 909-935 | ||||
factor_alt, factor_run | `ab | ac to a(b | c), ba | ca to (b | c)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-vectorselectssimplify_tree_old(expr-tree.cc:980-1017):normalize(dir)whenexpr-normalizeis set, thensimplify_tree_base, for direction 1 and then 0 (code).- Pieces:
merge_charset,basic_alt_factor,basic_simplify(expr-tree.cc:204-520) (code).
Dumps
| Option | Line format | |
|---|---|---|
-D rule-exprs | aare: <pattern> -> <regex> and `rule: <regex> -> <tree> priority=N [deny | prompt] (0x<perms>/<audit>)<accept>` |
-D expr-stats | `expr tree: c .., [] .., [^] .., | .., + .., * .., . .., cat .., the expr-vector: counters, simplified expr tree: ...` |
-D expr-tree | DFA: 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):
| Options | Tree | States 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/(b | sub/a)\.conf | other)< 0x10004> | /etc/demo/a\.conf< 0x3800e>)` | 32 |
-O no-expr-vector | `(/etc/(demo/(sub/a | b)\.conf | other)< 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
| Message | parser_regex.c line |
|---|---|
Regex grouping error: Invalid close ], no matching open [ detected | 275 |
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 { detected | 323 |
Regex grouping error: Unclosed grouping or character class, expecting close } | 414 |
Regex error: trailing '\' escape character | 421 |
Unable to parse input line '%s' | 430 |
warning: Character %c was quotedunnecessarily, dropped preceding quote ('\') character | 396-399 |
All rows: code.
Known discrepancies
-D expr-treeand-D expr-simplifiedprint the same tree (aare_rules.cc:236-255) (tree).reverseis 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-normalizedoes nothing with the default simplifier (code).- By title: "Character classes:
\^loses its escape, and*or?inside[...]are expanded"; "NotCharSetNode::contains_oob()is inverted, soxmatch_lenstops at the first wildcard"; "Without anabirule,xattrs=is dropped silently andchange_profile -> &xis 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
- How the kernel checks an access — the finished machine walked by the kernel
FILE ACCESS
- Globbing (AARE) — what the wildcards mean in a profile
- Exec modes — why exact rules matter for exec
PREAMBLE AND REUSE
- Variables — where the home variable was expanded
PROFILE HEAD
- Extended attribute conditions — the attachment condition behind the shared tail
INSIDE THE PARSER
- From AARE to regular expressions — the front end code that hands patterns to the backend
THE DFA ENGINE · libapparmor_re
- Building the DFA — the next stage where states are built from this tree
- Permissions in the DFA — what the accept nodes at the leaves carry
- The backend pipeline — the stage list this deck is the first box of