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?"