The current behavior of priority rules can be non-intuitive with
higher priority rules completely overriding lower priority rules even in
permissions not held in common. This behavior does have use cases but
its can be very confusing, and does not normal policy behavior
Eg.
priority=0 allow r /**,
priority=1 deny w /**,
will result in no allowed permissions even though the deny rule is
only removing the w permission, beause the higher priority rule
completely over ride lower priority permissions sets (including
none shared permissions).
Instead move to tracking the priority at a per permission level. This
allows the w permission to still override at priority 1, while the
read permission is allowed at priority 0.
The final constructed state will still drop priority for the final
permission set on the state.
Note: this patch updates the equality tests for the cases where
the complete override behavior was being tested for.
The complete override behavior will be reintroduced in a future
patch with a keyword extension, enabling that behavior to be used
for ordered blocks etc.
Signed-off-by: John Johansen <john.johansen@canonical.com>
The priority field is only used during state construction, and can
even prevent later optimizations like minimization. The parser already
explcitily clears the states priority field as part of the last thing
done during construction so it doesn't prevent minimization
optimizations.
This means the state priority not only wastes storage because it is
unused post construction but if used it could introduce regressions,
or other issues.
The change to the minimization tests just removes looking for the
priority field that is no longer reported.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Construction of the chfa can reorder states from what the numbering
given during the hfa constuctions because of reordering for better
compression, dead state removal to ensure better packing etc.
This however means the dfa dump is difficult (it is possible using
multiple dumpes) to match up to the chfa that the kernel is
using. Make this easier by making the dfa dump be able to take the
emapping as input, and provide an option to dump the chfa equivalent
hfa.
Renumbered states will show up as {new <== {orig}} in the dump
Eg.
--D dfa-states
{1} <== priority (allow/deny/prompt/audit/quiet)
{5} 0 (0x 4/0//0/0/0)
{1} perms: none
0x2 -> {5} 0 (0x 4/0//0/0/0)
0x4 -> {5} 0 (0x 4/0//0/0/0)
\a 0x7 -> {5} 0 (0x 4/0//0/0/0)
\t 0x9 -> {5} 0 (0x 4/0//0/0/0)
\n 0xa -> {5} 0 (0x 4/0//0/0/0)
\ 0x20 -> {5} 0 (0x 4/0//0/0/0)
4 0x34 -> {3}
{3} perms: none
0x0 -> {6}
{6} perms: none
1 0x31 -> {5} 0 (0x 4/0//0/0/0)
-D dfa-compressed-states
{1} <== priority (allow/deny/prompt/audit/quiet)
{2 == {5}} 0 (0x 4/0//0/0/0)
{1} perms: none
0x2 -> {2 == {5}} 0 (0x 4/0//0/0/0)
0x4 -> {2 == {5}} 0 (0x 4/0//0/0/0)
\a 0x7 -> {2 == {5}} 0 (0x 4/0//0/0/0)
\t 0x9 -> {2 == {5}} 0 (0x 4/0//0/0/0)
\n 0xa -> {2 == {5}} 0 (0x 4/0//0/0/0)
\ 0x20 -> {2 == {5}} 0 (0x 4/0//0/0/0)
4 0x34 -> {3}
{3} perms: none
0x0 -> {4 == {6}}
{4 == {6}} perms: none
1 0x31 -> {2 == {5}} 0 (0x 4/0//0/0/0)
Signed-off-by: John Johansen <john.johansen@canonical.com>
The parser recently changed how/where deny information is applied.
commit 1fa45b7c1 ("parser: dfa minimization prepare for extended
permissions") removed the implicit filtering of explicit denies during
the minimization pass. The implicit clear allowed the explicit
information to be carried into the minimization pass and merged with
implicit denies. The end result being a minimized dfa with the explicit
deny information available to be applied post minimization, and
then dropped later at permission encoding in the accept entries.
Extended permission however enable carrying explicit deny information
into the kernel to fix certain bugs like complain mode not being
able to distinguish between implicit and explicit deny rules (ie.
deny rules get ignored in complain mode). However keeping explicit
deny information when unnecessary result in a larger state machine
than necessary and slower compiles.
commit 179c1c1ba ("parser: fix minimization check for filtering_deny")
Moved the explicit apply_and_clear_deny() pass to before minimization
to restore mnimization's ability to create a minimized dfa with
explicit and implicit deny information merged but this also cleared
the explicit deny information that used to be carried through
minimization. This meant that when the deny information was applied
post minimization it resulted in the audit and quiet information
being cleared.
This resulted in the query_label tests failing as they are checking
for the expected audit infomation in the permissions.
Fixes: 179c1c1ba ("parser: fix minimization check for filtering_deny")
Bug: https://gitlab.com/apparmor/apparmor/-/issues/461
Signed-off-by: John Johansen <john.johansen@canonical.com>
MR: https://gitlab.com/apparmor/apparmor/-/merge_requests/1408
Approved-by: Ryan Lee <rlee287@yahoo.com>
Approved-by: John Johansen <john@jjmx.net>
Merged-by: John Johansen <john@jjmx.net>
The parser recently changed how/where deny information is applied.
commit 1fa45b7c1 ("parser: dfa minimization prepare for extended
permissions") removed the implicit filtering of explicit denies during
the minimization pass. The implicit clear allowed the explicit
information to be carried into the minimization pass and merged with
implicit denies. The end result being a minimized dfa with the explicit
deny information available to be applied post minimization, and
then dropped later at permission encoding in the accept entries.
Extended permission however enable carrying explicit deny information
into the kernel to fix certain bugs like complain mode not being
able to distinguish between implicit and explicit deny rules (ie.
deny rules get ignored in complain mode). However keeping explicit
deny information when unnecessary result in a larger state machine
than necessary and slower compiles.
commit 179c1c1ba ("parser: fix minimization check for filtering_deny")
Moved the explicit apply_and_clear_deny() pass to before minimization
to restore mnimization's ability to create a minimized dfa with
explicit and implicit deny information merged but this also cleared
the explicit deny information that used to be carried through
minimization. This meant that when the deny information was applied
post minimization it resulted in the audit and quiet information
being cleared.
This resulted in the query_label tests failing as they are checking
for the expected audit infomation in the permissions.
Fixes: 179c1c1ba ("parser: fix minimization check for filtering_deny")
Bug: https://gitlab.com/apparmor/apparmor/-/issues/461
Signed-off-by: John Johansen <john.johansen@canonical.com>
There is an integer overflow when comparing priorities when cmp is
used because it uses subtraction to find lessthan, equal, and greater
than in one operation.
But INT_MAX and INT_MIN are being used by priorities and this results
in INT_MAX - INT_MIN and INT_MIN - INT_MAX which are both overflows
causing an incorrect comparison result and selection of the wrong
rule permission.
Closes: https://gitlab.com/apparmor/apparmor/-/issues/452
Fixes: e3fca60d1 ("parser: add the ability to specify a priority prefix to rules")
Signed-off-by: John Johansen <john.johansen@canonical.com>
Moving apply_and_clear_deny() before the first minimization pass, which
was necessary to propperly support building accept information for
older none extended permission dfas, allows us to also get rid of doing a
second minimization pass if we want to force clearing explicit deny
info from extended permission tables.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Instead of compressing the permission set into 128 bit and using that
as the index in the permission map, just use the permissions directly
as the index into the permission map.
Note: this will break equality and minimization tests. Because deny
is not being cleared it will result in more partitions in the initial
setup. This will be addressed and the tests will be fixed in a follow
on patch.
Signed-off-by: John Johansen <john.johansen@canonical.com>
switch permission bits to use perm32_t type. This is just annotating
the code as it is no different than uint32_t at this time.
We do not convert the accept values as they may be mapped permission
bits or they may be and index value.
Signed-off-by: John Johansen <john.johansen@canonical.com>
v1 of permstable32 has some broken verification checks. By using two
copies of a merged dfa and an xtable the same size of the permstable
we can work around the issue.
Signed-off-by: John Johansen <john.johansen@canonical.com>
If extended permissions are supported use them. We need to build a
permission table and set the accept state of the chfa up as an index
into the table.
For now map the front end permission layout into the old format and
then convert that to the perms table just as the kernel does.
Signed-off-by: John Johansen <john.johansen@canonical.com>
speedup and reduce memory usage of dfa generation
A variety of changes to improve dfa generation
- By switching to Nodevec instead of Node sets we can reduce memory usage slightly and reduce code
- By using charsets for chars we reduce code and increase chances of node merging/reduction which reduces memory usage slightly
- By merging charsets we reduce the number of nodes
Signed-off-by: John Johansen <john.johansen@canonical.com>
MR: https://gitlab.com/apparmor/apparmor/-/merge_requests/1066
Approved-by: John Johansen <john@jjmx.net>
Merged-by: John Johansen <john@jjmx.net>
In preparation for more flags (not all of the backend dfa based),
rework the optimization and dump flag handling which has been exclusively
around the dfa up to this point.
- split dfa control and dump flags into separate fields. This gives more
room for new flags in the existing DFA set
- rename DFA_DUMP, and DFA_CONTROL to CONTROL_DFA and DUMP_DFA as
this will provide more uniform naming for none dfa flags
- group dump and control flags into a structure so they can be passed
together.
Signed-off-by: John Johansen <john.johansen@canonical.com>
With the exception of the documentation fixes, these should all be
invisible to users.
Signed-off-by: Steve Beattie <steve.beattie@canonical.com>
Acked-by: Christian Boltz <apparmor@cboltz.de>
MR: https://gitlab.com/apparmor/apparmor/-/merge_requests/687
v8 network permissions extend into the range used by exec mapping
so it is important to not blindly do execmapping on both the
file dfa and policydb dfa any more.
Track what type of dfa and its permissions we are building so
we can properly apply exec mapping only when building the
file dfa.
MR: https://gitlab.com/apparmor/apparmor/-/merge_requests/521
Signed-off-by: John Johansen <john.johansen@canonical.com>
Currently the NULL character is used as an out of band transition
for string/path elements. This works for them as the NULL character
is not valid for this data. However this does not work for binary
data that can contain a NULL character.
So far we have only dealt with fixed length fields of binary data
making the NULL separator either unnecessary.
However binary data like in the xattr match and mount data field are
variable length and can contain NULL characters. To deal with this
add the ability to specify out of band transitions, that can only
be triggered by code not input data.
The out of band transition can be used to separate variable length
data fields just as the NULL transition has been used to separate
variable length strings.
In the compressed hfa out of band transitions are expressed as a
negative offset from the states base. This leaves us room to expand
the character match range in the future if desired and on average
makes the range between the out of band transition and the input
transitions smaller than would be had if the out of band transition
had been stored after the valid input transitions.
Out of band transitions in the dfa will not break old kernels
that don't know about them, but they won't be able to trigger
the out of band transition match. So they should not be used unless
the kernel indicates that it supports them.
It should be noted that this patch only adds support for a single
out of band transition. If multiple out of band transitions are
required. It is trivial to extend.
- Add a tag indicating support in the kernel
- add a oob max range field to the dfa header so the kernel knows
what the max range that needs verifying is.
- extend oob generation fns to generate oob based on value instead
of a fixed -1.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Compiling the parser currently prints a deprecation warning. Remove
throw(int) annotations from function signatures. These aren't required
to catch exceptions.
For example, the following program catches the exception without a
throw(int) annotation:
#include <iostream>
void throw_an_error()
{
throw 3;
return;
}
int main ()
{
try
{
throw_an_error();
}
catch (int e)
{
std::cout << "caught exception " << e << '\n';
}
return 0;
}
This program prints:
$ g++ -o error error.cc
$ ./error
caught exception 3
Signed-off-by: Eric Chiang <ericchiang@google.com>
Refactor add_new_state into two versions, one that splits anodes from
nnodes, and one for use when anodes and nnodes are presplit
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Steve Beattie <steve@nxnw.org>
Acked-by: Seth Arnold <seth.arnold@canonical.com>
We need to rework permission type mapping to nodesets, which means we
need to move the nodeset computations earlier in the dfa creation
processes, instead of a post step of follow(), so move the nodeset
into expr-tree
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Steve Beattie <steve@nxnw.org>
Acked-by: Seth Arnold <seth.arnold@canonical.com>
So DFA minimization has a bug and feature that keeps it from minimizing
some dfas completely. This feature/bug did not result in incorrect dfas,
it just fails to result in full minimization.
The same mappings comparison is wrong. Or more correctly it is right when
transitions are not remapped to minimization partitions, but it may be
wrong when states are remapped. This means it will cause excess
partitioning (not removing all the states it should).
The trans hashing does a "guess" at partition splitting as a performance
enhancement. Basically it leverages the information that states that have
different transitions or transitions on different characters are not the
same. However this isn't always the case, because minimization can cause
some of those transitions to be altered. In previous testing this was
always a win, with only a few extra states being added some times. However
this changes with when the same mappings are fixed, as the hashing that was
done was based on the same flawed mapping as the broken same mappings.
If the same mappings are fixed and the hashing is not removed then there
is little to no change. However with both changes applied some dfas see
significant improvements. These improvements often result in performance
improvements despite minimization doing more work, because it means less
work to be done in the chfa comb compression
eg. test case that raised the issue (thanks tyler)
/t { mount fstype=ext2, mount, }
used to be minimized to
{1} <== (allow/deny/audit/quiet)
{6} (0x 2/0/0/0)
{1} -> {2}: 0x7
{2} -> {3}: 0x0
{2} -> {2}: []
{3} -> {4}: 0x0
{3} -> {3}: []
{4} -> {6}: 0x0
{4} -> {7}: 0x65 e
{4} -> {5}: []
{5} -> {6}: 0x0
{5} -> {5}: []
{6} (0x 2/0/0/0) -> {6}: [^\0x0]
{7} -> {6}: 0x0
{7} -> {8}: 0x78 x
{7} -> {5}: []
{8} -> {6}: 0x0
{8} -> {5}: 0x74 t
{8} -> {5}: []
with the patch it is now properly minimized to
{1} <== (allow/deny/audit/quiet)
{6} (0x 2/0/0/0)
{1} -> {2}: 0x7
{2} -> {3}: 0x0
{2} -> {2}: []
{3} -> {4}: 0x0
{3} -> {3}: []
{4} -> {6}: 0x0
{4} -> {4}: []
{6} (0x 2/0/0/0) -> {6}: [^\0x0]
The evince profile set sees some significant improvements picking a couple
example from its "minimized" dfas (it has 12) we see a reduction from 9720
states to 6232 states, and 6537 states to 3653 states. All told seeing the
performance/profile size going from
2.8 parser: 4.607s 1007267 bytes
dev head: 3.48s 1007267 bytes
min fix: 2.68s 549603 bytes
of course evince is an extreme example so a few more
firefox
2.066s 404549 bytes
to
1.336s 250585 bytes
cupsd
0.365s 90834 bytes
to
0.293s 58855 bytes
dnsmasq
0.118s 35689 bytes
to
0.112s 27992 bytes
smbd
0.187s 40897 bytes
to
0.162s 33665 bytes
weather applet profile from ubuntu touch
0.618s 105673 bytes
to
0.432s 89300 bytes
I have not seen a case where the parser regresses on performance but it is
possible. This patch will not cause a regression on generated policy size,
at worst it will result in policy that is the same size
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Tyler Hicks <tyhicks@canonical.com>
Acked-by: Steve Beattie <steve@nxnw.org>
Differential state compression encodes a state's transitions as the
difference between the state and its default state (the state it is
relative too).
This reduces the number of transitions that need to be stored in the
transition table, hence reducing the size of the dfa. There is a
trade off in that a single input character may have to traverse more
than one state. This is somewhat offset by reduced table sizes providing
better locality and caching properties.
With carefully encoding we can still make constant match time guarentees.
This patch guarentees that a state that is differentially encoded will do at
most 3m state traversal to match an input of length m (as opposed to a
non-differentially compressed dfa doing exactly m state traversals).
In practice the actually number of extra traversals is less than this becaus
we selectively choose which states are differentially encoded.
In addition to reducing the size of the dfa by reducing the number of
transitions that have to be stored. Differential encoding reduces the
number of transitions that need to be considered by comb compression,
which can result in tighter packing, due to a reduction in sparseness, and
also reduces the time spent in comb compression which currently uses an
O(n^2) algorithm.
Differential encoding will always result in a DFA that is smaller or equal
in size to the encoded DFA, and will usually improve compilation times,
with the performance improvements increasing as the DFA gets larger.
Eg. Given a example DFA that created 8991 states after minimization.
* If only comb compression (current default) is used
52057 transitions are packed into a table of 69591 entries. Achieving an
efficiency of about 75% (an average of about 7.74 table entries per state).
With a resulting compressed dfa16 size of 404238 bytes and a run time for
the dfa compilation of
real 0m9.037s
user 0m8.893s
sys 0m0.036s
* If differential encoding + comb compression is used, 8292 of the 8991
states are differentially encoded, with 31557 trans removed. Resulting in
20500 transitions are packed into a table of 20675 entries. Acheiving an
efficiency of about 99.2% (an average of about 2.3 table entries per state
With a resulting compressed dfa16 size of 207874 bytes (about 48.6%
reduction) and a run time for the dfa compilation of
real 0m5.416s (about 40% faster)
user 0m5.280s
sys 0m0.040s
Repeating with a larger DFA that has 17033 states after minimization.
* If only comb compression (current default) is used
102992 transitions are packed into a table of 137987 entries. Achieving
an efficiency of about 75% (an average of about 8.10 entries per state).
With a resultant compressed dfa16 size of 790410 bytes and a run time for d
compilation of
real 0m28.153s
user 0m27.634s
sys 0m0.120s
* with differential encoding
39374 transition are packed into a table of 39594 entries. Achieving an
efficiency of about 99.4% (an average of about 2.32 entries per state).
With a resultant compressed dfa16 size of 396838 bytes (about 50% reduction
and a run time for dfa compilation of
real 0m11.804s (about 58% faster)
user 0m11.657s
sys 0m0.084s
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Seth Arnold <seth.arnold@canonical.com>
The deny information is not used as valid accept state information,
so remove it from the is_null test. This does not change the dfa
generated but does result in the dumped information changing,
as states that don't have any accept information are no longer
reported as accepting. This is what changes the number of states
reported in the minimize tests.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
Also make sure the perms method properly switches to hex and back to dec
as some of the previous perm dump code did not.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
Minimization was failing because it was too agressive. It was minimizing
as if there was only 1 accept condition. This allowed it to remove more
states but at the cost of loosing unique permission sets, they where
being combined into single commulative perms. This means that audit,
deny, xtrans, ... info on one path would be applied to all other paths
that it was combined with during minimization.
This means that we need to retain the unique accept states, not allowing
them to be combined into a single state. To do this we put each unique
permission set into its own partition at the start of minimization.
The states within a partition have the same permissions and can be combined
within the other states in the partition as the loss of unique path
information is will not result in a conflict.
This is similar to what perm hashing used to do but deny information is
still being correctly applied and carried.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
The in x intersection consistency test for minimization was failing because
it was screening off the AA_MAY_EXEC permission before passing the exec
information to the consistency test fn. This resulted in the consistency
test fn not testing the consistency because it treated the permission set
as not having x permissions.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
Previously permission information was thrown away early and permissions
where packed to their CHFA form at the start of DFA construction. Because
of this permissions hashing to setup the initial DFA partitions was
required as x transition conflicts, etc. could not be resolved.
Move the mapping of permissions to CHFA construction, and track the full
permission set through DFA construction. This allows removal of the
perm_hashing hack, which prevented a full minimization from happening
in some DFAs. It also could result in x conflicts not being correctly
detected, and deny rules not being fully applied in some situations.
Eg.
pre full minimization
Created dfa: states 33451
Minimized dfa: final partitions 17033
with full minimization
Created dfa: states 33451
Minimized dfa: final partitions 9550
Dfa minimization no states removed: partitions 9550
The tracking of deny rules through to the completed DFA construction creates
a new class of states. That is states that are marked as being accepting
(carry permission information) but infact are non-accepting as they
only carry deny information. We add a second minimization pass where such
states have their permission information cleared and are thus moved into the
non-accepting partion.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Kees Cook <kees@ubuntu.com>
Delay the packing of audit and quiet permissions until chfa construction,
and track deny and quiet perms during DFA construction, so that we will
be able to do full minimization. Also delay the packing of audit and
Signed-off-by: John Johansen <john.johansen@canonical.com>
Currently hfa::match calls hfa::match_len to do matching. However this
requires walking the input string twice. Instead provide a match routine
for input that is supposed to terminate at a given input character.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
Add the ability to match strings directly from the hfa instead of needing
to build a cfha.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-By: Steve Beattie <sbeattie@ubuntu.com>
instead of a NodeSet.
We need to store sets of Nodes, to compute the dfa but the C++ set is
not the most efficient way to do this as, it has a has a lot of overhead
just to store a single pointer.
Instead we can use an array of tightly packed pointers + a some header
information. We can do this because once the Set is finalized it will
not change, we just need to be able to reference and compare to it.
We don't use C++ Vectors as they have more overhead than a plain array
and we don't need their additional functionality.
We only replace the use of hashedNodeSets for non-accepting states as
these sets are only used in the dfa construction, and dominate the memory
usage. The accepting states still may need to be modified during
minimization and there are only a small number of entries (20-30), so
it does not make sense to convert them.
Also introduce a NodeVec cache that serves the same purpose as the NodeSet
cache that was introduced earlier.
This is not abstracted this out as nicely as might be desired but avoiding
the use of a custom iterator and directly iterating on the Node array
allows for a small performance gain, on larger sets.
This patch reduces the amount of heap memory used by dfa creation by about
4x - overhead. So for small dfas the savings is only 2-3x but on larger
dfas the savings become more and more pronounced.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Kees Cook <kees@ubuntu.com>
non-accepting, and have the proto-state use them.
To reduce memory overhead each set gains its own "cache" that make sure
there is only a single instance of each NodeSet generated. And since
we have a cache abstraction, move relavent stats into it.
Also refactor code slightly to make caches and work_queue etc, DFA member
variables instead of passing them as parameters.
The split + caching results in a small reduction in memory use as the
cost of ProtoState + Caching is less than the redundancy that is eliminated.
However this results in a small decrease in performance.
Sorry I know this really should have been split into multiple patches
but the patch evolved and I got lazy and decided to just not bother
splitting it.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Kees Cook <kees@ubuntu.com>
It is the functional equivalent of ProtoState. We do this to provide a
new level of abstraction that ProtoState can leverage, when the node types
are split.
Signed-off-by: John Johansen <john.johansen@canonical.com>
Acked-by: Kees Cook <kees@ubuntu.com>
Create a new ProtoState class that will encapsulate the split, but for
this patch it will just contain what was done previously with NodeSet
Signed-off-by: John Johansen <john.johansen@canonical.com>
