1 /*******************************************************************************
2 * Copyright (c) 2017 Politecnico di Torino and others.
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;
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;
30 * Basic fields and other things required for model checking.
33 public class NetContext extends Core{
36 List<BoolExpr> constraints;
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;
43 public EnumSort node,address;
44 public FuncDecl src_port,dest_port,nodeHasAddr,addrToNode,send,recv;
45 public DatatypeSort packet;
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;
55 * Context for all of the rest that follows. Every network needs one of these
59 public NetContext(Context ctx,Object[]... args ){
65 protected void init(Context ctx, Object[]... args) {
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>() ;
72 mkTypes((String[])args[0],(String[])args[1]);
74 constraints = new ArrayList<BoolExpr>();
75 policies = new ArrayList<Core>();
82 * A policy is a collection of shared algorithms or functions used by multiple components
83 * (for instance compression or DPI policies etc).
86 public void AddPolicy (NetworkObject policy){
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);
99 private void mkTypes (String[] nodes, String[] addresses){
101 node = ctx.mkEnumSort("Node", nodes);
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});
107 nm.put(fd.toString(),dn);
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];
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);
121 am.put(fd.toString(),fd);
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)
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});
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
146 src_port = ctx.mkFuncDecl("sport", packet, ctx.mkIntSort());
147 dest_port = ctx.mkFuncDecl("dport", packet, ctx.mkIntSort());
149 // Some commonly used relations
151 // nodeHasAddr: node -> address -> boolean
154 * declare-fun nodeHasAddr (Node Address) Bool
155 * declare-fun addrToNode (Address) Node
158 nodeHasAddr = ctx.mkFuncDecl("nodeHasAddr", new Sort[]{node, address},ctx.mkBoolSort());
161 // addrToNode: address -> node
162 addrToNode = ctx.mkFuncDecl("addrToNode", address, node);
165 // Send and receive both have the form:
166 // source-> destination -> packet-> int-> bool
170 * declare-fun send (Node Node packet Int) Bool
171 * declare-fun recv(Node Node paket Int) Bool
175 // send: node -> node -> packet-> int-> bool
176 send = ctx.mkFuncDecl("send", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort());
179 // recv: node -> node -> packet-> int-> bool
180 recv = ctx.mkFuncDecl("recv", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort());
185 * Set up base conditions for the network
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");
197 // Constraint1 send(n_0, n_1, p_0, t_0) -> n_0 != n_1
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));
202 // Constraint2 recv(n_0, n_1, p_0, t_0) -> n_0 != n_1
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));
207 // Constraint3 send(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest
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));
213 // Constraint4 recv(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest
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));
219 // Constraint5 recv(n_0, n_1, p, t_0) -> send(n_0, n_1, p, t_1) && t_1 < t_0
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));
227 // Constraint6 send(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT
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));
234 // Constraint7 recv(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT
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));
241 // Constraint8 recv(n_0, n_1, p_0, t_0) -> t_0 > 0
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));
247 // Constraint9 send(n_0, n_1, p_0, t_0) -> t_0 > 0
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));
253 // Extra constriants for supporting the VPN gateway
255 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
262 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
269 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
276 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
283 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
290 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0},
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));
297 ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0, n_2, p_1, t_1},
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)),
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)
322 * Two packets have equal headers
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))});
339 * Two packets have equal bodies
344 public BoolExpr PacketContentEqual(Expr p1, Expr p2){
345 return ctx.mkEq(pf.get("body").apply(p1), pf.get("body").apply(p2));
349 /* seems to be useless
351 public Function failurePredicate (NetContext context)
353 return (NetworkObject node) -> ctx.mkNot(context.failed (node.z3Node));
357 public BoolExpr destAddrPredicate (Expr p, DatatypeExpr address){
358 return ctx.mkEq(pf.get("dest").apply(p),address);
361 public BoolExpr srcAddrPredicate (Expr p, DatatypeExpr address){
362 return ctx.mkEq(pf.get("src").apply(p),address);