Access Control Matrix

Protection State
State of a system
Current values of
All memory locations .
Registers
Other components of the system .

Protection state of system

Describes system attributes relevant to protection.

 P all possible protection states .

Q all authorized states (secure).
P-Q all elements of P are not in Q,
Not a secure state.

Security policy
Characterize the states in Q.

Security mechanism
Prevent the system from entering a state in PQ.

Access control matrix

Describes protection state precisely.
Matrix describing rights of subjects.
State transitions change elements of matrix.
read, write, send data, loading, execution (of a
program).
Object is the set of all protected entities.
Subject is set of active objects.

Description

Access Control Matrix for System

Processes p, q
Files f , g
Rights r, w, x, a, o
Rights are merely symbols; interpretation depends
on system .
Example: On UNIX, r means read for file and
list for directory.

Example 2:Permissions in UNIX

systems

File r,w,x
Dir r,w,x
Process r,w,x
Users and superuser

Access Control Matrix for Program

Procedures inc_ctr, dec_ctr, manage
Variable counter
Rights +, , call

Boolean Expression Evaluation

ACM controls access to database fields
Subjects are users authorized to access the
databases.
Verbs define type of access.
Rules associated with objects, verb pair.

Subject attempts to access object

Rule for object, verb evaluated, grants or denies
access.

 The Access Restriction Facility (ARF) defines

subjects as having attributes such as names , a
level, a role ,membership in groups and access
to programs.

 Verbs have a default rule:

"closed" : access denied unless explicitly granted (0)
"open" : access granted unless explicitly denied (1)

 Associated with each object is a set of verbs,

and each (object, verb) pair has an associated
rule:

Example
Subject Annie
Attributes role (artist), groups (creative)

Verb paint
Default 0 (deny unless explicitly granted)
Object picture
Rule:
paint: artist in subject.role and
creative in subject.groups and
time.hour 0 and time.hour < 5

ACM at 3AM and 10AM

At 3AM, time condition
met; ACM is:

At 10AM, time condition

not met; ACM is:

Access Controlled by History

Statistical databases are designed to
Answer queries about groups of records.
Prevent revelation of individual records.
Users query the database about sets of records C;
this set is the query set.

Query-set-overlap control
Prevention mechanism that answers queries only
when the size of the intersection of the query set
and each previous query set is smaller than some
parameter r.

Example
Consider the database with set r = 2.
Name

Position

Age

Salary

Celia

Teacher

45

$40000

Heidi

Aide

20

$20000

Holly

Principal

37

$60000

Leonard

Teacher

50

$50000

Matt

Teacher

33

$50000

 First query set be C1 = Position is

teacher"
Query 1:
sum_salary(position = teacher)

C2 =Age greater than 40 and teacher

Query 2:
sum_salary(age > 40 & position = teacher)
Should not be answered as Matts
salary can be deduced.

 This control can be modelled using an access

control matrix.
Subjects: entities issuing queries.
Objects: elements of the power set of records.
Oi : objects referenced in accesses 1..i
The function f(Oi) is read if |Oi| > 1 else is
A[s, o] = f(Oi+1 { o }) for query i where 1 <=i
and O0 = .

 Query 1: O1 = {Celia, Leonard, Matt} so the query can

be answered
A[asker, Celia] = {read}
A[asker, Leonard] = {read}
A[asker, Matt] = {read}

Query 2: O2 = {Celia, Leonard} but | O2 O1 | = 2; so

the query cannot be answered
A[asker, Celia] =
A[asker, Leonard] =

Protection State Transitions

Change the protection state of system.
| represents transition
Xi | Xi+1: command +1 moves system from
+1
state Xi to Xi+1 .
X| * Y : a sequence of commands moves system
from state X to Y.

Xi |

1 (
+
11
+ ,

, ,

1 )
+ ,

Xi+1

There is a command parameterized by

pk,1 pk,m that takes the system from state Xi to Xi+1

Primitive Commands
Set of primitive commands that alter the access
control matrix.
Before the execution of each command
protection state is (S;O;A) and (S;O;A) after
each command .
The preconditions state the conditions needed
for the primitive command to be executed, and
the postconditions state the results.

Create Subject
Precondition: s S
Primitive command: Create subject s
Postconditions: S' = S { s },
O' = O { s },
( y O')[a'[s, y] = ],
( x S')[a'[x, s] = ],
( x S)( y O)[a'[x, y] = a[x, y]]

Create Object
Precondition: o O
Primitive command: create object o
Postconditions: S' = S,
O' = O { o },
( x S')[a'[x, o] = ],
( x S)( y O)[a'[x, y] = a[x, y]]

Add Right
Precondition: s S, o O
Primitive command: enter r into a[s, o]
Postconditions: S' = S,
O' = O,
a'[s, o] = a[s, o] { r },
( x S')( y O')[(x, y) (s, o) a'[x,y] = a[x, y]]

Delete Right
Precondition: s S, o O
Primitive command: delete r from a[s, o]
Postconditions: S' = S,
O' = O,
a'[s, o] = a[s, o] { r },
(x S')(y O')[(x, y) (s, o) a'[x, y] = a[x, y]]

Destroy Subject
Precondition: s S
Primitive command: destroy subject s
Postconditions: S' = S { s },
O' = O { o },
(y O')[a'[s, y] = ],
(x S')[a'[x, s] = ],
( x S')(y O')[a'[x, y] = a[x, y]]

Destroy Object
Precondition: o O
Primitive command: destroy object o
Postconditions: S' = S,
O' = O { o },
(x S')[a'[x, o] =],
(x S')(y O')[a'[x, y] = a[x, y]]

Creating File
Process p creates file f with own, r and w
permission
command createfile(p, f)
create object f;
enter own into A[p, f];
enter r into A[p, f];
enter w into A[p, f];
end

Creating Process
Process p wishes to create a new process q.
command spawnprocess(p, q)
create subject q;
enter own into a[p, q];
enter r into a[p, q];
enter w into a[p, q];
enter r into a[q, p];
enter w into a[q, p];
end

Mono-Operational Commands
Make process p the owner of file g.
command makeowner(p, g)
enter own into a[p, g];
end
Mono-operational command
Single primitive operation in this command

Conditional Commands
Let p give process q rights to read a file f, if p
owns f
command grantreadfile1(p, f, q)
if own in A[p, f]
then
enter r into A[q, f];
end

Mono-conditional command
Single condition in this command

Multiple Conditions
Let p give q r and w rights over f, if p owns f
and p has c rights over q
command grantreadfile2(p, f, q)
if own in A[p, f] and c in A[p, q]
then
enter r into A[q, f];
enter w into A[q, f];
end

Principle of Attenuation Privilege

A subject may not give rights it does not
possess to another.
If Matt cannot read the file xyz , he should not be
able to grant Holly the right to read that file.

On most systems, the owner of an object can

give other subjects rights over the object
whether the owner has those rights enabled
or not .

 EXAMPLE: Suppose user bishop owns the file

/home/bishop/xyz but does not have read
permission on it.
chmod go+r /home/bishop/xyz

Copy Right
Allows possessor to give rights to another.
Often attached to a right, so only applies to
that right
r is read right that cannot be copied.
rc is read right that can be copied.

Is copy flag copied when giving r rights?

Depends on model, instantiation of model.

 EXAMPLE: c - copy right

p- subject has r rights
f - object.
Then the following command allows p to copy r over f
to another subject q only if p has a copy right over f.
command grantr(p,f,q)
if r in a[p,f] and c in a[p,f]
then
enter r into a[q,f];
end

Own Right
The own right is a special right that enables
possessors to add or delete privileges for
themselves.
It also allows the possessor to grant rights to
others.
The owner of an object is usually the subject
that created the object or a subject to which
the creator gave ownership.

Key points
The Access Control Matrix is the simplest abstraction
mechanism for representing protection state.
Transitions change the state of a system and are expressed in
terms of commands.
There are six primitive operations for altering the access control
matrix.
Transitions can be expressed as commands composed of these
operations and, possibly, conditions.
Such conditions may involve ownership or the ability to copy a
right.