* [PATCH userspace v2 0/7] Remove redundant rules when building policydb
@ 2019-05-28 14:59 Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
` (6 more replies)
0 siblings, 7 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
Changes in v2:
* fix handling of dontaudit (AVTAB_DENY) rules
* switch optimization from opt-out to opt-in everywhere
* add a patch from jwcart2 that adds optimization support to
checkpolicy as well
* add two RFC modifications (see log messages for details):
* one improves the optimization to detect also rules covered by the
union of two or more other rules (on permission set level)
* the other one drops libsemanage/semodule run-time enabling/
disabling of optimization in favor of a global config option
v1: https://lore.kernel.org/selinux/20190523102449.9621-1-omosnace@redhat.com/T/
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 the type attribute hierarchy.
Since the optimization might not always be useful (e.g. when care is
taken to not have redundant rules or when the attributes are
aggressively expanded) and might even drastically increase policy build
times under some cicumstances (for example with the DSSP standard policy
[1]), the optimization is applied only when requested explictly.
The optimization routine eliminates:
* all allow/dontaudit/auditallow(/neverallow) 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.
Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/537683392
Tested:
* live on my Fedora 29 devel machine under normal use (no unusual AVCs
observed with the optimized policy loaded)
* using: https://gitlab.com/omos/selinux-misc/blob/master/opt_test.sh
* tests also xperm rules
* doesn't test conditionals (yet)
[1] https://github.com/DefenSec/dssp2-standard
James Carter (1):
checkpolicy: add flag to enable policy optimization
Ondrej Mosnacek (6):
libsepol: add a function to optimize kernel policy
libsemanage: optionally optimize policy on rebuild
semodule: add flag to enable policy optimization
secilc: add flag to enable policy optimization
[RFC] lisepol: slightly more thorough optimization
[RFC] libsemanage: switch to config file entry
checkpolicy/checkpolicy.c | 16 +-
libsemanage/src/conf-parse.y | 15 +-
libsemanage/src/conf-scan.l | 1 +
libsemanage/src/direct_api.c | 7 +
libsemanage/src/semanage_conf.h | 1 +
libsepol/include/sepol/policydb.h | 5 +
libsepol/include/sepol/policydb/policydb.h | 2 +
libsepol/src/libsepol.map.in | 5 +
libsepol/src/optimize.c | 376 +++++++++++++++++++++
libsepol/src/policydb_public.c | 5 +
secilc/secilc.c | 16 +-
11 files changed, 445 insertions(+), 4 deletions(-)
create mode 100644 libsepol/src/optimize.c
--
2.20.1
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-29 20:32 ` [Non-DoD Source] " jwcart2
2019-05-28 14:59 ` [PATCH userspace v2 2/7] libsemanage: optionally optimize policy on rebuild Ondrej Mosnacek
` (5 subsequent siblings)
6 siblings, 1 reply; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
Add sepol_policydb_optimize(), which checks a kernel policy for
redundant rules (i.e. those that are covered by an existing more general
rule) and removes them.
Results on Fedora 29 policy:
WITHOUT OPTIMIZATION:
# time semodule -B
real 0m21,280s
user 0m18,636s
sys 0m2,525s
$ wc -c /sys/fs/selinux/policy
8692158 /sys/fs/selinux/policy
$ seinfo (edited)
Allow: 113159
Dontaudit: 10297
Total: 123156
WITH OPTIMIZATION ENABLED:
# time semodule -B
real 0m22,825s
user 0m20,178s
sys 0m2,520s
$ wc -c /sys/fs/selinux/policy
8096158 /sys/fs/selinux/policy
$ seinfo (edited)
Allow: 66334
Dontaudit: 7480
Total: 73814
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
libsepol/include/sepol/policydb.h | 5 +
libsepol/include/sepol/policydb/policydb.h | 2 +
libsepol/src/libsepol.map.in | 5 +
libsepol/src/optimize.c | 374 +++++++++++++++++++++
libsepol/src/policydb_public.c | 5 +
5 files changed, 391 insertions(+)
create mode 100644 libsepol/src/optimize.c
diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
index 6769b913..792913dd 100644
--- a/libsepol/include/sepol/policydb.h
+++ b/libsepol/include/sepol/policydb.h
@@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
int target_platform);
+/*
+ * Optimize the policy by removing redundant rules.
+ */
+extern int sepol_policydb_optimize(sepol_policydb_t * p);
+
/*
* Read a policydb from a policy file.
* This automatically sets the type and version based on the
diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
index 591ce6e0..a279382e 100644
--- a/libsepol/include/sepol/policydb/policydb.h
+++ b/libsepol/include/sepol/policydb/policydb.h
@@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
extern int policydb_reindex_users(policydb_t * p);
+extern int policydb_optimize(policydb_t * p);
+
extern void policydb_destroy(policydb_t * p);
extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
index d879016c..6358e51f 100644
--- a/libsepol/src/libsepol.map.in
+++ b/libsepol/src/libsepol.map.in
@@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
sepol_polcap_getnum;
sepol_polcap_getname;
} LIBSEPOL_1.0;
+
+LIBSEPOL_1.2 {
+ global:
+ sepol_optimize_policy;
+} LIBSEPOL_1.1;
diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
new file mode 100644
index 00000000..b3859b6c
--- /dev/null
+++ b/libsepol/src/optimize.c
@@ -0,0 +1,374 @@
+/*
+ * Author: Ondrej Mosnacek <omosnacek@gmail.com>
+ *
+ * Copyright (C) 2019 Red Hat Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/*
+ * Binary policy optimization.
+ *
+ * Defines the policydb_optimize() function, which finds and removes
+ * redundant rules from the binary policy to reduce its size and potentially
+ * improve rule matching times. Only rules that are already covered by a
+ * more general rule are removed. The resulting policy is functionally
+ * equivalent to the original one.
+ */
+
+#include <sepol/policydb/policydb.h>
+#include <sepol/policydb/conditional.h>
+
+/* builds map: type/attribute -> {all attributes that are a superset of it} */
+static ebitmap_t *build_type_map(const policydb_t *p)
+{
+ unsigned int i, k;
+ ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
+ if (!map)
+ return NULL;
+
+ for (i = 0; i < p->p_types.nprim; i++) {
+ if (p->type_val_to_struct[i] &&
+ p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
+ if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
+ goto err;
+ } else {
+ ebitmap_t *types_i = &p->attr_type_map[i];
+
+ ebitmap_init(&map[i]);
+ for (k = 0; k < p->p_types.nprim; k++) {
+ ebitmap_t *types_k = &p->attr_type_map[k];
+
+ if (ebitmap_contains(types_k, types_i)) {
+ if (ebitmap_set_bit(&map[i], k, 1))
+ goto err;
+ }
+ }
+ }
+ }
+ return map;
+err:
+ for (k = 0; k < i; k++)
+ ebitmap_destroy(&map[i]);
+ return NULL;
+}
+
+static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
+{
+ unsigned int i;
+ for (i = 0; i < p->p_types.nprim; i++)
+ ebitmap_destroy(&type_map[i]);
+ free(type_map);
+}
+
+static int match_xperms(const uint32_t *p1, const uint32_t *p2)
+{
+ size_t i;
+
+ for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
+ if ((p2[i] & p1[i]) != p1[i])
+ return 0;
+ }
+ return 1;
+}
+
+static int match_avtab_datum(uint16_t specified,
+ const avtab_datum_t *d1, const avtab_datum_t *d2)
+{
+ /* inverse logic needed for AUDITDENY rules */
+ if (specified & AVTAB_AUDITDENY)
+ return (d1->data & d2->data) == d2->data;
+
+ if (specified & AVTAB_AV)
+ return (d2->data & d1->data) == d1->data;
+
+ if (specified & AVTAB_XPERMS) {
+ const avtab_extended_perms_t *x1 = d1->xperms;
+ const avtab_extended_perms_t *x2 = d2->xperms;
+
+ if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
+ if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
+ if (x1->driver != x2->driver)
+ return 0;
+ return match_xperms(x1->perms, x2->perms);
+ }
+ if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
+ return xperm_test(x1->driver, x2->perms);
+ } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
+ if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
+ return 0;
+
+ if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
+ return match_xperms(x1->perms, x2->perms);
+ }
+ return 0;
+ }
+ return 0;
+}
+
+/* checks if avtab contains a rule that covers the given rule */
+static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
+ const ebitmap_t *type_map)
+{
+ unsigned int i, k, s_idx, t_idx;
+ ebitmap_node_t *snode, *tnode;
+ avtab_datum_t *d1, *d2;
+ avtab_key_t key;
+
+ /* we only care about AV rules */
+ if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
+ return 0;
+
+ s_idx = entry->key.source_type - 1;
+ t_idx = entry->key.target_type - 1;
+
+ key.target_class = entry->key.target_class;
+ key.specified = entry->key.specified;
+
+ d1 = &entry->datum;
+
+ ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
+ key.source_type = i + 1;
+
+ ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
+ if (s_idx == i && t_idx == k)
+ continue;
+
+ key.target_type = k + 1;
+
+ d2 = avtab_search(tab, &key);
+ if (!d2)
+ continue;
+
+ if (match_avtab_datum(key.specified, d1, d2))
+ return 1;
+ }
+ }
+ return 0;
+}
+
+static int is_type_attr(policydb_t *p, unsigned int id)
+{
+ return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
+}
+
+static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
+{
+ unsigned int s_idx = entry->key.source_type - 1;
+ unsigned int t_idx = entry->key.target_type - 1;
+
+ return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
+}
+
+/* checks if conditional list contains a rule that covers the given rule */
+static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
+ const ebitmap_t *type_map)
+{
+ unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
+
+ /* we only care about AV rules */
+ if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
+ return 0;
+
+ s1 = e1->key.source_type - 1;
+ t1 = e1->key.target_type - 1;
+ c1 = e1->key.target_class;
+ k1 = e1->key.specified;
+
+ for (; list; list = list->next) {
+ avtab_ptr_t e2 = list->node;
+
+ s2 = e2->key.source_type - 1;
+ t2 = e2->key.target_type - 1;
+ c2 = e2->key.target_class;
+ k2 = e2->key.specified;
+
+ if (k1 != k2 || c1 != c2)
+ continue;
+
+ if (s1 == s2 && t1 == t2)
+ continue;
+ if (!ebitmap_get_bit(&type_map[s1], s2))
+ continue;
+ if (!ebitmap_get_bit(&type_map[t1], t2))
+ continue;
+
+ if (match_avtab_datum(k1, &e1->datum, &e2->datum))
+ return 1;
+ }
+ return 0;
+}
+
+static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
+{
+ avtab_t *tab = &p->te_avtab;
+ unsigned int i;
+ avtab_ptr_t *cur;
+
+ for (i = 0; i < tab->nslot; i++) {
+ cur = &tab->htable[i];
+ while (*cur) {
+ if (is_avrule_redundant(*cur, tab, type_map)) {
+ /* redundant rule -> remove it */
+ avtab_ptr_t tmp = *cur;
+
+ *cur = tmp->next;
+ if (tmp->key.specified & AVTAB_XPERMS)
+ free(tmp->datum.xperms);
+ free(tmp);
+
+ tab->nel--;
+ } else {
+ /* rule not redundant -> move to next rule */
+ cur = &(*cur)->next;
+ }
+ }
+ }
+}
+
+/* find redundant rules in (*cond) and put them into (*del) */
+static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
+ policydb_t *p, const ebitmap_t *type_map)
+{
+ cond_av_list_t **listp = cond;
+ cond_av_list_t *pcov = NULL;
+ cond_av_list_t **pcov_cur = &pcov;
+
+ /*
+ * Separate out all "potentially covering" rules (src or tgt is an attr)
+ * and move them to the end of the list. This is needed to avoid
+ * polynomial complexity when almost all rules are expanded.
+ */
+ while (*cond) {
+ if (is_avrule_with_attr((*cond)->node, p)) {
+ cond_av_list_t *tmp = *cond;
+
+ *cond = tmp->next;
+ tmp->next = pcov;
+ pcov = tmp;
+ } else {
+ cond = &(*cond)->next;
+ }
+ }
+ /* link the "potentially covering" rules to the end of the list */
+ *cond = pcov;
+
+ /* now go through the list and find the redundant rules */
+ cond = listp;
+ pcov_cur = &pcov;
+ while (*cond) {
+ /* needed because pcov itself may get deleted */
+ if (*cond == pcov)
+ pcov_cur = cond;
+ /*
+ * First check if covered by an unconditional rule, then also
+ * check if covered by another rule in the same list.
+ */
+ if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
+ is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
+ cond_av_list_t *tmp = *cond;
+
+ *cond = tmp->next;
+ tmp->next = *del;
+ *del = tmp;
+ } else {
+ cond = &(*cond)->next;
+ }
+ }
+}
+
+static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
+{
+ avtab_t *tab = &p->te_cond_avtab;
+ unsigned int i;
+ avtab_ptr_t *cur;
+ cond_node_t **cond;
+ cond_av_list_t **avcond, *del = NULL;
+
+ /* First go through all conditionals and collect redundant rules. */
+ cond = &p->cond_list;
+ while (*cond) {
+ optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
+ optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
+ /* TODO: maybe also check for rules present in both lists */
+
+ /* nothing left in both lists -> remove the whole conditional */
+ if (!(*cond)->true_list && !(*cond)->false_list) {
+ cond_node_t *cond_tmp = *cond;
+
+ *cond = cond_tmp->next;
+ cond_node_destroy(cond_tmp);
+ } else {
+ cond = &(*cond)->next;
+ }
+ }
+
+ if (!del)
+ return;
+
+ /*
+ * Now go through the whole cond_avtab and remove all rules that are
+ * found in the 'del' list.
+ */
+ for (i = 0; i < tab->nslot; i++) {
+ cur = &tab->htable[i];
+ while (*cur) {
+ int redundant = 0;
+ avcond = &del;
+ while (*avcond) {
+ if ((*avcond)->node == *cur) {
+ cond_av_list_t *cond_tmp = *avcond;
+
+ *avcond = cond_tmp->next;
+ free(cond_tmp);
+ redundant = 1;
+ break;
+ } else {
+ avcond = &(*avcond)->next;
+ }
+ }
+ if (redundant) {
+ avtab_ptr_t tmp = *cur;
+
+ *cur = tmp->next;
+ if (tmp->key.specified & AVTAB_XPERMS)
+ free(tmp->datum.xperms);
+ free(tmp);
+
+ tab->nel--;
+ } else {
+ cur = &(*cur)->next;
+ }
+ }
+ }
+}
+
+int policydb_optimize(policydb_t *p)
+{
+ ebitmap_t *type_map;
+
+ if (p->policy_type != POLICY_KERN)
+ return -1;
+
+ type_map = build_type_map(p);
+ if (!type_map)
+ return -1;
+
+ optimize_avtab(p, type_map);
+ optimize_cond_avtab(p, type_map);
+
+ destroy_type_map(p, type_map);
+ return 0;
+}
diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
index e7218423..747a43ff 100644
--- a/libsepol/src/policydb_public.c
+++ b/libsepol/src/policydb_public.c
@@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
return 0;
}
+int sepol_policydb_optimize(sepol_policydb_t * p)
+{
+ return policydb_optimize(&p->p);
+}
+
int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
{
return policydb_read(&p->p, &pf->pf, 0);
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 2/7] libsemanage: optionally optimize policy on rebuild
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 3/7] semodule: add flag to enable policy optimization Ondrej Mosnacek
` (4 subsequent siblings)
6 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
When building binary policy, optionally run it through
sepol_policydb_optimize() just before writing it out.
Add a semanage_set_optimize() function to specify whether the
optimization should be applied or not.
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
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 +++++
5 files changed, 30 insertions(+)
diff --git a/libsemanage/include/semanage/handle.h b/libsemanage/include/semanage/handle.h
index c8165900..f23be35a 100644
--- a/libsemanage/include/semanage/handle.h
+++ b/libsemanage/include/semanage/handle.h
@@ -66,6 +66,10 @@ void semanage_set_reload(semanage_handle_t * handle, int do_reload);
* 1 for yes, 0 for no (default) */
void semanage_set_rebuild(semanage_handle_t * handle, int do_rebuild);
+/* set whether to optimize the policy (remove redundancies) when built.
+ * 1 for yes, 0 for no (default) */
+void semanage_set_optimize(semanage_handle_t * handle, int do_optimize);
+
/* Fills *compiler_path with the location of the hll compiler sh->conf->compiler_directory_path
* corresponding to lang_ext.
* Upon success returns 0, -1 on error. */
diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
index c58961be..95cbee81 100644
--- a/libsemanage/src/direct_api.c
+++ b/libsemanage/src/direct_api.c
@@ -1461,6 +1461,13 @@ rebuild:
cil_db_destroy(&cildb);
+ /* Remove redundancies in binary policy if requested. */
+ if (sh->do_optimize) {
+ retval = sepol_policydb_optimize(out);
+ if (retval < 0)
+ goto cleanup;
+ }
+
/* Write the linked policy before merging local changes. */
retval = semanage_write_policydb(sh, out,
SEMANAGE_LINKED);
diff --git a/libsemanage/src/handle.c b/libsemanage/src/handle.c
index e5109aef..8f4530c2 100644
--- a/libsemanage/src/handle.c
+++ b/libsemanage/src/handle.c
@@ -88,6 +88,10 @@ semanage_handle_t *semanage_handle_create(void)
* If any changes are made, this flag is ignored */
sh->do_rebuild = 0;
+ /* By default do not optimize policy on rebuild.
+ * If the policy is not being rebuilt, this flag is ignored. */
+ sh->do_optimize = 0;
+
sh->commit_err = 0;
/* By default always reload policy after commit if SELinux is enabled. */
@@ -125,6 +129,15 @@ void semanage_set_rebuild(semanage_handle_t * sh, int do_rebuild)
return;
}
+void semanage_set_optimize(semanage_handle_t * sh, int do_optimize)
+{
+
+ assert(sh != NULL);
+
+ sh->do_optimize = do_optimize;
+ return;
+}
+
void semanage_set_reload(semanage_handle_t * sh, int do_reload)
{
diff --git a/libsemanage/src/handle.h b/libsemanage/src/handle.h
index a91907b0..b8fbf120 100644
--- a/libsemanage/src/handle.h
+++ b/libsemanage/src/handle.h
@@ -62,6 +62,7 @@ struct semanage_handle {
int is_in_transaction;
int do_reload; /* whether to reload policy after commit */
int do_rebuild; /* whether to rebuild policy if there were no changes */
+ int do_optimize; /* whether to optimize the built policy */
int commit_err; /* set by semanage_direct_commit() if there are
* any errors when building or committing the
* sandbox to kernel policy at /etc/selinux
diff --git a/libsemanage/src/libsemanage.map b/libsemanage/src/libsemanage.map
index 02036696..535bd9b5 100644
--- a/libsemanage/src/libsemanage.map
+++ b/libsemanage/src/libsemanage.map
@@ -63,3 +63,8 @@ LIBSEMANAGE_1.1 {
semanage_module_remove_key;
semanage_set_store_root;
} LIBSEMANAGE_1.0;
+
+LIBSEMANAGE_1.2 {
+ global:
+ semanage_set_optimize;
+} LIBSEMANAGE_1.1;
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 3/7] semodule: add flag to enable policy optimization
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 2/7] libsemanage: optionally optimize policy on rebuild Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 4/7] secilc: " Ondrej Mosnacek
` (3 subsequent siblings)
6 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
Add a command-line option -O/--optimize to enable policy optimization
when building kernel policy.
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
policycoreutils/semodule/semodule.c | 15 ++++++++++++---
1 file changed, 12 insertions(+), 3 deletions(-)
diff --git a/policycoreutils/semodule/semodule.c b/policycoreutils/semodule/semodule.c
index a76797f5..40314117 100644
--- a/policycoreutils/semodule/semodule.c
+++ b/policycoreutils/semodule/semodule.c
@@ -46,6 +46,7 @@ static int verbose;
static int reload;
static int no_reload;
static int build;
+static int optimize;
static int disable_dontaudit;
static int preserve_tunables;
static int ignore_module_cache;
@@ -123,9 +124,10 @@ static void usage(char *progname)
printf("usage: %s [option]... MODE...\n", progname);
printf("Manage SELinux policy modules.\n");
printf("MODES:\n");
- printf(" -R, --reload reload policy\n");
- printf(" -B, --build build and reload policy\n");
+ printf(" -R,--reload reload policy\n");
+ printf(" -B,--build build and reload policy\n");
printf(" -D,--disable_dontaudit Remove dontaudits from policy\n");
+ printf(" -O,--optimize optimize built policy\n");
printf(" -i,--install=MODULE_PKG install a new module\n");
printf(" -r,--remove=MODULE_NAME remove existing module at desired priority\n");
printf(" -l[KIND],--list-modules[=KIND] display list of installed modules\n");
@@ -191,6 +193,7 @@ static void parse_command_line(int argc, char **argv)
{"reload", 0, NULL, 'R'},
{"noreload", 0, NULL, 'n'},
{"build", 0, NULL, 'B'},
+ {"optimize", 0, NULL, 'O'},
{"disable_dontaudit", 0, NULL, 'D'},
{"preserve_tunables", 0, NULL, 'P'},
{"ignore-module-cache", 0, NULL, 'C'},
@@ -207,9 +210,10 @@ static void parse_command_line(int argc, char **argv)
verbose = 0;
reload = 0;
no_reload = 0;
+ optimize = 0;
priority = 400;
while ((i =
- getopt_long(argc, argv, "s:b:hi:l::vr:u:RnNBDCPX:e:d:p:S:E:cH", opts,
+ getopt_long(argc, argv, "s:b:hi:l::vr:u:RnNBDOCPX:e:d:p:S:E:cH", opts,
NULL)) != -1) {
switch (i) {
case 'b':
@@ -268,6 +272,9 @@ static void parse_command_line(int argc, char **argv)
case 'B':
build = 1;
break;
+ case 'O':
+ optimize = 1;
+ break;
case 'D':
disable_dontaudit = 1;
break;
@@ -738,6 +745,8 @@ cleanup_disable:
semanage_set_reload(sh, 0);
if (build)
semanage_set_rebuild(sh, 1);
+ if (optimize)
+ semanage_set_optimize(sh, 1);
if (disable_dontaudit)
semanage_set_disable_dontaudit(sh, 1);
else if (build)
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 4/7] secilc: add flag to enable policy optimization
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
` (2 preceding siblings ...)
2019-05-28 14:59 ` [PATCH userspace v2 3/7] semodule: add flag to enable policy optimization Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-28 16:32 ` Dominick Grift
2019-05-28 14:59 ` [PATCH userspace v2 5/7] checkpolicy: " Ondrej Mosnacek
` (2 subsequent siblings)
6 siblings, 1 reply; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
Add a command-line option -O/--optimize to optimize the final policydb
using sepol_policydb_optimize() before writing it out.
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
secilc/secilc.c | 16 +++++++++++++++-
1 file changed, 15 insertions(+), 1 deletion(-)
diff --git a/secilc/secilc.c b/secilc/secilc.c
index ad6862ba..26996ef9 100644
--- a/secilc/secilc.c
+++ b/secilc/secilc.c
@@ -68,6 +68,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
printf(" -G, --expand-generated Expand and remove auto-generated attributes\n");
printf(" -X, --expand-size <SIZE> Expand type attributes with fewer than <SIZE>\n");
printf(" members.\n");
+ printf(" -n, --no-optimize do not optimize final policy\n");
printf(" -v, --verbose increment verbosity level\n");
printf(" -h, --help display usage information\n");
exit(1);
@@ -97,6 +98,7 @@ int main(int argc, char *argv[])
int policyvers = POLICYDB_VERSION_MAX;
int attrs_expand_generated = 0;
int attrs_expand_size = -1;
+ int optimize_policy = 1;
int opt_char;
int opt_index = 0;
char *fc_buf = NULL;
@@ -117,12 +119,13 @@ int main(int argc, char *argv[])
{"filecontexts", required_argument, 0, 'f'},
{"expand-generated", no_argument, 0, 'G'},
{"expand-size", required_argument, 0, 'X'},
+ {"no-optimize", no_argument, 0, 'n'},
{0, 0, 0, 0}
};
int i;
while (1) {
- opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:", long_opts, &opt_index);
+ opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:n", long_opts, &opt_index);
if (opt_char == -1) {
break;
}
@@ -211,6 +214,9 @@ int main(int argc, char *argv[])
}
break;
}
+ case 'n':
+ optimize_policy = 0;
+ break;
case 'h':
usage(argv[0]);
case '?':
@@ -294,6 +300,14 @@ int main(int argc, char *argv[])
goto exit;
}
+ if (optimize_policy) {
+ rc = sepol_policydb_optimize(pdb);
+ if (rc != SEPOL_OK) {
+ fprintf(stderr, "Failed to optimize policydb\n");
+ goto exit;
+ }
+ }
+
if (output == NULL) {
int size = snprintf(NULL, 0, "policy.%d", policyvers);
output = malloc((size + 1) * sizeof(char));
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 5/7] checkpolicy: add flag to enable policy optimization
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
` (3 preceding siblings ...)
2019-05-28 14:59 ` [PATCH userspace v2 4/7] secilc: " Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 6/7] [RFC] lisepol: slightly more thorough optimization Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 7/7] [RFC] libsemanage: switch to config file entry Ondrej Mosnacek
6 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux; +Cc: James Carter
From: James Carter <jwcart2@tycho.nsa.gov>
Add the command-line option 'O' to checkpolicy to cause kernel policies
to be optimized by calling policydb_optimize() before being written out.
This option can be used on conf files and binary kernel policies, but
not when converting a conf file to CIL.
Signed-off-by: James Carter <jwcart2@tycho.nsa.gov>
[omosnace: make commit desc more consistent with the other patches]
[omosnace: fix a typo in the commit message]
[omosnace: directly use policydb_optimize() as also the rest of code already uses
other policydb_*() functions...]
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
checkpolicy/checkpolicy.c | 16 ++++++++++++++--
secilc/secilc.c | 12 ++++++------
2 files changed, 20 insertions(+), 8 deletions(-)
diff --git a/checkpolicy/checkpolicy.c b/checkpolicy/checkpolicy.c
index e0a00f7c..f928ec06 100644
--- a/checkpolicy/checkpolicy.c
+++ b/checkpolicy/checkpolicy.c
@@ -394,7 +394,7 @@ int main(int argc, char **argv)
size_t scontext_len, pathlen;
unsigned int i;
unsigned int protocol, port;
- unsigned int binary = 0, debug = 0, sort = 0, cil = 0, conf = 0;
+ unsigned int binary = 0, debug = 0, sort = 0, cil = 0, conf = 0, optimize = 0;
struct val_to_name v;
int ret, ch, fd, target = SEPOL_TARGET_SELINUX;
unsigned int nel, uret;
@@ -419,11 +419,12 @@ int main(int argc, char **argv)
{"cil", no_argument, NULL, 'C'},
{"conf",no_argument, NULL, 'F'},
{"sort", no_argument, NULL, 'S'},
+ {"optimize", no_argument, NULL, 'O'},
{"help", no_argument, NULL, 'h'},
{NULL, 0, NULL, 0}
};
- while ((ch = getopt_long(argc, argv, "o:t:dbU:MCFSVc:h", long_options, NULL)) != -1) {
+ while ((ch = getopt_long(argc, argv, "o:t:dbU:MCFSVc:Oh", long_options, NULL)) != -1) {
switch (ch) {
case 'o':
outfile = optarg;
@@ -466,6 +467,9 @@ int main(int argc, char **argv)
case 'S':
sort = 1;
break;
+ case 'O':
+ optimize = 1;
+ break;
case 'M':
mlspol = 1;
break;
@@ -625,6 +629,14 @@ int main(int argc, char **argv)
if (policydb_load_isids(&policydb, &sidtab))
exit(1);
+ if (optimize && policydbp->policy_type == POLICY_KERN) {
+ ret = policydb_optimize(policydbp);
+ if (ret) {
+ fprintf(stderr, "%s: error optimizing policy\n", argv[0]);
+ exit(1);
+ }
+ }
+
if (outfile) {
outfp = fopen(outfile, "w");
if (!outfp) {
diff --git a/secilc/secilc.c b/secilc/secilc.c
index 26996ef9..9bea3a58 100644
--- a/secilc/secilc.c
+++ b/secilc/secilc.c
@@ -68,7 +68,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
printf(" -G, --expand-generated Expand and remove auto-generated attributes\n");
printf(" -X, --expand-size <SIZE> Expand type attributes with fewer than <SIZE>\n");
printf(" members.\n");
- printf(" -n, --no-optimize do not optimize final policy\n");
+ printf(" -O, --optimize-policy optimize final policy\n");
printf(" -v, --verbose increment verbosity level\n");
printf(" -h, --help display usage information\n");
exit(1);
@@ -98,7 +98,7 @@ int main(int argc, char *argv[])
int policyvers = POLICYDB_VERSION_MAX;
int attrs_expand_generated = 0;
int attrs_expand_size = -1;
- int optimize_policy = 1;
+ int optimize_policy = 0;
int opt_char;
int opt_index = 0;
char *fc_buf = NULL;
@@ -119,13 +119,13 @@ int main(int argc, char *argv[])
{"filecontexts", required_argument, 0, 'f'},
{"expand-generated", no_argument, 0, 'G'},
{"expand-size", required_argument, 0, 'X'},
- {"no-optimize", no_argument, 0, 'n'},
+ {"optimize-policy", no_argument, 0, 'O'},
{0, 0, 0, 0}
};
int i;
while (1) {
- opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:n", long_opts, &opt_index);
+ opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNOc:GX:n", long_opts, &opt_index);
if (opt_char == -1) {
break;
}
@@ -214,8 +214,8 @@ int main(int argc, char *argv[])
}
break;
}
- case 'n':
- optimize_policy = 0;
+ case 'O':
+ optimize_policy = 1;
break;
case 'h':
usage(argv[0]);
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 6/7] [RFC] lisepol: slightly more thorough optimization
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
` (4 preceding siblings ...)
2019-05-28 14:59 ` [PATCH userspace v2 5/7] checkpolicy: " Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 7/7] [RFC] libsemanage: switch to config file entry Ondrej Mosnacek
6 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
Removes also rules that are covered only by a union of two or more
rules. There are usually only a few of such rules (if any), but there
should be almost no (policy build) perfomance cost for this.
Side effect: clears all permission bits covered by a more general rule
-> might slow down avtab lookups (only a single rule will now match each
query)
---
libsepol/src/optimize.c | 28 +++++++++++++++-------------
1 file changed, 15 insertions(+), 13 deletions(-)
diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
index b3859b6c..abb711e7 100644
--- a/libsepol/src/optimize.c
+++ b/libsepol/src/optimize.c
@@ -73,36 +73,38 @@ static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
free(type_map);
}
-static int match_xperms(const uint32_t *p1, const uint32_t *p2)
+static int process_xperms(uint32_t *p1, const uint32_t *p2)
{
size_t i;
+ int ret = 1;
for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
- if ((p2[i] & p1[i]) != p1[i])
- return 0;
+ p1[i] &= ~p2[i];
+ if (p1[i] != 0)
+ ret = 0;
}
- return 1;
+ return ret;
}
-static int match_avtab_datum(uint16_t specified,
- const avtab_datum_t *d1, const avtab_datum_t *d2)
+static int process_avtab_datum(uint16_t specified,
+ avtab_datum_t *d1, const avtab_datum_t *d2)
{
/* inverse logic needed for AUDITDENY rules */
if (specified & AVTAB_AUDITDENY)
- return (d1->data & d2->data) == d2->data;
+ return (d1->data |= ~d2->data) == 0xFFFFFFFF;
if (specified & AVTAB_AV)
- return (d2->data & d1->data) == d1->data;
+ return (d1->data &= ~d2->data) == 0;
if (specified & AVTAB_XPERMS) {
- const avtab_extended_perms_t *x1 = d1->xperms;
+ avtab_extended_perms_t *x1 = d1->xperms;
const avtab_extended_perms_t *x2 = d2->xperms;
if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
if (x1->driver != x2->driver)
return 0;
- return match_xperms(x1->perms, x2->perms);
+ return process_xperms(x1->perms, x2->perms);
}
if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
return xperm_test(x1->driver, x2->perms);
@@ -111,7 +113,7 @@ static int match_avtab_datum(uint16_t specified,
return 0;
if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
- return match_xperms(x1->perms, x2->perms);
+ return process_xperms(x1->perms, x2->perms);
}
return 0;
}
@@ -152,7 +154,7 @@ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
if (!d2)
continue;
- if (match_avtab_datum(key.specified, d1, d2))
+ if (process_avtab_datum(key.specified, d1, d2))
return 1;
}
}
@@ -205,7 +207,7 @@ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
if (!ebitmap_get_bit(&type_map[t1], t2))
continue;
- if (match_avtab_datum(k1, &e1->datum, &e2->datum))
+ if (process_avtab_datum(k1, &e1->datum, &e2->datum))
return 1;
}
return 0;
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH userspace v2 7/7] [RFC] libsemanage: switch to config file entry
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
` (5 preceding siblings ...)
2019-05-28 14:59 ` [PATCH userspace v2 6/7] [RFC] lisepol: slightly more thorough optimization Ondrej Mosnacek
@ 2019-05-28 14:59 ` Ondrej Mosnacek
6 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 14:59 UTC (permalink / raw)
To: selinux
(to be squashed with the libsemanage + semodule patches or dropped based
on feedback)
Having a global config option for optimization will make more sense if
e.g. we decide to enable it for all operations in Fedora. In such case
it would be difficult to enforce/encourage the use of -O options
everywhere (semodule, semanage, custom Python scripts, ...). There could
still be command-line options and a libsemanage function to override the
global behavior, but I'm not sure if those would be worth the added
complexity...
---
libsemanage/include/semanage/handle.h | 4 ----
libsemanage/src/conf-parse.y | 15 ++++++++++++++-
libsemanage/src/conf-scan.l | 1 +
libsemanage/src/direct_api.c | 2 +-
libsemanage/src/handle.c | 13 -------------
libsemanage/src/handle.h | 1 -
libsemanage/src/libsemanage.map | 5 -----
libsemanage/src/semanage_conf.h | 1 +
policycoreutils/semodule/semodule.c | 15 +++------------
9 files changed, 20 insertions(+), 37 deletions(-)
diff --git a/libsemanage/include/semanage/handle.h b/libsemanage/include/semanage/handle.h
index f23be35a..c8165900 100644
--- a/libsemanage/include/semanage/handle.h
+++ b/libsemanage/include/semanage/handle.h
@@ -66,10 +66,6 @@ void semanage_set_reload(semanage_handle_t * handle, int do_reload);
* 1 for yes, 0 for no (default) */
void semanage_set_rebuild(semanage_handle_t * handle, int do_rebuild);
-/* set whether to optimize the policy (remove redundancies) when built.
- * 1 for yes, 0 for no (default) */
-void semanage_set_optimize(semanage_handle_t * handle, int do_optimize);
-
/* Fills *compiler_path with the location of the hll compiler sh->conf->compiler_directory_path
* corresponding to lang_ext.
* Upon success returns 0, -1 on error. */
diff --git a/libsemanage/src/conf-parse.y b/libsemanage/src/conf-parse.y
index b527e893..9bf9364a 100644
--- a/libsemanage/src/conf-parse.y
+++ b/libsemanage/src/conf-parse.y
@@ -59,7 +59,7 @@ static int parse_errors;
char *s;
}
-%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT
+%token MODULE_STORE VERSION EXPAND_CHECK FILE_MODE SAVE_PREVIOUS SAVE_LINKED TARGET_PLATFORM COMPILER_DIR IGNORE_MODULE_CACHE STORE_ROOT OPTIMIZE_POLICY
%token LOAD_POLICY_START SETFILES_START SEFCONTEXT_COMPILE_START DISABLE_GENHOMEDIRCON HANDLE_UNKNOWN USEPASSWD IGNOREDIRS
%token BZIP_BLOCKSIZE BZIP_SMALL REMOVE_HLL
%token VERIFY_MOD_START VERIFY_LINKED_START VERIFY_KERNEL_START BLOCK_END
@@ -95,6 +95,7 @@ single_opt: module_store
| bzip_blocksize
| bzip_small
| remove_hll
+ | optimize_policy
;
module_store: MODULE_STORE '=' ARG {
@@ -268,6 +269,17 @@ remove_hll: REMOVE_HLL'=' ARG {
free($3);
}
+optimize_policy: OPTIMIZE_POLICY '=' ARG {
+ if (strcasecmp($3, "false") == 0) {
+ current_conf->optimize_policy = 0;
+ } else if (strcasecmp($3, "true") == 0) {
+ current_conf->optimize_policy = 1;
+ } else {
+ yyerror("optimize-policy can only be 'true' or 'false'");
+ }
+ free($3);
+}
+
command_block:
command_start external_opts BLOCK_END {
if (new_external->path == NULL) {
@@ -352,6 +364,7 @@ static int semanage_conf_init(semanage_conf_t * conf)
conf->bzip_small = 0;
conf->ignore_module_cache = 0;
conf->remove_hll = 0;
+ conf->optimize_policy = 0;
conf->save_previous = 0;
conf->save_linked = 0;
diff --git a/libsemanage/src/conf-scan.l b/libsemanage/src/conf-scan.l
index 607bbf0b..b06a896c 100644
--- a/libsemanage/src/conf-scan.l
+++ b/libsemanage/src/conf-scan.l
@@ -54,6 +54,7 @@ handle-unknown return HANDLE_UNKNOWN;
bzip-blocksize return BZIP_BLOCKSIZE;
bzip-small return BZIP_SMALL;
remove-hll return REMOVE_HLL;
+optimize-policy return OPTIMIZE_POLICY;
"[load_policy]" return LOAD_POLICY_START;
"[setfiles]" return SETFILES_START;
"[sefcontext_compile]" return SEFCONTEXT_COMPILE_START;
diff --git a/libsemanage/src/direct_api.c b/libsemanage/src/direct_api.c
index 95cbee81..0153091f 100644
--- a/libsemanage/src/direct_api.c
+++ b/libsemanage/src/direct_api.c
@@ -1462,7 +1462,7 @@ rebuild:
cil_db_destroy(&cildb);
/* Remove redundancies in binary policy if requested. */
- if (sh->do_optimize) {
+ if (sh->conf->optimize_policy) {
retval = sepol_policydb_optimize(out);
if (retval < 0)
goto cleanup;
diff --git a/libsemanage/src/handle.c b/libsemanage/src/handle.c
index 8f4530c2..e5109aef 100644
--- a/libsemanage/src/handle.c
+++ b/libsemanage/src/handle.c
@@ -88,10 +88,6 @@ semanage_handle_t *semanage_handle_create(void)
* If any changes are made, this flag is ignored */
sh->do_rebuild = 0;
- /* By default do not optimize policy on rebuild.
- * If the policy is not being rebuilt, this flag is ignored. */
- sh->do_optimize = 0;
-
sh->commit_err = 0;
/* By default always reload policy after commit if SELinux is enabled. */
@@ -129,15 +125,6 @@ void semanage_set_rebuild(semanage_handle_t * sh, int do_rebuild)
return;
}
-void semanage_set_optimize(semanage_handle_t * sh, int do_optimize)
-{
-
- assert(sh != NULL);
-
- sh->do_optimize = do_optimize;
- return;
-}
-
void semanage_set_reload(semanage_handle_t * sh, int do_reload)
{
diff --git a/libsemanage/src/handle.h b/libsemanage/src/handle.h
index b8fbf120..a91907b0 100644
--- a/libsemanage/src/handle.h
+++ b/libsemanage/src/handle.h
@@ -62,7 +62,6 @@ struct semanage_handle {
int is_in_transaction;
int do_reload; /* whether to reload policy after commit */
int do_rebuild; /* whether to rebuild policy if there were no changes */
- int do_optimize; /* whether to optimize the built policy */
int commit_err; /* set by semanage_direct_commit() if there are
* any errors when building or committing the
* sandbox to kernel policy at /etc/selinux
diff --git a/libsemanage/src/libsemanage.map b/libsemanage/src/libsemanage.map
index 535bd9b5..02036696 100644
--- a/libsemanage/src/libsemanage.map
+++ b/libsemanage/src/libsemanage.map
@@ -63,8 +63,3 @@ LIBSEMANAGE_1.1 {
semanage_module_remove_key;
semanage_set_store_root;
} LIBSEMANAGE_1.0;
-
-LIBSEMANAGE_1.2 {
- global:
- semanage_set_optimize;
-} LIBSEMANAGE_1.1;
diff --git a/libsemanage/src/semanage_conf.h b/libsemanage/src/semanage_conf.h
index c99ac8c7..23c4b8b4 100644
--- a/libsemanage/src/semanage_conf.h
+++ b/libsemanage/src/semanage_conf.h
@@ -47,6 +47,7 @@ typedef struct semanage_conf {
int bzip_small;
int remove_hll;
int ignore_module_cache;
+ int optimize_policy;
char *ignoredirs; /* ";" separated of list for genhomedircon to ignore */
struct external_prog *load_policy;
struct external_prog *setfiles;
diff --git a/policycoreutils/semodule/semodule.c b/policycoreutils/semodule/semodule.c
index 40314117..a76797f5 100644
--- a/policycoreutils/semodule/semodule.c
+++ b/policycoreutils/semodule/semodule.c
@@ -46,7 +46,6 @@ static int verbose;
static int reload;
static int no_reload;
static int build;
-static int optimize;
static int disable_dontaudit;
static int preserve_tunables;
static int ignore_module_cache;
@@ -124,10 +123,9 @@ static void usage(char *progname)
printf("usage: %s [option]... MODE...\n", progname);
printf("Manage SELinux policy modules.\n");
printf("MODES:\n");
- printf(" -R,--reload reload policy\n");
- printf(" -B,--build build and reload policy\n");
+ printf(" -R, --reload reload policy\n");
+ printf(" -B, --build build and reload policy\n");
printf(" -D,--disable_dontaudit Remove dontaudits from policy\n");
- printf(" -O,--optimize optimize built policy\n");
printf(" -i,--install=MODULE_PKG install a new module\n");
printf(" -r,--remove=MODULE_NAME remove existing module at desired priority\n");
printf(" -l[KIND],--list-modules[=KIND] display list of installed modules\n");
@@ -193,7 +191,6 @@ static void parse_command_line(int argc, char **argv)
{"reload", 0, NULL, 'R'},
{"noreload", 0, NULL, 'n'},
{"build", 0, NULL, 'B'},
- {"optimize", 0, NULL, 'O'},
{"disable_dontaudit", 0, NULL, 'D'},
{"preserve_tunables", 0, NULL, 'P'},
{"ignore-module-cache", 0, NULL, 'C'},
@@ -210,10 +207,9 @@ static void parse_command_line(int argc, char **argv)
verbose = 0;
reload = 0;
no_reload = 0;
- optimize = 0;
priority = 400;
while ((i =
- getopt_long(argc, argv, "s:b:hi:l::vr:u:RnNBDOCPX:e:d:p:S:E:cH", opts,
+ getopt_long(argc, argv, "s:b:hi:l::vr:u:RnNBDCPX:e:d:p:S:E:cH", opts,
NULL)) != -1) {
switch (i) {
case 'b':
@@ -272,9 +268,6 @@ static void parse_command_line(int argc, char **argv)
case 'B':
build = 1;
break;
- case 'O':
- optimize = 1;
- break;
case 'D':
disable_dontaudit = 1;
break;
@@ -745,8 +738,6 @@ cleanup_disable:
semanage_set_reload(sh, 0);
if (build)
semanage_set_rebuild(sh, 1);
- if (optimize)
- semanage_set_optimize(sh, 1);
if (disable_dontaudit)
semanage_set_disable_dontaudit(sh, 1);
else if (build)
--
2.20.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH userspace v2 4/7] secilc: add flag to enable policy optimization
2019-05-28 14:59 ` [PATCH userspace v2 4/7] secilc: " Ondrej Mosnacek
@ 2019-05-28 16:32 ` Dominick Grift
2019-05-28 17:01 ` Ondrej Mosnacek
0 siblings, 1 reply; 14+ messages in thread
From: Dominick Grift @ 2019-05-28 16:32 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: selinux
[-- Attachment #1: Type: text/plain, Size: 2755 bytes --]
On Tue, May 28, 2019 at 04:59:09PM +0200, Ondrej Mosnacek wrote:
> Add a command-line option -O/--optimize to optimize the final policydb
> using sepol_policydb_optimize() before writing it out.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
> secilc/secilc.c | 16 +++++++++++++++-
> 1 file changed, 15 insertions(+), 1 deletion(-)
>
> diff --git a/secilc/secilc.c b/secilc/secilc.c
> index ad6862ba..26996ef9 100644
> --- a/secilc/secilc.c
> +++ b/secilc/secilc.c
> @@ -68,6 +68,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
> printf(" -G, --expand-generated Expand and remove auto-generated attributes\n");
> printf(" -X, --expand-size <SIZE> Expand type attributes with fewer than <SIZE>\n");
> printf(" members.\n");
> + printf(" -n, --no-optimize do not optimize final policy\n");
I think something may have gone wrong here.
> printf(" -v, --verbose increment verbosity level\n");
> printf(" -h, --help display usage information\n");
> exit(1);
> @@ -97,6 +98,7 @@ int main(int argc, char *argv[])
> int policyvers = POLICYDB_VERSION_MAX;
> int attrs_expand_generated = 0;
> int attrs_expand_size = -1;
> + int optimize_policy = 1;
> int opt_char;
> int opt_index = 0;
> char *fc_buf = NULL;
> @@ -117,12 +119,13 @@ int main(int argc, char *argv[])
> {"filecontexts", required_argument, 0, 'f'},
> {"expand-generated", no_argument, 0, 'G'},
> {"expand-size", required_argument, 0, 'X'},
> + {"no-optimize", no_argument, 0, 'n'},
> {0, 0, 0, 0}
> };
> int i;
>
> while (1) {
> - opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:", long_opts, &opt_index);
> + opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:n", long_opts, &opt_index);
> if (opt_char == -1) {
> break;
> }
> @@ -211,6 +214,9 @@ int main(int argc, char *argv[])
> }
> break;
> }
> + case 'n':
> + optimize_policy = 0;
> + break;
> case 'h':
> usage(argv[0]);
> case '?':
> @@ -294,6 +300,14 @@ int main(int argc, char *argv[])
> goto exit;
> }
>
> + if (optimize_policy) {
> + rc = sepol_policydb_optimize(pdb);
> + if (rc != SEPOL_OK) {
> + fprintf(stderr, "Failed to optimize policydb\n");
> + goto exit;
> + }
> + }
> +
> if (output == NULL) {
> int size = snprintf(NULL, 0, "policy.%d", policyvers);
> output = malloc((size + 1) * sizeof(char));
> --
> 2.20.1
>
--
Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
Dominick Grift
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH userspace v2 4/7] secilc: add flag to enable policy optimization
2019-05-28 16:32 ` Dominick Grift
@ 2019-05-28 17:01 ` Ondrej Mosnacek
0 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-28 17:01 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux
On Tue, May 28, 2019 at 6:32 PM Dominick Grift <dac.override@gmail.com> wrote:
>
> On Tue, May 28, 2019 at 04:59:09PM +0200, Ondrej Mosnacek wrote:
> > Add a command-line option -O/--optimize to optimize the final policydb
> > using sepol_policydb_optimize() before writing it out.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> > secilc/secilc.c | 16 +++++++++++++++-
> > 1 file changed, 15 insertions(+), 1 deletion(-)
> >
> > diff --git a/secilc/secilc.c b/secilc/secilc.c
> > index ad6862ba..26996ef9 100644
> > --- a/secilc/secilc.c
> > +++ b/secilc/secilc.c
> > @@ -68,6 +68,7 @@ static __attribute__((__noreturn__)) void usage(const char *prog)
> > printf(" -G, --expand-generated Expand and remove auto-generated attributes\n");
> > printf(" -X, --expand-size <SIZE> Expand type attributes with fewer than <SIZE>\n");
> > printf(" members.\n");
> > + printf(" -n, --no-optimize do not optimize final policy\n");
>
> I think something may have gone wrong here.
Ouch, you're right, I accidentally squashed the conversion into the
wrong patch (5/7). Will fix it up tomorrow.
>
> > printf(" -v, --verbose increment verbosity level\n");
> > printf(" -h, --help display usage information\n");
> > exit(1);
> > @@ -97,6 +98,7 @@ int main(int argc, char *argv[])
> > int policyvers = POLICYDB_VERSION_MAX;
> > int attrs_expand_generated = 0;
> > int attrs_expand_size = -1;
> > + int optimize_policy = 1;
> > int opt_char;
> > int opt_index = 0;
> > char *fc_buf = NULL;
> > @@ -117,12 +119,13 @@ int main(int argc, char *argv[])
> > {"filecontexts", required_argument, 0, 'f'},
> > {"expand-generated", no_argument, 0, 'G'},
> > {"expand-size", required_argument, 0, 'X'},
> > + {"no-optimize", no_argument, 0, 'n'},
> > {0, 0, 0, 0}
> > };
> > int i;
> >
> > while (1) {
> > - opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:", long_opts, &opt_index);
> > + opt_char = getopt_long(argc, argv, "o:f:U:hvt:M:PDmNc:GX:n", long_opts, &opt_index);
> > if (opt_char == -1) {
> > break;
> > }
> > @@ -211,6 +214,9 @@ int main(int argc, char *argv[])
> > }
> > break;
> > }
> > + case 'n':
> > + optimize_policy = 0;
> > + break;
> > case 'h':
> > usage(argv[0]);
> > case '?':
> > @@ -294,6 +300,14 @@ int main(int argc, char *argv[])
> > goto exit;
> > }
> >
> > + if (optimize_policy) {
> > + rc = sepol_policydb_optimize(pdb);
> > + if (rc != SEPOL_OK) {
> > + fprintf(stderr, "Failed to optimize policydb\n");
> > + goto exit;
> > + }
> > + }
> > +
> > if (output == NULL) {
> > int size = snprintf(NULL, 0, "policy.%d", policyvers);
> > output = malloc((size + 1) * sizeof(char));
> > --
> > 2.20.1
> >
>
> --
> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> Dominick Grift
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Non-DoD Source] [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy
2019-05-28 14:59 ` [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
@ 2019-05-29 20:32 ` jwcart2
2019-05-30 11:46 ` Ondrej Mosnacek
0 siblings, 1 reply; 14+ messages in thread
From: jwcart2 @ 2019-05-29 20:32 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux
On 5/28/19 10:59 AM, Ondrej Mosnacek wrote:
> Add sepol_policydb_optimize(), which checks a kernel policy for
> redundant rules (i.e. those that are covered by an existing more general
> rule) and removes them.
>
> Results on Fedora 29 policy:
>
> WITHOUT OPTIMIZATION:
> # time semodule -B
> real 0m21,280s
> user 0m18,636s
> sys 0m2,525s
>
> $ wc -c /sys/fs/selinux/policy
> 8692158 /sys/fs/selinux/policy
>
> $ seinfo (edited)
> Allow: 113159
> Dontaudit: 10297
> Total: 123156
>
> WITH OPTIMIZATION ENABLED:
> # time semodule -B
> real 0m22,825s
> user 0m20,178s
> sys 0m2,520s
>
> $ wc -c /sys/fs/selinux/policy
> 8096158 /sys/fs/selinux/policy
>
> $ seinfo (edited)
> Allow: 66334
> Dontaudit: 7480
> Total: 73814
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
> libsepol/include/sepol/policydb.h | 5 +
> libsepol/include/sepol/policydb/policydb.h | 2 +
> libsepol/src/libsepol.map.in | 5 +
> libsepol/src/optimize.c | 374 +++++++++++++++++++++
> libsepol/src/policydb_public.c | 5 +
> 5 files changed, 391 insertions(+)
> create mode 100644 libsepol/src/optimize.c
>
> diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
> index 6769b913..792913dd 100644
> --- a/libsepol/include/sepol/policydb.h
> +++ b/libsepol/include/sepol/policydb.h
> @@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
> extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
> int target_platform);
>
> +/*
> + * Optimize the policy by removing redundant rules.
> + */
> +extern int sepol_policydb_optimize(sepol_policydb_t * p);
> +
> /*
> * Read a policydb from a policy file.
> * This automatically sets the type and version based on the
> diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
> index 591ce6e0..a279382e 100644
> --- a/libsepol/include/sepol/policydb/policydb.h
> +++ b/libsepol/include/sepol/policydb/policydb.h
> @@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
>
> extern int policydb_reindex_users(policydb_t * p);
>
> +extern int policydb_optimize(policydb_t * p);
> +
> extern void policydb_destroy(policydb_t * p);
>
> extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
> diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
> index d879016c..6358e51f 100644
> --- a/libsepol/src/libsepol.map.in
> +++ b/libsepol/src/libsepol.map.in
> @@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
> sepol_polcap_getnum;
> sepol_polcap_getname;
> } LIBSEPOL_1.0;
> +
> +LIBSEPOL_1.2 {
> + global:
> + sepol_optimize_policy;
> +} LIBSEPOL_1.1;
> diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> new file mode 100644
> index 00000000..b3859b6c
> --- /dev/null
> +++ b/libsepol/src/optimize.c
> @@ -0,0 +1,374 @@
> +/*
> + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
> + *
> + * Copyright (C) 2019 Red Hat Inc.
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +/*
> + * Binary policy optimization.
> + *
> + * Defines the policydb_optimize() function, which finds and removes
> + * redundant rules from the binary policy to reduce its size and potentially
> + * improve rule matching times. Only rules that are already covered by a
> + * more general rule are removed. The resulting policy is functionally
> + * equivalent to the original one.
> + */
> +
> +#include <sepol/policydb/policydb.h>
> +#include <sepol/policydb/conditional.h>
> +
> +/* builds map: type/attribute -> {all attributes that are a superset of it} */
> +static ebitmap_t *build_type_map(const policydb_t *p)
> +{
> + unsigned int i, k;
> + ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
> + if (!map)
> + return NULL;
> +
> + for (i = 0; i < p->p_types.nprim; i++) {
> + if (p->type_val_to_struct[i] &&
> + p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
> + if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
> + goto err;
> + } else {
> + ebitmap_t *types_i = &p->attr_type_map[i];
> +
> + ebitmap_init(&map[i]);
> + for (k = 0; k < p->p_types.nprim; k++) {
> + ebitmap_t *types_k = &p->attr_type_map[k];
> +
> + if (ebitmap_contains(types_k, types_i)) {
> + if (ebitmap_set_bit(&map[i], k, 1))
> + goto err;
> + }
> + }
> + }
> + }
> + return map;
> +err:
> + for (k = 0; k < i; k++)
> + ebitmap_destroy(&map[i]);
Should be &map[k]
If ebitmap_set_bit() fails then you need to ebitmap_destroy the ith map, so it
should be k <= i in the for loop.
Still looking through this series. It does seem to produce the correct results.
Jim
> + return NULL;
> +}
> +
> +static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
> +{
> + unsigned int i;
> + for (i = 0; i < p->p_types.nprim; i++)
> + ebitmap_destroy(&type_map[i]);
> + free(type_map);
> +}
> +
> +static int match_xperms(const uint32_t *p1, const uint32_t *p2)
> +{
> + size_t i;
> +
> + for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
> + if ((p2[i] & p1[i]) != p1[i])
> + return 0;
> + }
> + return 1;
> +}
> +
> +static int match_avtab_datum(uint16_t specified,
> + const avtab_datum_t *d1, const avtab_datum_t *d2)
> +{
> + /* inverse logic needed for AUDITDENY rules */
> + if (specified & AVTAB_AUDITDENY)
> + return (d1->data & d2->data) == d2->data;
> +
> + if (specified & AVTAB_AV)
> + return (d2->data & d1->data) == d1->data;
> +
> + if (specified & AVTAB_XPERMS) {
> + const avtab_extended_perms_t *x1 = d1->xperms;
> + const avtab_extended_perms_t *x2 = d2->xperms;
> +
> + if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> + if (x1->driver != x2->driver)
> + return 0;
> + return match_xperms(x1->perms, x2->perms);
> + }
> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> + return xperm_test(x1->driver, x2->perms);
> + } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
> + return 0;
> +
> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> + return match_xperms(x1->perms, x2->perms);
> + }
> + return 0;
> + }
> + return 0;
> +}
> +
> +/* checks if avtab contains a rule that covers the given rule */
> +static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
> + const ebitmap_t *type_map)
> +{
> + unsigned int i, k, s_idx, t_idx;
> + ebitmap_node_t *snode, *tnode;
> + avtab_datum_t *d1, *d2;
> + avtab_key_t key;
> +
> + /* we only care about AV rules */
> + if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> + return 0;
> +
> + s_idx = entry->key.source_type - 1;
> + t_idx = entry->key.target_type - 1;
> +
> + key.target_class = entry->key.target_class;
> + key.specified = entry->key.specified;
> +
> + d1 = &entry->datum;
> +
> + ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
> + key.source_type = i + 1;
> +
> + ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
> + if (s_idx == i && t_idx == k)
> + continue;
> +
> + key.target_type = k + 1;
> +
> + d2 = avtab_search(tab, &key);
> + if (!d2)
> + continue;
> +
> + if (match_avtab_datum(key.specified, d1, d2))
> + return 1;
> + }
> + }
> + return 0;
> +}
> +
> +static int is_type_attr(policydb_t *p, unsigned int id)
> +{
> + return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
> +}
> +
> +static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
> +{
> + unsigned int s_idx = entry->key.source_type - 1;
> + unsigned int t_idx = entry->key.target_type - 1;
> +
> + return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
> +}
> +
> +/* checks if conditional list contains a rule that covers the given rule */
> +static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
> + const ebitmap_t *type_map)
> +{
> + unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
> +
> + /* we only care about AV rules */
> + if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> + return 0;
> +
> + s1 = e1->key.source_type - 1;
> + t1 = e1->key.target_type - 1;
> + c1 = e1->key.target_class;
> + k1 = e1->key.specified;
> +
> + for (; list; list = list->next) {
> + avtab_ptr_t e2 = list->node;
> +
> + s2 = e2->key.source_type - 1;
> + t2 = e2->key.target_type - 1;
> + c2 = e2->key.target_class;
> + k2 = e2->key.specified;
> +
> + if (k1 != k2 || c1 != c2)
> + continue;
> +
> + if (s1 == s2 && t1 == t2)
> + continue;
> + if (!ebitmap_get_bit(&type_map[s1], s2))
> + continue;
> + if (!ebitmap_get_bit(&type_map[t1], t2))
> + continue;
> +
> + if (match_avtab_datum(k1, &e1->datum, &e2->datum))
> + return 1;
> + }
> + return 0;
> +}
> +
> +static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
> +{
> + avtab_t *tab = &p->te_avtab;
> + unsigned int i;
> + avtab_ptr_t *cur;
> +
> + for (i = 0; i < tab->nslot; i++) {
> + cur = &tab->htable[i];
> + while (*cur) {
> + if (is_avrule_redundant(*cur, tab, type_map)) {
> + /* redundant rule -> remove it */
> + avtab_ptr_t tmp = *cur;
> +
> + *cur = tmp->next;
> + if (tmp->key.specified & AVTAB_XPERMS)
> + free(tmp->datum.xperms);
> + free(tmp);
> +
> + tab->nel--;
> + } else {
> + /* rule not redundant -> move to next rule */
> + cur = &(*cur)->next;
> + }
> + }
> + }
> +}
> +
> +/* find redundant rules in (*cond) and put them into (*del) */
> +static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
> + policydb_t *p, const ebitmap_t *type_map)
> +{
> + cond_av_list_t **listp = cond;
> + cond_av_list_t *pcov = NULL;
> + cond_av_list_t **pcov_cur = &pcov;
> +
> + /*
> + * Separate out all "potentially covering" rules (src or tgt is an attr)
> + * and move them to the end of the list. This is needed to avoid
> + * polynomial complexity when almost all rules are expanded.
> + */
> + while (*cond) {
> + if (is_avrule_with_attr((*cond)->node, p)) {
> + cond_av_list_t *tmp = *cond;
> +
> + *cond = tmp->next;
> + tmp->next = pcov;
> + pcov = tmp;
> + } else {
> + cond = &(*cond)->next;
> + }
> + }
> + /* link the "potentially covering" rules to the end of the list */
> + *cond = pcov;
> +
> + /* now go through the list and find the redundant rules */
> + cond = listp;
> + pcov_cur = &pcov;
> + while (*cond) {
> + /* needed because pcov itself may get deleted */
> + if (*cond == pcov)
> + pcov_cur = cond;
> + /*
> + * First check if covered by an unconditional rule, then also
> + * check if covered by another rule in the same list.
> + */
> + if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
> + is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
> + cond_av_list_t *tmp = *cond;
> +
> + *cond = tmp->next;
> + tmp->next = *del;
> + *del = tmp;
> + } else {
> + cond = &(*cond)->next;
> + }
> + }
> +}
> +
> +static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
> +{
> + avtab_t *tab = &p->te_cond_avtab;
> + unsigned int i;
> + avtab_ptr_t *cur;
> + cond_node_t **cond;
> + cond_av_list_t **avcond, *del = NULL;
> +
> + /* First go through all conditionals and collect redundant rules. */
> + cond = &p->cond_list;
> + while (*cond) {
> + optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
> + optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
> + /* TODO: maybe also check for rules present in both lists */
> +
> + /* nothing left in both lists -> remove the whole conditional */
> + if (!(*cond)->true_list && !(*cond)->false_list) {
> + cond_node_t *cond_tmp = *cond;
> +
> + *cond = cond_tmp->next;
> + cond_node_destroy(cond_tmp);
> + } else {
> + cond = &(*cond)->next;
> + }
> + }
> +
> + if (!del)
> + return;
> +
> + /*
> + * Now go through the whole cond_avtab and remove all rules that are
> + * found in the 'del' list.
> + */
> + for (i = 0; i < tab->nslot; i++) {
> + cur = &tab->htable[i];
> + while (*cur) {
> + int redundant = 0;
> + avcond = &del;
> + while (*avcond) {
> + if ((*avcond)->node == *cur) {
> + cond_av_list_t *cond_tmp = *avcond;
> +
> + *avcond = cond_tmp->next;
> + free(cond_tmp);
> + redundant = 1;
> + break;
> + } else {
> + avcond = &(*avcond)->next;
> + }
> + }
> + if (redundant) {
> + avtab_ptr_t tmp = *cur;
> +
> + *cur = tmp->next;
> + if (tmp->key.specified & AVTAB_XPERMS)
> + free(tmp->datum.xperms);
> + free(tmp);
> +
> + tab->nel--;
> + } else {
> + cur = &(*cur)->next;
> + }
> + }
> + }
> +}
> +
> +int policydb_optimize(policydb_t *p)
> +{
> + ebitmap_t *type_map;
> +
> + if (p->policy_type != POLICY_KERN)
> + return -1;
> +
> + type_map = build_type_map(p);
> + if (!type_map)
> + return -1;
> +
> + optimize_avtab(p, type_map);
> + optimize_cond_avtab(p, type_map);
> +
> + destroy_type_map(p, type_map);
> + return 0;
> +}
> diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
> index e7218423..747a43ff 100644
> --- a/libsepol/src/policydb_public.c
> +++ b/libsepol/src/policydb_public.c
> @@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
> return 0;
> }
>
> +int sepol_policydb_optimize(sepol_policydb_t * p)
> +{
> + return policydb_optimize(&p->p);
> +}
> +
> int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
> {
> return policydb_read(&p->p, &pf->pf, 0);
>
--
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [Non-DoD Source] [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy
2019-05-29 20:32 ` [Non-DoD Source] " jwcart2
@ 2019-05-30 11:46 ` Ondrej Mosnacek
2019-05-30 16:55 ` Stephen Smalley
0 siblings, 1 reply; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-30 11:46 UTC (permalink / raw)
To: jwcart2; +Cc: selinux
On Wed, May 29, 2019 at 10:32 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/28/19 10:59 AM, Ondrej Mosnacek wrote:
> > Add sepol_policydb_optimize(), which checks a kernel policy for
> > redundant rules (i.e. those that are covered by an existing more general
> > rule) and removes them.
> >
> > Results on Fedora 29 policy:
> >
> > WITHOUT OPTIMIZATION:
> > # time semodule -B
> > real 0m21,280s
> > user 0m18,636s
> > sys 0m2,525s
> >
> > $ wc -c /sys/fs/selinux/policy
> > 8692158 /sys/fs/selinux/policy
> >
> > $ seinfo (edited)
> > Allow: 113159
> > Dontaudit: 10297
> > Total: 123156
> >
> > WITH OPTIMIZATION ENABLED:
> > # time semodule -B
> > real 0m22,825s
> > user 0m20,178s
> > sys 0m2,520s
> >
> > $ wc -c /sys/fs/selinux/policy
> > 8096158 /sys/fs/selinux/policy
> >
> > $ seinfo (edited)
> > Allow: 66334
> > Dontaudit: 7480
> > Total: 73814
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> > libsepol/include/sepol/policydb.h | 5 +
> > libsepol/include/sepol/policydb/policydb.h | 2 +
> > libsepol/src/libsepol.map.in | 5 +
> > libsepol/src/optimize.c | 374 +++++++++++++++++++++
> > libsepol/src/policydb_public.c | 5 +
> > 5 files changed, 391 insertions(+)
> > create mode 100644 libsepol/src/optimize.c
> >
> > diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
> > index 6769b913..792913dd 100644
> > --- a/libsepol/include/sepol/policydb.h
> > +++ b/libsepol/include/sepol/policydb.h
> > @@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
> > extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
> > int target_platform);
> >
> > +/*
> > + * Optimize the policy by removing redundant rules.
> > + */
> > +extern int sepol_policydb_optimize(sepol_policydb_t * p);
> > +
> > /*
> > * Read a policydb from a policy file.
> > * This automatically sets the type and version based on the
> > diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
> > index 591ce6e0..a279382e 100644
> > --- a/libsepol/include/sepol/policydb/policydb.h
> > +++ b/libsepol/include/sepol/policydb/policydb.h
> > @@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
> >
> > extern int policydb_reindex_users(policydb_t * p);
> >
> > +extern int policydb_optimize(policydb_t * p);
> > +
> > extern void policydb_destroy(policydb_t * p);
> >
> > extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
> > diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
> > index d879016c..6358e51f 100644
> > --- a/libsepol/src/libsepol.map.in
> > +++ b/libsepol/src/libsepol.map.in
> > @@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
> > sepol_polcap_getnum;
> > sepol_polcap_getname;
> > } LIBSEPOL_1.0;
> > +
> > +LIBSEPOL_1.2 {
> > + global:
> > + sepol_optimize_policy;
> > +} LIBSEPOL_1.1;
> > diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> > new file mode 100644
> > index 00000000..b3859b6c
> > --- /dev/null
> > +++ b/libsepol/src/optimize.c
> > @@ -0,0 +1,374 @@
> > +/*
> > + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
> > + *
> > + * Copyright (C) 2019 Red Hat Inc.
> > + *
> > + * This library is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU Lesser General Public
> > + * License as published by the Free Software Foundation; either
> > + * version 2.1 of the License, or (at your option) any later version.
> > + *
> > + * This library is distributed in the hope that it will be useful,
> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> > + * Lesser General Public License for more details.
> > + *
> > + * You should have received a copy of the GNU Lesser General Public
> > + * License along with this library; if not, write to the Free Software
> > + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
> > + */
> > +
> > +/*
> > + * Binary policy optimization.
> > + *
> > + * Defines the policydb_optimize() function, which finds and removes
> > + * redundant rules from the binary policy to reduce its size and potentially
> > + * improve rule matching times. Only rules that are already covered by a
> > + * more general rule are removed. The resulting policy is functionally
> > + * equivalent to the original one.
> > + */
> > +
> > +#include <sepol/policydb/policydb.h>
> > +#include <sepol/policydb/conditional.h>
> > +
> > +/* builds map: type/attribute -> {all attributes that are a superset of it} */
> > +static ebitmap_t *build_type_map(const policydb_t *p)
> > +{
> > + unsigned int i, k;
> > + ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
> > + if (!map)
> > + return NULL;
> > +
> > + for (i = 0; i < p->p_types.nprim; i++) {
> > + if (p->type_val_to_struct[i] &&
> > + p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
> > + if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
> > + goto err;
> > + } else {
> > + ebitmap_t *types_i = &p->attr_type_map[i];
> > +
> > + ebitmap_init(&map[i]);
> > + for (k = 0; k < p->p_types.nprim; k++) {
> > + ebitmap_t *types_k = &p->attr_type_map[k];
> > +
> > + if (ebitmap_contains(types_k, types_i)) {
> > + if (ebitmap_set_bit(&map[i], k, 1))
> > + goto err;
> > + }
> > + }
> > + }
> > + }
> > + return map;
> > +err:
> > + for (k = 0; k < i; k++)
> > + ebitmap_destroy(&map[i]);
>
> Should be &map[k]
> If ebitmap_set_bit() fails then you need to ebitmap_destroy the ith map, so it
> should be k <= i in the for loop.
Good catch, thanks! I have queued the fix for next revision.
>
> Still looking through this series. It does seem to produce the correct results.
>
> Jim
>
> > + return NULL;
> > +}
> > +
> > +static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
> > +{
> > + unsigned int i;
> > + for (i = 0; i < p->p_types.nprim; i++)
> > + ebitmap_destroy(&type_map[i]);
> > + free(type_map);
> > +}
> > +
> > +static int match_xperms(const uint32_t *p1, const uint32_t *p2)
> > +{
> > + size_t i;
> > +
> > + for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
> > + if ((p2[i] & p1[i]) != p1[i])
> > + return 0;
> > + }
> > + return 1;
> > +}
> > +
> > +static int match_avtab_datum(uint16_t specified,
> > + const avtab_datum_t *d1, const avtab_datum_t *d2)
> > +{
> > + /* inverse logic needed for AUDITDENY rules */
> > + if (specified & AVTAB_AUDITDENY)
> > + return (d1->data & d2->data) == d2->data;
> > +
> > + if (specified & AVTAB_AV)
> > + return (d2->data & d1->data) == d1->data;
> > +
> > + if (specified & AVTAB_XPERMS) {
> > + const avtab_extended_perms_t *x1 = d1->xperms;
> > + const avtab_extended_perms_t *x2 = d2->xperms;
> > +
> > + if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> > + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> > + if (x1->driver != x2->driver)
> > + return 0;
> > + return match_xperms(x1->perms, x2->perms);
> > + }
> > + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> > + return xperm_test(x1->driver, x2->perms);
> > + } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
> > + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
> > + return 0;
> > +
> > + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> > + return match_xperms(x1->perms, x2->perms);
> > + }
> > + return 0;
> > + }
> > + return 0;
> > +}
> > +
> > +/* checks if avtab contains a rule that covers the given rule */
> > +static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
> > + const ebitmap_t *type_map)
> > +{
> > + unsigned int i, k, s_idx, t_idx;
> > + ebitmap_node_t *snode, *tnode;
> > + avtab_datum_t *d1, *d2;
> > + avtab_key_t key;
> > +
> > + /* we only care about AV rules */
> > + if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> > + return 0;
> > +
> > + s_idx = entry->key.source_type - 1;
> > + t_idx = entry->key.target_type - 1;
> > +
> > + key.target_class = entry->key.target_class;
> > + key.specified = entry->key.specified;
> > +
> > + d1 = &entry->datum;
> > +
> > + ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
> > + key.source_type = i + 1;
> > +
> > + ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
> > + if (s_idx == i && t_idx == k)
> > + continue;
> > +
> > + key.target_type = k + 1;
> > +
> > + d2 = avtab_search(tab, &key);
> > + if (!d2)
> > + continue;
> > +
> > + if (match_avtab_datum(key.specified, d1, d2))
> > + return 1;
> > + }
> > + }
> > + return 0;
> > +}
> > +
> > +static int is_type_attr(policydb_t *p, unsigned int id)
> > +{
> > + return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
> > +}
> > +
> > +static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
> > +{
> > + unsigned int s_idx = entry->key.source_type - 1;
> > + unsigned int t_idx = entry->key.target_type - 1;
> > +
> > + return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
> > +}
> > +
> > +/* checks if conditional list contains a rule that covers the given rule */
> > +static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
> > + const ebitmap_t *type_map)
> > +{
> > + unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
> > +
> > + /* we only care about AV rules */
> > + if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> > + return 0;
> > +
> > + s1 = e1->key.source_type - 1;
> > + t1 = e1->key.target_type - 1;
> > + c1 = e1->key.target_class;
> > + k1 = e1->key.specified;
> > +
> > + for (; list; list = list->next) {
> > + avtab_ptr_t e2 = list->node;
> > +
> > + s2 = e2->key.source_type - 1;
> > + t2 = e2->key.target_type - 1;
> > + c2 = e2->key.target_class;
> > + k2 = e2->key.specified;
> > +
> > + if (k1 != k2 || c1 != c2)
> > + continue;
> > +
> > + if (s1 == s2 && t1 == t2)
> > + continue;
> > + if (!ebitmap_get_bit(&type_map[s1], s2))
> > + continue;
> > + if (!ebitmap_get_bit(&type_map[t1], t2))
> > + continue;
> > +
> > + if (match_avtab_datum(k1, &e1->datum, &e2->datum))
> > + return 1;
> > + }
> > + return 0;
> > +}
> > +
> > +static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
> > +{
> > + avtab_t *tab = &p->te_avtab;
> > + unsigned int i;
> > + avtab_ptr_t *cur;
> > +
> > + for (i = 0; i < tab->nslot; i++) {
> > + cur = &tab->htable[i];
> > + while (*cur) {
> > + if (is_avrule_redundant(*cur, tab, type_map)) {
> > + /* redundant rule -> remove it */
> > + avtab_ptr_t tmp = *cur;
> > +
> > + *cur = tmp->next;
> > + if (tmp->key.specified & AVTAB_XPERMS)
> > + free(tmp->datum.xperms);
> > + free(tmp);
> > +
> > + tab->nel--;
> > + } else {
> > + /* rule not redundant -> move to next rule */
> > + cur = &(*cur)->next;
> > + }
> > + }
> > + }
> > +}
> > +
> > +/* find redundant rules in (*cond) and put them into (*del) */
> > +static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
> > + policydb_t *p, const ebitmap_t *type_map)
> > +{
> > + cond_av_list_t **listp = cond;
> > + cond_av_list_t *pcov = NULL;
> > + cond_av_list_t **pcov_cur = &pcov;
> > +
> > + /*
> > + * Separate out all "potentially covering" rules (src or tgt is an attr)
> > + * and move them to the end of the list. This is needed to avoid
> > + * polynomial complexity when almost all rules are expanded.
> > + */
> > + while (*cond) {
> > + if (is_avrule_with_attr((*cond)->node, p)) {
> > + cond_av_list_t *tmp = *cond;
> > +
> > + *cond = tmp->next;
> > + tmp->next = pcov;
> > + pcov = tmp;
> > + } else {
> > + cond = &(*cond)->next;
> > + }
> > + }
> > + /* link the "potentially covering" rules to the end of the list */
> > + *cond = pcov;
> > +
> > + /* now go through the list and find the redundant rules */
> > + cond = listp;
> > + pcov_cur = &pcov;
> > + while (*cond) {
> > + /* needed because pcov itself may get deleted */
> > + if (*cond == pcov)
> > + pcov_cur = cond;
> > + /*
> > + * First check if covered by an unconditional rule, then also
> > + * check if covered by another rule in the same list.
> > + */
> > + if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
> > + is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
> > + cond_av_list_t *tmp = *cond;
> > +
> > + *cond = tmp->next;
> > + tmp->next = *del;
> > + *del = tmp;
> > + } else {
> > + cond = &(*cond)->next;
> > + }
> > + }
> > +}
> > +
> > +static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
> > +{
> > + avtab_t *tab = &p->te_cond_avtab;
> > + unsigned int i;
> > + avtab_ptr_t *cur;
> > + cond_node_t **cond;
> > + cond_av_list_t **avcond, *del = NULL;
> > +
> > + /* First go through all conditionals and collect redundant rules. */
> > + cond = &p->cond_list;
> > + while (*cond) {
> > + optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
> > + optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
> > + /* TODO: maybe also check for rules present in both lists */
> > +
> > + /* nothing left in both lists -> remove the whole conditional */
> > + if (!(*cond)->true_list && !(*cond)->false_list) {
> > + cond_node_t *cond_tmp = *cond;
> > +
> > + *cond = cond_tmp->next;
> > + cond_node_destroy(cond_tmp);
> > + } else {
> > + cond = &(*cond)->next;
> > + }
> > + }
> > +
> > + if (!del)
> > + return;
> > +
> > + /*
> > + * Now go through the whole cond_avtab and remove all rules that are
> > + * found in the 'del' list.
> > + */
> > + for (i = 0; i < tab->nslot; i++) {
> > + cur = &tab->htable[i];
> > + while (*cur) {
> > + int redundant = 0;
> > + avcond = &del;
> > + while (*avcond) {
> > + if ((*avcond)->node == *cur) {
> > + cond_av_list_t *cond_tmp = *avcond;
> > +
> > + *avcond = cond_tmp->next;
> > + free(cond_tmp);
> > + redundant = 1;
> > + break;
> > + } else {
> > + avcond = &(*avcond)->next;
> > + }
> > + }
> > + if (redundant) {
> > + avtab_ptr_t tmp = *cur;
> > +
> > + *cur = tmp->next;
> > + if (tmp->key.specified & AVTAB_XPERMS)
> > + free(tmp->datum.xperms);
> > + free(tmp);
> > +
> > + tab->nel--;
> > + } else {
> > + cur = &(*cur)->next;
> > + }
> > + }
> > + }
> > +}
> > +
> > +int policydb_optimize(policydb_t *p)
> > +{
> > + ebitmap_t *type_map;
> > +
> > + if (p->policy_type != POLICY_KERN)
> > + return -1;
> > +
> > + type_map = build_type_map(p);
> > + if (!type_map)
> > + return -1;
> > +
> > + optimize_avtab(p, type_map);
> > + optimize_cond_avtab(p, type_map);
> > +
> > + destroy_type_map(p, type_map);
> > + return 0;
> > +}
> > diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
> > index e7218423..747a43ff 100644
> > --- a/libsepol/src/policydb_public.c
> > +++ b/libsepol/src/policydb_public.c
> > @@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
> > return 0;
> > }
> >
> > +int sepol_policydb_optimize(sepol_policydb_t * p)
> > +{
> > + return policydb_optimize(&p->p);
> > +}
> > +
> > int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
> > {
> > return policydb_read(&p->p, &pf->pf, 0);
> >
>
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy
2019-05-30 11:46 ` Ondrej Mosnacek
@ 2019-05-30 16:55 ` Stephen Smalley
2019-05-31 7:39 ` Ondrej Mosnacek
0 siblings, 1 reply; 14+ messages in thread
From: Stephen Smalley @ 2019-05-30 16:55 UTC (permalink / raw)
To: Ondrej Mosnacek, jwcart2; +Cc: selinux
On 5/30/19 7:46 AM, Ondrej Mosnacek wrote:
> On Wed, May 29, 2019 at 10:32 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
>> On 5/28/19 10:59 AM, Ondrej Mosnacek wrote:
>>> Add sepol_policydb_optimize(), which checks a kernel policy for
>>> redundant rules (i.e. those that are covered by an existing more general
>>> rule) and removes them.
>>>
>>> Results on Fedora 29 policy:
>>>
>>> WITHOUT OPTIMIZATION:
>>> # time semodule -B
>>> real 0m21,280s
>>> user 0m18,636s
>>> sys 0m2,525s
>>>
>>> $ wc -c /sys/fs/selinux/policy
>>> 8692158 /sys/fs/selinux/policy
>>>
>>> $ seinfo (edited)
>>> Allow: 113159
>>> Dontaudit: 10297
>>> Total: 123156
>>>
>>> WITH OPTIMIZATION ENABLED:
>>> # time semodule -B
>>> real 0m22,825s
>>> user 0m20,178s
>>> sys 0m2,520s
>>>
>>> $ wc -c /sys/fs/selinux/policy
>>> 8096158 /sys/fs/selinux/policy
>>>
>>> $ seinfo (edited)
>>> Allow: 66334
>>> Dontaudit: 7480
>>> Total: 73814
>>>
>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>>> ---
>>> libsepol/include/sepol/policydb.h | 5 +
>>> libsepol/include/sepol/policydb/policydb.h | 2 +
>>> libsepol/src/libsepol.map.in | 5 +
>>> libsepol/src/optimize.c | 374 +++++++++++++++++++++
>>> libsepol/src/policydb_public.c | 5 +
>>> 5 files changed, 391 insertions(+)
>>> create mode 100644 libsepol/src/optimize.c
>>>
>>> diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
>>> index 6769b913..792913dd 100644
>>> --- a/libsepol/include/sepol/policydb.h
>>> +++ b/libsepol/include/sepol/policydb.h
>>> @@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
>>> extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
>>> int target_platform);
>>>
>>> +/*
>>> + * Optimize the policy by removing redundant rules.
>>> + */
>>> +extern int sepol_policydb_optimize(sepol_policydb_t * p);
>>> +
>>> /*
>>> * Read a policydb from a policy file.
>>> * This automatically sets the type and version based on the
>>> diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
>>> index 591ce6e0..a279382e 100644
>>> --- a/libsepol/include/sepol/policydb/policydb.h
>>> +++ b/libsepol/include/sepol/policydb/policydb.h
>>> @@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
>>>
>>> extern int policydb_reindex_users(policydb_t * p);
>>>
>>> +extern int policydb_optimize(policydb_t * p);
>>> +
>>> extern void policydb_destroy(policydb_t * p);
>>>
>>> extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
>>> diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
>>> index d879016c..6358e51f 100644
>>> --- a/libsepol/src/libsepol.map.in
>>> +++ b/libsepol/src/libsepol.map.in
>>> @@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
>>> sepol_polcap_getnum;
>>> sepol_polcap_getname;
>>> } LIBSEPOL_1.0;
>>> +
>>> +LIBSEPOL_1.2 {
>>> + global:
>>> + sepol_optimize_policy;
>>> +} LIBSEPOL_1.1;
>>> diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
>>> new file mode 100644
>>> index 00000000..b3859b6c
>>> --- /dev/null
>>> +++ b/libsepol/src/optimize.c
>>> @@ -0,0 +1,374 @@
>>> +/*
>>> + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
>>> + *
>>> + * Copyright (C) 2019 Red Hat Inc.
>>> + *
>>> + * This library is free software; you can redistribute it and/or
>>> + * modify it under the terms of the GNU Lesser General Public
>>> + * License as published by the Free Software Foundation; either
>>> + * version 2.1 of the License, or (at your option) any later version.
>>> + *
>>> + * This library is distributed in the hope that it will be useful,
>>> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
>>> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
>>> + * Lesser General Public License for more details.
>>> + *
>>> + * You should have received a copy of the GNU Lesser General Public
>>> + * License along with this library; if not, write to the Free Software
>>> + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
>>> + */
>>> +
>>> +/*
>>> + * Binary policy optimization.
>>> + *
>>> + * Defines the policydb_optimize() function, which finds and removes
>>> + * redundant rules from the binary policy to reduce its size and potentially
>>> + * improve rule matching times. Only rules that are already covered by a
>>> + * more general rule are removed. The resulting policy is functionally
>>> + * equivalent to the original one.
>>> + */
>>> +
>>> +#include <sepol/policydb/policydb.h>
>>> +#include <sepol/policydb/conditional.h>
>>> +
>>> +/* builds map: type/attribute -> {all attributes that are a superset of it} */
>>> +static ebitmap_t *build_type_map(const policydb_t *p)
>>> +{
>>> + unsigned int i, k;
>>> + ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
>>> + if (!map)
>>> + return NULL;
>>> +
>>> + for (i = 0; i < p->p_types.nprim; i++) {
>>> + if (p->type_val_to_struct[i] &&
>>> + p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
>>> + if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
>>> + goto err;
>>> + } else {
>>> + ebitmap_t *types_i = &p->attr_type_map[i];
>>> +
>>> + ebitmap_init(&map[i]);
>>> + for (k = 0; k < p->p_types.nprim; k++) {
>>> + ebitmap_t *types_k = &p->attr_type_map[k];
>>> +
>>> + if (ebitmap_contains(types_k, types_i)) {
>>> + if (ebitmap_set_bit(&map[i], k, 1))
>>> + goto err;
>>> + }
>>> + }
>>> + }
>>> + }
>>> + return map;
>>> +err:
>>> + for (k = 0; k < i; k++)
>>> + ebitmap_destroy(&map[i]);
>>
>> Should be &map[k]
>> If ebitmap_set_bit() fails then you need to ebitmap_destroy the ith map, so it
>> should be k <= i in the for loop.
>
> Good catch, thanks! I have queued the fix for next revision.
Don't forget to free(map); too.
Also, valgrind --leak-check=full isn't clean for semodule -B after this
patch set with optimize-policy = true; I think you aren't always freeing
conditional nodes?
On a recent Android policy, secilc -O pruned 1127 out of 21718 allow
rules and 102 out of 391 allowx rules (ioctl xperms). Time difference
was negligible (0.433s versus 0.341s). sediff claimed no semantic
differences in the resulting kernel policy.
>
>>
>> Still looking through this series. It does seem to produce the correct results.
>>
>> Jim
>>
>>> + return NULL;
>>> +}
>>> +
>>> +static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
>>> +{
>>> + unsigned int i;
>>> + for (i = 0; i < p->p_types.nprim; i++)
>>> + ebitmap_destroy(&type_map[i]);
>>> + free(type_map);
>>> +}
>>> +
>>> +static int match_xperms(const uint32_t *p1, const uint32_t *p2)
>>> +{
>>> + size_t i;
>>> +
>>> + for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
>>> + if ((p2[i] & p1[i]) != p1[i])
>>> + return 0;
>>> + }
>>> + return 1;
>>> +}
>>> +
>>> +static int match_avtab_datum(uint16_t specified,
>>> + const avtab_datum_t *d1, const avtab_datum_t *d2)
>>> +{
>>> + /* inverse logic needed for AUDITDENY rules */
>>> + if (specified & AVTAB_AUDITDENY)
>>> + return (d1->data & d2->data) == d2->data;
>>> +
>>> + if (specified & AVTAB_AV)
>>> + return (d2->data & d1->data) == d1->data;
>>> +
>>> + if (specified & AVTAB_XPERMS) {
>>> + const avtab_extended_perms_t *x1 = d1->xperms;
>>> + const avtab_extended_perms_t *x2 = d2->xperms;
>>> +
>>> + if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
>>> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
>>> + if (x1->driver != x2->driver)
>>> + return 0;
>>> + return match_xperms(x1->perms, x2->perms);
>>> + }
>>> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
>>> + return xperm_test(x1->driver, x2->perms);
>>> + } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
>>> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
>>> + return 0;
>>> +
>>> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
>>> + return match_xperms(x1->perms, x2->perms);
>>> + }
>>> + return 0;
>>> + }
>>> + return 0;
>>> +}
>>> +
>>> +/* checks if avtab contains a rule that covers the given rule */
>>> +static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
>>> + const ebitmap_t *type_map)
>>> +{
>>> + unsigned int i, k, s_idx, t_idx;
>>> + ebitmap_node_t *snode, *tnode;
>>> + avtab_datum_t *d1, *d2;
>>> + avtab_key_t key;
>>> +
>>> + /* we only care about AV rules */
>>> + if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
>>> + return 0;
>>> +
>>> + s_idx = entry->key.source_type - 1;
>>> + t_idx = entry->key.target_type - 1;
>>> +
>>> + key.target_class = entry->key.target_class;
>>> + key.specified = entry->key.specified;
>>> +
>>> + d1 = &entry->datum;
>>> +
>>> + ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
>>> + key.source_type = i + 1;
>>> +
>>> + ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
>>> + if (s_idx == i && t_idx == k)
>>> + continue;
>>> +
>>> + key.target_type = k + 1;
>>> +
>>> + d2 = avtab_search(tab, &key);
>>> + if (!d2)
>>> + continue;
>>> +
>>> + if (match_avtab_datum(key.specified, d1, d2))
>>> + return 1;
>>> + }
>>> + }
>>> + return 0;
>>> +}
>>> +
>>> +static int is_type_attr(policydb_t *p, unsigned int id)
>>> +{
>>> + return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
>>> +}
>>> +
>>> +static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
>>> +{
>>> + unsigned int s_idx = entry->key.source_type - 1;
>>> + unsigned int t_idx = entry->key.target_type - 1;
>>> +
>>> + return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
>>> +}
>>> +
>>> +/* checks if conditional list contains a rule that covers the given rule */
>>> +static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
>>> + const ebitmap_t *type_map)
>>> +{
>>> + unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
>>> +
>>> + /* we only care about AV rules */
>>> + if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
>>> + return 0;
>>> +
>>> + s1 = e1->key.source_type - 1;
>>> + t1 = e1->key.target_type - 1;
>>> + c1 = e1->key.target_class;
>>> + k1 = e1->key.specified;
>>> +
>>> + for (; list; list = list->next) {
>>> + avtab_ptr_t e2 = list->node;
>>> +
>>> + s2 = e2->key.source_type - 1;
>>> + t2 = e2->key.target_type - 1;
>>> + c2 = e2->key.target_class;
>>> + k2 = e2->key.specified;
>>> +
>>> + if (k1 != k2 || c1 != c2)
>>> + continue;
>>> +
>>> + if (s1 == s2 && t1 == t2)
>>> + continue;
>>> + if (!ebitmap_get_bit(&type_map[s1], s2))
>>> + continue;
>>> + if (!ebitmap_get_bit(&type_map[t1], t2))
>>> + continue;
>>> +
>>> + if (match_avtab_datum(k1, &e1->datum, &e2->datum))
>>> + return 1;
>>> + }
>>> + return 0;
>>> +}
>>> +
>>> +static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
>>> +{
>>> + avtab_t *tab = &p->te_avtab;
>>> + unsigned int i;
>>> + avtab_ptr_t *cur;
>>> +
>>> + for (i = 0; i < tab->nslot; i++) {
>>> + cur = &tab->htable[i];
>>> + while (*cur) {
>>> + if (is_avrule_redundant(*cur, tab, type_map)) {
>>> + /* redundant rule -> remove it */
>>> + avtab_ptr_t tmp = *cur;
>>> +
>>> + *cur = tmp->next;
>>> + if (tmp->key.specified & AVTAB_XPERMS)
>>> + free(tmp->datum.xperms);
>>> + free(tmp);
>>> +
>>> + tab->nel--;
>>> + } else {
>>> + /* rule not redundant -> move to next rule */
>>> + cur = &(*cur)->next;
>>> + }
>>> + }
>>> + }
>>> +}
>>> +
>>> +/* find redundant rules in (*cond) and put them into (*del) */
>>> +static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
>>> + policydb_t *p, const ebitmap_t *type_map)
>>> +{
>>> + cond_av_list_t **listp = cond;
>>> + cond_av_list_t *pcov = NULL;
>>> + cond_av_list_t **pcov_cur = &pcov;
>>> +
>>> + /*
>>> + * Separate out all "potentially covering" rules (src or tgt is an attr)
>>> + * and move them to the end of the list. This is needed to avoid
>>> + * polynomial complexity when almost all rules are expanded.
>>> + */
>>> + while (*cond) {
>>> + if (is_avrule_with_attr((*cond)->node, p)) {
>>> + cond_av_list_t *tmp = *cond;
>>> +
>>> + *cond = tmp->next;
>>> + tmp->next = pcov;
>>> + pcov = tmp;
>>> + } else {
>>> + cond = &(*cond)->next;
>>> + }
>>> + }
>>> + /* link the "potentially covering" rules to the end of the list */
>>> + *cond = pcov;
>>> +
>>> + /* now go through the list and find the redundant rules */
>>> + cond = listp;
>>> + pcov_cur = &pcov;
>>> + while (*cond) {
>>> + /* needed because pcov itself may get deleted */
>>> + if (*cond == pcov)
>>> + pcov_cur = cond;
>>> + /*
>>> + * First check if covered by an unconditional rule, then also
>>> + * check if covered by another rule in the same list.
>>> + */
>>> + if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
>>> + is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
>>> + cond_av_list_t *tmp = *cond;
>>> +
>>> + *cond = tmp->next;
>>> + tmp->next = *del;
>>> + *del = tmp;
>>> + } else {
>>> + cond = &(*cond)->next;
>>> + }
>>> + }
>>> +}
>>> +
>>> +static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
>>> +{
>>> + avtab_t *tab = &p->te_cond_avtab;
>>> + unsigned int i;
>>> + avtab_ptr_t *cur;
>>> + cond_node_t **cond;
>>> + cond_av_list_t **avcond, *del = NULL;
>>> +
>>> + /* First go through all conditionals and collect redundant rules. */
>>> + cond = &p->cond_list;
>>> + while (*cond) {
>>> + optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
>>> + optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
>>> + /* TODO: maybe also check for rules present in both lists */
>>> +
>>> + /* nothing left in both lists -> remove the whole conditional */
>>> + if (!(*cond)->true_list && !(*cond)->false_list) {
>>> + cond_node_t *cond_tmp = *cond;
>>> +
>>> + *cond = cond_tmp->next;
>>> + cond_node_destroy(cond_tmp);
>>> + } else {
>>> + cond = &(*cond)->next;
>>> + }
>>> + }
>>> +
>>> + if (!del)
>>> + return;
>>> +
>>> + /*
>>> + * Now go through the whole cond_avtab and remove all rules that are
>>> + * found in the 'del' list.
>>> + */
>>> + for (i = 0; i < tab->nslot; i++) {
>>> + cur = &tab->htable[i];
>>> + while (*cur) {
>>> + int redundant = 0;
>>> + avcond = &del;
>>> + while (*avcond) {
>>> + if ((*avcond)->node == *cur) {
>>> + cond_av_list_t *cond_tmp = *avcond;
>>> +
>>> + *avcond = cond_tmp->next;
>>> + free(cond_tmp);
>>> + redundant = 1;
>>> + break;
>>> + } else {
>>> + avcond = &(*avcond)->next;
>>> + }
>>> + }
>>> + if (redundant) {
>>> + avtab_ptr_t tmp = *cur;
>>> +
>>> + *cur = tmp->next;
>>> + if (tmp->key.specified & AVTAB_XPERMS)
>>> + free(tmp->datum.xperms);
>>> + free(tmp);
>>> +
>>> + tab->nel--;
>>> + } else {
>>> + cur = &(*cur)->next;
>>> + }
>>> + }
>>> + }
>>> +}
>>> +
>>> +int policydb_optimize(policydb_t *p)
>>> +{
>>> + ebitmap_t *type_map;
>>> +
>>> + if (p->policy_type != POLICY_KERN)
>>> + return -1;
>>> +
>>> + type_map = build_type_map(p);
>>> + if (!type_map)
>>> + return -1;
>>> +
>>> + optimize_avtab(p, type_map);
>>> + optimize_cond_avtab(p, type_map);
>>> +
>>> + destroy_type_map(p, type_map);
>>> + return 0;
>>> +}
>>> diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
>>> index e7218423..747a43ff 100644
>>> --- a/libsepol/src/policydb_public.c
>>> +++ b/libsepol/src/policydb_public.c
>>> @@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
>>> return 0;
>>> }
>>>
>>> +int sepol_policydb_optimize(sepol_policydb_t * p)
>>> +{
>>> + return policydb_optimize(&p->p);
>>> +}
>>> +
>>> int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
>>> {
>>> return policydb_read(&p->p, &pf->pf, 0);
>>>
>>
>>
>> --
>> James Carter <jwcart2@tycho.nsa.gov>
>> National Security Agency
>
>
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy
2019-05-30 16:55 ` Stephen Smalley
@ 2019-05-31 7:39 ` Ondrej Mosnacek
0 siblings, 0 replies; 14+ messages in thread
From: Ondrej Mosnacek @ 2019-05-31 7:39 UTC (permalink / raw)
To: Stephen Smalley; +Cc: jwcart2, selinux
On Thu, May 30, 2019 at 6:56 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 5/30/19 7:46 AM, Ondrej Mosnacek wrote:
> > On Wed, May 29, 2019 at 10:32 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> >> On 5/28/19 10:59 AM, Ondrej Mosnacek wrote:
> >>> Add sepol_policydb_optimize(), which checks a kernel policy for
> >>> redundant rules (i.e. those that are covered by an existing more general
> >>> rule) and removes them.
> >>>
> >>> Results on Fedora 29 policy:
> >>>
> >>> WITHOUT OPTIMIZATION:
> >>> # time semodule -B
> >>> real 0m21,280s
> >>> user 0m18,636s
> >>> sys 0m2,525s
> >>>
> >>> $ wc -c /sys/fs/selinux/policy
> >>> 8692158 /sys/fs/selinux/policy
> >>>
> >>> $ seinfo (edited)
> >>> Allow: 113159
> >>> Dontaudit: 10297
> >>> Total: 123156
> >>>
> >>> WITH OPTIMIZATION ENABLED:
> >>> # time semodule -B
> >>> real 0m22,825s
> >>> user 0m20,178s
> >>> sys 0m2,520s
> >>>
> >>> $ wc -c /sys/fs/selinux/policy
> >>> 8096158 /sys/fs/selinux/policy
> >>>
> >>> $ seinfo (edited)
> >>> Allow: 66334
> >>> Dontaudit: 7480
> >>> Total: 73814
> >>>
> >>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> >>> ---
> >>> libsepol/include/sepol/policydb.h | 5 +
> >>> libsepol/include/sepol/policydb/policydb.h | 2 +
> >>> libsepol/src/libsepol.map.in | 5 +
> >>> libsepol/src/optimize.c | 374 +++++++++++++++++++++
> >>> libsepol/src/policydb_public.c | 5 +
> >>> 5 files changed, 391 insertions(+)
> >>> create mode 100644 libsepol/src/optimize.c
> >>>
> >>> diff --git a/libsepol/include/sepol/policydb.h b/libsepol/include/sepol/policydb.h
> >>> index 6769b913..792913dd 100644
> >>> --- a/libsepol/include/sepol/policydb.h
> >>> +++ b/libsepol/include/sepol/policydb.h
> >>> @@ -100,6 +100,11 @@ extern int sepol_policydb_set_handle_unknown(sepol_policydb_t * p,
> >>> extern int sepol_policydb_set_target_platform(sepol_policydb_t * p,
> >>> int target_platform);
> >>>
> >>> +/*
> >>> + * Optimize the policy by removing redundant rules.
> >>> + */
> >>> +extern int sepol_policydb_optimize(sepol_policydb_t * p);
> >>> +
> >>> /*
> >>> * Read a policydb from a policy file.
> >>> * This automatically sets the type and version based on the
> >>> diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h
> >>> index 591ce6e0..a279382e 100644
> >>> --- a/libsepol/include/sepol/policydb/policydb.h
> >>> +++ b/libsepol/include/sepol/policydb/policydb.h
> >>> @@ -636,6 +636,8 @@ extern int policydb_user_cache(hashtab_key_t key,
> >>>
> >>> extern int policydb_reindex_users(policydb_t * p);
> >>>
> >>> +extern int policydb_optimize(policydb_t * p);
> >>> +
> >>> extern void policydb_destroy(policydb_t * p);
> >>>
> >>> extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
> >>> diff --git a/libsepol/src/libsepol.map.in b/libsepol/src/libsepol.map.in
> >>> index d879016c..6358e51f 100644
> >>> --- a/libsepol/src/libsepol.map.in
> >>> +++ b/libsepol/src/libsepol.map.in
> >>> @@ -59,3 +59,8 @@ LIBSEPOL_1.1 {
> >>> sepol_polcap_getnum;
> >>> sepol_polcap_getname;
> >>> } LIBSEPOL_1.0;
> >>> +
> >>> +LIBSEPOL_1.2 {
> >>> + global:
> >>> + sepol_optimize_policy;
> >>> +} LIBSEPOL_1.1;
> >>> diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> >>> new file mode 100644
> >>> index 00000000..b3859b6c
> >>> --- /dev/null
> >>> +++ b/libsepol/src/optimize.c
> >>> @@ -0,0 +1,374 @@
> >>> +/*
> >>> + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
> >>> + *
> >>> + * Copyright (C) 2019 Red Hat Inc.
> >>> + *
> >>> + * This library is free software; you can redistribute it and/or
> >>> + * modify it under the terms of the GNU Lesser General Public
> >>> + * License as published by the Free Software Foundation; either
> >>> + * version 2.1 of the License, or (at your option) any later version.
> >>> + *
> >>> + * This library is distributed in the hope that it will be useful,
> >>> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> >>> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> >>> + * Lesser General Public License for more details.
> >>> + *
> >>> + * You should have received a copy of the GNU Lesser General Public
> >>> + * License along with this library; if not, write to the Free Software
> >>> + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
> >>> + */
> >>> +
> >>> +/*
> >>> + * Binary policy optimization.
> >>> + *
> >>> + * Defines the policydb_optimize() function, which finds and removes
> >>> + * redundant rules from the binary policy to reduce its size and potentially
> >>> + * improve rule matching times. Only rules that are already covered by a
> >>> + * more general rule are removed. The resulting policy is functionally
> >>> + * equivalent to the original one.
> >>> + */
> >>> +
> >>> +#include <sepol/policydb/policydb.h>
> >>> +#include <sepol/policydb/conditional.h>
> >>> +
> >>> +/* builds map: type/attribute -> {all attributes that are a superset of it} */
> >>> +static ebitmap_t *build_type_map(const policydb_t *p)
> >>> +{
> >>> + unsigned int i, k;
> >>> + ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
> >>> + if (!map)
> >>> + return NULL;
> >>> +
> >>> + for (i = 0; i < p->p_types.nprim; i++) {
> >>> + if (p->type_val_to_struct[i] &&
> >>> + p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
> >>> + if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
> >>> + goto err;
> >>> + } else {
> >>> + ebitmap_t *types_i = &p->attr_type_map[i];
> >>> +
> >>> + ebitmap_init(&map[i]);
> >>> + for (k = 0; k < p->p_types.nprim; k++) {
> >>> + ebitmap_t *types_k = &p->attr_type_map[k];
> >>> +
> >>> + if (ebitmap_contains(types_k, types_i)) {
> >>> + if (ebitmap_set_bit(&map[i], k, 1))
> >>> + goto err;
> >>> + }
> >>> + }
> >>> + }
> >>> + }
> >>> + return map;
> >>> +err:
> >>> + for (k = 0; k < i; k++)
> >>> + ebitmap_destroy(&map[i]);
> >>
> >> Should be &map[k]
> >> If ebitmap_set_bit() fails then you need to ebitmap_destroy the ith map, so it
> >> should be k <= i in the for loop.
> >
> > Good catch, thanks! I have queued the fix for next revision.
>
> Don't forget to free(map); too.
Damn, I always forget the most trivial things... :/
>
> Also, valgrind --leak-check=full isn't clean for semodule -B after this
> patch set with optimize-policy = true; I think you aren't always freeing
> conditional nodes?
*remembers that he can use valgrind in userspace...*
I'll have a look at that, thanks!
>
> On a recent Android policy, secilc -O pruned 1127 out of 21718 allow
> rules and 102 out of 391 allowx rules (ioctl xperms). Time difference
> was negligible (0.433s versus 0.341s). sediff claimed no semantic
> differences in the resulting kernel policy.
Looks like we (Fedora/RHEL) are the only ones with serious redundancy
in our policy... I wish we could fix it by rewriting the policy, but
with the current size of Fedora policy and our capacity it is not a
viable option, so we need to leave this up to the tooling.
>
> >
> >>
> >> Still looking through this series. It does seem to produce the correct results.
> >>
> >> Jim
> >>
> >>> + return NULL;
> >>> +}
> >>> +
> >>> +static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
> >>> +{
> >>> + unsigned int i;
> >>> + for (i = 0; i < p->p_types.nprim; i++)
> >>> + ebitmap_destroy(&type_map[i]);
> >>> + free(type_map);
> >>> +}
> >>> +
> >>> +static int match_xperms(const uint32_t *p1, const uint32_t *p2)
> >>> +{
> >>> + size_t i;
> >>> +
> >>> + for (i = 0; i < EXTENDED_PERMS_LEN; i++) {
> >>> + if ((p2[i] & p1[i]) != p1[i])
> >>> + return 0;
> >>> + }
> >>> + return 1;
> >>> +}
> >>> +
> >>> +static int match_avtab_datum(uint16_t specified,
> >>> + const avtab_datum_t *d1, const avtab_datum_t *d2)
> >>> +{
> >>> + /* inverse logic needed for AUDITDENY rules */
> >>> + if (specified & AVTAB_AUDITDENY)
> >>> + return (d1->data & d2->data) == d2->data;
> >>> +
> >>> + if (specified & AVTAB_AV)
> >>> + return (d2->data & d1->data) == d1->data;
> >>> +
> >>> + if (specified & AVTAB_XPERMS) {
> >>> + const avtab_extended_perms_t *x1 = d1->xperms;
> >>> + const avtab_extended_perms_t *x2 = d2->xperms;
> >>> +
> >>> + if (x1->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> >>> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION) {
> >>> + if (x1->driver != x2->driver)
> >>> + return 0;
> >>> + return match_xperms(x1->perms, x2->perms);
> >>> + }
> >>> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> >>> + return xperm_test(x1->driver, x2->perms);
> >>> + } else if (x1->specified == AVTAB_XPERMS_IOCTLDRIVER) {
> >>> + if (x2->specified == AVTAB_XPERMS_IOCTLFUNCTION)
> >>> + return 0;
> >>> +
> >>> + if (x2->specified == AVTAB_XPERMS_IOCTLDRIVER)
> >>> + return match_xperms(x1->perms, x2->perms);
> >>> + }
> >>> + return 0;
> >>> + }
> >>> + return 0;
> >>> +}
> >>> +
> >>> +/* checks if avtab contains a rule that covers the given rule */
> >>> +static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
> >>> + const ebitmap_t *type_map)
> >>> +{
> >>> + unsigned int i, k, s_idx, t_idx;
> >>> + ebitmap_node_t *snode, *tnode;
> >>> + avtab_datum_t *d1, *d2;
> >>> + avtab_key_t key;
> >>> +
> >>> + /* we only care about AV rules */
> >>> + if (!(entry->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> >>> + return 0;
> >>> +
> >>> + s_idx = entry->key.source_type - 1;
> >>> + t_idx = entry->key.target_type - 1;
> >>> +
> >>> + key.target_class = entry->key.target_class;
> >>> + key.specified = entry->key.specified;
> >>> +
> >>> + d1 = &entry->datum;
> >>> +
> >>> + ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
> >>> + key.source_type = i + 1;
> >>> +
> >>> + ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
> >>> + if (s_idx == i && t_idx == k)
> >>> + continue;
> >>> +
> >>> + key.target_type = k + 1;
> >>> +
> >>> + d2 = avtab_search(tab, &key);
> >>> + if (!d2)
> >>> + continue;
> >>> +
> >>> + if (match_avtab_datum(key.specified, d1, d2))
> >>> + return 1;
> >>> + }
> >>> + }
> >>> + return 0;
> >>> +}
> >>> +
> >>> +static int is_type_attr(policydb_t *p, unsigned int id)
> >>> +{
> >>> + return p->type_val_to_struct[id]->flavor == TYPE_ATTRIB;
> >>> +}
> >>> +
> >>> +static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
> >>> +{
> >>> + unsigned int s_idx = entry->key.source_type - 1;
> >>> + unsigned int t_idx = entry->key.target_type - 1;
> >>> +
> >>> + return is_type_attr(p, s_idx) || is_type_attr(p, t_idx);
> >>> +}
> >>> +
> >>> +/* checks if conditional list contains a rule that covers the given rule */
> >>> +static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
> >>> + const ebitmap_t *type_map)
> >>> +{
> >>> + unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
> >>> +
> >>> + /* we only care about AV rules */
> >>> + if (!(e1->key.specified & (AVTAB_AV|AVTAB_XPERMS)))
> >>> + return 0;
> >>> +
> >>> + s1 = e1->key.source_type - 1;
> >>> + t1 = e1->key.target_type - 1;
> >>> + c1 = e1->key.target_class;
> >>> + k1 = e1->key.specified;
> >>> +
> >>> + for (; list; list = list->next) {
> >>> + avtab_ptr_t e2 = list->node;
> >>> +
> >>> + s2 = e2->key.source_type - 1;
> >>> + t2 = e2->key.target_type - 1;
> >>> + c2 = e2->key.target_class;
> >>> + k2 = e2->key.specified;
> >>> +
> >>> + if (k1 != k2 || c1 != c2)
> >>> + continue;
> >>> +
> >>> + if (s1 == s2 && t1 == t2)
> >>> + continue;
> >>> + if (!ebitmap_get_bit(&type_map[s1], s2))
> >>> + continue;
> >>> + if (!ebitmap_get_bit(&type_map[t1], t2))
> >>> + continue;
> >>> +
> >>> + if (match_avtab_datum(k1, &e1->datum, &e2->datum))
> >>> + return 1;
> >>> + }
> >>> + return 0;
> >>> +}
> >>> +
> >>> +static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
> >>> +{
> >>> + avtab_t *tab = &p->te_avtab;
> >>> + unsigned int i;
> >>> + avtab_ptr_t *cur;
> >>> +
> >>> + for (i = 0; i < tab->nslot; i++) {
> >>> + cur = &tab->htable[i];
> >>> + while (*cur) {
> >>> + if (is_avrule_redundant(*cur, tab, type_map)) {
> >>> + /* redundant rule -> remove it */
> >>> + avtab_ptr_t tmp = *cur;
> >>> +
> >>> + *cur = tmp->next;
> >>> + if (tmp->key.specified & AVTAB_XPERMS)
> >>> + free(tmp->datum.xperms);
> >>> + free(tmp);
> >>> +
> >>> + tab->nel--;
> >>> + } else {
> >>> + /* rule not redundant -> move to next rule */
> >>> + cur = &(*cur)->next;
> >>> + }
> >>> + }
> >>> + }
> >>> +}
> >>> +
> >>> +/* find redundant rules in (*cond) and put them into (*del) */
> >>> +static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
> >>> + policydb_t *p, const ebitmap_t *type_map)
> >>> +{
> >>> + cond_av_list_t **listp = cond;
> >>> + cond_av_list_t *pcov = NULL;
> >>> + cond_av_list_t **pcov_cur = &pcov;
> >>> +
> >>> + /*
> >>> + * Separate out all "potentially covering" rules (src or tgt is an attr)
> >>> + * and move them to the end of the list. This is needed to avoid
> >>> + * polynomial complexity when almost all rules are expanded.
> >>> + */
> >>> + while (*cond) {
> >>> + if (is_avrule_with_attr((*cond)->node, p)) {
> >>> + cond_av_list_t *tmp = *cond;
> >>> +
> >>> + *cond = tmp->next;
> >>> + tmp->next = pcov;
> >>> + pcov = tmp;
> >>> + } else {
> >>> + cond = &(*cond)->next;
> >>> + }
> >>> + }
> >>> + /* link the "potentially covering" rules to the end of the list */
> >>> + *cond = pcov;
> >>> +
> >>> + /* now go through the list and find the redundant rules */
> >>> + cond = listp;
> >>> + pcov_cur = &pcov;
> >>> + while (*cond) {
> >>> + /* needed because pcov itself may get deleted */
> >>> + if (*cond == pcov)
> >>> + pcov_cur = cond;
> >>> + /*
> >>> + * First check if covered by an unconditional rule, then also
> >>> + * check if covered by another rule in the same list.
> >>> + */
> >>> + if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
> >>> + is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
> >>> + cond_av_list_t *tmp = *cond;
> >>> +
> >>> + *cond = tmp->next;
> >>> + tmp->next = *del;
> >>> + *del = tmp;
> >>> + } else {
> >>> + cond = &(*cond)->next;
> >>> + }
> >>> + }
> >>> +}
> >>> +
> >>> +static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
> >>> +{
> >>> + avtab_t *tab = &p->te_cond_avtab;
> >>> + unsigned int i;
> >>> + avtab_ptr_t *cur;
> >>> + cond_node_t **cond;
> >>> + cond_av_list_t **avcond, *del = NULL;
> >>> +
> >>> + /* First go through all conditionals and collect redundant rules. */
> >>> + cond = &p->cond_list;
> >>> + while (*cond) {
> >>> + optimize_cond_av_list(&(*cond)->true_list, &del, p, type_map);
> >>> + optimize_cond_av_list(&(*cond)->false_list, &del, p, type_map);
> >>> + /* TODO: maybe also check for rules present in both lists */
> >>> +
> >>> + /* nothing left in both lists -> remove the whole conditional */
> >>> + if (!(*cond)->true_list && !(*cond)->false_list) {
> >>> + cond_node_t *cond_tmp = *cond;
> >>> +
> >>> + *cond = cond_tmp->next;
> >>> + cond_node_destroy(cond_tmp);
> >>> + } else {
> >>> + cond = &(*cond)->next;
> >>> + }
> >>> + }
> >>> +
> >>> + if (!del)
> >>> + return;
> >>> +
> >>> + /*
> >>> + * Now go through the whole cond_avtab and remove all rules that are
> >>> + * found in the 'del' list.
> >>> + */
> >>> + for (i = 0; i < tab->nslot; i++) {
> >>> + cur = &tab->htable[i];
> >>> + while (*cur) {
> >>> + int redundant = 0;
> >>> + avcond = &del;
> >>> + while (*avcond) {
> >>> + if ((*avcond)->node == *cur) {
> >>> + cond_av_list_t *cond_tmp = *avcond;
> >>> +
> >>> + *avcond = cond_tmp->next;
> >>> + free(cond_tmp);
> >>> + redundant = 1;
> >>> + break;
> >>> + } else {
> >>> + avcond = &(*avcond)->next;
> >>> + }
> >>> + }
> >>> + if (redundant) {
> >>> + avtab_ptr_t tmp = *cur;
> >>> +
> >>> + *cur = tmp->next;
> >>> + if (tmp->key.specified & AVTAB_XPERMS)
> >>> + free(tmp->datum.xperms);
> >>> + free(tmp);
> >>> +
> >>> + tab->nel--;
> >>> + } else {
> >>> + cur = &(*cur)->next;
> >>> + }
> >>> + }
> >>> + }
> >>> +}
> >>> +
> >>> +int policydb_optimize(policydb_t *p)
> >>> +{
> >>> + ebitmap_t *type_map;
> >>> +
> >>> + if (p->policy_type != POLICY_KERN)
> >>> + return -1;
> >>> +
> >>> + type_map = build_type_map(p);
> >>> + if (!type_map)
> >>> + return -1;
> >>> +
> >>> + optimize_avtab(p, type_map);
> >>> + optimize_cond_avtab(p, type_map);
> >>> +
> >>> + destroy_type_map(p, type_map);
> >>> + return 0;
> >>> +}
> >>> diff --git a/libsepol/src/policydb_public.c b/libsepol/src/policydb_public.c
> >>> index e7218423..747a43ff 100644
> >>> --- a/libsepol/src/policydb_public.c
> >>> +++ b/libsepol/src/policydb_public.c
> >>> @@ -169,6 +169,11 @@ int sepol_policydb_set_target_platform(sepol_policydb_t * sp,
> >>> return 0;
> >>> }
> >>>
> >>> +int sepol_policydb_optimize(sepol_policydb_t * p)
> >>> +{
> >>> + return policydb_optimize(&p->p);
> >>> +}
> >>> +
> >>> int sepol_policydb_read(sepol_policydb_t * p, sepol_policy_file_t * pf)
> >>> {
> >>> return policydb_read(&p->p, &pf->pf, 0);
> >>>
> >>
> >>
> >> --
> >> James Carter <jwcart2@tycho.nsa.gov>
> >> National Security Agency
> >
> >
> >
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2019-05-31 7:39 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-05-28 14:59 [PATCH userspace v2 0/7] Remove redundant rules when building policydb Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 1/7] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
2019-05-29 20:32 ` [Non-DoD Source] " jwcart2
2019-05-30 11:46 ` Ondrej Mosnacek
2019-05-30 16:55 ` Stephen Smalley
2019-05-31 7:39 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 2/7] libsemanage: optionally optimize policy on rebuild Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 3/7] semodule: add flag to enable policy optimization Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 4/7] secilc: " Ondrej Mosnacek
2019-05-28 16:32 ` Dominick Grift
2019-05-28 17:01 ` Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 5/7] checkpolicy: " Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 6/7] [RFC] lisepol: slightly more thorough optimization Ondrej Mosnacek
2019-05-28 14:59 ` [PATCH userspace v2 7/7] [RFC] libsemanage: switch to config file entry Ondrej Mosnacek
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.