Unit4 - Subjective Questions

A Deadlock is a situation in an operating system where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

Necessary Conditions (Coffman Conditions)

For a deadlock to occur, the following four conditions must hold simultaneously:

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular Wait: A set of processes must exist such that is waiting for a resource held by , is waiting for a resource held by , ..., and is waiting for a resource held by .

Deadlock Prevention and Deadlock Avoidance are two different strategies for handling deadlocks before they occur.

The Banker's Algorithm is a deadlock avoidance algorithm that dynamically tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then making an 's-state' check to test for possible deadlock conditions.

Key Concepts:

1. Available: Vector of length . If , there are instances of resource type available.
2. Max: matrix. is the maximum demand of process for resource .
3. Allocation: matrix. is the number of instances of currently allocated to .
4. Need: matrix. .

Safe State:

A system is in a Safe State if there exists a Safe Sequence of processes such that for each , the resources that can still request can be satisfied by .

Logic:

If the system can find a sequence where every process can finish (get its max resources, execute, and return them), the state is safe. If no such sequence exists, the state is unsafe, and the request is denied.

Step 1: Calculate Need Matrix
Formula:

• :
• :
• :
• :
• :

Need Matrix:

Step 2: Safety Algorithm
Work Available =

1. Check : Need ? False.
2. Check : Need ? True.
   • Execute . New Available = .
3. Check : Need ? True.
   • Execute . New Available = .
4. Check : Need ? True.
   • Execute . New Available = .
5. Check : Need ? True.
   • Execute . New Available = .
6. Check : Need ? True.
   • Execute . New Available = .

Conclusion:
The system is in a Safe State.
Safe Sequence: (Note: Other sequences may also exist).

Deadlock Detection identifies if a deadlock has occurred by examining the state of the system.

Resource Allocation Graph (RAG)

A directed graph where nodes are Processes () and Resources (). Edges represent requests () or allocations ().

1. Single Instance of Each Resource Type:

   • If the Resource Allocation Graph contains a Cycle, then a deadlock exists.
   • The detection algorithm searches for cycles in the graph.

2. Multiple Instances of Resource Types:

   • A cycle in the graph is necessary but not sufficient for deadlock. A cycle indicates that a deadlock may exist.
   • To detect deadlock definitively in multi-instance systems, an algorithm similar to Banker's Algorithm is used (checking if any process sequence can complete). If the algorithm yields a state where some processes cannot finish, those processes are deadlocked.

Once a deadlock is detected, the system must recover to allow execution to proceed. There are two primary approaches:

1. Process Termination

• Abort all deadlocked processes: This breaks the deadlock cycle immediately but incurs a high cost as partial computations are lost.
• Abort one process at a time: The OS aborts one deadlocked process and runs the detection algorithm again. This continues until the deadlock is eliminated.
  • Challenge: Choosing the victim (based on priority, cost, time remaining).

2. Resource Preemption

Resources are successively preempted from processes and given to others until the deadlock cycle is broken.

• Selecting a Victim: Which process and resource to preempt to minimize cost.
• Rollback: The process from which the resource was preempted cannot continue. It must be rolled back to a safe checkpoint or restarted.
• Starvation: We must ensure the same process is not always picked as a victim.

Protection refers to a mechanism for controlling the access of programs, processes, or users to resources defined by a computer system. The main goals are:

1. Prevent Malicious Misuse: To prevent users from intentionally interfering with or destroying the data/resources of other users (e.g., malware, unauthorized access).
2. Prevent Accidental Damage: To ensure that bugs in a program (e.g., a pointer error) do not corrupt the integrity of the OS or other processes.
3. Ensure Component Integrity: To ensure that the resources (CPU, Memory, Files) are used only in ways consistent with stated policies.
4. Enforce Usage Policies: To manage resource quotas and access rights (e.g., Read-Only vs. Read-Write) based on user roles.
5. Error Confinement: If a subsystem fails or is compromised, protection boundaries ensure the damage is contained to that specific domain and does not crash the whole system.

A Domain of Protection defines the set of resources that a process may access and the operations it can perform on those resources.

• Structure: A domain is a set of Access Rights. An access right is an ordered pair . For example, .
• Association: At any point in time, a process runs within a specific protection domain.
• Static vs. Dynamic:
  • In a static model, the set of resources available to a process is fixed throughout its lifetime.
  • In a dynamic model, a process can switch between domains (domain switching) to gain or lose privileges based on its current task.
• Examples:
  • User/Kernel Mode: In UNIX, the domain is defined by the UID (User ID). A setuid program allows a process to switch domains effectively.

The Access Matrix is a general model of protection that abstractly describes the access rights of domains to objects.

Structure

It is a matrix where:

• Rows represent Domains ().
• Columns represent Objects () (Files, Hardware, or other Domains).
• Entry defines the set of access rights (e.g., Read, Write, Execute, Switch) that Domain has over Object .

Example

Mechanism vs. Policy

• The Access Matrix provides the mechanism (how to check permissions).
• The OS users/admins define the policy (who gets what permissions).

Since the Access Matrix is usually sparse (mostly empty), storing it as a 2D array is inefficient. It is typically implemented by decomposing the matrix by columns or rows.

1. Access Control Lists (ACL) - Decomposition by Column

• Each Object is associated with a list containing domains and their access rights.
• Format: Object : ...
• Pros: Easy to determine "Who can access this file?". Easy to revoke rights for a specific object.
• Cons: Hard to determine "What can this user access?".

2. Capability Lists (C-Lists) - Decomposition by Row

• Each Domain (Process/User) is associated with a list of objects and allowed operations.
• Format: Domain : ...
• Pros: Efficient access checks during execution (possession of capability implies access).
• Cons: Revocation is difficult (must find the capability in the user's list and delete it).

Buffer Overflow is a common security vulnerability that occurs when a program writes data beyond the boundaries of a pre-allocated fixed-length buffer.

Mechanism:

1. Memory Layout: A process memory includes a Stack, which stores local variables, function parameters, and the Return Address (instruction pointer).
2. The Attack: If a program (e.g., written in C) uses unsafe functions like gets() or strcpy() without checking bounds, an attacker can input a string longer than the buffer size.
3. Corruption: The excess data overwrites adjacent memory on the stack.
4. Exploit: The attacker crafts the input to overwrite the Return Address with a pointer to malicious code (shellcode) injected into the buffer.
5. Execution: When the function returns, the CPU jumps to the malicious code instead of the original caller, granting the attacker control (often with root privileges).

These are specific types of security threats:

1. Trapdoors (or Backdoors):

   • A secret entry point into a program that allows someone strictly aware of the trapdoor to gain access without going through the usual security access procedures.
   • Origin: Often left by developers for debugging or maintenance and forgotten, or inserted maliciously by a programmer.
   • Risk: An attacker discovering the backdoor can bypass authentication entirely.

2. Cache Poisoning:

   • Ideally refers to DNS Cache Poisoning or ARP Poisoning.
   • Mechanism: The attacker introduces incorrect data into a cache (e.g., a DNS resolver's cache).
   • Result: When a user requests a legitimate website (e.g., bank.com), the poisoned cache redirects them to a malicious IP address controlled by the attacker, facilitating phishing or Man-in-the-Middle attacks.

Password-based Authentication is the most common method of verifying user identity. The user provides a secret string (password) known only to them and the system.

Problems with Passwords:

1. Weakness: Users choose short or guessable passwords (dictionary words).
2. Sniffing: Plaintext passwords can be intercepted on the network.
3. Rainbow Tables: If the OS stores passwords as hashes, attackers can use precomputed tables (Rainbow Tables) to reverse the hash.

Salting:

To secure stored passwords, the system uses a Salt—a random string of data.

• Process: When a password is created, the system generates a random salt. . The salt is stored in plaintext alongside the hash.
• Benefit: Even if two users have the same password, their salts will differ, resulting in different stored hashes. This renders precomputed Rainbow Tables ineffective because the attacker would need to generate a new table for every unique salt.

Saltzer and Schroeder (1975) identified key principles for designing secure systems:

1. Least Privilege: Every program and user should operate using the least set of privileges necessary to complete the job. This limits the damage if an entity is compromised.
2. Fail-Safe Defaults: Access decisions should be based on permission rather than exclusion. The default setting should be "Deny Access".
3. Open Design: The security architecture should not depend on secrecy (Security by Obscurity). The design should be public; only the keys/passwords should be secret.
4. Separation of Privilege: Where feasible, a protection mechanism should require two keys (or conditions) to unlock, making it more robust.
5. Economy of Mechanism: Security mechanisms should be as simple and small as possible to facilitate verification and testing.
6. Least Common Mechanism: Minimize the amount of mechanism common to more than one user and depended on by all users (reduces shared channels).

Program threats are malware designed to exploit system vulnerabilities via program execution.

1. Trojan Horse:

   • A code segment that misuses its environment. It appears to be a useful program (e.g., a game or utility) but secretly performs malicious acts (stealing data, deleting files) when executed by the user.

2. Logic Bomb:

   • Code embedded in a legitimate program that is set to "explode" (execute malicious function) when certain conditions are met (e.g., a specific date, or if a specific employee name is removed from the payroll).

3. Stack and Buffer Overflow:

   • Exploits bug in code to overwrite memory and execute arbitrary instructions (explained in detail in separate questions).

4. Virus:

   • A fragment of code embedded in a legitimate program. It is self-replicating and requires a host program to spread. It modifies the host to include a copy of the virus.

A Virus is a piece of software that can infect other programs by modifying them to include a possibly evolved copy of itself. It requires a host program to execute.

Phases of a Virus Lifecycle:

1. Dormant Phase: The virus is idle. It will eventually be activated by some event (e.g., a date). Not all viruses have this stage.
2. Propagation Phase: The virus places a copy of itself into other programs or system areas on the disk. Each infected program will contain a clone of the virus.
3. Triggering Phase: The virus is activated to perform the function for which it was intended. It is caused by a systemic event (e.g., count of times executed).
4. Execution Phase: The function is performed. The function may be harmless (a message on screen) or destructive (deleting files).

These threats target the operating system via the network environment:

1. Sniffing (Eavesdropping):

   • Passive interception of network traffic. Attackers capture packets moving across a LAN/WAN to read sensitive data (passwords, emails) if not encrypted.

2. Spoofing:

   • Masquerading as a legitimate entity.
   • IP Spoofing: Altering the source IP address in a packet to hide identity or impersonate a trusted system.
   • Content Spoofing: Phishing sites that look like real sites.

3. Denial of Service (DoS):

   • An attack capable of preventing legitimate users from using the system.
   • Mechanism: Overloading the target server with a flood of requests (e.g., SYN Flood) so it cannot respond to genuine traffic.
   • DDoS (Distributed DoS): Using a botnet of zombies to launch the attack from multiple sources simultaneously.

A Security Vulnerability is a weakness in the system design, implementation, or operation that can be exploited by an adversary to violate the security policy (Confidentiality, Integrity, Availability).

Why Perfect Security is Impossible:

1. Complexity: Modern OSes contain millions of lines of code. It is statistically impossible to eliminate all bugs.
2. Unknown Attacks: Defenders protect against known threats, but "Zero-Day" exploits utilize vulnerabilities unknown to the vendor.
3. Human Factor: Social engineering (phishing) targets users, not software. Users are often the weakest link.
4. Trade-off: High security often reduces usability and performance. Systems must balance these factors.
5. Race Conditions: Vulnerabilities like TOCTTOU (Time-of-check to time-of-use) occur due to the asynchronous nature of OS operations.