danwalsh

One of the big changes when we went from FC4 to FC5 was the introduction of Modular Policy.  In FC4 and RHEL4 we use a single Monolithic policy.  In this policy we were able to setup the file context in the sort order, manually.  Since we controlled all of the policy we were able to hard code the sort order in a LIFO format.  So when a file gets put on disk it would get the file context of the "Last Regular Expression that matched from the /etc/selinux/targeted/contexts/file_contexts files.  We did add a couple of additional files_contexts files.  One would be the .local file so that administrators could add their own local customizations and the .homedirs file which genhomedircon would generate to map the home directories.

The actuall algorithm was then to take /etc/selinux/targeted/contexts/file_contexts and append on file_contexts.homedir and file_contexts.local.

With the introduction of loadable modules this all changed.  We no longer keep all of the file contexts in one RPM package.  So we needed a mechanism for "sorting" the file context.     Understanding the sorting algorithm is critical to making sure your policy and file_contexts gets added to the system correctlyand files get put on disk with the correct file context.

Christopher Ashworth of Tresys, sent a couple of  Emails to the Fedora-SELinux list that explains the algorithm.

The sorting algorithm is based on the following heuristics, applied in this order:

When comparing two file contexts A and B...

- if A is a regular expression and B is not, A is less specific than B
- if A's stem length (the number of characters before the first regular expression wildcard) is shorter than B's stem length, A is less specific than B

"Wildcard" isn't the best word to use here. "Meta character" is better.
They include:

. ^ $ ? * + | [ ( {

- if A's string length (the entire length of the file context string) is shorter than B's string length, A is less specific than B
- if A does not have a specified type and B does, A is less specific than B.
- else, they are considered equally specific.

These are the same heuristics applied to file contexts when building reference policy.

The sort is implemented as a stable iterative mergesort.


Understanding this algorithm is critical to writing good policy.