Firewall Rule Testing with BASH and TCPTraceRoute

I wanted to block the use of any DNS server except those that I select (google, openDNS and my router).

I also wanted to make sure that these DNS servers work and that others do not.

So I made a BASH script to verify my firewall rules.

#!/bin/bash

# only particular DNS servicer are allowed to be contacted. 

# this tests that this is so

LOCAL="the.IP.address.of.your.router"

ALLOW="8.8.8.8 8.8.4.4 208.67.220.220 208.67.222.222"

BLOCK="220.233.0.4 61.88.88.88 202.139.83.3 61.9.194.49 61.9.195.193 61.9.133.193 61.9.134.49 203.161.158.2"

echo "Testing DNS servers via UDP that are allowed to work..."

for d in $LOCAL $ALLOW; do

  dig @$d somename +time=1 +tries=1 +notcp > /dev/null

  [ $? -ne 0 ] && echo "FAIL: Failed to get response from $d via UDP." && exit 1

  echo "PASS: $d responded via UDP."

done

echo "Testing DNS servers via TCP that are allowed to work..."

for d in $LOCAL $ALLOW; do

  dig @$d somename +time=1 +tries=1 +tcp > /dev/null

  [ $? -ne 0 ] && echo "FAIL: Failed to get response from $d via TCP." && exit 1

  echo "PASS: $d responded via TCP."

done

echo "Testing DNS servers via UDP that are NOT allowed to work..."

for d in $BLOCK; do 

  dig @$d somename +time=1 +tries=1 +notcp > /dev/null 

  [ $? -eq 0 ] && echo "FAIL: Got response from blocked DNS server $d via UDP." && exit 1 

  echo "PASS: DNS server $d via UDP was correctly blocked." 

done 

echo "Testing DNS servers via TCP that are NOT allowed to work..." 

for d in $BLOCK; do 

  dig @$d somename +time=1 +tries=1 +tcp > /dev/null 

  [ $? -eq 0 ] && echo "FAIL: Got response from blocked DNS server $d via TCP." && exit 1 

  echo "PASS: DNS server $d via TCP was correctly blocked." 

done 

echo "" 

echo "Firewall PASSed."

Then I thought that I might be able to test other TCP blocking rules by setting the IP packet's time-to-live (TTL) to a small number and looking for ICMP time expired packets. To do this I needed to use tcptraceroute to get the core functionality. On the Mac I got this from fink.

If I get some response, the firewall is NOT blocking an outgoing port. If I get stars (* * *) then it probably is blocking the port.

#!/bin/bash

echo "Testing blocked outgoing port..."

# set TTL to 2 hops: host to ADSL router, ADSL router to ISP gateway

# if the ISP responds to TCP TTL timeouts then a blocked port should get '2  *'

# whereas an open outgoing port should get something more complicated like this:

# '2  37.1.233.220.static.exetel.com.au (220.233.1.37)  23.176 ms'

#sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 www.google.com 79 | grep '2  *' && echo "blocked"

BLOCK="135 136 137 138 139 445 593 1863 110 9000 5190 23 1503 1720 53"

VICTIM="www.some.real.site.com"

# The victim should not get any packets if the firewall rules are right.

for p in $BLOCK; do

  sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 $VICTIM $p | grep '2  \*'

  [ $? -ne 0 ] && echo "FAIL: Port $p is open for outgoing traffic." && exit 1

  echo "PASS: Port $p is blocked for outgoing traffic."

  echo ""

done

ALLOW="80 8080 443 25 21 119 22 123"

VICTIM="www.some.real.site.com"

# again, the victim should not get any packets since TTL is so small.

for p in $ALLOW; do

  sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 $VICTIM $p | grep '2  \*'

  [ $? -eq 0 ] && echo "FAIL: Port $p is blocked for outgoing traffic." && exit 1

  echo "PASS: Port $p is open for outgoing traffic."

  echo ""

done

echo "" 

echo "Firewall PASSed."

You will need to modify the script to suit your firewall rules.

Simple Rolling Hash- Part 3

The Rolling Hash

Now that there is a way to remove the first character and append a new last character (in constant time) to a string hash value, we can also use this hash function suite to perform substring searches in linear time.

To find a substring of length m in a string of length n you might proceed as follows:

Start at the first character of the string

Compare the substring to the string for m characters.

If same, then the substring is found.

else, repeat from the next character of the string (stop when there are less than m characters left in the string)

In practice this works well since it is unlikely that more than a few character will match each round so the effective time efficiency is much less than O(N x M). But for some strings, such as DNA which have small alphabets, the number of matches in each round could be large.

By using a rolling hash this can be reduced to linear-time.

Calculate the hash of the substring we are searching for.

Start with a hash of the first m characters of the string

If the hash values match then the substring is found - probably.

else remove the first character of the string from the hash and add the m+1 th character to the hash.

Now the hash is of m characters from the next character of the string.

This process is O(N).

The catch is that this finds a substring with high probability. To ensure that it is a match we need to check each character.

A Good Hash Function

My next question was 'is this hash good enough?'.

After some research I found that hashing is similar to a problem called Balls and Bins. The idea is to analyse mathematically the result of randomly throwing m balls into n bins.

It turns out that if a hash function is 'good' then it should produce results similar to randomly throwing balls (strings) into bins (string hash numbers).

I am no mathematician so this was slow going and a bit frustrating since I don't know all the tricks used to simplify problems.

I found that for a good hash function, the number of unused hash numbers after generating hash numbers from n random-like strings should be n/e. This is easy to test: I made an array of size n, generated random strings, hashed them, and incremented the element of the array indexed by the hash number.

(To keep the array size small, I first reduced the 28 bit hash number to a 16 bit number by mod 65536).

The probability that a hash number was used once is also n/e. And likewise it is easy to calculate the probabilities of a hash number being used k times:

Pr[ k ] = 1/ek!

And the probability that a hash number is used k or more times is roughly

Pr[ >=k ] ~ ((e/k)**k)/e

(to be completed)