Penetration testing methodology in Cybersecurity - Time & Space Complexity

Time Complexity: Penetration testing methodology

O(n * m)

Understanding Time Complexity

When performing penetration testing, it is important to understand how the time needed grows as the target system or network size increases.

We want to know how the steps in the testing process scale with the amount of information or systems involved.

Scenario Under Consideration

Analyze the time complexity of the following simplified penetration testing steps.

for each host in network:
    scan open ports on host
    for each open port:
        attempt known exploits
    record results

This code scans each host in a network, checks open ports, tries exploits on those ports, and saves findings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over each host and then each open port on that host.
• How many times: The outer loop runs once per host; the inner loop runs once per open port on that host.

How Execution Grows With Input

As the number of hosts increases, the scanning time grows roughly in proportion to the number of hosts and their open ports.

Input Size (hosts)	Approx. Operations
10	Scanning 10 hosts and their ports
100	Scanning 100 hosts and their ports, about 10 times more work
1000	Scanning 1000 hosts and their ports, about 100 times more work than 10 hosts

Pattern observation: The work grows roughly in direct proportion to the number of hosts and ports scanned.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with the number of hosts (n) times the average number of open ports per host (m).

Common Mistake

[X] Wrong: "The time only depends on the number of hosts, so it grows linearly with hosts."

[OK] Correct: Each host can have many open ports, and testing each port adds extra work, so the total time depends on both hosts and ports.

Interview Connect

Understanding how testing steps scale helps you explain your approach clearly and shows you think about efficiency in real-world security tasks.

Self-Check

"What if we added a step that tries multiple exploits per open port? How would the time complexity change?"