Some years ago
NPR
started running a series called
This I Believe as a tribute to
Edward R. Murrow and his
original 1951 radio program of the same name.
As I commuted I would occasionally catch an episode and hear an essay
about the topic in which a contributor believed.
I would listen to an essay around a weighty topic as
God,
Love,
Funerals,
Good and Evil or
Public Service
and think, "no", "maybe", or "yeah, sure".
Then one day I heard Michael Mullane's essay on
The Rule Of Law
and I thought "Yes! This I believe!"
I particularly liked Michael's point that the
Tinkerbell effect applies to the Rule of Law.
As he says, God exists (or does not exist) whether or not you or
I believe that to be so,
but with the Rule of Law, it can only exist if almost all of us
believe in it and follow it.
As Death says to a human near the end of Terry Pratchett's
Discworld book
Hogfather,
"YOU NEED TO BELIEVE IN THINGS THAT AREN'T TRUE.
HOW ELSE CAN THEY BECOME?"
(Death always talks IN CAPITAL LETTERS.)
The Importance of Law
Why is law important?
The American
Declaration of Independence
asserts that "all men are created equal"
and
The Universal Declaration of Human Rights
asserts that "all human beings are born free and equal in dignity and rights."
To support that position we need a system of law that in fact
treats all people equally.
But even if the law does not protect all of the fundamental human rights,
it can provide an important benefit to its society:
stability
through
predictability.
To be predictable, the system of laws must be:
Understandable - the laws can be understood by most people.
Consistent - individual laws do not conflict with each other.
Extensive - the laws cover all common situations and a large portion
of less common situations.
There have been many successful nations that followed the Rule of Law
with different laws for different classes of people,
including
Rome
and
Greece.
A system of law can provide stability and a foundation for an orderly
and effective society without treating all people equally.
Prescriptive and Proscriptive Law
Prescriptive laws are those that tell us what we must do, such as
Honour thy father and thy mother.
Proscriptive laws are those that tell us what we must not do, such as
"Thou shalt not kill".
You can think of prescriptive law as
additive manufacturing:
you can start with nothing, and add pieces until you get something useful,
like building up a sculpture by adding little pieces of clay, or
3D printing.
Proscriptive law is more like
subtractive manufacturing:
you start with a block of something and carve away pieces until
you get the desired result,
like starting with a chunk of marble and carving a sculpture out of it, or
machining.
(But don't try searching for additive law or subtractive law
unless you are working with primary colors. :-) )
Given the assumption of freedom
in both of the Declarations above,
it's easier to start by saying people can do anything, then add
proscriptive laws specifying what they can't do.
Compared to the complete freedom and anarchy of a society with no laws,
you can get pretty far down the road to stability just with proscriptive laws.
Of the
Ten Commandments,
eight are proscriptive and only two are prescriptive.
Law versus Convention
While the Rule of Law normally refers to the explicit and codified laws
on the books, which can be enforced by the state, there is another set
of rules that most of us live by which are not legally mandated.
These conventions include social guidelines that prescribe how to
behave and communicate, including when and how it is appropriate to
touch (such as shaking hands or a pat on the back),
to ask for something (with "please" and "thank you"),
to offer advice
("true/kind/necessary")
or apologies,
and many other behaviors.
These conventions don't have the force of law.
If you break these rules, you won't be sent to jail or be forced
to pay someone monetary damages -
but you might find that you are a little less successful and your
life might be a little less pleasant.
Like laws, conventions are only useful if most of us agree on them,
and like laws, a widely accepted and understood set of conventions
helps make the world a little bit more predictable, which in turn
makes it a little bit easier for people to make plans and be successful.
In effect, social conventions are simply another layer of "laws"
that sit below the constitutional laws and the statute laws
(and in reality the American legal system has many other levels than
just those two).
Multiple Systems of Law
I am intrigued by the fact that we have so many different implementations
of the Rule of Law.
Every nation on Earth that abides by the Rule of Law has its own
system of law.
The ways in which the laws of nations interact is as varied as the
relationships between the nations.
For example, American Law has specific sections dealing with the
fact that there are Native American "domestic dependent nations"
within its borders that have their own laws.
Similarly, every nation has a different set of social conventions,
those unwritten rules that lubricate our everyday interactions.
On top of all those different systems of law, we have
International Law,
with the intent of providing structure for interactions between nations
when those nations have different and possibly incompatible systems of laws.
Two aspects of International Law that I find particularly thought-provoking
are the
Law of War, and
Jurisdiction.
(For an interesting bit of history about Jurisdiction, read about
Peine forte et dure.)
Meta Law
In order to be predictable, the laws must be stable and not change often;
but the laws must sometimes be changed in order to cover new situations
or to correct problems in existing laws.
One approach to improving the predictability of the system of laws
while still allowing for change is
to use a layered approach, where some laws are considered more important
than others and are thus harder to change.
The set of harder-to-change laws typically includes
the rules on how to change the laws.
This is the basis of the constitutional model, as is used in the United States,
in which the most important laws are embodied in the constitution,
with rules that make those laws much harder to change than regular laws.
A constitution will typically include rules on how both
"normal" rules and the rules embodied in the constitution can be changed.
Back in 1982, a "constitution" game by Peter Suber called Nomic
appeared in
Douglas R. Hofstadter's column, "Metamagical Themas," in
Scientific American.
In this game, players take turns proposing changes to the rules of the game.
The rules start out in two categories, "immutable" and "mutable",
corresponding to the simple two-level "constitutional" and "statute" law
that Americans are taught in civics classes.
The rules of the game tell how a player wins the game, and also tell
how the rules can be changed - including how to change the rules that
tell how to win and how to change the rules.
The Nomic game is intended to illustrate the mechanisms and possibilities
described in Peter Suber's book
The Paradox of Self-Amendment, available
online.
For the quickest read on the game, you can jump straight to the
rules,
but the
game description,
although somewhat lengthy, is also interesting.
In Suber's book he starts by asking how a legal system can deal with
paradox, when there are laws that directly contradict each other, and he
notes that
"paradoxes come and go without much notice and are dealt with without much ado."
Given that systems of laws seem always to be self-referential (since they
include rules about how to change the rules), attempting to craft a
system of laws that is also complete and consistent would seem to run into
a version of
Gödel's Incompleteness Theorem.
In practice, systems of laws are not really complete and still
blithely violate consistency, yet manage to be quite useful despite
their flaws.
Law and Software
The title of this section might refer to laws that affect software,
such as copyright law,
or it might refer to the use of software to assist in the application
of law, such as computerized law indexes or
Regulation by Software;
but in fact, I am referring to the use of law as a concept in defining
how software works.
As in a society, a programming language is built on a set of rules that
describe how statements in the language are interpreted by the computer.
The developer uses his knowledge of these rules to create a program that
instructs the computer to do something that is useful to the developer.
Imagine trying to program in a computer language with no rules.
How could you get anything done?
You could never predict the results of a statement, so you could never
make a program that produced anything predictable.
Just as different societies each have their own set of rules,
different programming languages each have their own set of rules.
And just as with social conventions, different groups of programmers
typically adopt programming conventions that are not enforced by the
compiler but are intended to make life a bit simpler for the
developers in the group.
In fact, all of the concepts discussed above are applicable to software.
You can consider that as we take a look at what it means
to define software in terms of laws.
Law and Object-Oriented Programming
Back in 1987
Naftaly Minsky and David Rozenshtein published
"A Law-Based Approach to Object-Oriented Programming"
(available for purchase
on-line)
in which they discussed how an object-oriented system can be described
in terms of the laws that control the exchange of messages between objects.
(Minsky has published quite a few
other papers
on related topics concerning law and software.)
They start by defining objects as containing state and program, with
four primitive messages (prefixed by the octothorpe character, #)
to create (#new) and destroy (#kill) objects and
to get (#get) and set (#mutate) state.
Messages are defined as a triplet of sender, message text, and target.
Message delivery goes through the law system, which can take one of
three actions:
The message can be delivered to its target.
The message text and/or target can be modified and then delivered.
The message can be blocked and thus not delivered.
With these definitions and a permissive law that allows any object to
send any message to any other object, the system does not exhibit
many of the characteristics typically associated with object-oriented
systems.
They then examine the effect of different kinds of laws,
such as allowing primitive messages to be sent only by the same object.
Through this approach they show how to implement common
object-oriented features such as
encapsulation, inheritance, and class variables
as well as less common features such as multiple inheritance,
exclusion of methods from inheritance, and triggers.
Given that the program is part of the state of the object,
it can be modified with a #mutate message,
so it is possible to describe self-modifying programs within this framework.
The laws of the system control whether and how this message is
allowed to be sent.
By defining the laws in objects that
are themselves part of the system, those laws can then be changed.
The system could start with a separate subset of laws that control
how the laws can be changed, making this approach look very much like
Suber's Constitution game.
The law system allows the laws to modify the content of
a message or redirect it to a different target,
allowing for the implementation of security checks and other
forms of enforced delegation.
I am not aware of a production system that directly uses this style of
law-based control of message passing, but there are some systems that
use a conceptually similar method of applying a set of rules to some messages
to control their delivery.
For example, in the
Java security model
different environments can
have different implementations of the SecurityManager, each with its
own definition of the security policy (i.e. rules) that controls
whether certain actions are allowed to be taken, which can be viewed as
allowing the messages requesting those actions to be delivered.
The
OSGi security model
goes further towards being a general law-based system,
including the ability to specify rules via a string and
to compose multiple security policies.
Law and Mind
For both societies and software, laws are rules telling us what we must and
must not do, or do differently,
and conventions are rules telling us what we should and
should not do, or do differently.
By following these rules and conventions, a society or a software system
can be far more productive than one with the same underlying capabilities
but where the rules and laws are less cohesive and effective
or are not followed.
Could it be that the same is true for our minds?
According to Marvin Minsky's theory of the mind as set forth in
Society of Mind,
our minds are composed of many small agents communicating with each other.
Minsky's agents are very small pieces, and the communication between them
is below our level of awareness.
Perhaps our minds use something like Naftaly Minsky's law-based message
delivery mechanism to monitor and control these low-level communications
between agents.
Maybe the biggest difference between people who are productive and
those who are not is in the different internal rules the two minds follow,
and not so much a difference in raw underlying capability.
Maybe productive people have a better set of mental rules controlling
the messages within their minds.
And if that is true, that leads to an interesting question:
to what extent is it possible for people to rewrite
their own low-level internal communication rules
to improve their performance,
and how might that be accomplished?
Many years ago I had a fence that needed to be repaired.
I got a recommendation for a fence repair man from a friend and had him
come out to take a look.
He said the panels between the posts were fine and did not need to be
replaced, I just needed new posts.
He quoted me a price for installing new fence posts
that seemed quite reasonable, and I accepted his bid.
A few days later he came back to do the job.
After he had been out there working for a while, I went out to take a look.
I was surprised when I saw how he had installed the new fence posts.
He had not removed the old posts and put new posts in their places,
as I had assumed; instead, he simply planted a new post next to each
old post and strapped them together.
I was flabbergasted, and complained to him that my expectation was that
he was going to take out the old posts and replace them with new posts.
He was nonplussed. "I told you I would install new posts," he said.
"Taking out the old posts would be way more work, and I would have to
charge you more."
Well, he had me: he had indeed said only that he would install new posts.
I was the one who assumed he would take out the old posts.
I grumbled, paid him extra to replace a few of the old posts where it was
particularly troublesome to have an extra post sticking out,
and had the whole fence replaced the right way a few years later.
Keep using gmail
One of the startups at which I worked used gmail and was acquired by
a large company that used Exchange.
Concerned about the possibility of having to move to
what we felt was a worse system,
we asked what would happen with email.
We were relieved when they said we could keep using gmail.
On the very first day that we were officially part of the new company,
we were all told that we now had Exchange email accounts.
"Hey!," we said, "you told us we could keep our gmail accounts."
"Yes, you can," came the response, "but you also need to have an
Exchange account for all official company email."
This was, of course, not what we had expected when we asked if we could
keep our gmail accounts.
But, as with the new fence posts, they had in fact kept their word and
let us keep our gmail accounts;
it was we who assumed that that would continue to be our only email account.
Everything under SCCS
At one of the places I worked, we hired a contractor to work on a subsystem.
At one point we became concerned about how he was managing his source code,
so we asked how he was doing that.
"Everything is under sccs," he said.
(This was well before the days of
git,
subversion,
cvs, or even
rcs; at the time,
sccs
(Source Code Control System)
was what most people in our industry were using.)
When he finally delivered the source code to us, we were annoyed to discover
that he simply had a directory named "sccs", and all of his source code
was contained in that directory; there was in fact no versioning or history.
Once again, this was not what we had expected.
When he said "sccs" we assumed he was talking about the source code
control system, when in fact he was just referring to a directory name;
and when he said "under" we assumed he meant "managed by", when in fact
he just meant "contained in."
A new and improved version of Android
My first smart phone was an Android phone running version 2.2.
I watched as the newer versions of Android came out, filled with
interesting new features.
Finally, an over-the-air update was available for my phone.
I eagerly updated and started playing with the new features.
My first disappointment was with the new and definitely not improved
performance: my phone was slow and laggy, and it no longer lasted
even one day on a full charge.
I was even more dismayed to discover that they had removed USB
Mass Storage Mode
(MSC or UMS)
and replaced it with a significantly less functional
alternative,
MTP
(Media Transfer Protocol).
In my case, it was completely non-functional for my use, because my
home desktop machine was running Linux, and at the time there was not
a working Linux driver for MTP mode.
I was, as you might expect, pretty ticked off.
I had assumed without thinking about it
that they would not remove a significant feature from
a new version of the software, but they never said that.
Alternate Interpretations
Ask yourself: when reading the above anecdotes, did you realize in advance
of the denouement what the problem would be for all of them?
If it had been you, would you have made the same assumptions as I did?
Sometimes something seems so obvious to us that it does not even cross
our minds that there might be an alternate interpretation.
I don't think it is possible for us to see these alternative interpretations
in every case; often it is something with which we have had no experience,
so could not be expected to know.
We do, of course, sometimes consider alternative interpretations.
In the future, if someone tells me they will install new fence posts,
I will be sure to ask for more details.
But we have to make assumptions as we deal with the world every day.
If we examined every statement and every experience
for alternative interpretations, that would
consume all of our time, and we would not have any time left to
pursue new thoughts.
We learn to make instant and unconscious judgment calls:
as long as what we hear and see has a high enough probability of an
unambiguous interpretation, the possibility that there is an alternate
interpretation does not bubble up to our conscious minds.
Overall this is a very effective strategy that lets us focus
our mental energies on situations where an unusual outcome is
more likely.
But this does mean that every once in a while we will miss something,
with undesired results.
Going beyond obvious
I have already given my recommendation to
State The Obvious.
However, as you can see from the above anecdotes, this is not always enough.
But what else can we do?
If you consider the anecdotes above,
you might notice that, in most of them,
by the time I realized that I had made an incorrect assumption,
the deed was done and I was stuck with an undesired result.
But the fence post story was a little different:
in that case, I checked up on the work before it was done.
Because I discovered the problem while it was happening,
I was able to ask for changes and get a result that
was closer to what I wanted.
Software Development
Not all of my blog posts are about software development,
but in this case the application is obvious.
Well, it seems obvious to me, but just in case it is not obvious
to everyone, I will follow my own advice and explain in detail.
In the traditional
waterfall process,
a complete and detailed specification of the desired system is created
before doing any of the implementation work.
Once that spec is done, the system is built to match it.
But, as we have seen from the anecdotes above,
even a very simple spec, such as "install new fence posts", might be
interpreted in a bizarre way that still matches the letter of the specification.
In this case, the result might be something that arguably
matches what was specified, but is not what was wanted.
Based on my personal experience and anecdotes I have heard from others,
I believe that it is very difficult to write a good spec
for something new,
and impossible to
write a spec
that can not be interpreted by somebody
in some bizarre way that satisfies the spec but is not the desired result.
Given that we can't guarantee that we can write a spec that will not be
misinterpreted, what is the alternative?
I think the only alternative is to do what I did in the fence-post case:
check up on the work and make corrections along the way.
This is embodied in a couple of the value statements in
The Agile Manifesto:
"Customer collaboration over contract negotiation" and
"Responding to change over following a plan".
If you are asking someone to create something that is very similar to
things that have been created before,
and through previous common experience there is already a shared
vocabulary sufficient to describe how the desired result compares to
those previous creations,
then you can perhaps write a spec that will get you what you want.
The closer the new thing is to those previously created things, the
easier that will be.
But in software development, where the goal is often specifically to
create something novel,
this is particularly difficult.
In that situation, I think that creating and then relying solely on a detailed
spec is less likely to result in a satisfactory outcome;
I believe an agreement on direction and major points, followed by
keeping a close eye on progress,
paying particular attention when something is being done for the first time,
is the key to good results.
Writing a Spec
I'm not saying
don't write a spec.
I'm saying you need to recognize that a spec
won't take you all the way,
and a poorly written spec can
hinder your progress.
Writing a spec is like looking at a map and planning your route:
often necessary but seldom sufficient.
You need to be prepared for construction closures, blocking accidents,
or even additional interesting sights you might decide to see along the way.
For any of these diversions, you will need to reexamine your route in
the middle of the trip and select an alternative.
For a short trip, you might not run into any such problems and thus
not need to modify your route,
but the longer the journey the more likely that at some point you will
need or want to deviate from your original route.
If you are familiar with the roads and have a clear destination,
you might be able to dispense with the initial route planning completely:
just head in the right direction and follow the signs.
Or if you are on a discovery road trip and don't have a specific
destination, then heading out without a planned route is fine.
In most cases, though, some level of advance route planning will save time.
You just need to stay agile and be prepared to change your route
along the way.
In our team project at work, we wanted to have a set of style guidelines
to allow everyone to more easily and quickly read the codebase and to
avoid spurious code reformatting changes.
As you might expect, there were different opinions on many points.
To avoid fruitless "my way is just better" discussions,
I wanted to step back and make sure we could all agree on some
general goals.
With that agreement in place, we could at least ask people to
explain how their preferred style on some point supports our
general goals.
If nobody can provide an argument to support a favored construct,
we might as well flip a coin.
Below are the goals I proposed and with which the team agreed.
I think many of these are obvious, but then I usually believe in
stating the obvious.
The first two criteria below are also listed in my post on
Software Quality Dimensions.
Your team may choose slightly different guiding principles, but I think
having the team agree on and write down their principles and asking
people to justify their proposed standards against those principles can
help short-circuit disagreements that might otherwise take longer to resolve.
Goals
In order of priority, with the most important criteria first:
First, we want our code to be correct.
This means that the code must:
perform the desired primary behavior.
behave in a defined way for expected error conditions.
not have undesirable side-effects.
not have security vulnerabilities such as buffer overflows or injections.
not have memory problems such as leaks or use of released or uninitialized memory.
Second, we want our code to be robust.
This means that the code should be written in such a way as to minimize the probability of incorrect behavior under a wide range of conditions, including when:
Authentication - assuring that the user is who he says he is.
Authorization - allowing each authenticated user to perform selected
privileged actions.
Audit - recording privileged actions to allow review of changes
or potential abuse of privileges.
Given authentication and auditing it is pretty simple to add a bit
more monitoring that is very useful for billing purposes and
resource management, so you
more often see the combination
AAA (Authentication, Authorization, Accounting) or
AAAA (Authentication, Authorization, Audit, Accounting).
In this post I discuss only authorization.
Authentication and auditing are each big topics,
so I won't try to cover them here.
Similarly, I assume that the code and data are themselves secure.
In particular, I do not cover the issue of multiple security domains
and the problem of having lower security code make requests to
higher security code.
With my focus only on authorization,
in the discussion below I assume that the user has been authenticated
so that we can trust that piece of data within the application.
I will use the language of relational databases in this post
because it is well-known and precise.
An implementation of this model can use some other mechanism to
store and query the authorization data.
The SQL examples provide precision to the discussion, but you should
be able to skip the SQL code and still gain a basic understanding of the model.
In the SQL example code I indicate replacement variables within braces;
for example the string {user} in a SQL statement indicates
that the application should plug in the user name at that point
in the expression.
For a real implementation, the actual syntax would depend on the
database access package in use.
I have run into some authorization systems intended to provide
a powerful set of capabilities for a complex situation
that were, unfortunately, themselves so complex as to make it
difficult to understand how they were supposed to work, and
even after having it explained, difficult to remember because
there was not a simple underlying model to tie it all together.
In this post I present an approach to authorization
that I believe provides a very high
level of power with a model that is relatively simple to understand
and to extend as needed.
This model initially implements a
Role-Based Access Control (RBAC) mechanism,
a widely used approach to security that is now a
NIST standard.
I add a few extensions to the common model that make it start to look
more like an
Attribute-Based Access Control (ABAC) model.
In an authorization system, we want to
separate
the management of authorization from the application.
The application should ask permission for what it wants to do,
which permission is supplied by the authorization system.
All management of the granting of the authorizations is
handled from the authorization system,
completely outside of the application.
If you build a system in which any of the abstractions used in the
management of authorizations,
such as roles, appear in the application, then, as they say,
you are doing it wrong.
In this post I focus only on the part of the system that determines
whether to grant authorization.
A separate system is required to maintain the data that is used by
the authorization system.
That maintenance can become quite complex in enterprise systems,
but I will not be discussing it further in this post except to
mention that the authorization mechanism described here can be
applied to the system that maintains the authorization data in order
to control who is allowed to modify what parts of that data.
Let's start with perhaps the simplest useful authorization model possible.
We begin with a one-column user table containing user names.
create table user(name varchar(32) primary key);
When the application wants to check for our sole authorization,
it takes a passed-in authenticated user name
and calls the authorization function with that value.
The authorization function just checks to
see if that user exists in the table.
If so, the user is authorized and the authorization function returns true;
if not, the user is not authorized and the authorization function returns false.
-- authorized if count>0
select count(*) from user where name={user};
The user-only model is too simple for most applications.
The next step is to add a one-column action table containing actions.
We will assume each action is represented by a string name,
although for performance reasons some might choose a different representation.
We add one row to this table for each restricted action;
for example, we might have entries for
login, reboot_system, and view_system_users.
With the addition of the action table we can no longer just
look up users in the user table.
We add a third table called grant
(or auth_grant, since grant is typically
a reserved word in SQL) with two columns
that are foreign-key columns to the user and action tables.
Each row of the grant table refers to a user and an action,
with the meaning that that user is granted authorization
to perform that action.
create table auth_grant(
user varchar(32) not null,
action varchar(32) not null,
constraint FK_grant_user foreign key(user)
references user(name),
constraint FK_grant_action foreign key(action)
references action(name)
);
Our authorization function will now accept a combination of values.
We will refer to this combination as the requested operation
(the NIST standard uses transaction as the unit for
which permissions are granted).
When an application wants to perform a potentially restricted operation,
it takes the passed-in authenticated user name,
adds the action it wants to perform,
and passes that data to the authorization function.
The authorization function takes the passed-in user and action arguments
and looks in the grant table
for a row in which the passed-in values for user and action
match the values in the corresponding columns in the table.
That row defines a permission to execute the requested operation.
If that row exists, the operation is authorized;
if that row does not exist, the operation is not authorized.
-- authorized if count>0
select count(*) from auth_grant where
user={user} and
action={action};
The user+action model is sufficient for many simple systems, such as
granting login rights to some users and admin rights to other users.
With just users and actions, each action granted to a user effectively
has global scope within the system.
This is fine for actions such as login which truly are intended to be
global in scope, but we would also like to be able to specify that
certain actions can be performed on specific objects.
Modern operating systems include mechanisms to grant different
access rights, such as read-file or write-file,
to specific files based on the user.
We add a one-column object table containing references to the
objects in our system for which we want to be able to issue grants,
with one row for each such object.
We are making the simplifying assumption that each object already has
a unique identifier that can be stored in our database.
We add a third column to our grant table that is a foreign-key
column to the object table, exactly analogous to the existing
references to the user and action tables.
Each row of the grant table now refers to a user, an action and
an object, with the meaning that that user is granted authorization
to perform that action on that object.
create table auth_grant(
user varchar(32) not null,
action varchar(32) not null,
object varchar(32) not null,
constraint FK_grant_user foreign key(user)
references user(name),
constraint FK_grant_action foreign key(action)
references action(name),
constraint FK_grant_object foreign key(object)
references object(name)
);
If we still want to have actions with global scope,
such as the example of a login action in the user+action model,
we can add a special system object that can be used in that situation.
Our authorization requests from the application
now include three pieces of data.
We modify our function for authorizing a restricted operation to take
an argument specifying the object, along with the user and action
arguments that we already have.
The authorization function looks in the grant table as before,
but it now must find a row that matches all three fields rather than
only user and action.
-- authorized if count>0
select count(*) from auth_grant where
user={user} and
action={action} and
object={object};
The user+action+object model presented here is used in many databases,
with the objects being database tables or views and the actions being
the four database actions of select, insert, update and delete.
There may also be additional actions such as grant (the ability to
create additional grants on an object) or actions that allow creating
and modifying users or databases.
In order to simplify the maintenance of grants when we have a large
number of users, we add a mechanism that allows us to group users together
and grant permissions to a group of users rather than just to a single user.
Users are grouped according to the roles they play; example roles are
user, administrator, and superuser.
We add a role table with one row for each role we define.
(We will look at other possible implementations later,
but this choice serves well for explaining the concepts.)
create table role(name varchar(32) primary key);
In order to indicate which users have been granted (assigned) which roles,
we add a user_role table with two columns:
the user column is a foreign key to the user table
that references the user, and
the role column is a foreign key to the role table.
A user having a role is indicated by adding a row to the
user_role table referencing that user and that role.
When granting authorization, a user will receive authorization
for all roles he has.
create table user_role(
user varchar(32) not null,
role varchar(32) not null,
constraint FK_userrole_user foreign key(user)
references user(name),
constraint FK_userrole_role foreign key(role)
references role(name)
);
We also add a role column to our grant table.
This column is a foreign key to the one column in our role table.
A row in the grant table can now refer either to a user or
to a role.
It must reference one or the other; while it might be possible to set up
a structure to enforce that constraint directly in the database,
we will skip that exercise and instead suggest that this constraint
could be enforced by an application-level database consistency check.
create table auth_grant(
user varchar(32),
role varchar(32),
action varchar(32) not null,
object varchar(32) not null,
constraint FK_grant_user foreign key(user)
references user(name),
constraint FK_grant_role foreign key(role)
references role(name),
constraint FK_grant_action foreign key(action)
references action(name),
constraint FK_grant_object foreign key(object)
references object(name)
);
The addition of roles is entirely an abstraction within the
authorization system; the application is not aware of roles.
An operation is defined by the same three values as before, and
the application calls the authorization function in the same way as before
to see if an operation is authorized,
but the authorization function has to do a little more work now.
The application still passes the user, action and object arguments to the
authorization function, and the authorization function still looks
in the grant table to see if that combination of user, action
and object is authorized, but now in addition to looking for a row
that exactly matches those three values, it also looks up all of the
roles the specified user has, and it looks for
a row in the grant table in which the action and object values
exactly match the values passed in and in which the role in the
grant table is one of the roles the user has.
If the authorization function finds
a row that exactly matches the action and object
and that exactly matches either the user or any of the user's roles
then the action is authorized; if no such matching row is found
then the action is not authorized.
-- authorized if count>0
select count(*) from auth_grant where
(user={user} or role in (select role from user_role where user={user})) and
action={action} and
object={object};
The (user+role)+action+object model presented here has been used
in the
Unix filesystem
for many years, with the objects being files
and directories, the actions being read, write and execute/search,
and the roles called groups.
In the NIST RBAC model permissions can only be assigned to roles,
not to users.
A strict implementation of this aspect could easily be implemented
by dropping the user check in our authorization test
(which also means we can drop the user column in the
grant table):
-- authorized if count>0
select count(*) from auth_grant where
role in (select role from user_role where user={user}) and
action={action} and
object={object};
Alternatively, we could think of each user as automatically being
assigned a unique role whose name is the same as the user name.
Or, we can choose never to assign any permissions to a user,
only assigning them to roles.
The NIST RBAC standard includes a concept called Role Activation
(or Role Authorization).
When a user logs in, some subset of his roles can be activated.
Allowing a user to activate and deactivate his assigned roles
gives the user a way to ensure that he (or some program he is running)
does not perform a privileged operation when he is not expecting it.
Permissions are only granted for active roles,
so even if a user has been given permissions through a role, a program will
not be able to take advantage of them unless the user
has activated a role that grants those permissions.
We can implement role activation globally by adding an is_active
column to the user_role table.
create table user_role(
user varchar(32) not null,
role varchar(32) not null,
is_active boolean not null default false,
constraint FK_userrole_user foreign key(user)
references user(name),
constraint FK_userrole_role foreign key(role)
references role(name)
);
When checking for authorization, we only include roles that are
active for that user.
If we continue to allow user-based permissions, then we would need to
add an is_active flag for those permissions as well.
When using activation it is simpler to exclude user-based permissions,
as is done in the NIST RBAC model.
-- authorized if count>0
select count(*) from auth_grant where
role in (select role from user_role where user={user} and is_active) and
action={action} and
object={object};
The NIST RBAC standard uses session-based activation rather than
global activation.
This allows a user to have multiple sessions open simultaneously
with different roles active for each session.
To implement this, rather than adding an is_active
column to the user_role table, we create a session
table that keeps track of our sessions and a
session_role table that lists the roles that are active for
each session.
create table session(
id varchar(32) primary key,
user varchar(32) not null,
constraint FK_session_user foreign key(user)
references user(name)
);
create table session_role(
session_id varchar(32) not null,
role varchar(32) not null,
constraint FK_sessionrole_sessionid foreign key(session_id)
references session(id),
constraint FK_sessionrole_role foreign key(role)
references role(name)
);
When testing for authorization we only want to use roles that are
both assigned (in the user_role table) and active (in the
session_role table).
Assuming the mechanism that maintains active roles in the session_role
table ensures that the only roles appearing in that table are in the
user_role table
(i.e. only an assigned role from the user_role table
can be active in the session_role table),
then we can
modify the authorization function to accept an additional
argument which is the session_id, and change our implementation SQL:
-- authorized if count>0
select count(*) from auth_grant where
role in (select role from session_role where user={user} and session_id={session_id}) and
action={action} and
object={object};
At this point our model includes the capabilities of RBAC0,
the first level of the NIST RBAC standard
(although the NIST model does not include action and
object as presented above).
However, in order to keep the discussion of the other aspects of
the model less cluttered, I will generally not be including role
activation in the remainder of this discussion except where noted.
Given the ability to group users into roles and thus simplify the number
of grants we need to create, we can generalize on that concept by also
allowing roles to be grouped into other roles.
In the discussion of Roles above, we added a user_role table
that allowed us to assign roles to users.
We now add a role_hierarchy table with parent and child
columns that allows us to assign roles (children)
to other roles (parents).
When collecting the list of roles for a user,
we now have to recursively consult the role_hierarchy table
to collect all of the child roles for any role the user has.
How this is actually done is heavily dependent on the implementation.
Some SQL databases include the ability to formulate recursive queries,
but most do not.
We hide this implementation detail inside a view that collects
the closure of the role-role relationships, effectively
flattening our hierarchy.
Defining this flattening in a view
allows us to change how we collect the closure of the roles
without affecting the queries that invoke this view.
In this particular example, our view is defined using a
non-recursive query that will suffice for a hierarchy
of limited depth.
-- not a full closure if the hierarchy is too deep
create view role_closure as
select distinct user, a3.child as role from user_role
join role_hierarchy as a1 on user_role.role=a1.parent or
(user_role.user=a1.parent and user_role.role=a1.child)
join role_hierarchy as a2 on a1.child=a2.parent or
(user_role.user=a2.parent and user_role.role=a2.child)
join role_hierarchy as a3 on a2.child=a3.parent or
(user_role.user=a3.parent and user_role.role=a3.child)
;
We can now use the role_closure view
in place of the user_role table:
-- authorized if count>0
select count(*) from auth_grant where
(user={user} or role in (select role from role_closure where user={user})) and
action={action} and
object={object};
If we want to use session-based activation, we can do that by
modifying our role_closure view to be based on the
session_role table rather than the user_role table:
-- not a full closure if the hierarchy is too deep
create view role_closure as
select distinct session_id, user, a3.child as role from session_role
join role_hierarchy as a1 on session_role.role=a1.parent or
(session_role.user=a1.parent and session_role.role=a1.child)
join role_hierarchy as a2 on a1.child=a2.parent or
(session_role.user=a2.parent and session_role.role=a2.child)
join role_hierarchy as a3 on a2.child=a3.parent or
(session_role.user=a3.parent and session_role.role=a3.child)
;
As above when adding session-based role activation,
the authorization SQL includes the session-id and we no longer
allow user-based permissions:
-- authorized if count>0
select count(*) from auth_grant where
role in (select role from role_closure where user={user} and session_id={session_id}) and
action={action} and
object={object};
This change can be made in any of the authorization SQL statements
given below to add session-based authorization where it is otherwise
not included.
Note that although we stated that the role parent/child relationships
form a hierarchy, there is actually no reason to limit it to that,
and our design does not preclude defining role relationships
that form a more complex graph.
We do want to avoid cycles in our role graph, as a graph with cycles
would not provide us any useful benefits, and we need to ensure
that our implementation does not blow up if the role graph happens
to have some cycles.
If we use the role_closure view implementation provided above,
an incidental benefit is that the closure mechanism is so simple and limited,
cycles will not cause any problems other than wasting a bit of
processing power.
The NIST RBAC standard defines both general and restricted forms of hierarchy
as part of the RBAC1 level.
The restricted form is a tree structure and
the general form is an arbitrary partial order.
Our model above support the general form.
NIST RBAC levels RBAC2 and RBAC3 add Constraints (to ensure support of
Separation of Duties)
and Symmetry (the ability to review permission-role assignments as well as
user-role assignments).
With the simple database implementation presented here, these capabilities
are available.
In the implementation of user roles and role hierarchies above
we added a role table, a user_role table
and a role_hierarchy table,
we added a role column to the grant table,
we added a role_closure view
and we modified our example SQL select statement for checking authorization
to use that view.
In this section I present
three alternate approaches to this step when using a relational database,
and of course there are other approaches not
discussed here that are not based on a relational database.
These implementation alternatives do not affect the basic model
being developed.
In the first alternate approach, after defining the role table
we next define the user_or_role view that is the union of those
two tables.
create view user_or_role as
(select name from user)
union all
(select name from role)
;
In the grant table, rather than adding a role column and
having the user
column be a foreign key to the user table, we make the user
column a foreign key to the user_or_role view.
Unfortunately, it is typically not possible to declare a foreign key
to a view, in which case this foreign key relationship would
have to remain implicit and not enforced by the database
(it could be part of our application-level database consistency checks).
Nonetheless, the SQL statements that join using this foreign key will
work the same as if the foreign key were declared,
although performance may be an issue if the user_or_role view can not
be indexed.
By using a materialized view it might be possible to index the view
and have a foreign key refer to it,
but then we would need to deal with rematerializing the view every
time we changed the contents of the user or role tables.
Instead of creating a role_hierarchy table,
we do the same thing to the user column of the user_role
table as we did to the grant table, making it a foreign key
to the user_or_role view rather than to the user table.
This allows the user_role table to represent which roles have
other roles as well as which roles users have directly been given.
In our second alternate implementation, we start by defining
user_or_role as a table that contains the records for
both users and roles,
with an is_role column that indicates
whether a row represents a user or a role.
We then create user and role
as appropriate views into that table.
create table user_or_role (
name varchar(32) primary key,
is_role boolean not null default false
);
create view user as
select name from user_or_role where not is_role;
create view role as
select name from user_or_role where is_role;
As in our first alternate implementation, the grant table
points to the user_or_role table, as does the user
column in the user_role table.
create table auth_grant(
user_or_role varchar(32) not null,
action varchar(32) not null,
object varchar(32) not null,
constraint FK_grant_user foreign key(user_or_role)
references user_or_role(name),
constraint FK_grant_action foreign key(action)
references action(name),
constraint FK_grant_object foreign key(object)
references object(name)
);
create table user_role(
user varchar(32) not null,
role varchar(32) not null,
constraint FK_userrole_user foreign key(user)
references user_or_role(name),
constraint FK_userrole_role foreign key(role)
references role(name)
);
Many databases, including MySQL,
do not allow indexes or foreign keys on views, so neither of
the above two alternate implementations will work very well on those
databases,
and the table statements would have to be modified not to declare
foreign keys to view columns.
If we want to use indexes and foreign keys, we have to compromise our
data model a bit and not use views when we need foreign keys,
which leads us to our final alternative.
In our third alternate implementation, we don't have a
separate role table or view.
Instead, we use the user_or_role approach as in
the second alternative above:
we place the role names into the
user table and add an is_role column that indicates
whether a row represents a user or a role.
create table user (
name varchar(32) primary key,
is_role boolean not null default false
);
In our user_role table, in which the role column
was a foreign key to the role table, we make that column
instead be a foreign key to the user table, where we are
now storing our role names.
create table user_role(
user varchar(32) not null,
role varchar(32) not null,
constraint FK_userrole_user foreign key(user)
references user(name),
constraint FK_userrole_role foreign key(role)
references user(name)
);
We don't need a role_hierarchy table because we can now
represent those role-to-role relationships in the user_role table.
In our role_closure view we replace the role_hierarchy
references with user_role references.
create view role_closure as
select distinct a0.user, a3.role from user_role as a0
join user_role as a1 on a0.role=a1.user or
(a0.user=a1.user and a0.role=a1.role)
join user_role as a2 on a1.role=a2.user or
(a0.user=a2.user and a0.role=a2.role)
join user_role as a3 on a2.role=a3.user or
(a0.user=a3.user and a0.role=a3.role)
;
Because we are now storing our roles in the user table,
the user column in our grant table can refer to either
a user or a role, depending on what we are storing in the user table,
so we don't need the role column and we can go back to the
previous definition that did not have that column.
With this implementation our foreign key constraints all
work because we are not dealing with any views, and our table structure
is simpler because we have combined users and roles into one table.
Although we are putting roles into the user table, we do need
to remember that this is just a convenient fiction to simplify our
implementation because there are some situations in which we want to
treat users and roles the same.
But we must remember that, although we are storing them in the same table
and in some situations ignoring the difference between them,
if we forget about that difference and start treating them the same
in other situations we can easily start getting absurd behavior from
our system.
(I have a mental image of our legal system as having a people
table, and a law table with a foreign key to the people table.
At some early point, someone wanted some laws that applied to corporations
as well as people, so they said, "I know, let's just add an
is_corporation flag to the people table and put the
corporations in there,
then our foreign keys from the law table will still work
and we won't need to add a bunch more structure to our law schema!"
With the passage of time, law programmers who should have been paying
attention to the is_corporation flag started ignoring it more
and more often, until finally the law programmers were saying,
"Well, those corporations are in the people table, so they must be people."
If you are concerned that this kind of situation might happen to you,
you might not want to put roles into the user table.)
For the remainder of this discussion, we will use this third
alternate implementation approach.
In the above discussions, I have been assuming that the names of users,
actions, objects and roles are also their key values.
This implies that each of those names are unique.
Given that I have discussed a couple of implementations in which users
and roles have been mixed together, you might wonder whether it would
cause problems to add a user whose name is the same as a role.
In the above simple implementation the answer is "yes", and the system
would have to disallow that.
A real system is likely to be a bit more complex, using unique IDs as
primary keys rather than names.
The problem of having unique names thus gets moved from a database
issue to an application-level issue.
The system implementer must decide under what circumstances it is
acceptable to have duplicate names,
and there must be a way to distinguish those duplicates to someone
operating the system.
We have reached a point in the development of our authorization model
that is similar in power to many existing systems.
People who need more flexibility than this model provides might diverge
at this point into custom authorization systems with various forms of
exceptions and extensions that rapidly start adding complexity to
the model.
There are still a number of extensions we can make to our
authorization model that will improves its power while adding only
a small amount to the cognitive load of understanding how it all works.
Let's get back to our model and add some more power to it.
In the same way that we allow specifying a group of users having a role,
we add the ability to specify a group of actions, which we call a task.
The relation between tasks and actions is exactly analogous to the
relation between users and roles.
Each action can be assigned to multiple tasks,
a task can be assigned other tasks,
and an authorization grant can refer either to
an action or to a task.
Analogous with our second alternative implementation above,
in which we added an is_role column to the user table
and put roles into the user table,
for the equivalent addition of tasks we
add an is_task column to the action table,
add an action_task table with columns
action and task both being foreign key references to
the action table,
and add a task_closure view.
create table action(
name varchar(32) primary key,
is_task boolean not null
);
create table action_task(
action varchar(32) not null,
task varchar(32) not null,
constraint FK_actiontask_action foreign key(action)
references action(name),
constraint FK_actiontask_task foreign key(task)
references action(name)
);
create view task_closure as
select action, a3.task as task from action_task as a0
join action_task as a1 on a0.task=a1.action or
(a0.action=a1.action and a0.task=a1.task)
join action_task as a2 on a1.task=a2.action or
(a0.action=a2.action and a0.task=a2.task)
join action_task as a3 on a2.task=a3.action or
(a0.action=a3.action and a0.task=a3.task)
;
We expand our authorization query to look for tasks in the same way as we
expanded it to handle roles, with the same caveats about
hierarchy depth.
-- authorized if count>0
select count(*) from auth_grant where
(user={user} or user in (select role from role_closure where user={user})) and
(action={action} or action in (select task from task_closure where action={action})) and
object={object};
Roles and tasks give us the ability to group users and actions.
We complete the pattern by adding the ability to group objects
into groups that we call domains (not to be confused with internet
domain names).
As with the tasks example above,
we add the is_domain column to the object table,
create the object_domain table to allow defining groups of objects,
create the domain_closure view,
and modify the authorization function to check for either objects
or domains in the same way as we modified it to check for
either actions or tasks.
All of these steps are exactly analogous to what we did when
we added tasks.
There are three dimensions: user, action, and object.
The handling of the three dimensions is completely symmetric
(unless role activation is being used, in which case the
user dimension has that extra wrinkle).
The application passes those three values to the authorization function,
which returns true if that operation is authorized, false if not.
For each dimension, there is a grouping mechanism:
role for user group, task for action group, domain for object group.
The grouping mechanism supports a hierarchy of groups, or more generally
a (directed acyclic) graph of groups (a partial ordering).
To determine if a request should be authorized, take each dimension,
collect the closure of the groups for that dimension,
and look for a grant in which each dimension of the grant matches
any of the items in the closure for that dimension.
The model presented above is easy to understand,
but despite its simplicity it is quite powerful.
Yet it does not suffice for everyone.
Let's see how we can continue to enhance it's power without
significantly increasing its complexity.
In some systems it is desirable to allow some operations only at
specified times.
For example, one might want to allow users to log in to the system
only during their work shift.
We define another dimension, the time dimension,
and we define a time range as a period,
where a period is an interval of time such as 8AM to 5PM, or Sunday,
or 8AM to 5PM on weekdays.
We add the time dimension to our definition of an operation, so
when the application calls the authorization function, it must now
pass the current time as a fourth argument.
The dimensions we have defined previously are all discrete dimensions,
with only one matching value for each definition.
The time dimension is different in that it is a continuous dimension:
there are multiple time values that can match a period.
This makes the authorization function a little more difficult to
write, but it does not add much complexity to the user's conceptual model.
The other dimensions all have groups, so it would not add to the complexity
of the model to add groups of periods.
In fact, the model would be more complex if we did not add
groups of periods, as that would make this dimension different from
all the others in that aspect,
which would be an additional detail that the user
would have to factor into his mental model.
We add a group called schedule.
As with all the other groups, a period can be included in any number
of schedules, and schedules can contain other schedules.
When checking authorization,
we collect all the periods that match the current time
and the closure of all the schedules for those periods,
and we search for grants that include any of those in the period column.
By now the pattern should be pretty clear.
If the system requires other dimensions, they are easy to add
by following the same pattern.
By keeping to the pattern, the complexity of the model that the
user must work with to understand the system is kept low,
even when there is some small difference for the new dimension,
as there was for the time dimension when
compared to the three previously defined dimensions.
When there are small model extensions for a dimension,
as there was when we added the time dimension,
we can leverage that model concept when adding some other dimension.
Location is a system-specific concept.
For some systems it might be a logical location,
such as "console", "secure terminal", or "dial up".
Since these are discrete values, it would suffice to have a
location table, group locations in regions,
and handle it in the same manner as the other discrete dimensions
such as user.
For other systems a location might mean a physical location specified by
one or more continuous values, such as latitude and longitude,
in which case we define an area analogously to a period,
where one area includes a range of locations.
The area might be defined with a center point and radius, it might be defined
with a bounding box, it might be defined as a polygon, using splines,
or in some other even more complex way.
As with periods, the complexity of the definition of an area has
an effect on the difficulty of implementing the authorization function
that has to determine whether a location is or is not in an area,
but has little effect on the complexity of the user's mental model
of the authorization.
For the user, it is sufficient to know that
a given location will be either contained in or not contained in an area,
and that grants are based on areas.
Our group for an area is a region, and it groups together
areas and other regions in the same way as the groups in the other dimensions.
The approach described above is essentially a "whitelist" approach,
which is the standard approach to authorization.
If an operation is listed in the grant table then it is allowed;
any operation which is not listed is not allowed.
It is also possible to use a "blacklist" approach:
rather than allowing what is listed and denying everything else,
we can deny what is listed and allow everything else.
In this case we would create a denial table that is exactly
like the grant table except that it contains operations to
be denied rather than operations to be allowed.
The authorization function would do the same search as before,
except that it would deny the operation if any matching records
were found, and allow the operation otherwise.
Using a blacklist approach to authorization as just described
is generally not recommended
(in fact the NIST RBAC standard specifically recommends against
"Negative permissions", although it does not outright disallow them).
Since the default action is to
allow an operation, if a new operation is added to the system
and through oversight the appropriate denials are not added, then
there is no protection for the new operations.
We can combine the original grant approach and the
denial approach described just above to give us the ability
to have both a whitelist and a blacklist.
We start with our original grant table approach,
following the recommended position that the default is to
deny any operation unless it is explicitly granted;
on top of that, we add the denial table as exceptions to the grants.
Our authorization function first looks in the denial table;
if a matching record is found, then the request is denied.
If no matching record is found, then the function looks in
the grant table; if a matching record is found, then
the request is granted; otherwise it is denied.
This allows the admin to think in terms of exceptions:
grant privileges to all of X, except for Y.
In some situations this allows expressing the intended grants
more simply than if one is restricted to just additive grants.
We could also flip the grant and denial tables around,
first looking in the grant table for a match, then looking
in the denial table for a match, then granting if nothing
is found.
As discussed in the previous section, this is not recommended,
but understanding that it is possible is conceptually useful,
and leads us to our last enhancement.
The structure of the grant and denial tables are
identical, and their contents are checked in the same way, with the
only difference being an inversion of the interpretation of the results
in one case as compared to the other.
We can easily combine both of these tables into a single auth
table that includes an additional allow column that is
true for all records from the grant table and false for
all the records from the denial table.
We can also add a priority column that we use to determine which
records we should attend to first.
create table auth(
id integer auto_increment,
allow boolean not null default true,
priority integer not null default 0, -- higher values take precedence
user varchar(32) not null,
action varchar(32) not null,
object varchar(32) not null,
period varchar(32) not null,
area varchar(32) not null,
constraint FK_auth_user foreign key(user)
references user(name),
constraint FK_auth_action foreign key(action)
references action(name),
constraint FK_auth_object foreign key(object)
references object(name),
constraint FK_auth_period foreign key(period)
references period(name),
constraint FK_auth_area foreign key(area)
references area(name)
);
If we define the priority value such that higher values are more
important than lower values, then we can get the same behavior as
described in the first part of the previous section
by setting the priority on all the denial records to 2 and
setting the priority on all the grant records to 1.
Our authorization function then looks in the auth table
for the matching record with the highest priority value
and looks at the allow value for that record.
If we wanted to get the (non-recommended) behavior as described at
the end of the previous section, we could do that by setting the
priority of all the grant records to 2 and setting the
priority of all the denial records to 1,
plus making the default behavior (when no matching rows are found)
to allow the operation.
Given this structure, we can of course put in records with any priority
value.
This allows building up a series of toggling exceptions, much as the way
leap years in the Gregorian calendar are
defined
(each year has 365 days, except every 4th year is a leap year with 366 days,
except every 100 years is not a leap year, except every 400 years is
a leap year).
Since we can stack up alternating grant and denial
records, the only distinction between the "whitelist" and "blacklist"
approaches discussed earlier is the question of what the default is when no
matching records are found in the auth table
(the default for whitelisting is deny, the default for
blacklisting is grant).
Given that using a default of allow is not recommended,
we define the system to use a default of deny,
but we provide a way that the system can effectively be set up with
a default of allow if desired.
To simulate a default of allow, the admin can create a group for each
of the dimensions in our authorization model (user, action, etc)
that includes all elements of that dimension.
Thus there would be an AllUsers role, an AllActions task,
an AllObjects domain, etc.
The admin then creates a rule that includes all of these groups
with allow set to true and priority set to zero.
Since the rule has been defined to include all elements of every dimension,
it will always match every operation,
so there will never be a case where there are no matches and the
system default of deny is used.
Assuming all other priority values are greater than zero,
this rule will be the lowest priority,
so it will only have an effect if there are no other matches,
and thus it acts as the default.
As described above, there is one more potential ambiguity to resolve:
what happens if there are two rules with the same priority
but opposite allow values?
(Two rules with the same priority and the same allow
are not a problem, as they both give the same result.)
We resolve this ambiguity by defining the denial records to
take precedence over the grant records when they have
the same priority value.
This definition reduces nicely to the desired behavior for the
simplest denial+grant case when all records have the same priority.
Our authorization function thus looks for all matching records in the
auth table, sorts first by priority then by allow,
picks the first one, and uses its allow value to determine
whether to allow the operation.
If no matching records are found, the operation is not allowed.
Ignoring for now the more complicated portions of the WHERE clause
for selecting time and location,
here is our SQL statement for determining if an operation is authorized:
-- The single selected value is true if authorized; if false or no records, not authorized
select allow from auth_grant where
(user={user} or user in (select role from role_closure where user={user})) and
(action={action} or action in (select task from task_closure where action={action})) and
(object={object} or object in (select domain from domain_closure where object={object}))
order by priority desc, allow asc
limit 1
Adding prioritization like this adds a new concept to the authorization
model, but provides a good amount of additional power relative
to the additional mental load to understand the model.
However, creating well-structured rules using prioritization
is trickier that it seems at first glance.
It has the same essential problem as for the blacklist approach
described above:
mistakes in setting up
the conceptual layers of the different levels of prioritization
can result in unexpected security holes.
If you can figure out how to set up your authorizations using grants
only, without denials, you should do that.
But if the grant-only model is not sufficient,
then adding prioritization as described in this section is a reasonable
way to take the model to the next level of power -
just remember that you have to be more careful in how you
set up your rules.
With the addition of prioritization in the previous section,
our authorization model is complete. Let's review the complete model.
There are two kinds of dimensions: discrete and continuous.
There are five dimensions: user, action, object, time and location.
User, action and object are discrete;
time is continuous;
location can be either discrete or continuous,
depending on how the system defines it.
Additional dimensions can be added if necessary, following
the pattern of the existing dimensions.
The handling of every discrete dimension is completely symmetrical
with every other discrete dimension
(unless session-based role activation is included, in which
case the user dimension is a little different);
the handling of each continuous dimension is close to completely
symmetrical with the other continuous dimensions;
and there is a high level of symmetry between the discrete and
the continuous dimensions.
The application passes a value for each dimension
to the authorization function.
This collection of dimension values is the operation for which
the application is requesting authorization.
The authorization function returns true if that operation is authorized,
false if not.
For each continuous dimensions, there is a range defined as the basic
match:
period for time, area for location.
For each dimension, there is a grouping mechanism:
role for user group, task for action group, domain for object group,
schedule for period group, region for area or location group.
The grouping mechanism supports a hierarchy of groups, or more generally
a (directed acyclic) graph of groups.
There is a set of rules that is used to determine whether an operation
is authorized.
Each rule includes a set of comparison values, one for each dimension,
a priority,
and an allow flag that tells whether that rule specifies
that authorization for a matching operation should be granted or denied.
To determine if a request is authorized,
take the value for each dimension in the request,
collect the closure of the groups for that value,
and collect the records in which each dimension of the grant matches
any of the items in the closure for that dimension.
Pick the record with the highest priority, giving preference to
deny records over grant records, and use the allow
value of that record to determine whether to authorize or deny
the operation.
If no matching records are found, the operation is denied.
This conceptual model is no longer trivial, but the above rules are
still relatively concise and easy to understand.
The model is general enough and powerful enough that it should be
suitable for a wide variety of applications.
In our model the application passes in a set of values to the authorization
function, which uses its abstractions (in the form of groups) and rules
(in the form of prioritization) to determine whether or not to grant
permission for an operation.
If we need more power,
the application can pass in additional information, whether it is
additional attribute information about the user, the environment, or
other aspects of the operation,
and the authorization system can apply even more complex rules.
This is the approach used by
Attribute-Based Access Control,
with a rules engine used in place of the mechanisms described here.
In both my personal and my work projects I prefer to use
git rebase
to keep my commit histories simple and readable.
To make this work in a team setting, we never work on the master
branch, instead always working on a feature branch in our local repositories.
Our process flow looks something like this:
$ git branch feature #create the working branch
$ git checkout feature #do all development work on that branch
#Edit files, etc.
$ git commit -m "Implement Feature"
#Repeat the above as desired during development.
#When ready to merge to master, do the following:
$ git checkout master
$ git pull #update master from shared repository
$ git checkout feature
$ git rebase master #optionally with -i if squashing is desired
$ git checkout master
$ git merge feature
$ git push origin master
$ git branch -d feature
Because we never use our local master branch for development, the
git pull on master is always a
fast-forward merge.
Likewise, because we have just rebased the feature branch against the master
right before we merge that feature branch back into master, that merge is also
always a fast-forward merge.
Looking at it another way, we don't have any merge conflicts when
updating or merging master because we resolve all of the merge
conflicts when we rebase the feature branch against the latest master.
The Problem
At work, we have a large codebase and a handful of active developers who
typically merge feature branches to the master using the above workflow
multiple times each day. Sometimes somebody has a feature branch that
takes a long time to finish, so that between the time that branch was
started and the time it is ready to go into master, there may
have been 40 or 50 other commits made to master.
In general in this situation we will occasionally rebase our local
feature branch against the latest master a few times during feature
development, but inevitably there are occasions when a large rebase
across many commits ends up being done.
Even if there are many commits on the master branch,
if none of those commits touched any of the same code as the commits
on the feature branch, then there should be no merge conflicts when
rebasing the feature branch against the updated main branch.
However, in my experience this has not always been the case.
Sometimes git rebase reports merge conflicts when I think there
should not be any.
Since I don't generally know exactly what code the other team members have
edited, I can't immediately tell if the merge conflicts make sense.
The normal advice for how to handle merge conflicts is to edit the named
file, look for the conflict markers, inspect the conflicting code fragments,
determine what to keep, edit out what is not being kept along with the
conflict markers, git add the repaired file, and
git rebase --continue to let it tell you about the next merge conflict.
That's a lot of work, and it might all be completely unnecessary.
The Solution
It seems that git sometimes just gets confused when doing a rebase across
a large number of commits.
Sometimes if you rebase in smaller steps, git will happily rebase each
smaller step with no merge conflicts, until you have stepped all the way
up to the latest master, at which point your rebase is done.
You could rebase against every single commit and work your way up to master,
but that, too, is a lot of work.
Here's what I do when the initial rebase of the feature branch against
the latest master tells me there are merge conflicts.
When the initial git rebase reports a merge conflict,
I immediately do git rebase --abort to undo that rebase attempt.
Using gitk --all to view the commit tree, which lets me see
the master branch and the commit at which my feature branch branches
off the master branch, I select a commit on the master branch
about half way between those two commits.
I copy the commit ID and paste it into a rebase command that looks
something like this:
$ git rebase 8bc85584989e4435c2d98b13447bcab37648ba7f
If this rebase reports no merge conflicts, then I try rebasing
against master and repeat the process.
If there are merge conflicts, then I abort the rebase and pick another
commit half way again to the branch point.
I repeat this until either the rebase succeeds or I am trying to
rebase across a single commit.
At that point, if there are still merge conflicts, they are real
and I address them in the normal way.
Since the conflict is only across a single commit, it is easier to
see the cause of the conflict and to resolve it.
After resolving the conflict across that one commit,
I go back to the first step and try rebasing against master again,
repeating the process.
I have followed this process a number of times.
I think that a majority of these times I binary-divide my commits
a few times and end up piecemeal stepping through the commits
until I have rebased against master without ever having to resolve
any conflicts.
The other times I typically have to resolve one or two small conflicts,
after which I can rebase against master.
The next time you do a rebase across more than one commit and git
tells you there are merge conflicts, try this approach.
You might save yourself a lot of work.
Unless otherwise specified in individual blog entries, all source code in this blog is Copyright by Jim McBeath, as of the posting date, under the GNU Lesser General Public License (LGPL), Version 3.
