May 13th, 2006
SpocP and Lisp.
For a few years I’ve been involved with an open source project called SpocP, through work. SpocP is a framework and protocol for handling mostly any authorization tasks any application can have. The base distribution is a server written in C, which when started with rules definitions answers TCP (or socket) requests with YES or NO, and attaching a blob if the rule says so. If you want to, you can write all your authorization information directly in SpocP rules. This is usually not that interesting since the common case is that you have a data source somewhere that you’d like to use as basis for authorization. Maybe a LDAP server with role information, maybe an RDBMS, or something entirely different.
The interesting thing about SpocP is the format used for Rules and Queries. (Rules are what SpocP uses to provide an answer, a Query is a specific authorization request translated into the SpocP Query language. In human terms a rule might be “All persons who have OU=itc in our LDAP server have access to all pages of the web application named ‘itdoc'”, and a typical query that might answer YES for this rule is “Can the person with uid ‘olagus’ access the page ‘showLinks.do’ for application ‘itdoc’?”). The format for queries and rules in SpocP is based on S-expressions (which is a fancy word for more-or-less-Lisp syntax). The reason for using S-expressions is the interesting fact that S-expressions have the mathematical property that one S-expression can be compared to another, and judge less-than-or-equal or not. This is all that’s needed to implement generic authorization facilities, and also some other fascinating possibilities. As an example, take a rule file looking like this:
(spocp (action view) (resource (app “itdoc”) (page “admin.do”)) (subject (uid)))
(spocp (action view) (resource (app “itdoc”) (page)) (subject (uid)))
(spocp (action admin) (resource (app “kimkat”)) (subject (uid) (role)))
and a query like this:
(spocp (action view) (resource (app “itdoc” “http://itdoc.it.ki.se”) (page “showLinks.do”)) (subject (uid “olagus”) (role “user”) (loggedIn 200505260115)))
When receiving this request, SpocP will walk through all rules until it finds anyone where the RULE is <= QUERY. If it does find one matching it will return "YES" otherwise "NO". In this case rule number 2 would make the answer "YES". You've now seen the first part of SpocP matching. But how do we involve external data sources? With something called boundary conditions. The idea is that for each rule matching, check the attached boundary conditions, and if these return positive answers too, the whole expression is deemed true. A typical boundary condition may look something like this:
urn:spocp:ldapset:ldap.ki.se;ou=people,o=ki.se;{uid & ${uid}}/ou & “itc”
which more or less is the same as the LDAP query (&(uid=$UID)(ou=itc)).
This boundary conditions checks if the second element of the list with tag “uid” exists in our LDAP server, and if that entry also has an ou with value “itc”. Boundary conditions can be chained and linked with and, or and not, and you can also predefine boundary conditions so you don’t have to define the same one more than once.
I recommend using SpocP if you have a need to decouple your authorization from the application. As soon as you have defined what kind of queries a typical application may do, you can implement this on a central server, and when your business rules change, you can change the SpocP definitions without having to change the application. There is not much extra complexity involved and you buy yourself some very nice flexibility. There are SpocP client libraries available for most of the standard languages.
The fun thing with SpocP is that the fundamental operation of checking less-than-or-equal between two S-expressions have always been defined mathematically, and in some highly optimized C-code. When fooling around with this, I found a simple executable definition of the SpocP core in Common Lisp. The whole thing look like this:
(defun starform-p (list)
(eql (first list) ‘*))(defun starform-match (query rule)
(let ((form (second rule))
(data (cddr rule)))
(case form
(any (member query data))
(prefix (string-equal (car data) (string query) :end2 (length (car data))))
(suffix (string-equal (car data) (string query) :start2 (- (length (string query)) (length (car data)))))
(range (member query data)) ;;not implemented
(set (member query data))
(t t))))(defun matches-p (query rules))
(some #'(lambda (rule) (match-p query rule)) rules))(defun match-p (query rule)
(if (and (atom query) (atom rule))
(eql query rule)
(if (starform-p rule)
(starform-match query rule)
(every #’match-p query rule))))
The only thing missing here is one of the so called star-forms, range. Otherwise this is a complete definition of the SpocP core evaluation of rules. To use it, do something like this:
(matches-p ‘(spocp (action view) (resource “foo”)) ‘((spocp (action admin) (resource) (subject (uid) (role “admin”)))(spocp (action view) (resource “foo”))))
