file context ordering

file context ordering

[Christopher J. PeBenito]

One of the problems we've come against with reference policy (also in
loadable modules) is the fact that the file context specifications are
not ordered correctly, since the system file_contexts are taken from the
modules and concatenated in an arbitrary order.  The matchpathcon code
finds a match by going through all of the specs, and the last one that
is matched is used.

There is a little sorting in matchpathcon, to push the specs with
regular expressions to the top and explicit matches (those without
regular expressions) to the bottom.  This has worked for the current
policy since the specs in file_contexts/program/*.fc are generally
specific matches and types.fc has always been at the top.  Types.fc has
most of the very unspecific regular expressions, and is hand ordered.
With reference policy, all of these specs are split up into their
respective modules, so there is no ordering of file contexts, except
within a module.

To try to fix this we looked for regular expression sorting algorithms,
but pretty much came up empty.  So we wrote support/fc_sort.c to do a
stable sort (merge sort) with this comparison function:

1. does one have a meta chars and the other not
2. length of the spec up to the first meta char
3. length of the entire spec
4. does one have a specific file type (--, -d, etc.) and the other not

This still does not end up being perfect, since we have specs that are
of about the same specificity, and end up being in a different order
then the current fc.  For example, these two specs end up being in the
opposite order that they are in the NSA example policy:

/usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
/usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t

So this results in a handful of mislabeled files
(think /usr/lib/foo/bin/*).

What are your thoughts on how to fix this?

-- 
Chris PeBenito
Tresys Technology, LLC
(410) 290-1411 x150


--
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: file context ordering

[Ron Kuris]

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

My suggestion:

Use M4 diversions to raise the priority of the more important rules.
M4 will output diverted text at the end of the script, and you can
prioritize each section this way.

This worked perfectly for me when I had a similar problem:

divert(3)
[ insert selinux rules here ]
divert(0)

The rules between the diverts will be output at the end, in order by
the diversion number (in this case, 3).

Ron

Christopher J. PeBenito wrote:

| One of the problems we've come against with reference policy (also
| in loadable modules) is the fact that the file context
| specifications are not ordered correctly, since the system
| file_contexts are taken from the modules and concatenated in an
| arbitrary order.  The matchpathcon code finds a match by going
| through all of the specs, and the last one that is matched is used.
|
|
| There is a little sorting in matchpathcon, to push the specs with
| regular expressions to the top and explicit matches (those without
| regular expressions) to the bottom.  This has worked for the
| current policy since the specs in file_contexts/program/*.fc are
| generally specific matches and types.fc has always been at the top.
| Types.fc has most of the very unspecific regular expressions, and
| is hand ordered. With reference policy, all of these specs are
| split up into their respective modules, so there is no ordering of
| file contexts, except within a module.
|
| To try to fix this we looked for regular expression sorting
| algorithms, but pretty much came up empty.  So we wrote
| support/fc_sort.c to do a stable sort (merge sort) with this
| comparison function:
|
| 1. does one have a meta chars and the other not 2. length of the
| spec up to the first meta char 3. length of the entire spec 4. does
| one have a specific file type (--, -d, etc.) and the other not
|
| This still does not end up being perfect, since we have specs that
| are of about the same specificity, and end up being in a different
| order then the current fc.  For example, these two specs end up
| being in the opposite order that they are in the NSA example
| policy:
|
| /usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
| /usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t
|
| So this results in a handful of mislabeled files (think
| /usr/lib/foo/bin/*).
|
| What are your thoughts on how to fix this?
|

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFC6UbtVkC/44kdyuYRAjQQAKD9Cyizhuv12Cz91GbckGn0WnoLLgCgqptl
wSTxRNrI9uO/g5Z/FTtM5oY=
=TUVs
-----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: file context ordering

[Christopher J. PeBenito]

On Thu, 2005-07-28 at 13:58 -0700, Ron Kuris wrote:
> My suggestion:
> 
> Use M4 diversions to raise the priority of the more important rules.
> M4 will output diverted text at the end of the script, and you can
> prioritize each section this way.
> 
> This worked perfectly for me when I had a similar problem:
> 
> divert(3)
> [ insert selinux rules here ]
> divert(0)
> 
> The rules between the diverts will be output at the end, in order by
> the diversion number (in this case, 3).

Well this is definitely an interesting solution.  The problem is that it
doesn't apply to the loadable policy modules, since the file contexts in
a module don't have m4.  Preserving m4 into the modules, and having
semodule run m4 to reconstruct file_contexts is probably a bad idea.
Adding a weight to specs, which is what Steve suggested, would be more
general than leveraging m4.

-- 
Chris PeBenito
Tresys Technology, LLC
(410) 290-1411 x150


--
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: file context ordering

[Ron Kuris]

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

Christopher J. PeBenito wrote:

| On Thu, 2005-07-28 at 13:58 -0700, Ron Kuris wrote:
|
|> Use M4 diversions ... [snip]
|
|
| Well this is definitely an interesting solution.  The problem is
| that it doesn't apply to the loadable policy modules, since the
| file contexts in a module don't have m4.  Preserving m4 into the
| modules, and having semodule run m4 to reconstruct file_contexts is
| probably a bad idea. Adding a weight to specs, which is what Steve
| suggested, would be more general than leveraging m4.
|
I guess I don't know enough about the loadable module plans.

So that means the loadable modules cannot use any of the m4 macros either?

Ron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFC6nswVkC/44kdyuYRAuoyAKDGKVk6aOCtUZg5hOKY6NrEQ3U2YgCfQnUx
ugMfR4Bw5R7AHr1cUwm/4wM=
=Tqmz
-----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: file context ordering

[Christopher J. PeBenito]

On Fri, 2005-07-29 at 11:53 -0700, Ron Kuris wrote:
> Christopher J. PeBenito wrote:
> | On Thu, 2005-07-28 at 13:58 -0700, Ron Kuris wrote:
> |
> |> Use M4 diversions ... [snip]
> |
> |
> | Well this is definitely an interesting solution.  The problem is
> | that it doesn't apply to the loadable policy modules, since the
> | file contexts in a module don't have m4.  Preserving m4 into the
> | modules, and having semodule run m4 to reconstruct file_contexts is
> | probably a bad idea. Adding a weight to specs, which is what Steve
> | suggested, would be more general than leveraging m4.
> |
> I guess I don't know enough about the loadable module plans.
> 
> So that means the loadable modules cannot use any of the m4 macros either?

They can; the m4 is expanded before compiling the module.  So if you
divert something in the file_contexts, it would only be diverted for
that module.

-- 
Chris PeBenito
Tresys Technology, LLC
(410) 290-1411 x150


--
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: file context ordering

[Daniel J Walsh]

Christopher J. PeBenito wrote:

>One of the problems we've come against with reference policy (also in
>loadable modules) is the fact that the file context specifications are
>not ordered correctly, since the system file_contexts are taken from the
>modules and concatenated in an arbitrary order.  The matchpathcon code
>finds a match by going through all of the specs, and the last one that
>is matched is used.
>
>There is a little sorting in matchpathcon, to push the specs with
>regular expressions to the top and explicit matches (those without
>regular expressions) to the bottom.  This has worked for the current
>policy since the specs in file_contexts/program/*.fc are generally
>specific matches and types.fc has always been at the top.  Types.fc has
>most of the very unspecific regular expressions, and is hand ordered.
>With reference policy, all of these specs are split up into their
>respective modules, so there is no ordering of file contexts, except
>within a module.
>
>To try to fix this we looked for regular expression sorting algorithms,
>but pretty much came up empty.  So we wrote support/fc_sort.c to do a
>stable sort (merge sort) with this comparison function:
>
>1. does one have a meta chars and the other not
>2. length of the spec up to the first meta char
>3. length of the entire spec
>4. does one have a specific file type (--, -d, etc.) and the other not
>
>This still does not end up being perfect, since we have specs that are
>of about the same specificity, and end up being in a different order
>then the current fc.  For example, these two specs end up being in the
>opposite order that they are in the NSA example policy:
>
>/usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
>/usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t
>
>  
>
We could add on a case by case basis

/usr(/.*)?/lib(64)?(/.*)?/bin(/.*)?   system_u:object_r:bin_t
Or hard code some hierarchy where bin_t is always after lib_t in this situation.

I would doubt we would have /usr/bin/lib/...



>So this results in a handful of mislabeled files
>(think /usr/lib/foo/bin/*).
>
>What are your thoughts on how to fix this?
>
>  
>


-- 



--
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: file context ordering

[Christopher J. PeBenito]

On Fri, 2005-07-29 at 06:26 -0400, Daniel J Walsh wrote:
> Christopher J. PeBenito wrote:
> >One of the problems we've come against with reference policy (also in
> >loadable modules) is the fact that the file context specifications are
> >not ordered correctly, since the system file_contexts are taken from the
> >modules and concatenated in an arbitrary order.  The matchpathcon code
> >finds a match by going through all of the specs, and the last one that
> >is matched is used.
[cut]
> >This still does not end up being perfect, since we have specs that are
> >of about the same specificity, and end up being in a different order
> >then the current fc.  For example, these two specs end up being in the
> >opposite order that they are in the NSA example policy:
> >
> >/usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
> >/usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t
> >
> >  
> >
> We could add on a case by case basis
> 
> /usr(/.*)?/lib(64)?(/.*)?/bin(/.*)?   system_u:object_r:bin_t

This would be a good solution for now.  I still feel that, if possible,
we should find a generic solution.

> Or hard code some hierarchy where bin_t is always after lib_t in this
> situation.
> 
> I would doubt we would have /usr/bin/lib/...

Well hard coding it isn't the answer, especially since this is just one
example.

-- 
Chris PeBenito
Tresys Technology, LLC
(410) 290-1411 x150


--
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: file context ordering

[Stephen Smalley]

On Thu, 2005-07-28 at 15:16 -0400, Christopher J. PeBenito wrote:
> One of the problems we've come against with reference policy (also in
> loadable modules) is the fact that the file context specifications are
> not ordered correctly, since the system file_contexts are taken from the
> modules and concatenated in an arbitrary order.  The matchpathcon code
> finds a match by going through all of the specs, and the last one that
> is matched is used.

To be precise, matchpathcon searches the specs in reverse order and
stops as soon as it finds a matching one.  And matchpathcon_filespec_add
uses the ordering to choose which spec to apply when multiple hard links
to an inode match conflicting specifications.

> There is a little sorting in matchpathcon, to push the specs with
> regular expressions to the top and explicit matches (those without
> regular expressions) to the bottom.  This has worked for the current
> policy since the specs in file_contexts/program/*.fc are generally
> specific matches and types.fc has always been at the top.  Types.fc has
> most of the very unspecific regular expressions, and is hand ordered.
> With reference policy, all of these specs are split up into their
> respective modules, so there is no ordering of file contexts, except
> within a module.

So we need an explicit ordering notation in the file_contexts file?  An
optional field specifying an ordering value, so that they can still be
ordered relative to one another even when they are in separate modules.

> To try to fix this we looked for regular expression sorting algorithms,
> but pretty much came up empty.  So we wrote support/fc_sort.c to do a
> stable sort (merge sort) with this comparison function:
> 
> 1. does one have a meta chars and the other not
> 2. length of the spec up to the first meta char
> 3. length of the entire spec
> 4. does one have a specific file type (--, -d, etc.) and the other not

Back when NAI looked into modifying setfiles originally to sort the .fc
entries, I had looked briefly into techniques for computing the
generality of a given pathname regex as a way of ordering them, but they
didn't want to pursue that approach due to time limitations and concerns
about complexity and ambiguity.  I have that email somewhere if you want
me to dig it out.

> This still does not end up being perfect, since we have specs that are
> of about the same specificity, and end up being in a different order
> then the current fc.  For example, these two specs end up being in the
> opposite order that they are in the NSA example policy:
> 
> /usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
> /usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t
> 
> So this results in a handful of mislabeled files
> (think /usr/lib/foo/bin/*).
> 
> What are your thoughts on how to fix this?

The simplest approach would seem to just be:
- introduce an optional ordering value field so that the policy writer
can explicitly order entries relative to each other even when they are
in separate modules (but this naturally has issues when different people
are writing different modules without knowing exactly what is in the
other modules),
- have matchpathcon check for multiple matching specifications with the
same ordering value (whether explicitly specified or implicitly
determined using your algorithm) and issue warnings in those cases so
that we get warnings on such ambiguity, just as it presently warns about
multiple hard links that match conflicting specifications.

-- 
Stephen Smalley
National Security Agency


--
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: file context ordering

[Christopher J. PeBenito]

On Fri, 2005-07-29 at 08:44 -0400, Stephen Smalley wrote:
> > There is a little sorting in matchpathcon, to push the specs with
> > regular expressions to the top and explicit matches (those without
> > regular expressions) to the bottom.  This has worked for the current
> > policy since the specs in file_contexts/program/*.fc are generally
> > specific matches and types.fc has always been at the top.  Types.fc has
> > most of the very unspecific regular expressions, and is hand ordered.
> > With reference policy, all of these specs are split up into their
> > respective modules, so there is no ordering of file contexts, except
> > within a module.
[cut]
> > To try to fix this we looked for regular expression sorting algorithms,
> > but pretty much came up empty.
[cut]
> Back when NAI looked into modifying setfiles originally to sort the .fc
> entries, I had looked briefly into techniques for computing the
> generality of a given pathname regex as a way of ordering them, but they
> didn't want to pursue that approach due to time limitations and concerns
> about complexity and ambiguity.  I have that email somewhere if you want
> me to dig it out.

Yes, if you would.  Thanks.

> > This still does not end up being perfect, since we have specs that are
> > of about the same specificity, and end up being in a different order
> > then the current fc.  For example, these two specs end up being in the
> > opposite order that they are in the NSA example policy:
> > 
> > /usr(/.*)?/bin(/.*)?        system_u:object_r:bin_t
> > /usr(/.*)?/lib(64)?(/.*)?   system_u:object_r:lib_t
> > 
> > So this results in a handful of mislabeled files
> > (think /usr/lib/foo/bin/*).
> > 
> > What are your thoughts on how to fix this?
> 
> The simplest approach would seem to just be:
> - introduce an optional ordering value field so that the policy writer
> can explicitly order entries relative to each other even when they are
> in separate modules (but this naturally has issues when different people
> are writing different modules without knowing exactly what is in the
> other modules),

The issues you're talking about could be more problematic in the future.
Especially since, with both loadable policy modules and reference
policy, one of the things we're trying to facilitate is handling of 3rd
party policy modules.  Not that I'm saying that this is a bad solution.
It just seems like it might be more painful untangling a labeling
problems this way, since weights are arbitrary, than adding more
specific expressions on a case by case basis, as Dan suggested.  You
also end up at the same problem if the weights are the same.

> - have matchpathcon check for multiple matching specifications with the
> same ordering value (whether explicitly specified or implicitly
> determined using your algorithm) and issue warnings in those cases so
> that we get warnings on such ambiguity, just as it presently warns about
> multiple hard links that match conflicting specifications.

This is probably a good thing to have, regardless.

-- 
Chris PeBenito
Tresys Technology, LLC
(410) 290-1411 x150


--
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.