CS5430 Project: Access Control Analysis (Fall 2022)

General Instructions. You are strongly encouraged to work as part of a group of 2 or 3 students. Match-making assistance will be provided for those seeking help in forming a group.

Due Dates:

Submit your solution using CMS.

A social network comprises a community of members who (i) post new items and (ii) read previously posted items. In our SN social network, members have names that are strings up to 15 characters long and are constructed from letters (upper and lower case) and digits.

In SN, only certain posted items can be read by a member. Whether a previously posted items can be read by a member is based on two relations---F and BF. Each relation defines a set of pairs of members.

Note that F and BF are not necessarily reflexive, symmetric, or transitive. So, for example, (A,A) ∈ F does not necessarily hold for a member A, having (A,B) ∈ F hold does not necessarily imply that (B,A) ∈ F holds, and having both (A,B) ∈ F and (B,C) ∈ F hold does not necessarily imply that (A,C) ∈ F holds. Also, with F not necessarily reflexive, initially -- that is, by default -- a member is not able to read its own posts.

Propagation Analysis. SN management has learned that members desire a propagation analyzer so that a member who is going to post an item can first determine which other members would be able to read that item at the time the item is being posted.

The input to the propagation analyzer will be a sequence of lines. Each line contains either a single syntactically correct command or a comment. The syntax of each type of command is detailed below. The syntax of comments allows any text that is not a syntactically correct command. Any sequence of comments and commands is allowed.

Input lines are processed in the order that they are read. The processing of a command is explained below. To process a comment, that comment is simply copied to the output.

Commands facilitate performing propagation analysis in the context of evolving F and BF relations. Initially, F and BF are empty. As time passes, these relations evolve as members become friends, become best friends, cease to be friends, or cease to be best friends. We model the evolution of F and BF by giving a sequence of commands. The command syntax and operational interpretations are given below. Note that AddF and AddBF are the only commands that cause a new element to be added to relations F and BF; these commands cause add only the specified element.

Building the Analyzer

Implement the propagation analyzer. It should should support analysis of systems involving up to 80 members. 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 an 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 -- to avoid an unpleasant surprise -- 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.

Phase 1 (due 11/11 at 5pm)

Phase 1 requires you to provide a program for correctly handling comments. So, for an input file that contains only comments your system will generate an output file where each input line has been copied. Trivial? Yes, but phase 1 forces you to confront all of the details associated with writing a system that (i) executes on the UGCLab computers and (ii) we will be able to install and run on the UGCLab computers.

What to submit. Submit to CMS an archive named phase1.zip containing:

Grading Criteria.

Phase2 (due 11/21 at 5pm)

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

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