Describe each of the following four kinds of access control mechanisms in terms of (a) ease of determining authorized access during execution, (b) ease of adding access for a new subject, (c) ease of deleting access by a subject, and (d) ease of creating a new object to which all subjects by default have access.

1. Per-subject access control list (that is, one list for each subject tells all the objects to which that subject has access)

2. Per-object access control list (that is, one list for each object tells all the subjects who have access to that object)

3. Access control matrix

4. Capability

1. Per-­?subject access control: (a) A simple lookup from the list, which can be an O(1) operation in the average case if implemented as a hash table. (b) An addition to that subject’s list, which can effectively be an O(1) operation. (c) A removal from that subject’s list, which can effectively be an O(1) operation. (d) An entry needs to be added to all subjects’ lists, which is an O(n) operation where n is the number of subjects.

2. Per-­?object access control: (a) A simple lookupfrom the list, which can effectively be an O(1) operation. (b) An addition to the list, which can effectivelybe an O(1) operation. (c) A removal from the list, which can effectivelybe an O(1) operation. (d) In this model, default access rights for an object can be set, so this, too, can be an O(1) operation.

3. Access control matrix: (a) This is essentially a lookup by subject and object, and the speed depends on implementation, but is likely O(n). (b) Assuming the subject is being newly created, a new row must be added to the matrix, which can be quite costly depending on implementation (potentially requiring the whole table to be copied). (c) This is essentially a lookup by subject and object, and the speed depends on implementation, but is likely O(n). (d) Depending on implementation, creating a new object may require making a copy of the whole table, which would be O(n^2), or may just require adding a new entry to an existing table, which can be made to have a default entry for a performance of O(1).

4. Capability: The capability model needs to be backed by one of the other models, so, depending on implementation, it can effectively have the same performance as any of the other models. The onlypotential difference is in revocation, where the need to track capability “tickets” for revocation becomes an issue.