On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@xxxxxxxxxxxxx> wrote:On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:This series implements an optional optimization step when building a policydb via semodule or secilc, which identifies and removes rules that are redundant -- i.e. they are already covered by a more general rule based on attribute inheritance. Since the performance penalty of this additional step is very small (it adds about 1 s to the current running time of ~20-30 s [1]) and it can have a big positive effect on the number of rules in policy (it manages to remove ~40% AV rules from Fedora 29 policy), the optimization is enabled by default and can be turned off using a command-line option (--no-optimize) in secilc and semodule [2]. The optimization routine eliminates: * all allow/neverallow/dontaudit/auditallow rules (including xperm variants) that are covered by another more general rule, * all conditional versions of the above rules that are covered by a more general rule either in the unconditional table or in the same branch of the same conditional. The optimization doesn't process other rules, since they currently do not support attributes. There is some room left for more precise optimization of conditional rules, but it would likely bring only little additional benefit. When the policy is mostly or fully expanded, the optimization should be turned off. If it isn't, the policy build time will increase a lot for no benefit. However, the complexity of optimization will be only linear w.r.t. the number of rules and so the impact should not be catastrophic. (When testing with secilc on a subset of Fedora policy with -X 100000 the build time was 1.7 s with optimization vs. 1 s without it.) Tested live on my Fedora 29 devel machine under normal use. No unusual AVCs were observed with optimized policy loaded. Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427 NOTE: The xperm rule support wasn't tested -- I would welcome some peer review/testing of this part. [1] As measured on my machine (Fedora 29 policy, x86_64). [2] I have no problem with switching it to opt-in if that is preferred. Ondrej Mosnacek (4): libsepol: add a function to optimize kernel policy secilc: optimize policy before writing libsemanage: optimize policy on rebuild semodule: add flag to disable policy optimization libsemanage/include/semanage/handle.h | 4 + libsemanage/src/direct_api.c | 7 + libsemanage/src/handle.c | 13 + libsemanage/src/handle.h | 1 + libsemanage/src/libsemanage.map | 5 + libsepol/include/sepol/policydb.h | 5 + libsepol/include/sepol/policydb/policydb.h | 2 + libsepol/src/libsepol.map.in | 5 + libsepol/src/optimize.c | 370 +++++++++++++++++++++ libsepol/src/policydb_public.c | 5 + policycoreutils/semodule/semodule.c | 12 +- secilc/secilc.c | 16 +- 12 files changed, 442 insertions(+), 3 deletions(-) create mode 100644 libsepol/src/optimize.cIt would be nice to have checkpolicy support this as well. It shouldn't be too hard to do that.Looking at checkpolicy.c, it looks like it only generates POLICY_BASE or POLICY_MODULE policy types. I currently limit the optimization only to POLICY_KERN type, because from comments in policydb.h I got the impression that other policy types have different structure and I'm not sure if they need some special handling. I don't have that much knowledge about SELinux userspace code yet... if you can give me some hints about the difference between the various POLICY_* types, then I will be happy to make some adjustments if they make sense.
It is kind of confusing. I sent a patch to the list. You can incorporate that into your patch series or I can just do it after.
I've attached the test policy that I used and a test script. I haven't had a chance to dig more into what may be going on.
Jim
I need to do some more testing, but I think something is not working correctly. I am starting from conf files here because I have both Fedora and Android ones that I have used for testing and it is easier to run them through checkpolicy to convert to CIL. With these rules: # Redundant 1 allow tp01 tpr1:cl01 { p01a p11a p01b p11b }; allow tp02 tpr1:cl01 { p01a p11a }; allow at02 tpr1:cl01 { p01a p11a p01b }; # Redundant 2 dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b }; dontaudit tp02 tpr2:cl01 { p01a p11a }; dontaudit at02 tpr2:cl01 { p01a p11a p01b }; # Redundant 3 allow at02 tpr3:cl01 { p01a p11a p01b }; if (b01) { allow tp01 tpr3:cl01 { p01a p11a p01b p11b }; allow tp02 tpr3:cl01 { p01a p11a }; } # Redundant 4 dontaudit at02 tpr4:cl01 { p01a p11a p01b }; if (b01) { dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b }; dontaudit tp02 tpr4:cl01 { p01a p11a }; } I see the following from sediff: Allow Rules (0 Added, 1 Removed, 0 Modified) Removed Allow Rules: 1 - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True Dontaudit Rules (0 Added, 1 Removed, 1 Modified) Removed Dontaudit Rules: 1 - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True Modified Dontaudit Rules: 1 * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b }; So it handles Redundant 1 just fine, but has problems with Redundant 2 which should be the same.Yes, I think I'm handling the dontaudit rules incorrectly... For some (historical?) reason they actually specify the permissions that *are* audited, although the semantic of combining multiple rules is still that a permission is dontaudited if there is at least one dontaudit rule for it, so the logic of handling the raw perms data has to be inverted for AVTAB_AUDITDENY entries. I had noticed earlier that AVTAB_AUDITDENY rules are handled differently but somehow I concluded that the perms values should still bitwise-or together... Can you please try it with adding: if (specified & AVTAB_AUDITDENY) return (d1->data & d2->data) == d2->data; to the beginning of match_avtab_datum() in optimize.c? (patch form here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)I don't remember what to expect from sediff for boolean rules. I had played around with removing rules with some of my earlier lua tools and I thought that sediff handled removing redundant rules from booleans, but I could be wrong. I will look at this more maybe tomorrow, but most likely after the Memorial day weekend. Jim -- James Carter <jwcart2@xxxxxxxxxxxxx> National Security Agency-- Ondrej Mosnacek <omosnace at redhat dot com> Software Engineer, Security Technologies Red Hat, Inc.
-- James Carter <jwcart2@xxxxxxxxxxxxx> National Security Agency
# All policy.conf rules
# Called test_02.conf in expected_pass/conf
# Added redundantallow rules that are covered by attribute
class cl01
class cl02
class cl03
class cl04
class clx
sid kernel
sid security
sid unlabeled
common cm01 { p11a p11b }
common cm02 { p22a p22b }
class cl01 inherits cm01 { p01a p01b }
class cl02 inherits cm02
class cl03 { p03a p03b }
class cl04 { p04a p04b }
class clx { ioctl }
default_user { cl01 cl02 cl03 } source;
default_role { cl01 } source;
default_type { cl02 } target;
default_range { cl03 } target low-high;
sensitivity s01 alias syslow;
sensitivity s02;
sensitivity s03 alias { syshigh maxsens };
dominance { s01 s02 s03 }
category c01 alias cat01;
category c02 alias { cat02a cat02b };
category c03;
level s01;
level s02:c01,c03;
level s03:c01.c03;
mlsconstrain cl01 { p01a } ((h1 dom h2) and (l1 domby h1));
mlsvalidatetrans cl02 ((l1 eq l2) or (l1 incomp l2));
mlsvalidatetrans cl02 ((l1 eq l2) or (t3 eq tpo));
policycap network_peer_controls;
policycap open_perms;
attribute at01;
attribute at02;
attribute_role ar01;
attribute_role ar02;
bool b01 false;
bool b02 true;
type tpo;
type tpx;
type tp01;
type tp02;
type tp03p;
type tp03c;
type tp04;
type tpr1;
type tpr2;
type tpr3;
type tpr4;
type tpr5;
typealias tp01 alias { ta01a ta01b };
typealias tp02 alias ta02;
typebounds tp03p tp03c;
typeattribute tp01 at01, at02;
typeattribute tp02 at02;
permissive tp01;
allow tp01 self:cl01 { p01a p11a };
allow tp01 ta01a:cl01 p01b;
allow tp01 at01:cl01 p11b;
allow tp01 tpo:cl02 p22a;
allow at02 tpo:cl02 p22b;
allow tp03p tpo:cl03 { p03a p03b };
allow tp03c tpo:cl03 p03a;
allow tp04 tpx:clx ioctl;
auditallow tp01 tpo:cl01 p01a;
dontaudit tp01 tpo:cl01 p01b;
neverallow tp01 tpo:cl01 p11a;
# Redundant 1
allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
allow tp02 tpr1:cl01 { p01a p11a };
allow at02 tpr1:cl01 { p01a p11a p01b };
# Redundant 2
dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr2:cl01 { p01a p11a };
dontaudit at02 tpr2:cl01 { p01a p11a p01b };
# Redundant 3
allow at02 tpr3:cl01 { p01a p11a p01b };
if (b01) {
allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
allow tp02 tpr3:cl01 { p01a p11a };
}
# Redundant 4
dontaudit at02 tpr4:cl01 { p01a p11a p01b };
if (b01) {
dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr4:cl01 { p01a p11a };
}
# Redundant 5
if (b01) {
allow tp01 tpr5:cl01 { p01a p11a p01b p11b };
allow tp02 tpr5:cl01 { p01a p11a };
} else {
allow at02 tpr5:cl01 { p01a p11a p01b };
}
allowxperm tp04 tpx:clx ioctl 0x1234;
auditallowxperm tp04 tpx:clx ioctl 0x9911;
dontauditxperm tp04 tpx:clx ioctl 0x9922;
neverallowxperm tp04 tpx:clx ioctl 0x9933;
type_transition tp01 tpo:cl01 tp02;
type_member tp01 tpo:cl02 tp02;
type_change tp01 tpo:cl03 tp02;
type_transition tp01 tpo:cl04 tp02 "file01";
range_transition tp01 tpo:cl01 s02;
range_transition tp01 tpo:cl02 s02 - s03:c01,cat02a;
role rl01;
role rl02;
role rl03p;
role rl03c;
role rl01 types { tp01 tp02 };
role rl02 types { tp02 };
role rl03p types tp03p;
role rl03c types tp03c;
roleattribute rl01 ar01, ar02;
roleattribute rl02 ar02;
allow rl01 rl02;
role_transition rl01 tpo:cl01 rl02;
user us01 roles rl01 level s01 range s01 - s03:c01.c03;
constrain cl01 { p01b } not ((t1 == tpo) and (u1 != u2));
validatetrans cl02 ((u1 == u2) or (r1 == r2));
validatetrans cl02 ((u1 == u2) or (t3 == tpo));
sid kernel us01:rl01:tp01:syslow - syshigh:c01,cat02b,c03
sid security us01:rl01:tp01:s01 - s02
sid unlabeled us01:rl01:tp01:s02:c01,c03 - maxsens:cat01,c03
fs_use_xattr fs01 us01:rl01:tp01:s01;
fs_use_task fs02 us01:rl01:tp01:s01;
fs_use_trans fs03 us01:rl01:tp01:s01;
genfscon fs04 / us01:rl01:tp01:s01
portcon udp 1000 us01:rl01:tp01:s01
portcon udp 1001-1009 us01:rl01:tp01:s01
portcon tcp 2000 us01:rl01:tp01:s01
portcon tcp 2001-2009 us01:rl01:tp01:s01
portcon dccp 3000 us01:rl01:tp01:s01
portcon dccp 3001-3009 us01:rl01:tp01:s01
netifcon if01 us01:rl01:tp01:s01 us01:rl01:tp02:s01
nodecon 10.0.0.1 255.255.255.0 us01:rl01:tp01:s01
nodecon fc00::1 fc00::ffff us01:rl01:tp01:s01
# XEN
#pirqcon 65535 us01:rl01:tp01:s01
#iomemcon 0-99999 us01:rl01:tp01:s01
#ioportcon 0-99999 us01:rl01:tp01:s01
#pcidevicecon 99999 us01:rl01:tp01:s01
#devicetreecon "/PATH" us01:rl01:tp01:s01Attachment:
test.sh
Description: application/shellscript
