FCGlob

FCGlob

[Russell Coker]

http://selinux-symposium.org/2007/papers/06-fcglob.pdf

I've just read the above paper.  It seems apparent that this is generally the 
right approach.

Page 3 states that a down-side is "the tree would be a binary file and not 
human readable any more".  Why would this be so?  Currently we compile a set 
of plain text .fc files into a plain text file that is not directly 
accessible to the sys-admin (everyone on this list knows how to get it - but 
it's not a documented interface) and there is also a semanage option to 
display the same data.

It seems to me that having .fc files with FCGlob data which are human readable 
and then compiling them into a binary form will not be any different.  
The .fc files shipped as part of policy modules will still need to be 
plain-text (the tree structure depends on nodes from other .fc files), and 
the semanage command can still do much the same tasks.

Why would it be desirable to compile FCGlob to regular expressions?  Once the 
performance benefits are proven we might as well go full-speed ahead.

As for regex's that have no clear meaning, the only thing to do is to remove 
them and wait for the original policy author to complain.  There are many 
regular expressions that never matched anything and probably many more that 
match old versions of software.

-- 
russell@coker.com.au
http://etbe.blogspot.com/          My Blog

http://www.coker.com.au/sponsorship.html Sponsoring Free Software development

--
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: FCGlob

[John D. Ramsdell]

Russell Coker <russell@coker.com.au> writes:

> Why would it be desirable to compile FCGlob to regular expressions?
> Once the performance benefits are proven we might as well go
> full-speed ahead.

I too spent some time thinking about the FCGlob paper.  I believe the
reason one wants to be able to translate FCGlob patterns into regular
expressions is so that one can implement the comparison function
described in the paper as follows:

   A comparison function that receives two patterns as parameters and
   returns the set relationship. Possible set relationships between
   the set of paths pattern A matches and the set of paths pattern B
   matches are: subset, superset, disjoint and ambiguous.

It seems to me that finite automata theory is called for.  The FCGlob
pattern language as described can easily be translated into a regular
expression.  A regular expression can be translated into a
deterministic finite automata without epsilon transitions.  It is easy
to convert this machine into one that recognizes the complement of its
language by complementing the set of final states of the machine.  A
machine that computes the intersection of two languages can be
produced by taking the cross product of the states of the machine for
each language.  Finally, it is easy to test if a machine accepts no
strings.  These primitives can be used to implement the comparison
function as specified.

Finite state machines can be designed so they have more interesting
outputs other than just accept or reject.  In particular, each state
can be associated with a set of security contexts.  A rejecting state
would be associated with the empty set, and an unambiguous state would
be associated with a singleton set.

If you look at the problem as a whole, it seems to me it is possible
to build one finite state machine for a file context that tests if a
pathname matches all the patterns at the same time, and produces a set
of security contexts as its answer.  Given a large number of patterns,
this approach should be very efficient as the input would be traversed
just once.  The only down side is one would have to invest the time to
generate this special purpose machine.

I happened to notice a relevant paper.  The translation of a regular
expression to a deterministic finite automata, typically starts by
translating it to a non-deterministic finite automata with epsilon
transitions.  For this step, the following paper may be helpful: "A
Simple Way to Construct NFA with Fewer States and Transitions" by
Guangming Xing.

Finally, I noticed that the library gfsm appears to export functions
that perform the operations described above.  I have never used the
gfsm library, so I cannot attest to its quality.

John



--
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: FCGlob (does someone have the time to generate a special purpose machine)

[Zwartsenberg, Remmolt]

[-- Attachment #1: Type: text/plain, Size: 5931 bytes --]

Hello John,
 
Having some experience with designing and implementing finite state machines and implementing these in datastructures matching the expected behaviour in algorithms running on high-performance computers i have some questions regarding your thought-patterns that are by the way very well written:

1.	
	Regular expressions typically behave as expected in linear computations ('vintage von Neumann ones') but tend to be unable to define relationships between intra-set elements within unstructured sets. I would vote for a datastructure known as 'Undirected Graph' for input and the expected output should be a 'Directed Graph' designating the relationship between the elements within the set. This would enhance the 'reject or accept' state with a 3d one, being an image of the intraset relationship between the elements within the set without superimposing a preconveived 'anthropomorphic' structure. Of course we would have to watch out for spending too much processor time by starting a watchdog deamon that will kill the process after a preset deltatime interval has elapsed. My question to you is: do we need to do this just for generating a security policy? (set of security context rules)
2.	
	I would not mind implementing this requirement on the 64 processor Linux Cluster at the University of Utrecht, but do any of you guys have any idea of how we could fund this?

I hope this helps,

Remmolt

"In research you uncover the unknown. In application of the results you will have to cover the known." -parafrase of Sir Thomas Pickering-



________________________________

From: owner-selinux@tycho.nsa.gov on behalf of John D. Ramsdell
Sent: Tue 4/17/2007 1:23 PM
To: russell@coker.com.au
Cc: SE-Linux
Subject: Re: FCGlob



Russell Coker <russell@coker.com.au> writes:

> Why would it be desirable to compile FCGlob to regular expressions?
> Once the performance benefits are proven we might as well go
> full-speed ahead.

I too spent some time thinking about the FCGlob paper.  I believe the
reason one wants to be able to translate FCGlob patterns into regular
expressions is so that one can implement the comparison function
described in the paper as follows:

   A comparison function that receives two patterns as parameters and
   returns the set relationship. Possible set relationships between
   the set of paths pattern A matches and the set of paths pattern B
   matches are: subset, superset, disjoint and ambiguous.

It seems to me that finite automata theory is called for.  The FCGlob
pattern language as described can easily be translated into a regular
expression.  A regular expression can be translated into a
deterministic finite automata without epsilon transitions.  It is easy
to convert this machine into one that recognizes the complement of its
language by complementing the set of final states of the machine.  A
machine that computes the intersection of two languages can be
produced by taking the cross product of the states of the machine for
each language.  Finally, it is easy to test if a machine accepts no
strings.  These primitives can be used to implement the comparison
function as specified.

Finite state machines can be designed so they have more interesting
outputs other than just accept or reject.  In particular, each state
can be associated with a set of security contexts.  A rejecting state
would be associated with the empty set, and an unambiguous state would
be associated with a singleton set.

If you look at the problem as a whole, it seems to me it is possible
to build one finite state machine for a file context that tests if a
pathname matches all the patterns at the same time, and produces a set
of security contexts as its answer.  Given a large number of patterns,
this approach should be very efficient as the input would be traversed
just once.  The only down side is one would have to invest the time to
generate this special purpose machine.

I happened to notice a relevant paper.  The translation of a regular
expression to a deterministic finite automata, typically starts by
translating it to a non-deterministic finite automata with epsilon
transitions.  For this step, the following paper may be helpful: "A
Simple Way to Construct NFA with Fewer States and Transitions" by
Guangming Xing.

Finally, I noticed that the library gfsm appears to export functions
that perform the operations described above.  I have never used the
gfsm library, so I cannot attest to its quality.

John



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


Disclaimer

Dit bericht met eventuele bijlagen is vertrouwelijk en uitsluitend bestemd voor de geadresseerde. Indien u niet de bedoelde ontvanger bent, wordt u verzocht de afzender te waarschuwen en dit bericht met eventuele bijlagen direct te verwijderen en/of te vernietigen. Het is niet toegestaan dit bericht en eventuele bijlagen te vermenigvuldigen, door te sturen, openbaar te maken, op te slaan of op andere wijze te gebruiken. Ordina N.V. en/of haar groepsmaatschappijen accepteren geen verantwoordelijkheid of aansprakelijkheid voor schade die voortvloeit uit de inhoud en/of de verzending van dit bericht.

This e-mail and any attachments are confidential and is solely intended for the addressee only. If you are not the intended recipient, please notify the sender and delete and/or destroy this message and any attachments immediately. It is prohibited to copy, to distribute, to disclose or to use this e-mail and any attachments in any other way. Ordina N.V. and/or its group companies do not accept any responsibility nor liability for any damage resulting from the content of and/or the transmission of this message.

[-- Attachment #2: Type: text/html, Size: 6894 bytes --]

Re: FCGlob (does someone have the time to generate a special purpose machine)

[John D. Ramsdell]

"Zwartsenberg, Remmolt" <remmolt.zwartsenberg@ordina.nl> writes:

> Having some experience with designing and implementing finite state
> machines ...

I have no experience implementing finite state machines, so I cannot
comment on your implementation questions.  My first impulse would be
to see if gfsm provides the needed functionality.  

> I would not mind implementing this requirement on the 64 processor
> Linux Cluster at the University of Utrecht, but do any of you guys
> have any idea of how we could fund this?

Once again, I'm afraid I am of no help.

John

--
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: FCGlob

[Christopher Ashworth]

Hullo John,

> -----Original Message-----
> From: owner-selinux@tycho.nsa.gov 
> [mailto:owner-selinux@tycho.nsa.gov] On Behalf Of John D. Ramsdell
> Sent: Tuesday, April 17, 2007 7:24 AM
> To: russell@coker.com.au
> Cc: SE-Linux
> Subject: Re: FCGlob
> 
> Russell Coker <russell@coker.com.au> writes:
> 
> > Why would it be desirable to compile FCGlob to regular expressions?
> > Once the performance benefits are proven we might as well go 
> > full-speed ahead.
> 
> I too spent some time thinking about the FCGlob paper.  I 
> believe the reason one wants to be able to translate FCGlob 
> patterns into regular expressions is so that one can 
> implement the comparison function described in the paper as follows:

[...snip...]
 
> It seems to me that finite automata theory is called for. 
> The FCGlob pattern language as described can easily be 
> translated into a regular expression.  A regular expression 
> can be translated into a deterministic finite automata 
> without epsilon transitions.  It is easy to convert this 
> machine into one that recognizes the complement of its 
> language by complementing the set of final states of the 
> machine.  A machine that computes the intersection of two 
> languages can be produced by taking the cross product of the 
> states of the machine for each language.  Finally, it is easy 
> to test if a machine accepts no strings.  These primitives 
> can be used to implement the comparison function as specified.

Ack!  Wait!  Danger!  Will Robinson!  :)

One of the goals for using FCGlob is to avoid everything you just
described.

Since in a subsequent email you said "I have no experience implementing
finite state machines" I assume that what you mean above by all the "it
is easy" bits is that it is easy in theory.  No arguments there.  I
think one of the main points of FCGlob is that it is NOT easy in
practice.  That's why the current file context system uses heuristics
instead of a real sorting algorithm. 

I'm not trying to bash on the idea of using FAs in theory, because a lot
of the points you make are interesting.  But the observation at hand is
that replacing regular expressions in the file context specs would buy
us a lot of improvements--not the least of which is that we wouldn't
have to sort the darn things with a complicated finite automata
mechanism to get proper sorting.

Cheers,
Christopher


--
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: FCGlob

[John D. Ramsdell]

"Christopher Ashworth" <cashworth@tresys.com> writes:

> Ack!  Wait!  Danger!  Will Robinson!  :)

I'm laughing.  I watched first runs of that show.  I hope your arms
were flailing as you wrote that text.

> Since in a subsequent email you said "I have no experience
> implementing finite state machines" I assume that what you mean
> above by all the "it is easy" bits is that it is easy in theory.

This is correct.  It could be easy in practice, I just don't know.

> That's why the current file context system uses heuristics instead
> of a real sorting algorithm.

The paper states that an FCGlob prototype would require creating:

   A comparison function that receives two patterns as parameters and
   returns the set relationship. Possible set relationships between
   the set of paths pattern A matches and the set of paths pattern B
   matches are: subset, superset, disjoint and ambiguous.

I speculated that finite automata is required to implement the
comparison function as specified.  Do you have an alternative
algorithm that meets the above specification?  I don't recall seeing
one in the paper.

> But the observation at hand is that replacing regular expressions in
> the file context specs would buy us a lot of improvements.

As I said at the meeting, I like the idea of using file globbing
syntax as I agree with your assertion they are less error prone.

John

--
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: FCGlob

[John D. Ramsdell]

I think I understand now.  When you say ambiguous, you mean your
heuristic is unable to determine if two patterns are related by
subset, superset, or being disjoint.  In short, it always gives the
correct answer when two patterns are related by subset, superset, or
is disjoint, so the heuristic is safe.

John

"Christopher Ashworth" <cashworth@tresys.com> writes:

> Hullo John,
> 
> > -----Original Message-----
> > From: owner-selinux@tycho.nsa.gov 
> > [mailto:owner-selinux@tycho.nsa.gov] On Behalf Of John D. Ramsdell
> > Sent: Tuesday, April 17, 2007 7:24 AM
> > To: russell@coker.com.au
> > Cc: SE-Linux
> > Subject: Re: FCGlob
> > 
> > Russell Coker <russell@coker.com.au> writes:
> > 
> > > Why would it be desirable to compile FCGlob to regular expressions?
> > > Once the performance benefits are proven we might as well go 
> > > full-speed ahead.
> > 
> > I too spent some time thinking about the FCGlob paper.  I 
> > believe the reason one wants to be able to translate FCGlob 
> > patterns into regular expressions is so that one can 
> > implement the comparison function described in the paper as follows:
> 
> [...snip...]
>  
> > It seems to me that finite automata theory is called for. 
> > The FCGlob pattern language as described can easily be 
> > translated into a regular expression.  A regular expression 
> > can be translated into a deterministic finite automata 
> > without epsilon transitions.  It is easy to convert this 
> > machine into one that recognizes the complement of its 
> > language by complementing the set of final states of the 
> > machine.  A machine that computes the intersection of two 
> > languages can be produced by taking the cross product of the 
> > states of the machine for each language.  Finally, it is easy 
> > to test if a machine accepts no strings.  These primitives 
> > can be used to implement the comparison function as specified.
> 
> Ack!  Wait!  Danger!  Will Robinson!  :)
> 
> One of the goals for using FCGlob is to avoid everything you just
> described.
> 
> Since in a subsequent email you said "I have no experience implementing
> finite state machines" I assume that what you mean above by all the "it
> is easy" bits is that it is easy in theory.  No arguments there.  I
> think one of the main points of FCGlob is that it is NOT easy in
> practice.  That's why the current file context system uses heuristics
> instead of a real sorting algorithm. 
> 
> I'm not trying to bash on the idea of using FAs in theory, because a lot
> of the points you make are interesting.  But the observation at hand is
> that replacing regular expressions in the file context specs would buy
> us a lot of improvements--not the least of which is that we wouldn't
> have to sort the darn things with a complicated finite automata
> mechanism to get proper sorting.
> 
> Cheers,
> Christopher

--
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: FCGlob

[James Antill]

[-- Attachment #1: Type: text/plain, Size: 1305 bytes --]

On Tue, 2007-04-17 at 13:51 -0400, John D. Ramsdell wrote:

> The paper states that an FCGlob prototype would require creating:
> 
>    A comparison function that receives two patterns as parameters and
>    returns the set relationship. Possible set relationships between
>    the set of paths pattern A matches and the set of paths pattern B
>    matches are: subset, superset, disjoint and ambiguous.
> 
> I speculated that finite automata is required to implement the
> comparison function as specified.  Do you have an alternative
> algorithm that meets the above specification?  I don't recall seeing
> one in the paper.

 Sections two and three (and figure 3 within section three) explains
this, AIUI. The idea is that you can split the "patterns" into a list of
nodes and the easily compare nodes, so:

cmp("/x/y/a*/**/b", "/x/**/b")

  ==

cmp(["x", "y", "a*", "**", "b"], ["x", "**", "b"])

  ==

cmp(["x", "y", "a*", "b"], ["x", "*", "*", "*", "b"])

...and the comparison function for the last part should "be easy",
although AIUI they hadn't written it.

-- 
James Antill - <james.antill@redhat.com>
setsockopt(fd, IPPROTO_TCP, TCP_CONGESTION, ...);
setsockopt(fd, IPPROTO_TCP, TCP_DEFER_ACCEPT, ...);
setsockopt(fd, SOL_SOCKET,  SO_ATTACH_FILTER, ...);


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: FCGlob

[James Athey]

On Tue, 2007-04-17 at 21:07 +1100, Russell Coker wrote:
> Page 3 states that a down-side is "the tree would be a binary file and not 
> human readable any more".  Why would this be so?
Perhaps this part of the paper could have been clearer.  The only reason
to leave the file_contexts in a binary format would be to save time when
parsing them into the tree for use by matchpathcon and semanage.  In
retrospect, this suggestion was premature; code first, optimize later,
right?
> Why would it be desirable to compile FCGlob to regular expressions?  Once the 
> performance benefits are proven we might as well go full-speed ahead.
It's not desirable, but it is necessary for backwards compatibility with old
toolchains.  Newer toolchains would use FCGlob directly.
> As for regex's that have no clear meaning, the only thing to do is to remove 
> them and wait for the original policy author to complain.  There are many 
> regular expressions that never matched anything and probably many more that 
> match old versions of software.
Old versions of software matter.  For example, RHEL 4 is a supported
platform for reference policy, and any file contexts that are specific
to RHEL4 need to stay in the policy, marked off with an
ifdef(`distro_rhel4' if necessary.

There also seems to be some confusion about how FCGlob contexts can be
compared and sorted.  There's a handwaving explanation of the comparison
algorithm in the presentation on FCGlob from the 2007 SELinux Symposium:
http://selinux-symposium.org/2007/slides/03-fcglob.pdf .  Look at pages
8 and 9.

James


--
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: FCGlob

[Russell Coker]

On Wednesday 18 April 2007 05:07, James Athey <jathey@tresys.com> wrote:
> On Tue, 2007-04-17 at 21:07 +1100, Russell Coker wrote:
> > Page 3 states that a down-side is "the tree would be a binary file and
> > not human readable any more".  Why would this be so?
>
> Perhaps this part of the paper could have been clearer.  The only reason
> to leave the file_contexts in a binary format would be to save time when
> parsing them into the tree for use by matchpathcon and semanage.  In
> retrospect, this suggestion was premature; code first, optimize later,
> right?

That depends.  If one of the major aims of the code is to improve performance 
then a certain degree of optimisation should be done to prove it's worth.

> > As for regex's that have no clear meaning, the only thing to do is to
> > remove them and wait for the original policy author to complain.  There
> > are many regular expressions that never matched anything and probably
> > many more that match old versions of software.
>
> Old versions of software matter.  For example, RHEL 4 is a supported
> platform for reference policy, and any file contexts that are specific
> to RHEL4 need to stay in the policy, marked off with an
> ifdef(`distro_rhel4' if necessary.

Why do you want to do that?  The Red Hat support agreement was always that if 
you use any policy other than the one that they ship then you must reproduce 
bugs on either the Red Hat policy or a machine with SE Linux disabled (often 
permissive-mode would do).  Given this situation why would there be demand 
for a newer policy on RHEL4?  Red Hat is still providing policy updates for 
RHEL4 as needed.

There is also nothing stopping anyone from maintaining a separate policy tree 
for RHEL4.  Why compromise development of the new tree when we can have 
separate trees and avoid the effort?

-- 
russell@coker.com.au
http://etbe.blogspot.com/          My Blog

http://www.coker.com.au/sponsorship.html Sponsoring Free Software development

--
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: FCGlob

[John D. Ramsdell]

James Athey <jathey@tresys.com> writes:

> There also seems to be some confusion about how FCGlob contexts can be
> compared and sorted.  There's a handwaving explanation of the comparison
> algorithm in the presentation on FCGlob from the 2007 SELinux Symposium:
> http://selinux-symposium.org/2007/slides/03-fcglob.pdf .  Look at pages
> 8 and 9.

I read this and understand now.  Thanks for the pointer.

John

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