Chapter 1: Introduction
Fall 2020
Cp 633
Slide #3-*
Chapter 3: Foundational Results
Decidability
We will use only sections 3.1 and 3.2
Cp 633
*
Fall 2020
Cp 633
Slide #3-*
Overview
We consider access control matrix without own and copy rights and assume only mono-operational protection commands.
We consider generic right r.
We assume that attenuation of privilege rule does not exist.
We consider security view based on rights
Start with access control matrix A
Leak: is a situation when command adds right r to an element of A not containing r.
Safe: System is safe with respect to right r if r cannot be leaked
Here, “safe” = “secure” for an abstract model
However, safe abstract model may not have secure implementation.
Cp 633
*
Fall 2020
Cp 633
Slide #3-*
What Is “Secure”?
Adding a generic right r where there was not one is “leaking”
If a system S, beginning in initial state s0, cannot leak right r, it is safe with respect to the right r.
This is very restrictive.
E.g. network administrator can listen to networking traffic but can not communicate with users so his right can not be passed on to the users.
Does there exist an algorithm for determining whether a protection system S with initial state s0 is safe with respect to a generic right r?
Cp 633
Fall 2020
Cp 633
Slide #3-*
Safety Question
Given
initial state X0 = (S0, O0, A0)
Set of primitive commands c
Can we reach state Xn where s,o such that An[s,o] includes a right r not in A0[s,o]?
If so, the system is not safe.
Note that safety doesn’t distinguish leak from authorized transfer of rights
Subjects authorized to receive transfer of rights deemed “trusted”
Eliminate trusted subjects from matrix
Cp 633
Fall 2020
Cp 633
Slide #3-*
Decidability Theorem HRU
(Harrison, Ruzzo, Ullman)
Given a system where each command consists of a single primitive command HRU result says:
Theorem: There exists an algorithm that will determine if a protection system with initial state X0 is safe with respect to right r.
However, even if ACM is safe we need to check if:
Are commands correctly implemented?
Are commands protected against concurrency issues?
Are commands invoked with the right parameters?
Cp 633
Decidability Result HRU
Proof: determine minimum number of commands k to leak
Delete/destroy commands: Can’t leak (or be detected)
Create/enter: new subjects/objects “equal”, so treat all new subjects as one i.e. the first one s1 to leak the rights.
That subject can change access rights for any object.
Assume that at creation of leaking subject there were |S0| subjects and |O0| objects in the ACM.
This new subject can change any field in the new ACM which has (|S0|+1)(|O0|+1) fields.
If leak on any of n rights is possible, must be able to leak in n(|S0|+1)(|O0|+1)+1 commands.
Fall 2020
Cp 633
Slide #3-*
Cp 633
Fall 2020
Cp 633
Slide #3-*
Decidability: Non-Primitive Commands
In a system with potentially unlimited number of subjects it is un-decidable if a given state of a given protection system is safe for a given generic right.
However, if the number of subjects is finite, the safety of arbitrary authorization system is decidable.
Cp 633
Fall 2020
Cp 633
Slide #3-*
Example: Unix file system
Access Control Matrix
Root has access to all files
Owner has access to his/her own files
How can Unix be safe with respect to file access right?
No chmod/chown command ?
Only “root” can get root privileges no Set-user-id feature?
Only user can authenticate as himself, i.e. no /dev/su program
Is “Safe” definition useful?
Cp 633
Fall 2020
Cp 633
Slide #3-*
Example of problematic command: The user ID of a process in Unix
The kernel associates two user IDs with a process: a real user ID and effective user ID or setuid.
Real user ID identifies the user responsible for running the process.
The effective user ID is used to:
assign ownership of newly created files, to perform file access and to send signals (kill).
A setuid program is an executable file which has setuid bit set in its permission mode field.
When a process exec-s a setuid program the kernel sets effective user id in the process table to the owner ID of the executable file.
A child process inherits parent’s real and effective user id.
Cp 633
Fall 2020
Cp 633
Slide #3-*
Example : setuid
Assume two users in the system:
Maury with user id 8319
Mjb with user id 5088
Maury has created executable file named “program” with setud bit on.
There are also two data files “maury” and “mjb” owned by Maury and Mjb respectively.
On following slide we show source code for “program”.
Cp 633
Main() { int uid, euid, fdmjb, fdmaury;
Uid = getuid(); /* get real UID */
Euid = geteuid(); /* get effective UID */
Printf(“uid %d euid %d\n”, uid, euid);
Fdmjb= open(“mjb”, O_RDONLY);
Fdmaury= open(“maury”, O_RDONLY);
Printf(“fdmjb %d fdmaury %d\n”, fdmjb, fdmaury);
Setuid(uid);
Printf(“after setuid (%d): uid %d euid %d\n”, uid, getuid(), geteuid());
Fdmjb = open(“mjb”, O_READONLY);
Fdmaury= open(“maury”, O_RDONLY);
Printf(“fdmjb %d fdmaury %d\n”, fdmjb, fdmaury);
Setuid(euid);
Printf(“after setuid (%d): uid %d euid %d\n”, uid, getuid(), geteuid()); }
Fall 2020
Cp 633
Slide #3-*
Results of the program
When user “mjb” runs the program the output is:
Uid 5088 euid 8319
Fdmjb –1 fdmaury 3
After setuid (5088): uid 5088 euid 5088
Fdmjb 4 fdmaury –1
After setuid (8319): uid 5088 euid 8319
When user “maury” runs the program the output is:
Uid 8319 euid 8319
Fdmjb –1 fdmaury 3
After setuid(8319): uid 8319 euid 8319
Fdmjb –1 fdmaury 4
After setuid(8319): uid 8319 euid 8319
Cp 633
Fall 2020
Cp 633
Slide #3-*
Login program in Unix
Many system programs use setuid call.
The login program uses setuid call
Login is setuid to superuser and starts running with effective user ID root.
It queries the user for password and if passwd check is ok, invokes the setuid system call to set the real and effective user ID to that of the user trying to log in (found in “/etc/passwd”).
Login finally exec-s the shell which runs with real and effective ID for the appropriate user.
Cp 633