COMP 304B Object-Oriented Software Design - Assignment 3

Practical information

• This assignment is worth 9% of your final grade.
• Due date: Monday, February 22nd, 2010, before 23:59.
• The TA for this assignment is Chris Dragert. Ask your questions on WebCT or make an appointment to meet with Chris.
• Team size == 2 (pair programming) !
• Each team submits only one full solution. Use the index.html template provided on the assignments page. Use exactly this format to specify names and IDs of the team members. The other team member must submit a single index.html file containing only the coordinates of both team members. This will allow us to put in grades for both team members in WebCT. Beware: after the submission deadline there is no way of adding the other team member's index.html file!
• Your submission on WebCT must be in the form of a simple HTML file (index.html) with explicit references to all submitted files as well as inline inclusion of images. See the general assignments page for an index.html template.
• The submission medium is WebCT.
• To get feedback about the assignment workload, provide the number of hours you spent on this assignment.

Goals

This assignment will make you familiar with UML class diagrams, UML sequence diagrams, finite state automata, and regular expressions.
The grading scheme is as follows:

• Task 1 (33%):
  • Image & datafiles of your class diagram using BoUML (5%)
  • Image & datafiles of your sequence diagrams using BoUML (28%)
• Task 2 (67%):
  • Six regular expressions (30%)
  • Image & datafiles of your finite state automata using BoUML (20%)
  • Correct implementation of the finite state automata (12%)
  • Bug identification and correction (5%)

Upload all images, datafiles, source files and result files to WebCT and provide links to all of them from your index.html file.
Also include any additional information the corrector might require to correct the assignment.
Your submission should consist of two distinct directories: Task1, Task2.

Assignment

In this assignment, your task is to design and verify a communication protocol of a client-server system. The client part of the system has a user interface from which the user can input messages and send them. The client also receives messages from a chat room which it has subscribed to. A chat room is a server. It receives messages from its clients and broadcasts these messages to subscribed clients. A chat room can have 0 or more clients. A client can be connected to 0 or more chat rooms at any time. In your design, there will be no actual interaction with the human user. Rather, the clients simulate human operations (i.e., sending connection requests and sending messages) in a random way.
You are given an implementation along with the object-interaction trace (in a file) obtained from the existing implementation. You need to model first a set of Regular Expressions and then a set of FSAs, which you will subsequently be encoded to automatically verify whether the system implementation complies with the system (protocol) specification given in the requirements below (and modelled visually in Sequence Diagram form).

The following is a textual description of a simple protocol:

• There are 6 clients and 2 chat rooms in the system. The clients must be connected to a chat room before they can randomly send messages.
• The system works in a round-robin fashion. In each round, a random client will connect or send a message to a random chat room.
• Initially, the clients are not connected. They try to connect to a random chat room in each round. The requested chat room immediately receives the request (no network delays).
• A chat room can accept at most 3 clients. It accepts a connection request if and only if its capacity is not exceeded.
• The requesting client receives acceptance or rejection from the chat room immediately (no network delays).
• When connected, a client sends random messages to the chat room in each round. The chat room immediately receives the message. It processes the message and broadcasts it to all the other clients (except the sender) connected to it.
• The clients immediately receive the broadcast messages.
• For simplicity, disconnection and reconnection need not be modelled.

Hints:

• Adding an association class between Clients and Chat rooms which can record connections is not a bad idea.
• It could be easier to model dynamic system behaviour if you define two phases in a client's life: connecting and communicating.

Interaction behaviour to be verified (use cases):

1. When a client sends a connection request to a chat room, the chat room immediately responds by printing to the output.
2. On receiving a connection request, the chat room immediately makes a decision whether to accept the client or reject it.
3. When a chat room accepts a client, the client immediately receives the acceptance and dumps to the output.
4. When a chat room rejects a client, the client also immediately dumps the rejection.
5. When a client sends a message, the chat room immediately receives it and prints the message to the output.
6. When a chat room receives a message, it broadcasts it to all connected clients except the sender.
7. The sender cannot receive its own message after it sends it.

Task 1

Provide a design model of the above chat protocol.

1. Design the static structure in UML Class Diagrams of the described system in BoUML. You can base yourself on the already provided implementation found in chatprotocol.py. Remember that your design may have differences with the actual implementation: you should rely on the requirements exclusively. This task could have been automated through reverse engineering, but BoUML does not support Python reverse by default. For the operations, you only need to include their signature, not their body.
2. Design the dynamic interaction behaviour in UML Sequence Diagrams for each use cases in BoUML.

Task 2

Provide a verification model.

1. Write regular expressions (refer to the format of the given output trace) for verifying the above use cases. The regular expression for use case 1 is provided as an example:
   

   Regular expression pattern for rule 1:
   ##[^\n]*\n\(CL (\d+)\) RS (\d+)\.\n##[^\n]*\n\(CR \2\) RR \1\.\n
   
   The following output will match the above pattern (multiple lines!):
   ## (Client 2) A connection request is sent to chat room 1.
   (CL 2) RS 1.
   ## (Chat room 1) Received connection request from client 2.
   (CR 1) RR 2.
   

   Clarification: the above uses a Regular Expression notation commonly used in UNIX Regular Expressions (as used in the stream editor sed for example) which differs from the examples given in class. In addition to the slightly different notation, the expressive power of these Regular Expressions is also higher as it allows for memory of matched expressions making the patterns context dependent.
   • [eE] stands for e or E.
   • [a-z] stands for one of the characters in the range a to z.
   • ^ means "match at the beginning of a line/string".
   • $ means "match at the end of the line/string".
   • [^x] means not x, so ##[^\n]*\n matches a comment line: ## followed by 0 or more non-newline characters, followed by newline.
   • . matches any single character.
   • X? matches 0 or 1 repititions of X.
   • X* matches 0 or more repititions of X.
   • X+ matches 1 or more repititions of X.
   • \ is used to escape meta-characters such as (. If you want to match the character (, you need the pattern \(.
   • The ( and ) meta-characters are used to memorize a match for later use. They can be used around arbitrarily complex patterns. The first (\d+) in the above regular expression matches any non-empty sequence of digits (assuming d has been defined elsewhere as [0-9]). The matched pattern is memorized and can be referred to later by using \1. Following matched bracketed patterns are referred to by \2, \3, etc. Note that you will need to encode powerful features such as this one by adding appropriate actions (side-effects) to your automaton encoding the regular expression. This can easily be done by storing a matched pattern in a variable and later referring to it again.
   You are welcome to use different variant notations (such as the one used in the Python Regular Expression module) as long as you explain your notation.
    
2. Design a FSA which encodes the regular expressions of rules 2 and 7 ONLY for verification in BoUML. Again, this could have been automated, but BoUML does not support that.
3. Implement this FSA for verification in the provided code framework (see scanner.py);
4. Run this FSA implementation (which in turn implements the Regular Expressions which in turn encode the checking of interaction behaviour use cases which were modelled as Sequence Diagrams) on the given output trace to verify the specification. There is an intentional bug in the implementation (chatprotocol.py) which makes it fail to satisfy the system specification. You need to figure it out by verifying the output trace with your FSA implementation, and fix it (just one line).

WARNING: the language expressed in the regular expressions, the FSA, and the actual code of the scanner must be consistent. Small variations invalidate the process as this process can be entirely automated. Make sure that any modification you make on one model is reflected on the others!

Starting Point

• The program implementing the system: chatprotocol.py
• The output trace generated from the above program: output trace
  To make life easier, we use abbreviations to shorten the messages that you need to recognize in your RegExp/FSA. Here are the mappings:

  CL := Client
  CR := Chat room
  RS := A connection request is sent to chat room
  RR := Received connection request from client
  AC := Accepted client
  AB := Accepted by chat room
  RC := Rejected client
  RB := Rejected by chat room
  SY := Says
  RM := Received message from client
  SM := Sent message to all connected clients except client
  

  As you can see, any message in the output file which starts with "##" is some comments to make the output readable. You need to ignore these messages when you do verification.
• Programs used to implement FSA: the scanner is in scanner.py which requires an input stream class CharacterStream found in charstream.py.

Examples

Regular Expression patterns recognition

Sample BoUML Project