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