if(pkt,env)【 2 inport read_inport (pkt); //inport<-{inport】 dst read_packet(pkt,"eth.dst"); //dst<-(dst】 src read packet (pkt,"eth.src"); /src <-(src) mod env(env,"mac2port",src,inport); /mod enve6 <-(src,inport) port read_env(env,"mac2port",dst); port <-(dst,env(mac2port)) if(port！=0){ /branche8 <-(dst,env(mac2port)) 9 上=port; /r <-(dst,env(mac2port)) else r =-inport; //r <-{dst,env(mac2port),inport) //r <-(dst,env(mac2port),inport) 14 if(test_equal(pkt,"eth.type",0x800))( /branche14 <-(test (type)) ttl read_packet (pkt,"eth.ipv4.ttl"); /ttl <-(test(type),ttl) if (!test_equal(pkt,"eth.ipv4.ttl",1)){//branche16 <-(test(ttl)) 17 mod_packet (pkt,"eth.ipv4.ttl",ttl -1);//mod_packete17 <-(test(type),ttl) 】else{ r=0: //r <(test (type),test(ttl)) 21 22 //r<-{dst, env(mac2port),inport,test (type),test(ttl)} return ri /return@23 <-(dst,env(mac2port),inport,test(type),test(ttl)) 24 Fig.3.Taint analysis for learning switches in POMP priority in_p src dst type ttl action merge the results.As an example,the label set for r at line 13 2 h2 hi 0x800 64 MOD FLD (tt1,63); is the union of the sets at lines 9 and 11 respectively.When OUT[1] 0x800 MOD FLD(ttl,63); analysing each branch,we also need to consider the label set OUT[2] of the boolean branch condition of the if statements.because h3 0x800 DROP of the implicit information flow caused by control dependence. Therefore the label set of variable r is the union of the label Fig.4.Flow table layout of learning switches sets of both inport and port. TABLE I B.Xgraphs and Pipeline Generation SOURCES AND SINKS Although the taint analysis generates dependence for each Source Label sink (at lines 6,17 and 23),we also need to maintain the read inport (pkt) inport control flow to decide the order of these actions in the read_packet(pkt,fld) fld forwarding pipeline.We let the taint analysis generate Xgraph, test_equal(pkt,fld,v) test(fld) read_env(env,var,key) env(var) an intermediate representation of both the control flow and (a)Sources and Labels the dependence (i.e.label sets).The Xgraph for our example Sink is shown in Fig.5.There are two types of nodes.The mod packet (pkt,fld,v) mod_env(env,var,key,v) square node represents an action corresponding to a sink. return r It records the name and the line number of the action (e.g. (b)Sinks mod_enve6 in the first node),and the corresponding label set (e.g.{src,inport in the first node).Each diamond node represents a branch.It records the label set of the branch Comments in Fig.3 demonstrates how we trace the infor- expression and the line number of the branch.The edges in mation flow.Every variable is assigned to a set of labels, the Xgraph represent the control flow. recording the information flowing into the variable Given the Xgraph,we can do a"node to node"translation For assignment statements,the label set of the variable on to generate the multi-stage forwarding pipeline.Fig.6 shows the left hand side is the union of the label sets of the variables the pipeline generated from Fig.5.For each square node in on the right and the set of sources accessed.For example, the Xgraph,we generate a flow table for the functionality.The the variable dst is assigned the label set fdst at line 7 match fields of the flow table are the packet header fields and (packet field prefix omitted in the label set to avoid clutter).the ingress port in the dependence set of the corresponding and port at line 4 is assigned {env(mac2port),dst}.Xgraph node.The action is translated from the corresponding which is obtained by fenv (mac2port)}Ulabel(dst). controller action in the Xgraph node,but not necessarily The label set of a sink is the union of the label set of its the same.For example,we translate the controller action arguments.The modenv (at line 6 is a sink.Its label set mod_env (in Fig.5 into a [GOTO]action,which does is the union of the label sets of src and inport. nothing and jumps to the next flow table on the pipeline.As For if statements,we analyse both branches and then we explained before,the only effect of this table is to generate1 f(pkt, env) { 2 inport = read_inport(pkt); // inport <- {inport} 3 dst = read_packet(pkt, "eth.dst"); // dst <- {dst} 4 src = read_packet(pkt, "eth.src"); // src <- {src} 5 6 mod_env(env, "mac2port", src, inport); // mod_env@6 <- {src, inport} 7 port = read_env(env, "mac2port", dst); // port <- {dst, env(mac2port)} 8 if (port != 0) { // branch@8 <- {dst, env(mac2port)} 9 r = port; // r <- {dst, env(mac2port)} 10 } else { 11 r = -inport; // r <- {dst, env(mac2port), inport} 12 } 13 // r <- {dst, env(mac2port), inport} 14 if(test_equal(pkt, "eth.type", 0x800)) { // branch@14 <- {test(type)} 15 ttl = read_packet(pkt, "eth.ipv4.ttl"); // ttl <- {test(type), ttl} 16 if (!test_equal(pkt, "eth.ipv4.ttl", 1)) { // branch@16 <- {test(ttl)} 17 mod_packet(pkt, "eth.ipv4.ttl", ttl - 1); // mod_packet@17 <- {test(type), ttl} 18 } else { 19 r = 0; // r <- {test(type), test(ttl)} 20 } 21 } 22 // r <- {dst, env(mac2port), inport, test(type), test(ttl)} 23 return r; // return@23 <- {dst, env(mac2port), inport, test(type), test(ttl)} 24 } Fig. 3. Taint analysis for learning switches in POMP priority in p src dst type ttl action 1 2 h2 h1 0x800 64 MOD_FLD(ttl,63); OUT[1] 1 1 h1 h2 0x800 64 MOD_FLD(ttl,63); OUT[2] 1 1 h1 h3 0x800 1 DROP ... ... ... ... ... ... Fig. 4. Flow table layout of learning switches TABLE I SOURCES AND SINKS Source Label read_inport(pkt) inport read_packet(pkt, fld) fld test_equal(pkt, fld, v) test(fld) read_env(env, var, key) env(var) (a) Sources and Labels Sink mod_packet(pkt, fld, v) mod_env(env, var, key, v) return r (b) Sinks Comments in Fig. 3 demonstrates how we trace the infor￾mation flow. Every variable is assigned to a set of labels, recording the information flowing into the variable. For assignment statements, the label set of the variable on the left hand side is the union of the label sets of the variables on the right and the set of sources accessed. For example, the variable dst is assigned the label set {dst} at line 7 (packet field prefix omitted in the label set to avoid clutter), and port at line 4 is assigned {env(mac2port), dst}, which is obtained by {env(mac2port)} ∪ label(dst). The label set of a sink is the union of the label set of its arguments. The mod_env() at line 6 is a sink. Its label set is the union of the label sets of src and inport. For if statements, we analyse both branches and then merge the results. As an example, the label set for r at line 13 is the union of the sets at lines 9 and 11 respectively. When analysing each branch, we also need to consider the label set of the boolean branch condition of the if statements, because of the implicit information flow caused by control dependence. Therefore the label set of variable r is the union of the label sets of both inport and port. B. Xgraphs and Pipeline Generation Although the taint analysis generates dependence for each sink (at lines 6, 17 and 23), we also need to maintain the control flow to decide the order of these actions in the forwarding pipeline. We let the taint analysis generate Xgraph, an intermediate representation of both the control flow and the dependence (i.e. label sets). The Xgraph for our example is shown in Fig. 5. There are two types of nodes. The square node represents an action corresponding to a sink. It records the name and the line number of the action (e.g. mod_env@6 in the first node), and the corresponding label set (e.g. {src, inport} in the first node). Each diamond node represents a branch. It records the label set of the branch expression and the line number of the branch. The edges in the Xgraph represent the control flow. Given the Xgraph, we can do a “node to node” translation to generate the multi-stage forwarding pipeline. Fig. 6 shows the pipeline generated from Fig. 5. For each square node in the Xgraph, we generate a flow table for the functionality. The match fields of the flow table are the packet header fields and the ingress port in the dependence set of the corresponding Xgraph node. The action is translated from the corresponding controller action in the Xgraph node, but not necessarily the same. For example, we translate the controller action mod_env() in Fig. 5 into a [GOTO] action, which does nothing and jumps to the next flow table on the pipeline. As we explained before, the only effect of this table is to generate