[userspace,v2,0/7] Remove redundant rules when building policydb

Message

Ondrej Mosnacek May 28, 2019, 2:59 p.m. UTC

Changes in v2:
 * fix handling of dontaudit (AVTAB_DENY) rules
 * switch optimization from opt-out to opt-in everywhere
 * add a patch from jwcart2 that adds optimization support to
   checkpolicy as well
 * add two RFC modifications (see log messages for details):
   * one improves the optimization to detect also rules covered by the
     union of two or more other rules (on permission set level)
   * the other one drops libsemanage/semodule run-time enabling/
     disabling of optimization in favor of a global config option
v1: https://lore.kernel.org/selinux/[e-mail]/T/

This series implements an optional optimization step when building a
policydb via semodule or secilc, which identifies and removes rules that
are redundant -- i.e. they are already covered by a more general rule
based on the type attribute hierarchy.

Since the optimization might not always be useful (e.g. when care is
taken to not have redundant rules or when the attributes are
aggressively expanded) and might even drastically increase policy build
times under some cicumstances (for example with the DSSP standard policy
[1]), the optimization is applied only when requested explictly.

The optimization routine eliminates:
 * all allow/dontaudit/auditallow(/neverallow) rules (including xperm
   variants) that are covered by another more general rule,
 * all conditional versions of the above rules that are covered by a
   more general rule either in the unconditional table or in the same
   branch of the same conditional.

The optimization doesn't process other rules, since they currently do
not support attributes. There is some room left for more precise
optimization of conditional rules, but it would likely bring only little
additional benefit.

Travis build passed: https://travis-ci.org/WOnder93/selinux/builds/537683392

Tested:
 * live on my Fedora 29 devel machine under normal use (no unusual AVCs
   observed with the optimized policy loaded)
 * using: https://gitlab.com/omos/selinux-misc/blob/master/opt_test.sh
   * tests also xperm rules
   * doesn't test conditionals (yet)

[1] https://github.com/DefenSec/dssp2-standard

James Carter (1):
  checkpolicy: add flag to enable policy optimization

Ondrej Mosnacek (6):
  libsepol: add a function to optimize kernel policy
  libsemanage: optionally optimize policy on rebuild
  semodule: add flag to enable policy optimization
  secilc: add flag to enable policy optimization
  [RFC] lisepol: slightly more thorough optimization
  [RFC] libsemanage: switch to config file entry

 checkpolicy/checkpolicy.c                  |  16 +-
 libsemanage/src/conf-parse.y               |  15 +-
 libsemanage/src/conf-scan.l                |   1 +
 libsemanage/src/direct_api.c               |   7 +
 libsemanage/src/semanage_conf.h            |   1 +
 libsepol/include/sepol/policydb.h          |   5 +
 libsepol/include/sepol/policydb/policydb.h |   2 +
 libsepol/src/libsepol.map.in               |   5 +
 libsepol/src/optimize.c                    | 376 +++++++++++++++++++++
 libsepol/src/policydb_public.c             |   5 +
 secilc/secilc.c                            |  16 +-
 11 files changed, 445 insertions(+), 4 deletions(-)
 create mode 100644 libsepol/src/optimize.c