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