Buffer overflow attacks in Operating Systems - Time & Space Complexity

Time Complexity: Buffer overflow attacks

O(n)

Understanding Time Complexity

Analyzing time complexity helps us understand how the cost of detecting or exploiting buffer overflow attacks grows as input size changes.

We want to know how the number of operations scales when handling input that might overflow a buffer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

char buffer[10];
void copy_input(char *input) {
  int i = 0;
  while (input[i] != '\0') {
    buffer[i] = input[i];
    i++;
  }
}
    

This code copies characters from input into a fixed-size buffer without checking length, which can cause a buffer overflow.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop copies each character from input to buffer one by one.
• How many times: The loop runs once for each character until it finds the end of the input string.

How Execution Grows With Input

As the input string gets longer, the number of copy operations grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 copy steps
100	About 100 copy steps
1000	About 1000 copy steps

Pattern observation: The number of operations increases in a straight line as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to copy input grows directly in proportion to the input length.

Common Mistake

[X] Wrong: "The loop will always stop at the buffer size, so time is constant."

[OK] Correct: The code does not check buffer size, so the loop depends on input length, not buffer size, which can cause overflow and longer execution.

Interview Connect

Understanding how input size affects operations in buffer handling is key to spotting vulnerabilities and writing safer code.

Self-Check

"What if we added a check to stop copying when the buffer is full? How would the time complexity change?"

Practice

1. What is a buffer overflow attack in simple terms?

easy

A. Putting more data into a memory space than it can hold

B. Deleting data from memory intentionally

C. Encrypting data to protect it

D. Backing up data to a safe location

Solution

1. Step 1: Understand what a buffer is

   A buffer is a small area in memory used to store data temporarily.

2. Step 2: Define buffer overflow

   Buffer overflow happens when more data is put into this area than it can hold, causing errors or security risks.

3. Final Answer:

   Putting more data into a memory space than it can hold -> Option A

4. Quick Check:

   Buffer overflow = Too much data in small memory [OK]

Hint: Too much data in small space causes overflow [OK]

Common Mistakes:

• Confusing overflow with data deletion
• Thinking encryption is overflow
• Mixing backup with overflow

2. Which of the following is the correct way to prevent buffer overflow in programming?

easy

A. Using unlimited memory without checks

B. Ignoring input size and trusting user data

C. Checking input size before storing it in memory

D. Allowing programs to crash to fix errors

Solution

1. Step 1: Identify safe programming practice

   Safe programming means checking input size before storing it to avoid overflow.

2. Step 2: Evaluate options

   Ignoring input or using unlimited memory without checks is unsafe; allowing crashes is not prevention.

3. Final Answer:

   Checking input size before storing it in memory -> Option C

4. Quick Check:

   Input size check = Prevent overflow [OK]

Hint: Always check input size before storing [OK]

Common Mistakes:

• Trusting user input blindly
• Assuming memory is unlimited
• Ignoring program crashes

3. Consider this code snippet in C-like pseudocode:

char buffer[5];
strcpy(buffer, "HelloWorld");

What will likely happen when this code runs?

medium

A. The program stores "Hello" safely and ignores the rest

B. The program crashes or behaves unpredictably due to overflow

C. The program automatically resizes buffer to fit the string

D. The program throws a syntax error before running

Solution

1. Step 1: Analyze buffer size and input

   The buffer can hold 5 characters, but the string "HelloWorld" has 10 characters.

2. Step 2: Understand strcpy behavior

   strcpy copies all characters without checking size, causing overflow beyond buffer limits.

3. Final Answer:

   The program crashes or behaves unpredictably due to overflow -> Option B

4. Quick Check:

   Copying too large string = Crash or error [OK]

Hint: Copying bigger string than buffer causes crash [OK]

Common Mistakes:

• Assuming partial copy happens safely
• Thinking buffer resizes automatically
• Confusing syntax error with runtime error

4. Identify the error in this pseudocode that causes a buffer overflow:

char data[4];
input = getUserInput();
for i in range(len(input)) {
  data[i] = input[i];
}

medium

A. The data array is declared with too many elements

B. The input is not converted to uppercase

C. The loop uses the wrong variable name

D. The loop does not check if i exceeds data size

Solution

1. Step 1: Examine loop and array size

   The data array has size 4, but the loop runs for the full length of input without limit.

2. Step 2: Identify missing boundary check

   Without checking if i < 4, the loop writes beyond data's memory, causing overflow.

3. Final Answer:

   The loop does not check if i exceeds data size -> Option D

4. Quick Check:

   Missing boundary check = Overflow risk [OK]

Hint: Always check loop limits against buffer size [OK]

Common Mistakes:

• Ignoring array size limits
• Focusing on unrelated input format
• Confusing variable names

5. A program uses a buffer of size 8 to store user input. Which approach best prevents buffer overflow while allowing flexible input length?

hard

A. Use dynamic memory allocation to resize buffer as needed

B. Use a fixed buffer and truncate input longer than 8 characters

C. Ignore input size and trust user to enter short data

D. Allow buffer overflow and handle errors after crash

Solution

1. Step 1: Understand fixed buffer limits

   Fixed buffer size limits input length, truncation loses data, ignoring size risks overflow.

2. Step 2: Evaluate dynamic allocation benefits

   Dynamic memory allocation adjusts buffer size to input length, preventing overflow and preserving data.

3. Final Answer:

   Use dynamic memory allocation to resize buffer as needed -> Option A

4. Quick Check:

   Dynamic resizing = Safe flexible input [OK]

Hint: Resize buffer dynamically to fit input safely [OK]

Common Mistakes:

• Relying on truncation losing data
• Trusting user input blindly
• Ignoring errors after overflow