Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb

[jwcart2 <jwcart2@tycho.nsa.gov>]

[-- Attachment #1: Type: text/plain, Size: 7424 bytes --]

On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
> On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> 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.c
>>>
>>
>> It 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@tycho.nsa.gov>
>> National Security Agency
> --
> Ondrej Mosnacek <omosnace at redhat dot com>
> Software Engineer, Security Technologies
> Red Hat, Inc.
> 


-- 
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency

[-- Attachment #2: test_01.conf --]
[-- Type: text/plain, Size: 4295 bytes --]

# 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:s01

[-- Attachment #3: test.sh --]
[-- Type: application/x-shellscript, Size: 990 bytes --]