CS5430 Project: Access Control Analysis (Fall 2022)

Due Dates:

• Phase 1: Due November 11 at 5:00pm.
• Phase 2: Due November 21 at 5:00pm.

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.

• (A,B) ∈ F iff member A is a friend of member B and, therefore, A can read any posting that has been made by B.
• (A,B) ∈ BF iff individual A is a best friend of member B and, therefore, A can read any posting that B can read.

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.

• AddF, M1, M2
  Execution of this command informs the analyzer that ( M1 , M2 ) ∈ F now holds for members M1 and M2. If ( M1 , M2 ) ∈ F holds just before the command is invoked than no change is made to F. Either way, the analyzer outputs a new line that echoes the input.
• AddBF, M1, M2
  Execution of this command informs the analyzer that ( M1 , M2 ) ∈ BF now holds for members M1 and M2. If ( M1 , M2 ) ∈ BF holds just before the command is invoked than no change is made to BF. Either way, the analyzer outputs a new line that echoes the input.
• RemoveF, M1, M2
  Execution of this command informs the analyzer that ( M1 , M2 ) ∉ F now holds for members M1 and M2. If ( M1 , M2 ) ∉ F holds just before the command is invoked than no change is made to F. Either way, the analyzer outputs a new line that echoes the input.
• RemoveBF, M1, M2
  Execution of this command informs the analyzer that ( M1 , M2 ) ∉ BF now holds for members M1 and M2. If ( M1 , M2 ) ∉ BF holds just before the command is invoked than no change is made to BF. Either way, the analyzer outputs a new line that echoes the input.
• Query, M1, M2
  Execution of this command outputs a new line that echoes the input followed by a blank space and then:
  • YES if a posting by member M1 can be read by member M2, given the existing F and BF relations.
  • NO if a posting by member M1 cannot be read by individual M2, given the existing F and BF relations.

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:

• Source code for your phase 1,
• bash script setup.sh to compile and install your system.
• bash script phase1.sh to run your system on data, so this script should expect two file names as arguments: one for input and one for output.
• README.txt that documents how we should use these scripts install, configure, and run your phase 1. This document must be sufficiently clear that we can get your submission installed and running within a couple of minutes. Instructions that are unclear will be penalized.

• 75% Can a grader who reads your README.txt install and run your system on the UGCLab computers.
• 25% Does the system correctly handle input files that contain only comments.

Phase2 (due 11/21 at 5pm)

• 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 a test script 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 script setup.sh to compile and install your system.
  • bash script phase2.sh to run your system on data, so this script should expect two file names as arguments: one for input and one for output.
  • README.txt that documents how we should use 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.