# Homework 4 (FCS)

## Ex 1

Identify and describe the possible time-of-check time-of-use (TOCTOU) errors in
the following code snippet, and provide correction of the errors

# We are working under the assumption that the function is not atomic

int addMoneyOnDate(String sourceAccount, String destinationAccount,
Money amount, Date date)
{
    Date today = getCurrentDate();
    if (date.equals(today))
            if (currentUser.owns(sourceAccount))
                if (sourceAccount != destinationAccount) {
                    File *sourceFile = new File(sourceAccount);
                    File *destinationFile = new File(destinationAccount);
                   
                    if (balance(sourceFile) >= amount) {
                    
                    # interleaves here --> change balance(sourceFile)
                        debitByAmount(sourceFile, amount);
                        creditByAmount(destinationFile, amount);
                     
                }
            }

By definiton:

The software checks the state of a resource before using that resource, 
but the resource's state can change between the check and the use in 
a way that invalidates the results of the check. 
This can cause the software to perform invalid actions when 
the resource is in an unexpected state.

This weakness can be security-relevant when an attacker can influence 
the state of the resource between check and use. 
This can happen with shared resources such as 
files, memory, or even variables in multithreaded programs.

Source : https://cwe.mitre.org/data/definitions/367.html

By definition, the state of resource, which in our case is the `balance(sourceFile)`, can be changed if the attacker interleaves before the `debitByAmount(sourceFile)` is run. Changing this value will cause the function to invalidly run since the initial check will no longer be valid.

An example can be seen in the following case:

Let `balance(sourceFile)` = 10,000 and `amount` = 9000.

At the first checkin the line, `if (balance(sourceFile) >= amount)`, it is completely valid which makes the program continue on as the if statement is regarded as `True`. However, between the if statement being `True` and the function `debitByAmount(sourceFile, amount);`, say there is an attacker which interleaves and changes the value of `balance(sourceFile)` to 5,000. This creates a state where the result of the initial if statement to become invalid and causes the function to perform an invalid action as the ``balance(sourceFile)`` is now in an unexpected state.

To fix the issue, It is necessary to make the function atomic such that it is either wholely executed or not executed at all. This negates the possibility of interleaving and changing the states of resources during the execution of the program.

## Ex 2

a)
Original rules followed by the philosophers:

•	think until the left fork is available; when it is, pick it up;
•	think until the right fork is available; when it is, pick it up;
•	when both forks are held, eat for a fixed amount of time;
•	then release both forks
•	repeat from the beginning.

To solve the deadlock problem, each fork must first be assigned an integer from 1-N (to simulate priority) such that the lower number will be prioritised to be picked up first and the higher number will be prioritised to be picked up later. This will ensure the highest numbered fork will be available for the philosopher if they follow the following modified rules:

•	think until the **lower numbered** fork is available; when it is, pick it up;
•	think until the **higher numbered** fork is available; when it is, pick it up;
•	when both forks are held, eat for a fixed amount of time;
•	then release both forks
•	repeat from the beginning.

b)


Sequence 1 : Plato (P1), Socrates(P2), Camus (P3)

State, P1, P2, P3
0, Thinking, Thinking, Thinking
1, Fork 1 Pick up, Thinking (cannot pick up Fork 1), Picks up fork 2
2, Fork 3 Pick up, Thinking (cannot pick up Fork 1), Thinking (cannot pick up Fork 3)
3, **Eats spaghetti**, Thinking (cannot pick up Fork 1), Thinking (cannot pick up Fork 3)
4, Fork 1 Put Down, Fork 1 Pick up, Thinking (cannot pick up fork 3)
5, Fork 3 Put Down, Thinking (cannot pick up fork 2), Fork 3 Pick Up
6, Thinking , Thinking (cannot pick up fork 2), **Eats spaghetti**
7, Thinking (cannot pick up fork 1), Thinking (cannot pick up fork 2), Fork 2 Put down
8, Thinking (cannot pick up fork 1), Fork 2 Pick up, Fork 3 put down
9, Thinking (cannot pick up fork 1), **Eats spaghetti**, Thinking

Sequence 2 : Camus (P3), Socrates(P2), Plato (P1)

State, P1, P2, P3
0, Thinking, Thinking, Thinking
1, Thinking (cannot pick up fork 1),Picks up Fork 1 ,Picks up Fork 2
2, Thinking (cannot pick up fork 1), Thinking (cannot pick up fork 2),Picks up Fork 3
3, Thinking (cannot pick up fork 1), Thinking (cannot pick up fork 2), **Eats spaghetti**
4, Thinking (cannot pick up fork 1), Picks up fork 2, Puts down Fork 2
5, Thinking (cannot pick up fork 1),**Eats spaghetti**, Puts down Fork 3
6, Picks up Fork 1,Puts down Fork 1, Thinking
7, Picks up Fork 3, Puts down Fork 2, Thinking (cannot pick up fork 2)
8, **Eats spaghetti**, Thinking, Picks up Fork 2

## Ex 3

a)

No deadlock can occur since one of the 2 processes can always run to completion.

b)

All 3 processes make their first acquisition, (X acquires A, Y, acquires B, Z acquires C) then hang waiting for a resource that will never become available since each of the processes will waiting to acquire their respective next resource (X will wait to acquire B, Y will wait to acquire C, Z will wait to acquire A).

c)

To fully avoid deadlock, we can change Z such that it acquires A first then C. So the algorithm becomes:

• Process X acquires A, then B, uses both and then releases both.
• Process Y acquires B, then C, uses both and then releases both.
• Process Z acquires A, then C, uses both and then releases both.

## Ex 4

$U = 2; V = 1$


a)

>P1 --> U = 1; V = 2
>P1 --> U = 0; V = 3

2 C's at max because only for Process 1 there is a call to `wait(U)` and `type(C)` operations. No more resources will be allocated to process 1 afterwards since there is no `signal(U)` operation anywhere else.

b)

>P1 --> U = 1; V = 2
>P1 --> U = 0; V = 3

>P2 --> Effectively results in the same resources available since V is waited and signalled.

>P3 --> First D results in V = 2;
>P3 --> Second D results in V = 1;
>P3 --> Third D results in V = 0;

Only 3 D's will be printed when the execution halts. Process 1 can only be executed at max twice resulting in $max\{V\} = 3$ and since Process 2 effectively does not result in a change of total resources, Process 3 can only be run 3 times during the course of the execution. Once both Process 1 and Process 3 finishes execution, it will then halt since there are no more resources to be distributed.

c)

Is CCDDABD a possible output sequence when this set of processes runs? Why?

Sequences, Process , Resource Allocation, Accumulated Output
0,Initial, U = 2 | V= 1, None
1,Process 1, U = 1 | V = 2, C
2,Process 1, U = 0 | V = 3, CC
3,Process 3, U = 0 | V = 2, CCD
4,Process 3, U = 0 | V = 1, CCDD
5,Process 2, U = 0 | V = 1, CCDDAB
6,Process 3, U = 0 | V = 0, CCDDABD

Yes it is a possible output for the sequence because it still adheres to the defined semaphore limits. Process 1 can only be run at a maximum of 2 times and Process 3 can only be run at a maximum 3 times, and Process 2, while there is still semaphore V available, can be run as many times as necessary.