#!/usr/bin/python
'''
acllint - show redundant ACL lines
options:
  filename ...        name of acl file to analyse
  -c  'acl line 1' 'acl line 2'
         compare the two given ACL lines
  -d  increase debugging level
  -h, --help print this help text
examples:
acllint monash.acl
acllint sn048.acl 

TODO:
 - inteligently interpret "options" at end of ACL,
   eg established, echo, unreachable

Written by Kim Oldfield, 2005-2012
$Id: acllint,v 1.4 2012/07/22 12:30:11 kim Exp kim $
'''
copyright = '''
Copyright (C) 2005, Kim Oldfield.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License version 2 as
published by the Free Software Foundation, http://www.gnu.org/

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.
'''

import sys, re, struct, fileinput, socket
from pprint import pprint

debug = 0

def ip2int(ip):
	# print 'ip:', ip
	if ip.isdigit(): # IPv6 mask
		masklen = int(ip)
		return ~ ((2 ** masklen - 1) << (128 - masklen))
	elif ':' in ip: # IPv6
		try:
			s = socket.inet_pton(socket.AF_INET6, ip)
		except socket.error, msg:
			print 'Error converting %s to an IPv6 number: %s' % (`ip`, msg)
			return 0
		n = 0
		for i in s:
			n *= 256
			n += ord(i)
		return n
	else: # IPv4
		if ip == '255.255.255.255':
			# in old python versions inet_aton dies on 255.255.255.255
			return -1
		#return struct.unpack('>i', socket.inet_aton(ip))[0]
		try:
			return struct.unpack('>i', socket.inet_pton(socket.AF_INET, ip))[0]
		except socket.error, msg:
			print 'Error converting %s to an IPv4 number: %s' % (`ip`, msg)
			return 0

def int2ip(n):
	print 'int2ip(%s)' % `n`
	if n >= 2**32: # IPv6
		s = ''.join([ (n >> (8*(15-i))) & 0xff for i in range(16) ])
		return socket.inet_ntop(socket.AF_INET6, s)
	else: # IPv4
		return socket.inet_ntoa(struct.pack('>i', n))

def toipmask(s):
	'''
	converts a cisco acl definition for:
	 - host xxx,
	 - any, or
	 - xxx yyy (wildcard mask)
	to an (ip, netmask) pair
	'''
	if s == 'any':
		return 0, 0
	if s.startswith('host'):
		b = s.split(None, 1)[1]
		return ip2int(b), ip2int('255.255.255.255')
	if '/' in s: # IPv6
		a, b = s.split('/', 1)
	else: # IPv4
		a, b = s.split(None, 1)
	ip = ip2int(a)
	mask = ~ ip2int(b)
	if ip & ~ mask:
		print 'Warning: bits set within mask:', `s`
		ip = ip & mask
	return ip, mask

def readservices():
	services = {'tcp': {}, 'udp': {}}
	for line in fileinput.input('/etc/services'):
		if re.search(r'^\s*(\#.*)?$', line):
			# skip comment only or blank line
			continue
		m = re.search(r'''^(?P<service>\S+)
			\s+(?P<port>\d+)\/(?P<proto>tcp|udp)
			(?P<alias>(\s+[-\w]+)*)
			(?P<comment>\s*\#.*)?
			\s*$''',
			line, re.VERBOSE)
		if m:
			#print `line`
			#print m.groups()
			dict = services[m.group('proto')]
			if dict.has_key(m.group('service')):
				if debug:
					print 'Duplicate %s service: %s' % (m.group('proto'), m.group('service'))
			else:
				dict[m.group('service')] = int(m.group('port'))
			if m.group('alias'):
				aliases = m.group('alias').split()
				for i in aliases:
					if dict.has_key(i):
						if debug:
							print 'Duplicate %s service alias: %s' % (m.group('proto'), i)
					else:
						dict[i] = int(m.group('port'))
		else: # ignore unmatched lines
			if debug:
				print 'Ignoring service line:', `line`
	# add some names which are used by IOS, but not in /etc/services
	# port numbers from http://www.cs.sfu.ca/CC/401/tiko/lecnotes/ch3.3.pdf
	dict = services['tcp']
	for name, port in (
		('lpd', 515),
		('netbios-ns', 137),
		('netbios-dg', 138),
		('netbios-ss', 139),
		):
		if not dict.has_key(name):
			dict[name] = port
	dict = services['udp']
	for name, port in (
		('netbios-ns', 137),
		('netbios-dg', 138),
		('netbios-ss', 139),
		('nameserver', 42),
		):
		if not dict.has_key(name):
			dict[name] = port
	return services

def torange(s, p):
	'''
	converts a cisco acl port specification
	p = protocole, tcp or udp
	s = string, one of
	  - eq
	  - lt
	  - gt
	  - range x y
	to a port range (lower, upper)
	'''
	if s == None:	# no restriction => allports
		return 0, 0xffff
	list = s.split()
	if list[0] == 'eq':
		return port2int(list[1], p), port2int(list[1], p)
	if list[0] == 'lt':
		return 0, port2int(list[1], p)
	if list[0] == 'gt':
		return port2int(list[1], p), 0xffff
	if list[0] == 'range':
		return port2int(list[1], p), port2int(list[2], p)
	print 'Unrecognised port defintion:', s
	return 0, 0xffff

def port2int(service, protocol):
	if services[protocol].has_key(service):
		return services[protocol][service]
	return int(service)

aclre = re.compile(r'''^\s*(?P<pd>permit|deny)
	\s+(?P<proto>ip|ipv6|icmp|tcp|udp|pim|gre|esp|\d+)
	\s+(?P<src>any
		|host\s+\d+(\.\d+){3}
		|\d+(\.\d+){3}\s+\d+(\.\d+){3}
		|[0-9a-z:]+/\d{1,3}
		)
	(\s+(?P<srcport>range\s+[-\w]+\s+[-\w]+|(eq|gt|lt)\s+[-\w]+))?
	\s+(?P<dst>any
		|host\s+\d+(\.\d+){3}
		|\d+(\.\d+){3}\s+\d+(\.\d+){3}
		|[0-9a-z:]+/\d{1,3}
		)
	(\s+(?P<dstport>range\s+[-\w]+\s+[-\w]+|(eq|gt|lt)\s+[-\w]+))?
	(\s+(?P<opt>established|echo(-request|-reply)?|(port-)?unreachable
		|fragments|packet-too-big|time-exceeded|administratively-prohibited
		|nd-n[as]
		))*
	(\s+(?P<log>log|log-input))*
	\s*(?P<comment>\!.*)?
	$''', re.VERBOSE)

'''
IP address examples:

a = 172.18.242.0 / 255.254.254.0 (ie not a /x mask) (wildcard 0.1.001.255)
b = 172.18.000.0 / 255.255.000.0 (ie /16) (wildcard 0.0.255.255)
c = 172.18.242.0 / 255.255.255.0 (ie /24) (wildcard 0.0.000.255)

c << b
  c[0] & b[1] = 172.18.0.0 = b[0]

b !<<
a overlaps b
  

a overlaps c

a[0] & b[1] = 172.18.0.0 = b[0]
b[0] & a[1] = 172.18.0.0 != a[0]

11010111 xxxxxxxx
11010xxx 101xxxxx
'''
def compareip(a, b):
	'''
	Compares 2 IP addresses and netmasks
	a and b are both a list/tuple with (ip (as an int), netmask (as an int))
	returns:
	  0  if a == b
	  1  if a is contianed within b
	  2  if b is contianed within a
	  3  if they overlap, but one is not completely contained
	     within the other
	  4  if they don't ever overlap
	'''
	if debug > 2:
		print 'comparip(%s, %s)' % (a, b)
		print 'comparip(%s/%s, %s/%s)' % (int2ip(a[0]), int2ip(a[1]), int2ip(b[0]), int2ip(b[1]))
	if a == b:
		return 0
	if a[0] & b[1] == b[0] and a[1] & b[1] == b[1]: # a << b
		return 1
	if b[0] & a[1] == a[0] and b[1] & a[1] == a[1]: # b << a
		return 2
	if a[0] & b[1] == b[0] & b[1]: # overlap
		return 3
	#if no overlap:
	return 4

def compareport(a, b):
	'''
	Compares two sets of ports (eg (0,44) and (30,50)) and returns:
	  0  if a == b
	  1  if a is contianed within b
	  2  if b is contianed within a
	  3  if they overlap, but one is not completely contained
	     within the other
	  4  if they don't ever overlap
	'''
	if a == b:
		return 0
	if a[0] >= b[0] and a[1] <= b[1]:
		return 1
	if b[0] >= a[0] and b[1] <= a[1]:
		return 2
	if a[0] > b[1] or a[1] < b[0]:
		return 4
	return 3

def compareproto(a, b):
	'''
	Compares 2 protocols (eg ip & tcp) and returns:
	  0  if a == b
	  1  if a is contianed within b
	  2  if b is contianed within a
	  3  if they overlap, but one is not completely contained
	     within the other
	  4  if they don't ever overlap
	'''
	if a == b:
		return 0
	if b == 'ip':
		return 1
	if a == 'ip':
		return 2
	return 4

def compareopt(a, b):
	'Compare options, eg echo, established, etc'
	if a == b:
		return 0
	if a and not b:
		return 1
	if b and not a:
		return 2
	return 4

class aclline:
	def __init__(self, aclline):
		# aclline = (line number, text of line)
		# stip comments and leading or trailing whitespace
		#print `aclline`
		if debug:
			print 'Compiling line:', `aclline`
		if type(aclline) == type(''):
			self.lineno = '-1'
			self.line = aclline.strip()
		else:
			self.lineno = aclline[0]
			self.line = aclline[1].strip()
		m = aclre.search(self.line)
		if not m:
			self.valid = 0
			return	# empty line
		self.valid = 1
		if m.group('pd') == 'permit':
			self.permit = 1
		elif m.group('pd') == 'deny':
			self.permit = 0
		else:
			print '%s isn\'t permit or deny' % `m.group('pd')`
		self.proto = m.group('proto')
		self.src = toipmask(m.group('src'))
		self.srcport = torange(m.group('srcport'), self.proto)
		self.dst = toipmask(m.group('dst'))
		self.dstport = torange(m.group('dstport'), self.proto)
		self.opt = m.group('opt')
		self.log = m.group('log')
		self.comment = m.group('comment')

	def __nonzero__(self):
		return self.valid

	def __str__(a):
		# a = acl
		# s = string
		if not a.valid:
			return 'Invalid aclline'
		if a.permit:
			s = 'permit'
		else:
			s = 'deny'
		s += ' %s %s/%s [%i:%i] => %s/%s [%i:%i]' % (
			a.proto,
			int2ip(a.src[0]), int2ip(a.src[1]),
			a.srcport[0], a.srcport[1],
			int2ip(a.dst[0]), int2ip(a.dst[1]),
			a.dstport[0], a.dstport[1] )
		if a.opt:
			s += ' ' + a.opt
		if a.log:
			s += ',' + a.log
		return s

	def compare(a, b):
		'''
		returns:
		  0  if a == b
		  1  if a is contianed within b
		  2  if b is contianed within a
		  3  if they overlap, but one is not completely contained
		     within the other
		  4  if they don't ever overlap
		'''
		c = []
		proto = compareproto(a.proto, b.proto)
		ipsrc = compareip(a.src, b.src)
		ipdst = compareip(a.dst, b.dst)
		portsrc = compareport(a.srcport, b.srcport)
		portdst = compareport(a.dstport, b.dstport)
		opt = compareopt(a.opt, b.opt)
		if debug > 2:
			print 'aclline.compare(A, B):'
			print ' A:', a
			print ' B:', b
			print ' proto=%s ipsrc=%s ipdst=%s portsrc=%s portdst=%s opt=%s' % (proto, ipsrc, ipdst, portsrc, portdst, opt)
		#if portsrc == 3 or portdst == 3:
		#	return 3
		if ipsrc == 4 or ipdst == 4:
			return 4
		if proto == 0:
			if ipsrc==0 and ipdst==0 and portsrc==0 and portdst==0 and opt==0:
				return 0
			if ipsrc==4 or ipdst==4 or portsrc==4 or portdst==4 or opt==4:
				return 4
			if ipsrc in (0,1) and ipdst in (0,1) and portsrc in (0,1) and portdst in (0,1) and opt in (0,1):
				return 1
			if ipsrc in (0,2) and ipdst in (0,2) and portsrc in (0,2) and portdst in (0,2) and opt in (0,2):
				return 2
			return 3
		elif proto == 1:
			if ipsrc in (0,1) and ipdst in (0,1) and opt in (0,1):
				return 1
			else:
				return 3
		elif proto == 2:
			if ipsrc in (0,2) and ipdst in (0,2) and opt in (0,2):
				return 2
			else:
				return 3
		elif proto == 4:
			return 4
		print 'What about this situation?'
		print 'proto=%i ipsrc=%i ipdst=%i portsrc=%i portdst=%i' % \
			(proto, ipsrc, ipdst, portsrc, portdst)
		print 'A:', a.line
		print 'B:', b.line

def isdenyanyany(acl):
	'Check is acl is equivalent to "deny ip any any"'
	allip = toipmask('any')
	allport = torange(None, acl.proto)
	if acl.proto != 'ip' or acl.src != allip or acl.dst != allip or \
	   acl.srcport != allport or acl.dstport != allport or acl.opt:
		return 0
	return 1

def checkacl(acllist, name=None):
	'''
	Analyse the given ACL
	acl is a list of strings, one per line of the ACL
	name is the file/ACL name which is printed if a problem is found
	'''
	if debug:
		print 'checkacl(acllist, %s)' % `name`
	if name:	
		printname = 0
	else:	# no name specified, don't bother printing it
		printname = 1
	acl = [ aclline(i) for i in acllist ]
	if len(acl) and not isdenyanyany(acl[-1]):
		acl.append(aclline((acllist[-1][0]+1, 'deny ip any any ! implicit end')))
	for i in range(len(acl)):
		acl1 = acl[i]
		overlap = []
		if debug:
			print 'ACL:', acl1.line
		for j in range(i+1, len(acl)):
			acl2 = acl[j]
			mes = ''
			c = acl1.compare(acl2)
			if debug > 1:
				print ' comparing(c=%i): %s' % (c, acl2.line)
				#print ' len(overlap) =', len(overlap)
			if c == 0:
				mes = 'ACL lines are the same.'
			elif c == 1 and acl1.permit == acl2.permit and not overlap:
				mes = 'Line %i makes line %i redundant.' % (acl2.lineno, acl1.lineno)
			elif c == 2:
				mes = 'Line %i will never match due to line %i.' % (acl2.lineno, acl1.lineno)
			#elif c == 3:
			#	print ' overlap:', acl2.line
			if acl1.permit != acl2.permit and c in (1, 3):
				overlap.append(acl2)
			if mes:
				if not printname:
					print
					print name
					printname = 1
				print mes
				print '%5i: %s' % (acl1.lineno, acl1.line)
				print '%5i: %s' % (acl2.lineno, acl2.line)

def checkfile(filename):
	'''
	Read in the given filename, search for anything which looks like
	an ACL within it, and analyse it.
	Repeat for all ACLs found in the file.
	'''
	aclstartre = re.compile(r'^ip(v6)?\s+access-list(\s+extended)?\s+(?P<name>[-\w]+)$')
	permitdenyre = re.compile(r'^\s*(permit|deny)\s')
	blankre = re.compile(r'^\s*((\!|remark\s+).*)?$')
	printfilename = 0
	try:
		aclname = None
		fh = open(filename)
		lineno = 0
		while 1:
			line = fh.readline()
			lineno += 1
			if not line:
				break
			inacl = -1
			# stip comments and leading or trailing whitespace
			m = blankre.search(line)
			if m:
				continue	# ignore empty lines
			line = line.strip()
			m = aclstartre.search(line)
			if m:
				# start of new ACL
				if aclname != None:
					# we were already in an ACL, check previous ACL
					checkacl(aclall, 'Filename %s, ACL: %s' % (filename, aclname))
				aclname = m.group('name')
				aclall = []
			elif aclname != None:
				# we are currently in an ACL
				m = aclre.search(line)
				if m:
					aclall.append((lineno, line))
				elif permitdenyre.search(line):
					if not printfilename:
						print
						print 'Filename:', filename
						printfilename = 1
					print 'Unrecognised ACL line:'
					print '%5s: %s' % (lineno, line)
				else:
					# end of ACL
					checkacl(aclall, 'Filename %s, ACL: %s' % (filename, aclname))
					aclname = None
			else:
				# we are not in an ACL
				m = aclre.search(line)
				if m:
					if not printfilename:
						print
						print 'Filename:', filename
						printfilename = 1
					print 'Found this ACL line not in an access-list:'
					print '%5s: %s' % (lineno, line)
					print 'Assuming it is the first line of a new ACL.'
					aclname = 'anonymous'
					aclall = [(lineno, line)]
		if aclname:
			checkacl(aclall)
	except IOError, msg:
		print 'IOError attempting to read file %s: %s' % (`filename`, msg)

def main():
	global debug, services
	args = sys.argv[1:]
	if len(sys.argv) <= 1 or '--help' in args or '-h' in args:
		print __doc__
		return
	while '-d' in args:
		debug += 1
		args.remove('-d')
	services = readservices()
	if args[0] == '-c':
		# compare 2 acls on the command line
		# useful for debuging
		if len(args) != 3:
			print __doc__
			return
		acl1 = aclline(args[1])
		acl2 = aclline(args[2])
		print 'ACL A:'
		print ' ', `acl1.line`
		print ' ', acl1
		print 'ACL B:'
		print ' ', `acl2.line`
		print ' ', acl2
		print 'Comparing:'
		r = acl1.compare(acl2)
		resulttable = { 0: 'ACLs are the same',
			1: 'A is contained within B',
			2: 'B is contained within A',
			3: 'they partially overlap, but one is not completely contained within the other',
			4: 'they don\'t overlap at all'
			}
		print 'Comparison returned %i which means' % r
		print resulttable[r]
	else:
		for filename in args:
			#print
			#print 'Reading file:', filename
			checkfile(filename)

if __name__ == '__main__':
	main()