Unit4 - Subjective Questions

A deadlock situation can arise if the following four conditions hold simultaneously in a system (often called the Coffman conditions):

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 .

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

• Deadlock Prevention:

  • Concept: Provides a set of methods to ensure that at least one of the four necessary conditions (Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait) cannot hold.
  • Mechanism: Restricts the way requests can be made (e.g., requesting all resources at start).
  • Resource Utilization: Generally leads to low device utilization and reduced system throughput due to strict restrictions.
  • Example: Forcing a process to release all resources before requesting a new one (attacking Hold & Wait).

• Deadlock Avoidance:

  • Concept: Requires the operating system to have additional prior information about which resources a process will request and use during its lifetime.
  • Mechanism: The system dynamically decides whether to grant a resource request by checking if the resulting state is a Safe State.
  • Resource Utilization: Allows higher utilization than prevention but requires knowledge of maximum demands.
  • Example: Banker's Algorithm.

The Banker's Algorithm is a deadlock avoidance algorithm applicable to systems with multiple instances of each resource type. It ensures the system always remains in a Safe State.

Data Structures:

Let be the number of processes and be the number of resource types.

1. Available: A vector of length . If , there are instances of resource type available.
2. Max: An matrix. means process may request at most instances of resource type .
3. Allocation: An matrix. means is currently allocated instances of .
4. Need: An matrix. means needs more instances of to complete its task. Calculation: .

Algorithm Logic:

1. Request Algorithm: When a request is made, the system checks if and . If true, it pretends to allocate resources and runs the Safety Algorithm.
2. Safety Algorithm:
   • Initialize and for all .
   • Find an index such that and .
   • If such exists: ; ; repeat.
   • If no such exists, check if all are true. If yes, the state is safe.

Starvation (Indefinite Blocking):
Starvation occurs when a process waits indefinitely within the semaphore or scheduling queue because other processes are continuously preferred over it. This usually happens in priority-based scheduling algorithms where low-priority processes may never get the CPU if high-priority processes keep arriving.

Differences from Deadlock:

• Definition: Deadlock is a state where a set of processes are blocked because each is holding a resource and waiting for another resource held by someone else in the set. Starvation is where a process is unable to gain access to resources due to scheduling policies.
• Structure: Deadlock requires a Circular Wait. Starvation does not necessarily imply a cycle; it can happen in a linear queue.
• Outcome: In deadlock, none of the participating processes can proceed. In starvation, the system makes progress (other processes run), but the starved process does not.
• Resolution: Deadlock is resolved by preemption or termination. Starvation is often resolved by Aging (gradually increasing the priority of waiting processes).

A Resource Allocation Graph (RAG) is a directed graph used to visualize resource allocation and deadlock states.

Components:

1. Vertices (V): Partitioned into two types:
   • Process Nodes (): Represented by circles ().
   • Resource Nodes (): Represented by rectangles (). Dots inside the rectangle represent the number of instances.
2. Edges (E):
   • Request Edge: Directed edge from process to resource ().
   • Assignment Edge: Directed edge from resource to process ().

Characterizing Deadlock:

• Single Instance per Resource Type: If the graph contains a cycle, then a deadlock exists.
• Multiple Instances per Resource Type: If the graph contains a cycle, a deadlock may exist (necessary but not sufficient condition). A knot or lack of available resources to break the cycle is required for deadlock.
• No Cycle: If there is no cycle in the graph, then no process is deadlocked.

Once a deadlock detection algorithm identifies a deadlock, the system must recover to break the cycle. 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 system aborts one process and re-runs the detection algorithm until the deadlock is eliminated. The overhead is the repeated execution of the detection algorithm.
  • Selection criteria: Priority of the process, computation time used/remaining, resources used.

2. Resource Preemption:

• Selecting a victim: Choose a process to preempt resources from (based on cost factors).
• Rollback: The system cannot just take the resource; the process usually cannot continue. It must be rolled back to a safe checkpoint or restarted completely.
• Starvation: Ensure the same process is not always picked as the victim (include the number of rollbacks in the cost factor).

The goals of protection in an Operating System are designed to ensure the reliability and integrity of the system and its data:

1. Safety and Integrity: To prevent malicious or accidental access to system resources, ensuring that data is not corrupted or deleted.
2. Access Control: To ensure that each active program component (process) uses system resources (CPU, memory, files) only in ways consistent with stated policies.
3. Error Containment: To prevent errors in one subsystem from contaminating other subsystems (e.g., a buggy program shouldn't crash the OS).
4. Information Flow Control: To regulate the flow of information within the system, ensuring confidential data isn't leaked to unauthorized domains.
5. Auditability: To provide mechanisms (like logs) to trace which user or process accessed specific resources, aiding in forensics.

Saltzer and Schroeder outlined several key principles for designing secure protection systems:

1. Principle of Least Privilege: Programs, users, and systems should be given just enough privileges to perform their tasks. This limits damage if a component is compromised.
2. Need-to-Know: A process should only have access to the resources currently required to complete its task.
3. Fail-Safe Defaults: Access decisions should be based on permission rather than exclusion. If a rule is missing, access is denied by default.
4. Open Design: The security mechanism should not depend on the secrecy of its design (avoid "Security by Obscurity"). The design should be public and verifiable.
5. Separation of Privilege: Where feasible, a protection mechanism requiring two keys is more robust than one (e.g., Multi-Factor Authentication).
6. Economy of Mechanism: Security mechanisms should be as simple and small as possible to allow for thorough testing and verification.
7. Least Common Mechanism: Minimize the amount of mechanism common to more than one user and depended on by all users (e.g., shared variables).

Domain of Protection defines the environment in which a process executes. It specifies the resources that the process may access and the operations it may perform on those resources.

• Structure: A domain is a set of Access Rights. An access right is an ordered pair .
  • For example, if Domain has access right , a process executing in Domain can read and write to file .
• Associations:
  • User-based: The domain is defined by the user identity (User Mode vs. Kernel Mode).
  • Process-based: The domain is defined by the process identity.
  • Procedure-based: The domain changes based on the procedure being executed.
• Domain Switching: The ability of a process to switch from one domain to another (e.g., using setuid in Unix to temporarily gain root privileges).

An Access Matrix is a general model of protection used to describe the rights of processes (domains) over various objects (files, devices).

Structure:

• Rows: Represent Domains ().
• Columns: Represent Objects ().
• Entry : Defines the set of access rights domain has on object (e.g., Read, Write, Execute).

Implementation Methods:
Since the matrix is often sparse (mostly empty), storing it as a 2D array is inefficient. Common implementations include:

1. Global Table: A list of triples . Hard to search and manage.
2. Access Control Lists (ACLs): Decomposition by Column (Object). Each object has a list of domains that can access it and their rights. (e.g., File permissions in Windows/Unix).
3. Capability Lists (C-Lists): Decomposition by Row (Domain). Each domain acts as a user and holds a list of objects (capabilities) it can access and the associated rights. Possessing the capability grants access (like a key).

Buffer Overflow is a common software vulnerability that occurs when a program writes data to a buffer (a temporary storage area in memory) and overruns the buffer's boundary, overwriting adjacent memory locations.

• Mechanism: Typically occurs in languages like C/C++ that do not perform automatic bounds checking. If a user inputs data larger than the allocated array, the extra data spills over.
• Consequences:
  • Crash: Corrupts data or instructions, causing a segmentation fault.
  • Execution of Malicious Code: Attackers can craft input to overwrite the Return Address on the stack. Instead of returning to the calling function, the CPU jumps to malicious code (shellcode) injected by the attacker.
• Mitigation: Input validation, using safe functions (e.g., strncpy instead of strcpy), and hardware support (NX bit - No Execute).

Trapdoors (or Backdoors):

• Definition: A trapdoor is a secret entry point into a program or system that allows someone that is aware of the trapdoor to gain access without going through the usual security access procedures (like authentication).
• Origin:
  • Intentional: Developers often leave debug code or special bypasses to fix bugs or test the system easily during development. If not removed before release, these become security holes.
  • Malicious: An attacker or a disgruntled employee might modify the source code or compiler to include a hidden entry mechanism.
• Risk: They are difficult to detect because they are often embedded in the legitimate code logic. An attacker using a trapdoor can bypass firewalls and passwords entirely.

Password-based Authentication is the most common method of identifying a user. The user provides a secret string (password) associated with their identity.

Security Issues:

• Weak passwords (guessable).
• Transmission in plaintext (sniffing).
• Storage leaks.

Methods to Secure Passwords:

1. Hashing: Never store passwords in plaintext. Store a cryptographic hash (e.g., SHA-256). One-way functions ensure the original password cannot be easily derived from the stored value.
2. Salting: Add a random string (Salt) to the password before hashing (). This prevents Rainbow Table attacks (precomputed hash tables) and ensures two users with the same password have different stored hashes.
3. Password Aging: Forcing users to change passwords periodically.
4. Multi-Factor Authentication (MFA): Combining passwords with something the user has (phone/token).

Program Threats:
These are malware written to exploit vulnerabilities in a program or operating system to hijack the process's context or privileges.

• Target: Specific processes or applications.
• Examples:
  • Trojan Horse: A program that looks useful but contains hidden malicious code.
  • Trap Door: Secret entry point.
  • Logic Bomb: Code that initiates a malicious act when certain conditions are met.
  • Buffer Overflow: Exploiting memory bounds.

System and Network Threats:
These threats involve the abuse of devices and network connections to disrupt services or propagate malware across a network.

• Target: The entire operating system or network infrastructure.
• Examples:
  • Worms: Self-replicating malware that uses the network to spread without user intervention.
  • Port Scanning: Automated detection of open ports to find vulnerabilities.
  • Denial of Service (DoS): Flooding a system with traffic to make it unavailable to legitimate users.

A Virus is a fragment of code embedded in a legitimate program. It is self-replicating and requires a host program to spread.

Virus Lifecycle:

1. Dormant Phase: The virus is idle, waiting for an event (date, time, file presence).
2. Propagation Phase: The virus places a copy of itself into other programs or system areas.
3. Triggering Phase: The virus is activated to perform the function for which it was intended.
4. Execution Phase: The function is performed (e.g., displaying a message, deleting files).

Types of Viruses:

• Parasitic Virus: Attaches to executable files (.exe).
• Boot Sector Virus: Infects the master boot record and spreads when the system is booted.
• Polymorphic Virus: Changes its signature (code pattern) every time it replicates to evade antivirus detection.
• Macro Virus: Written in macro languages (like VBA) embedded in documents (Word, Excel).
• Stealth Virus: Hides modifications made to files or boot records.

Cache Poisoning is a type of attack where incorrect or malicious data is inserted into the cache of a system (typically a DNS cache or a web cache).

• DNS Cache Poisoning (DNS Spoofing):
  • Mechanism: An attacker tricks a DNS server into believing that a fake IP address is associated with a legitimate domain name (e.g., google.com).
  • Result: The DNS server caches this false mapping. When users query the domain, the server returns the attacker's IP, redirecting users to a malicious site (phishing).
• Impact: It facilitates Man-in-the-Middle (MITM) attacks and phishing, compromising user credentials and sensitive data.

A system is in a Safe State if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock.

• Safe Sequence: A sequence of processes is a safe sequence if, for each , the resources that can still request can be satisfied by the currently available resources plus the resources held by all the processes (where ).
• Logic: If such a sequence exists, the system guarantees that even if all processes request their maximum resources immediately, there is a path where everyone finishes: finishes and returns resources, allowing to finish, and so on.
• Relation to Deadlock:
  • Safe State No Deadlock.
  • Unsafe State Possibility of Deadlock (not certainty, but the guarantee of safety is lost).

To prevent deadlock by invalidating the Hold and Wait condition, we must ensure that whenever a process requests a resource, it does not hold any other resources. Two protocols can achieve this:

1. Protocol 1 (Total Allocation): Require each process to request and be allocated all its resources before it begins execution.
   • Disadvantage: Low resource utilization (resources held but not used for a long time).
2. Protocol 2 (No Hold while Requesting): Allow a process to request resources only when it has none. If a process has resources and needs more, it must first release all currently held resources and then re-request them along with the new ones.
   • Disadvantage: Possibility of Starvation (a popular resource might never be free when the process releases its current set).

Denial of Service (DoS) is a system/network threat aimed at making a machine or network resource unavailable to its intended users.

• Mechanism: The attacker floods the target system with a surplus of requests, overloading the system and preventing it from responding to legitimate traffic.
• Types:
  • Resource Depletion: Consuming all CPU, memory, or disk space.
  • Bandwidth Consumption: Saturating the network link.
  • TCP SYN Flood: Initiating many TCP connections but never completing the handshake, leaving the server waiting with open ports.
• DDoS (Distributed DoS): The attack is launched from multiple compromised computers (botnet) simultaneously, making it harder to block.

Access Control List (ACL) is a method of implementing the Access Matrix by decomposing the matrix by columns (Objects).

• Concept: For each object (e.g., a file), the system maintains a list of domains (users/groups) and their specific access rights to that object.
• Structure:
• Default: If a domain is not listed in the ACL, access is denied.

Example:
Consider File . The ACL might look like:

• Advantages: corresponds well to users' concept of protection (Who can access my file?); efficient for revoking rights for a specific object.

• Disadvantages: It is difficult to determine all access rights for a specific user (requires searching all ACLs).