-
Notifications
You must be signed in to change notification settings - Fork 21
Writing New libpoldiff Modules
August 1, 2007
##0. Introduction
libpoldiff is a library to be used in conjunction with libapol to find "semantic" differences between policies. For the purposes of this HOWTO, the term "semantic" refers to how the SELinux kernel would enforce accesses. If two policies could ever be enforced differently then they are defined to be semantically different.
libpoldiff operates by breaking a policy into various 'policy items'. Examples of items are users, object classes, and type enforcement rules. These items correspond to flags passed into the sediff program. So as to be extensible, libpoldiff was designed to allow one to add new diff modules (and hence additional flags to sediff). These modules should operate independent of each other and without regard to ordering of modules.
libpoldiff implements what we term "the generic diffing algorithm", akin to a merge sort. The algorithm takes two ordered lists of items and successively picks the first item from the lists. If the two match, according to the items' comparison function, then they are deemed the same. Otherwise the same ordering used to generate the lists may also be used to determine if one was added or removed from the policy.
As an example, consider a diff of users for two hypothetical SELinux policies, "orig.policy" and "updated.policy". Within orig.policy are users adam_u, charlie_u, and dave_u. updated.policy has the users adam_u, bob_u, and charlie_u. The first step of the generic diffing algorithm is to get the ordered list of items. Let the ordering algorithm be alphabetical order; thus the lists would be:
orig.policy -> {adam_u, charlie_u, dave_u}
updated.policy -> {adam_u, bob_u, charlie_u}
The algorithm picks the first item from each list and compares them. As that "adam_u" is the same as "adam_u", the algorithm accepts them as the same and continues. The next two items are "charlie_u" and "bob_u". The ordering functions finds "bob_u" to be "earlier" than "charlie_u" (because it appears earlier alphabetically), "bob_u" is marked as item added to updated.policy. The algorithm keeps "charlie_u" from the first policy but advances the pointer for the second list. These "charlie_u" are the same. The remaining type, "dave_u", has no complement in the second list and is thus marked as removed.
Of course, finding differences for users is not as simple as comparing their names. In addition one must also examine the roles assigned to them as well. Comparing names was a "shallow diff"; checking roles is a "deep diff". The deep diff must look at all aspects of the two items to determine if they are the same, modified, modified-by-adding-a-type, or modified-by-removing-a-type. (At this time the users' allowed MLS ranges and default range would also be checked.)
To complicate things, consider the aspect of type remapping. Type names may be changed between the policies; they could also be joined into a new type and conversely split. Thus one must be careful how the ordered lists of types are generated. The functions type_map_lookup() and type_map_lookup_reverse() will prove essential.
If a difference was found, either via a shallow diff or a deep diff,
then an "item diff" struct must be created. If it the difference was
added or removed then libpoldiff's poldiff_do_item_diff() will
call the item diff creation function. If instead the difference was
found within the deep diff comparison function then that function is
responsible for creating the item diff struct. The item diff struct is
used by each item's to_string() function to create a human-readable
report.
The following walkthrough describes the process for writing a diff for items between the original and modified policies. The shallow diff is to see if a type in the original policy exists in the modified policy, with respect to the type map. The deep diff determines if the types have the same set of attributes.
Create a new file, libpoldiff/include/poldiff/type_diff.h, to declare publicly accessible functions. At least three functions must exist here:
extern void poldiff_type_get_stats(poldiff_t *diff, size_t stats[5]);
extern apol_vector_t *poldiff_get_type_vector(poldiff_t *diff);
extern poldiff_form_e *poldiff_type_get_form(const void *type);
extern char *poldiff_type_to_string(poldiff_t *diff, const void *type);
(The reason for using a void * in poldiff_type_to_string() will become apparant in section 3d.) Also in this file, declare an opaque object to hold a single type difference:
typedef struct poldiff_type poldiff_type_t;
Once a user gets a vector of poldiff_type_t objects, via poldiff_get_type_vector(), he may want to do a number of things with it. He could print it via poldiff_type_to_string() or get its form; or just get the type's name, list of added attributes, or list of removed attributes. Therefore add these three functions to type_diff.h:
extern const char *poldiff_type_get_name(poldiff_type_t *type);
extern apol_vector_t *poldiff_type_get_added_attribs(poldiff_type_t *type);
extern apol_vector_t *poldiff_type_get_removed_attribs(poldiff_type_t *type);
As a convenience to developers, one should only need to #include the public poldiff.h to pick up all diff modules. Modify libpoldiff/include/poldiff/poldiff.h in the vicinity of line 187:
#include <poldiff/type_diff.h>
Finally, modify libpoldiff/include/poldiff/Makefile.am by adding an entry for type_diff.h.
There will be functions accessible only between library files (i.e.,
protected functions). To distinguish public functions from those that
are protected, do not prefix these with poldiff_. Create a new file,
libpoldiff/src/type_internal.h, that declares protected routines.
libpoldiff requires these four functions to exist:
apol_vector_t *type_get_items(poldiff_t *diff, apol_policy_t *policy);
int type_new_diff(poldiff_t *diff, poldiff_form_e form, const void *item);
int type_comp(const void *x, const void *y, poldiff_t *diff);
int type_deep_diff(poldiff_t *diff, const void *x, const void *y);
Associated with the computed list of poldiff_type_t objects is a
summary structure. Check that libpoldiff/src/poldiff_internal.h has
declare a struct poldiff_type_summary, then add the following line to
the protected header:
typedef struct poldiff_type_summary poldiff_type_summary_t;
As with all other poldiff objects, you will need a constructor and a destructor:
poldiff_type_summary_t *type_create(void);
void type_destroy(poldiff_type_summary_t **ts);
As a convenience to developers, one should only need to #include the protected poldiff_internal.h to pick up all diff modules. Modify libpoldiff/src/poldiff_internal.h in the vicinity of line 50:
#include "type_internal.h"
Finally, modify libpoldiff/src/Makefile.am by adding an entry for type_internal.h.
Create a new file, libpoldiff/src/type_diff.c, to implement all public, protected, and any necessary private functions. First declare the contents of the structures:
struct poldiff_type_summary {
size_t num_added;
size_t num_removed;
size_t num_modified;
apol_vector_t *diffs; /* vector of poldiff_type_t */
};
struct poldiff_type {
char *name;
poldiff_form_e form;
apol_vector_t *added_attribs; /* vector of char* */
apol_vector_t *removed_attribs; /* vector of char* */
};
The public functions are easy to write.
-
poldiff_type_get_stats() fetches the fields diff->type_diffs->num_added, diff->type_diffs->num_removed, and diff->type_diffs->num_modified.
-
poldiff_type_get_form() fetches an individual result's form. Note that you must first cast the second parameter from void* to a poldiff_type_t*, because this function operates upon items returned by poldiff_get_type_vector().
-
poldiff_type_to_string() returns an allocated string akin to poldiff_user_to_string(). Note that you must first cast the second parameter from void* to a poldiff_type_t*, because this function operates upon items returned by poldiff_get_type_vector().
-
poldiff_get_type_vector() returns diff->type_diffs->diffs.
The rest of the public functions are accessors into a poldiff_type_t object.
The protected functions are more difficult.
-
type_create() and type_destroy() affect a poldiff_type_summary_t object.
-
The other protected functions are described in section 3e.
Finally, modify libpoldiff/src/Makefile.am by adding an entry for type_diff.c.
The main library now needs to create and destroy the poldiff_type_summary_t object and to actually diff types. Make these changes to libpoldiff/src/poldiff.c:
-
Create a poldiff_type_summary_t object by calling type_create() within poldiff_create().
-
Destroy the summary by calling type_destroy() within poldiff_destroy().
-
To enforce that all diff modules have the requisite public and protected functions, one must fulfill the requirements as given by a poldiff_item_record, as defined on line 41. The first four callbacks are satisfied by the first four public functions, the remainder are met by protected functions. Thus add a new record to the item_records[] array like so:
/* ... */
{
"type",
POLDIFF_DIFF_TYPES,
poldiff_type_get_stats,
poldiff_get_type_vector,
poldiff_type_get_form,
poldiff_type_to_string,
type_reset,
type_get_items,
type_comp,
type_new_diff,
type_deep_diff
},
/* ... */
Finally, for the public functions to be accessible through
libpoldiff.so, add this line to libpoldiff/src/libpoldiff.map under the
global category:
poldiff_type_*;
Rather than comparing qpol_type_t pointers from one policy to another, it is more convenient to convert those pointers to "pseudo-type values", which are represented as uint32_ts. These new values handle the type mappings between policies. Whenever a difference is found, convert those pseudo-type values back to the component qpol_type_t pointers. With type splits and type joins, a single pseudo-type value may map to multiple qpol_type_t pointers.
First look at type_get_items(). Its job is to return a sorted list of unique items. Write it like this:
apol_vector_t *type_get_items(poldiff_t *diff, apol_policy_t *policy)
{
get an iterator of types from the policy
allocate a new vector v
for each item in the iterator,
convert qpol_type_t* to uint32_t via type_map_lookup()
append that uint32_t to v
sort and unquify v
return v
}
type_map_lookup() needs a third parameter that says from which policy the type originated. Use these lines to calculate the parameter:
if (policy == diff->orig_pol)
which_pol = POLDIFF_POLICY_ORIG;
else
which_pol = POLDIFF_POLICY_MOD;
Now that you have a vector of pseudo-type values, all further functions will need to be in terms of these values. libpoldiff will pass elements from the type_get_items() vector into your protected functions. In this walkthrough you will thus need to cast all values from void* to uint32_t because type_get_items() returned a vector of uint32_ts. For example:
int type_comp(const void *x, const void *y,
poldiff_t *diff __attribute__((unused)))
{
uint32_t t1 = (uint32_t) x;
uint32_t t2 = (uint32_t) y;
return t1 - t2;
}
int type_deep_diff(poldiff_t *diff, const void *x, const void *y)
{
uint32_t t1 = (uint32_t) x;
uint32_t t2 = (uint32_t) y;
apol_vector_t *v1 = type_map_lookup_reverse(diff, t1,
POLDIFF_POLICY_ORIG);
apol_vector_t *v2 = type_map_lookup_reverse(diff, t2,
POLDIFF_POLICY_ORIG);
apol_vector_t *added_attribs, *removed_attribs;
let vector a1 = union of all attributes for all types in vector v1
let vector a2 = union of all attributes for all types in vector v2
sort and uniquify a1
sort and uniquify a2
for all attributes in a1 not in a2,
append to removed_attribs those attributes
for all attributes in a2 not in a1,
append to added_attribs those attributes
if a1 is not empty or a2 is not empty, then foreach type in v1,
create a new poldiff_type_t
set the poldiff_type_t's name to the type's name
set the form to POLDIFF_FORM_MODIFIED
clone added_attribs
clone removed_attribs
append the poldiff_type_t to diff->type_diffs->diffs
if no poldiff_type_t was created
return 0
else
return non-zero
}
int type_new_diff(poldiff_t *diff, poldiff_form_e form, const void *item)
{
uint32_t t = (uint32_t) item;
apol_vector_t *v;
if (form == POLDIFF_FORM_REMOVED)
v = type_map_lookup(diff, t, POLDIFF_POLICY_ORIG);
else
v = type_map_lookup(diff, t, POLDIFF_POLICY_MOD);
foreach type in v,
create a new poldiff_type_t
set the poldiff_type_t's name to the type's name
set the form to form
append the poldiff_type_t to diff->type_diffs->diffs
}
One implementation of creating temporary vectors similar to added_attribs and removed_attribs may be found at libpoldiff/src/role_diff.c:role_deep_diff().