CS5430 Project: Access Control Analysis (Fall 2021)

Due: November 23 at 5:00pm. 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 a set of files as well as all subjects.

Authorization triple ( S, O, p ) signifies that subject S is allowed to perform any operation on object O for which privilege p is required. At any time, the operations that the system allows to be executed are described by the set of valid authorization triples. This set 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 T.

• ( 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', T ) authorizes subject S to invoke a take 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 there already exists a valid authorization triple ( S', O, p ).

Privilege Analysis. A security administrator could be concerned about whether ( S, O, p) already is valid or could become valid because take operations were executed by some subjects. The answer to this safety question can be determined by using 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 of each command is detailed below. The syntax of 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 has become valid; query ascertains whether an authorization triple is already valid or could become valid by some series of take 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 T, as appropriate depending on whether obj in the command is a subject.

• 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) take operations that would make authorization triple ( subj, obj, priv) valid.
  • NO if no sequence of take operations could make authorization triple ( subj, obj, priv) valid.

Building the Analyzer

Implement the analyzer. It should should support analysis of systems involving at least 40 subjects and at least 40 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 and Query, along with a complete explanation of how these running times were measured and/or calculated.
• tests.txt (30 pages max) giving one or more test scripts that you have used to get assurance in your implementation. Comments interspersed with the commands in the script should explain what features or functionality of your analyzer is being tested by that part of the script.

• 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.
• 10% Completeness of test script and quality of accompanying explanation.
• 15% 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.