Writing firewall rules

Question

Congratulations, you're now a network administrator! As your first task you will need to configure a firewall to stop any traffic to some blacklisted addresses.

Unfortunately, the only firewall at your disposal only takes in rules in this format:

x.y.z.t/m ALLOW

There's no DENY keyword. If you want to exclude a specific address, you'll have to write a lot of rules to allow everything except that address. If you want to exclude more than one address or a whole range, then you're in luck because these ALLOW rules will overlap to some degree.

The challenge

You are given a list of blacklisted IPs. Write a program that will print out rules for our firewall. Also, be sensible when writing rules: don't just enumerate all 256^4 and don't print out duplicates.

Code golf rules apply: shortest code wins

*this problem is inspired by a real life assignment; a friend actually needed this done

Example

To block address 0.1.2.3 you could write the following ALLOW rules (this is not the only solution possible, and it's certainly not the shortest):

0.1.2.0 ALLOW
0.1.2.1 ALLOW
0.1.2.2 ALLOW
0.1.2.4 ALLOW
...
0.1.2.255 ALLOW

0.1.0.0/24 ALLOW
0.1.1.0/24 ALLOW
0.1.4.0/24 ALLOW
...
0.1.255.0/24 ALLOW

0.0.0.0/16 ALLOW
0.2.0.0/16 ALLOW
...
0.255.0.0/16 ALLOW

1.0.0.0/8 ALLOW
...
255.0.0.0/8 ALLOW

Answer 1

Python3 - 325 chars

import sys
r=[(0,32)]
for b in (int('%02x'*4%tuple(int(x) for x in y.split('.')),16) for y in sys.stdin):
 i=0
 while i<len(r):l,q=r[i];o=2**q//2;m=l+o;h=m+o;k=l<=b<h;r[i:i+1]=[(l,q-k),(m,q-k)][0:k+1*(not l==h==b)];i+=1-k
for n,m in r:print('%s/%d ALLOW'%('.'.join(str(int(('%08x'%n)[i:i+2],16)) for i in range(0,8,2)),32-m))

Answer 2

Python 3: 253 characters

Yay, Python!

from ipaddress import *
import sys
def e(x,a):
 b=[]
 for i in a:
  try: b+=i.address_exclude(ip_network(x))
  except ValueError: b+=[i]
 return b
a=[ip_network('0.0.0.0/0')]
for h in sys.stdin:
 for i in h.split(): a=e(i,a)
for i in a: print(i,'ALLOW')

It accepts a list of addresses on stdin, separated by any (ASCII) whitespace you like (no commas, though).

You can save 12 characters by replacing the stdin loop with for i in sys.stdin: a=e(i.strip(),a). The strip() is necessary to get rid of a trailing newline anyway, though, so I figured I'd use split() and another for loop and allow any whitespace.

You can probably save a few more characters by moving the code out of that pesky function. I didn't because I figured I was already confusing myself enough.

You can also make it work for IPv6 instead by changing only one line.

Ungolfed version:

#!/usr/bin/env python3

import ipaddress
import sys

def exclude(address, networks):
    new_networks = []
    for network in networks:
        try:
            new_networks.extend(network.address_exclude(ipaddress.ip_network(address)))
        except ValueError:
            new_networks.append(network)
        except TypeError:
            pass
    return new_networks

networks = [ipaddress.IPv6Network('::/0'), ipaddress.IPv4Network('0.0.0.0/0')]
for line in sys.stdin:
    for address in line.split():
        networks = exclude(line, networks)

for network in networks:
    print(network)

This one has the added benefit of working for IPv4 and IPv6, no tweaking necessary. :)

Answer 3

PHP 5.3, 465 characters

$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

Usage:

$w = array('2.5.5.4', '1.2.3.4');
$p = 'data.txt';
$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

This will write to data.txt

Uncompressed:

$deny = array('2.5.5.4', '1.2.3.4');
$file = 'data.txt';

$list = array_map(function($v){return explode('.', $v);}, $deny);
$l = 256;
$n = " ALLOW\r\n";$o = '';

$first = $second = $third = $fourth = range(0,$l-1);
foreach($list as $ip){unset($first[$ip[0]], $second[$ip[1]], $third[$ip[2]], $fourth[$ip[3]]);}
    
for($x=0;$x<$l;$x++){
    for($y=0;$y<$l;$y++){
        for($z=0;$z<$l;$z++){
            for($t=0;$t<$l;$t++){
                if(isset($first[$x])){
                    $o .= "$x.0.0.0/8$n";break 3;
                }else{
                    if(isset($second[$y])){
                        $o.="$x.$y.0.0/16$n";break 2;
                    }else{
                        if(isset($third[$z])){
                            $o.="$x.$y.$z.0/24$n";break 1;
                        }else{
                            if(isset($fourth[$t])){
                                $o.="$x.$y.$z.$t$n";
                            }
                        }
                    }
                }
            }
        }
    }
}

file_put_contents($file, $o);