---
tags: P&O-CW-2022-2023
author: Dirk Nuyens, Justus Fasse, Tim Van hamme, Maarten Volkaerts, Jonathan Oostvogels
---

# P&O CW 2022-2023 1e semester

:::info
Imagine receiving the following message from a friend:
> ==[FriendlyFriend:]== Forgot root password, could you plse quickly share it, it's urgent! Thanks you are a god!

(You scratch your head...)

Or, the following message from your sibling:
> ==[LittleSibby:]== Heyyy how was your birthday yesterday?

(Think about this one before you start bragging and confessing...)

Wouldn't it be great if you could somehow get a little bit of trust in the first message actually indeed being from your friend, and not some hacker; and the second message really being from your sibling instead of your parent who accidentally got hold of an unlocked phone or computer?
:::

## Background story

You all recently joined a new dynamic startup that wants to innovate in the space of messenger apps. Your founder has inherited a fortune but does not possess the technical know-how to realize their dream. In order to satisfy the venture capitalists that they managed to rope into this project, a MVP (minimum viable product), should be presented by late spring of next year.
This startup values features over security and privacy because the founder believes users to be more convinced by innovative, well-integrated, features that are directly visible to the user.

Your first task will be to implement a barebones chat server which will serve as the testbed for new and exciting features.

As noted, the founder is not particularly security-conscious and as a result often forgets to lock their screen when leaving their desk. It has become a habit of their colleagues and friends to use these opportunities to send embarrassing messages.

Thus the first innovative feature added to your chat client will be a keystroke recognition service that, after a learning phase, is meant to recognize the typing of its users and lock itself when detecting that most likely somebody else is currently typing. Of course, a passphrase may be used to unlock the chat client again.

## Step 0: Meet your team

- We have assigned you to a team.
- We will assign your team to a spot in the lab.
- Always use the same spot in the lab with your team.

## Step 1: Set up the repository

The source code of your project will be on the KU Leuven gitlab server with the same setup as in the past weeks: other teams will be able to see your source code / merge requests / issues / branches / ...

You have been invited to a repo together with your fellow group members.

You can use the repositories from the past weeks as further examples. You can check the [First steps with Node, JavaScript and TypeScript](/4diV-P1vQiuJnjuSXY_obw) tutorial if needed.

Do not check in the `.vscode` directory. This was only to make for an easy start in setting up VS Code for the [An illustrative story of a development team](/Uxwzfa4vSj-UKafTQKmMAQ) tutorial.

The other team members clone the repository and everybody sets up their editor correctly as in the [Welcome to the team!](/bc-4mICFRS2ns-y60Sje8Q) note. This means that you have to **enable format-on-save**.

For the **source code** of your project we have the following rules from the [Assignment commons](https://wms.cs.kuleuven.be/cs/english/study/assignment-commons): ES-GW-TP-TS-PP-VP:
- ES: External Sources
- GW: Group Work
- TP: Talk Peers
- TS: Talk Strangers
- PP: Pass Peers
- VP: View Peers

To avoid any confusion: you can look at code from other teams, have it on your laptop, run it, test it, smell it, etc... but you cannot share it with people outside of the course.

When you find code on the internet that helped you solve a particular problem, then attribute the source in your source files and provide a URL. Pay attention to fair use. Respect copyright clauses.

Of course, it is not allowed to copy code from other teams in the solution of your own team. If the code from another team gave you a hint on how to solve your problem then you can try to implement a similar solution and you put an attribution in your source files that you got (part of) the idea from some other team. There is no shame in doing this, it shows you have the style it takes...

You are allowed to use npm packages implementing certain needed functionalities. Always check the licenses of those packages. Keep a file `LICENSES.md` (plural, as `LICENSE.md` would be the license for your package) in your repository which lists the npm packages and their software license (just the type of the license, not the full text), also if you use e.g. a dictionary file, or other external files or code, then list the license there. This is only needed for npm packages which are needed for the final application, so not for the development packages. I.e., when you have to implement the "about" button in your app, you will need to list all packages which are being used by your app according to their license.

If you want to use or adjust an implementation that you found online but you are not sure if we want you to actually implement it yourself, then please ask! If you use verbatim or modified code, put an attribution in your source files, add a URL, and add the type of the license to the `LICENSES.md` file. Also write down in the source files what you modified.

## Step 2: Have a team meeting

Read through the rest of the assignment and then have a first team meeting. **Have a team meeting each Monday at the start of the session.**

**NOTE** The idea is that you subdivide the assignment in **small and independent tasks that are testable** and that you agree with your team what the minimal bare bones unit tests are for the tasks. Similar as in the story book example. If you notice that tasks are too big or not well defined (this will happen! certainly in the beginning) then you will have to reiterate with your team until you find the right balance!

You will not be able to define all features and all corresponding tasks in the first team meeting. Keep it focused. Only mention those things you want to deal with in the next week(s). You have to read through the assignment and figure out which are the most important ones to do first.

Start a **private hackmd page for your team** (share it by using the URL, do **not** push *publish*), also share the URL with the TA that follows your team. You are free to discuss with other teams, and anybody else, but **do not share your team notes with other teams**.

You can use your private hackmd team page to link to other hackmd pages with notes from your team. Make a heading "Monday team meetings" and you can then make a list there to a note for every Monday meeting.

Your team should use these notes to keep track of todo lists and document features and tasks as in the [story book example](/Uxwzfa4vSj-UKafTQKmMAQ). It is okay to put a lot of time in this in the beginning. Later you will benefit from the experience.

Hints: you can make nice diagrams and easily include pictures (just drag and drop). Check out this [hackmd features](https://hackmd.io/s/features) note. Click on "Check the source of this note" to see how to do these things.

For the **hackmd notes** that you share with your team we have more restricted rules from the [Assignment commons](https://wms.cs.kuleuven.be/cs/english/study/assignment-commons) than for the source code: ES-GW-TP-TS-**NPP**-**NVP**:
- ES: External Sources
- GW: Group Work
- TP: Talk Peers
- TS: Talk Strangers
- **NPP: No Pass Peers**
- **NVP: No View Peers**

## Description of the app

We build a basic terminal-based chat application consisting of a central server and several chat clients. (In the second semester we will move to a web based chat client.)

**Target:** By the end of the semester we expect at least the chat server to be demonstrable with a couple of running chat clients and a visual indication of the keystroke fingerprinting. Our focus is on working together as a team using the ideas you learned from the story book. **Take responsibility for your code, convince the others (and yourself) that it works correctly, give feedback to your team mates on their code.**

The assignment contains more features than you need for this bare bone target. Feel free to advance as far as you want, and to even add more features...

### Basic chat application

#### Usage of websockets

We will be using the `ws` package to have WebSockets in Node.js. ([WebSockets](https://developer.mozilla.org/en-US/docs/Web/API/WebSocket) are standard available in your browser but not in Node.js.)

WebSocket connections exist as `ws://` and `wss://` protocols, similar to `http://` and `https://`. In first instance it is sufficient to get a `ws://` version running.

Resources:
- https://github.com/websockets/ws
- https://developer.mozilla.org/en-US/docs/Web/API/WebSocket
- https://ably.com/blog/web-app-websockets-nodejs

#### Runtime typechecking

It is sometimes convenient to send JSON messages over the WebSocket connection. You might be tempted to send e.g.

{ "command": "ChannelJoin", "userId": "@0a89c22c", "channelId": "#a00d200b" }

and on the other side accept this as a string and then run this through `JSON.parse()` and hope to be able to access the `.command` property, and then the `.nickname` property. However, you will quickly notice that TypeScript will consider the return type to be `any`.

The only safe way out is to actually have runtime code which will check that what you receive is indeed of the correct type and then also explain this to the TypeScript compiler.

If you need this then you should use the `zod` npm package.

#### The chat server

The simplest architecture for this task involves a central server that coordinates the different chat clients. Naturally, the chat server will have to support multiple chats at the same time.

In first instance the chat server can just be a server where clients connect and can send messages to and all the other clients receive all these messages.

Of course we want to identify users with nicknames. You can make a decision if they should be unique or not, but every user must be uniquely defined by a `userId`. We suggest to take hexadecimal strings starting with an `@`. For channels we have the same concept and they start with `#`.

#### The chat client

The chat client's job is to interface with the user and hide as much of the technical details of how to interact with the chat server from the user.

You will have to investigate how to have the user interact with the chat client through the terminal. Be careful not to tie this too deep into your chat client.

To be able to analyze keystroke fingerprinting there will have to be a way to save history of chats. In this way you could analyze the history of other users you know and also of yourself.

#### The protocol

You will need to come up with a protocol such that the server and client can talk to each other. At the same time you should abstract away implementation details of either where possible.

E.g. if somebody joins a chat channel we could send a message with the following interface:

interface ChannelJoin {
  userId: string,
  channelId: string
}

and the server could respond with

interface ChannelJoined {
  userId: string,
  channelId: string
}

Note that this is a form of stateless communication (which simplifies a lot of the logic).
Of course, the server should actually verify that the `userId` corresponds to the connected client and that the `channelId` exists.

Client -> Server: ChannelJoin(chan, me)
Server -> Client: ChannelJoined(chan, me)
Server --> Other clients: ChannelJoined(chan, me)

Setting up a connection could be done like:

interface Connect {
  nickName: string
}

and the server can respond with a generated `userId`:

interface Connected {
  nickName: string,
  userId: string
}

or

interface ConnectionRefused {
  nickName: string,
  reason: string
}

The reason to have ids and names is to make it easy to rename a user or a channel.

#### Mocking

You will see that testing becomes quickly very complicated since most of our implementation will be almost directly using the underlying `WebSocket` infrastructure. To decouple this we will provide a `MockWebSocket` and a `MockWebSocketServer`.

### Some initial features

#### Keystroke fingerprinting

We want to avoid somebody hijacking a chat session and impersonating the original owner. For this we will use keystroke analysis of messages (based on timings of n-grams) and compare those with those of previously recorded messages to hopefully detect the impostor.

To be able to do this we will first need to build a database for the user(s) that we want to compare to. We call this the *enrollment* phase. This is just some initial phase in which we collect messages with timings from that user.

Afterwards we can interrogate the database using a new message and compare to the known user(s). We can distinguish the following use cases:
1. (Classification) Compare some new input from one of the known users to the existing profiles. The highest ranked is hopefully the user typing. (We are assuming the input comes from a user which is known to the database, if not, then this is certainly not true, hence the next use case...)
2. (Identification) To detect if the new input is "similar enough" to one of the known users in the database we could use a threshold. Determining such a threshold might be non-trivial.
3. (Authentication) Of course, if we know who is supposed to be on the other side of the chat channel then we only need to compare to one existing user. Also here we need to decide if the new input is similar enough and so need to decide on a good threshold.

The keystroke analysis will use the timing of the keystrokes (in ms). E.g. when the user types "hello" we will register

[['h', 0], ['e', 90], ['l', 140], ['l', 190], ['o', 220]]

assuming that the "e" arrived 90 ms after the "h" and so on.

From this input data we can calculate the time needed from the start of an n-gram to the end of that n-gram. E.g. if considering the 2-grams for the above example we obtain

| 2-gram | start | end | delta |
| ------ | ----- | ---- | ----- |
| `he` | 0 | 90 | 90 |
| `el` | 90 | 140 | 50 |
| `ll` | 140 | 190 | 50 |
| `lo` | 190 | 220 | 30 |

If the same n-gram occurs multiple times we average the delta time and then we sort the n-grams on delta:

[ 'lo', 'el', 'll', 'he' ]

We compare to timings from existing messages and only use those n-grams from those existing messages which also occur in the new message. We then also sort those n-grams according to the delta time. We should now have a second vector of exactly the same length, but the order could be a permutation of the first one, e.g.

[ 'lo', 'll', 'el', 'he' ]

In terms of the order of the elements from the first vector this permutation looks like

[ 1, 3, 2, 4 ]

We can now substract elementwise the expected order `[ 1, 2, 3, 4 ]` and take absolute values to get how much each n-gram has to be moved in this comparison:

[ 0, 1, 1, 0 ]

Summing these numbers would give a measure of the movement. Dividing this by the maximum possible value then normalizes this measure. (See the reference at the end of this section: look for the "R" measure which measures the *disorder*; the "R" stands for relative as we are not concerned with the absolute values of the timings.) In our case the normalized value for this example comparison would be $2/(4^2/2) = 1/4$.

One could now compare with all previous text samples from a user, or from different users, and pick the best match. Measures using different $n$'s for the n-grams could be combined; e.g. a combination of 2-grams and 3-grams. (See the reference paper [GC2005].)

Note that to start implementing this "extensive" feature it is probably best to start with some watered down versions first. Your tasks would include also getting some samples from users. We are not so interested in keystroke analysis which is working impressively well, we are more interested in a simple system which was implemented in a way that the team trusts the code.

- [GC2005] Gunetti, Daniele, and Claudia Picardi. Keystroke analysis of free text. *ACM Transactions on Information and System Security*, 8(3):312-347, 2005. https://dl.acm.org/doi/pdf/10.1145/1085126.1085129

#### Word suggestions

Based on a corpus by calculating probabilities of word-n-grams.

We want the chat application to assist users by offering to automatically complete the word they might want to type, while they are typing it. To offer such completions, the application should continuously inspect the words near the one that is currently being typed, as well as the characters of the latter word that have been typed so far.

Offering completions requires the application to have an understanding of how often specific sequences of words occur in practice. For this purpose, the application will learn how to estimate the likelihood with which a given word follows the preceding n-1 words from a larger body of text.

#### Reverse dictionary lookup

Normally, a dictionary lookup consists of searching for the description of a specified word (e.g. we look up the word dog to find four-legged pet). In a reverse dictionary search, the opposite is true: we want to find words that satisfy a given description. The software created during the Storybook assignment can act as a good starting point for this task.

Example 1: Imagine you forgot the word for "elephant", how would you describe it to someone as to be understood. Perhaps, "big animal with long nose" (unfortunately we have forgotten the word for "snout" as well!). In that case the reverse dictionary ought to suggest words that roughly correspond to that query, including the word elephant.

Example 2: car with four doors -> sedan

### Privacy concerns

Analyzing keystroke dynamics, as done here for fingerprinting, is part of a much larger field called (behavioral) biometrics. It bears many of the same advantages and risks associated with the collection and treatment of other biometric features. Crucially, users are unlikely to expect their keystrokes to be logged, especially because this is currently an uncommon feature.
You are expected to understand what data you are collecting and how you are using it and for what purpose. This information should be transparent to the user.