Introduction

Firewall is an essential protective component in an enterprise or academic network environment. It filters packets, blocks malicious connections, and prevents internal hosts from attacks. However, as the number and complexity of firewall rules grow, there are conflicting behaviours between rules. Any error can cause unwanted traffic pass or blocking desired traffic. In the paper Abedin, M., et al., they have proposed four relations between the rules: disjoint, exactly matching, inclusively matching, and correlated. Based on these relations, there are three possible anomalies: shadowing anomaly, correlation anomaly, and redundancy anomaly.
I've implemented the anomaly resolution algorithm in Abedin, M., et al. for resolving for Ryu restful firewall. The code is held at this repository.

Program Structure

There are four classes:
  1. RuleParser: an abstract class that holds a list of rules and defines an abstract function, parse_file
  2. SimpleRuleParser
  3. Rule
  4. AnomalyResolver

SimpleRuleParser

SimpleRuleParser is an implementation of RuleParser that parses a firewall rules file in the following format: 
priority. <direction, source IP, source port, destination IP, destination port, actions>
Each line is a firewall rule. You can implement RuleParser to support different format of firewall rules file.

Rule

Rule contains the following fields which are defined in Ryu restful firewall and OpenFlow Specification. In order to stay flexible, most of these fields are stored in string. 
	_fields_ = [('switch', STRING_TYPE),
	 	# REST_SWITCHID, [ 'all' | Switch ID ]
		('vlan', STRING_TYPE),
		# REST_VLANID, [ 'all' | VLAN ID ]
		('priority', ctypes.c_int),
		# REST_PRIORITY, [ 0 - 65535 ]
		('in_port', STRING_TYPE),
		# REST_IN_PORT, [ 0 - 65535 ]
		('dl_src', STRING_TYPE),
		# REST_SRC_MAC, '<xx:xx:xx:xx:xx:xx>'
		('dl_dst', STRING_TYPE),
		# REST_DST_MAC, '<xx:xx:xx:xx:xx:xx>'
		('dl_type', STRING_TYPE),
		# REST_DL_TYPE, [ 'ARP' | 'IPv4' | 'IPv6' ]
		('nw_src', STRING_TYPE),
		# REST_SRC_IP, '<xxx.xxx.xxx.xxx/xx>'
		('nw_dst', STRING_TYPE),
		# REST_DST_IP, '<xxx.xxx.xxx.xxx/xx>'
		('ipv6_src', STRING_TYPE),
		# REST_SRC_IPV6, '<xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx/xx>'
		('ipv6_dst', STRING_TYPE),
		# REST_DST_IPV6, '<xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx:xxxx/xx>'
		('nw_proto', STRING_TYPE),
		# REST_NW_PROTO, [ 'TCP' | 'UDP' | 'ICMP' | 'ICMPv6' ]
		('tp_src', STRING_TYPE),
		# REST_TP_SRC, [ 0 - 65535 ]
		('tp_dst', STRING_TYPE),
		# REST_TP_DST, [ 0 - 65535 ]
		('direction', STRING_TYPE),
		# [ 'IN' | 'OUT' ]
		('actions', STRING_TYPE)
		# REST_ACTION, [ 'ALLOW' | 'DENY' ]
	]
When initializing a Rule, _sanity_check is called to check whether the string in each field is valid.
disjoint, issubset, and contiguous check the relations between two rules. issubset is inclusively matching in the paper.

AnomalyResolver

detect_anomalies accepts a rules list and reports any detected anomaly.
resolve_anomalies follows the algorithm describe in the paper. First, create a new rules list, insert old rules into it one by one, and check for redundancy.
  • insert checks if a rule is disjoint with rules inside the new rules list. If not, resolve for these two rules.
  • resolve performs anomaly detection and resolution by removing, reordering, or calling split.
  • split extracts the parts of the rules which are disjoint to the two rules and creates a new rule with the common part.
merge_contiguous_rules first calls construct_rule_tree, and merge contiguous rules.
  • construct_rule_tree creates a firewall rule tree.
  • tree_insert inserts a rule into a node of the rule tree.
  • get_rule_tree_root
  • merge merges edges of a node representing a contunous range.
  • cut_edge removes an edge from the rule tree.
  • subtree_equal checks if the subtree of an edges is equal to that of the other edge.

Conclusion

Firewall rule anomalies can result in security breaches. However, manual detecting and resolving these anomalies is an error prone task. With this algorithm, we can write a program that resolve any anomaly present in the firewall rules by reoder and split operations.

History

Reference

  1. Detection and Resolution of Anomalies in Firewall Policy Rules
  2. Anomaly Firewall Rule Detection and Resolution