Using Prolog to implement authorization rules

Question

I'm working on a user management "pseudoframework" in PHP, and I'm trying to implement fine-grained rule-based authorization. I'm using a combination of SQL and condition-checking functions written in PHP right now, but I'm not completely satisfied. It works, but it is not very elegant and suffers from some limitations.

Prolog is Turing-complete, so it occurs to me that any arbitrary authorization rules could be implemented this way. For example:

in_group("Alice","admin").
in_group("Alice","user").
in_group("Bob","user").
in_group("Carlos","admin").
in_group("Carlos","user").
allowed("delete_user",X,Y):-    in_group(X,"admin"),
                                not(in_group(Y,"admin")).

This basically says "Only allow user X to delete user Y if X is an admin and Y isn't."

My questions are basically:

1. Will issues in scalability still arise in modern Prolog implementations?
2. How would these issues be complicated by the way that people typically use web applications?
3. What are the risks of compromising security due to the "unintended consequences" of some Prolog constructs?
4. How difficult will this make it for people without a Prolog background to modify authorization rules? The above example looks straightforward to me, but what if there are thousands of rules?

If Prolog isn't the best idea for this situation, are there other logic programming languages that might be better suited?

I read this post: Why Aren't Rule Engines Written In Prolog?, but that question seems to be about rules engines in general, not authorization rules specifically.

Answer 1

Even though this could work, this might be a little overkill.

1. Will issues in scalability still arise in modern Prolog implementations?

Beware of strings. In some implementations, the generated code for querying in_group/2 will result in a lot of branching, as in if "Alice" then ... else if "Bob" ....

Replace double-quotes with single-quotes, and you have atoms, which lead to hash-table based queries. Unless you want to complicate things, have names and roles in ASCII (if you can).

Some implementation also have worker threads, if you want to have multiple queries in parallel.

2. How would these issues be complicated by the way that people typically use web applications?

This should not matter.

3. What are the risks of compromising security due to the "unintended consequences" of some Prolog constructs?

Well, you can backtrack, but this is intended, right?

• in_group(X,Y) gives you all pairs of values.
• in_group(N,admin) gives you all admins.
• in_group(N,admin),in_group(N,user) gives the intersection of users and admins.
• in_group(N,X),member(X,[admin,user]) gives the union instead.

Unintended consequences are synonym with programming errors here, assuming you understand the language. If you mess with variable names or make a typo, you could have an exception at runtime: you generally don't leave the execution environment (even if you stack-overflow because you wrote an infinitely recursive predicate), but you can't reply to further requests. This is the same as for any dynamic language.

How difficult will this make it for people without a Prolog background to modify authorization rules? The above example looks straightforward to me, but what if there are thousands of rules?

If you don't enclose name in quotes and start them with an uppercase letter, those are variables: you will have the unintended consequences you mentioned.

Maybe you can try to teach and trust people who will modify your file (but compile and test your queries before deploying).

Otherwise, make them use "higher-level" queries that check inputs and produce predicates (i.e. dynamic predicates or compile_term).

Answer 2

A much better framework for this kind of thing is Drools. It uses a very efficient algorithm to search for rules that apply to a given set of facts. It is a Java-based system, so you won't necessarily want to use it in your program but you should study it to see what you can learn about how the pros do it.

All of that being said, I believe you are opening your application up to a world of heartache. Having many different, fragmentary statements about security and accessibility creates a nightmare world where it is extremely easy to specify rules that allow large trucks to drive in and steal your stuff, or, almost as bad, wall off areas of a system that are not accessible by the people who need to access it, in a computer-driven catch-22.