* Overview

I will write a tool to help understand and modify iptables config. This tool can answer questions like "What does chain X do to packets that look like this ?" and "Modify chain X to ACCEPT/DROP/REJECT packets that look like this". It will help iptables config management.

* The need it fulfils

A tool that could help to understand and modify the scary iptables config file in a way that avoiding redundant rules would be very useful. When a program needs to modify the config file, it can get the chain required as output only by inputting the original chain and the modification requirements to this tool. And the tool can ensure that the firewall is consistent, complete and compact. An optimized iptables config without redundant rules will help to save a lot of CPU cycles.

* Implementation

The main theoretical background for this tool is described in [2]. The firewall decision diagram (FDD, for short) is the data structure model representing the firewall and it helps to ensure the consistency and the completeness. Five algorithms based on the FDD given in the paper are the complete solution for generating optimized and simple firewall from the FDD. The paper covers a large enough subset that will be used in practice. The FDD is friendly for implementation, since it is an acyclic directed graph. Many of the operations on the FDD are similar to those on directed graph. By using the methods provided in the paper for minimizing the firewall rules, so we could get a good amount of optimization.

(1) Construct data structures to represent FDDs and perform basic operations on them.
(2) Implement methods to parse one iptables chain into an FDD.
(3) Implement operation (a) described as "What does chain X do to packets that look like this ?" from above based on that representation.
(4) Implement operation (b) described as "Modify chain X to ACCEPT/DROP/REJECT packets that look like this ?".
(5) Output an iptables chain from the FDD.

The basic data model used would be based on how packets are actually represented. A packet consists of a header and some payload where the header is of a fixed length. A header has a number of parent fields and values that those fields must match. A field is an offset and length (in bits) in a header. The fields in the FDD are relevant to the fields in the packet header. For some match criteria that don't have a direct representation in the packet, we would invent pseudo-headers and fields. The program can describe all the criteria for matching that iptables provides as data by using such a data model.

The frameworks for operation (a) and (b) are as follows. Operation (a) can be done by traveling the FDD. The result is the label on the terminal node. But values for some of the fields in the FDD are not set in input, since the input is a description of a set of packets rather than a packet. We would output information on what happens for any value of these fields. This can be done by reducing the FDD as the follow steps: reduce the FDD by using the values for fields that are known, only keeping those parts of the FDD that are reachable when these fields has the values given, then output that reduced FDD. For Operation (b): First, parse all the current iptables chain to the FDD. Second, parse the rules given by the user to this FDD. Third, minimize the FDD, using the five algorithms introduced in the paper [2]. Finally, output the iptables chain. We will avoid outputting anything if the user-supplied rules are already represented in the FDD.

This tool was planned to be implemented in the OCaml programming language. OCaml is a very powerful functional language and it would be much easier to complete this  project in OCaml. But I intend to implement this project in C now. I am very sorry for the time delayed and the change of the programming language.

Since the number of options and possible rules for iptables is overwhelming, I will stick with a relatively small subset of iptables match criteria and then expand that over time once the overall program is working.

References:

[1] https://www.ericzma.com
[2] http://www.cse.msu.edu/~alexliu/publications/FDD/fdd.pdf
[3] http://www.networksorcery.com/enp/protocol/tcp.htm