verigraph/service/src/mcnet/components/Network.java

   1 /*******************************************************************************
   2  * Copyright (c) 2017 Politecnico di Torino and others.
   3  *
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Apache License, Version 2.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.apache.org/licenses/LICENSE-2.0
   8  *******************************************************************************/
   9
  10 package mcnet.components;
  11 import java.util.ArrayList;
  12 import java.util.HashMap;
  13 import java.util.List;
  14 import java.util.Map;
  15
  16 import com.microsoft.z3.BoolExpr;
  17 import com.microsoft.z3.Context;
  18 import com.microsoft.z3.DatatypeExpr;
  19 import com.microsoft.z3.Expr;
  20 import com.microsoft.z3.IntExpr;
  21 import com.microsoft.z3.Solver;
  22 import com.microsoft.z3.Z3Exception;
  23
  24 /**Model for a network, encompasses routing and wiring
  25  *
  26  */
  27 public class Network extends Core{
  28
  29         Context ctx;
  30         NetContext nctx;
  31         List<BoolExpr> constraints;
  32         List<NetworkObject> elements;
  33
  34
  35
  36         public Network(Context ctx,Object[]... args) {
  37                 super(ctx, args);
  38         }
  39
  40         @Override
  41         protected void init(Context ctx, Object[]... args) {
  42                 this.ctx = ctx;
  43                 this.nctx = (NetContext) args[0][0];
  44         constraints = new ArrayList<BoolExpr>();
  45         elements = new ArrayList<NetworkObject>();
  46
  47         }
  48
  49         /**Composes the network linking the configured network objects
  50          *
  51          * @param elements
  52          */
  53         public void attach (NetworkObject ... elements){
  54               for(NetworkObject el : elements)
  55                   this.elements.add(el);
  56         }
  57
  58         @Override
  59         protected void addConstraints(Solver solver) {
  60                 try {
  61                         BoolExpr[] constr = new BoolExpr[constraints.size()];
  62                     solver.add(constraints.toArray(constr));
  63                 } catch (Z3Exception e) {
  64                         e.printStackTrace();
  65                 }
  66         }
  67
  68         /**
  69          * Specify host to address mapping.
  70          * Handles the case in which we have more than one address for a node
  71          * @param addrmap
  72          */
  73          public void setAddressMappings(ArrayList<Tuple<NetworkObject,ArrayList<DatatypeExpr>>> addrmap){
  74                  // Set address mapping for nodes.
  75                  for (Tuple<NetworkObject,ArrayList<DatatypeExpr>> entry : addrmap) {
  76                     NetworkObject node=entry._1;
  77                     List<DatatypeExpr> addr=entry._2;
  78                     Expr a_0 = ctx.mkConst(node+"_address_mapping_a_0",nctx.address);
  79                             ArrayList<BoolExpr> or_clause = new ArrayList<BoolExpr>();
  80
  81                            // Constraint 1                      addrToNode(foreach ad in addr) = node
  82                     for (DatatypeExpr ad : addr){
  83                       constraints.add(ctx.mkEq(nctx.addrToNode.apply(ad), node.getZ3Node()));
  84                       or_clause.add(ctx.mkEq(a_0,ad));
  85                         }
  86                     BoolExpr[] orClause = new BoolExpr[or_clause.size()];
  87
  88                     // Constraint 2                     nodeHasAddr(node, a_0) == Or(foreach ad in addr (a_0 == ad))
  89                         // Note we need the iff here to make sure that we set nodeHasAddr to false
  90                         // for other addresses.
  91                     constraints.add(ctx.mkForall(new Expr[]{a_0},
  92                           ctx.mkEq(ctx.mkOr(or_clause.toArray(orClause)), nctx.nodeHasAddr.apply(node.getZ3Node(), a_0)),1,null,null,null,null));
  93                         }
  94          }
  95
  96
  97
  98         /**
  99          * Don't forward packets addressed to node
 100          * @param node
 101          */
 102          public void saneSend(NetworkObject node){
 103              Expr n_0 = ctx.mkConst(node+"_saneSend_n_0", nctx.node);
 104              Expr p_0 = ctx.mkConst(node+"_saneSend_p_0", nctx.packet);
 105              IntExpr t_0 = ctx.mkIntConst(node+"_saneSend_t_0");
 106                 // Constant: node
 107                 //Constraint     send(node, n_0, p, t_0) -> !nodeHasAddr(node, p.dest)
 108                 constraints.add(
 109                         ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 110                             ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(),n_0, p_0, t_0),
 111                                         ctx.mkNot((BoolExpr)nctx.nodeHasAddr.apply( node.getZ3Node(),
 112                                                         nctx.pf.get("dest").apply(p_0)))),1,null,null,null,null));
 113             }
 114
 115          /**
 116           * Node sends all traffic through gateway
 117           * @param node
 118           * @param gateway
 119           */
 120           public void setGateway (NetworkObject node, NetworkObject gateway){
 121                 // SetGateway(self, node, gateway): All packets from node are sent through gateway
 122                 Expr n_0 = ctx.mkConst(node+"_gateway_n_0", nctx.node);
 123                 Expr p_0 = ctx.mkConst(node+"_gateway_p_0", nctx.packet);
 124                 IntExpr t_0 = ctx.mkIntConst(node+"_gateway_t_0");
 125
 126                 //Constraint     send(node, n_0, p_0, t_0) -> n_0 = gateway
 127                 constraints.add(
 128                                  ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 129                                                  ctx.mkImplies(
 130                                                                  (BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0),
 131                                                    ctx.mkEq(n_0,gateway.getZ3Node())),1,null,null,null,null));
 132
 133 //              constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 134 //                  ctx.mkImplies((BoolExpr)nctx.recv.apply(n_0, node.getZ3Node(),  p_0, t_0),
 135 //                                                  ctx.mkEq(n_0,gateway.getZ3Node())),1,null,null,null,null));
 136           }
 137
 138           /**
 139            * Assigns a specific routing table to a network object. Routing entries in the form: address -> node
 140            * @param node
 141            * @param routing_table
 142            */
 143        public void routingTable (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table){
 144                compositionPolicy(node,routing_table);
 145            }
 146
 147        /**
 148         * Composition policies steer packets between middleboxes.
 149         * @param node
 150         * @param policy
 151         */
 152        public void compositionPolicy (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> policy){
 153                 //Policy is of the form predicate -> node
 154                 Expr p_0 = ctx.mkConst(node+"_composition_p_0", nctx.packet);
 155                 Expr n_0 = ctx.mkConst(node+"_composition_n_0", nctx.node);
 156                 Expr t_0 = ctx.mkIntConst(node+"_composition_t_0");
 157
 158                 HashMap<String,ArrayList<BoolExpr>> collected = new HashMap<String,ArrayList<BoolExpr>>();
 159                 HashMap<String,NetworkObject> node_dict = new HashMap<String,NetworkObject>();
 160             BoolExpr predicates;
 161             for(int y=0;y<policy.size();y++){
 162                 Tuple<DatatypeExpr,NetworkObject> tp = policy.get(y);
 163                 if(collected.containsKey(""+tp._2))      collected.get(""+tp._2).add(nctx.destAddrPredicate(p_0,tp._1));
 164                 else{
 165                         ArrayList<BoolExpr> alb = new ArrayList<BoolExpr>();
 166                         alb.add(nctx.destAddrPredicate(p_0,tp._1));
 167                         collected.put(""+tp._2,alb);
 168                 }
 169                 node_dict.put(""+tp._2, tp._2);
 170             }
 171
 172             //Constraint                foreach rtAddr,rtNode in rt( send(node, n_0, p_0, t_0) &&
 173             //                                  Or(foreach rtAddr in rt destAddrPredicate(p_0,rtAddr)) -> n_0 == rtNode )
 174                 for (Map.Entry<String,ArrayList<BoolExpr>> entry : collected.entrySet()) {
 175                         BoolExpr[] pred = new BoolExpr[entry.getValue().size()];
 176                     predicates = ctx.mkOr(entry.getValue().toArray(pred));
 177
 178                     constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 179                     ctx.mkImplies(ctx.mkAnd((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), predicates),
 180                                 ctx.mkEq(n_0, node_dict.get(entry.getKey()).getZ3Node())),1,null,null,null,null));
 181                 }
 182         }
 183
 184             /**
 185              * Routing entries are in the form: address -> node. Also allows packet to be sent to another box for further processing
 186              * @param node
 187              * @param routing_table
 188              * @param shunt_node
 189              */
 190            public void routingTableShunt (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table,NetworkObject shunt_node){
 191                    compositionPolicyShunt(node,routing_table,shunt_node);
 192                     }
 193
 194             /**
 195              * Composition policies steer packets between middleboxes.Policy is in the form: predicate -> node
 196              * @param node
 197              * @param routing_table
 198              * @param shunt_node
 199              */
 200            public void compositionPolicyShunt (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table,NetworkObject shunt_node){
 201                     Expr p_0 = ctx.mkConst(node+"_composition_p_0", nctx.packet);
 202                 Expr n_0 = ctx.mkConst(node+"_composition_n_0", nctx.node);
 203                 Expr t_0 = ctx.mkIntConst(node+"_composition_t_0");
 204
 205                 HashMap<String,ArrayList<BoolExpr>> collected = new HashMap<String,ArrayList<BoolExpr>>();
 206                 HashMap<String,NetworkObject> node_dict = new HashMap<String,NetworkObject>();
 207                 BoolExpr predicates;
 208             for(int y=0;y<routing_table.size();y++){
 209                 Tuple<DatatypeExpr,NetworkObject> tp = routing_table.get(y);
 210                 if(collected.containsKey(""+tp._2))      collected.get(""+tp._2).add(nctx.destAddrPredicate(p_0,tp._1));
 211                 else{
 212                         ArrayList<BoolExpr> alb = new ArrayList<BoolExpr>();
 213                         alb.add(nctx.destAddrPredicate(p_0,tp._1));
 214                         collected.put(""+tp._2,alb);
 215                 }
 216                 node_dict.put(""+tp._2, tp._2);
 217             }
 218
 219             //Constraint                foreach rtAddr,rtNode in rt( send(node, n_0, p_0, t_0) &&
 220             //                                  Or(foreach rtAddr in rt destAddrPredicate(p_0,rtAddr)) -> n_0 == rtNode )
 221                 for (Map.Entry<String,ArrayList<BoolExpr>> entry : collected.entrySet()) {
 222                     BoolExpr[] pred = new BoolExpr[entry.getValue().size()];
 223                     predicates = ctx.mkOr(entry.getValue().toArray(pred));
 224
 225                     constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 226                     ctx.mkImplies(ctx.mkAnd((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), predicates),
 227                                ctx.mkOr(ctx.mkEq(n_0, node_dict.get(entry.getKey()).getZ3Node()),ctx.mkEq(n_0, shunt_node.getZ3Node()))),1,null,null,null,null));
 228                 }
 229
 230             }
 231
 232 //          public void SimpleIsolation (NetworkObject node, ArrayList<DatatypeExpr> addresses){
 233 //             Expr p = ctx.mkConst(node+"_s_p", nctx.packet);
 234 //             Expr n = ctx.mkConst(node+"_s_n", nctx.node);
 235 //             IntExpr t = ctx.mkInt(node+"_s_t");
 236 //
 237 //             BoolExpr[] a_pred= new BoolExpr[addresses.size()];
 238 //              for(int y=0;y<addresses.size();y++){
 239 //                      DatatypeExpr de = addresses.get(y);
 240 //                      a_pred[y] = ctx.mkOr(ctx.mkEq(nctx.pf.get("src").apply(p), de),ctx.mkEq(nctx.pf.get("dest").apply(p), de));
 241 //              }
 242 //
 243 //              constraints.add(
 244 //                      ctx.mkForall(new Expr[]{p, n, t},
 245 //                        ctx.mkImplies((BoolExpr)nctx.recv.apply(n, node.getZ3Node(), p, t),
 246 //                                  ctx.mkOr(a_pred)),1,null,null,null,null));
 247 //              constraints.add(
 248 //                      ctx.mkForall(new Expr[]{p, n, t},
 249 //                        ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(), n, p, t),
 250 //                                  ctx.mkOr(a_pred)),1,null,null,null,null));
 251 //          }
 252
 253
 254            /**
 255             * Set isolation constraints on a node.
 256             * Doesn't need to be set but useful when interfering policies are in play.
 257             * @param node
 258             * @param adjacencies
 259             *
 260             */
 261            public void SetIsolationConstraint ( NetworkObject node,  ArrayList<NetworkObject> adjacencies){
 262
 263                         Expr n_0 = ctx.mkConst(node+"_isolation_n_0", nctx.node);
 264                 Expr p_0 = ctx.mkConst(node+"_isolation_p_0", nctx.packet);
 265                 IntExpr t_0 = ctx.mkInt(node+"_isolation_t_0");
 266
 267                 BoolExpr[] adj = new BoolExpr[adjacencies.size()];
 268                 for(int y=0;y<adjacencies.size();y++){
 269                         NetworkObject no = adjacencies.get(y);
 270                         adj[y] =  ctx.mkEq(n_0,no.getZ3Node());
 271                 }
 272                 BoolExpr clause = ctx.mkOr(adj);
 273
 274                 constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 275                     ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0),
 276                                             clause),1,null,null,null,null));
 277                 constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0},
 278                     ctx.mkImplies((BoolExpr)nctx.recv.apply(n_0, node.getZ3Node(), p_0, t_0),
 279                                             clause),1,null,null,null,null));
 280                }
 281
 282           /**
 283            * Return all currently attached endhosts
 284            * @return NetworkObject
 285            */
 286            public List<String> EndHosts(){
 287                    List<String> att_nos = new ArrayList<String>();
 288                    for(NetworkObject el :elements){
 289                            if(el.isEndHost){
 290                                    System.out.println("el: "+el);
 291                                         att_nos.add(el.getZ3Node().toString());
 292                                 }
 293                         }
 294                 return att_nos;
 295            }
 296 }