In science, we make abstractions that are simplified models of reality,
then we try to describe them with equations that let us make accurate
predictions given the conditions assumed by the model.
In this post I attempt to do that for software projects.
In physics, the behavior of an idealized gas is described by the
ideal gas law:
PV=nRT, where P is pressure, V is volume, n is the quantity
of gas, R is a constant,
and T is the absolute
temperature. While real gases don't follow this law exactly, it can be
used to make pretty good predictions. It can help you understand how
steam engines, refrigerators, and hot air balloons work.
A key insight that follows from this equation is that you can't hold
three of the four parameters fixed and change just one parameter. If you
have a fixed amount of gas at a given pressure, volume, and temperature,
and you increase the temperature, then either the pressure goes up,
the volume goes up, or both. If, with the same starting conditions,
you decrease the volume, then either the pressure must go up, or the
temperature must go down, or both. You can keep any two parameters fixed
and change the other two in fixed relationships, but you simply can't
hold three of the parameters fixed and change just one. If you try to
do that, you will invariably fail: one or more of the other parameters
will, perforce, also change.
We can use a similar equation to convey the relationships among the
parameters of software development. Instead of PV=nRT, we have:
FQ=nST
where F is functionality, Q is quality, n is development
resources, S is a constant, and T is the amount of time to complete
development. As with the ideal gas law, this equation does not precisely
apply to real software projects, but it can be used to make predictions
and gain insights. In particular, we can see in this formulation the
same basic insight as with the ideal gas law: it is not possible to hold
all but one of the parameters fixed and change only one parameter. If
you try to do so, one or more of the other parameters will, perforce,
also change.
Functionality represents what our software can do.
There are defined ways
to measure the functional size
of software, such as COSMIC function points,
but we would like something simpler that still allows us to understand the relationships
between the parameters of the equation.
For our purposes, a reasonable proxy for functionality is lines of code (LoC).
We are not claiming that lines of code is a good general metric for measuring productivity.
Some people write denser code than others, so can implement more
functionality in the same number of lines of code.
Some research has concluded that people can write the same number of lines of code
per day independent of language, but a higher-level language can express more with the
same number of lines of code, so could be used to implement more functionality
in the same number of lines of code as compared to a lower-level language.
Some projects have a more difficult environment than others, so developers
produce fewer lines of code per day in that environment.
However, we are using LoC slightly
differently in this case. We are not using it to compare productivity or functionality
between projects and teams,
but only within the team and project for which we are measuring functionality.
We assume that all of the factors mentioned above that affect the LoC metric
are constant within the project and time span of interest, so that twice as many
lines of code will provide twice as much functionality.
For quality, we could use a sophisticated quality model
such as ISO/IEC 25010,
but for this exercise we will use the simpler
Defect Management
approach.
Intuitively, it makes sense that higher quality software will have
fewer bugs (also called defects). We also expect a larger project to have more total bugs
than a smaller project. Roughly speaking, then, we can think of the
number of bugs per line of code as being a proxy for the level of
quality of a software project. We can call this the bug density (or defect density).
We want our parameter to be larger for higher quality software,
so we use the reciprocal of the bug density. The reciprocal of density
for materials is called
specific volume,
so we will call this measure bug specific volume (or defect specific volume), and use
that as our measure of quality.
Our units for quality are thus LoC/bug.
We recognize that there are some practical problems with this measure.
Firstly, bugs come in different sizes. For our purpose
we will assume some kind of "normalized" bug units, and assign
more serious bugs more than one bug unit.
Secondly, we don't know how many bugs are in a piece of software
until well after it is delivered. We assume those bugs exist and
will be revealed over time, at a rate which depends on factors such
as how much use the software gets, so although we don't know the
number in advance, we can still use this concept in our abstraction
to understand the relation of quality to the other parameters.
Resources, as in Human Resources, refers to the people we have available to work
on the project.
To a first approximation, n is the number of people developing the project.
Many studies have shown that different people have
different levels of productivity.
For this idealization we assume that there is a baseline developer and that
we know what the productivity multiplier is for each of our developers
as compared to that baseline developer,
despite that in practice
this might be difficult,
and the factor could be different depending on circumstances.
We then define n as the number of baseline developers on the project.
If we have a developer who we believe is three times as productive as our baseline,
that would increase n by three.
Our units for n are thus baseline developers, but
for simplicity, we will sometimes just refer to the units for n as people.
Our idealized
equation assumes that we could do our project in half the time if we had
twice the resources. We recognize that we are blatantly ignoring the problems of
the mythical man-month.
Time refers to how much time it will take to complete the project.
This is the most straightforward dimension to measure, and because of that it is
often the dimension
that gets the most attention during project planning.
We choose to use days as our units, as that is a commonly used unit
for other aspects of software development.
The units we have selected for the four
parameters define the units of the constant S.
F(LoC)Q(LoC/bug)=n(person)S(??)T(days)
Therefore the
units for S must be (LoC^2)/(bug*person*days).
We can also write this as (LoC/bug)*(LoC/person/day).
LoC/bug is a bug specific volume (our quality measure), and LoC/person/day is a
development velocity
for our baseline developer,
so S is the product of a
bug specific volume and a
per-person development velocity.
We can think of S as the "quality velocity" for one baseline developer.
A higher value of S means higher
productivity: more functionality or quality from a given amount of time, per developer.
So what value should we use for S?
Some people (such as Brooks in The Mythical Man-Month) say a programmer
can write about 10 lines of production code per day. Other sources use
different numbers, but as a baseline we will go with Brooks value of 10 LoC/person/day.
For bug density,
various studies
have come up with a number from 3 to 50 defects per 1000 LoC.
As a starting point, I will select 10 bugs per 1000 LoC,
or a bug specific volume of 100.
Combining these two values gives 10 * 100 = 1000 as the value of S.
This means our baseline developer could, for example, write 10 lines of code
with 10 bugs per 1000 LoC in one day, or 20 lines of code with
20 bugs per 1000 LoC.
In reality, different collections of people, different development environments,
and different project attributes will all lead to different values of S.
Organization should always be looking for ways to increase the value of S
for their projects, but for this analysis I am assuming that they have
already done this in all the easy ways, and the remaining opportunities
to increase S require larger investments and time to have an effect on the project.
Thus when analyzing our equation to see what predictions it makes for
a particular project, we will assume S is constant.
Our Ideal Software Law is similarly assembled from simpler guidelines.
We don't have previously stated laws, so we rely on our intuition to guide us.
All other things being equal, functionality is proportional to resources: F ∝ n
All other things being equal, functionality is proportional to time: F ∝ T
All other things being equal, quality will he higher with more resources
All other things being equal, quality will he higher with more time
Because quality is hard to define and measure, we don't actually know how close to
being proportional to the other variables it is.
For simplicity, we assume that it is proportional to both resources and time,
the same as functionality: Q ∝ n and Q ∝ T.
These four rules, when assembled, give us the form of the equation for
the Ideal Software Law shown above.
Solving for d, we get d = (10,000*200)/(10*1000) = 200 days. A project team, given the assumptions above
(although perhaps not so explicitly), would perhaps deliver this estimate to
management when asked how long the project will take.
Now let's play with the parameters and see what happens.
The typical scenario is that management comes back to the team and says
"That estimate is too long. We need to deliver sooner. Make it happen faster."
What options does the team have?
Looking at the Ideal Software Law equation, if we want to make T smaller, we have four options:
Make F smaller (less functionality)
Make Q smaller (less quality)
Make n larger (more developers)
Make S larger (higher velocity)
Clearly making S larger would be good, but, as mentioned above, when considering the schedule for
a single project, this is unlikely to be a short-term option. That leaves us with three other
parameters that can be changed.
We could make n larger by adding more developers to the team. This can be effective if there are
people available, but practically speaking is difficult because of limited budgets, the difficulty
of finding appropriate developers, and the time-cost of bringing a new team member up to speed.
All of those factors make this choice possible but unlikely.
Now we are down to two parameters: functionality and quality. The developer team will typically
propose to make F smaller, also called a reduction in scope, by removing features from the project.
If this is acceptable to management, then the reduced value of T can be balanced by the reduced
value of F.
In many cases, however, management insists on not cutting any features. Now we are left with only
one parameter: quality. Because this is the hardest parameter to measure, it is also the one that
most often is ignored. In this situation, when T is made smaller and F, n, and S are unchanged,
Q must, perforce, be made smaller by the same fraction as T was reduced.
The choice to reduce quality is sometimes made consciously, and could come with a commitment to go back
later and improve quality. This is often referred to as taking on
technical debt,
which is expected to
be paid back by improving the code later. The word "debt" is used here in intentional analogy to financial debt:
there is a carrying cost to debt in the form of interest, making the total cost continue to go up the
longer it remains unpaid. In software, this manifests as more time spent fixing bugs after product release,
until such time as the debt is repaid by cleaning up the code to bring its quality back up.
If, however, a decision is made to reduce project time without changing functionality or resources, without
consciously recognizing that there will be a reduction in quality, this is effectively like borrowing
money without realizing it or having a plan to pay it back. The interest payments will still be there,
in the form of more time spent fixing bugs and more time required to add new features,
and that will negatively impact the team's schedule on future projects.
All abstractions will eventually break down when the parameters go outside the valid range of the abstraction.
Newton's law of gravity elegantly describes the paths of the planets, but starts to break
down in strong gravitational fields
The constant-time swing of a pendulum
of a given length starts to change
when the pendulum swings too far from its center position
The Ideal Gas Law
becomes less accurate
at lower temperatures, higher pressures, and with larger gas molecules
Understanding the limitations of an abstraction allows us to improve our predictions.
In the Parameters section above, I discuss some of the assumptions
about each parameter. When we recognize that an assumption does not hold, we can bend the
results of our formula to try to compensate.
For example, our formula tells us we can get the same functionality in half the time
by doubling our resources. But we know that it takes time to bring a new developer up to speed
on a project, so we won't actually be able to cut our time in half. By estimating how much
reality deviates from our assumption, we can improve the accuracy of the predictions made
by the formula despite
the fact that the assumptions behind the formula are not entirely accurate.
By abstracting the parameters of software development and creating an equation, we can make
practical predictions about those parameters.
We can make such predictions even when the assumptions behind our formula are not completely true.
One of the most important predictions is this:
If you insist on reducing the time available to complete a software project, and you don't increase
the number of people on the project or cut some features, the quality of the delivered sofware will
decrease proportionally to the reduction in time.
My bathroom is pretty far from the water heater. It took over
a minute of running the hot water for it to actually get hot. That's
a lot of water wasted every time I waited for hot water.
I wanted hot water faster.
Last year, as part of a bathroom remodel, I had a hot water recirculating
system installed. This consisted of a return pipe from the bathroom
and a recirculating pump at the water heater to
pull water from the return pipe, thus bringing hot water to the bathroom
without having to run water down the drain waiting for it to warm up.
Once the system was installed, I learned that the pump is not supposed to
run all the time. In addition,
the pump, while not terribly noisy, produced enough noise to be
annoying, especially in the parts of the house adjacent to the garage
where the water heater and pump were located. So I didn't want to run
it all the time for that reason.
The installer gave me a timer. I set it up to run in the morning and the
evening. My schedule wasn't precise
enough to run the timer for just a short amount of time, so I had it
set up to run for about an hour.
This didn't work very well:
besides the noise issue mentioned above,
the temperature of the water dropped a noticeable amount during this period.
I needed another solution.
My solution was to set up a home automation system with some outlets and
some battery-powered pushbuttons and program it so that when one of the
pushbuttons was pressed, it would turn on the outlet for a couple of minutes
to run the recirculating pump. This has worked well.
Years ago I used a bunch of
X10
switches and outlets. I even
installed a blocker to isolate the X10 signals in my house from the incoming
power line and a coupler to ensure the X10 signals from one 120V leg made it
to devices on the other 120V leg.
I eventually stopped using those devices and had not installed any other
home automation until now.
After looking at what was available, I decided to use the following technologies
for my new home automation system:
Home Assistant as the controller
I chose this for two reasons:
I don't want my system to depend on the cloud or to be sending data
out to anyone. Home Assistant allows me to do everything myself and
be isolated from the internet. My automation won't stop working when
my internet connection or someone else's computers or software go down.
I like to tinker. Home Assistant is highly customizable - as long as
you are willing to fiddle with it.
Zigbee 3.0 devices
I looked at Zigbee and Z-wave and decided Zigbee looked like the better
choice for number of compatible available devices.
I specifically did not want to use wifi devices.
Having made those two choices, the next choice was where to run Home Assistant and
how to connect the Zigbee devices to it.
I figured I would use a USB Zigbee coordinator.
For the Home Assistant host, I considered running it on my desktop (which is always on),
on my Synology NAS, or on a bespoke device such as a Raspberry Pi. I learned that
Synology announced they would be
removing support for external USB devices
other than disks,
so I eliminated that choice. I starting looking into using a Raspberry Pi and read
multiple comments about high failure rates of the SD cards. Someone suggested attaching
a USB SSD, which seemed like a good idea, but that would require more research and figuring
out how to mount everything. About this time I discovered
HA Blue,
a nice little device based on the Odroid-N2 with 128GB of on-board eMMC,
4 USB ports, ethernet, and HDMI, all in a good-looking extruded aluminum case,
and pre-loaded with Home Assistant.
It's a little more expensive than some other options, but for me the
added convenience of a pre-installed system and the nice case were
worth the price.
Note: Home Assistant Blue has been discontinued and is being superseded by
Home Assistant Yellow,
which has a built-in Zigbee radio and more expansion slots.
Even after deciding on Zigbee, there were a few different available ways to set up
the communication between the Zigbee devices and
Home Assistant. After doing some reading, I settled on using zigbee2mqtt.
It seems like one of the newer solutions, and one where I would have less
trouble integrating a wider variety of devices.
For my initial foray into home automation and based on my decisions above, I bought the following:
HA Blue
bespoke Home Assistant controller pre-loaded with Home Assistant
SmartLight Zigbee CC2652P Coordinator v4 USB Adapter preflashed with
CC2652P_E72_20210319 firmware to support zigbee2mqtt
Some Sonoff S31 Lite Zigbee outlet plugs
Sonoff SNZB-01 Zigbee switch
Some Linkind Zigbee switches and outlets
I used the Blakadder compatibility list
to find devices that were compatible with zigbee2mqtt, then looked at which ones I
could get and what they cost. The outlets and switches I bought were on the less
expensive end of the range, costing less than $10 each, although the price
has since gone up.
Setting up the HA Blue system was straightforward:
Plug it in to power and ethernet
Look in my DHCP log to see what IP address it was assigned
Open my web browser to port 8123 at that IP address
Wait for it to run through its first-boot setup (about 10 minutes)
Create an account for myself
I set up the Zigbee USB adapter (following a
YouTUBE video
(but beware, there have been some changes since that video was made):
Plug in the Zigbee USB adapter
Log into HA Blue using my account
Enable Advanced mode in my profile
Create user "mqtt" to handle mqtt stuff
From the Add-on store, install Mosquito Broker
Configure Mosquito Broker by adding the mqtt user, and start it
Once the Zigbee adapter was in place, I set up zigbee2mqtt:
In the Add-on store screen, from the "..." menu, select Repository
and add the URL for the
zigbee2mqtt repository,
then find the Zigbee2mqtt Hass.io Add-on near the bottom and select it
Find the USB port the Zigbee adapter is connected to: in
Supervisor, System, Host box, three-dot menu, Hardware is a list of
devices in /dev; by plugging and unplugging the Zigbee adapter
I could see that it shows up as device 1-1.2 with path /dev/bus/usb/001/004
and as /dev/ttyUSB0. Or you can just assume /dev/ttyUSB0.
Edit the configuration on the zigbee2mqtt module and change the default pot
from /dev/ttyACM0 to /dev/ttyUSB0, and change the username to mqtt
Start the module
I also set up ssh to simplify future customizations:
Install the Terminal & SSH Add-on and start it
Open the Terminal & SSH Web UI, which is a web terminal, usable as an alternative to ssh
In the Terminal & SSH Config network page, specify port 22
In the Terminal & SSH Config page, add my public key
to the authorized_keys array in single quotes
Save, and restart the module
ssh to the HA Blue as root
At this point I rebooted the HA Blue and looked in the Log for each module
to make sure it was working properly.
The above description of setting up zigbee2mqtt is condensed, as I actually
had a bit of trouble setting it up, including using an old zigbee2mqtt repository
that I later replaced with the newer repository URL given above.
With Zigbee configured on my HA system, I was ready to add my Zigbee switches and outlets.
In order to add a new Zigbee device to the network, the zigbee2mqtt module must be configured to
permit devices to join. Initially I was doing this by directly editing the configuration
of the zigbee2mqtt module and changing the value of the permit-join attribute to true.
Once the new device had been added, I then edited the configuration again and changed
permit-join back to false. Later, I discovered I could just use the Web UI for the
zigbee2mqtt module and click on the "Permit join" button, which enables permit-join
for 255 seconds with a count-down timer, after which it automatically turns it off.
With the HA Blue system beside me, I enabled permit-join. The LED in the Zigbee adapter started
flashing green to indicate that it was in permit-join mode.
The first device I attached was a SONOFF SNZB-01 button:
Pry off the back of the button, remove the paper battery insulation sheet,
replace the battery and back
Using a paper clip, press and hold the reset button for 5 seconds, until the red light flashes
After a couple more seconds, the tile for Mosquitto Broker shows "1 device and 3 entities"
Click on "1 device" to open a list of devices
Click on the device to open its details page
Click on the pencil icon by the hex name at the top of the page and rename the device
and the entity IDs
Press the button, it briefly shows "single" by the "action" line
Double-click, it briefly shows "double" by the "action" line
Yay, my first Zigbee device is working!
I added a few more devices with basically the same process. Sometimes they would
join just by enabling permit-join, but sometimes I also had to reset the device.
I had some Sonoff devices and some Linkind devices, and I got them all working,
although I did have one unexpected hiccup.
I had purchased a few Linkind outlets. The first one successfully joined my
network, but the second one did not. After a few tries, I finally looked at the
zigbee2mqtt log and saw that there were error messages saying the unit was
not supported. (Lesson: if a new device doesn't join right away, look in the
log file for errors!) Although the two outlets were sold under the same product name
and looked the same, it turned out they had different model numbers:
the unit that worked was ZS190000118 and the unit that failed to join was
ZS190000108.
In order to add support for this slightly different flavor of Linkind outlet,
I found and followed some instructions to
support a new device.
ssh into my HA Blue as root
cd to config/zigbee2mqtt
edit the new file ZS190000118.js
In web browser, open https://github.com/Koenkk/zigbee-herdsman-converters/blob/master/devices/linkind.js,
look for Linkind ZS190000118, and copy that stanza into my yaml file
(this assumed the description was compatible, which turned out to be true)
Change zigbeeModel to ['ZB_ONOFFPlug_D0008'] (from the zigbee2mqtt log)
Change model to 'ZS190000108' (from the zigbee2mqtt log)
Add the rest of the boilerplate as specified in step 2 of the instructions
Write out the new file
Update the zigbee2mqtt config to add the new device:
set advanced:log_level: debug (was warn);
set external_converters: - ZS190000108.js
Once the hardware was all in place and working, the next step was to set up
the programming. It looks like there are multiple ways this can be done, and
as a programmer I figured it wouldn't be too hard to write some automation
code, but then I discovered Node-RED, a graphical editor plugin.
I installed Node-RED from the Community section of the AddOns menu.
I had a bit of trouble with the certificate stuff, but eventually got
that working. I then created a flow such that when I pressed one of
my buttons, it would turn on the pump for two minutes.
I spent too much time trying to figure out how to do the whole thing
using standard components, but eventually decided the standard components
were not quite up to the task. I ended up using a few function components,
in which I wrote a bit of Javascript code.
My buttons are connected to the input of the Add Time function component,
which adds time to a counter each time a button is pressed, with a
max value. The buttons are also wired to an on-outlet component
that turns on the recirculating pump.
Here is the Add Time code:
// On Start
flow.set("max_count", 120); // 2 minutes
flow.set("button_increment", 80); // 1 minute and 20 seconds
// On Message
max_count = flow.get("max_count");
button_increment = flow.get("button_increment");
c = flow.get("counter")
if (c < 0) {
c = 0;
}
c = c + button_increment;
if (c > max_count) {
c = max_count;
}
node.status({fill:"blue",shape:"dot",text:"count:"+c});
flow.set("counter", c);
return msg;
Once time has been added to the timer, there is another function
that counts down to zero, the Count Down function.
The input of the Count Down function is connected to a Ticker
component that ticks once per second.
The output of the Count Down function is connected to an off-outlet
component that turns off the recirculating pump.
Here is the Count Down code:
// On Start
flow.set("counter", 0)
// On Message
c = flow.get("counter")
c = c - 1
flow.set("counter", c)
if (c > 0) {
node.status({fill:"green",shape:"dot",text:"count:"+c});
return {payload:{counter:c}};
} else if (c == 0) {
node.status({fill:"yellow",shape:"dot",text:"stop"});
return {payload:"stop"};
} else {
node.status({fill:"red",shape:"dot",text:"stopped"});
return {payload:"stopped"};
}
This worked well, but I wanted some kind of feedback so I knew when
the pump was on. To get that, I added another smart outlet, into which
I plugged a
guide light.
I then added a function component that monitored the state of the pump switch
with a state-changed component, such that when the pump outlet turned on or off,
the function would turn on or off the outlet with the guide light.
The function also set the node status within Home Assistant so I could see
on the Node-RED schematic when it was on or off.
Here is the Outlet State code:
// On Start
flow.set("counter", 0)
// On Message
state = msg.payload;
if (state == "on") {
node.status({fill:"green",shape:"dot",text:"on"});
} else if (state == "off") {
node.status({fill:"red",shape:"dot",text:"off"});
}
return msg
After getting this all set up, I spent some time testing with
different pump-on times and tweaked the values to be just long
enough to get the initial hot water to the bathroom sinks.
I'm pretty happy with how it is working now.
Go does not support inheritance, but sometimes using embedded structs can look
a little like inheritance. I explore that feature to see how it differs.
In lieu of inheritance, the Go language encourages composition
by allowing one struct to be embedded in another struct in a way that allows
calling methods defined on the embedded struct as if they are defined on the
containing struct.
Note: In this post I occasionally use object-oriented terminology such as base class,
subclass, and override. Please remember that Go does not support these concepts; I am
using those terms here to show how thinking that way with Go can lead to problems.
For the examples that follow, I assume we are building a graphical editor that
allows manipulating visual objects on the screen. We want to be able to draw
those objects, and we want to be able to transform them with operations such
as rotate, so we define an interface with those methods:
Note: For convenience, the final collected code used in this post is available
on play.golang.org.
type shape interface {
draw()
rotate(radians float64)
// translate and scale omitted for simplicity
}
We write a function that will draw all our shapes:
func drawShapes(shapes []shape) {
for _, s := range shapes {
s.draw()
}
}
When we run this program, it produces the expected output:
draw polygon with sides=3
draw from (1.000, 0.000) to (-0.500, 0.866)
draw from (-0.500, 0.866) to (-0.500, -0.866)
draw from (-0.500, -0.866) to (1.000, -0.000)
draw polygon with sides=4
draw from (1.000, 0.000) to (0.000, 1.000)
draw from (0.000, 1.000) to (-1.000, 0.000)
draw from (-1.000, 0.000) to (-0.000, -1.000)
draw from (-0.000, -1.000) to (1.000, -0.000)
Note that we have not defined any methods on the
triangle and square types,
yet the compiler accepts them as implementing shape, as seen by the fact that
we can store them in a slice of shape and we can invoke draw on them.
Because we embedded polygon in triangle and square, without giving them field
names, Go has promoted all of the methods in polygon into the namespaces of
triangle and square, allowing draw to be called directly on an
instance of type triangle or square.
So far, relying on an object-oriented mental model has not caused us problems.
Let's keep going and see when it does.
Let's add a method to our interface and "base class" that invokes the method that we
are overriding, and a new test function to call it.
This is sometimes referred to as a downcall, in that a superclass calls into the
overriding method of a subclass that is below it in the class hierarchy.
type shape interface {
draw()
rotate(radians float64)
// translate and scale omitted for simplicity
typeName() string
nameAndSides() string
}
func (p *polygon) nameAndSides() string {
return fmt.Sprintf("%s (%d)", p.typeName(), p.sides)
}
func printShapeNamesAndSides(shapes []shape) {
for _, s := range shapes {
fmt.Println(s.nameAndSides())
}
}
func testShapeNamesAndSides() {
printShapeNamesAndSides(createTestShapes())
}
func main() { testShapeNamesAndSides() }
This outputs:
polygon (3)
polygon (4)
Well, that doesn't look right.
We wanted it to print triangle and square instead of polygon both times.
Thinking of this as inheritance has led us astray.
So, what happened here?
Why did printShapeNames work, but printShapeNamesAndSides did not?
Let's dig into that.
The return value of createShapes is []shape, which is a slice of objects that implement
the shape interface. Since the triangle and square types implement that interface, we can store
instances of those types
in that slice. But how is it that those types implement that interface when we didn't write those
methods for those types?
The answer is method promotion.
When we embed one type inside another without giving the internal type a field name,
Go automatically promotes all unambiguous names from the embedded type to the containing type.
Effectively, for each method in the embedded type whose name does not conflict with a method
in the containing type or in any other embedded type within that container,
Go creates a method on the containing type that turns around and calls that method on
the embedded type. For example, when we embed polygon in triangle
the compiler effectively creates this code:
If the embedded type satisfies an interface, and there are no ambiguous
method names, this promotion of all the methods of the embedded type
makes the containing type also satisfy that interface.
Let's explore this method promotion behavior.
We create another struct type called thing that
has a typeName method,
embed it along with our previously defined polygon,
which also has a typeName method, in a new type polygonThing,
then try to assign an instance of that to a variable of type shape.
type thing struct{}
func (t *thing) typeName() string { return "thing" }
type polygonThing struct {
polygon
thing
}
func testPolygonThing() {
p := &polygonThing{}
p.draw()
fmt.Println(p.typeName())
var s shape = p
fmt.Println(s.typeName())
}
func main() { testPolygonThing() }
When we compile this, we get these errors:
./comp.go:130:16: ambiguous selector p.typeName
./comp.go:131:7: polygonThing.typeName is ambiguous
./comp.go:131:7: cannot use p (type *polygonThing) as type shape in assignment:
*polygonThing does not implement shape (missing typeName method)
where line 131 is the line where we are assigning to s.
From this error we can see that Go did not promote the typeName method from either
of the embedded structs into polygonThing. But there was no error message about the
call to draw, so it did promote that method from polygon, since it is
not ambiguous.
If we comment out the embedded thing line from the definition of polygonThing,
the code compiles.
If, instead, we comment out the embedded polygon line, we get different errors:
./comp.go:129:4: p.draw undefined (type *polygonThing has no field or method draw)
./comp.go:131:7: cannot use p (type *polygonThing) as type shape in assignment:
*polygonThing does not implement shape (missing draw method)
If we want to keep both embedded structs in our composite struct,
there are a couple of ways we can resolve the ambiguity of typeName
appearing in both embedded structs.
The simplest is to assign a name to one
of the embedded structs, converting it to a regular field. Instead of writing
thing in the definition of polygonThing, we can write t thing.
Go then does not attempt to promote the methods from thing into polygonThing,
and the promotion of typeName from polygon into
polygonThing is no longer ambiguous, so it succeeds.
Another possibility is to resolve the ambiguity by defining a typeName method
directly on polygonThing. In this case, Go does not attempt to promote typeName
from either of the embedded structs. We can call a method in an embedded struct
by referring to that embedded struct as if it were a named field.
Now that we understand how embedded structs work in Go, let's go back and reconsider what happened
with our printShapeNamesAndSides function.
Assume one of the elements in our slice of shape is an instance of triangle.
We call nameAndSides with that triangle as the receiver. Since we did not define nameAndSides
on triangle, that calls the promoted version of that method. That promoted method turns around and calls
nameAndSides on the embedded polygon, passing the embedded polygon as the receiver.
In polygon.nameAndSides, it calls p.typeName, but p here is the receiver of the
nameAndSides method, which is the polygon, not the triangle. So the call from nameAndSides
to typeName
call's the typeName method on polygon rather than on triangle.
With this understanding, let's update our code to make "overriding" work.
The difference between the behavior we are seeing and what we would expect from a system
with inheritance and overriding
is that here our "base class" does not, by default, make calls to methods of the "subclass".
It can't because the method in the "base class" has no reference to the type of the containing object.
In order to implement a call to method in an instance of a "subclass" from polygon.nameAndSides, we need a reference to
that instance, such as a triangle.
We will do this by explicitly passing our shape as an argument, then calling the typeName method on
that shape rather than on the receiver.
By calling a method on a passed-in argument rather than the receiver,
it is clear, when looking at that method in the "base class", that the call may
be going to a different type of object than polygon.
type shape interface {
...
nameAndSides(s shape) string
}
func (p *polygon) nameAndSides(s shape) string {
return fmt.Sprintf("%s (%d)", s.typeName(), p.sides)
}
func printShapeNamesAndSides(shapes []shape) {
for _, s := range shapes {
fmt.Println(s.nameAndSides(s))
}
}
The way Go promotes methods of embedded structs makes it have some of the characteristics of
inheritance as defined in object-oriented programming. In particular, it allows for methods to
be automatically promoted to the containing struct, and thus for interfaces to be automatically
promoted to the containing struct. One key difference is that, when you override one of those
promoted methods in the containing struct, the code in the embedded class does not automatically call the overridden
method in the containing class, as happens in some object-oriented languages such as Java.
You may have heard of the fragile base class problem.
A related issue, that can arise when there are downcalls from a superclass to an overridden method in a subclass,
similar to the example here where I "overrode" the typeName method,
might be termed the fragile subclass problem.
If you are interested into digging into that, you can read
Safely Creating Correct Subclasses without Seeing Superclass Code,
a paper from OOPSLA 2000 that examines that issue. See section 4.
The designers of Go chose not to implement inheritance, but instead to
favor composition.
Although some Go constructs can look a little like inheritance, it's better to
start thinking about designing in Go using composition rather than trying to bend
Go to do something like inheritance.
As described in my
previous blog post,
I recently rewrote my image viewer desktop app as a web app,
for which I wrote the web server in go.
Since I was adding a new potential attack vector, I wanted to add security;
but since this is only available on my internal network, and it's not
critically valuable data, I did not need enterprise-grade security.
In this post I describe how I implemented a relatively simple
authentication and authorization mechanism, in particular highlighting
the features of go I used that made that easy to do.
For a simple app such as this one, the third of the
three As of security, auditing,
can be done with simple logging if desired.
The code I present here is taken from the github repo for my
mimsrv project,
with links to specific commits and versions of various files.
You can visit that project if you'd like to see more of the code
than I present in this post.
Go has good support for writing simple web servers. The
net.http
package allows setting up a web server that routes
requests based on path to specific functions.
In the first commit for mimsrv, before there was any code for
authentication or authorization, the http processing code looked
like this:
The above two functions set up the routing and start the web server.
The code in mimsrv.go creates a top-level router (mux) that routes
any request with a path starting with "/api/" to the api handler that
is created by the NewHandler function in api.go. The top-level router
also defines routes for other top-level paths, such as "/ui/" for
delivering the UI files.
The api code in turn
sets up the second-level routing for all of the paths within /api
(the h.apiPrefix function adds "/api/" to its argument).
So when I make a request with the path /api/list, the main mux passes
the request to the api mux, which then calls the h.list function.
To implement authentication
in mimsrv, I added a new "auth" package with three files, and
modified mimsrv.go to use that new auth package. The most interesting
part of this change is that it implements the enforcement of the
constraint that all requests to any path starting with "/api/" must
be authenticated, yet I did not have to make any changes to any of
the api code that services those requests.
When I originally wrote my request routing code,
it could have been simpler if I had defined everything in one mux.
I didn't do that because I think the approach I took provides better
modularity, but in addition, that structure
made it easy for me to require authentication for all of the api calls.
The authentication code itself is not trivial, but wiring that code into
the request routing to enforce authentication for whole chunks of the
request path space was. I wrote a wrapper function and inserted it in the
middle of the request-handling flow for requests where I wanted to require
authentication.
To wire in the authentication requirement for all requests starting
with "/api/", I
changed mimsrv.go
to replace this line:
Here is the RequireAuth method from the newly added
auth.go:
func (h *Handler) RequireAuth(httpHandler http.Handler) http.Handler {
return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request){
token := cookieValue(r, tokenCookieName)
idstr := clientIdString(r)
if isValidToken(token, idstr) {
httpHandler.ServeHTTP(w, r)
} else {
// No token, or token is not valid
http.Error(w, "Invalid token", http.StatusUnauthorized)
}
})
}
The RequireAuth function looks at a cookie to see if the user is currently
logged in (which means the user has been authenticated).
If so, RequireAuth calls the handler it was passed, which in this case
is the one created by api.NewHandler. If not, then RequireAuth calls
http.Error, which prevents the request from being fulfilled and instead
returns an authorization error to the web caller.
When the mimsrv client gets this error it displays a login dialog.
The other code I added handles things like login,
logout, and cookie renewal and expiration, but all of
that code other than RequireAuth is specific to
my implementation of authentication. You could instead, for example,
use OAuth to authenticate, in which case you would have a completely
different mechanism for authenticating a user, but you could still
use a function similar to RequireAuth and wire it in the same way.
Wrapping selected request paths as described above makes it so that
authentication provides authorization for those requests.
This coarse-grained authorization is a good start, but for mimsrv I
wanted to be able to use fine-grained authorization as well.
As this is a simple program with a very small number of users,
I don't need anything sophisticated such as
role-based authorization.
I chose to implement a model in which I only define permissions for
global actions, then assign those permissions directly to users.
For this simple permissions model, I needed to be able to define permissions,
assign them to users, and check them at run-time before performing an
action that requires authorization. My permissions are simple strings,
stored in a column in the CSV file that defines my users. To give a
permission to a user, I manually edit that CSV file, and to check for
authorization before taking an action, the code looks for that permission
string in the set of permissions for the current user.
The one piece that is not obvious is how to pass the user's permissions
to the code that needs to check them.
The reason this is not obvious is because the http routing package
defines the function signature for the functions that process an http
request, and that function signature includes only the request and
a writer for the response.
You can't simply add another argument in which you pass your user
information, so you have to dig a little deeper to figure out how
to pass along that information.
The solution relies on the fact that there is a Context attached to
the Request that is passed to the handler function. By adding the user
info to the Context, you can then extract that information further along
in the processing when you need to check the permission.
The RequireAuth function validates that the user making the request is
authenticated, so it already has information about who the user is, and this
is the point at which we want to add the user info to the Context.
We do this in our RequireAuth function by
replacing
this line:
When the code needs to know whether the current user is authorized for
an action, it can call the new
CurrentUser function,
which retrieves the user info from the Context attached to the Request,
from which the code can query the user's permissions:
func CurrentUser(r *http.Request) *users.User {
v := r.Context().Value(ctxUserKey)
if v == nil {
return nil
}
return v.(*users.User)
}
While implementing authentication and authorization in a web server takes
more than just a few lines of code, at least the part about how it gets
tied in to the http processing in go is only a few lines. Although that
part is only a few lines of code, it took me a while to dig around and
find exactly how to do that. I hope that this article can save some other
people a bit of time when doing their own research on how to add auth to a
go web server.
I have found Go to be a nice tool for developing a small web server,
and Polymer + Typescript to be a nice combination for developing a web UI.
The Go server acts as both the API server and the static content server
delivering the UI pages.
If you think you might want to try this approach, you can look at my
mimsrv program on github
as an example.
If it looks too complicated, browse in the git history back to some of
the earliest commits, such as the
first ui commit
and the
first api commit,
to see how things looked at a simpler time.
Background
I have been developing web pages and apps for a long time,
since the earliest days of HTML when there were no tools
more sophisticated than a text editor, and server-side scripts
were the only form of executable web code.
In 1994 I wrote
htimp,
an experiment in how to attach a web browser to an interactive program
with a lifetime longer than a single message.
Over the years I tried many technologies, including
JavaServer Pages,
JavaServer Faces,
PHP,
jQuery, and others I have forgotten.
Some were better than others (more accurately, some were bad
and some were excruciating),
but I never felt any of them provided a reasonable mental
model for how to put together an application.
I was away from the web UI scene for a while, and when I got back to
doing some web development a couple of years ago, things seemed to have
improved quite a bit. In the last year, I have been introduced to a few
technologies that, in combination, provide me with a development
environment with a working mental model of how to put together a program,
and a set of tools that makes it easy to do that at a good clip.
The three technologies that together have brought pleasure back to my web
programming are:
Below I describe the project on which I tried out these technologies,
followed by a discussion of what I liked about them.
Mimsrv
Mimsrv
is a web server and UI to view a collection of photos.
It is a replacement for
mimprint,
which is a desktop app that I
originally wrote starting in 2001 in Java, and converted to Scala
starting in 2008.
A couple of years ago I started looking into
rewriting mimprint once again, this time as a web app.
As a web app, I would no longer have to worry about distributing a
desktop application to the various machines I have on which I wanted to view
my photos.
I also thought I should be able to leverage the web browser's
media capabilities so that I would not have to develop or support
that whole chunk of code.
The tools I tried were never nice enough to pull
me in and get me going on that replacement, and I had moved my
rewrite-mimprint project way down on my TODO-list.
At Google last year I worked on the open-source
Datalab project.
When I started on it, we were using jQuery and Javascript.
I liked it when we converted to Polymer-2 and Typescript,
and I liked it more when we switched to using Polymer decorators.
I started learning Go in order to review code from my teammates. It took
a little getting used to, but the more I learned, the more it made sense
to me. I felt it was much easier to understand the existing Go
codebase than similar codebases I had looked at in other languages. It
grew on me, and after I started adding my own Go code to the project, I
was surprised at how much I liked using it, and I felt that I was making
pretty good coding progress.
I thought the combination of Go for the server, and Polymer and Typescript
with decorators for the client, worked quite well, and I decided to try it
for my personal project.
So far that combination has worked well for me, and I have been quite
happy with it.
What I Like
Offline Development
One of my requirements is that I be able to develop when I am offline. I
insist on this because one of the situations in which I have the most
amount of time available for programming on my personal projects is when I
am traveling and often don't have network access.
In a previous attempt at putting together a collection of technologies
for developing web apps, some of the pieces used maven, and I was unable
to figure out how to convince it not to go out looking for new versions
of the snapshots I needed every time it compiled.
After using Go on a project at work and being pleasantly surprised at how
much I enjoyed using it, I decided to see it if would work for my
personal projects. When I downloaded and installed it, I was delighted to
discover that, not only did the installation provide everything I needed
to compile and run my programs, but it also included all of the documentation
and the Go Tour, so those would all be available to me offline!
Similarly, the Typescript and Polymer tools allow just building the
code, without attempting to do any dependency resolution, so can
easily be used offline.
Simple Mental Model
There are a couple of changes to the web app landscape that have made for a
much simpler mental model than in the old days.
The main one is the Single Page Application (SPA).
With the old approach of having to move to a new page every time the
user took an action, saving state across those page changes
required mental and technical gyrations.
With a SPA, you make AJAX calls to the server using XMLHttpRequest,
and just keep your state in variables as in any other program.
The SPA model also allows for a clean separation of responsibility
between the server and the client. With Polymer, all of the UI
manipulation is handled in the client, so the server doesn't need to
deal with any kind of templating of client-side functionality.
This means the server can focus on the API and on just delivering the
UI code to the client, and the client can focus on managing the UI
and making API calls.
The other big change on the client side is the progress that has been made
on the asynchronous programming model.
At first we had to pass around success and failure callbacks,
which requires splitting code up in unwieldy ways around every
asynchronous call.
The introduction of Promises provided a nice way to avoid
the "callback hell" of deeply nested callbacks,
but still requires chopping your code up around every
asynchronous call.
Lastly, the introduction of the async and await keywords
made asynchronous programming almost as straightforward as
synchronous programming.
I'm particularly impressed that you can do things like have an
if-statement with synchronous code on one side and asynchronous
code on the other side, or a loop with an asynchronous call in it.
This is so much simpler to reason about than if you had to figure out
how to do that with callbacks or even Promises.
Simple Dependency Management
The few times I had to deal with Maven were unpleasant.
I found it hard to control, hard to configure, and hard to understand
what it was doing. Perhaps it's just that, with the march of time,
people have figured out how to make dependency management better,
but I found the dependency management in both Go and Polymer to be
pleasant to use.
In Go, when you need a package, you just say go get package,
and it downloads that package and all its dependencies. Assuming you follow
the Go conventions when naming and locating your package, when someone
then wants to download your package, they do the same thing, and Go will
also download all of your dependencies to their system.
Polymer-2 uses bower for its package management, and it is almost as easy
to use. The bower.json file lists the packages needed,
and running bower install installs those packages and their
dependencies. When you add a new dependency to one of your Polymer components,
you just run
bower install --save new-package to download that
new package, and you're done.
Not quite as effortless as go, but much better than my
experience with maven.
For both Go and bower, they don't attempt to download anything except
when you explicitly tell them to with go get or
bower install, which is good for offline development.
Simple Compilation
For pretty much my whole programming career, I have been accustomed
to using some kind of build tool that requires a configuration file:
make, ant, maven, sbt, grunt, bazel, gradle, and others.
Go is different: it is so opinionated about where you have to put your
packages and how you have to name stuff, that it has all the dependency
information it needs by looking at the source files. You just tell it
to build your program with the command go build, and it
does it. No build config file required.
The Typescript compiler and Polymer build commands do require config
files, but they were pretty simple to set up and understand,
and seldom need to be modified. Running tsc compiles all
the Typescript files to Javascript, and running polymer build
packages all the Polymer Javascript and HTML files into a directory
where they are served by the Go server.
Type Safety
I like the compiler to catch as many errors in my code as possible.
Using compile-time types allows the compiler to spot more errors.
This is why I greatly prefer Typescript over Javascript.
Go is also a compiled and typed language, so it catches a lot of
problems before execution time.
Separation of Concerns
While I don't think having to use multiple languages is a benefit,
the ability to select the best tools for different parts of the problem
is.
Go works very well as a web server for API calls and static content.
Most people using Polymer embed Javascript code in their HTML file,
but I prefer using Typescript and am happy putting that in a separate
file from the HTML, where my editor understands it better.
Go http support
Go has a nice http package that makes it easy to define web routing
and implement handler functions.
Because Go supports functions as first-class
values, it's easy to define a function that can take a function as
an argument and return another function. In my case, I used that
approach to create a function that I could use to specify that certain
parts of my API required authentication.
I wrote my http handlers to do only the marshaling and unmarshaling
of data and then call the underlying routine that implements the
requested functionality. This made it easy to write unit tests of the
underlying function.
But Go also provides a nice testing package for http handlers that makes it
relatively easy to test the http handler as well.
Room for Improvement
I'm pretty happy with this collection of technologies, but there are
a couple of things I would like to see improved.
Polymer/Typescript type mismatch
Polymer decorators are a nice improvement over the previous approach, as
there is now much less boilerplate and repeated code. But I still have to
specify a type in each Polymer.decorators.property line, and
that type is not quite the same as the Typescript type (for example,
string vs String, any vs Object).
I suppose this is not that surprising, given that Typescript is not
officially supported by Polymer. I guess that's really what I would
like to see happen.
Debugging Typescript
Writing Typescript rather than Javascript is nice, but when it gets
loaded into the browser it's Javascript, so debugging in the browser
uses the transpiled Javascript.
The Javascript is usually close enough to the source Typescript that it's
manageable, but it would be nice to be able to debug with the Typescript
source code.
Maybe this situation will get better when
WebAssembly gets implemented.
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.
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.
