Scanning and enumeration in Cybersecurity - Time & Space Complexity

Time Complexity: Scanning and enumeration

O(n * m)

Understanding Time Complexity

When scanning and enumerating a network or system, it is important to understand how the time taken grows as the number of targets increases.

We want to know how the scanning process scales when more devices or ports are involved.

Scenario Under Consideration

Analyze the time complexity of the following scanning code snippet.

for ip in network_range:
    for port in common_ports:
        if scan_port(ip, port):
            record_open_port(ip, port)
    

This code scans each IP address in a network range for a list of common ports and records which ports are open.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops scanning each IP and each port.
• How many times: For every IP address, it checks every port in the list.

How Execution Grows With Input

As the number of IP addresses or ports increases, the total scans increase by multiplying these counts.

Input Size (IPs x Ports)	Approx. Operations
10 IPs x 10 ports	100 scans
100 IPs x 10 ports	1,000 scans
100 IPs x 100 ports	10,000 scans

Pattern observation: Doubling the number of IPs or ports roughly doubles the total scans, showing a combined growth.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of IP addresses times the number of ports scanned.

Common Mistake

[X] Wrong: "Scanning more ports doesn't affect time much because ports are small numbers."

[OK] Correct: Each port adds a full scan operation per IP, so more ports multiply the total work significantly.

Interview Connect

Understanding how scanning time grows helps you explain how tools behave on large networks and how to plan efficient scans.

Self-Check

"What if we scanned only a subset of ports for each IP instead of all ports? How would the time complexity change?"