On Thu, May 30, 2019 at 6:56 PM Stephen Smalley <sds@xxxxxxxxxxxxx> wrote:
> On 5/30/19 7:46 AM, Ondrej Mosnacek wrote:
> > On Wed, May 29, 2019 at 10:32 PM jwcart2 <jwcart2@xxxxxxxxxxxxx> 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@xxxxxxxxxx>
> >>> ---
> >>> 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@xxxxxxxxx>
> >>> + *
> >>> + * 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@xxxxxxxxxxxxx>
> >> National Security Agency
> >
> >
> >
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
