| Message ID | 20200227160257.340737-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | libsepol: Speed up policy optimization | expand |
On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > This series contains two small changes (these don't seem to affect > performance measurably, but are nonetheless logical) and a patch that > changes how the policy optimization "type_map" helper structure is > represented, which speeds up the whole process. > > Ondrej Mosnacek (3): > libsepol: skip unnecessary check in build_type_map() > libsepol: optimize inner loop in build_type_map() > libsepol: speed up policy optimization Not a comment on the patches themselves, but this made me wonder if the optimization support is actually tested by our travis configuration. Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf with optimize-policy true).
On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > This series contains two small changes (these don't seem to affect > > performance measurably, but are nonetheless logical) and a patch that > > changes how the policy optimization "type_map" helper structure is > > represented, which speeds up the whole process. > > > > Ondrej Mosnacek (3): > > libsepol: skip unnecessary check in build_type_map() > > libsepol: optimize inner loop in build_type_map() > > libsepol: speed up policy optimization > > Not a comment on the patches themselves, but this made me wonder if > the optimization support is actually tested by our travis > configuration. > Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf > with optimize-policy true). Adding optimize-policy = true to /etc/selinux/semanage.conf and running semodule -BN before and after these patches yields different binary kernel policy files (policy.32). Is that expected?
On Mon, Mar 2, 2020 at 9:50 AM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > > > On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > This series contains two small changes (these don't seem to affect > > > performance measurably, but are nonetheless logical) and a patch that > > > changes how the policy optimization "type_map" helper structure is > > > represented, which speeds up the whole process. > > > > > > Ondrej Mosnacek (3): > > > libsepol: skip unnecessary check in build_type_map() > > > libsepol: optimize inner loop in build_type_map() > > > libsepol: speed up policy optimization > > > > Not a comment on the patches themselves, but this made me wonder if > > the optimization support is actually tested by our travis > > configuration. > > Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf > > with optimize-policy true). > > Adding optimize-policy = true to /etc/selinux/semanage.conf and > running semodule -BN before and after these patches yields different > binary kernel policy files (policy.32). > Is that expected? Here is one example difference between the policies, along with what was present in the original unoptimized policy: $ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.unoptimized allow guest_t guest_t:context contains; allow guest_usertype guest_usertype:context contains; $ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.optimizedbefore allow guest_t guest_t:context contains; $ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.optimizedafter allow guest_usertype guest_usertype:context contains; Seems like the code prior to these changes yielded a more optimal policy since guest_usertype only has a single type in it.
On Mon, Mar 2, 2020 at 3:57 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > On Mon, Mar 2, 2020 at 9:50 AM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > > > On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley > > <stephen.smalley.work@gmail.com> wrote: > > > > > > On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > > > This series contains two small changes (these don't seem to affect > > > > performance measurably, but are nonetheless logical) and a patch that > > > > changes how the policy optimization "type_map" helper structure is > > > > represented, which speeds up the whole process. > > > > > > > > Ondrej Mosnacek (3): > > > > libsepol: skip unnecessary check in build_type_map() > > > > libsepol: optimize inner loop in build_type_map() > > > > libsepol: speed up policy optimization > > > > > > Not a comment on the patches themselves, but this made me wonder if > > > the optimization support is actually tested by our travis > > > configuration. > > > Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf > > > with optimize-policy true). Yeah, there is currently no test for this. I have something hackish that I used locally - I'll try to convert it to something more usable an automated and integrate it into the repo. > > > > Adding optimize-policy = true to /etc/selinux/semanage.conf and > > running semodule -BN before and after these patches yields different > > binary kernel policy files (policy.32). > > Is that expected? > > Here is one example difference between the policies, along with what > was present in the original unoptimized policy: > $ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.unoptimized > allow guest_t guest_t:context contains; > allow guest_usertype guest_usertype:context contains; > > $ sesearch -A -s guest_t -t guest_t -c context -p contains > policy.32.optimizedbefore > allow guest_t guest_t:context contains; > > $ sesearch -A -s guest_t -t guest_t -c context -p contains > policy.32.optimizedafter > allow guest_usertype guest_usertype:context contains; > > Seems like the code prior to these changes yielded a more optimal > policy since guest_usertype only has a single type in it. Hm... this is probably a consequence of the second patch. Types are no longer considered a superset of an attribute containing a single type, so the single-type rule gets removed instead of the attribute one... But even before it picked the first rule only by chance (it was first in order). I would say that picking a single-type rule over an attribute rule in this case is outside of the scope of the algorithm. Shouldn't the compiler automatically expand each attribute that has less than 5 types in it? I recall seeing something in the code that did this. I think this was in the CIL part of libsepol, so maybe it applies only when compiling from CIL?
On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > Hm... this is probably a consequence of the second patch. Types are no > longer considered a superset of an attribute containing a single type, > so the single-type rule gets removed instead of the attribute one... > But even before it picked the first rule only by chance (it was first > in order). I would say that picking a single-type rule over an > attribute rule in this case is outside of the scope of the algorithm. > Shouldn't the compiler automatically expand each attribute that has > less than 5 types in it? I recall seeing something in the code that > did this. I think this was in the CIL part of libsepol, so maybe it > applies only when compiling from CIL? secilc has -G and -X options for controlling expansion of attributes, but there aren't equivalent settings in semanage.conf to control when building modular policies. Internally it all uses the libsepol CIL support so it ought to be fixable. Looks like the default is 1 in cil_db_init() so it only happens when the attribute has no types by default?
On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > Yeah, there is currently no test for this. I have something hackish > that I used locally - I'll try to convert it to something more usable > an automated and integrate it into the repo. FWIW, my "test" in this case was to generate unoptimized and optimized policies before and after the patches, and use cmp as a first level check on whether the kernel policy was completely unchanged by the patches, and then when cmp failed on the old and new optimized policies, I used checkpolicy -M -F -o policy.conf -b policy.32 to decompile each of the optimized policies to policy.conf sources, and then I diff'd the two policy.conf files to see if/where they actually differed. (normally I'd use sediff for this kind of thing but in this case we want to see non-semantic differences between the policies wrt optimization, not just semantic differences, and also sediff took too much time and memory on Fedora policies until recent changes by James that I don't think have made their way into an official release yet.)
On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Hm... this is probably a consequence of the second patch. Types are no > > longer considered a superset of an attribute containing a single type, > > so the single-type rule gets removed instead of the attribute one... > > But even before it picked the first rule only by chance (it was first > > in order). I would say that picking a single-type rule over an > > attribute rule in this case is outside of the scope of the algorithm. > > Shouldn't the compiler automatically expand each attribute that has > > less than 5 types in it? I recall seeing something in the code that > > did this. I think this was in the CIL part of libsepol, so maybe it > > applies only when compiling from CIL? > > secilc has -G and -X options for controlling expansion of attributes, but > there aren't equivalent settings in semanage.conf to control when > building modular policies. > Internally it all uses the libsepol CIL support so it ought to be fixable. > Looks like the default is 1 in cil_db_init() so it only happens when > the attribute has no types by default? Apparently that was to eliminate attributes that have no types at all. Seems like we could add new options to semanage.conf to provide equivalents to secilc -G and -X, and have semanage_direct_commit() call cil_set_attrs_expand_generated() and cil_set_attrs_expand_size() in the same manner as secilc does based on those semanage.conf settings. Could also look at increasing the default size to 5 or something and see what impact that has on Fedora policies.
On Mon, Mar 2, 2020 at 9:22 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > > > On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > Hm... this is probably a consequence of the second patch. Types are no > > > longer considered a superset of an attribute containing a single type, > > > so the single-type rule gets removed instead of the attribute one... > > > But even before it picked the first rule only by chance (it was first > > > in order). I would say that picking a single-type rule over an > > > attribute rule in this case is outside of the scope of the algorithm. > > > Shouldn't the compiler automatically expand each attribute that has > > > less than 5 types in it? I recall seeing something in the code that > > > did this. I think this was in the CIL part of libsepol, so maybe it > > > applies only when compiling from CIL? > > > > secilc has -G and -X options for controlling expansion of attributes, but > > there aren't equivalent settings in semanage.conf to control when > > building modular policies. > > Internally it all uses the libsepol CIL support so it ought to be fixable. > > Looks like the default is 1 in cil_db_init() so it only happens when > > the attribute has no types by default? Okay, I don't know where I got the "5" boundary from... maybe my brain just made it up. > > Apparently that was to eliminate attributes that have no types at all. > Seems like we could add new options to semanage.conf to provide equivalents > to secilc -G and -X, and have semanage_direct_commit() call > cil_set_attrs_expand_generated() > and cil_set_attrs_expand_size() in the same manner as secilc does based on those > semanage.conf settings. > > Could also look at increasing the default size to 5 or something and > see what impact that has on > Fedora policies. Well, for a start we could increase the default to 2, which should only remove those attributes that have only one type. That has practically no downsides (other than making it a bit harder to trace the rule back to source policy) and would be just enough to make the optimization work nicely. I wouldn't change the default to higher values than that for now, since such values already trade off policy size increase for rule lookup performance, which is more of a gray area.
On Mon, Mar 2, 2020 at 10:08 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > On Mon, Mar 2, 2020 at 9:22 PM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley > > <stephen.smalley.work@gmail.com> wrote: [...] > > > secilc has -G and -X options for controlling expansion of attributes, but > > > there aren't equivalent settings in semanage.conf to control when > > > building modular policies. > > > Internally it all uses the libsepol CIL support so it ought to be fixable. > > > Looks like the default is 1 in cil_db_init() so it only happens when > > > the attribute has no types by default? [...] > > > > Apparently that was to eliminate attributes that have no types at all. > > Seems like we could add new options to semanage.conf to provide equivalents > > to secilc -G and -X, and have semanage_direct_commit() call > > cil_set_attrs_expand_generated() > > and cil_set_attrs_expand_size() in the same manner as secilc does based on those > > semanage.conf settings. > > > > Could also look at increasing the default size to 5 or something and > > see what impact that has on > > Fedora policies. > > Well, for a start we could increase the default to 2, which should > only remove those attributes that have only one type. That has > practically no downsides (other than making it a bit harder to trace > the rule back to source policy) and would be just enough to make the > optimization work nicely. I played with this a bit by recompiling the local binary policy with secilc and then comparing the CIL of both binary policies (I used this script [1]) and the results are a bit confusing... There is no difference in result between -X 0 and -X 1 [2] and in both cases it removes some unused attributes (those are only referenced from neverallow rules) that were in the original policy (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine), but not in the one recompiled via checkpolicy -C + secilc... At least I was able to confirm that secilc -X 2 really removes the attributes that have only one type and reduces the policy size by a few kilobytes. I suspect that the reason for the unremoved attributes in the policy built by semodule are due to a bug in libsepol: It seems that when it starts with a cildb that has the neverallow rules in the input policy + has disable_neverallow set, it removes the rules but not the attributes that are used only in them. Only when it reads the policy again, it identifies these unused attributes (since there are no longer any neverallow rules in the input) and removes them unconditionally. It could be something else, but if I'm right then I think libsepol should be fixed to remove the unused attributes right away. I don't dare digging into the CIL code to investigate it, though ;) [1] https://gitlab.com/omos/selinux-misc/-/blob/master/diffexpand.sh [2] Okay, this part is not really confusing, sonce semodule should already build the policy with an equivalent of -X 1, so -X 0 should yield the same result.
On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > I played with this a bit by recompiling the local binary policy with > secilc and then comparing the CIL of both binary policies (I used this > script [1]) and the results are a bit confusing... There is no > difference in result between -X 0 and -X 1 [2] and in both cases it > removes some unused attributes (those are only referenced from > neverallow rules) that were in the original policy > (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine), > but not in the one recompiled via checkpolicy -C + secilc... At least > I was able to confirm that secilc -X 2 really removes the attributes > that have only one type and reduces the policy size by a few > kilobytes. > > I suspect that the reason for the unremoved attributes in the policy > built by semodule are due to a bug in libsepol: It seems that when it > starts with a cildb that has the neverallow rules in the input policy > + has disable_neverallow set, it removes the rules but not the > attributes that are used only in them. Only when it reads the policy > again, it identifies these unused attributes (since there are no > longer any neverallow rules in the input) and removes them > unconditionally. It could be something else, but if I'm right then I > think libsepol should be fixed to remove the unused attributes right > away. I don't dare digging into the CIL code to investigate it, though > ;) James will have to confirm the details but IIRC we had to keep attributes in the policy when they are referenced by a neverallow in order to avoid breaking Android because it uses the attribute definition from the policy as part of CTS validation of OEM policies (it extracts the neverallows from the AOSP policy, extracts the binary policy from the device, and checks the neverallows against the device policy). > > [1] https://gitlab.com/omos/selinux-misc/-/blob/master/diffexpand.sh > [2] Okay, this part is not really confusing, sonce semodule should > already build the policy with an equivalent of -X 1, so -X 0 should > yield the same result.
On Wed, Mar 4, 2020 at 9:25 AM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > I played with this a bit by recompiling the local binary policy with > > secilc and then comparing the CIL of both binary policies (I used this > > script [1]) and the results are a bit confusing... There is no > > difference in result between -X 0 and -X 1 [2] and in both cases it > > removes some unused attributes (those are only referenced from > > neverallow rules) that were in the original policy > > (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine), > > but not in the one recompiled via checkpolicy -C + secilc... At least > > I was able to confirm that secilc -X 2 really removes the attributes > > that have only one type and reduces the policy size by a few > > kilobytes. > > > > I suspect that the reason for the unremoved attributes in the policy > > built by semodule are due to a bug in libsepol: It seems that when it > > starts with a cildb that has the neverallow rules in the input policy > > + has disable_neverallow set, it removes the rules but not the > > attributes that are used only in them. Only when it reads the policy > > again, it identifies these unused attributes (since there are no > > longer any neverallow rules in the input) and removes them > > unconditionally. It could be something else, but if I'm right then I > > think libsepol should be fixed to remove the unused attributes right > > away. I don't dare digging into the CIL code to investigate it, though > > ;) > > James will have to confirm the details but IIRC we had to keep > attributes in the policy > when they are referenced by a neverallow in order to avoid breaking > Android because > it uses the attribute definition from the policy as part of CTS > validation of OEM policies > (it extracts the neverallows from the AOSP policy, extracts the binary > policy from the device, > and checks the neverallows against the device policy). > Steve is correct, we keep attributes that appear in neverallow rules to avoid breaking Android. We also keep attributes that appear in typeattributesets for attributes that appear in neverallow rules. See commits 67b410e80f0917bf1b378997cac0dddf1e6406f7 (libsepol/cil: Keep attributes used by generated attributes in neverallow rules) and 0be23c3f15fdbef35a57d8586aeeae9b1f7606cc (libsepol/cil: Add ability to expand some attributes in binary policy) for more details. Jim
On Wed, Mar 4, 2020 at 4:32 PM James Carter <jwcart2@gmail.com> wrote: > On Wed, Mar 4, 2020 at 9:25 AM Stephen Smalley > <stephen.smalley.work@gmail.com> wrote: > > > > On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > I played with this a bit by recompiling the local binary policy with > > > secilc and then comparing the CIL of both binary policies (I used this > > > script [1]) and the results are a bit confusing... There is no > > > difference in result between -X 0 and -X 1 [2] and in both cases it > > > removes some unused attributes (those are only referenced from > > > neverallow rules) that were in the original policy > > > (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine), > > > but not in the one recompiled via checkpolicy -C + secilc... At least > > > I was able to confirm that secilc -X 2 really removes the attributes > > > that have only one type and reduces the policy size by a few > > > kilobytes. > > > > > > I suspect that the reason for the unremoved attributes in the policy > > > built by semodule are due to a bug in libsepol: It seems that when it > > > starts with a cildb that has the neverallow rules in the input policy > > > + has disable_neverallow set, it removes the rules but not the > > > attributes that are used only in them. Only when it reads the policy > > > again, it identifies these unused attributes (since there are no > > > longer any neverallow rules in the input) and removes them > > > unconditionally. It could be something else, but if I'm right then I > > > think libsepol should be fixed to remove the unused attributes right > > > away. I don't dare digging into the CIL code to investigate it, though > > > ;) > > > > James will have to confirm the details but IIRC we had to keep > > attributes in the policy > > when they are referenced by a neverallow in order to avoid breaking > > Android because > > it uses the attribute definition from the policy as part of CTS > > validation of OEM policies > > (it extracts the neverallows from the AOSP policy, extracts the binary > > policy from the device, > > and checks the neverallows against the device policy). > > > > Steve is correct, we keep attributes that appear in neverallow rules > to avoid breaking Android. We also keep attributes that appear in > typeattributesets for attributes that appear in neverallow rules. > > See commits 67b410e80f0917bf1b378997cac0dddf1e6406f7 (libsepol/cil: > Keep attributes used by generated attributes in neverallow rules) and > 0be23c3f15fdbef35a57d8586aeeae9b1f7606cc (libsepol/cil: Add ability to > expand some attributes in binary policy) for more details. OK, so it is actually expected behavior. Fortunately bumping the attrs_expand_size to 2 doesn't interfere with this logic (I compared the binary policies produced by semodule -B with and without the patch [1] and the neverallow-only attributes were not removed). [1] https://patchwork.kernel.org/patch/11419703/
On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > This series contains two small changes (these don't seem to affect > performance measurably, but are nonetheless logical) and a patch that > changes how the policy optimization "type_map" helper structure is > represented, which speeds up the whole process. > > Ondrej Mosnacek (3): > libsepol: skip unnecessary check in build_type_map() > libsepol: optimize inner loop in build_type_map() > libsepol: speed up policy optimization > > libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++--------- > 1 file changed, 94 insertions(+), 25 deletions(-) > > -- > 2.24.1 I can see this series marked as "Changes Requested" in patchwork - is there anything requested other than a test for policy optimization? After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to 2") the second no longer leads to a different output (with expand size >=2).
On Fri, Mar 13, 2020 at 7:53 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > This series contains two small changes (these don't seem to affect > > performance measurably, but are nonetheless logical) and a patch that > > changes how the policy optimization "type_map" helper structure is > > represented, which speeds up the whole process. > > > > Ondrej Mosnacek (3): > > libsepol: skip unnecessary check in build_type_map() > > libsepol: optimize inner loop in build_type_map() > > libsepol: speed up policy optimization > > > > libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++--------- > > 1 file changed, 94 insertions(+), 25 deletions(-) > > > > -- > > 2.24.1 > > I can see this series marked as "Changes Requested" in patchwork - is > there anything requested other than a test for policy optimization? > After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to > 2") the second no longer leads to a different output (with expand size > >=2). I suppose you could move it back to New.
On Fri, Mar 13, 2020 at 3:07 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Fri, Mar 13, 2020 at 7:53 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > This series contains two small changes (these don't seem to affect > > > performance measurably, but are nonetheless logical) and a patch that > > > changes how the policy optimization "type_map" helper structure is > > > represented, which speeds up the whole process. > > > > > > Ondrej Mosnacek (3): > > > libsepol: skip unnecessary check in build_type_map() > > > libsepol: optimize inner loop in build_type_map() > > > libsepol: speed up policy optimization > > > > > > libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++--------- > > > 1 file changed, 94 insertions(+), 25 deletions(-) > > > > > > -- > > > 2.24.1 > > > > I can see this series marked as "Changes Requested" in patchwork - is > > there anything requested other than a test for policy optimization? > > After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to > > 2") the second no longer leads to a different output (with expand size > > >=2). > > I suppose you could move it back to New. I can confirm that it no longer yields a different kernel policy. Tested-by: Stephen Smalley <sds@tycho.nsa.gov>