Common network protocols and vulnerabilities in Cybersecurity - Time & Space Complexity

Time Complexity: Common network protocols and vulnerabilities

O(n * m)

Understanding Time Complexity

When studying network protocols and their vulnerabilities, it is important to understand how the time to detect or exploit a vulnerability grows as the network size or traffic increases.

We want to know how the effort or operations needed change as more devices or data are involved.

Scenario Under Consideration

Analyze the time complexity of scanning a network for open ports using a simple port scanner.

for ip in network_range:
    for port in common_ports:
        if scan_port(ip, port) == 'open':
            log_open_port(ip, port)
    

This code checks each IP address in a network range against a list of common ports to find which ports are open.

Identify Repeating Operations

• Primary operation: Checking each port on each IP address.
• How many times: For every IP in the network range, it checks every port in the list.

How Execution Grows With Input

As the number of IP addresses or ports increases, the total checks grow quickly.

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

Pattern observation: The total operations grow proportionally to the number of IPs times the number of ports.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows directly with both the number of IP addresses and the number of ports scanned.

Common Mistake

[X] Wrong: "Scanning more ports won't affect the time much if the network is small."

[OK] Correct: Even with a small network, increasing ports scanned multiplies the total checks, so time grows accordingly.

Interview Connect

Understanding how scanning operations grow helps you explain how vulnerabilities can be found or exploited efficiently in real networks.

Self-Check

"What if we only scan a random sample of ports instead of all common ports? How would the time complexity change?"