IPv4 addresses

This notebook shows how IPv4 addresses can be described, generated and recognized with a grammar.

References

• Wikipedia

  • IP address: (IPv4) defines an IP address as a 32-bit number […] written and displayed in human-readable notations

  • IPv4: 32-bit address space which provides 4,294,967,296 (2^32) unique addresses

import random
import subprocess

import alogos as al

Grammar

bnf_text = """
<ip> ::= <number>.<number>.<number>.<number>
<number> ::= <digit> | <non-zero><digit> | 1<digit><digit> | 2<zero-four><digit> | 25<zero-five>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<non-zero> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<zero-four> ::= 0 | 1 | 2 | 3 | 4
<zero-five> ::= 0 | 1 | 2 | 3 | 4 | 5
"""

grammar = al.Grammar(bnf_text=bnf_text)

Generate random IPv4 addresses

1) With Python’s random.choice

def generate_random_ip():
    allowed_numbers = list(range(256))
    random_numbers = [random.choice(allowed_numbers) for _ in range(4)]
    ip = '{}.{}.{}.{}'.format(*random_numbers)
    return ip

generate_random_ip()

'186.174.7.182'

2) With the grammar

grammar.generate_string()

'105.253.133.42'

Is there a response?

Use ping to see if there’s a server responding to an ICMP ECHO_REQUEST at some random addresses

for i in range(25):
    ip_address = grammar.generate_string()
    returned = subprocess.call(['ping', '-W', '1', '-c', '1', ip_address], stdout=subprocess.DEVNULL)
    print('{:2}:  IP: {:16} Response: {}'.format(i, ip_address, 'yes' if returned==0 else 'no'))

 0:  IP: 229.251.245.241  Response: no
 1:  IP: 254.252.249.170  Response: no
 2:  IP: 250.187.20.130   Response: no
 3:  IP: 5.67.40.31       Response: yes
 4:  IP: 165.223.188.244  Response: no
 5:  IP: 1.255.175.170    Response: yes
 6:  IP: 42.237.190.17    Response: no
 7:  IP: 116.9.255.136    Response: no
 8:  IP: 47.2.230.4       Response: no
 9:  IP: 201.2.6.217      Response: yes
10:  IP: 46.211.5.190     Response: no
11:  IP: 242.242.255.7    Response: no
12:  IP: 5.34.12.253      Response: no
13:  IP: 255.0.251.175    Response: no
14:  IP: 143.38.69.0      Response: no
15:  IP: 22.172.7.132     Response: no
16:  IP: 229.253.41.9     Response: no
17:  IP: 236.4.104.253    Response: no
18:  IP: 244.143.57.5     Response: no
19:  IP: 1.30.247.243     Response: no
20:  IP: 22.233.46.46     Response: no
21:  IP: 220.1.0.252      Response: no
22:  IP: 255.98.33.2      Response: no
23:  IP: 250.48.48.8      Response: no
24:  IP: 64.254.254.75    Response: no

Parse and recognize IPv4 addresses

parse_tree = grammar.parse_string('0.1.2.3')
parse_tree

parse_tree = grammar.parse_string('192.168.249.255')
parse_tree

# Check that 2000 randomly generated IPv4 addresses are recognized as part of the language
for _ in range(2000):
    random_ip = generate_random_ip()
    if not grammar.recognize_string(random_ip):
        print('Valid IP was not recognized:', random_ip)

# Check that some invalid addresses are not part of the language
for invalid_address in ['255.255.255.256', '0.0.0.09', '13.014.22.101', '300.1.2.3']:
    if grammar.recognize_string(invalid_address):
        print('Invalid IP was recognized:', random_ip)

Optimization

Try to find the smallest and largest IPv4 addresses

Size of the search space: 4,294,967,296 elements

print('Number of IPv4 addresses: 2^32 = {:,} or equivalently 256^4 = {:,}'.format(2**32, 256**4))

Number of IPv4 addresses: 2^32 = 4,294,967,296 or equivalently 256^4 = 4,294,967,296

def objective_function(string):
    numbers = [int(s) for s in string.split('.')]
    return sum(numbers)

ea = al.EvolutionaryAlgorithm(grammar, objective_function, 'min', max_generations=50)
best_individual = ea.run()
print(best_individual.phenotype)

0.0.0.0

ea = al.EvolutionaryAlgorithm(grammar, objective_function, 'max', max_generations=50)
best_individual = ea.run()
print(best_individual.phenotype)

255.255.255.255