CSI 2310/5006 – Data Structures
Project 1 (Prj1)
Connects to the following learning outcomes:
Implement / use linked lists, binary trees, stacks, queues, priority queues.
Points:
6 points. Contributes to the assessment item “homework”, which has a total weight of 30% of the
grade.
Due date:
October 10th, at 23:59:59 PM.
Description
A network intrusion detection system (NIDS) analyzes all incoming and outgoing traffic for signs of
intrusion. More specifically, a NIDS extracts the payload part of each network packet, and compares it
with rules that are called vulnerability signatures. The payload is the actual data part of a network
packet. Attackers have adapted their exploit techniques to try to evade the various checks that are
performed by a NIDS.
Attackers split the attack data into multiple network packets. That way, a single packet payload does
not match any vulnerability signatures. On the other hand, defenders have improved the code of NIDS
by reassembling fragmented network packets before analyzing them, so that their payloads are merged
and analyzed as a single piece of data.
NIDS uses a linked list to store network packets in ascending order based on TCP sequence numbers.
When a new network packet arrives, the NIDS needs to insert it in the linked list at a position that does
not break the ascending order of the nodes. Furthermore, if the linked list already contains a node, i.e. a
packet, that has the same TCP sequence number as the new packet, then the NIDS does the following:
1) Removes the existing node from the linked list. 2) Extracts its payload and appends it to the payload of the new packet. 3) Inserts the revised new packet in the linked list at the appropriate position.
In this project, we do not implement step 2 given that it is not pertinent to linked lists.
This project consists of NIDS code written in Java that organizes network packets into a linked list in
ascending order and without duplicates. This project description is accompanied by a zip archive named
Code.zip, which contains two Java files, namely intrusionDetectorClass.java and IntNode.java.
Students are required to implement the methods of the IntNode class. The intrusionDetectorClass
simply uses the methods of the IntNode class to create and maintain the linked list of network packets.
Students can verify the correctness of their IntNode class by comparing their output with the following
output:
Prj1 is running. The (sequence number, data) pairs in the linked list are: (13,230185386) Running removeDuplicate() on target 13 The linked list is empty. Running addNodeInOrder() on target 13 and data 308329763 The (sequence number, data) pairs in the linked list are: (13,308329763) Running removeDuplicate() on target 14 The (sequence number, data) pairs in the linked list are: (13,308329763) Running addNodeInOrder() on target 14 and data 248041794 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,248041794) Running removeDuplicate() on target 14 The (sequence number, data) pairs in the linked list are: (13,308329763) Running addNodeInOrder() on target 14 and data 295106305 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) Running removeDuplicate() on target 15 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) Running addNodeInOrder() on target 15 and data 325615905 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) Running removeDuplicate() on target 16 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) Running addNodeInOrder() on target 16 and data 652976466 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) (16,652976466)
Running removeDuplicate() on target 17 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) (16,652976466) Running addNodeInOrder() on target 17 and data 847897267 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) (16,652976466) (17,847897267) Running removeDuplicate() on target 17 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) (16,652976466) Running addNodeInOrder() on target 17 and data 927847798 The (sequence number, data) pairs in the linked list are: (13,308329763) (14,295106305) (15,325615905) (16,652976466) (17,927847798) End of run.
Deliverable
A fully implemented IntNode class, which students shall submit on Moodle.
Grading Rubric:
The following rubric details how your submission will be graded:
Accomplishment Points
The NIDS correctly creates and maintains a
linked list of network packets in ascending
order and without duplicates.
6
The NIDS correctly creates and maintains a
linked list of network packets in ascending
order, but is unable to remove duplicates.
4
The NIDS creates and maintains a linked
list of network packets, but is unable to
keep nodes in ascending order and remove
duplicates.
2
The NIDS is unable to create and maintain a
linked list of network packets in any way.
0