Reconnaissance and information gathering in Cybersecurity - Time & Space Complexity

Time Complexity: Reconnaissance and information gathering

O(n * p)

Understanding Time Complexity

When gathering information about a target system, it is important to understand how the time taken grows as the amount of data or targets increases.

We want to know how the effort changes when scanning more hosts or collecting more details.

Scenario Under Consideration

Analyze the time complexity of the following reconnaissance code snippet.

for ip in ip_range:
    open_ports = scan_ports(ip)
    for port in open_ports:
        service_info = get_service_info(ip, port)
        store(service_info)
    gather_os_info(ip)

This code scans a list of IP addresses, checks open ports on each, collects service details, and gathers operating system info.

Identify Repeating Operations

Look at the loops and repeated steps:

• Primary operation: Looping over each IP address in the range.
• Nested operation: For each IP, scanning all open ports and gathering info on each port.
• How many times: The outer loop runs once per IP; the inner loop runs once per open port found on that IP.

How Execution Grows With Input

As the number of IPs increases, the scanning time grows roughly in proportion to the number of IPs and the number of open ports per IP.

Input Size (IPs)	Approx. Operations
10	About 10 times the port scans and info gathers
100	About 100 times the port scans and info gathers
1000	About 1000 times the port scans and info gathers

Pattern observation: The total work grows roughly linearly with the number of IPs scanned, multiplied by the number of ports per IP.

Final Time Complexity

Time Complexity: O(n * p)

This means the time grows proportionally to the number of IP addresses (n) times the average number of open ports (p) per IP.

Common Mistake

[X] Wrong: "Scanning more IPs only slightly increases time because ports are scanned in parallel."

[OK] Correct: Even with some parallelism, each IP and port still requires time to scan, so total time grows with the total number of checks.

Interview Connect

Understanding how scanning time grows helps you plan efficient reconnaissance and shows you can think about scaling tasks in cybersecurity.

Self-Check

"What if we limited port scanning to only the top 10 common ports instead of all open ports? How would the time complexity change?"