avtab dense hash table

avtab dense hash table

[Pavel Roschin]

Hello, I have some questions about hash tables in SELinux. As I see, all AV
rules are stored inside hash tables: I found them in kernel source and in
libsepol source. All types, domains, classes and so on also stored inside hash
tables.

Regarding source code of libsepol I see that all hash tables are fixed-size:
maximum avtab size is 2^13 - 8192 buckets. But in RHEL seinfo shows that there
are 250000+ allow rules and 170000+ dontaudit rules. Shouldn't that be a huge
performance kick?

In Linux kernel, avtab has size 2^11 - 2048 buckets for 256000+ av rules. Huge
hash table will be transformed into lists and linear search that should be slow
as hell, shouldn't?

>From kernel source:

#define MAX_AVTAB_HASH_BITS 11
#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)

What is the reason of such dense hash maps?

--
Best regards,
Pavel Roschin


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Stephen Smalley]

On 12/05/2013 04:04 AM, Pavel Roschin wrote:
> Hello, I have some questions about hash tables in SELinux. As I see, all AV
> rules are stored inside hash tables: I found them in kernel source and in
> libsepol source. All types, domains, classes and so on also stored inside hash
> tables.
> 
> Regarding source code of libsepol I see that all hash tables are fixed-size:
> maximum avtab size is 2^13 - 8192 buckets. But in RHEL seinfo shows that there
> are 250000+ allow rules and 170000+ dontaudit rules. Shouldn't that be a huge
> performance kick?
> 
> In Linux kernel, avtab has size 2^11 - 2048 buckets for 256000+ av rules. Huge
> hash table will be transformed into lists and linear search that should be slow
> as hell, shouldn't?
> 
>>From kernel source:
> 
> #define MAX_AVTAB_HASH_BITS 11
> #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
> #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
> 
> What is the reason of such dense hash maps?

So, first, originally the policy was much smaller.  I'm personally of
the view that people need to take a chainsaw to the refpolicy and look
to greatly coalesce domains/types, and to rework the way policy is
packaged in RHEL/Fedora to only install the policy modules relevant for
the packages that are installed.  See prior discussions from the list on
that.  Certainly you'll find that the policy we wrote from scratch for
Android is vastly smaller and simpler.

Second, most policy lookups should be resolved in the AVC and never
reach the avtab lookup at all.  At least that's the intent.

Third, the avtab hash table size has been tuned over the years to
balance between chain size and the desire to avoid high order
allocations for the hash table itself, e.g.
http://marc.info/?l=selinux&m=126866435230447&w=2

Not saying that we wouldn't take a patch though to improve the
situation.  You just need to show that it doesn't cause adverse side
effects (like high order allocations).


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Dominick Grift]

On Thu, 2013-12-05 at 09:15 -0500, Stephen Smalley wrote:

> So, first, originally the policy was much smaller.  I'm personally of
> the view that people need to take a chainsaw to the refpolicy and look
> to greatly coalesce domains/types

Could you please give some examples of existing types that you would
merge or even remove and why. I might be able to find patterns in how
you decide when its worth to merge types and when not in your opinion. I
generally like the idea but i could use some inspiration. Where would
you draw the line and why?





--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Stephen Smalley]

On 12/05/2013 10:49 AM, Dominick Grift wrote:
> On Thu, 2013-12-05 at 09:15 -0500, Stephen Smalley wrote:
> 
>> So, first, originally the policy was much smaller.  I'm personally of
>> the view that people need to take a chainsaw to the refpolicy and look
>> to greatly coalesce domains/types
> 
> Could you please give some examples of existing types that you would
> merge or even remove and why. I might be able to find patterns in how
> you decide when its worth to merge types and when not in your opinion. I
> generally like the idea but i could use some inspiration. Where would
> you draw the line and why?

I have a tool for SE for Android (under external/sepolicy/tools -
sepolicy-analyze.c) that analyzes that policy for identical types and
reports them.  Also looks for redundant allow rules (allowed by
attribute and individually).  Unfortunately the type equivalence
analysis seems to take forever on Fedora policy since it does it by
first expanding the attributes; I have a patch to do it without
requiring full attribute expansion but that fails to identify some
cases.  apol also has a types relationship analysis facility that will
let you examine how two types compare, but only a pairwise basis.

We're also planning to extend sepolicy-analyze to not only report
equivalent types but also look for isomorphic types, as we otherwise
never see identical domains due to the unique entrypoint, tmpfs, and
similar relationships.



--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Dominick Grift]

On Thu, 2013-12-05 at 16:16 -0500, Stephen Smalley wrote:
> On 12/05/2013 10:49 AM, Dominick Grift wrote:
> > On Thu, 2013-12-05 at 09:15 -0500, Stephen Smalley wrote:
> > 
> >> So, first, originally the policy was much smaller.  I'm personally of
> >> the view that people need to take a chainsaw to the refpolicy and look
> >> to greatly coalesce domains/types
> > 
> > Could you please give some examples of existing types that you would
> > merge or even remove and why. I might be able to find patterns in how
> > you decide when its worth to merge types and when not in your opinion. I
> > generally like the idea but i could use some inspiration. Where would
> > you draw the line and why?
> 
> I have a tool for SE for Android (under external/sepolicy/tools -
> sepolicy-analyze.c) that analyzes that policy for identical types and
> reports them.  Also looks for redundant allow rules (allowed by
> attribute and individually).  Unfortunately the type equivalence
> analysis seems to take forever on Fedora policy since it does it by
> first expanding the attributes; I have a patch to do it without
> requiring full attribute expansion but that fails to identify some
> cases.  apol also has a types relationship analysis facility that will
> let you examine how two types compare, but only a pairwise basis.
> 
> We're also planning to extend sepolicy-analyze to not only report
> equivalent types but also look for isomorphic types, as we otherwise
> never see identical domains due to the unique entrypoint, tmpfs, and
> similar relationships.
> 

Thanks, But if i understand it correctly then types that have (roughly)
the same properties would be candidates for merger.

That could be processes (or files) with different properties ( but same
rules associated with them )

That would mean that a system could end up with various different
processes running in the same domain (thus they can in theory affect
each other)

The way i am approaching it is besides requiring types to have similar
properties that also the processes have similar properties

So for example merge all web servers if the policy is roughly the same.

My reasoning for this is that only one kind of web server runs on a
system at any given time (usually).

Another example all: all irc clients in the same domain because often
one kind of irc client is used on a system at any given time

I see that you are willing to take this further. If for example (stupid
example) a mail server would have the same properties (rules) as a web
server that would be a candidate for a merger. Even though the mail
server and the web server could run on a system at any given time. Thus
they could affect each other

For android that approach would work since seandroid also associates
unique categories to uids but this does not apply to regular Linux

Would you agree that a system like Fedora has different properties than
a system like seandroid?

It occurs to me that Fedora is much more general purpose whereas android
is a phone operating system.

I believe that there is a lot of room for improvement in reference
policy and i am willing to do the leg work to bring some change in this
regard. Consensus is not easy to achieve though. I could not even make
the case for getting nginx in the apache domain.

I hope that this thread can get a discussion going with regard to
simplifying the policy without compromising too much

Thank you for you reply


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Stephen Smalley]

On 12/05/2013 04:37 PM, Dominick Grift wrote:
> Thanks, But if i understand it correctly then types that have (roughly)
> the same properties would be candidates for merger.

That's correct.  Domains/types are intended to be security equivalence
classes; all subjects that require the same accesses to the same objects
should be in the same domain and all objects that need to be accessed
identically by the same subjects should be in the same type.  It wasn't
supposed to be one domain for every program executable or one type for
every directory/file.

> That could be processes (or files) with different properties ( but same
> rules associated with them )
> 
> That would mean that a system could end up with various different
> processes running in the same domain (thus they can in theory affect
> each other)
> 
> The way i am approaching it is besides requiring types to have similar
> properties that also the processes have similar properties
> 
> So for example merge all web servers if the policy is roughly the same.
> 
> My reasoning for this is that only one kind of web server runs on a
> system at any given time (usually).
> 
> Another example all: all irc clients in the same domain because often
> one kind of irc client is used on a system at any given time

Exactly, and if you still want to isolate the different instances from
each other, you can use category sets more effectively for that purpose
than needing to define separate domains/types.

> I see that you are willing to take this further. If for example (stupid
> example) a mail server would have the same properties (rules) as a web
> server that would be a candidate for a merger. Even though the mail
> server and the web server could run on a system at any given time. Thus
> they could affect each other
> 
> For android that approach would work since seandroid also associates
> unique categories to uids but this does not apply to regular Linux

Well, at least in mainline Android, we had to back off of per-app
category sets because Android does permit direct app interactions.  But
the category-based separation can still be applied at differing
granularities, from per-app to per-user (Android now supports
multi-user) to per-container (e.g. personal/business separation), based
on your specific policy configuration.

> Would you agree that a system like Fedora has different properties than
> a system like seandroid?
> 
> It occurs to me that Fedora is much more general purpose whereas android
> is a phone operating system.

I certainly agree that they differ, and that Android is much easier to
construct a policy for.  That said, there does seem to be increasing
convergence and many of the same techniques can be applied, e.g.
category-based separation has already been effectively applied in Fedora
for sandbox, svirt, OpenShift, and others.

> I believe that there is a lot of room for improvement in reference
> policy and i am willing to do the leg work to bring some change in this
> regard. Consensus is not easy to achieve though. I could not even make
> the case for getting nginx in the apache domain.

It may be necessary to fork a separate policy, at least for a while, to
truly explore more radical surgery, and then try to gradually feed the
changes back.

> I hope that this thread can get a discussion going with regard to
> simplifying the policy without compromising too much
> 
> Thank you for you reply

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Daniel J Walsh]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/06/2013 08:51 AM, Stephen Smalley wrote:
> On 12/05/2013 04:37 PM, Dominick Grift wrote:
>> Thanks, But if i understand it correctly then types that have (roughly) 
>> the same properties would be candidates for merger.
> 
> That's correct.  Domains/types are intended to be security equivalence 
> classes; all subjects that require the same accesses to the same objects 
> should be in the same domain and all objects that need to be accessed 
> identically by the same subjects should be in the same type.  It wasn't 
> supposed to be one domain for every program executable or one type for 
> every directory/file.
> 
>> That could be processes (or files) with different properties ( but same 
>> rules associated with them )
>> 
>> That would mean that a system could end up with various different 
>> processes running in the same domain (thus they can in theory affect each
>> other)
>> 
>> The way i am approaching it is besides requiring types to have similar 
>> properties that also the processes have similar properties
>> 
>> So for example merge all web servers if the policy is roughly the same.
>> 
>> My reasoning for this is that only one kind of web server runs on a 
>> system at any given time (usually).
>> 
>> Another example all: all irc clients in the same domain because often one
>> kind of irc client is used on a system at any given time
> 
> Exactly, and if you still want to isolate the different instances from each
> other, you can use category sets more effectively for that purpose than
> needing to define separate domains/types.
> 
>> I see that you are willing to take this further. If for example (stupid 
>> example) a mail server would have the same properties (rules) as a web 
>> server that would be a candidate for a merger. Even though the mail 
>> server and the web server could run on a system at any given time. Thus 
>> they could affect each other
>> 
>> For android that approach would work since seandroid also associates 
>> unique categories to uids but this does not apply to regular Linux
> 
> Well, at least in mainline Android, we had to back off of per-app category
> sets because Android does permit direct app interactions.  But the
> category-based separation can still be applied at differing granularities,
> from per-app to per-user (Android now supports multi-user) to per-container
> (e.g. personal/business separation), based on your specific policy
> configuration.
> 
>> Would you agree that a system like Fedora has different properties than a
>> system like seandroid?
>> 
>> It occurs to me that Fedora is much more general purpose whereas android 
>> is a phone operating system.
> 
> I certainly agree that they differ, and that Android is much easier to 
> construct a policy for.  That said, there does seem to be increasing 
> convergence and many of the same techniques can be applied, e.g. 
> category-based separation has already been effectively applied in Fedora 
> for sandbox, svirt, OpenShift, and others.
> 
>> I believe that there is a lot of room for improvement in reference policy
>> and i am willing to do the leg work to bring some change in this regard.
>> Consensus is not easy to achieve though. I could not even make the case
>> for getting nginx in the apache domain.
> 
> It may be necessary to fork a separate policy, at least for a while, to 
> truly explore more radical surgery, and then try to gradually feed the 
> changes back.
> 
>> I hope that this thread can get a discussion going with regard to 
>> simplifying the policy without compromising too much
>> 
>> Thank you for you reply
> 
> -- This message was distributed to subscribers of the selinux mailing
> list. If you no longer wish to subscribe, send mail to
> majordomo@tycho.nsa.gov with the words "unsubscribe selinux" without quotes
> as the message.
> 

We have been doing some consolidation in Fedora.  We have combined spam tools
into a single domain spamassassin.  Might have been better to create a new
policy for this.

We have also created antivirus which combined all of the antivirus tools.

The next big one I would like to see combined are mail servers and mail
clients.  (Elimination of all the different postfix domains, would eliminate
large numbers of bugs over the years.)


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.15 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iEYEARECAAYFAlKh26gACgkQrlYvE4MpobPzSQCg6E2BpD9CWfPU9q84+U8kPQs9
qi4AoInIXDi4u2I5x9HM3patjyJdVrH5
=sAud
-----END PGP SIGNATURE-----

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Dominick Grift]

On Fri, 2013-12-06 at 09:14 -0500, Daniel J Walsh wrote:

> 
> We have been doing some consolidation in Fedora.  We have combined spam tools
> into a single domain spamassassin.  Might have been better to create a new
> policy for this.
> 
> We have also created antivirus which combined all of the antivirus tools.
> 
> The next big one I would like to see combined are mail servers and mail
> clients.  (Elimination of all the different postfix domains, would eliminate
> large numbers of bugs over the years.)
> 
> 

Yes i am aware of the antivirus policy in Fedora. I did not merge that
into refpolicy (yet) because at that point i did not feel comfortable
with it. I probably thought it was too early to merge it, and wanted to
wait for some of the bugs to be ironed out in fedora first.

Some other consolidation changes i am not comfortable with (yet).
fortunately those mostly apply to refpolicy-base, and so it is not up to
be to decide whether to adopt those or not.

There are also some things i plain do not like the way it is implemented
now. For example modules that have combinations of domains that might
not strictly depend on each other. (one possible example might be rhcs
module). I like to keep domains separate as much as possible because
that provides flexibility. e.g. I could remove one or a few without
having to remove them all.




--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: avtab dense hash table

[Daniel J Walsh]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/06/2013 10:46 AM, Dominick Grift wrote:
> On Fri, 2013-12-06 at 09:14 -0500, Daniel J Walsh wrote:
> 
>> 
>> We have been doing some consolidation in Fedora.  We have combined spam
>> tools into a single domain spamassassin.  Might have been better to
>> create a new policy for this.
>> 
>> We have also created antivirus which combined all of the antivirus
>> tools.
>> 
>> The next big one I would like to see combined are mail servers and mail 
>> clients.  (Elimination of all the different postfix domains, would
>> eliminate large numbers of bugs over the years.)
>> 
>> 
> 
> Yes i am aware of the antivirus policy in Fedora. I did not merge that into
> refpolicy (yet) because at that point i did not feel comfortable with it. I
> probably thought it was too early to merge it, and wanted to wait for some
> of the bugs to be ironed out in fedora first.
> 
> Some other consolidation changes i am not comfortable with (yet). 
> fortunately those mostly apply to refpolicy-base, and so it is not up to be
> to decide whether to adopt those or not.
> 
> There are also some things i plain do not like the way it is implemented 
> now. For example modules that have combinations of domains that might not
> strictly depend on each other. (one possible example might be rhcs module).
> I like to keep domains separate as much as possible because that provides
> flexibility. e.g. I could remove one or a few without having to remove them
> all.
> 
> 
> 
Yes I guess work with mgrepl on splitting that one apart.  It seems to have
grown organically.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.15 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iEYEARECAAYFAlKh9NEACgkQrlYvE4MpobN1eACgpfYJhhNP7j2/NST4/cJH8wJU
srMAoNDXVwVUekVVWtDLcHqaFp2RpvpQ
=RsZ2
-----END PGP SIGNATURE-----

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.