COMP 304B Object-Oriented Software Design - Assignment 3

Practical information


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:

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.



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:


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 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. 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;
  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 ( 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


Regular Expression patterns recognition

Sample BoUML Project

Eugene Syriani Winter Term 2010.