Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

FDD Leaf Nodes Generating Un-constrained Drop Rules #463

Open
craig-riecke opened this issue Dec 17, 2015 · 13 comments
Open

FDD Leaf Nodes Generating Un-constrained Drop Rules #463

craig-riecke opened this issue Dec 17, 2015 · 13 comments
Assignees
@craig-riecke
Labels
bug

Comments

@craig-riecke
Copy link
Collaborator

I'm sending over NetKAT that generates the following flow table:

+-----------------------------------------------------+
| 95073481681482 | Pattern  | Action                  |
|-----------------------------------------------------|
| IP4Dst = 192.168.56.1     | Output(Controller(128)) |
| EthType = 0x806 (arp)     |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.56.1     |                         |
|-----------------------------------------------------|
| InPort = 1                | Output(Controller(128)) |
| IP4Dst = 192.168.57.0/24  |                         |
| IP4Src = 192.168.56.100   |                         |
| EthType = 0x800 (ip)      |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.57.0/24  |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.156.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp)     |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.156.0/24 |                         |
|-----------------------------------------------------|
| InPort = 1                | Output(Controller(128)) |
| IP4Dst = 192.168.157.0/24 |                         |
| EthType = 0x800 (ip)      |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.157.0/24 |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.158.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp)     |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.158.0/24 |                         |
|-----------------------------------------------------|
| InPort = 1                | Output(Controller(128)) |
| IP4Dst = 192.168.159.0/24 |                         |
| EthType = 0x800 (ip)      |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.159.0/24 |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.160.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp)     |                         |
|-----------------------------------------------------|
| IP4Dst = 192.168.160.0/24 |                         |
|-----------------------------------------------------|
| InPort = 1                | Output(Controller(128)) |
| IP4Dst = 192.168.161.0/24 |                         |
| EthType = 0x800 (ip)      |                         |
|-----------------------------------------------------|
|                           |                         |
+-----------------------------------------------------+

The rules that look like "condition" -> drop (no actions) are artifacts of FDD complilation. If this generated the right flow table in OpenFlow, it'd be fine ... the drop rules have lower priority than the ones above it, and are therefore not fired under the right circumstances. But on OpenVSwitch, here's the flow table:

priority=65535,arp,arp_tpa=192.168.56.1 actions=CONTROLLER:128
priority=65534 actions=drop
priority=65533,ip,in_port=1,nw_src=192.168.56.100,nw_dst=192.168.57.0/24 actions=CONTROLLER:128
priority=65531,arp,arp_tpa=192.168.156.0/24 actions=CONTROLLER:128
priority=65532 actions=drop
priority=65530 actions=drop
priority=65529,ip,in_port=1,nw_dst=192.168.157.0/24 actions=CONTROLLER:128
priority=65528 actions=drop
priority=65527,arp,arp_tpa=192.168.158.0/24 actions=CONTROLLER:128
priority=65526 actions=drop
priority=65525,ip,in_port=1,nw_dst=192.168.159.0/24 actions=CONTROLLER:128
priority=65524 actions=drop
priority=65523,arp,arp_tpa=192.168.160.0/24 actions=CONTROLLER:128
priority=65522 actions=drop
priority=65521,ip,in_port=1,nw_dst=192.168.161.0/24 actions=CONTROLLER:128
priority=65520 actions=drop

Because the rule in 65534 does not have a condition, it's catching all the packets that don't fit rule 65535 and dropping them.
@jnfoster
Copy link
Member

I think the problem may be that the EthType 0x800 is not set for the IP
matches. Hence, Frenetic thinks it has the right flow table but OpenVswitch
interprets these (correctly) as wildcarded patterns.

-N

On Thu, Dec 17, 2015 at 10:31 AM, Craig Riecke notifications@github.com
wrote:

I'm sending over NetKAT that generates the following flow table:

+-----------------------------------------------------+
| 95073481681482 | Pattern | Action |
|-----------------------------------------------------|
| IP4Dst = 192.168.56.1 | Output(Controller(128)) |
| EthType = 0x806 (arp) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.56.1 | |
|-----------------------------------------------------|
| InPort = 1 | Output(Controller(128)) |
| IP4Dst = 192.168.57.0/24 | |
| IP4Src = 192.168.56.100 | |
| EthType = 0x800 (ip) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.57.0/24 | |
|-----------------------------------------------------|
| IP4Dst = 192.168.156.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.156.0/24 | |
|-----------------------------------------------------|
| InPort = 1 | Output(Controller(128)) |
| IP4Dst = 192.168.157.0/24 | |
| EthType = 0x800 (ip) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.157.0/24 | |
|-----------------------------------------------------|
| IP4Dst = 192.168.158.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.158.0/24 | |
|-----------------------------------------------------|
| InPort = 1 | Output(Controller(128)) |
| IP4Dst = 192.168.159.0/24 | |
| EthType = 0x800 (ip) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.159.0/24 | |
|-----------------------------------------------------|
| IP4Dst = 192.168.160.0/24 | Output(Controller(128)) |
| EthType = 0x806 (arp) | |
|-----------------------------------------------------|
| IP4Dst = 192.168.160.0/24 | |
|-----------------------------------------------------|
| InPort = 1 | Output(Controller(128)) |
| IP4Dst = 192.168.161.0/24 | |
| EthType = 0x800 (ip) | |
|-----------------------------------------------------|
| | |
+-----------------------------------------------------+

The rules that look like "condition" -> drop (no actions) are artifacts of
FDD complilation. If this generated the right flow table in OpenFlow, it'd
be fine ... the drop rules have lower priority than the ones above it, and
are therefore not fired under the right circumstances. But on OpenVSwitch,
here's the flow table:

priority=65535,arp,arp_tpa=192.168.56.1 actions=CONTROLLER:128
priority=65534 actions=drop
priority=65533,ip,in_port=1,nw_src=192.168.56.100,nw_dst=192.168.57.0/24 actions=CONTROLLER:128
priority=65531,arp,arp_tpa=192.168.156.0/24 actions=CONTROLLER:128
priority=65532 actions=drop
priority=65530 actions=drop
priority=65529,ip,in_port=1,nw_dst=192.168.157.0/24 actions=CONTROLLER:128
priority=65528 actions=drop
priority=65527,arp,arp_tpa=192.168.158.0/24 actions=CONTROLLER:128
priority=65526 actions=drop
priority=65525,ip,in_port=1,nw_dst=192.168.159.0/24 actions=CONTROLLER:128
priority=65524 actions=drop
priority=65523,arp,arp_tpa=192.168.160.0/24 actions=CONTROLLER:128
priority=65522 actions=drop
priority=65521,ip,in_port=1,nw_dst=192.168.161.0/24 actions=CONTROLLER:128
priority=65520 actions=drop

Because the rule in 65534 does not have a condition, it's catching all the
packets that don't fit rule 65535 and dropping them.

—
Reply to this email directly or view it on GitHub
#463.

@craig-riecke
Copy link
Collaborator Author

@arjun @smolkaj: So Nate and I talked about this. OpenVSwitch is doing the right thing by interpreting the condition "Ipv4Dst = nn" as "*" because it doesn't specify the EthType. The problem is that rule is an artifact of FDD-to-table generation, not something I explicitly wrote in NetKAT.

Nate came up with a possible fix. If we enumerate a row which contains Ip4Src or Ip4Dst, for those fields to make sense, EthTyp must be 0x800 or 0x806. So rather than emitting a false branch is "EthTyp is *", it would be "EthTyp is {0x800, 0x806} minus everything that we haven't matched on a true branch". If all of those values have been specified, we emit no rule. If the rule doesn't specify a dependent field, then EthTyp rule generation is left alone.

Does this make sense?

@smolkaj
Copy link
Member

smolkaj commented Dec 17, 2015

Actually, I think I am to blame for this. Look at my recent pull reques #454. If you recompile your example with openflow-adherence = Strict (the default prior to my pull request), I think you will get the correct table.

@smolkaj
Copy link
Member

smolkaj commented Dec 17, 2015

This still leaves the question of how the compiler should deal with missing ethTyp and dlTyp tests. My pull request #454 does not seem to be the right answer.

@craig-riecke
Copy link
Collaborator Author

Oh, I see. And yes, turning on Strict did make it work. I thought #454's default mode only allowed writing NetKAT with Ip4Src/Dst and no EthTyp.

@jnfoster
Copy link
Member

Here's how I would do it:

During the iterative conversion from an FDD to a Flowtable, if you
encounter a test on a field with dependencies, keep track of those
dependencies as well as the accumulated tests on the path from root to the
current node. Use these dependencies to generate a well-formed rule.

For example if a test on IPSrc appears high in the FDD, then when we go
past it, we add the dependency that EthType = 0x800 or 0x806. Now if we
later test EthType and are on the "true" branch, either the dependency is
satisfied or contradictory. On the no branch, we enumerate the remaining
"live" candidates for EthType and emit the appropriate rule.

-N

On Thu, Dec 17, 2015 at 1:07 PM, Steffen Smolka notifications@github.com
wrote:

This still leaves the question of how the compiler should deal with
missing ethTyp and dlTyp tests. My pull request #454
#454 does not seem to be
the right answer.

—
Reply to this email directly or view it on GitHub
#463 (comment)
.

@craig-riecke craig-riecke self-assigned this Jan 14, 2016
@craig-riecke
Copy link
Collaborator Author

I'm gonna grab this just because the CoSciN app needs it.

@seliopou
Copy link
Collaborator

FYI implementing BDD minimization (or approximating heuristics) should address this problem. Minimal diagram should produce minimal rules and therefore minimal drops.

Just remember that the ordering you're going for isn't just on the field, but on field * value.

@jnfoster
Copy link
Member

Huh. I don't see how this would help (it's possible I'm missing something).
I think the FDD is correct it just doesn't reflect the field dependency
order.

On Thu, Jan 14, 2016 at 7:53 AM, Spiros Eliopoulos <notifications@github.com

wrote:

FYI implementing BDD minimization (or approximating heuristics) should
address this problem. Minimal diagram should produce minimal rules and
therefore minimal drops.

Just remember that the ordering you're going for isn't just on the field,
but on field * value.

—
Reply to this email directly or view it on GitHub
#463 (comment)
.

@craig-riecke
Copy link
Collaborator Author

Got it working for ip4Src, ip4Dst and ipProto dependencies. As a bonus, as you can see in the second example, if you forget the dependency in the NetKAT, it simply fills it in for you. It sorta has to be that way because there's no way to tell whether an FDD node came from an explicit NetKAT policy or was just generated

vagrant@frenetic:~/src/frenetic$ fresh
Frenetic Shell v 4.0
Type `help` for a list of commands
frenetic> load examples/issue_463a.kat
filter (ip4Dst=192.168.56.1 and ethTyp=0x806); port:=9 |
filter (port=1 and ip4Dst=192.168.57.0 and ip4Src=192.168.56.100 and ethTyp=0x800); port:=10

frenetic> flow-table
+--------------------------------------+
| 0 | Pattern             | Action     |
|--------------------------------------|
| IP4Dst = 192.168.56.1   | Output(9)  |
| EthType = 0x806 (arp)   |            |
|--------------------------------------|
| IP4Dst = 192.168.56.1   |            |
| EthType = 0x800 (ip)    |            |
|--------------------------------------|
| InPort = 1              | Output(10) |
| IP4Dst = 192.168.57.0   |            |
| IP4Src = 192.168.56.100 |            |
| EthType = 0x800 (ip)    |            |
|--------------------------------------|
|                         |            |
+--------------------------------------+
frenetic> load examples/issue_463b.kat
filter ipProto=6; port:=9 |
filter ipProto=1; port:=10
frenetic> flow-table
+-----------------------------------+
| 0 | Pattern          | Action     |
|-----------------------------------|
| ipProto = 0x1 (icmp) | Output(10) |
| EthType = 0x800 (ip) |            |
|-----------------------------------|
| ipProto = 0x6 (tcp)  | Output(9)  |
| EthType = 0x800 (ip) |            |
|-----------------------------------|
|                      |            |
+-----------------------------------+

The last thing I need is to handle tcpSrcPort and tcpDstPort, but these are harder because there are TWO field dependencies: ethDst=0x800 and ipProto in [1, 17].

@jnfoster
Copy link
Member

COOL!!! Nice job!

-N

On Fri, Mar 18, 2016 at 2:03 PM, Craig Riecke notifications@github.com
wrote:

Got it working for ip4Src, ip4Dst and ipProto dependencies. As a bonus, as
you can see in the second example, if you forget the dependency in the
NetKAT, it simply fills it in for you. It sorta has to be that way because
there's no way to tell whether an FDD node came from an explicit NetKAT
policy or was just generated

vagrant@frenetic:~/src/frenetic$ fresh
Frenetic Shell v 4.0
Type help for a list of commands
frenetic> load examples/issue_463a.kat
filter (ip4Dst=192.168.56.1 and ethTyp=0x806); port:=9 |
filter (port=1 and ip4Dst=192.168.57.0 and ip4Src=192.168.56.100 and ethTyp=0x800); port:=10

frenetic> flow-table
+--------------------------------------+
| 0 | Pattern | Action |
|--------------------------------------|
| IP4Dst = 192.168.56.1 | Output(9) |
| EthType = 0x806 (arp) | |
|--------------------------------------|
| IP4Dst = 192.168.56.1 | |
| EthType = 0x800 (ip) | |
|--------------------------------------|
| InPort = 1 | Output(10) |
| IP4Dst = 192.168.57.0 | |
| IP4Src = 192.168.56.100 | |
| EthType = 0x800 (ip) | |
|--------------------------------------|
| | |
+--------------------------------------+
frenetic> load examples/issue_463b.kat
filter ipProto=6; port:=9 |
filter ipProto=1; port:=10
frenetic> flow-table
+-----------------------------------+
| 0 | Pattern | Action |
|-----------------------------------|
| ipProto = 0x1 (icmp) | Output(10) |
| EthType = 0x800 (ip) | |
|-----------------------------------|
| ipProto = 0x6 (tcp) | Output(9) |
| EthType = 0x800 (ip) | |
|-----------------------------------|
| | |
+-----------------------------------+

The last thing I need is to handle tcpSrcPort and tcpDstPort, but these
are harder because there are TWO field dependencies: ethDst=0x800 and
ipProto in [1, 17].

—
You are receiving this because you commented.
Reply to this email directly or view it on GitHub
#463 (comment)

@craig-riecke craig-riecke mentioned this issue Mar 28, 2016
Closed
craig-riecke added a commit that referenced this issue Apr 4, 2016
@craig-riecke
Merge pull request #478 from frenetic-lang/issue_463_field_dependencies
7ba4c13 
Fixes issue #463 - field dependencies.
@smolkaj smolkaj reopened this Nov 18, 2016
@smolkaj
Copy link
Member

smolkaj commented Nov 18, 2016

This is not working as it should, see examples/fall-through-optimization2.kat.

@smolkaj smolkaj added the bug label Nov 18, 2016
@jnfoster
Copy link
Member

:-(

Damn. Well, the fix is not hard.

-N

On Fri, Nov 18, 2016 at 12:38 AM, Steffen Smolka notifications@github.com
wrote:

This is not working as it should, see examples/fall-through-
optimization2.kat.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#463 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABwi0tWPFJYGmibc68v__NjIg_vUwxjOks5q_WP1gaJpZM4G3b8a
.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@craig-riecke craig-riecke

Labels
bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@seliopou @craig-riecke @jnfoster @smolkaj