Question

For the DAC model discussed in Section 4.3, an alternative representation of the protection state is a directed graph. Each subject and each object in the protection state is represented by a node (a single node is used for an entity that is both subject and object). A directed line from a subject to an object indicates an access right, and the label on the link defines the access right.

a. Draw a directed graph that corresponds to the access matrix of Figure 4.3a.

b. Draw a directed graph that corresponds to the access matrix of Figure 4.4.

c. Is there a one-to-one correspondence between the directed graph representation and the access matrix representation? Explain.

Answer 1

Note: Refer the “Figure 4.3a” and “Figure 4.4” in the text book.

Access matrix:

Access matrix is a user authentication policy; it has a security model to protect the system.

• One dimension of the matrix contains an identified subject which may attempt the data access for the resource.

• Other dimension of the matrix lists the object which may be accessed.

Directed graph:

The directed graph is a type of graph; it is having a set of nodes which is connected by the edges.

• In the directed graph the edges have a direction.

a. Directed graph for Access matrix:

$14526-4-1P_1.jpg$

In the above directed graph “User A”, “User B”, and “User C” are the subjects and the “File1”, “File2”, and “File3” are the objects.

• “User A” having the Owner, Read, and Write permission for the “File1” and “File3”.

• “User B” having the Read permission for the “File1”, Owner, Read, Write permission for the “File2”, Write permission for the “File3” and Read permission for “File4”.

• “User C” having the Read, Write permission for the “File1”, Read permission for the “File2”, and Owner, Read, Write permission for “File4”.

b. Directed graph for Extended Access control matrix:

$14526-4-1P_2.jpg$

• In the above directed graph “S1”, “S2”, and “S3” are the subjects.

• The objects are following, “F1” and “F2” denotes the files, “P1” and “P2” denotes the processes, and “D1” and “D2” denotes the disk drives.

Subject “S1” is having control on itself.

• “S1” is having the owner permission on subject “S2” and “S3”.

• “S1” is having the read permission for file “F1” and read and owner permission for the file “F2”.

• “S1” is having the wakeup permission for the processes “P1” and “P2”.

• “S1” is having the seek permission on the disk drive “D1” and having the owner permission on the disk drive “D2”.

Subject “S2” is having control on itself.

• “S2” is having the write permission on file “F1” and execute permission on file “F2”.

• “S2” is having the owner permission on the disk drive “D1” and having the seek permission on the disk drive “D2”.

Subject “S3” is having control on itself.

• “S3” is having the write permission on file “F2”.

• “S3” is having the stop permission on the processes “P1”.

c.

One-to-one correspondence between the directed graph representation and the access matrix representation:

Yes, there is a one-to-one correspondence between the directed graph and access matrix representation.

Explanation:

Since the access matrix passes to all the respective edges from user vertex to file vertex in a directed graph. The users are represented with the one dimension and the files are in the other dimension of the matrix.

In the directed graph, the user vertices are at the top whereas the file vertices are specified at the bottom. If the access rights are granted from the user to a file, then the directed graph contains an edge from the vertex which means that the correspondence from subject to object.

Therefore, there is a one to one correspondence between the directed graph and access matrix.