INCREASING PERFORMANCE AND
GRANULARITY IN ROLE-BASED ACCESSCONTROL SYSTEMSA CASE STUDY IN GRSECURITY
Bradley Spengler (bspengle@bucknell.edu)

ABSTRACT

1. INTRODUCTION

There is a movement in progress
among operating system vendors tobring greater security throughpreventative measures. One suchmeasure making headway in the Linux
operating system is Role-Based AccessControl (RBAC). For such a measure to
be widely accepted, it needs to have an
insignificant performance hit and scale
well in large corporate environments.
Such a measure also needs to be intuitiveand require as little manual configurationas possible, while at the same time
providing an effective level of security.
This paper provides a case study of an
RBAC system and illustrates changes
that were made in order to help it
become more widely accepted andprovide a strong level of protection
while still being administrator-friendly.
The changes involved altering data
structures to remove algorithmicallycomplex bottlenecks, providing dynamic
unions of policy to ease configuration
and reduce memory usage, allowing
dynamic interpretation of wildcards insecurity policy, implementing ananticipatory memory allocator, andproviding a robust method of defining
allowed user and group transitions on aLinux system.

In today's globally networked
society, security is of great concern toeveryone, from the individual home user
to the corporate giants. Security is aconcern for good reason, as the numberof successful attacks against computer
systems increases yearly. If a perfectsolution in the technical sense to the
problem of security existed, the global
community would still not accept it.
Often, the claim is made that
performance must be sacrificed in thename of security. For this reason, many
commercial entities are unwilling to add
additional levels of security to theiralready resource-starved systems. In
addition to a base level performancedecrease, scalability plays a role,
especially for large corporations who
have thousands of users and incredibly
complex and diverse software systems.
In addition to incurring a negligible
performance hit, a security system thatwill be accepted by the global
community must require little to no
manual configuration. In other words,
the security system must be a solution
and not a toolbox for an administrator tohand-write custom policies for every
machine under his/her control. Creating
an effective security solution as opposedto an effective security toolbox isperhaps not obviously a non-trivial task.
A few questions that must be resolved
are: How do we anticipate future
legitimate usage? How do we determine
what resources are important to protect?
When do we decide to label anapplication as privileged? How do we
reduce policies to a manageable size
while retaining the same level of
security?
Algorithms devised to solve theproblems these questions describe are
obviously complex in design and most
likely complex in the time and spacesense of algorithm complexity. Thus,
innovative ideas need to be used for boththe problems themselves and thesolutions to the problems. The primary
focus of my recent research has been to
apply intelligent solutions to the alreadypresent solutions I have developed toanswer the questions above.
A necessary decision in a usable
security system is to abstract the policy
definition from the details of theoperating system. Administrators
generally do not understand the security
ramifications of every single system call
implemented by the operating system, so
by abstracting policy permissions into
read, write, execute, etc. theadministrator immediately knows whatkind of operations are allowed on a
resource. Even the most knowledgeableof administrators might not be aware that
it is possible to kill a process not onlywith the kill system call, but also byusing a number of flags of the fcntl
system call.
Of course, there is a tradeoff being
made here between granularity andusability. For a security system to beboth flexible and tightly controlling ofresources, it needs to provide a highlevel of granularity. One direction thatcan be taken in regards to this tradeoff isto only increase granularity where there
is a definite security benefit. For
instance, restricting whether a process
can call the getpid system call has no
security benefit, so enforcing such athing in the security system would
simply add bloat and be confusing to theadministrator. Increasing granularity
where there is a security benefit has been
the secondary focus of my recent
research.

2. GRSECURITY
The results of my research into
performance and granularity in security
systems have been implemented in thegrsecurity [0] project. Grsecurity exists
as a patch to the 2.4 and 2.6 trees of theLinux kernel and provides many security
features [1] from the operating systemlevel. It employs a "detection,
prevention, and containment" [2] modelthrough its wide spectrum of security
enhancements.
Among its list of features include
change root restrictions that disallow a
process with a file system root changedby the chroot system call fromperforming certain operations that would
allow it to access the global file systemor affect outside processes in any way.
Grsecurity also includes the work of the
PaX project [3] that provides protection
against exploitation of entire classes ofaddress space bugs, including the mostcommonly exploited software
vulnerability today: the buffer overflow.
Additionally, grsecurity provides arobust Role-Based Access Control(RBAC) system that offers fine-grained
auditing in addition to access control.

3. Role-Based Access Control(RBAC)

According to [4], Role-Based
Access Control allows access decisions
to be "based on the roles that individual
users have as part of an organization."
Roles are simply a descriptor for thekinds of tasks a user can perform. In thereal world, a role can be a doctor, nurse,
teller, manager, etc. In an RBAC
system, a role can be created for a DNS
server administrator, local users that
only check their mail, or remote users ofa source code repository like CVS. For
these roles, the policy administrator can
how users within those roles can interact
with the system on a per-process basis.
Essentially, each role will its own viewof the file system and other processes.
RBAC systems also carry over concepts
from Mandatory Access Control (MAC)
such as subjects and objects. Subjects
are labels for processes, while objects
are generally labels for files being
accessed. [5]Grsecurity also features IP-based
roles. For any role, a list of IP addresses
can be specified with optional netmasksthat define which hosts can use the role.
If a user logged in from a host not
specified in the list for the role attempts
to use the role, they will fall backthrough the role heirarchy until anapplicable role can be found. In
grsecurity, the role hierarchy moves fromhigh to low in the following order:
special role, user role, group role, default
role. The default role is the role that is
applied when no other role applies.

Grsecurity takes the basic conceptof a Role-Based Access Control systemand provides several useful extensions.

Grsecurity also implements roletransition tables. These allow the policy
administrator to specify the special roles
to which a given role can transition.
Grsecurity provides both authenticatedand non-authenticated access to special
roles. Role transition tables arenecessary in the case of nonauthenticated access and provide an
additional layer of protection in the caseof a compromised password forauthenticated access.

In grsecurity, roles are split into
three different categories: user, group,and special roles. User and group roles
are roles that are tied to specific user orgroup IDs. To illustrate, if anapplication were to call setuid(31) and
UID 31 had an associated user role, thenthat user role would be automaticallyapplied to the application. Special roles
however can be created and assigned
arbitrarily as they have no association
with the UNIX user or group ID system.
Since a design goal of grsecurity is neverto grant any privilege over what theLinux system would normally allow,
special roles are incredibly useful for
creating separate administrator roles on
the system, as every administrator stillneeds to have UID 0.

Perhaps most importantly,
grsecurity is the only free software
security system that features anintelligent learning system that cangenerate least-privilege policies for theentire system with no configuration.
The learning system intercepts every
access checkpoint in the RBAC systemand sends a log entry through a character
device to an application in user spacethat caches the most frequently logged
entries and writes all logs not existing in
the cache to disk. Each log entry
includes the full pathname of the binary
or script that was executed for theprocess to be created, the UID and GIDof the process, the full pathname, inodenumber, device number, and operation
type of the target file, the number of theLinux capability used, the socket type,protocol, IP address, and port involvedin a socket operation, and the resource
type and requested resource amount.
With this information, very descriptive
policies can be generated. The learningfeature can be used on the entire system,a single role, or a single process. Whenlearning is performed on a single role orprocess, the rest of the system can still
be protected. Additionally, only accessattempts that are denied for that role orprocess are logged by the learning
system, so it can be very useful incorrecting a non-functioning policy.

important files within /etc is not.
Analysis involves detecting whether areduction led to a weakened policy andauto-correcting the weakness. For
instance, if a number read accesses in /etc were reduced to read access to all of /etc, this would cause the problem ofleaving the private SSH keys located in /etc/ssh readable. In this case, theanalysis algorithm would insert a rule
disallowing reads to /etc/ssh. Because
these processes are so complex in termsof time and memory consumption, theperformance review accomplishedthrough my research was most welcome.

The learning log analyzer and ruleset generator is a very complex programas it attempts to solve the difficult
problems stated in the introduction. The
application performs a complex multistage graph and heuristics-based
reduction and analysis of rules.
Reduction involves reducing the number
rules in a policy in appropriate ways.
For instance, reducing 1000 similaraccesses to randomly named temporary
files located within /tmp is appropriate,while reducing two different accesses to

4. METHODOLOGY

%
time
53.89
43.45
1.34
0.59
0.38
0.14
0.09

total
s/call
0.00
0.59
0.00
37.45
0.00
0.00
0.06

cumulative
self
seconds seconds calls
35.84
35.84
341732
64.73
28.89
49
65.62
0.89
405541
66.01
0.39
1
66.26
0.25
325745
66.35
0.09
379
66.41
0.06
1

self
s/call
0.00
0.59
0.00
0.39
0.00
0.00
0.06

The important area to note here is
the leftmost column, which identifies thepercentage of time spent in a single
function out of the entire application. It
is clearly visible that there are two hugebottlenecks: is_proc_object_dupe andexpand_acl. Upon analysis of the sourcecode of gradm, it was determined that

To identify the performancebottlenecks in gradm, the RBAC
administration utility of grsecurity, I
compiled the utility with profilingsupport. So that any function of linear or
polynomial complexity would be clearlyvisible, I created a rule set with over
300,000 objects. The following is theresulting profile of the application:

nameis_proc_object_dupe
expand_acl
gradmlex
gradmparse
add_proc_object_acl
check_permission
conv_user_to_kernel

the is_proc_object_dupe function has O(n) complexity, where n is the number ofobjects within the subject currently beingparsed from the centralized policy file.
However, because the function is called
during the addition of every object, thetotal effective complexity of using thefunction becomes O(n2).

The second function, expand_acl,
is related to subject inheritance in thecentralized policy file. In grsecurity's
RBAC system, the configuration
language supports inheriting the policy
subject /
/
/opt
/home
/mnt
/dev
/dev/grsec/dev/urandom/dev/random/dev/zero/dev/input/dev/psaux/dev/null/dev/tty?
/dev/console/dev/tty/dev/pts/dev/ptmx/dev/dsp/dev/mixer/dev/initctl/dev/mem/dev/kmem/dev/port
/bin
/sbin
/lib
/usr
/etc
/proc
/proc/kcore/proc/sys
/root
/tmp
/var
/var/tmp/var/log/boot/etc/grsech/etc/ssh

r
rx
rwxcd
rw
h
r
r
rw
rw
rw
rw
rw
rw
rw
rw
rw
rw
rw
rw
h
h
h
rx
rx
rx
rx
rx
rwx
h
r
r
rwcd
rwxcd
rwcd
r
r
h

of a parent subject, where parent subject
is defined as a subject placed on a parent
directory of the inheriting subject. To
illustrate using a sample configuration:

-CAP_SYS_TTY_CONFIG-CAP_LINUX_IMMUTABLE-CAP_NET_RAW-CAP_MKNOD-CAP_SYS_ADMIN-CAP_SYS_RAWIO-CAP_SYS_MODULE-CAP_SYS_PTRACE-CAP_NET_ADMIN-CAP_NET_BIND_SERVICE-CAP_SYS_CHROOT
subject /usr/sbin/sshd/etc/ssh/dev/log

dprrw+CAP_SYS_TTY_CONFIG+CAP_SYS_CHROOT
The important thing to note in thisconfiguration is that the administrator
only needed to add two more Linux
capabilities and more privileged access
to two files over the parent subject. To
simplify configuration and improvepolicy readability, he/she usedconfiguration inheritance to make the /usr/sbin/sshd subject inherit the subjectof / in this case, as / was the closest
matching parent directory. To reducecomplexity of policy enforcement in the
kernel, it was initially decided to expand
the inheritance within the administration
utility itself. The expand_acl function
performs this static subject inheritance.
To accomplish this, the expand_acl
function iterates upon every object in theparent subject and compares the object's
filename with the filename of every
filename in the inheriting subject. If thefilename does not exist in the inheriting
subject, then the object in the parent
subject is copied into the inheriting
subject. Clearly, this function has
polynomial complexity due to its nested
loops. It is specifically O(m*n), wherem is the number of objects in the parent

subject and n is the number of objects in
the inheriting subject.
Other bottlenecks were identified
without the need for profiling. To
reduce the kernel complexity of accesslookups, a decision was initially made tohave the administration utility expand
the ‘*’ and ‘?’ wildcard characters inobjects. This has a number of effects on
both performance and granularity. Since
the wildcards are interpreted at policy
enable time, an object like /tmp/* does
not apply to temporary files created after
the policy is enabled. Additionally,
every existing file matching thewildcarded has to be accessed to obtain
its inode and device numbers, which
increases run time proportional to thenumber of files the object expands to.
This also has an effect on performance inother areas of the code as the additional
objects further demonstrate the highalgorithmic complexity of certain
functions, such as the two analyzed
earlier. For example, an object like /dev/* will on most Linux systems
expand to over 1500 different objects.
Accessing each of these files andcreating new object structures for eachentry takes a considerable amount oftime relative to the total run time of anotherwise small rule set.
The learning log analysis and ruleset generation code utilizes a graphstructure to perform rule set reducation.
A level of abstraction is provided so thatthe same data structure can be used when
performing the heuristics-based
reduction. Though a discussion of theactual algorithms behind this reduction
is not appropriate for this paper, what isof importance is how the process ofconstructing the graph structures affects
performance. Each vertex in the graphcontains a dynamically allocated array ofpointers to adjacent vertices. Upon
addition of another adjacent vertex
during graph construction, the array
containing the pointers to adjacentvertices is resized to a size equal to thecurrent size plus the size necessary forthe storage of an additional pointer.
Additionally, because the graphs that
describe the access profile parsed fromthe learning log are generated
immediately, there are many calls to the
dynamic memory allocator to store theinformation for each vertex. The
resizing of pointer arrays can cause poor
performance, as the reallocation function
may have to move the array to resize it.
When dealing with large numbers ofdynamic memory allocations, the brk
system call is frequently called to expand
the size of the heap. The resulting
transfer of control to the kernel on aconstant basis greatly decreases
performance.
One area that I noticed needed
improvement in terms of granularity
involved the superuser's ability totransition to other users or groups.
This can be done through the family ofsystem calls that allow a privileged user
to modify the current process' effective,

real, saved, or file system user or group
IDs. It can also be accomplished byexecuting a setuid or setgid application
with the owner or group of the binary set
to the user or group the user wishes totransition to.
On an unmodified Linux system,
superusers have the ability to bypass thenormal DAC system, effectively
allowing them to modify files owned byother users, even if there are no suchpermissions specified that would
normally allow such a modification.
Linux does provide, however, acapability named
CAP_DAC_OVERRIDE that allows one
to disable the ability to override the
DAC system for a given process. Linuxalso provides two capabilities named
CAP_SETUID and CAP_SETGID that
permit a process to transition to otherusers or groups. In the presence of thesecapabilities, a process can effectively
recreate the CAP_DAC_OVERRIDE
capability by first checking theownership of a file it wishes to accessand then transitioning to the owner ofthe file. After it accesses the file, theprocess can return to its old user orgroup ID and repeat the process foranother file. In RBAC it is important tointerlock with the DAC permissions byadding policy enforcement at areas inwhich a process can modify its state toconform to the DAC permissions and beable to modify a given file. There is aclear lack of granularity in this case thathas an additional effect. In grsecurity's
RBAC system, changing one's real UID
or GID causes an immediate transition toan applicable user or group role. It is
important for these transitions to beprotected as well, since a process with
CAP_SETUID or CAP_SETGID canarbitrarily change to any user or grouprole.

5. IMPLEMENTATIONIn the previous section, a profile of
the administration utility was presented
that demonstrated two functions withhigh algorithmic complexity. The twofunctions, is_proc_object_dupe andexpand_acl constitute over 96% of therunning time of the application. To
correct these two bottlenecks, I proposed
two changes in my research: a hash tabledata structure for each subject that
contains pointers to each object
belonging to the subject, and kernelinterpretation of configuration
inheritance.
Three goals were made for theconversion to hash tables. The objects
belonging to each subject should still beable to be traversed in a list fashion, notby skipping over null entries in the hashtable. In addition, the change should be
abstracted from higher-level functions
and thus require minimal changes to thehigh-level code. The hash tables should
additionally be searchable by filename.
The hash function used is the sameprovided by the Linux kernel to hashfilenames. Quadratic probing was
%
time
18.94
14.20
8.88
8.28
7.69
7.10
6.51
6.51
5.92
4.14
3.55
3.25
2.96

cumulative
self
seconds seconds calls
0.32
0.32
4055410.56
0.2424992880
0.71
0.153520310.85
0.1410885220.98
0.133361521.10
0.1214405411.21
0.11
712337
1.32
0.11
1
1.42
0.10
1440541
1.49
0.07
1
1.55
0.06
3257451.61
0.06
1048477
1.66
0.05
325745chosen to handle collisions in the hashtable due to its simplicity andeffectiveness in preventing primaryclusters. Because objects would becontinually added to the subject and thenumber of them would not be predetermined, a method to resize the hashtable was created. It was noted that
although the number of subjects in agiven policy is much smaller than thenumber of objects, the same O(n2)algorithm applied to duplicate checkingof subjects. For this reason, similar hashtables were created to store pointers toeach subject belonging to a given role.
By making these changes, several
expensive routines in the administration
utility were changed to constant timecomplexity.
Below is a profile taken of theapplication after the algorithmicenhancements. You will notice that theprevious two bottlenecks havedisappeared and that now the lexer is themost time intensive operation of theapplication. You will also notice thetime percentages are more evenly
distributed among the functions, unlike
previously where two functions alone
made up 96% of the running time.
self totals/call s/call
0.00 0.00
0.00 0.00
0.00 0.00
0.00 0.00
0.00 0.00
0.00 0.00
0.00 0.00
0.11 1.62
0.00 0.00
0.07 0.07
0.00 0.00
0.00 0.00
0.00 0.00

namegradmlexpartial_name_hashlookup_name_entry
insert_name_entry
lookup_hash_entry
full_name_hashinsert_hash_entry
gradmparsenhashconv_user_to_kernel
proc_object_mode_conv
fhash
add_proc_object_acl

0.59
0.59
0.59

1.67
1.68
1.69

0.01
0.01
0.01

35134633607711058

The change to a kernelinterpretation of configuration
inheritance required many changes. On
the user land end, a pointer had to be
added to each subject, which referenced
its parent subject. Until all rules fromthe configuration file are parsed andconverted into usable data structures, thepointer remains null. After this time,each subject of every role is checked tosee if it is using configuration
inheritance. If it is, each trailing pathcomponents of the current subject's
filename is stripped off and a hashlookup is performed to find a subject in
the current role with that modified
filename. This process iterates until theremaining filename is the file systemroot. When a matching subject is found,the parent subject pointer for the current
subject is set to the matching subject. If
the subject does not use configuration
inheritance, the parent subject pointerremains null. What essentially results
when this entire process is complete arechains of inheritance for subjects. This
happens because a subject that isinherited by another subject can itself
inherit a subject, and so on. The chains
are traversable by following the parent
subject recursively until a null parent
subject pointer is found.
The kernel land changes required
for the new configuration inheritancesystem were much more extensive. The
process of passing the generated policy
to the kernel for enforcement essentiallyinvolves the kernel taking a pointer fromuser space and copying the structuresfrom user space directly, following any
pointers located within the structures andcopying them as well. Before the new

0.00 0.00
0.00 0.00
0.00 0.00

is_proc_object_dupe
insert_acl_object
is_deleted_file_dupe

configuration inheritance system, it wasnever the case that two pointers in theinformation passed to the kernelreferenced the same location. Now with
the new system, a method had to be
implemented to determine if a subject
had already been copied to the kernel, sothat the parent subject pointer could
reference the kernel address of thealready copied parent subject. Since thenumber of subjects being copied to thekernel is pre-determined, a hash table
was created that mapped the user spaceaddress of a subject to its address in the
kernel. Upon seeing a parent subject
pointer, its user space address is looked
up in the hash table. If a match is notfound, then the subject is copied into
kernel memory, the hash table isupdated, and the address of the subject inkernel memory is returned. Otherwise,
the matching kernel address is returned.
The caller of the function sets thisaddress to the parent subject pointer.
The low-level access check functions
also had to be modified for the new
inheritance system. Normally, upon
attempted access of a file, the RBAC
system would traverse down the filesystem tree towards the real file systemroot, checking every path along the way
for a matching object in the subject of
the current process. If a matching object
were found, then the requested
permissions would be checked against
the granted permissions, and either
success or failure would be returned in
the appropriate cases. With the new
configuration system, at every iterationof traversing down the file system tree,
the chain of parent subjects is followed,
and a lookup for the path at the current
iteration is performed to attempt toobtain an object. If an object is found,then the lookup function proceeds as
before with checking permissions andreturning success or failure.
Not only does this change to akernel interpretation of configuration
inheritance result in performance
improvements in user space, but it also
results in huge memory savings in the
kernel. The memory savings are mostdramatic when the inherited subject has
many objects and there are many
subjects inheriting that subject. Upon apoll of users of the RBAC system, it was
shown that many use this form ofconfiguration and will thus benefit
greatly from such a change.
The addition of a kernelinterpretation of wildcard characters inobjects was a welcome change amongusers. It provides a dynamic matching of
the object containing wildcards to thefile being accessed. This results in large
memory savings in the kernel in many
instances. For the feature to be viable
performance-wise, however, it had tohave no impact on the performance of
normal access lookups. With this inmind, a suitable solution was developed.
The general idea was to attach an arrayof filenames and allowed permissions toan object, and when the access lookup
matched that object when no explicit
object existed for the file being accessed,
the filenames in the array would bechecked against that of the file being
accessed.
To accomplish this, two problems
had to be solved. First, we needed todecide what object the wildcarded object
would be attached to. Second, we don't
want to generate a filename for every fileaccess, as the RBAC's access lookups
uses the structures provided by Linux's
Virtual File System (VFS) to identify
files by inode and device number. The

solution to the first problem was to findthe first wildcard character in thewildcarded filename, and truncate thefilename at the point where the pathcomponent started that contained thewildcard character. So for example, if
the object were /home/*/test/*/file, thenthe object that the wildcarded object
would be attached to would be /home.
We can be assured in the kernel that thisis the case since the administration
utility will enforce that there be an object
for /home when it finds a wildcarded
object that it needs to attach to the /home
object. This solution also implies thatthe access lookup functions will favor
non-wildcarded objects. That is, if theobjects /home/*/test/*/file and /home/user1/test exist and the file /home/user1/test/dir1/file is accessed,
the /home/user1/test object will match
first and thus be used to checkpermissions and grant or deny access tothe file. To solve the second problem,
filenames are generated by demand by
the access lookup functions in the RBAC
system.
Additionally, so that the filename is notrecreated every time a wildcarded object
is encountered in a lookup for a single
file, the lower level access lookup
functions have as a parameter a pointerto a pointer on the stack that references
the created filename. If the filename has
not been generated yet, the dereferenced
pointer results in a null pointer, at which
point the code will generate the filename
and update the pointer to reference thegenerated filename. If the dereferenced
pointer is non-null, then the resulting
pointer is used as a reference to thefilename. Currently, only the ‘*’ and ‘?’
wildcards are expanded, however this
could easily be extended to support suchobjects as /dev/tty[0-9]+.
The following chart demonstrates
the performance benefit of the kernelinterpretation of wildcarded objects. It
represents the time required to enable apolicy through the administration utility.
The rule set that was used contained a
combination of 4,000 objects andwildcarded objects. With the kernelinterpretation of wildcarded objects,
these objects are not expanded at all, andTo solve the problems regarding
dynamic memory allocation and resizingin the learning log analysis and rule set
generation code, an anticipatory memory
allocation system was developed. The
allocation system has two parts: an
allocator and a reallocator. The allocator
allocates a number of structures that holdpointers to large contiguous buffers.
These buffers are used for memory
allocations that are not meant to be
resized. Initially, the pointers to thecontiguous buffers are null. When an
allocation request is made, the algorithm
checks each of the structures to see if its
pointer to an allocation buffer is not null.
If the pointer is not null, the algorithm
checks to see if there is enough room inthe contiguous buffer for the allocation,and returns the allocated address if so. If
there is not enough room, the algorithm

only 4,000 objects are sent to the kernel.
Without this new enhancement, thewildcarded objects would expand to over
400,000 objects that would all be passed
directly to the kernel. You can see anenormous difference in running times of
the two versions.

continues through all the structures
looking for a contiguous buffer withenough room, or a null pointer. If a nullpointer is found, then a contiguous
buffer is allocated and the address
returned is the start of the buffer. If thealgorithm iterates to the last structurewith no success, then additional
structures are added and a newcontiguous buffer is allocated to service
the current allocation and allow for
future allocations. Because of the usageof memory allocations in the specificinstance of the learning log analysis andrule set generation code, a method to freeallocated memory was not needed. All
allocated memory is generally inconstant use until the process exits.
The reallocator requires a special
allocator that allows for reallocation.
When an allocation request is made, abuffer is allocated that allows room for astructure that contains information about
the current usage of the buffer and its
maximum size. The allocated buffer
also allows for a large gap at the end for
future growth. The returned address isthe start of the buffer plus the size of theallocation structure. Upon a reallocation
request, the address passed to thefunction is subtracted by the size of theallocation structure, and then its
members are checked to see if there isenough room in the current buffer tosatisfy the request. If there is, then theaddress passed in is simply returned. If
there is not, then the reallocation
function provided by libc is called with asize large enough to service the current
request and several future requests. The
address returned is the start of thereallocated buffer plus the size of theallocation structure. To free these kindsof allocations, the free function simply
subtracts the size of the allocation
structure and frees the resulting pointer.

To test the performance of the newmemory allocation functions, anapplication was written that simulates
the usage of memory allocation in thelearning log analysis and rule set
generation code. The following chart
demonstrates the significant
improvement over the standard memory
allocation functions. The only unusual
difference between the two runningtimes is the system time. The small
difference, around .03s, can be explainedfor. When large contiguous memory
allocations are made, the libc allocation
functions, which the new allocation
functions wrap around, do not use thebrk system call. Instead, they create an
anonymous mapping through the mmap
system call. The mmap system call ismore complex than the brk system call,thus resulting in the difference in systemtimes.

Finally, to improve the granularity
of security checks around transitioning
to different users or groups, I have added

the following syntax to the RBAC
system's configuration language:

user_transitions_allow user1 otheruser anotherusergroup_transitions_allow group1 othergroup anothergroupuser_transitions_deny root secretusergroup_transitions_deny root secretgroup
Notice that the ability is given tocontrol access to users or groups on an
inclusive or exclusive basis. To enforce
this, checks were added to every locationin the kernel where a process' user orgroup credentials change, namely the
set*id family of functions and theroutines that handle setuid and setgid
executables. If a transition to a user orgroup is not allowed, then a process'effective, real, saved, or file system useror group ID cannot be changed to the ID
for that user or group.

6. CONCLUSION
In summary, these performanceand granularity changes to grsecurity's
RBAC system have greatly increased its
ability to be a usable security system andnot just a tool box. The methodology
applied to this project to increase
performance and scalability can be used
towards other projects as well. Thanks
to these improvements, grsecurity's
RBAC system can now scale well inlarge corporate environments, an area
where many other systems would fail.

7. FUTURE WORKIn the areas of performance andgranularity, there is always room for
improvement. In light of this, I would
like to expand upon my current researchwith several projects to improve security

while requiring little configuration,
improve the performance of grsecurity's
learning system in disk, memory, andCPU usage, and improve granularity inimportant cases where a full systemcompromise can be prevented.
First, I would like to transpose an
integrity model on top of the current
RBAC framework of grsecurity. An
integrity model works well to prevent
untrusted data from affecting trusted
services. A great benefit of an integrity
model is that it requires little if any
manual configuration. The LOMAC [6]project will most likely serve as a guidefor this work.
Second, I would like to develop atransparent method of sandboxing
applications. The proposed mechanism
is as follows: a process under thecontrol of the sandbox will have its filesystem calls intercepted such that for any
operation that would modify the filesystem, a private copy of that file ismade that is operated upon. When theprocess exits, the modified files are
stored in a compressed archive andassociated with the process. If theapplication executes another program,the new program will be sandboxed aswell. This has an advantage over thechroot system call as it does not require
any source modification or the
duplication of lots of read-only code anddata. The sandboxing will be able to beturned on for a per-role and per-processbasis in the RBAC system. An example

use of this would be to sandbox all users'
shells. No files they create will exist on
the real filesystem, such as all files intheir home directories. Additionally, thismechanism removes an entire class ofbugs involving insecure file permissions,as any files with improper permissions
will not be accessible by other, possibly
malicious, users. Exploiting a setuid root
application on the system will not allow
them to modify/etc/passwd or /etc/shadow, for instance,since the change will only be made totheir private copies of the files. Notehowever, that sandboxing in this manner
will not solve the problem of a user
being able to read the contents of /etc/shadow, cracking the password, andlogging in as root or another user. For
this reason, the sandboxing will be
integrated into the RBAC system.

UNIX-like operating systems. Only
access to the first 1024 I/O ports areallowed to be specifically configured
through the ioperm system call. To
allow access to any of the remaining
64512 I/O ports, the iopl system callmust be used. By using the iopl systemcall to enable such access, immediately
all 65536 ports are allowed to beaccessed. I plan to work with the PaX
project on extending per-port
configuration to all 65536 I/O ports. As
for direct physical memory access, I planon allowing to specify within the
RBAC configuration language, whichranges within a file or device can beaccessed for reading or writing. These
two changes alone greatly reduce thepreviously massive security risk ofrunning XFree86 or other similarlycomplex applications on trusted systems.

Additionally, I would like toimplement a similar feature to one
planned by the Linux kernel developers:role-based resource limits. Currently, allresources limits except for number ofprocesses are enforced per-process.
Limiting of number of processes is doneon a per-user basis. Linux kernel
developers had planned to extend someof the other resource limits to be per-user
as well, however no work has yet been
done on this. I would like to extend theresource limits to apply to an entire role,
where such an extension is reasonable.
Resource limits such as maximum filesize would be acceptable candidates forsuch an extension.

To ease configuration and give anadditional safety blanket to allapplications on the system, I propose to
add a global role to the RBAC system.
Upon every access lookup within the
RBAC system, the global role will be
consulted first, followed by the role ofthe current process. From a usability
standpoint, the global role will give theadministrator instant information about
what kind of accesses will be impossibleon the system, no matter how the rest of
the policy is configured. It will also
reduce the amount of policy duplicatedamong roles by having it stored in one
central location.

Granularity in the case of
applications such as XFree86 is very
important. XFree86 uses privileged I/O
ports on the Intel Architecture andaccesses physical memory directly
through a character device provided by
Linux. Access to privileged I/O ports isvery coarse-grained on Linux and otherThough there is little left to bedone in the kernel portion of grsecurity's
RBAC system in terms of performance, I
plan on adding caching to accesslookups. The reason for caching is thatthough access lookups are generally O(1), they can be as bad as O(m*n) wherem is the inheritance depth of the current

subject and n is the number of pathcomponents of the pathname being
accessed. Though in practice both ofthese numbers are very small andunlikely to cause any scalability issues,caching will aid in reducing the lookup
cost of frequent accesses to the same
file. The cache will map an inode anddevice pair to the object that would
result if a full lookup were performed.
The cache will be invalidated uponcreation, deletion, and renaming.

accesses before they are inserted into thegraph structure, we will greatly reduce
the amount of time required to analyze
and generate policies for a heavily usedsystem.

Performance in the learning systemof grsecurity is currently a great concern.
Many users are generating learning logs
that are hundreds of megabytes large.
Attempts to analyze the learning logs
and generate a working policy out ofthem result in out of memory conditions.
To alleviate these problems, I plan on
taking several approaches. First, I would
like to change the learning reduction
code so that it is done in multiple passes.
That is, the logs will be read multiple
times, but the generated policy will not
be created and written out all at once.
The policy may be generated one role orprocess at a time, where only the data
relating to that role or process will be inmemory at one time. Second, I would
like to perform simple rule reduction
before learning logs are written to disk
by the learning daemon. In cases ofapplications like top, where pathnames
matching the regular expression /proc/*/exe are continually accessed, I
would like to reduce those accesses tothe regular expression before being
written to disk. This will result in hugedisk savings. I would also like toperform reduction at the stage before
access information is inserted into agraph structure. At that stage, allaccesses are sorted by filename, whichallows one to easily identify if there havebeen many accesses of the same kind toa single directory. By reducing these[2] Brad Spengler. Detection,
Prevention, and Containment: A Studyof Grsecurity.

REFERENCES[0] Grsecurity homepage.

http://www.grsecurity.net[1] Grsecurity features page.

http://www.grsecurity.net/features.php

http://www.grsecurity.net/grsecur
ity-slide_files/frame.htm[3] PaX homepage.

http://pax.grsecurity.net[4] NIST/ITL Bulletin, An Introduction
to Role-Based Access Control.
December, 1995.
http://csrc.nist.gov/rbac/NISTITL-RBAC-bulletin.html[5] Ravi S. Sandhu. Lattice-Based
Access Control Models. ACM Journals
Nov 2003. vol 26, issue 11, p9-19.

http://www.list.gmu.edu/journals/
computer/i93lbacm(org).pdf[6] Timothy Fraser. "LOMAC: MAC
You Can Live With," in the Proceedingsof the FREENIX Track, 2001 USENIX
Technical Conference, Boston,
Massachusetts, USA, 2001.

http://opensource.nailabs.com/lom
ac/docs/lomac-freenix01.pdf