Cross-site scripting (XSS) in Cybersecurity - Time & Space Complexity

Time Complexity: Cross-site scripting (XSS)

O(n * m)

Understanding Time Complexity

When analyzing Cross-site scripting (XSS), we want to understand how the time to detect or exploit XSS grows as the input or attack surface increases.

We ask: How does the effort change when the website or input size grows?

Scenario Under Consideration

Analyze the time complexity of the following simplified XSS detection code.

for input in user_inputs:
    if "<script>" in input:
        alert("XSS detected")

This code checks each user input for a simple XSS pattern by scanning for the <script> tag.

Identify Repeating Operations

• Primary operation: Looping through each user input and scanning the input string for the <script> substring.
• How many times: Once for each input in the list; scanning each input depends on its length.

How Execution Grows With Input

As the number of inputs grows, the code checks more items. Also, longer inputs take more time to scan.

Input Size (n)	Approx. Operations
10	Checks 10 inputs, each scanned for <script>
100	Checks 100 inputs, scanning each one
1000	Checks 1000 inputs, scanning each one

Pattern observation: The total work grows roughly in direct proportion to the number of inputs and their length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with both the number of inputs (n) and the length of each input (m).

Common Mistake

[X] Wrong: "Checking just a few inputs is always fast, no matter how long they are."

[OK] Correct: Even a small number of very long inputs can take a lot of time to scan because the code looks through each character.

Interview Connect

Understanding how scanning inputs for XSS scales helps you think like a security engineer. It shows you how to balance thorough checks with performance.

Self-Check

"What if we used a more complex pattern matching method instead of simple substring search? How would the time complexity change?"