verigraph/src/it/polito/verigraph/mcnet/components/NetContext.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 com.microsoft.z3.BoolExpr;
  15 import com.microsoft.z3.Constructor;
  16 import com.microsoft.z3.Context;
  17 import com.microsoft.z3.DatatypeExpr;
  18 import com.microsoft.z3.DatatypeSort;
  19 import com.microsoft.z3.EnumSort;
  20 import com.microsoft.z3.Expr;
  21 import com.microsoft.z3.FuncDecl;
  22 import com.microsoft.z3.IntExpr;
  23 import com.microsoft.z3.Solver;
  24 import com.microsoft.z3.Sort;
  25 import it.polito.verigraph.mcnet.netobjs.DumbNode;
  26 import it.polito.verigraph.mcnet.components.Core;
  27 import it.polito.verigraph.mcnet.components.NetworkObject;
  28
  29 /**
  30  * Basic fields and other things required for model checking.
  31  *
  32  */
  33 public class NetContext extends Core{
  34
  35
  36     List<BoolExpr> constraints;
  37     List<Core> policies;
  38
  39     public HashMap<String,NetworkObject> nm; //list of nodes, callable by node name
  40     public HashMap<String,DatatypeExpr> am; // list of addresses, callable by address name
  41     public HashMap<String,FuncDecl> pf;
  42     Context ctx;
  43     public EnumSort node,address;
  44     public FuncDecl src_port,dest_port,nodeHasAddr,addrToNode,send,recv;
  45     public DatatypeSort packet;
  46
  47     /*   Constants definition
  48         - used in the packet proto field */
  49     public final int HTTP_REQUEST    = 1;
  50     public final int HTTP_RESPONSE   = 2;
  51     public final int POP3_REQUEST    = 3;
  52     public final int POP3_RESPONSE   = 4;
  53
  54     /**
  55      * Context for all of the rest that follows. Every network needs one of these
  56      * @param ctx
  57      * @param args
  58      */
  59     public NetContext(Context ctx,Object[]... args ){
  60         super(ctx,args);
  61
  62     }
  63
  64     @Override
  65     protected void init(Context ctx, Object[]... args) {
  66         this.ctx = ctx;
  67         nm = new HashMap<String,NetworkObject>(); //list of nodes, callable by node name
  68         am = new HashMap<String,DatatypeExpr>(); // list of addresses, callable by address name
  69         pf= new HashMap<String,FuncDecl>() ;
  70
  71
  72         mkTypes((String[])args[0],(String[])args[1]);
  73
  74         constraints = new ArrayList<BoolExpr>();
  75         policies = new ArrayList<Core>();
  76
  77         baseCondition();
  78
  79     }
  80
  81     /**
  82      * A policy is a collection of shared algorithms or functions used by multiple components
  83      * (for instance compression or DPI policies etc).
  84      * @param policy
  85      */
  86     public void AddPolicy (NetworkObject policy){
  87         policies.add(policy);
  88     }
  89
  90     @Override
  91     protected void addConstraints(Solver solver) {
  92         BoolExpr[] constr = new BoolExpr[constraints.size()];
  93         solver.add(constraints.toArray(constr));
  94         for (Core policy : policies){
  95             policy.addConstraints(solver);
  96         }
  97     }
  98
  99     private void mkTypes (String[] nodes, String[] addresses){
 100         //Nodes in a network
 101         node = ctx.mkEnumSort("Node", nodes);
 102
 103         for(int i=0;i<node.getConsts().length;i++){
 104             DatatypeExpr fd  = (DatatypeExpr)node.getConst(i);
 105             DumbNode dn =new DumbNode(ctx,new Object[]{fd});
 106
 107             nm.put(fd.toString(),dn);
 108         }
 109
 110         //Addresses for this network
 111         String[] new_addr = new String[addresses.length+1];
 112         for(int k=0;k<addresses.length;k++)
 113             new_addr[k] = addresses[k];
 114
 115         new_addr[new_addr.length-1] = "null";
 116         address = ctx.mkEnumSort("Address", new_addr);
 117         for(int i=0;i<address.getConsts().length;i++){
 118             DatatypeExpr fd  = (DatatypeExpr)address.getConst(i);
 119
 120
 121             am.put(fd.toString(),fd);
 122         }
 123
 124         // Type for packets, contains (some of these are currently represented as relations):
 125         // -   src: Source address
 126         // -   dest: Destination address
 127         // -   origin: Node where the data originated. (Node)
 128         // -   body: Packet contents. (Integer)
 129         // -   seq: Sequence number for packets. (Integer)
 130         // -   options: A representation for IP options. (Integer)
 131
 132         String[] fieldNames = new String[]{
 133                 "src","dest","inner_src","inner_dest","origin","orig_body","body","seq","proto","emailFrom","url","options","encrypted"};
 134         Sort[] srt = new Sort[]{
 135                 address,address,address,address,node,ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(),
 136                 ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkBoolSort()};
 137         Constructor packetcon = ctx.mkConstructor("packet", "is_packet", fieldNames, srt, null);
 138         packet = ctx.mkDatatypeSort("packet",  new Constructor[] {packetcon});
 139
 140
 141         for(int i=0;i<fieldNames.length;i++){
 142             pf.put(fieldNames[i], packet.getAccessors()[0][i]); // pf to get packet's function declarations by name
 143         }
 144
 145
 146         src_port = ctx.mkFuncDecl("sport", packet, ctx.mkIntSort());
 147         dest_port = ctx.mkFuncDecl("dport", packet, ctx.mkIntSort());
 148
 149         // Some commonly used relations
 150
 151         // nodeHasAddr: node -> address -> boolean
 152
 153         /* OUTPUT:
 154          * declare-fun nodeHasAddr (Node Address) Bool
 155          * declare-fun addrToNode (Address) Node
 156          */
 157
 158         nodeHasAddr = ctx.mkFuncDecl("nodeHasAddr", new Sort[]{node, address},ctx.mkBoolSort());
 159
 160
 161         // addrToNode: address -> node
 162         addrToNode = ctx.mkFuncDecl("addrToNode", address, node);
 163
 164
 165         // Send and receive both have the form:
 166         // source-> destination -> packet-> int-> bool
 167
 168
 169         /*OUTPUT:
 170          * declare-fun send (Node Node packet Int) Bool
 171          * declare-fun recv(Node Node paket Int) Bool
 172          */
 173
 174
 175         // send: node -> node -> packet-> int-> bool
 176         send = ctx.mkFuncDecl("send", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort());
 177
 178
 179         // recv: node -> node -> packet-> int-> bool
 180         recv = ctx.mkFuncDecl("recv", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort());
 181
 182     }
 183
 184     /**
 185      * Set up base conditions for the network
 186      */
 187     private void baseCondition(){
 188         // Basic constraints for the overall model
 189         Expr n_0 = ctx.mkConst("ctx_base_n_0", node);
 190         Expr n_1 = ctx.mkConst("ctx_base_n_1", node);
 191         Expr n_2 = ctx.mkConst("ctx_base_n_2", node);
 192         Expr p_0 = ctx.mkConst("ctx_base_p_0", packet);
 193         Expr p_1 = ctx.mkConst("ctx_base_p_1", packet);
 194         IntExpr t_0 = ctx.mkIntConst("ctx_base_t_0");
 195         IntExpr t_1 = ctx.mkIntConst("ctx_base_t_1");
 196
 197         // Constraint1 send(n_0, n_1, p_0, t_0) -> n_0 != n_1
 198         constraints.add(
 199                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 200                         ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0),ctx.mkNot(ctx.mkEq( n_0, n_1))),1,null,null,null,null));
 201
 202         // Constraint2 recv(n_0, n_1, p_0, t_0) -> n_0 != n_1
 203         constraints.add(
 204                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 205                         ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),ctx.mkNot(ctx.mkEq( n_0, n_1))),1,null,null,null,null));
 206
 207         // Constraint3 send(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest
 208         constraints.add(
 209                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 210                         ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 211                                 ctx.mkNot(ctx.mkEq(  pf.get("src").apply(p_0), pf.get("dest").apply(p_0)))),1,null,null,null,null));
 212
 213         // Constraint4 recv(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest
 214         constraints.add(
 215                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 216                         ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 217                                 ctx.mkNot(ctx.mkEq(pf.get("src").apply(p_0),pf.get("dest").apply(p_0)))),1,null,null,null,null));
 218
 219         // Constraint5 recv(n_0, n_1, p, t_0) -> send(n_0, n_1, p, t_1) && t_1 < t_0
 220         constraints.add(
 221                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 222                         ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 223                                 ctx.mkExists(new Expr[]{t_1},
 224                                         ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_1),
 225                                                 ctx.mkLt(t_1, t_0)),1,null,null,null,null)),1,null,null,null,null));
 226
 227         // Constraint6 send(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT
 228         constraints.add(
 229                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 230                         ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 231                                 ctx.mkAnd( ctx.mkGe((IntExpr)src_port.apply(p_0),(IntExpr)ctx.mkInt(0)),
 232                                         ctx.mkLt((IntExpr)src_port.apply(p_0),(IntExpr) ctx.mkInt(MAX_PORT)))),1,null,null,null,null));
 233
 234         // Constraint7 recv(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT
 235         constraints.add(
 236                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 237                         ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 238                                 ctx.mkAnd( ctx.mkGe((IntExpr)dest_port.apply(p_0),(IntExpr)ctx.mkInt(0)),
 239                                         ctx.mkLt((IntExpr)dest_port.apply(p_0),(IntExpr) ctx.mkInt(MAX_PORT)))),1,null,null,null,null));
 240
 241         // Constraint8 recv(n_0, n_1, p_0, t_0) -> t_0 > 0
 242         constraints.add(
 243                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 244                         ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 245                                 ctx.mkGt(t_0,ctx.mkInt(0))),1,null,null,null,null));
 246
 247         // Constraint9 send(n_0, n_1, p_0, t_0) -> t_0 > 0
 248         constraints.add(
 249                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 250                         ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 251                                 ctx.mkGt(t_0,ctx.mkInt(0))),1,null,null,null,null));
 252
 253         // Extra constriants for supporting the VPN gateway
 254         constraints.add(
 255                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 256                         ctx.mkImplies(
 257                                 ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 258                                         ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null")))),
 259                                 ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0)))),1,null,null,null,null));
 260
 261         constraints.add(
 262                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 263                         ctx.mkImplies(
 264                                 ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 265                                         ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null"))),
 266                                 ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null));
 267
 268         constraints.add(
 269                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 270                         ctx.mkImplies(
 271                                 ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 272                                         ctx.mkEq(this.pf.get("inner_dest").apply(p_0), this.am.get("null"))),
 273                                 ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null));
 274
 275         constraints.add(
 276                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 277                         ctx.mkImplies(
 278                                 ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 279                                         ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null")))),
 280                                 ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0)))),1,null,null,null,null));
 281
 282         constraints.add(
 283                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 284                         ctx.mkImplies(
 285                                 ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 286                                         ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null"))),
 287                                 ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null));
 288
 289         constraints.add(
 290                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
 291                         ctx.mkImplies(
 292                                 ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0),
 293                                         ctx.mkEq(this.pf.get("inner_dest").apply(p_0), this.am.get("null"))),
 294                                 ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null));
 295
 296         constraints.add(
 297                 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0, n_2, p_1, t_1},
 298                         ctx.mkImplies(
 299                                 ctx.mkAnd(
 300                                         ctx.mkLt(t_1, t_0),
 301                                         (BoolExpr)send.apply(n_0, n_1, p_0, t_0),
 302                                         (BoolExpr)this.pf.get("encrypted").apply(p_1),
 303                                         (BoolExpr)recv.apply(n_2, n_0, p_1, t_1),
 304                                         (BoolExpr)this.pf.get("encrypted").apply(p_0)),
 305                                 ctx.mkAnd(
 306                                         ctx.mkEq(this.pf.get("inner_src").apply(p_1), this.pf.get("inner_src").apply(p_0)),
 307                                         ctx.mkEq(this.pf.get("inner_dest").apply(p_1), this.pf.get("inner_dest").apply(p_0)),
 308                                         ctx.mkEq(this.pf.get("origin").apply(p_1), this.pf.get("origin").apply(p_0)),
 309                                         ctx.mkEq(this.pf.get("orig_body").apply(p_1), this.pf.get("orig_body").apply(p_0)),
 310                                         ctx.mkEq(this.pf.get("body").apply(p_1), this.pf.get("body").apply(p_0)),
 311                                         ctx.mkEq(this.pf.get("seq").apply(p_1), this.pf.get("seq").apply(p_0)),
 312                                         ctx.mkEq(this.pf.get("proto").apply(p_1), this.pf.get("proto").apply(p_0)),
 313                                         ctx.mkEq(this.pf.get("emailFrom").apply(p_1), this.pf.get("emailFrom").apply(p_0)),
 314                                         ctx.mkEq(this.pf.get("url").apply(p_1), this.pf.get("url").apply(p_0)),
 315                                         ctx.mkEq(this.pf.get("options").apply(p_1), this.pf.get("options").apply(p_0)))),1,null,null,null,null)
 316                 );
 317
 318
 319     }
 320
 321     /**
 322      * Two packets have equal headers
 323      * @param p1
 324      * @param p2
 325      * @return
 326      */
 327     public BoolExpr PacketsHeadersEqual(Expr p1, Expr p2){
 328         return ctx.mkAnd(new BoolExpr[]{
 329                 ctx.mkEq(pf.get("src").apply(p1), pf.get("src").apply(p2)),
 330                 ctx.mkEq(pf.get("dest").apply(p1), pf.get("dest").apply(p2)),
 331                 ctx.mkEq(pf.get("origin").apply(p1), pf.get("origin").apply(p2)),
 332                 ctx.mkEq(pf.get("seq").apply(p1), pf.get("seq").apply(p2)),
 333                 ctx.mkEq(src_port.apply(p1),src_port.apply(p2)),
 334                 ctx.mkEq(dest_port.apply(p1), dest_port.apply(p2)),
 335                 ctx.mkEq(pf.get("options").apply(p1),pf.get("options").apply(p2))});
 336     }
 337
 338     /**
 339      * Two packets have equal bodies
 340      * @param p1
 341      * @param p2
 342      * @return
 343      */
 344     public BoolExpr PacketContentEqual(Expr p1, Expr p2){
 345         return ctx.mkEq(pf.get("body").apply(p1), pf.get("body").apply(p2));
 346     }
 347
 348
 349     /* seems to be useless
 350      *
 351 public Function failurePredicate (NetContext context)
 352 {
 353     return (NetworkObject node) -> ctx.mkNot(context.failed (node.z3Node));
 354
 355 }*/
 356
 357     public BoolExpr destAddrPredicate (Expr p, DatatypeExpr address){
 358         return  ctx.mkEq(pf.get("dest").apply(p),address);
 359     }
 360
 361     public  BoolExpr srcAddrPredicate (Expr p, DatatypeExpr address){
 362         return  ctx.mkEq(pf.get("src").apply(p),address);
 363     }
 364
 365 }