Can share algorithm

Show that there is an algorithm of complexity O(|V| + |E|) that tests the predicate can•share, where V is the set of vertices and E the set of edges, in G0. Prove this by showing one such algorithm.

This question is from the book: Computer Security: Art and Science by Matt Bishop. I Found this question quite interesting (especially the algorithm part), hence the post.

---

According to theorem 3-10, The predicate can•share(a, x, y, G0) is true if and only if there is an edge from x to y in G0 labeled a, or if the following hold simultaneously:

a. There is a vertex s in G0 with an s-to-y edge labeled a.
b. There exists a subject vertex x' such that x' = x or x' initially spans to x.
c. There exists a subject vertex s' such that s' = s or s' terminally spans to s
d. There exist islands I1, …, In such that x' belongs to I1, s' belongs to In, and there is a bridge from Ij to Ij+1

Algorithm:

(Abstraction level 1)

The idea for the algorithm is as follows:

1. If node x or y does not exist, return false.
2. If there is an edge ‘a’ from x to y, return true.
3. Check conditions a, b, c, d of theorem 3-10, if they hold simultaneously, return true else return false.

(Abstraction level 2)

Step 3 from above can be elaborated as follows:

1. Start from node x.
2. Try to find x' satisfying condition B of theorem 3-10. If no, return false. If yes, for every such x', loop step 3.
3. Try to find s' satisfying condition D of theorem 3-10. (We don’t return false here as there might be some other x' for which step 3 might be true, so we check exhaustively; i.e., since we are in a loop right now). If yes, for every such s', loop step 4.
4. Try to find s satisfying condition C of theorem 3-10. If yes, for every such s, loop step 5.
5. If there is an edge ‘a’ from s to y, return true. (Checking condition A of theorem 3-10)
6. Return false (If it reached this step, it means that step 5 failed to return true)

The above sequence of actions can be represented as:

1. Start from node x.
2. Algorithm Step2(x)
3. Algorithm Step3(x')
4. Algorithm Step4(s')
5. If there is an edge ‘a’ from s to y, return true. (Checking condition A of theorem 3-10)
6. Return false (If it reached this step, it means that step 5 failed to return true)

(Abstraction level 3)

Algorithm Step2(X)

The graph data structure is such that every node has an associated data ‘visited’, which is Boolean in nature. This data is used so that the node is not re-analyzed again. We need to find all x', such that, x' is a subject and x' has a T*G path to x. Two intermediate algorithms used within this algorithm, they are:

Algo1(X) (Finds the neighborhood node of X such that it has a grant right over X)

1. For each neighboring vertex V of X such that V->visited = false (for loop), execute steps 2, 3
2. Make V->visited = true
3. If( V -> X has a grant), call Algo2(V)

Algo2(V) (Recursively checks for T* paths and calls step3 whenever appropriate)

1. For each neighboring vertex x' of V, if x' -> V has a Take right and x' -> visited = false. Execute steps 2, 3, 5
2. x' -> visited = true
3. If x' is a subject vertex, execute step 4
4. Call algorithm Step3(x')
5. Call algorithm Algo2(x') (This call gives us the desired effect to check T* paths)

The Step2(X) algorithm is defined as:

1. Call algorithm Algo1(X)

Algorithm Step3(X')

//Check for paths satisfying T* ->, T* <-, T* -> G <- T* <-, T* -> G -> T* <- Algo3(X') (Checks for T* <- paths)

1. For each neighboring vertex n of x', if n <- x' has a Take right and n -> visited = false. Execute steps 2, 3, 5
2. n -> visited = true
3. If n is a subject vertex, execute step 4
4. Call algorithm Step4(n)
5. Call algorithm Algo3(x') (This call gives us the desired effect to check T* paths)

Algo4(X') (Handles remaining cases)

For each neighboring vertex n of x', if n <- x' has a Take right and n -> visited = false. Execute steps 2, 3, 8

1. n -> visited = true
2. If n is a subject vertex, execute block 4, 5, 6, 7
3. Call algorithm Step4(n)
4. For each neighboring vertex n' of n, if n' -> n or n' <- n has a Grant right and n' -> visited = false. Execute step 6, 7
5. n' -> visited = true
6. Call Algo3(n') (Tries to terminate with subject vertex having T* ->)
7. Call algorithm Algo4(x') (Handles recursive paths with similar signature)

The Step3(X') algorithm is defined as:

1. Call algorithm Algo3(X')
2. Call algorithm Algo4(X')

Algorithm Step4(S)

//Try to find s' such that s' -> s has T* path.

1. Call algorithm Algo2(S) used in Step2, modify step 3 of Algo2 as ‘Call Step 5’

---

Complexity Analysis:

From abstraction level 1, we conclude that the running time of the algorithm is the running time of step 3 as steps 1, 2 take O(1) time (Since only a lookup operation needs to be performed in the adjacency matrix)

From abstraction level 2, we conclude that the complexity is determined by the sequence of actions in steps 2, 3, 4, 5.

By observing steps 2, 3, 4, 5; in the worst case, all the edges and the vertices of the graph will be explored. (This will happen when all nodes connected to node n initially spans to it, making step 2 call step 3. Similarly, step 3, 4, 5 may explore all nodes before step 6 is reached).

Therefore, worst case running time for the algorithm is O(|V| + |E|)
The best case running time is O(1) (If the algorithm concludes with step 1 or 2 in abstraction level 1)