Safety of File Protection Systems

This is the last problem in the “Storage and Retrieval” section of the appendix and uses the Linear Bounded Automaton Acceptance problem from last week. So, since LBA acceptance was “not known to be in NP”, this problem is as well.

The problem: Safety of File Protection Systems.  This is problem SR36 in the appendix.

The description: We’re given:

  • A set R of “generic rights” (intuitively, these are things like “read access” or “write access”)
  • A set O of “objects”
  • A set S ⊆ O of “subjects”
  • A matrix P defining the set of rights for each combination of set and objects.  That is: for all s∈S and o∈O, P[s][o] defines the rights (a subset of R)  that subject s has on object o.
  • A set C of “commands”  Each command takes a set of parameters X1 through Xm, where each Xi is an object (and many are subjects as well).
  • The commands begin with a series of if statements: “if ri ∈ P[Xsi][Xoi]”, where “si” and “oi” are numbers from 1 to m.  So the if statement is asking if a specific right exists for a specific pair of parameters to the command.  The command will have several of these if statements connected by “and” statements.
  • If all of the clauses in the if statement is true then a list of several operations can happen.  The two operations that can happen are “enter a right into P” or “delete a right from P”.   I think you can also delete objects and subjects, but you can’t create them (in the version of the problem we’re talking about), so I don’t know if it matters

Can we find a sequence of commands in C where at some point in the sequence after executing a command, some set P[s][o] has a right r’ that it previously did not have?

Example: It’s pretty easy to come up with an example that is unsafe- just create a function that gives a right to someone.  I think where it gets harder is when you deal with operations that have sets of commands.  Here is an example from the paper by Harrison, Ruzzo, and Ullman that discusses this problem:

command IREAD(s1, s2, o){  
  if "read" ∈(s2, o) and
     "iread" ∈ (s1, s2)
     enter "read" into (s1, o)
     delete "read" from (s1, o)

The command “iread” is meant to stand for “indirect read”.   So what this is saying is that s2 can read 0, and s1 has the rights to read what s2 reads.  So s1 gets (temporary) permission to read 0.  Presumably, some time passes in between the granting of the read permission to s1 and the removal of that right, during which the data in o gets read by s1.  Notice that this is a safe procedure because, by the end, no new rights have been granted.

Reduction: The paper referenced above shows that a system in which we also have operations that can create objects and subjects is undecidable.  They do this by showing how this system can simulate an arbitrary Turing Machine.  The reduction turns each transition into a command in the system: The current state, the current cell the head is over, and the contents of that cell are implemented as rights, and then state transitions can be seen as commands: The “if” parts of the command check that the machine is in the correct configuration, and the “then” parts change rights in a way that simulates the moving of the head, the output to the tape, and the transition to a new state.   Importantly for our purposes, the only time these commands use the “create” commands (that are in the undecidable version of the problem, but not in ours) is when the Turing Machine moves the head into a previously unexplored area of the tape.

They then say that in our problem, which doesn’t have “create” commands, a simulation “similar to that used” in the undecidability reduction can also be used to convert an LBA into a set of commands, since an LBA won’t be moving its head arbitrarily into new space.  I think the LBA still is allowed to use some new space though, but I guess that since it is bounded by a polynomial in the input size, we can simulate that by having each cell get it’s own access rights, and that keeps us with a polynomial-sized reduction.

Difficulty: 8.  This is a hard problem to understand, and the reduction is done in a non-standard way (and depends on the LBA acceptance reduction which is also done in a non-standard way), so it may throw some people for a loop.  It is a cool example of showing non-standard ways to reduce things though if that’s what you’re looking for.

Leave a Reply

Your email address will not be published. Required fields are marked *