Access Matrix in Operating System :
Access matrix is a model of protection helps in protection of a system. It is a two-dimensional matrix with rows representing domains and columns representing objects. Each cell (i,j) or entry in a matrix defines access rights that processes in domain Di can invoke on object Oj. Consider an example that there are three domains (D1, D2, D3) and four files (file-1, 2, 3, 4) with the following access rights,
- A process running in domain D1 can read all files and write them into file-1 only.
- A process in domain D2 can read file-1, write into file-2 and execute file-4.
- In domain, D3 processes can write file-1 and file-3 and execute file-4.
The above set of access rights can be represented in the access matrix as shown in the below figure.
Access matrix can be used to specify a variety of policies like read, write, execute, print, etc. To enforce these policies, we must ensure that in a particular domain Di, a process can access only those operations specified in a row. Whenever a new object is created Ok, then a new column Ok is added to the access matrix and it is initialized as specified by its creator.
Both static and dynamic access rights can be specified and implemented using an access matrix. When a process switches from one domain to another domain then it is similar that we are executing an operation (domain switch) on an object (the domain). The figure below shows that there is a domain switch possible from D1 to D2, D2 to D1 and D3.
Now domain switching is allowed from Di to Dj only if matrix (i,j) has permission to “switch”. If the contents of the access matrix need to be changed in a controlled fashion then three additional operations, copy, owner, and control are to be used.
If an access-right from one domain can be copied to another domain, then it is represented by an asterisk (*). The copy is done only within the column for which the right is defined. There are two flavors of this scheme,
- If an access-right is copied from a matrix (i,j) to matrix (k,j), then it is removed from (i,j). It is similar to “cut-paste”. This is known as transfer.
- We can limit the “copy of right” (R*) to be copied again, i.e., if a right from a matrix (i,j) is copied to a matrix (k,j) then the right from (k,j) cannot be further copied. This is also known as limited copy.
The owner’s right is used to add and remove rights. If matrix (i,j) has owner rights, then any process executing in that domain ‘i’ can add or remove rights from any entry in column ‘j’. The control right is used to add or remove rights from rows i.e., domains.
Implementation of Access Matrix in OS :
Access matrix is usually a sparse matrix because many of the entries will be empty (if there are no rights present). A sparse matrix can be implemented by using traditional data structural schemes but it is not appropriate because of the protection. Hence, the following methods are used to implement the access matrix.
Global Table :
A global table can be maintained which consists of ordered triples <domain, object, right-set>. When a process in domain Di wants to execute some operation “Opr” on object Oj, then the table is searched for an entry or row <Di, Oj, Rset> and Opr ∈ Rset. If such an entry is found the operation is executed otherwise an exception is raised saying “access denied”. The limitation of this method is that due to several objects existing in the system, the size of the table is increased.
Access Lists :
Lists can be created for each object. It means for each column of the access matrix one list is created. It consist of ordered pair <domain, right-set>. We can also define a default set of access rights when a process in domain Di requests to perform an operation Opr on some object Oj. Then we simply search the access list of object Oj to find an entry <Di, Rset> with Opre ∈ Rset. If the entry is not found, we try to find it in the default-access rights list. If it is found, the operation is allowed, otherwise, the “access denied” exception is raised.
Capability Lists :
Capability lists can be maintained for each domain in which rows of access matrix are maintained as separate lists. It is a list of objects and the operations that are allowed on them in a particular domain. In other words for each domain, a capability list is associated but processes executing in that domain don’t have direct access to it and is a protected object itself.
Users have to access it indirectly through the operating system. To provide basic protection, capabilities must be distinguished from other objects. It is done in two ways,
- A tag is provided for each object which tells the type of object, whether it is a capability or accessible data. Application programs can’t directly access these tags. One bit is enough for a tag, but several bits are used so as to support hardware to distinguish among integers, floats, booleans, pointers, characters, capabilities, etc.
- The address space can be divided into two parts. One containing data and instructions accessible to the program. And other containing capability lists not accessible to program but to operating system. The Mach operating system uses a capability-based protection scheme.
Lock-key Mechanism :
Access and capability lists collectively work in lock-key mechanisms. For each object, a list of unique hit patterns called locks is maintained. And similarly, for each domain, unique hit patterns called keys are maintained.
When a process running in a particular domain Di wants to access an object then the key of that domain Di should match with the lock of that object, then only the access is allowed. The operating system should manage the locks and keys so that unauthorized access is not allowed on them.