* [PATCH userspace 1/4] libsepol: add a function to optimize kernel policy
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
@ 2019-05-23 10:24 ` Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 2/4] secilc: optimize policy before writing Ondrej Mosnacek
` (4 subsequent siblings)
5 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-23 10:24 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 --no-optimize
real 0m20,190s
user 0m18,003s
sys 0m2,075s
$ wc -c /sys/fs/selinux/policy
8689631 /sys/fs/selinux/policy
$ seinfo (edited)
Allow: 113152
Dontaudit: 10294
Total: 123146
WITH OPTIMIZATION ENABLED:
# time semodule -B
real 0m21,406s
user 0m19,061s
sys 0m2,227s
$ wc -c /sys/fs/selinux/policy
8089575 /sys/fs/selinux/policy
$ seinfo (edited)
Allow: 66328
Dontaudit: 7138
Total: 73466
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 | 370 +++++++++++++++++++++
libsepol/src/policydb_public.c | 5 +
5 files changed, 387 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..1fa1495c
--- /dev/null
+++ b/libsepol/src/optimize.c
@@ -0,0 +1,370 @@
+/*
+ * 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)
+{
+ 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] 15+ messages in thread* [PATCH userspace 2/4] secilc: optimize policy before writing
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 1/4] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
@ 2019-05-23 10:24 ` Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 3/4] libsemanage: optimize policy on rebuild Ondrej Mosnacek
` (3 subsequent siblings)
5 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-23 10:24 UTC (permalink / raw)
To: selinux
Call sepol_policydb_optimize() on the final policydb before writing it
out. Also add a command-line flag to optionally skip this step.
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] 15+ messages in thread* [PATCH userspace 3/4] libsemanage: optimize policy on rebuild
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 1/4] libsepol: add a function to optimize kernel policy Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 2/4] secilc: optimize policy before writing Ondrej Mosnacek
@ 2019-05-23 10:24 ` Ondrej Mosnacek
2019-05-23 10:24 ` [PATCH userspace 4/4] semodule: add flag to disable policy optimization Ondrej Mosnacek
` (2 subsequent siblings)
5 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-23 10:24 UTC (permalink / raw)
To: selinux
When building binary policy, run it through sepol_policydb_optimize()
just before writing the final policy to disk.
Also add a semanage_set_optimize() function to allow skipping the
optimization step.
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..418c2c72 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 (default), 0 for no */
+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..0160ba18 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;
+ /* Optimize policy by default. If the policy is not
+ * being rebuilt, this flag is ignored. */
+ sh->do_optimize = 1;
+
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] 15+ messages in thread* [PATCH userspace 4/4] semodule: add flag to disable policy optimization
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
` (2 preceding siblings ...)
2019-05-23 10:24 ` [PATCH userspace 3/4] libsemanage: optimize policy on rebuild Ondrej Mosnacek
@ 2019-05-23 10:24 ` Ondrej Mosnacek
2019-05-23 13:14 ` [PATCH userspace 0/4] Remove redundant rules when building policydb Dominick Grift
2019-05-23 20:39 ` [Non-DoD Source] " jwcart2
5 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-23 10:24 UTC (permalink / raw)
To: selinux
Skip binary policy optimization on rebuild when the --no-optimize
command-line flag is given.
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
policycoreutils/semodule/semodule.c | 12 ++++++++++--
1 file changed, 10 insertions(+), 2 deletions(-)
diff --git a/policycoreutils/semodule/semodule.c b/policycoreutils/semodule/semodule.c
index a76797f5..f490ca2e 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 no_optimize;
static int disable_dontaudit;
static int preserve_tunables;
static int ignore_module_cache;
@@ -123,8 +124,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(" --no-optimize do not optimize built policy\n");
printf(" -D,--disable_dontaudit Remove dontaudits from policy\n");
printf(" -i,--install=MODULE_PKG install a new module\n");
printf(" -r,--remove=MODULE_NAME remove existing module at desired priority\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'},
+ {"no-optimize", 0, NULL, 'O'},
{"disable_dontaudit", 0, NULL, 'D'},
{"preserve_tunables", 0, NULL, 'P'},
{"ignore-module-cache", 0, NULL, 'C'},
@@ -268,6 +271,9 @@ static void parse_command_line(int argc, char **argv)
case 'B':
build = 1;
break;
+ case 'O':
+ no_optimize = 1;
+ break;
case 'D':
disable_dontaudit = 1;
break;
@@ -738,6 +744,8 @@ cleanup_disable:
semanage_set_reload(sh, 0);
if (build)
semanage_set_rebuild(sh, 1);
+ if (no_optimize)
+ semanage_set_optimize(sh, 0);
if (disable_dontaudit)
semanage_set_disable_dontaudit(sh, 1);
else if (build)
--
2.20.1
^ permalink raw reply related [flat|nested] 15+ messages in thread* Re: [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
` (3 preceding siblings ...)
2019-05-23 10:24 ` [PATCH userspace 4/4] semodule: add flag to disable policy optimization Ondrej Mosnacek
@ 2019-05-23 13:14 ` Dominick Grift
2019-05-23 13:39 ` Dominick Grift
2019-05-23 20:39 ` [Non-DoD Source] " jwcart2
5 siblings, 1 reply; 15+ messages in thread
From: Dominick Grift @ 2019-05-23 13:14 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: selinux
[-- Attachment #1: Type: text/plain, Size: 4051 bytes --]
On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> This series implements an optional optimization step when building
> a policydb via semodule or secilc, which identifies and removes rules
> that are redundant -- i.e. they are already covered by a more general
> rule based on attribute inheritance.
Some stats with dssp2-standard:
[kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
real 0m9.278s
user 0m7.036s
sys 0m2.017s
[kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
real 0m19.343s
user 0m16.939s
sys 0m2.027s
[kcinimod@myguest dssp2-standard]$ ls -lh policy.*
-rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
-rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
Was unable to see the actual diff as sediff got oom-killed on me
>
> Since the performance penalty of this additional step is very small
> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> it can have a big positive effect on the number of rules in policy
> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> optimization is enabled by default and can be turned off using a
> command-line option (--no-optimize) in secilc and semodule [2].
>
> The optimization routine eliminates:
> * all allow/neverallow/dontaudit/auditallow rules (including xperm
> variants) that are covered by another more general rule,
> * all conditional versions of the above rules that are covered by a
> more general rule either in the unconditional table or in the same
> branch of the same conditional.
>
> The optimization doesn't process other rules, since they currently
> do not support attributes. There is some room left for more precise
> optimization of conditional rules, but it would likely bring only
> little additional benefit.
>
> When the policy is mostly or fully expanded, the optimization should
> be turned off. If it isn't, the policy build time will increase a lot
> for no benefit. However, the complexity of optimization will be only
> linear w.r.t. the number of rules and so the impact should not be
> catastrophic. (When testing with secilc on a subset of Fedora policy
> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> without it.)
>
> Tested live on my Fedora 29 devel machine under normal use. No unusual
> AVCs were observed with optimized policy loaded.
>
> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>
> NOTE: The xperm rule support wasn't tested -- I would welcome some
> peer review/testing of this part.
>
> [1] As measured on my machine (Fedora 29 policy, x86_64).
> [2] I have no problem with switching it to opt-in if that is preferred.
>
> Ondrej Mosnacek (4):
> libsepol: add a function to optimize kernel policy
> secilc: optimize policy before writing
> libsemanage: optimize policy on rebuild
> semodule: add flag to disable policy optimization
>
> libsemanage/include/semanage/handle.h | 4 +
> libsemanage/src/direct_api.c | 7 +
> libsemanage/src/handle.c | 13 +
> libsemanage/src/handle.h | 1 +
> libsemanage/src/libsemanage.map | 5 +
> libsepol/include/sepol/policydb.h | 5 +
> libsepol/include/sepol/policydb/policydb.h | 2 +
> libsepol/src/libsepol.map.in | 5 +
> libsepol/src/optimize.c | 370 +++++++++++++++++++++
> libsepol/src/policydb_public.c | 5 +
> policycoreutils/semodule/semodule.c | 12 +-
> secilc/secilc.c | 16 +-
> 12 files changed, 442 insertions(+), 3 deletions(-)
> create mode 100644 libsepol/src/optimize.c
>
> --
> 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] 15+ messages in thread* Re: [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 13:14 ` [PATCH userspace 0/4] Remove redundant rules when building policydb Dominick Grift
@ 2019-05-23 13:39 ` Dominick Grift
2019-05-23 14:08 ` Ondrej Mosnacek
0 siblings, 1 reply; 15+ messages in thread
From: Dominick Grift @ 2019-05-23 13:39 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux
[-- Attachment #1: Type: text/plain, Size: 4643 bytes --]
On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> > This series implements an optional optimization step when building
> > a policydb via semodule or secilc, which identifies and removes rules
> > that are redundant -- i.e. they are already covered by a more general
> > rule based on attribute inheritance.
>
> Some stats with dssp2-standard:
>
> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
>
> real 0m9.278s
> user 0m7.036s
> sys 0m2.017s
> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
>
> real 0m19.343s
> user 0m16.939s
> sys 0m2.027s
> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
>
> Was unable to see the actual diff as sediff got oom-killed on me
According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
Looks like dssp2-standard is pretty efficient as it is.
>
> >
> > Since the performance penalty of this additional step is very small
> > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > it can have a big positive effect on the number of rules in policy
> > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > optimization is enabled by default and can be turned off using a
> > command-line option (--no-optimize) in secilc and semodule [2].
> >
> > The optimization routine eliminates:
> > * all allow/neverallow/dontaudit/auditallow rules (including xperm
> > variants) that are covered by another more general rule,
> > * all conditional versions of the above rules that are covered by a
> > more general rule either in the unconditional table or in the same
> > branch of the same conditional.
> >
> > The optimization doesn't process other rules, since they currently
> > do not support attributes. There is some room left for more precise
> > optimization of conditional rules, but it would likely bring only
> > little additional benefit.
> >
> > When the policy is mostly or fully expanded, the optimization should
> > be turned off. If it isn't, the policy build time will increase a lot
> > for no benefit. However, the complexity of optimization will be only
> > linear w.r.t. the number of rules and so the impact should not be
> > catastrophic. (When testing with secilc on a subset of Fedora policy
> > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > without it.)
> >
> > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > AVCs were observed with optimized policy loaded.
> >
> > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >
> > NOTE: The xperm rule support wasn't tested -- I would welcome some
> > peer review/testing of this part.
> >
> > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > [2] I have no problem with switching it to opt-in if that is preferred.
> >
> > Ondrej Mosnacek (4):
> > libsepol: add a function to optimize kernel policy
> > secilc: optimize policy before writing
> > libsemanage: optimize policy on rebuild
> > semodule: add flag to disable policy optimization
> >
> > libsemanage/include/semanage/handle.h | 4 +
> > libsemanage/src/direct_api.c | 7 +
> > libsemanage/src/handle.c | 13 +
> > libsemanage/src/handle.h | 1 +
> > libsemanage/src/libsemanage.map | 5 +
> > libsepol/include/sepol/policydb.h | 5 +
> > libsepol/include/sepol/policydb/policydb.h | 2 +
> > libsepol/src/libsepol.map.in | 5 +
> > libsepol/src/optimize.c | 370 +++++++++++++++++++++
> > libsepol/src/policydb_public.c | 5 +
> > policycoreutils/semodule/semodule.c | 12 +-
> > secilc/secilc.c | 16 +-
> > 12 files changed, 442 insertions(+), 3 deletions(-)
> > create mode 100644 libsepol/src/optimize.c
> >
> > --
> > 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
--
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] 15+ messages in thread
* Re: [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 13:39 ` Dominick Grift
@ 2019-05-23 14:08 ` Ondrej Mosnacek
2019-05-24 16:02 ` [Non-DoD Source] " jwcart2
0 siblings, 1 reply; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-23 14:08 UTC (permalink / raw)
To: Dominick Grift; +Cc: selinux
On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> > On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> > > This series implements an optional optimization step when building
> > > a policydb via semodule or secilc, which identifies and removes rules
> > > that are redundant -- i.e. they are already covered by a more general
> > > rule based on attribute inheritance.
> >
> > Some stats with dssp2-standard:
> >
> > [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
> >
> > real 0m9.278s
> > user 0m7.036s
> > sys 0m2.017s
> > [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
> >
> > real 0m19.343s
> > user 0m16.939s
> > sys 0m2.027s
> > [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> > -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> > -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
> >
> > Was unable to see the actual diff as sediff got oom-killed on me
>
> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
> Looks like dssp2-standard is pretty efficient as it is.
Hmm, yeah, looks like I'll have to make it opt-in after all... or add
some heuristic to decide if running the optimization is really worth
it.
>
> >
> > >
> > > Since the performance penalty of this additional step is very small
> > > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > > it can have a big positive effect on the number of rules in policy
> > > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > > optimization is enabled by default and can be turned off using a
> > > command-line option (--no-optimize) in secilc and semodule [2].
> > >
> > > The optimization routine eliminates:
> > > * all allow/neverallow/dontaudit/auditallow rules (including xperm
> > > variants) that are covered by another more general rule,
> > > * all conditional versions of the above rules that are covered by a
> > > more general rule either in the unconditional table or in the same
> > > branch of the same conditional.
> > >
> > > The optimization doesn't process other rules, since they currently
> > > do not support attributes. There is some room left for more precise
> > > optimization of conditional rules, but it would likely bring only
> > > little additional benefit.
> > >
> > > When the policy is mostly or fully expanded, the optimization should
> > > be turned off. If it isn't, the policy build time will increase a lot
> > > for no benefit. However, the complexity of optimization will be only
> > > linear w.r.t. the number of rules and so the impact should not be
> > > catastrophic. (When testing with secilc on a subset of Fedora policy
> > > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > > without it.)
> > >
> > > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > > AVCs were observed with optimized policy loaded.
> > >
> > > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> > >
> > > NOTE: The xperm rule support wasn't tested -- I would welcome some
> > > peer review/testing of this part.
> > >
> > > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > > [2] I have no problem with switching it to opt-in if that is preferred.
> > >
> > > Ondrej Mosnacek (4):
> > > libsepol: add a function to optimize kernel policy
> > > secilc: optimize policy before writing
> > > libsemanage: optimize policy on rebuild
> > > semodule: add flag to disable policy optimization
> > >
> > > libsemanage/include/semanage/handle.h | 4 +
> > > libsemanage/src/direct_api.c | 7 +
> > > libsemanage/src/handle.c | 13 +
> > > libsemanage/src/handle.h | 1 +
> > > libsemanage/src/libsemanage.map | 5 +
> > > libsepol/include/sepol/policydb.h | 5 +
> > > libsepol/include/sepol/policydb/policydb.h | 2 +
> > > libsepol/src/libsepol.map.in | 5 +
> > > libsepol/src/optimize.c | 370 +++++++++++++++++++++
> > > libsepol/src/policydb_public.c | 5 +
> > > policycoreutils/semodule/semodule.c | 12 +-
> > > secilc/secilc.c | 16 +-
> > > 12 files changed, 442 insertions(+), 3 deletions(-)
> > > create mode 100644 libsepol/src/optimize.c
> > >
> > > --
> > > 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
>
>
>
> --
> 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] 15+ messages in thread
* Re: [Non-DoD Source] Re: [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 14:08 ` Ondrej Mosnacek
@ 2019-05-24 16:02 ` jwcart2
2019-05-24 20:04 ` Ondrej Mosnacek
0 siblings, 1 reply; 15+ messages in thread
From: jwcart2 @ 2019-05-24 16:02 UTC (permalink / raw)
To: Ondrej Mosnacek, Dominick Grift; +Cc: selinux
On 5/23/19 10:08 AM, Ondrej Mosnacek wrote:
> On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
>> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
>>> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
>>>> This series implements an optional optimization step when building
>>>> a policydb via semodule or secilc, which identifies and removes rules
>>>> that are redundant -- i.e. they are already covered by a more general
>>>> rule based on attribute inheritance.
>>>
>>> Some stats with dssp2-standard:
>>>
>>> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
>>>
>>> real 0m9.278s
>>> user 0m7.036s
>>> sys 0m2.017s
>>> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
>>>
>>> real 0m19.343s
>>> user 0m16.939s
>>> sys 0m2.027s
>>> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
>>> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
>>> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
>>>
>>> Was unable to see the actual diff as sediff got oom-killed on me
>>
>> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
>> Looks like dssp2-standard is pretty efficient as it is.
>
> Hmm, yeah, looks like I'll have to make it opt-in after all... or add
> some heuristic to decide if running the optimization is really worth
> it.
>
Opt-in makes sense. How about just using 'O' for the option?
Jim
>>
>>>
>>>>
>>>> Since the performance penalty of this additional step is very small
>>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
>>>> it can have a big positive effect on the number of rules in policy
>>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
>>>> optimization is enabled by default and can be turned off using a
>>>> command-line option (--no-optimize) in secilc and semodule [2].
>>>>
>>>> The optimization routine eliminates:
>>>> * all allow/neverallow/dontaudit/auditallow rules (including xperm
>>>> variants) that are covered by another more general rule,
>>>> * all conditional versions of the above rules that are covered by a
>>>> more general rule either in the unconditional table or in the same
>>>> branch of the same conditional.
>>>>
>>>> The optimization doesn't process other rules, since they currently
>>>> do not support attributes. There is some room left for more precise
>>>> optimization of conditional rules, but it would likely bring only
>>>> little additional benefit.
>>>>
>>>> When the policy is mostly or fully expanded, the optimization should
>>>> be turned off. If it isn't, the policy build time will increase a lot
>>>> for no benefit. However, the complexity of optimization will be only
>>>> linear w.r.t. the number of rules and so the impact should not be
>>>> catastrophic. (When testing with secilc on a subset of Fedora policy
>>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
>>>> without it.)
>>>>
>>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
>>>> AVCs were observed with optimized policy loaded.
>>>>
>>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>>>>
>>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
>>>> peer review/testing of this part.
>>>>
>>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
>>>> [2] I have no problem with switching it to opt-in if that is preferred.
>>>>
>>>> Ondrej Mosnacek (4):
>>>> libsepol: add a function to optimize kernel policy
>>>> secilc: optimize policy before writing
>>>> libsemanage: optimize policy on rebuild
>>>> semodule: add flag to disable policy optimization
>>>>
>>>> libsemanage/include/semanage/handle.h | 4 +
>>>> libsemanage/src/direct_api.c | 7 +
>>>> libsemanage/src/handle.c | 13 +
>>>> libsemanage/src/handle.h | 1 +
>>>> libsemanage/src/libsemanage.map | 5 +
>>>> libsepol/include/sepol/policydb.h | 5 +
>>>> libsepol/include/sepol/policydb/policydb.h | 2 +
>>>> libsepol/src/libsepol.map.in | 5 +
>>>> libsepol/src/optimize.c | 370 +++++++++++++++++++++
>>>> libsepol/src/policydb_public.c | 5 +
>>>> policycoreutils/semodule/semodule.c | 12 +-
>>>> secilc/secilc.c | 16 +-
>>>> 12 files changed, 442 insertions(+), 3 deletions(-)
>>>> create mode 100644 libsepol/src/optimize.c
>>>>
>>>> --
>>>> 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
>>
>>
>>
>> --
>> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
>> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
>> Dominick Grift
>
>
>
--
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [Non-DoD Source] Re: [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-24 16:02 ` [Non-DoD Source] " jwcart2
@ 2019-05-24 20:04 ` Ondrej Mosnacek
0 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-24 20:04 UTC (permalink / raw)
To: jwcart2; +Cc: Dominick Grift, selinux
On Fri, May 24, 2019 at 6:02 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/23/19 10:08 AM, Ondrej Mosnacek wrote:
> > On Thu, May 23, 2019 at 3:40 PM Dominick Grift <dac.override@gmail.com> wrote:
> >> On Thu, May 23, 2019 at 03:14:55PM +0200, Dominick Grift wrote:
> >>> On Thu, May 23, 2019 at 12:24:45PM +0200, Ondrej Mosnacek wrote:
> >>>> This series implements an optional optimization step when building
> >>>> a policydb via semodule or secilc, which identifies and removes rules
> >>>> that are redundant -- i.e. they are already covered by a more general
> >>>> rule based on attribute inheritance.
> >>>
> >>> Some stats with dssp2-standard:
> >>>
> >>> [kcinimod@myguest dssp2-standard]$ time secilc -n `find . -name *.cil` -o policy.31.noopt
> >>>
> >>> real 0m9.278s
> >>> user 0m7.036s
> >>> sys 0m2.017s
> >>> [kcinimod@myguest dssp2-standard]$ time secilc `find . -name *.cil` -o policy.31.opt
> >>>
> >>> real 0m19.343s
> >>> user 0m16.939s
> >>> sys 0m2.027s
> >>> [kcinimod@myguest dssp2-standard]$ ls -lh policy.*
> >>> -rw-rw-r--. 1 kcinimod kcinimod 2.4M May 23 15:11 policy.31.noopt
> >>> -rw-rw-r--. 1 kcinimod kcinimod 2.3M May 23 15:12 policy.31.opt
> >>>
> >>> Was unable to see the actual diff as sediff got oom-killed on me
> >>
> >> According to percentage calculator thats roughly a 4 percent gain size-wise at a 47 percent performance penalty.
> >> Looks like dssp2-standard is pretty efficient as it is.
> >
> > Hmm, yeah, looks like I'll have to make it opt-in after all... or add
> > some heuristic to decide if running the optimization is really worth
> > it.
> >
>
> Opt-in makes sense. How about just using 'O' for the option?
Sure, I already have patches to convert to opt-in ready in my devel
branch [1]. Expect them to be incorporated in v2 respin.
[1] https://github.com/WOnder93/selinux/compare/master...optimize-policy-v2
>
> Jim
>
> >>
> >>>
> >>>>
> >>>> Since the performance penalty of this additional step is very small
> >>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> >>>> it can have a big positive effect on the number of rules in policy
> >>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> >>>> optimization is enabled by default and can be turned off using a
> >>>> command-line option (--no-optimize) in secilc and semodule [2].
> >>>>
> >>>> The optimization routine eliminates:
> >>>> * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >>>> variants) that are covered by another more general rule,
> >>>> * all conditional versions of the above rules that are covered by a
> >>>> more general rule either in the unconditional table or in the same
> >>>> branch of the same conditional.
> >>>>
> >>>> The optimization doesn't process other rules, since they currently
> >>>> do not support attributes. There is some room left for more precise
> >>>> optimization of conditional rules, but it would likely bring only
> >>>> little additional benefit.
> >>>>
> >>>> When the policy is mostly or fully expanded, the optimization should
> >>>> be turned off. If it isn't, the policy build time will increase a lot
> >>>> for no benefit. However, the complexity of optimization will be only
> >>>> linear w.r.t. the number of rules and so the impact should not be
> >>>> catastrophic. (When testing with secilc on a subset of Fedora policy
> >>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> >>>> without it.)
> >>>>
> >>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
> >>>> AVCs were observed with optimized policy loaded.
> >>>>
> >>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >>>>
> >>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
> >>>> peer review/testing of this part.
> >>>>
> >>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
> >>>> [2] I have no problem with switching it to opt-in if that is preferred.
> >>>>
> >>>> Ondrej Mosnacek (4):
> >>>> libsepol: add a function to optimize kernel policy
> >>>> secilc: optimize policy before writing
> >>>> libsemanage: optimize policy on rebuild
> >>>> semodule: add flag to disable policy optimization
> >>>>
> >>>> libsemanage/include/semanage/handle.h | 4 +
> >>>> libsemanage/src/direct_api.c | 7 +
> >>>> libsemanage/src/handle.c | 13 +
> >>>> libsemanage/src/handle.h | 1 +
> >>>> libsemanage/src/libsemanage.map | 5 +
> >>>> libsepol/include/sepol/policydb.h | 5 +
> >>>> libsepol/include/sepol/policydb/policydb.h | 2 +
> >>>> libsepol/src/libsepol.map.in | 5 +
> >>>> libsepol/src/optimize.c | 370 +++++++++++++++++++++
> >>>> libsepol/src/policydb_public.c | 5 +
> >>>> policycoreutils/semodule/semodule.c | 12 +-
> >>>> secilc/secilc.c | 16 +-
> >>>> 12 files changed, 442 insertions(+), 3 deletions(-)
> >>>> create mode 100644 libsepol/src/optimize.c
> >>>>
> >>>> --
> >>>> 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
> >>
> >>
> >>
> >> --
> >> Key fingerprint = 5F4D 3CDB D3F8 3652 FBD8 02D5 3B6C 5F1D 2C7B 6B02
> >> https://sks-keyservers.net/pks/lookup?op=get&search=0x3B6C5F1D2C7B6B02
> >> Dominick Grift
> >
> >
> >
>
>
> --
> 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] 15+ messages in thread
* Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 10:24 [PATCH userspace 0/4] Remove redundant rules when building policydb Ondrej Mosnacek
` (4 preceding siblings ...)
2019-05-23 13:14 ` [PATCH userspace 0/4] Remove redundant rules when building policydb Dominick Grift
@ 2019-05-23 20:39 ` jwcart2
2019-05-24 8:54 ` Ondrej Mosnacek
2019-05-27 17:11 ` Chris PeBenito
5 siblings, 2 replies; 15+ messages in thread
From: jwcart2 @ 2019-05-23 20:39 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux
On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> This series implements an optional optimization step when building
> a policydb via semodule or secilc, which identifies and removes rules
> that are redundant -- i.e. they are already covered by a more general
> rule based on attribute inheritance.
>
> Since the performance penalty of this additional step is very small
> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> it can have a big positive effect on the number of rules in policy
> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> optimization is enabled by default and can be turned off using a
> command-line option (--no-optimize) in secilc and semodule [2].
>
> The optimization routine eliminates:
> * all allow/neverallow/dontaudit/auditallow rules (including xperm
> variants) that are covered by another more general rule,
> * all conditional versions of the above rules that are covered by a
> more general rule either in the unconditional table or in the same
> branch of the same conditional.
>
> The optimization doesn't process other rules, since they currently
> do not support attributes. There is some room left for more precise
> optimization of conditional rules, but it would likely bring only
> little additional benefit.
>
> When the policy is mostly or fully expanded, the optimization should
> be turned off. If it isn't, the policy build time will increase a lot
> for no benefit. However, the complexity of optimization will be only
> linear w.r.t. the number of rules and so the impact should not be
> catastrophic. (When testing with secilc on a subset of Fedora policy
> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> without it.)
>
> Tested live on my Fedora 29 devel machine under normal use. No unusual
> AVCs were observed with optimized policy loaded.
>
> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>
> NOTE: The xperm rule support wasn't tested -- I would welcome some
> peer review/testing of this part.
>
> [1] As measured on my machine (Fedora 29 policy, x86_64).
> [2] I have no problem with switching it to opt-in if that is preferred.
>
> Ondrej Mosnacek (4):
> libsepol: add a function to optimize kernel policy
> secilc: optimize policy before writing
> libsemanage: optimize policy on rebuild
> semodule: add flag to disable policy optimization
>
> libsemanage/include/semanage/handle.h | 4 +
> libsemanage/src/direct_api.c | 7 +
> libsemanage/src/handle.c | 13 +
> libsemanage/src/handle.h | 1 +
> libsemanage/src/libsemanage.map | 5 +
> libsepol/include/sepol/policydb.h | 5 +
> libsepol/include/sepol/policydb/policydb.h | 2 +
> libsepol/src/libsepol.map.in | 5 +
> libsepol/src/optimize.c | 370 +++++++++++++++++++++
> libsepol/src/policydb_public.c | 5 +
> policycoreutils/semodule/semodule.c | 12 +-
> secilc/secilc.c | 16 +-
> 12 files changed, 442 insertions(+), 3 deletions(-)
> create mode 100644 libsepol/src/optimize.c
>
It would be nice to have checkpolicy support this as well. It shouldn't be too
hard to do that.
I need to do some more testing, but I think something is not working correctly.
I am starting from conf files here because I have both Fedora and Android ones
that I have used for testing and it is easier to run them through checkpolicy to
convert to CIL.
With these rules:
# Redundant 1
allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
allow tp02 tpr1:cl01 { p01a p11a };
allow at02 tpr1:cl01 { p01a p11a p01b };
# Redundant 2
dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr2:cl01 { p01a p11a };
dontaudit at02 tpr2:cl01 { p01a p11a p01b };
# Redundant 3
allow at02 tpr3:cl01 { p01a p11a p01b };
if (b01) {
allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
allow tp02 tpr3:cl01 { p01a p11a };
}
# Redundant 4
dontaudit at02 tpr4:cl01 { p01a p11a p01b };
if (b01) {
dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr4:cl01 { p01a p11a };
}
I see the following from sediff:
Allow Rules (0 Added, 1 Removed, 0 Modified)
Removed Allow Rules: 1
- allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
Removed Dontaudit Rules: 1
- dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
Modified Dontaudit Rules: 1
* dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
So it handles Redundant 1 just fine, but has problems with Redundant 2 which
should be the same.
I don't remember what to expect from sediff for boolean rules. I had played
around with removing rules with some of my earlier lua tools and I thought that
sediff handled removing redundant rules from booleans, but I could be wrong.
I will look at this more maybe tomorrow, but most likely after the Memorial day
weekend.
Jim
--
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 20:39 ` [Non-DoD Source] " jwcart2
@ 2019-05-24 8:54 ` Ondrej Mosnacek
2019-05-24 16:01 ` jwcart2
2019-05-27 17:11 ` Chris PeBenito
1 sibling, 1 reply; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-24 8:54 UTC (permalink / raw)
To: jwcart2; +Cc: selinux
On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> > This series implements an optional optimization step when building
> > a policydb via semodule or secilc, which identifies and removes rules
> > that are redundant -- i.e. they are already covered by a more general
> > rule based on attribute inheritance.
> >
> > Since the performance penalty of this additional step is very small
> > (it adds about 1 s to the current running time of ~20-30 s [1]) and
> > it can have a big positive effect on the number of rules in policy
> > (it manages to remove ~40% AV rules from Fedora 29 policy), the
> > optimization is enabled by default and can be turned off using a
> > command-line option (--no-optimize) in secilc and semodule [2].
> >
> > The optimization routine eliminates:
> > * all allow/neverallow/dontaudit/auditallow rules (including xperm
> > variants) that are covered by another more general rule,
> > * all conditional versions of the above rules that are covered by a
> > more general rule either in the unconditional table or in the same
> > branch of the same conditional.
> >
> > The optimization doesn't process other rules, since they currently
> > do not support attributes. There is some room left for more precise
> > optimization of conditional rules, but it would likely bring only
> > little additional benefit.
> >
> > When the policy is mostly or fully expanded, the optimization should
> > be turned off. If it isn't, the policy build time will increase a lot
> > for no benefit. However, the complexity of optimization will be only
> > linear w.r.t. the number of rules and so the impact should not be
> > catastrophic. (When testing with secilc on a subset of Fedora policy
> > with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> > without it.)
> >
> > Tested live on my Fedora 29 devel machine under normal use. No unusual
> > AVCs were observed with optimized policy loaded.
> >
> > Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >
> > NOTE: The xperm rule support wasn't tested -- I would welcome some
> > peer review/testing of this part.
> >
> > [1] As measured on my machine (Fedora 29 policy, x86_64).
> > [2] I have no problem with switching it to opt-in if that is preferred.
> >
> > Ondrej Mosnacek (4):
> > libsepol: add a function to optimize kernel policy
> > secilc: optimize policy before writing
> > libsemanage: optimize policy on rebuild
> > semodule: add flag to disable policy optimization
> >
> > libsemanage/include/semanage/handle.h | 4 +
> > libsemanage/src/direct_api.c | 7 +
> > libsemanage/src/handle.c | 13 +
> > libsemanage/src/handle.h | 1 +
> > libsemanage/src/libsemanage.map | 5 +
> > libsepol/include/sepol/policydb.h | 5 +
> > libsepol/include/sepol/policydb/policydb.h | 2 +
> > libsepol/src/libsepol.map.in | 5 +
> > libsepol/src/optimize.c | 370 +++++++++++++++++++++
> > libsepol/src/policydb_public.c | 5 +
> > policycoreutils/semodule/semodule.c | 12 +-
> > secilc/secilc.c | 16 +-
> > 12 files changed, 442 insertions(+), 3 deletions(-)
> > create mode 100644 libsepol/src/optimize.c
> >
>
> It would be nice to have checkpolicy support this as well. It shouldn't be too
> hard to do that.
Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
or POLICY_MODULE policy types. I currently limit the optimization only
to POLICY_KERN type, because from comments in policydb.h I got the
impression that other policy types have different structure and I'm
not sure if they need some special handling. I don't have that much
knowledge about SELinux userspace code yet... if you can give me some
hints about the difference between the various POLICY_* types, then I
will be happy to make some adjustments if they make sense.
>
> I need to do some more testing, but I think something is not working correctly.
>
> I am starting from conf files here because I have both Fedora and Android ones
> that I have used for testing and it is easier to run them through checkpolicy to
> convert to CIL.
>
> With these rules:
>
> # Redundant 1
> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr1:cl01 { p01a p11a };
> allow at02 tpr1:cl01 { p01a p11a p01b };
>
> # Redundant 2
> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr2:cl01 { p01a p11a };
> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
>
> # Redundant 3
> allow at02 tpr3:cl01 { p01a p11a p01b };
> if (b01) {
> allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr3:cl01 { p01a p11a };
> }
>
> # Redundant 4
> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> if (b01) {
> dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr4:cl01 { p01a p11a };
> }
>
>
> I see the following from sediff:
>
> Allow Rules (0 Added, 1 Removed, 0 Modified)
> Removed Allow Rules: 1
> - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
>
> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
> Removed Dontaudit Rules: 1
> - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
> Modified Dontaudit Rules: 1
> * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
>
> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
> should be the same.
Yes, I think I'm handling the dontaudit rules incorrectly... For some
(historical?) reason they actually specify the permissions that *are*
audited, although the semantic of combining multiple rules is still
that a permission is dontaudited if there is at least one dontaudit
rule for it, so the logic of handling the raw perms data has to be
inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
AVTAB_AUDITDENY rules are handled differently but somehow I concluded
that the perms values should still bitwise-or together...
Can you please try it with adding:
if (specified & AVTAB_AUDITDENY)
return (d1->data & d2->data) == d2->data;
to the beginning of match_avtab_datum() in optimize.c? (patch form
here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)
>
> I don't remember what to expect from sediff for boolean rules. I had played
> around with removing rules with some of my earlier lua tools and I thought that
> sediff handled removing redundant rules from booleans, but I could be wrong.
>
> I will look at this more maybe tomorrow, but most likely after the Memorial day
> weekend.
>
> Jim
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-24 8:54 ` Ondrej Mosnacek
@ 2019-05-24 16:01 ` jwcart2
2019-05-24 20:00 ` Ondrej Mosnacek
0 siblings, 1 reply; 15+ messages in thread
From: jwcart2 @ 2019-05-24 16:01 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: selinux
[-- Attachment #1: Type: text/plain, Size: 7424 bytes --]
On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
> On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
>> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
>>> This series implements an optional optimization step when building
>>> a policydb via semodule or secilc, which identifies and removes rules
>>> that are redundant -- i.e. they are already covered by a more general
>>> rule based on attribute inheritance.
>>>
>>> Since the performance penalty of this additional step is very small
>>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
>>> it can have a big positive effect on the number of rules in policy
>>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
>>> optimization is enabled by default and can be turned off using a
>>> command-line option (--no-optimize) in secilc and semodule [2].
>>>
>>> The optimization routine eliminates:
>>> * all allow/neverallow/dontaudit/auditallow rules (including xperm
>>> variants) that are covered by another more general rule,
>>> * all conditional versions of the above rules that are covered by a
>>> more general rule either in the unconditional table or in the same
>>> branch of the same conditional.
>>>
>>> The optimization doesn't process other rules, since they currently
>>> do not support attributes. There is some room left for more precise
>>> optimization of conditional rules, but it would likely bring only
>>> little additional benefit.
>>>
>>> When the policy is mostly or fully expanded, the optimization should
>>> be turned off. If it isn't, the policy build time will increase a lot
>>> for no benefit. However, the complexity of optimization will be only
>>> linear w.r.t. the number of rules and so the impact should not be
>>> catastrophic. (When testing with secilc on a subset of Fedora policy
>>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
>>> without it.)
>>>
>>> Tested live on my Fedora 29 devel machine under normal use. No unusual
>>> AVCs were observed with optimized policy loaded.
>>>
>>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
>>>
>>> NOTE: The xperm rule support wasn't tested -- I would welcome some
>>> peer review/testing of this part.
>>>
>>> [1] As measured on my machine (Fedora 29 policy, x86_64).
>>> [2] I have no problem with switching it to opt-in if that is preferred.
>>>
>>> Ondrej Mosnacek (4):
>>> libsepol: add a function to optimize kernel policy
>>> secilc: optimize policy before writing
>>> libsemanage: optimize policy on rebuild
>>> semodule: add flag to disable policy optimization
>>>
>>> libsemanage/include/semanage/handle.h | 4 +
>>> libsemanage/src/direct_api.c | 7 +
>>> libsemanage/src/handle.c | 13 +
>>> libsemanage/src/handle.h | 1 +
>>> libsemanage/src/libsemanage.map | 5 +
>>> libsepol/include/sepol/policydb.h | 5 +
>>> libsepol/include/sepol/policydb/policydb.h | 2 +
>>> libsepol/src/libsepol.map.in | 5 +
>>> libsepol/src/optimize.c | 370 +++++++++++++++++++++
>>> libsepol/src/policydb_public.c | 5 +
>>> policycoreutils/semodule/semodule.c | 12 +-
>>> secilc/secilc.c | 16 +-
>>> 12 files changed, 442 insertions(+), 3 deletions(-)
>>> create mode 100644 libsepol/src/optimize.c
>>>
>>
>> It would be nice to have checkpolicy support this as well. It shouldn't be too
>> hard to do that.
>
> Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
> or POLICY_MODULE policy types. I currently limit the optimization only
> to POLICY_KERN type, because from comments in policydb.h I got the
> impression that other policy types have different structure and I'm
> not sure if they need some special handling. I don't have that much
> knowledge about SELinux userspace code yet... if you can give me some
> hints about the difference between the various POLICY_* types, then I
> will be happy to make some adjustments if they make sense.
>
It is kind of confusing. I sent a patch to the list. You can incorporate that
into your patch series or I can just do it after.
I've attached the test policy that I used and a test script. I haven't had a
chance to dig more into what may be going on.
Jim
>>
>> I need to do some more testing, but I think something is not working correctly.
>>
>> I am starting from conf files here because I have both Fedora and Android ones
>> that I have used for testing and it is easier to run them through checkpolicy to
>> convert to CIL.
>>
>> With these rules:
>>
>> # Redundant 1
>> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
>> allow tp02 tpr1:cl01 { p01a p11a };
>> allow at02 tpr1:cl01 { p01a p11a p01b };
>>
>> # Redundant 2
>> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
>> dontaudit tp02 tpr2:cl01 { p01a p11a };
>> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
>>
>> # Redundant 3
>> allow at02 tpr3:cl01 { p01a p11a p01b };
>> if (b01) {
>> allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
>> allow tp02 tpr3:cl01 { p01a p11a };
>> }
>>
>> # Redundant 4
>> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
>> if (b01) {
>> dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
>> dontaudit tp02 tpr4:cl01 { p01a p11a };
>> }
>>
>>
>> I see the following from sediff:
>>
>> Allow Rules (0 Added, 1 Removed, 0 Modified)
>> Removed Allow Rules: 1
>> - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
>>
>> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
>> Removed Dontaudit Rules: 1
>> - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
>> Modified Dontaudit Rules: 1
>> * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
>>
>> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
>> should be the same.
>
> Yes, I think I'm handling the dontaudit rules incorrectly... For some
> (historical?) reason they actually specify the permissions that *are*
> audited, although the semantic of combining multiple rules is still
> that a permission is dontaudited if there is at least one dontaudit
> rule for it, so the logic of handling the raw perms data has to be
> inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
> AVTAB_AUDITDENY rules are handled differently but somehow I concluded
> that the perms values should still bitwise-or together...
>
> Can you please try it with adding:
>
> if (specified & AVTAB_AUDITDENY)
> return (d1->data & d2->data) == d2->data;
>
> to the beginning of match_avtab_datum() in optimize.c? (patch form
> here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)
>
>>
>> I don't remember what to expect from sediff for boolean rules. I had played
>> around with removing rules with some of my earlier lua tools and I thought that
>> sediff handled removing redundant rules from booleans, but I could be wrong.
>>
>> I will look at this more maybe tomorrow, but most likely after the Memorial day
>> weekend.
>>
>> Jim
>>
>> --
>> James Carter <jwcart2@tycho.nsa.gov>
>> National Security Agency
> --
> Ondrej Mosnacek <omosnace at redhat dot com>
> Software Engineer, Security Technologies
> Red Hat, Inc.
>
--
James Carter <jwcart2@tycho.nsa.gov>
National Security Agency
[-- Attachment #2: test_01.conf --]
[-- Type: text/plain, Size: 4295 bytes --]
# All policy.conf rules
# Called test_02.conf in expected_pass/conf
# Added redundantallow rules that are covered by attribute
class cl01
class cl02
class cl03
class cl04
class clx
sid kernel
sid security
sid unlabeled
common cm01 { p11a p11b }
common cm02 { p22a p22b }
class cl01 inherits cm01 { p01a p01b }
class cl02 inherits cm02
class cl03 { p03a p03b }
class cl04 { p04a p04b }
class clx { ioctl }
default_user { cl01 cl02 cl03 } source;
default_role { cl01 } source;
default_type { cl02 } target;
default_range { cl03 } target low-high;
sensitivity s01 alias syslow;
sensitivity s02;
sensitivity s03 alias { syshigh maxsens };
dominance { s01 s02 s03 }
category c01 alias cat01;
category c02 alias { cat02a cat02b };
category c03;
level s01;
level s02:c01,c03;
level s03:c01.c03;
mlsconstrain cl01 { p01a } ((h1 dom h2) and (l1 domby h1));
mlsvalidatetrans cl02 ((l1 eq l2) or (l1 incomp l2));
mlsvalidatetrans cl02 ((l1 eq l2) or (t3 eq tpo));
policycap network_peer_controls;
policycap open_perms;
attribute at01;
attribute at02;
attribute_role ar01;
attribute_role ar02;
bool b01 false;
bool b02 true;
type tpo;
type tpx;
type tp01;
type tp02;
type tp03p;
type tp03c;
type tp04;
type tpr1;
type tpr2;
type tpr3;
type tpr4;
type tpr5;
typealias tp01 alias { ta01a ta01b };
typealias tp02 alias ta02;
typebounds tp03p tp03c;
typeattribute tp01 at01, at02;
typeattribute tp02 at02;
permissive tp01;
allow tp01 self:cl01 { p01a p11a };
allow tp01 ta01a:cl01 p01b;
allow tp01 at01:cl01 p11b;
allow tp01 tpo:cl02 p22a;
allow at02 tpo:cl02 p22b;
allow tp03p tpo:cl03 { p03a p03b };
allow tp03c tpo:cl03 p03a;
allow tp04 tpx:clx ioctl;
auditallow tp01 tpo:cl01 p01a;
dontaudit tp01 tpo:cl01 p01b;
neverallow tp01 tpo:cl01 p11a;
# Redundant 1
allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
allow tp02 tpr1:cl01 { p01a p11a };
allow at02 tpr1:cl01 { p01a p11a p01b };
# Redundant 2
dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr2:cl01 { p01a p11a };
dontaudit at02 tpr2:cl01 { p01a p11a p01b };
# Redundant 3
allow at02 tpr3:cl01 { p01a p11a p01b };
if (b01) {
allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
allow tp02 tpr3:cl01 { p01a p11a };
}
# Redundant 4
dontaudit at02 tpr4:cl01 { p01a p11a p01b };
if (b01) {
dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
dontaudit tp02 tpr4:cl01 { p01a p11a };
}
# Redundant 5
if (b01) {
allow tp01 tpr5:cl01 { p01a p11a p01b p11b };
allow tp02 tpr5:cl01 { p01a p11a };
} else {
allow at02 tpr5:cl01 { p01a p11a p01b };
}
allowxperm tp04 tpx:clx ioctl 0x1234;
auditallowxperm tp04 tpx:clx ioctl 0x9911;
dontauditxperm tp04 tpx:clx ioctl 0x9922;
neverallowxperm tp04 tpx:clx ioctl 0x9933;
type_transition tp01 tpo:cl01 tp02;
type_member tp01 tpo:cl02 tp02;
type_change tp01 tpo:cl03 tp02;
type_transition tp01 tpo:cl04 tp02 "file01";
range_transition tp01 tpo:cl01 s02;
range_transition tp01 tpo:cl02 s02 - s03:c01,cat02a;
role rl01;
role rl02;
role rl03p;
role rl03c;
role rl01 types { tp01 tp02 };
role rl02 types { tp02 };
role rl03p types tp03p;
role rl03c types tp03c;
roleattribute rl01 ar01, ar02;
roleattribute rl02 ar02;
allow rl01 rl02;
role_transition rl01 tpo:cl01 rl02;
user us01 roles rl01 level s01 range s01 - s03:c01.c03;
constrain cl01 { p01b } not ((t1 == tpo) and (u1 != u2));
validatetrans cl02 ((u1 == u2) or (r1 == r2));
validatetrans cl02 ((u1 == u2) or (t3 == tpo));
sid kernel us01:rl01:tp01:syslow - syshigh:c01,cat02b,c03
sid security us01:rl01:tp01:s01 - s02
sid unlabeled us01:rl01:tp01:s02:c01,c03 - maxsens:cat01,c03
fs_use_xattr fs01 us01:rl01:tp01:s01;
fs_use_task fs02 us01:rl01:tp01:s01;
fs_use_trans fs03 us01:rl01:tp01:s01;
genfscon fs04 / us01:rl01:tp01:s01
portcon udp 1000 us01:rl01:tp01:s01
portcon udp 1001-1009 us01:rl01:tp01:s01
portcon tcp 2000 us01:rl01:tp01:s01
portcon tcp 2001-2009 us01:rl01:tp01:s01
portcon dccp 3000 us01:rl01:tp01:s01
portcon dccp 3001-3009 us01:rl01:tp01:s01
netifcon if01 us01:rl01:tp01:s01 us01:rl01:tp02:s01
nodecon 10.0.0.1 255.255.255.0 us01:rl01:tp01:s01
nodecon fc00::1 fc00::ffff us01:rl01:tp01:s01
# XEN
#pirqcon 65535 us01:rl01:tp01:s01
#iomemcon 0-99999 us01:rl01:tp01:s01
#ioportcon 0-99999 us01:rl01:tp01:s01
#pcidevicecon 99999 us01:rl01:tp01:s01
#devicetreecon "/PATH" us01:rl01:tp01:s01
[-- Attachment #3: test.sh --]
[-- Type: application/x-shellscript, Size: 990 bytes --]
^ permalink raw reply [flat|nested] 15+ messages in thread* Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-24 16:01 ` jwcart2
@ 2019-05-24 20:00 ` Ondrej Mosnacek
0 siblings, 0 replies; 15+ messages in thread
From: Ondrej Mosnacek @ 2019-05-24 20:00 UTC (permalink / raw)
To: jwcart2; +Cc: selinux
On Fri, May 24, 2019 at 6:01 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> On 5/24/19 4:54 AM, Ondrej Mosnacek wrote:
> > On Thu, May 23, 2019 at 10:39 PM jwcart2 <jwcart2@tycho.nsa.gov> wrote:
> >> On 5/23/19 6:24 AM, Ondrej Mosnacek wrote:
> >>> This series implements an optional optimization step when building
> >>> a policydb via semodule or secilc, which identifies and removes rules
> >>> that are redundant -- i.e. they are already covered by a more general
> >>> rule based on attribute inheritance.
> >>>
> >>> Since the performance penalty of this additional step is very small
> >>> (it adds about 1 s to the current running time of ~20-30 s [1]) and
> >>> it can have a big positive effect on the number of rules in policy
> >>> (it manages to remove ~40% AV rules from Fedora 29 policy), the
> >>> optimization is enabled by default and can be turned off using a
> >>> command-line option (--no-optimize) in secilc and semodule [2].
> >>>
> >>> The optimization routine eliminates:
> >>> * all allow/neverallow/dontaudit/auditallow rules (including xperm
> >>> variants) that are covered by another more general rule,
> >>> * all conditional versions of the above rules that are covered by a
> >>> more general rule either in the unconditional table or in the same
> >>> branch of the same conditional.
> >>>
> >>> The optimization doesn't process other rules, since they currently
> >>> do not support attributes. There is some room left for more precise
> >>> optimization of conditional rules, but it would likely bring only
> >>> little additional benefit.
> >>>
> >>> When the policy is mostly or fully expanded, the optimization should
> >>> be turned off. If it isn't, the policy build time will increase a lot
> >>> for no benefit. However, the complexity of optimization will be only
> >>> linear w.r.t. the number of rules and so the impact should not be
> >>> catastrophic. (When testing with secilc on a subset of Fedora policy
> >>> with -X 100000 the build time was 1.7 s with optimization vs. 1 s
> >>> without it.)
> >>>
> >>> Tested live on my Fedora 29 devel machine under normal use. No unusual
> >>> AVCs were observed with optimized policy loaded.
> >>>
> >>> Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/536157427
> >>>
> >>> NOTE: The xperm rule support wasn't tested -- I would welcome some
> >>> peer review/testing of this part.
> >>>
> >>> [1] As measured on my machine (Fedora 29 policy, x86_64).
> >>> [2] I have no problem with switching it to opt-in if that is preferred.
> >>>
> >>> Ondrej Mosnacek (4):
> >>> libsepol: add a function to optimize kernel policy
> >>> secilc: optimize policy before writing
> >>> libsemanage: optimize policy on rebuild
> >>> semodule: add flag to disable policy optimization
> >>>
> >>> libsemanage/include/semanage/handle.h | 4 +
> >>> libsemanage/src/direct_api.c | 7 +
> >>> libsemanage/src/handle.c | 13 +
> >>> libsemanage/src/handle.h | 1 +
> >>> libsemanage/src/libsemanage.map | 5 +
> >>> libsepol/include/sepol/policydb.h | 5 +
> >>> libsepol/include/sepol/policydb/policydb.h | 2 +
> >>> libsepol/src/libsepol.map.in | 5 +
> >>> libsepol/src/optimize.c | 370 +++++++++++++++++++++
> >>> libsepol/src/policydb_public.c | 5 +
> >>> policycoreutils/semodule/semodule.c | 12 +-
> >>> secilc/secilc.c | 16 +-
> >>> 12 files changed, 442 insertions(+), 3 deletions(-)
> >>> create mode 100644 libsepol/src/optimize.c
> >>>
> >>
> >> It would be nice to have checkpolicy support this as well. It shouldn't be too
> >> hard to do that.
> >
> > Looking at checkpolicy.c, it looks like it only generates POLICY_BASE
> > or POLICY_MODULE policy types. I currently limit the optimization only
> > to POLICY_KERN type, because from comments in policydb.h I got the
> > impression that other policy types have different structure and I'm
> > not sure if they need some special handling. I don't have that much
> > knowledge about SELinux userspace code yet... if you can give me some
> > hints about the difference between the various POLICY_* types, then I
> > will be happy to make some adjustments if they make sense.
> >
>
> It is kind of confusing. I sent a patch to the list. You can incorporate that
> into your patch series or I can just do it after.
Thanks, I'll have a look at it and probably just include in v2.
>
> I've attached the test policy that I used and a test script. I haven't had a
> chance to dig more into what may be going on.
Cool, this test policy will also help me test the xperms support,
thanks! I will play with it tomorrow or on Monday.
I'm ~95% sure that my incremental patch will fix the dontaudit issue -
if I manage to verify it, then I'll squash it in and include in v2.
>
> Jim
>
>
> >>
> >> I need to do some more testing, but I think something is not working correctly.
> >>
> >> I am starting from conf files here because I have both Fedora and Android ones
> >> that I have used for testing and it is easier to run them through checkpolicy to
> >> convert to CIL.
> >>
> >> With these rules:
> >>
> >> # Redundant 1
> >> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> >> allow tp02 tpr1:cl01 { p01a p11a };
> >> allow at02 tpr1:cl01 { p01a p11a p01b };
> >>
> >> # Redundant 2
> >> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> >> dontaudit tp02 tpr2:cl01 { p01a p11a };
> >> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
> >>
> >> # Redundant 3
> >> allow at02 tpr3:cl01 { p01a p11a p01b };
> >> if (b01) {
> >> allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
> >> allow tp02 tpr3:cl01 { p01a p11a };
> >> }
> >>
> >> # Redundant 4
> >> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> >> if (b01) {
> >> dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
> >> dontaudit tp02 tpr4:cl01 { p01a p11a };
> >> }
> >>
> >>
> >> I see the following from sediff:
> >>
> >> Allow Rules (0 Added, 1 Removed, 0 Modified)
> >> Removed Allow Rules: 1
> >> - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
> >>
> >> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
> >> Removed Dontaudit Rules: 1
> >> - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
> >> Modified Dontaudit Rules: 1
> >> * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
> >>
> >> So it handles Redundant 1 just fine, but has problems with Redundant 2 which
> >> should be the same.
> >
> > Yes, I think I'm handling the dontaudit rules incorrectly... For some
> > (historical?) reason they actually specify the permissions that *are*
> > audited, although the semantic of combining multiple rules is still
> > that a permission is dontaudited if there is at least one dontaudit
> > rule for it, so the logic of handling the raw perms data has to be
> > inverted for AVTAB_AUDITDENY entries. I had noticed earlier that
> > AVTAB_AUDITDENY rules are handled differently but somehow I concluded
> > that the perms values should still bitwise-or together...
> >
> > Can you please try it with adding:
> >
> > if (specified & AVTAB_AUDITDENY)
> > return (d1->data & d2->data) == d2->data;
> >
> > to the beginning of match_avtab_datum() in optimize.c? (patch form
> > here: https://github.com/WOnder93/selinux/commit/17c77e4bb8857ebfff9b32e2e0bc800e206aba1e.patch)
> >
> >>
> >> I don't remember what to expect from sediff for boolean rules. I had played
> >> around with removing rules with some of my earlier lua tools and I thought that
> >> sediff handled removing redundant rules from booleans, but I could be wrong.
> >>
> >> I will look at this more maybe tomorrow, but most likely after the Memorial day
> >> weekend.
> >>
> >> Jim
> >>
> >> --
> >> James Carter <jwcart2@tycho.nsa.gov>
> >> National Security Agency
> > --
> > Ondrej Mosnacek <omosnace at redhat dot com>
> > Software Engineer, Security Technologies
> > Red Hat, Inc.
> >
>
>
> --
> James Carter <jwcart2@tycho.nsa.gov>
> National Security Agency
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [Non-DoD Source] [PATCH userspace 0/4] Remove redundant rules when building policydb
2019-05-23 20:39 ` [Non-DoD Source] " jwcart2
2019-05-24 8:54 ` Ondrej Mosnacek
@ 2019-05-27 17:11 ` Chris PeBenito
1 sibling, 0 replies; 15+ messages in thread
From: Chris PeBenito @ 2019-05-27 17:11 UTC (permalink / raw)
To: jwcart2, Ondrej Mosnacek, selinux
On 5/23/19 4:39 PM, jwcart2 wrote:
> With these rules:
>
> # Redundant 1
> allow tp01 tpr1:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr1:cl01 { p01a p11a };
> allow at02 tpr1:cl01 { p01a p11a p01b };
>
> # Redundant 2
> dontaudit tp01 tpr2:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr2:cl01 { p01a p11a };
> dontaudit at02 tpr2:cl01 { p01a p11a p01b };
>
> # Redundant 3
> allow at02 tpr3:cl01 { p01a p11a p01b };
> if (b01) {
> allow tp01 tpr3:cl01 { p01a p11a p01b p11b };
> allow tp02 tpr3:cl01 { p01a p11a };
> }
>
> # Redundant 4
> dontaudit at02 tpr4:cl01 { p01a p11a p01b };
> if (b01) {
> dontaudit tp01 tpr4:cl01 { p01a p11a p01b p11b };
> dontaudit tp02 tpr4:cl01 { p01a p11a };
> }
>
>
> I see the following from sediff:
>
> Allow Rules (0 Added, 1 Removed, 0 Modified)
> Removed Allow Rules: 1
> - allow tp02 tpr3:cl01 { p01a p11a }; [ b01 ]:True
>
> Dontaudit Rules (0 Added, 1 Removed, 1 Modified)
> Removed Dontaudit Rules: 1
> - dontaudit tp01 tpr4:cl01 { p01a p01b p11a p11b }; [ b01 ]:True
> Modified Dontaudit Rules: 1
> * dontaudit tp01 tpr2:cl01 { p01b p11a p01a -p11b };
>
> So it handles Redundant 1 just fine, but has problems with Redundant 2
> which should be the same.
>
> I don't remember what to expect from sediff for boolean rules. I had
> played around with removing rules with some of my earlier lua tools and
> I thought that sediff handled removing redundant rules from booleans,
> but I could be wrong.
Sediff doesn't do this optimization at this time. Rules inside a
conditional block won't be considered redundant to unconditional rules.
--
Chris PeBenito
^ permalink raw reply [flat|nested] 15+ messages in thread