Unit 4: Deadlock & Security

1. Deadlock Characterization

Deadlock is a situation in a multi-programming 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 in the same set.

The Coffman Conditions (Necessary Conditions)

A deadlock situation can arise if and only if the following four conditions hold simultaneously in a system:

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 waiting 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 .

2. Handling of Deadlocks

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

1. Deadlock Prevention or Avoidance: Ensure that the system simply 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 and Windows for rare deadlocks to avoid overhead).

Deadlock Prevention

Prevention involves negating one of the four necessary conditions:

• Mutual Exclusion: Cannot be denied for non-sharable resources (e.g., printers), but sharable resources (read-only files) do not require mutually exclusive access.
• Hold and Wait: Guarantee that whenever a process requests a resource, it does not hold any other resources (Request all at start). Low resource utilization.
• No Preemption: If a process holding some resources requests another that cannot be immediately allocated, all currently held resources are released (preempted).
• Circular Wait: Impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration.

Deadlock Avoidance

Avoidance requires that the OS 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 in some order (safe sequence) and still avoid a deadlock.
• Banker's Algorithm: Used for systems with multiple instances of each resource type.
  • Data Structures: Available Vector, Max Matrix, Allocation Matrix, Need Matrix.
  • Logic: When a request is made, pretend to allocate. If the resulting state is Safe, grant request; otherwise, the process must wait.

Deadlock Detection

If the system does not employ prevention or avoidance, it must provide:

1. An algorithm to examine the state of the system to determine whether a deadlock has occurred.
2. An algorithm to recover from the deadlock.

• Wait-for Graph: Used for single instance resources. A deadlock exists if the graph contains a cycle.
• Detection Algorithm: Similar to Banker’s algorithm but tracks current requests rather than potential maximums.

Deadlock Recovery

Once detected, the system must recover:

1. Process Termination:
   • Abort all deadlocked processes (expensive).
   • Abort one process at a time until the deadlock cycle is eliminated (overhead of re-running detection).
2. Resource Preemption:
   • Select a victim (minimize cost).
   • Rollback (return process to safe state).
   • Prevent Starvation (ensure the same process isn't always picked as the victim).

Starvation

Starvation (Indefinite Blocking) occurs when a process waits indefinitely within the semaphore or monitor because other processes keep utilizing the resources it needs. While deadlock implies a standstill, starvation implies that the system is moving, but a specific process is never served.

3. Protection and Security: Fundamentals

Distinction

• Protection: Refers to a mechanism for controlling the access of programs, processes, or users to the resources defined by a computer system. It is internal.
• Security: Requires not only an adequate protection system but also consideration of the external environment. It protects the system from external and internal attacks (e.g., unauthorized access, viruses).

Need for Security (The CIA Triad)

1. Confidentiality: Assets are accessible only by authorized parties.
2. Integrity: Assets can be modified only by authorized parties (prevention of unauthorized writing).
3. Availability: Assets are available to authorized parties when needed (prevention of Denial of Service).

Security Vulnerabilities

A vulnerability is a weakness in the security system (design, implementation, or operation) that might be exploited to cause loss or harm.

1. Buffer Overflow:
   • Occurs when a program writes data beyond the buffer boundary and overwrites adjacent memory locations.
   • Stack Smashing: Attackers overwrite the "return address" on the stack to point to malicious code they injected.
2. Trapdoors (Backdoors):
   • Code segments left by designers/programmers to bypass security checks (e.g., a specific password that grants root access for debugging). If discovered by attackers, it is a major risk.
3. Cache Poisoning:
   • Malicious data is introduced into a cache (e.g., DNS cache or ARP cache) to redirect traffic to a phisher's website.

4. Authentication

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

Password-based Authentication

The most common method. The user provides a secret string.

• Vulnerabilities: Brute force attacks, dictionary attacks, shoulder surfing, packet sniffing.

Password Maintenance & Secure Communication

To store passwords securely, the OS should never store plain text.

• Hashing: Passwords are passed through a one-way hash function (e.g., SHA-256). The system stores the hash.
• Salting: A random string (salt) is appended to the password before hashing. This prevents "Rainbow Table" attacks (pre-computed hash tables) and ensures two users with the same password have different stored hashes.

5. Application Security & Program Threats

Malicious Software (Malware)

1. Trojan Horse: A code segment that misuses its environment. It appears useful (e.g., a free game) but performs malicious actions in the background.
2. Trap Door: (See above).
3. 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).

Viruses

A fragment of code embedded in a legitimate program. It requires a host to run.

• Lifecycle: Dormant Propagation (Replication) Triggering Execution.
• Types:
  • File Virus: Appends to .exe or .com files.
  • Boot Sector Virus: Infects the master boot record.
  • Macro Virus: Embedded in high-level documents (Word, Excel).
  • Polymorphic Virus: Changes its signature every time it replicates to evade antivirus detection.

Worms

Standalone malware that replicates itself to spread to other computers. Unlike viruses, worms do not need to attach to a host program. They consume network bandwidth and system resources.

6. Protection Mechanisms

Goals of Protection

1. Prevent malicious misuse of the system.
2. Ensure that resources are used only in ways consistent with stated policies.
3. Detect errors in interfaces between component subsystems.

Principles of Protection

1. Principle of Least Privilege: Programs, users, and systems should be given just enough privileges to perform their tasks.
2. Need-to-Know: A process should only have access to resources it currently needs to complete its task.
3. Separation of Privilege: Where feasible, a protection mechanism that requires two keys is more robust than one.

Domain of Protection

A computer system is a collection of processes and objects (hardware or software).

• Domain: A set of access rights.
• Access Right: An ordered pair <object-name, rights-set>.
• Example: Domain D1 might have rights <file1, {read, write}> and <printer, {print}>.

Access Matrix

A general model of protection. It is a matrix where:

• Rows represent Domains (users/processes).
• Columns represent Objects (files/resources).
• Entry Access(i, j): Defines the set of operations a process executing in Domain can invoke on Object .

Implementation of Access Matrix

The matrix is usually sparse (mostly empty), so storing it as a 2D array is inefficient.

1. Global Table: Ordered triples <domain, object, rights>. Hard to search.
2. Access Control Lists (ACLs): Store by Column (Object). Each object has a list of domains that can access it. (Used in Windows/Unix file systems).
   • File A: { (D1, Read), (D2, Execute) }
3. Capability Lists (C-Lists): Store by Row (Domain). Each domain has a list of objects it can access.
   • Domain 1: { (File A, Read), (File B, Write) }

7. System and Network Threats

Concepts

• Sniffing: Passive interception of network traffic. Attackers read data (passwords, emails) traveling over the network.
• Spoofing: Active attack where one machine impersonates another (e.g., IP Spoofing).
• Denial of Service (DoS): Disrupting legitimate use of a service by overwhelming the system with requests. Distributed DoS (DDoS) uses a botnet.

Examples of Attacks

1. Man-in-the-Middle (MitM): An attacker sits between the user and the server, intercepting and potentially altering communications without either party knowing.
2. Phishing: Social engineering attack using email/websites to trick users into revealing credentials.
3. Port Scanning: Not an attack per se, but a reconnaissance technique to find open ports and services to identify vulnerabilities.