CS5430 System Security - Project 1 (Fall 2020)

CS5430 Project 1: Access Control Analysis (Fall 2020)

General Instructions. You are strongly encouraged to work as part of a group of 3 students, but working alone or in a smaller group is allowed. Match-making assistance will be provided to those seeking to form groups.

Due: October 27, 2020 at 10:00am. No late assignments will be accepted.

Submit your solution using CMS.

With discretionary access control, the system associates with each subject a separate set of privileges for accessing each object. For this assignment:

the set of subjects are principals that invoke various operations, and
the set of objects includes all files as well as all subjects.

At any time, the operations that the system allows to be executed are described by the set of valid authorization triples. A valid authorization triple ( S, O, p ) signifies that subject S is allowed to perform any operation on object O for which privilege p is required. The set of valid authorization triples might be represented by using access control lists, capabilities, and/or an access control matrix.

This assignment is concerned only with authorization triples for certain privileges: R, W, and G.

( S, O, R ) authorizes subject S to invoke a read operation on a file O.
( S, O, W ) authorizes subject S to invoke a write operation on a file O.
( S, S', G ) authorizes subject S to invoke a grant operation that augments the privileges of subject S' by creating a valid authorization triple ( S', O, p ) for every object O and every privilege p where a valid authorization triple ( S, O, p ) already exists.

Privilege Analysis. A security administrator could be concerned about whether ( S, O, p) is valid or could become valid because of some grant operations. The answer to this safety question can be determined by writing a program to analyze the set of valid authorization triples.

The input to such an analyzer is a sequence of lines. Each line contains either a single syntactically correct command or a comment. The syntax for a command is detailed below. The syntax for comments allows any text that is not a syntactically correct command.

Input lines are processed in the order read. The processing of a command is explained below. To process a comment, that comment is simply copied to the output. Any sequence of comments and commands is allowed.

The Add and Query commands facilitate privilege analysis. Initially, no authorization triple is valid. Add asserts that an authorization triple is valid; query ascertains whether an authorization triple is already valid or could become valid by grant operations.

For an Add or Query command to be considered syntactically correct, we require:

subj be a name that has (i) not appeared in a previous command or (ii) has appeared and was used to identify a subject.

obj be a name that has (i) not appeared in a previous command or (ii) has appeared and was used used to identify an object.

priv is one of R, W, or G, as appropriate depending on whether obj in the command is a subject.

The command details are:

Add, subj, obj, priv
Execution of this command informs the analyzer that authorization triple ( subj, obj, priv) is valid, and the analyzer outputs a new line that echoes the input.
Query, subj, obj, priv
Execution of this command outputs a new line that echoes the input followed by a blank space and then:
- YES if there exists some sequence of zero or more (authorized) grant operations that makes authorization triple ( subj, obj, priv) valid.
- NO if no sequence of grant operations could make authorization triple ( subj, obj, priv) valid.

Leakage Analysis. Another concern that a security administrator might have is whether the contents of a specified object F1 that is a file could be transferred into a specified object F2 that is a file. Transfer of content from F1 to F2 is possible when (i) there is a subject S for which (S, F1, R) and (S, F2, W) are valid authorization triples or (ii) multiple subjects conspire and use additional files. Again, the answer to this potential flow question can be determined by analyzing the set of valid authorization triples. A command for requesting such an analysis is the following.

Leak, F1, F2
This command is syntactically correct provided F1 and F2 each is a name that has (i) not appeared in a previous command or (ii) has appeared and was used used to identify an object but not a subject. Execution of this command outputs a new line that echoes the input followed by a blank space and then
- YES if a sequence of zero or more (authorized) grant, read, and write operations by some set of subjects could cause the contents of file F1 to be transferred into file F2.
- NO if no such execution is possible.

Building the Analyzer

Implement the analyzer. It should allow subject names and other object names to be character strings up to 15 characters long (though supporting longer names is fine), and it should support analysis of systems involving at least 20 subjects and at least 20 files (though supporting larger numbers of subjects and files in fine). The analyzer will be invoked with two arguments: a Unix file name for a file containing the input, a Unix file name to which output will be written. This is an example of a trivial input file; your analyzer should generate an output file that looks like this.

You may develop your system anywhere. But we will grade your system by running it on the Linux hosts in UGCLab. So use a programming or scripting language available within this environment, and use Linux hosts in UGCLab to test what you will submit.

Submissions that do not run on the Linux hosts in UGCLab will receive no credit for executing correctly. Login to the UGCLab computers and test your system before you submit it, leaving plenty of time to make changes that may be needed.

What to submit. CMS will be set-up for submissions comprising the following elements.

design.pdf (10 pages max) documenting the design of your analyzer. Include justifications for the choice of key algorithms and data structures (with comparison of viable alternatives). Include a discussion of the asymptotic complexity (i.e. "big O notation") for each type of command. Also include UGCLab running times for your implementations of Add, Query, and Leak, along with a complete explanation of how these running times were measured and/or calculated.

An archive named analyzer.zip containing:
- Source code for your analyzer,
- Bash scripts setup.sh and analyze.sh for preparing and running your analyzer respectively. Thus, analyze.sh should expect two file names as arguments: one for input and one for output.
- README.txt that documents how these scripts install, configure, and run your analyzer. This document must be sufficiently clear that we can get your analyzer installed and running within a couple of minutes. Instructions that are unclear will be penalized.

Grading Criteria. Here is a rough breakdown of the relative importance of each piece of this project.

20% Quality of your write-up in design.pdf.
25% Asymptotic time and space efficiency of the implementation.
30% Robustness and overall quality of the code that was submitted.
15% Whether your system produces correct output on our test cases.
10% Actual execution time on our test scripts.