Unit 4: Deadlock, Protection and Security

Part 1: Deadlocks

1. Deadlock Characterization

A deadlock is a situation in a multi-programmed environment where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

The Four Necessary Conditions (Coffman Conditions)

For a deadlock to occur, all four of the following 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 .

Resource Allocation Graph (RAG)

• Nodes: Processes () typically represented by circles; Resources () represented by rectangles.
• Edges:
  • Request Edge: (Process wants resource).
  • Assignment Edge: (Resource allocated to process).
• Deadlock Indication:
  • If the graph contains no cycles, no deadlock exists.
  • If the graph contains a cycle and there is only one instance per resource type, deadlock exists.
  • If the graph contains a cycle but multiple instances per resource type, deadlock is possible (but not guaranteed).

2. Handling of Deadlocks

Operating systems generally use one of three methods to handle deadlocks:

1. Deadlock Prevention or Avoidance: Ensure the system never enters a deadlock state.
2. Deadlock Detection and Recovery: Allow the system to enter a deadlock state, detect it, and recover.
3. The Ostrich Approach: Ignore the problem altogether and pretend that deadlocks never occur (used by UNIX/Linux and Windows due to the rarity and high cost of handling code).

3. Deadlock Prevention

Prevention involves negating one of the four Coffman conditions:

• Mutual Exclusion: Hard to prevent because some resources (e.g., printers) are intrinsically non-sharable. Read-only files do not require mutual exclusion.
• Hold and Wait:
  • Protocol 1: Require a process to request and be allocated all its resources before execution starts. (Low resource utilization).
  • Protocol 2: Allow a process to request resources only when it has none.
• No Preemption: If a process holding some resources requests another resource that cannot be immediately allocated, all resources currently held are released (preempted). The process is restarted only when it can regain its old resources plus the new ones.
• Circular Wait: Impose a total ordering of all resource types. A process can only request resources in an increasing order of enumeration.

4. Deadlock Avoidance

Avoidance requires the OS to be given additional information in advance concerning which resources a process will request and release.

Safe State

A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. An unsafe state does not strictly imply deadlock, but it implies deadlock is possible.

Banker’s Algorithm (Dijkstra)

Used for systems with multiple instances of each resource type.

• Data Structures:
  • Available: Vector of length (number of resources).
  • Max: matrix (max demand of each process).
  • Allocation: matrix (current allocation).
  • Need: matrix ().
• Logic: The algorithm tentatively grants a request and checks if the resulting state is safe. If safe, the request is granted; otherwise, the process must wait.

5. Deadlock Detection

If the system does not employ prevention or avoidance, a deadlock detection algorithm must run.

• Single Instance of each Resource: Use a Wait-for Graph. This is a collapsed version of the Resource Allocation Graph where nodes are processes. An edge exists if is waiting for a resource held by . A cycle implies deadlock.
• Multiple Instances: Use a variation of the Banker's Algorithm (using Available, Allocation, and Request matrices) to see if a sequence exists where all processes can finish.

6. Deadlock Recovery

Once a deadlock is detected, the system must recover.

1. Process Termination:
   • Abort all deadlocked processes. (Drastic, work lost).
   • Abort one process at a time until the deadlock cycle is eliminated. (Overhead of re-running detection algorithm after every abort).
2. Resource Preemption:
   • Selection of Victim: Minimize cost (CPU time used, resources held).
   • Rollback: Return process to a safe state (usually total rollback/restart).
   • Starvation: Ensure the same process is not always picked as a victim (include rollback count in cost factor).

7. Starvation

• Definition: Starvation (or Indefinite Blocking) occurs when a process waits indefinitely within the semaphore or monitor because other processes are constantly utilizing the resource.
• Deadlock vs. Starvation: Deadlock is a circular wait where no one proceeds. Starvation is where specific processes do not proceed while others do.

Part 2: Protection

1. Goals and Principles of Protection

Goals:

• Prevent malicious misuse of the system by users or programs.
• Ensure that system resources are used only in accordance with stated policies.
• Detect errors in interfaces between subsystems.

Principles:

1. Principle of Least Privilege (POLP): Programs, users, and systems should be given just enough privileges to perform their task, and no more.
2. Need-to-know: A process should only have access to objects it currently requires to complete its task.
3. Saltzer and Schroeder’s Principles:
   • Economy of mechanism: Keep the design as simple and small as possible.
   • Fail-safe defaults: Access decisions should be based on permission rather than exclusion.
   • Open design: The design should not be secret (security by obscurity is bad).

2. Domain of Protection

A computer system is a collection of processes and objects.

• Object: Hardware (CPU, printer) or Software (files, semaphores).
• Access Right: Permission to perform an operation on an object (e.g., Read, Write, Execute).
• Domain: A set of <object, {access rights}> pairs.
  • A process operates within a protection domain.
  • User-based: Domain = User ID.
  • Process-based: Domain = Process ID.

3. Access Matrix

The Access Matrix is a conceptual model to specify protection.

• Rows: Domains ().
• Columns: Objects ().
• Entry access[i,j]: Defines the set of operations that a process executing in Domain can invoke on Object .

4. Implementation of Access Matrix

Since the matrix is sparse (mostly empty), storing it as a table is inefficient.

1. Global Table: Stores ordered triples <domain, object, rights>.
   • Drawback: Large table, difficult to group by object or domain.
2. Access Control Lists (ACLs): Decomposes the matrix by columns (Objects).
   • Each object has a list of domains and their rights.
   • Example: File 1 .
   • Used in UNIX/Windows file systems.
3. Capability Lists (C-Lists): Decomposes the matrix by rows (Domains).
   • Each domain (process) has a list of objects and allowed operations.
   • Example: D1 .
   • Possession of a capability serves as the "key" to access.
4. Lock-Key Mechanism:
   • Each object has a list of unique bit patterns (Locks).
   • Each domain has a list of unique bit patterns (Keys).
   • Access allowed only if Key matches Lock.

Part 3: Security

1. Need for Security

While Protection handles internal threats (access control), Security handles external threats. The "CIA Triad" defines security goals:

1. Confidentiality: Information is accessible only to authorized parties.
2. Integrity: Information can be modified only by authorized parties.
3. Availability: Systems work promptly and service is not denied to authorized users.

2. Security Vulnerabilities

A. Buffer Overflow (Stack Smashing)

• The most common vulnerability in C/C++ programs.
• Occurs when input data exceeds the allocated buffer size.
• The excess data overwrites adjacent memory, specifically the Return Address on the stack.
• Attackers replace the return address with the address of malicious code (Shellcode).

B. Trapdoors (Backdoors)

• A code segment intentionally left by the designer to bypass security checks.
• Example: A special password allowing a developer to log in without validation.
• Dangerous if discovered by attackers.

C. Cache Poisoning (DNS Spoofing)

• Introducing corrupt data into the cache of the Domain Name System (DNS) resolver.
• Example: Mapping www.google.com to a malicious IP address in the cache, redirecting users to a fake site.

3. Authentication

Authentication is the process of verifying the identity of a user or system.

Password-based Authentication

• The most common method.
• Vulnerabilities:
  • Brute Force: Trying all possible combinations.
  • Dictionary Attack: Trying common words/passwords.
  • Sniffing: Intercepting passwords sent over networks in plain text.

Password Maintenance & Defense

1. Salting: Appending a random string (salt) to the password before hashing. Even if two users have the same password, their stored hashes will differ.
2. Hashing: Storing the one-way hash (e.g., SHA-256) rather than the plaintext password.
3. Password Aging: Forcing users to change passwords periodically.
4. Passphrase: Encouraging long sentences rather than short words.

Secure Communication

To protect data in transit:

• Cryptography:
  • Symmetric (Secret Key): Same key for encryption and decryption (e.g., AES). Fast, but key distribution is hard.
  • Asymmetric (Public Key): Public key to encrypt, Private key to decrypt (e.g., RSA). Solves key distribution.
• Digital Signatures: Ensures authenticity and non-repudiation. Sender encrypts hash with their Private Key; Receiver verifies with Sender's Public Key.

Part 4: Threats and Attacks

1. Program Threats

Malware written to exploit target systems.

• Trojan Horse: A code segment that misuses its environment. It appears to be a useful program (e.g., a game or utility) but performs malicious actions (like stealing data) in the background.
• Trap Door: (Defined in vulnerabilities).
• Logic Bomb: Code embedded in a legitimate program that "explodes" (executes malicious function) when specific conditions are met (e.g., a specific date or if an employee name is removed from the payroll).
• Virus: A fragment of code embedded in a legitimate program. It is self-replicating. When the infected program runs, the virus runs and infects other programs.
  • Boot Sector Virus: Infects the master boot record.
  • Macro Virus: Embedded in documents (Word, Excel).
  • Polymorphic Virus: Changes its own signature (binary pattern) every time it replicates to evade antivirus detection.

2. System and Network Threats

Attacks targeting the operating environment or communication channels.

• Worms: Similar to viruses but standalone programs (do not need a host file). They use the network to replicate and spread autonomously (e.g., Morris Worm). They consume system resources (CPU/Bandwidth).
• Port Scanning: Automated process of sending messages to ports on a computer to detect open services (reconnaissance before an attack).
• Denial of Service (DoS): Flooding a server with requests to disrupt service for legitimate users.
• Distributed DoS (DDoS): Using a botnet (network of infected zombie computers) to launch a DoS attack from multiple sources.

3. Application Security

Modern OS security involves securing the applications running on top of it.

• SQL Injection: Inserting malicious SQL queries into input fields to manipulate the database (e.g., logging in without a password).
• Cross-Site Scripting (XSS): Injecting malicious client-side scripts into web pages viewed by other users.

4. Examples of Attacks

• Man-in-the-Middle (MITM): An attacker sits between the user and the server, intercepting and potentially altering the communication.
• Phishing: Social engineering attack sending fraudulent communications (usually email) that appear to come from a reputable source to steal sensitive data like credit cards or login info.
• Ransomware: Encrypts the victim's data and demands payment (ransom) for the decryption key (e.g., WannaCry).