<repo_name>milo-trujillo/CriticalityTest<file_sep>/README.md
# Criticality Test

*<NAME>*

The Internet is a hybrid system - at a high level it is widely decentralized and redundant, but at local levels the network topology is often very rigidly structured. But how centralized *is* our network connection? How many ‘hops’ out to the Internet are critical hubs, any one of which failing would cut us off from the wider world?

This is a tool for auto-detecting the degree of local network centralization. This tool will explore routing information to reach a number of geographically diverse servers (three across the United States, more in Japan, India, Australia, and England). In a decentralized network the routes to reach each of these systems would be completely different. However, by identifying the overlaps between these routes we can determine how many systems are “critical hubs” all of our traffic must flow through before reaching the larger web.

To run the test:

    sudo ./test.py

Results will appear in a few minutes after the traceroutes complete. Creating raw packets requires superuser access, so this tool must be run with `sudo`.

**NOTE**

At present this tool is only known to work on OSX. It will probably run correctly on any BSD system. However, it does *not* work on Linux systems. I think the Linux kernel steps on one of the IP or UDP headers I create and overrides information I was using for tracking responses.
<file_sep>/test.py
#!/usr/bin/env python

import socket, threading, random
from traceroute import traceroute

"""
	The following hosts were chosen because we confirmed that their webhosting
	is located at the locations their names specify. That is, we send a
	traceroute to:
		- Seattle, Washington
		- Austin, Texas
		- Portland, Maine
		- London, UK
		- Melbourne, Australia
		- Tokyo, Japan
		- Shakarpur, India
	These destinations are geographically diverse enough that the routes taken
	should significantly differ to reach at least one.
"""
Hosts = ["www.seattle.gov", "austintexas.gov", "www1.maine.gov", "cityoflondon.gov.uk", "australia.gov.au", "www.jnto.go.jp", "india.gov.in"]
Timeout = 120 # Maximum seconds to spend reaching any destination
BasePort = 33434 # Traceroute uses ports 33434 through 33534

def column(matrix, i):
	return [row[i] for row in matrix]

# This finds the common hosts at the start of every route
def findCommonHops(routes):
	if( len(routes) == 0 ):
		return []

	# Find the shortest route - we can't have any critical hops past that length
	minLen = len(routes[0])
	for r in routes:
		if( len(r) < minLen ):
			minLen = len(r)

	commonHops = []
	for i in range(0, minLen):
		col = column(routes, i)
		match = all(x == col[0] for x in col)
		if( match ):
			commonHops += [col[0]]
		else:
			return commonHops
	return commonHops 

# Reverse lookup, get a domain name for an IP address if possible
def getHostname(IP):
	try:
		name, alias, addresslist = socket.gethostbyaddr(host)
		return name
	except (socket.error, socket.herror, socket.gaierror, socket.timeout):
		return "Unknown Host"

if __name__ == "__main__":
	routes = []
	routeLock = threading.RLock()
	threads = []

	random.seed()

	print "Initating test. Spinning up traceroutes to %d destinations." % (len(Hosts))
	#for i in range(0, 1):
	for i in range(0, len(Hosts)):
		host = Hosts[i]
		# Choose a random high port that's unlikely to be listened to
		port = random.randint(33434, 65500)
		worker = threading.Thread(
			target=traceroute, 
			args=(host, port, routes, routeLock))
		threads += [worker]
		worker.start()

	print "Please be patient, it can take a few minutes to collect our data..."

	for i in range(0, len(threads)):
		threads[i].join()

	print ""
	print "================================================"
	print "All traceroutes complete. Summary is as follows."
	print "================================================"
	print ""

	common = findCommonHops(routes)

	print "Leading common hosts in all routes: %d" % (len(common))
	for host in common:
		name = getHostname(host)
		print "%s\t(%s)" % (host, name)
<file_sep>/traceroute.py
#!/usr/bin/env python

import socket, select, copy, struct

# Maximum TTL before we abort
MaxHops = 30
# How many seconds before we abort a certain TTL step
Timeout = 5
# If debug is enabled we print every step as received
Debug = False

"""
Traceroute implementation based on: 
 https://blogs.oracle.com/ksplice/entry/learning_by_doing_writing_your
However, unlike that example I implement the black magic used in BSD
to solve the multiple copies of traceroute problem.
You can read what I mean in the FreeBSD source code:
    /usr/src/contrib/traceroute/traceroute.c

I use random numbers instead of PIDs, but it's the same principle.
I also used example code to parse the ICMP header myself:
    https://gist.github.com/pklaus/856268
"""
def traceroute(host, port, routes, lock):
	dest = socket.gethostbyname(host)
	icmp = socket.getprotobyname('icmp')
	udp = socket.getprotobyname('udp')
	ttl = 1
	route = []

	with lock:
		print "Attempting to reach %s at %s using port %d" % (host, dest, port)
	while True:
		recv_socket = None
		send_socket = None
		
		try:
			recv_socket = socket.socket(socket.AF_INET, socket.SOCK_RAW, icmp)
			#send_socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, udp)
			# Luke, you switched off your targeting computer! What's wrong?
			# Nothing. I'm alright. Just writing all my packets by hand.
			send_socket = socket.socket(socket.AF_INET, socket.SOCK_RAW, socket.IPPROTO_RAW)
		except socket.error:
			print "Unable to create raw socket. Try running as root?"
			return

		# Set up our sockets and send a UDP probe to our next hop
		try:
			send_socket.setsockopt(socket.SOL_IP, socket.IP_TTL, ttl)
			recv_socket.bind(("", port + ttl))
			send_socket.bind(("", port + ttl)) # THIS IS ESSENTIAL FOR BLACK MAGIC
			probe = makeProbe(port + ttl, ttl, dest, port + ttl, port + ttl)
			send_socket.sendto(probe, (dest, port + ttl))
		except socket.error:
			print "Unable to bind to port %d, perhaps it's already in use?" % (port)
			return

		# Okay, now let's try to receive an ICMP echo response for that UDP probe
		# This may or may not succeed, depending on the host we sent to
		addr = None
		try:
			# We use select to enforce a timeout. We also need to ignore packets
			# destined for other traceroute instances.
			while( True ):
				ready = select.select([recv_socket], [], [], Timeout)
				if( ready[0] ):
					# Blocksize doesn't matter much, we use 512
					data, src = recv_socket.recvfrom(512)
					n = len(data)
					sig = getICMPid(data)
					src = src[0] # Extract just IP, not port
					if( Debug ):
						print "Read %d bytes from %s with signature: %s" % (n, src, sig)
					if( sig >= port and sig <= port + MaxHops ):
						addr = src
						break
				else:
					break
		except socket.error:
			pass
		finally:
			send_socket.close()
			recv_socket.close()

		# Okay, at this point we're done trying to receive a packet.
		# We either got an appropriate one from 'addr', or we hit
		# our timeout and 'addr' is set to None.

		if( addr is None ):
			addr = "*"

		if( Debug ):
			print "%d\t%s" % (ttl, addr)
	
		# Record the newly found hop in the route.	
		route += [copy.deepcopy(addr)]
		ttl += 1

		# If we're done then record our route in the global routing list
		if( addr == dest or ttl > MaxHops ):
			with lock:
				routes += [route]
				print "Host '%s' reached. Hops: %d" % (host, ttl)
				if( Debug ):
					print routeToString(route)
			break

def routeToString(route):
	s = ""
	for r in route:
		s += (str(r) + ",")
	if( len(s) > 0 ):
		return s[:-1]
	return ""

"""
 I read how to make a raw IP header from:
	https://stackoverflow.com/questions/24520799
"""
def makeProbe(_id, ttl, dest, srcPrt, dstPrt):
	version = 4 # IPv4
	ihl = 5     # Header length in 32-bit words (5 words == 20 bytes)
	DF = 0      # Optional fields, leaving them blank
	# Length will be filled in by kernel
	Tlen = 0   # Length of data (0) + 20 bytes for ipv4 header + 8 byte udp
	ID = _id    # ID of packet
	Flag = 0    # Flags and fragment offset
	TTL = ttl   # Time to live
	Proto = socket.IPPROTO_UDP # Protocol 17, UDP
	ip_checksum = 0 # Checksum will be automatically filled in
	SIP = socket.inet_aton("0.0.0.0")
	DIP = socket.inet_aton(dest)
	ver_ihl = ver_ihl = (version << 4) + ihl
	#f_f = (Flag << 13) + Fragment
	#ip_hdr =  struct.pack("!BBHHHBBH4s4s", ver_ihl,DF,Tlen,ID,f_f,TTL,Proto,ip_checksum,SIP,DIP)
	#return ip_hdr
	IP_HEADER = struct.pack(
		"!"        # Network (Big endian)
		"2B"       # Version and IHL, DSCP, and ECN
		"3H"       # Total length, ID, Flags and fragment offset
		"2B"       # TTL, protocol
		"H"        # Checksum
		"4s"       # Source IP
		"4s"       # Dest IP
		, ver_ihl, DF, Tlen, ID, Flag, TTL, Proto, ip_checksum, SIP, DIP)

	# UDP uses "source port, dest port, length, checksum
	UDP_HEADER = struct.pack("!4H", srcPrt, dstPrt, 8, 0)
	return IP_HEADER + UDP_HEADER


"""
 This parses the header of an ICMP packet and returns the ID
 Heavily draws from https://gist.github.com/pklaus/856268
"""
def getICMPid(packet):
	icmp_header = packet[20:]
	_type, code = struct.unpack('bb', icmp_header[:2])
	#_type, code, checksum, unused = struct.unpack('bbHL', icmp_header[:8])
	
	# We only care about responses to traceroute (type 11 code 0)
	if( _type != 11 ):
		return -1

	# ICMP header for type 11 will be:
	# Type / code (2 bytes)
	# Checksum (2 bytes)
	# Unused (4 bytes)
	#
	# That's a total of 8 bytes used. After that we have:
	# IP header (20 bytes?)
	# 8 Bytes of UDP header data
	# So if we just care about the UDP part we should skip 48 bytes in, for:
	# Original IP header (20) + ICMP header (8) + 2nd IP header (20)
	
	# The above math is a little off. By manual examination of the packets
	# in wireshark we know we need to scroll in 52, not 48. Why? Magic.

	return struct.unpack_from('!H', packet, 52)[0]
