The Packet-Filtering Framework

The previous lesson’s oracle was the target’s filter, and looked at from inside the tunnel, that filter could not be told apart from not reaching the target at all. A silently dropped packet sends nothing back; there is a timeout for the sender, no event at all for the destination. This lesson goes inside that filter.

The question to ask is a question of place: how far into this machine did a packet get, and at which stop was the decision made. The answer to this question is not written in a rule list. The list shows what could happen; it does not show which rule actually ran, and the gap between these two sentences is what this lesson measures.

Hops, Tables, and Chains

The packet-filtering framework is made of hooks placed at fixed points in the kernel’s network stack. Each hook holds one or more chains, and chains are grouped by tables. A table is a purpose: raw processing, marking, address translation, filtering. A chain is that purpose’s rule list at a particular hook. When more than one table has a chain at the same hook, their order is fixed by table priority.

The packet’s path splits in two after the routing decision. The dump below is not executed; it is written to show the order among the hooks:

# example dump, not executed
# a packet headed to a local process
interface -> prerouting-raw -> prerouting-nat -> routing-decision
       -> input-mangle -> input-filter -> service

# a packet forwarded to another interface
interface -> prerouting-raw -> prerouting-nat -> routing-decision
       -> forward-filter -> postrouting -> output-interface

The two paths are identical up to the routing decision and never merge again after it. This is the source of a common mistake in diagnosis: the forward chain is examined for a packet that never reaches the local service, when the packet never passed through there at all. Or the reverse happens, and a rule meant for a packet to be forwarded is written into the input chain. The chain’s name states where the decision is made; where the decision is made depends on the path the packet follows.

A chain has two components: ordered rules and a policy. Rules are evaluated top to bottom, the first matching rule makes the decision, and the rest of the chain does not run. If no rule matches, the policy is applied. The dump below is also not executed and is not a real framework’s syntax; it is a simplified notation meant to show how the chain, policy, and order concepts are laid out:

# example dump, not executed, not real syntax
table filter
  chain input   policy drop
    1  state established or related       -> accept
    2  interface loopback                 -> accept
    3  destination port <management-port> -> accept
  chain forward policy drop
  chain output  policy accept

What rule evaluation order changes within a single list was measured in the access control lists lesson of the Cybersecurity curriculum. What is measured here is not order within a list but order among hops: once a packet finds its decision at one hop, the chains of the following hops never run at all, and a rule written there does nothing.

At Which Hop Is the Decision Made

The setup is this: a remote client cannot reach a service on this machine. There are nine candidate causes, and each makes the decision at a specific hop.

• EF21 — The candidate-cause list has nine items and is exhaustive. Three are in the input-filter chain, two on the forwarding path, one at the raw hook, one at the marking hook, one before the interface, one at the service.
• EF22 — The oracle is chosen as input-default-refused: no rule matches, and the chain policy refuses the packet.
• EF23 — The rule set is the same in all nine cases and is 34 lines; what changes is the packet’s fate, not the configuration.
• EF24 — Eight readings are defined, and four of them are measured under two conditions each: counter reading on a loaded and a quiet machine, tracing on and off.
• EF25 — On a loaded machine, background traffic increases every chain’s counters; the counter difference cannot be tied to the test packet.
• EF26 — Tracing must have been turned on before the fault; while off, the lines it produces are 0.
• EF27 — Tracing reports the hop and the reason together; two candidates that drop at the same hop for the same reason still cannot be separated by it.
• EF28 — An accept rule is added to the input-filter chain in two positions: at the head and at the tail. A rule added at the tail is never evaluated if a rule before it already matches.
• EF29 — The candidate set sweep is done with eight-, nine-, and ten-candidate lists.
• EF30 — All counts are exhaustive; there is no randomness or seed.

"""The packet's stops inside the machine: at which hop the decision was made, and which reading sees it."""
LOCAL = ("interface", "prerouting-raw", "prerouting-nat", "routing-decision",
         "input-mangle", "input-filter", "service")
FORWARD = ("interface", "prerouting-raw", "prerouting-nat", "routing-decision",
          "forward-filter", "postrouting", "output-interface")
PATH = {"local": LOCAL, "forward": FORWARD}
CHAIN = {"prerouting-raw", "prerouting-nat", "input-mangle", "input-filter",
          "forward-filter", "postrouting"}
CANDIDATE = {
    "packet-never-arrived": ("local", 0, "none"),
    "prerouting-raw-dropped": ("local", 1, "rule"),
    "input-mangle-dropped": ("local", 4, "rule"),
    "input-filter-rule-dropped": ("local", 5, "rule"),
    "input-default-refused": ("local", 5, "policy"),
    "state-rule-missing": ("local", 5, "rule"),
    "nat-wrong-target": ("forward", 4, "rule"),
    "routing-wrong": ("forward", 4, "rule"),
    "service-not-listening": ("local", 6, "service"),
}
RULE_LINES = 34
ORACLE = "input-default-refused"


def last_hop(a):
    path, i, _ = CANDIDATE[a]
    return PATH[path][i]


def unreached(a):
    path, i, _ = CANDIDATE[a]
    return len(PATH[path]) - (i + 1)


TEST = {
    "rule-list": lambda a: f"{RULE_LINES}-lines",
    "interface-capture": lambda a: "did-not-arrive" if CANDIDATE[a][1] == 0 else "arrived",
    "egress-capture": lambda a: "exited" if CANDIDATE[a][0] == "forward" else "did-not-exit",
    "connection-attempt": lambda a: ("refused" if CANDIDATE[a][2] == "service"
                                    else "timeout"),
    "counter-loaded": lambda a: "all-counters-increased",
    "counter-quiet": lambda a: (last_hop(a) if last_hop(a) in CHAIN
                               else "no-counter"),
    "trace-off": lambda a: "no-line",
    "trace-on": lambda a: f"{last_hop(a)}/{CANDIDATE[a][2]}",
}
LINES = {"rule-list": RULE_LINES, "interface-capture": 6,
         "egress-capture": 6, "connection-attempt": 1, "counter-loaded": 34,
         "counter-quiet": 34, "trace-off": 0, "trace-on": 12}


def eliminate(candidates, s, answer):
    return tuple(a for a in candidates if TEST[s](a) == answer)


def group(tests, candidates):
    o = {}
    for a in candidates:
        o.setdefault(tuple(TEST[s](a) for s in tests), []).append(a)
    return [sorted(v) for v in o.values() if len(v) > 1]


A = tuple(CANDIDATE)
print("candidate causes:", len(A), "| tests:", len(TEST), "| oracle:", ORACLE)
print()
print("candidate                   path     last hop           unreached hops")
for a in A:
    print(f"  {a:26s} {CANDIDATE[a][0]:7s}  {last_hop(a):18s} {unreached(a):9d}")
print("  total unreached hops:", sum(unreached(a) for a in A))
print()
print("test                lines  distinct answers  eliminated  remaining")
for s in TEST:
    remaining = len(eliminate(A, s, TEST[s](ORACLE)))
    print(f"  {s:18s} {LINES[s]:5d} {len({TEST[s](a) for a in A}):11d}"
          f" {len(A) - remaining:7d} {remaining:6d}")
print()
print("tool set                             lines  indistinguishable group")
for ad, k in (("rule list alone", ["rule-list"]),
              ("list + connection attempt",
               ["rule-list", "connection-attempt"]),
              ("four readings on a loaded machine",
               ["rule-list", "interface-capture", "connection-attempt",
                "counter-loaded"]),
              ("four readings on a quiet machine",
               ["rule-list", "interface-capture", "connection-attempt",
                "counter-quiet"]),
              ("trace on", ["trace-on"])):
    o = group(k, A)
    print(f"  {ad:34s} {sum(LINES[s] for s in k):5d} {len(o):8d}")
    if o:
        for x in o:
            print(f"      {x}")
print()
print("how many faults an accept rule added to the input-filter chain fixes")
for ad, cond in (
        ("at the head of the chain", lambda a: CANDIDATE[a][0] == "local" and CANDIDATE[a][1] == 5),
        ("at the tail of the chain",
         lambda a: CANDIDATE[a][0] == "local" and CANDIDATE[a][1] == 5
         and CANDIDATE[a][2] == "policy")):
    d = [a for a in A if cond(a)]
    print(f"  {ad:16s} fixed {len(d)} / {len(A)}", d)
print()
print("candidate set sweep")
CANDIDATE["input-filter-wrong-interface"] = ("local", 5, "rule")
for ad, k in (("8 candidates: state-rule-missing removed",
               tuple(a for a in A if a != "state-rule-missing")),
              ("9 candidates: base list", A),
              ("10 candidates: input-filter-wrong-interface added",
               A + ("input-filter-wrong-interface",))):
    remaining = len(eliminate(k, "counter-quiet", TEST["counter-quiet"](ORACLE)))
    o = group(["trace-on"], k)
    print(f"  {ad:42s} quiet counter eliminated {len(k) - remaining:2d} remaining {remaining:2d}"
          f" | group trace cannot separate {len(o)}"
          f" largest {max((len(x) for x in o), default=0)}")

candidate causes: 9 | tests: 8 | oracle: input-default-refused

candidate                   path     last hop           unreached hops
  packet-never-arrived       local    interface                  6
  prerouting-raw-dropped     local    prerouting-raw             5
  input-mangle-dropped       local    input-mangle               2
  input-filter-rule-dropped  local    input-filter               1
  input-default-refused      local    input-filter               1
  state-rule-missing         local    input-filter               1
  nat-wrong-target           forward  forward-filter             2
  routing-wrong              forward  forward-filter             2
  service-not-listening      local    service                    0
  total unreached hops: 20

test                lines  distinct answers  eliminated  remaining
  rule-list             34           1       0      9
  interface-capture      6           2       1      8
  egress-capture         6           2       2      7
  connection-attempt     1           2       1      8
  counter-loaded        34           1       0      9
  counter-quiet         34           5       6      3
  trace-off              0           1       0      9
  trace-on              12           7       8      1

tool set                             lines  indistinguishable group
  rule list alone                       34        1
      ['input-default-refused', 'input-filter-rule-dropped', 'input-mangle-dropped', 'nat-wrong-target', 'packet-never-arrived', 'prerouting-raw-dropped', 'routing-wrong', 'service-not-listening', 'state-rule-missing']
  list + connection attempt             35        1
      ['input-default-refused', 'input-filter-rule-dropped', 'input-mangle-dropped', 'nat-wrong-target', 'packet-never-arrived', 'prerouting-raw-dropped', 'routing-wrong', 'state-rule-missing']
  four readings on a loaded machine     75        1
      ['input-default-refused', 'input-filter-rule-dropped', 'input-mangle-dropped', 'nat-wrong-target', 'prerouting-raw-dropped', 'routing-wrong', 'state-rule-missing']
  four readings on a quiet machine      75        2
      ['input-default-refused', 'input-filter-rule-dropped', 'state-rule-missing']
      ['nat-wrong-target', 'routing-wrong']
  trace on                              12        2
      ['input-filter-rule-dropped', 'state-rule-missing']
      ['nat-wrong-target', 'routing-wrong']

how many faults an accept rule added to the input-filter chain fixes
  at the head of the chain fixed 3 / 9 ['input-filter-rule-dropped', 'input-default-refused', 'state-rule-missing']
  at the tail of the chain fixed 1 / 9 ['input-default-refused']

candidate set sweep
  8 candidates: state-rule-missing removed   quiet counter eliminated  6 remaining  2 | group trace cannot separate 1 largest 2
  9 candidates: base list                    quiet counter eliminated  6 remaining  3 | group trace cannot separate 2 largest 2
  10 candidates: input-filter-wrong-interface added quiet counter eliminated  6 remaining  4 | group trace cannot separate 2 largest 3

Three Numbers

Oracle: the decision is made at the input-filter hop; because no rule matches, it is made by the policy. Test: the rule list prints thirty-four lines; the counter reading on a loaded machine gives thirty-four numbers; the same reading on a quiet machine gives the chain name; open tracing says “input-filter/policy” in twelve lines. Candidates eliminated: rule list 0, loaded counter 0, tracing off 0, connection attempt 1, quiet counter 6, tracing on 8.

The three zeros above are this lesson’s result. The rule list is a thirty-four-line output, and it eliminates none of the nine candidates, because it is the same list in all nine cases. The list shows the configuration, not the packet’s fate. The output with the highest count sits in the same row as the one with the lowest elimination power: more output does not mean better diagnosis.

The connection attempt prints one line and eliminates one candidate. Its ratio is infinitely better than the rule list’s, but its absolute value is low, and the reason was established in the shared reference: a dropped packet produces a timeout, a refused packet gives a separate answer. Eight of nine candidates produce a timeout.

What the Counter Proves

The difference between the counter reading’s two lines is this lesson’s most practical finding. On a quiet machine, the counter gives five distinct answers and eliminates six candidates: whichever chain’s counter increased is where the decision was made. On a loaded machine, the same reading gives a single answer and eliminates zero candidates, because background traffic increases every chain’s counters. The counter difference exists; it just cannot be shown to belong to the test packet.

For this reason, a counter reading cannot be written as a standalone procedure on its own. To become measurable, either traffic must stop, or the counter must be reset before the test and only one packet sent; the second cannot always be done on a running system. What the counter tells you depends on how quiet the machine is, and this is a property of the environment, not of the tool.

Tracing’s two lines give the same lesson on the time axis. On, it produces twelve lines and eliminates eight candidates; off, zero lines and zero candidates. The difference is a setting, and that setting must have been turned on before the fault. Turning tracing on after the fault does not bring back the packet from the past. The evidence does not wait.

Even open tracing cannot separate everything. Two groups remain: a rule fault dropping for the same reason at the same chain versus the state rule being missing, and the two faults dropping on the forwarding path. Tracing states the hop and the reason; stating which rule matched requires a separate level of detail.

Where Adding a Rule Actually Helps

The bottom table counts the framework’s most expensive misunderstanding. When an accept rule is added to the input-filter chain, how many of nine faults are fixed: 3 if the rule is added to the head of the chain, 1 if added to the tail.

The gap between the two numbers comes from the first-matching-rule rule. An accept rule added at the tail is never evaluated at all if a drop rule matching before it exists; it fixes only the case where no rule matches at all — that is, the case where the policy kicks in. The rule was added, the list got longer, the output came back “successful,” and the fault continues.

For the remaining six faults, position makes no difference at all, because the packet never reaches that chain in the first place. The top table’s last column counts this: for nine faults, the total of unreached hops is 20. If the packet was dropped at the raw hook, the next five hops never ran; if dropped at the marking hook, the next two never ran. Every rule written at those hops is a dead rule, however correctly it is written.

The order rule that follows is this: before adding a rule, find out at which hop the decision is being made. When this order is reversed — adding the rule first — what results is not an error message but a fix that does not work and a growing rule set.

Candidate Set Sweep

The bottom table tries the candidate list at three sizes, and the result looks in the same direction as the previous two lessons. The number of candidates the quiet counter eliminates is 6 in all three lists; what remains is 2, 3, and 4. As the candidate list grows, the same reading eliminates the same number of candidates and leaves more behind. The largest group tracing cannot separate rises from two members to three, because the added candidate drops at the same hop for the same reason.

Summary

• The packet-filtering framework is made of fixed hooks; each hook holds chains grouped by table, and after the routing decision the local path and the forward path never merge again.
• In a chain, the first matching rule makes the decision and the rest does not run; if no rule matches, the policy applies.
• A thirty-four-line rule list eliminates none of nine candidates, because it is the same in all nine cases. On a loaded machine the counter reading also eliminates 0; on a quiet machine 6, with tracing on 8.
• Tracing produces 0 lines while off, and turning it on after the fault does not bring back the packet from the past.
• An accept rule added to the input-filter chain fixes 3 faults at the head, 1 at the tail; for the remaining six, the packet never reaches that chain at all. The total of unreached hops across nine faults is 20.

Next Step

This lesson asked where the decision was made and chose the policy as the oracle: no rule matched, so the chain’s default kicked in. The next lesson takes up that default itself. A default-deny policy is a security decision, and the order it is applied in is an operational one; applied in the wrong order, it can cut off the administrator’s own access. What will be measured is how many of the application orders produce this result, and which paths bring the cost down to zero.