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

• grc: Could you add some test cases?
• John Dvorak: "shortest code" conflicts with "be sensible". Are there any hard requirements for "being sensible"? Note there is always exactly one optimal solution and it's fairly easy to find and verify optimality. You could require that.

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. :)

• Doorknob: You could still remove unnecessary spaces, such as the ones after :s and before the first *. Great first answer on this site! :) +1

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);

• jarnbjo: Won't this solution only consider the subnets /8, /16 and /24?
• HamZa: @jarnbjo correct, but it will write the rest without /x. For examlpe in this case it will write 1.2.3.0 ALLOW\r\n1.2.3.1 ALLOW\r\n 1.2.3.2 ALLOW\r\n1.2.3.3 ALLOW\r\n1.2.3.5 ALLOW ....
• jarnbjo: The shortest rule list to block only 0.1.2.3 would require the rule "0.1.2.0/31 ALLOW" instead of allowing the IP addresses 0.1.2.0 and 0.1.2.1 separately.
• HamZa: @jarnbjo I know, but if I would take that into consideration the code will be too huge, I'm already using PHP so I'm suffering enough from the code length. Besides it isn't specified by the OP :)
• jarnbjo: I assumed that returning the shortest rule list is part of the "being sensible" requirement. Otherwise you could shorten your code a lot and simply output each allowed IP address, but that's obviously not what's asked for either.