flow_table: check_for_overlapping_entries does not do overlap checking

[jmiserez]

The current implementation for the overlap checking in flow tables is wrong.

In flow_table.py:328, for two flows with the same priorities the following is checked:

if e.is_matched_by(in_entry.match) or in_entry.is_matched_by(e.match):
    return True
return False

However, this is wrong when wildcards are considered. E.g. for two flows with src/dst (10..., 10.1.2.3) and (10.1.2.3, 10...), neither contains the other but there is still a single packet (10.1.2.3, 10.1.2.3) that matches both. This can be verified with a simple testcase as below. Just set the pox repository path and execute it.

The correct check would involve checking if they have the same bit value at every bit that is not wildcarded in either of the two flows. See also the OVS implementation (here, and here]

Tested on branch eel, commit 3d8eac7:

#!/usr/bin/env python
import os
import sys

sys.path.append(os.path.join(os.path.dirname(__file__), "../../pox")) # path to pox git repository relative to this file
from pox.openflow.libopenflow_01 import *
from pox.openflow.flow_table import FlowTable, TableEntry
from pox.lib.addresses import *


if __name__ == '__main__':   
  addr1 = parse_cidr("10.0.0.0/8") # returns (wildcardbits, ipaddr)
  addr2 = parse_cidr("10.1.2.3")

  match1 = ofp_match()
  match1.set_nw_src(addr1)
  match1.set_nw_dst(addr2)

  match2 = ofp_match()
  match2.set_nw_src(addr2)
  match2.set_nw_dst(addr1)

  check1 = match1.matches_with_wildcards(match2)
  check2 = match2.matches_with_wildcards(match1)

  print "m2 contained in m1: {}".format(str(check1))
  print "m1 contained in m2: {}".format(str(check2))

  flow1 = ofp_flow_mod()
  flow1.priority = 5
  flow1.match = match1
  entry1 = TableEntry.from_flow_mod(flow1)

  flow2 = ofp_flow_mod()
  flow2.priority = 5
  flow2.match = match2
  entry2 = TableEntry.from_flow_mod(flow2)

  table1 = FlowTable()
  table1.add_entry(entry1)
  overlap1 = table1.check_for_overlapping_entry(entry2)

  table2 = FlowTable()
  table2.add_entry(entry2)
  overlap2 = table2.check_for_overlapping_entry(entry1)

  overlap3 = check1 or check2

  assert (overlap1 == overlap2)
  assert (overlap2 == overlap3)

  print "POX check_for_overlapping_entry: {}".format(str(overlap3))

  # Now let's check if we can construct a packet that actually DOES overlap.

  match3 = ofp_match()
  match3.set_nw_src(addr2)
  match3.set_nw_dst(addr2)

  check4 = match1.matches_with_wildcards(match3)
  check5 = match2.matches_with_wildcards(match3)

  print "m3 contained in m1: {}".format(str(check4))
  print "m3 contained in m2: {}".format(str(check5))

  overlap4 = check4 and check5

  print "Correct check_for_overlapping_entry: {}".format(str(overlap4))

  if overlap3 != overlap4:
    print "Overlap bug in POX."
  else:
    print "No bug in POX."

Output:

m2 contained in m1: False
m1 contained in m2: False
POX check_for_overlapping_entry: False
m3 contained in m1: True
m3 contained in m2: True
Correct check_for_overlapping_entry: True
Overlap bug in POX.

[jmiserez]

I implemented overlap checking and added the functionality to the ofp_match class. It would be great if anyone could take a look and see if this is correct.

For reference, I looked at the Open vSwitch implementation, the Openflow spec, and the "Intersection" section in the paper Header Space Analysis: Static Checking For Networks.

[jmiserez]

@MurphyMc: I see you were faster, great. I added my implementation to the ofp_match() class, I think it makes more sense there as there already is the matches_with_wildcards function there.

One question though: Adresses like "10.1.2.3/8" obviously don't make sense. But assuming an ofp_match were to contain such an address with 24 wildcard bits, is it ever normalized to "10.0.0.0/8" in POX? If not, will the .in_network() work correctly in all cases?

[MurphyMc]

Thanks for finding this. There were a number of things in the flow table and the switch which I had been surprised were so easy, but never specifically worked through myself. I think a number have been addressed over time (when I rewrote so much of the switch and when we did a bunch of OFTest conformance testing), but I guess there are still some lurking (and I guess OFTest didn't catch this case!).

I just threw together my own attempt at it too, though I haven't tested it all.

From a quick glance at yours, I see a couple potential problems, which are probably pretty easily fixed. They may not come up in the case of the software switch, for example, which should pretty much always do things the same way, but for full generality...

1. It's possible to have an ofp_match where fields are not wildcarded even though a switch will treat them as if they were. For example, you might have the transport ports set even though the match doesn't specify TCP or UDP. I've thrown in a call to _unwire_wildcards() in an attempt to fix that.
2. ofp_match doesn't canonize field values, so there's no guarantee that, e.g., dl_dst will contain an EthAddr. So I made exceptions for the addresses and make sure they actually are as expected before comparing.

I put mine as a static method in the flow table, but I think putting it in ofp_match, as you did, and as the existing overlap-checking stuff is, may make more sense. Also, I used a loop, but that's probably mostly because I am lazy. I also fixed the weird else/if in the calling function.

Maybe the best result is a combination of both of ours?

As for your .in_network() point, yeah, you're right. I think cases like that will cause a runtime exception because .in_network() doesn't call parse_cidr() with allow_host=True. You know, IPAddr should just have like a .get_network(<bits/mask>) or .apply_netmask(<bits/mask>) or something which returns just the network part as an IPAddr(). That's a relatively common piece of functionality and it'd be nice to hide the bitwise stuff inside lib.addresses. And, to the point, the result could be used as the argument to .in_network().

[jmiserez]

Yes, your version seems more generic/future-proof.

1. Agreed, I was unsure how to handle this. Doesn't matches_with_wildcards() suffer from the same problem?

2. I'm not sure I understand. I thought dl_dst and dst_src should always contain either a MAC address or nothing (None+wildcard bit set)? From looking at OF 1.0, they can only contain OFP_ETH_ALEN (6) bytes, and they are either all wildcarded or none of them are. So the correct way to fix this issue would be to set the fields to None in the normalization step, if the the OFPFW_DL_SRC/OFPFW_DL_DST wildcard bit is set. The function fix() in ofp_match already seems to do something similar if I'm not mistaken.

3. in_network: Agreed.

FYI, normally I'm using an older version of POX (the one modified for STS) and there are a lot of differences between the two. So I'm not sure if all my observations about the current eel branch are accurate.

[MurphyMc]

I tweaked yours a little bit. Take a look at https://github.com/MurphyMc/pox/commits/fix_overlap and see what you think.

[MurphyMc]

Were you ever able to check out the most recent proposed patch? I know it was a while ago, but it'd be nice to merge a working version.

[jmiserez]

Sorry for the late reply. Unfortunately I forgot to backport your proposed changes into my branch. So the version I've been using for the past 6 months is this one:

https://github.com/jmiserez/pox/blob/hb/pox/openflow/libopenflow_01.py#L820

I used it within the context of the software switch as well as directly like this:

if isinstance(m1, ofp_flow_mod) and isinstance(m2, ofp_flow_mod):
  return m1.match.check_overlap(m2.match)
if isinstance(m1, ofp_match) and isinstance(m2, ofp_match):
  return m1.check_overlap(m2)

and I haven't had any issues with it. Besides all renamed but semantically equivalent code, I noticed the following changes:

1. norm(m) is different, specifically _normalize_wildcards() is not called anymore. I assume this is because it is absolutely always called in unpack() first, right?
2. do_not_overlap(): I have an AND for the two None checks, you have an OR. Is this a bug in my implementation, or can there in fact be an overlap when e.g. the dl_vlan is None in mine and some value in other?
3. do_not_overlap_nw(): Same AND vs OR here, but possibly different issue?
4. Reordering of the order of simple fields. Not sure why exactly, but makes no difference I think.
5. Special handling for dl_src and dl_dst. Still not clear on this, see my question 2) from my last comment. Can you clarify why this conversion is really needed? Is this just because the new POX ( handles this differently in another place? This is the commit history for my version, as you can see it diverged in 2012/2013 so it's really old:

https://github.com/jmiserez/pox/commits/hb/pox/openflow/libopenflow_01.py

[MurphyMc]

Before reading your new list, I realized I never responded to your point 2 above (from April 26 last year). Sorry about that! I wrote up the response first off, but now that I've read the rest, I'll move it down to point 5 below...

1. Right. Though this code looks slightly broken in my version (self_nw and other_nw actually don't appear to be ever set, but I think they should just get populated from get_nw_src()/get_nw_dst()?).
2. From my docstring: "Two entries overlap if there exists a packet that would match both. In such a case, this method returns True. This should be symmetric (a.overlaps_with(b) == b.overlaps_with(a))." So I think the answer to your question is... yes, by my definition of overlapping. It's not checking that one match is "inside" another -- it's checking whether there's any crossover. Which I think should be symmetric. I guess a question is whether this is the right/useful definition? I obviously thought so at the time, but I could've been wrong. :)
3. I think the same issue as extensiveness of gitignore #2.
4. Yeah, I don't think it makes any difference. I think I mostly just moved the vlan stuff together and then I pulled the Ethernet stuff out to do the special case as per item 5...
5. You're right that it should always contain None or an Ethernet address, but exactly what an Ethernet address is... is a bit of a question. :) The "correct" answer in POX is that it's an instance of EthAddr, but there are places where POX will accept raw bytes, and it'll (hopefully) get turned into an EthAddr later. I believe one of this places this magic happens is in ofp_match.pack(), so it'd be too late as far as the overlap comparisons are concerned.

And yes, it did diverge a long time ago. The fact that STS never got resynced with mainline was really too bad, because there were many, many bugs that got fixed and improvements that were made (especially to the switch). Some of it has been hand-backported. And some of it... I think has been simply reproduced by duplicate effort since then (e.g. I think supporting table entry timeouts?). And some has probably been missed altogether. :(

[MurphyMc]

Additional on #2 above: The 1.0 spec says of flow_mod with command=add and overlap_check: "Two flow entries overlap if a single packet may match both, and both entries have the same priority." This probably influenced my implementation.