diff options
Diffstat (limited to 'verigraph/src/it/polito/verigraph/mcnet/components')
9 files changed, 1316 insertions, 0 deletions
diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/Checker.java b/verigraph/src/it/polito/verigraph/mcnet/components/Checker.java new file mode 100644 index 0000000..2d1f2d5 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/Checker.java @@ -0,0 +1,377 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Context; +import com.microsoft.z3.Expr; +import com.microsoft.z3.IntExpr; +import com.microsoft.z3.Model; +import com.microsoft.z3.Solver; +import com.microsoft.z3.Status; +import it.polito.verigraph.mcnet.components.IsolationResult; +import it.polito.verigraph.mcnet.components.NetContext; +import it.polito.verigraph.mcnet.components.Network; +import it.polito.verigraph.mcnet.components.NetworkObject; + +/**Various checks for specific properties in the network. + * + * + */ +public class Checker { + + Context ctx; + Network net; + NetContext nctx; + Solver solver; + ArrayList<BoolExpr> constraints; + public BoolExpr [] assertions; + public Status result; + public Model model; + + + public Checker(Context context,NetContext nctx,Network network){ + this.ctx = context; + this.net = network; + this.nctx = nctx; + this.solver = ctx.mkSolver(); + this.constraints = new ArrayList<BoolExpr>(); + } + + /**Resets the constraints + * + */ + public void clearState (){ + this.solver.reset(); + this.constraints = new ArrayList<BoolExpr>(); + } + + /**Checks whether the source provided can reach the destination + * + * @param src + * @param dest + * @return + */ + public IsolationResult checkIsolationProperty (NetworkObject src, NetworkObject dest){ + assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + solver.push (); + addConstraints(); + + + Expr p0 = ctx.mkConst("check_isolation_p0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + Expr p1 = ctx.mkConst("check_isolation_p1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_1 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + IntExpr t_0 = ctx.mkIntConst("check_isolation_t0_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_1 = ctx.mkIntConst("check_isolation_t1_"+src.getZ3Node()+"_"+dest.getZ3Node()); + + // Constraint1recv(n_0,destNode,p0,t_0) + this.solver.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p0, t_0)); + + // Constraint2send(srcNode,n_1,p1,t_1) + this.solver.add((BoolExpr)nctx.send.apply(src.getZ3Node(), n_1, p1, t_1)); + + // Constraint3nodeHasAddr(srcNode,p1.srcAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(src.getZ3Node(), nctx.pf.get("src").apply(p1))); + + + // Constraint4p1.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p1), src.getZ3Node())); + + // Constraint5nodeHasAddr(destNode,p1.destAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(dest.getZ3Node(), nctx.pf.get("dest").apply(p1))); + + //NON sembrano necessari + // this.solver.add(z3.Or(this.ctx.nodeHasAddr(src.getZ3Node(), this.ctx.packet.src(p0)),\ + // this.ctx.nodeHasAddr(n_0, this.ctx.packet.src(p0)),\ + // this.ctx.nodeHasAddr(n_1, this.ctx.packet.src(p0)))) + //this.solver.add(this.ctx.packet.dest(p1) == this.ctx.packet.dest(p0)) + + // Constraint6p1.origin == p0.origin + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p1),nctx.pf.get("origin").apply(p0))); + + // Constraint7nodeHasAddr(destNode, p0.destAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(dest.getZ3Node(), nctx.pf.get("dest").apply(p0))); + + result = this.solver.check(); + model = null; + assertions = this.solver.getAssertions(); + if (result == Status.SATISFIABLE){ + model = this.solver.getModel(); + } + this.solver.pop(); + return new IsolationResult(ctx,result, p0, n_0, t_1, t_0, nctx, assertions, model); + } + + + + /*public IsolationResult CheckIsolationFlowProperty (NetworkObject src, NetworkObject dest){ +assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + solver.push (); + addConstraints(); + + Expr p = ctx.mkConst("check_isolation_p_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_1 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_2 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + + IntExpr t_0 = ctx.mkIntConst("check_isolation_t0_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_1 = ctx.mkIntConst("check_isolation_t1_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_2 = ctx.mkIntConst("check_isolation_t2_"+src.getZ3Node()+"_"+dest.getZ3Node()); + +// Constraint1recv(n_0,destNode,p,t_0) + this.solver.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p, t_0)); + +// Constraint2send(srcNode,n_1,p1,t_1) + this.solver.add((BoolExpr)nctx.send.apply(src.getZ3Node(), n_1, p, t_1)); + +// Constraint3nodeHasAddr(srcNode,p.srcAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(src.getZ3Node(), nctx.pf.get("src").apply(p))); + +// Constraint4p.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p), src.getZ3Node())); + + + Expr p_2 = ctx.mkConst("check_isolation_p_flow_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + + // Constraint5there does not exist p_2, n_2, t_2 : +// send(destNode,n_2,p_2,t_2) && +// p_2.srcAddr == p. destAddr && +// p_2.srcPort == p.destPort && +// p_2.destPort == p.srcPort && +// p_2.destt == p.src && +// t_2 < t_0 + this.solver.add(ctx.mkNot(ctx.mkExists(new Expr[]{p_2,n_2,t_2}, + ctx.mkAnd( + (BoolExpr)nctx.send.apply(dest.getZ3Node(), n_2, p_2, t_2), + ctx.mkEq(nctx.pf.get("src").apply(p_2), nctx.pf.get("dest").apply(p)), + ctx.mkEq(nctx.src_port.apply(p_2), nctx.dest_port.apply(p)), + ctx.mkEq(nctx.dest_port.apply(p_2), nctx.src_port.apply(p)), + ctx.mkEq(nctx.pf.get("dest").apply(p_2), nctx.pf.get("src").apply(p)), + ctx.mkLt(t_2,t_0)),1,null,null,null,null))); + //System.out.println((ctx.mkNot(ctx.mkExists(new Expr[]{p_2,n_2,t_2}, +ctx.mkAnd( +(BoolExpr)nctx.send.apply(dest.getZ3Node(), n_2, p_2, t_2), +ctx.mkEq(nctx.pf.get("src").apply(p_2), nctx.pf.get("dest").apply(p)), +ctx.mkEq(nctx.src_port.apply(p_2), nctx.dest_port.apply(p)), +ctx.mkEq(nctx.dest_port.apply(p_2), nctx.src_port.apply(p)), +ctx.mkEq(nctx.pf.get("dest").apply(p_2), nctx.pf.get("src").apply(p)), +ctx.mkLt(t_2,t_0)),1,null,null,null,null)))); + + result = this.solver.check(); + model = null; + assertions = this.solver.getAssertions(); + if (result == Status.SATISFIABLE){ + model = this.solver.getModel(); + } + this.solver.pop(); + return new IsolationResult(ctx,result, p, n_0, t_1, t_0, nctx, assertions, model); +} + + + + public IsolationResult CheckNodeTraversalProperty (NetworkObject src, NetworkObject dest, NetworkObject node){ +assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + solver.push (); + addConstraints(); + + Expr p = ctx.mkConst("check_isolation_p_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_1 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_2 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + + IntExpr t_0 = ctx.mkIntConst("check_isolation_t0_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_1 = ctx.mkIntConst("check_isolation_t1_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_2 = ctx.mkIntConst("check_isolation_t2_"+src.getZ3Node()+"_"+dest.getZ3Node()); + +// Constraint1recv(n_0,destNode,p,t_0) + this.solver.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p, t_0)); + +// Constraint2send(srcNode,n_1,p1,t_1) + this.solver.add((BoolExpr)nctx.send.apply(src.getZ3Node(), n_1, p, t_1)); + +// Constraint3nodeHasAddr(srcNode,p.srcAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(src.getZ3Node(), nctx.pf.get("src").apply(p))); + +// Constraint4p.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p), src.getZ3Node())); + + +//Constraint5there does not exist n_2, t_2 : recv(n_2,node,p,t_2) && t_2 < t_0 + this.solver.add(ctx.mkNot(ctx.mkExists(new Expr[]{n_2,t_2}, + ctx.mkAnd( + (BoolExpr)nctx.recv.apply(n_2, node.getZ3Node(), p, t_2), + ctx.mkLt(t_2,t_0)),1,null,null,null,null))); + +//Constraint 6there does not exist n_2, t_2 : send(node,n_2,p,t_2) && t_2 < t_0 + this.solver.add(ctx.mkNot(ctx.mkExists(new Expr[]{n_2,t_2}, +ctx.mkAnd( +(BoolExpr)nctx.send.apply(node.getZ3Node(), n_2, p, t_2), +ctx.mkLt(t_2,t_0)),1,null,null,null,null))); + + + result = this.solver.check(); + model = null; + assertions = this.solver.getAssertions(); + if (result == Status.SATISFIABLE){ + model = this.solver.getModel(); + } + this.solver.pop(); + return new IsolationResult(ctx,result, p, n_0, t_1, t_0, nctx, assertions, model); + + } + + public IsolationResult CheckLinkTraversalProperty (NetworkObject src, NetworkObject dest, NetworkObject le0, NetworkObject le1){ +assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + solver.push (); + addConstraints(); + + Expr p = ctx.mkConst("check_isolation_p_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + Expr n_1 =ctx.mkConst("check_isolation_n_1_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + + IntExpr t_0 = ctx.mkIntConst("check_isolation_t0_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_1 = ctx.mkIntConst("check_isolation_t1_"+src.getZ3Node()+"_"+dest.getZ3Node()); + IntExpr t_2 = ctx.mkIntConst("check_isolation_t2_"+src.getZ3Node()+"_"+dest.getZ3Node()); + +// Constraint1recv(n_0,destNode,p,t_0) + this.solver.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p, t_0)); + +// Constraint2send(srcNode,n_1,p,t_1) + this.solver.add((BoolExpr)nctx.send.apply(src.getZ3Node(), n_1, p, t_1)); + +// Constraint3nodeHasAddr(srcNode,p.srcAddr) + this.solver.add((BoolExpr)nctx.nodeHasAddr.apply(src.getZ3Node(), nctx.pf.get("src").apply(p))); + +// Constraint4p.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p), src.getZ3Node())); + +//Constraint5∃ t_1, t_2 : + // send(linkNode0,linkNode1,p,t_1) && +// recv(linkNode0,linkNode1,p,t_2) && +// t_1 < t_0 && +// t_2 < t_0 + this.solver.add(ctx.mkExists(new Expr[]{t_1,t_2}, + ctx.mkAnd( + (BoolExpr)nctx.send.apply(le0.getZ3Node(), le1.getZ3Node(), p, t_1), + (BoolExpr)nctx.recv.apply(le0.getZ3Node(), le1.getZ3Node(), p, t_2), + ctx.mkLt(t_1,t_0), + ctx.mkLt(t_2,t_0)),1,null,null,null,null)); + + + result = this.solver.check(); + model = null; + assertions = this.solver.getAssertions(); + if (result == Status.SATISFIABLE){ + model = this.solver.getModel(); + } + this.solver.pop(); + return new IsolationResult(ctx,result, p, n_0, t_1, t_0, nctx, assertions, model); + + } + + public Result CheckDataIsolationPropertyCore (NetworkObject src, NetworkObject dest){ + assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + List<BoolExpr> constr = new ArrayList(this.getConstraints()); + + Expr p = ctx.mkConst("check_isolation_p_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + + IntExpr t = ctx.mkIntConst("check_isolation_t_"+src.getZ3Node()+"_"+dest.getZ3Node()); + +// Constraint1recv(n_0,destNode,p,t) + constr.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p, t)); + + +// Constraint2p.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p), src.getZ3Node())); + + this.solver.push(); + + // Constraint3for each constraint( n -> constraint) + ArrayList<BoolExpr> names =new ArrayList<BoolExpr>(); + for(BoolExpr con : constr){ + BoolExpr n = ctx.mkBoolConst(""+con); + names.add(n); + this.solver.add(ctx.mkImplies(n, con)); + } + + BoolExpr[] nam = new BoolExpr[names.size()]; + result = this.solver.check(names.toArray(nam)); + Result ret =null; + + if (result == Status.SATISFIABLE){ + System.out.println("SAT"); + ret = new Result(ctx,this.solver.getModel()); + }else if(result == Status.UNSATISFIABLE){ + System.out.println("unsat"); + ret = new Result(ctx,this.solver.getUnsatCore()); + } + this.solver.pop(); + return ret; + } + + public DataIsolationResult CheckDataIsolationProperty(NetworkObject src, NetworkObject dest){ + assert(net.elements.contains(src)); + assert(net.elements.contains(dest)); + solver.push (); + addConstraints(); + + Expr p = ctx.mkConst("check_isolation_p_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.packet); + + Expr n_0 =ctx.mkConst("check_isolation_n_0_"+src.getZ3Node()+"_"+dest.getZ3Node(), nctx.node); + IntExpr t = ctx.mkIntConst("check_isolation_t_"+src.getZ3Node()+"_"+dest.getZ3Node()); + +// Constraint1recv(n_0,destNode,p,t) + this.solver.add((BoolExpr)nctx.recv.apply(n_0, dest.getZ3Node(), p, t)); + +// Constraint2p.origin == srcNode + this.solver.add(ctx.mkEq(nctx.pf.get("origin").apply(p), src.getZ3Node())); + + result = this.solver.check(); + model = null; + assertions = this.solver.getAssertions(); + if (result == Status.SATISFIABLE){ + model = this.solver.getModel(); + } + this.solver.pop(); + return new DataIsolationResult(ctx,result, p, n_0, t, nctx, assertions, model); + } + */ + + + + public void addConstraints(){ + nctx.addConstraints(solver); + net.addConstraints(solver); + for (NetworkObject el : net.elements) + el.addConstraints(solver); + } + + + public List<BoolExpr> getConstraints(){ + Solver l = ctx.mkSolver(); + nctx.addConstraints(l); + net.addConstraints(l); + for (NetworkObject el : net.elements) + el.addConstraints(l); + return Arrays.asList(l.getAssertions()); + } +} diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/Core.java b/verigraph/src/it/polito/verigraph/mcnet/components/Core.java new file mode 100644 index 0000000..3789817 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/Core.java @@ -0,0 +1,43 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import com.microsoft.z3.Context; +import com.microsoft.z3.Solver; + +/**Core component for everything that matters + * + * + */ +public abstract class Core{ + + final int MAX_PORT = 512; + + /** + * Base class for all objects in the modeling framework + * @param ctx + * @param args + */ + public Core(Context ctx, Object[]... args){ // Object[]... -> The nearest way to implement variable length argument lists + //in Java, in the most generic way. + init(ctx,args); + } + /** + * Override _init for any constructor initialization. Avoids having to explicitly call super.__init__ every Time.class + * @param ctx + * @param args + */ + abstract protected void init(Context ctx,Object[]... args); + + /** + * Add constraints to solver + * @param solver + */ + abstract protected void addConstraints(Solver solver); +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/DataIsolationResult.java b/verigraph/src/it/polito/verigraph/mcnet/components/DataIsolationResult.java new file mode 100644 index 0000000..b56f960 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/DataIsolationResult.java @@ -0,0 +1,40 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Context; +import com.microsoft.z3.Expr; +import com.microsoft.z3.Model; +import com.microsoft.z3.Status; + +import it.polito.verigraph.mcnet.components.NetContext; + +/**Data structure for the response to a check request for data isolation property + * + */ +public class DataIsolationResult { + + Context ctx; + public NetContext nctx; + public Status result; + public Model model; + public Expr violating_packet,last_hop,last_time,t_1; + public BoolExpr [] assertions; + + public DataIsolationResult(Context ctx,Status result, Expr violating_packet, Expr last_hop, Expr last_time, NetContext nctx, BoolExpr[] assertions, Model model){ + this.ctx = ctx; + this.result = result; + this.violating_packet = violating_packet; + this.last_hop = last_hop; + this.model = model; + this.last_time = last_time; + this.assertions = assertions; + } +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/IsolationResult.java b/verigraph/src/it/polito/verigraph/mcnet/components/IsolationResult.java new file mode 100644 index 0000000..0fe0946 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/IsolationResult.java @@ -0,0 +1,42 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Context; +import com.microsoft.z3.Expr; +import com.microsoft.z3.Model; +import com.microsoft.z3.Status; + +import it.polito.verigraph.mcnet.components.NetContext; + +/** + * Data structure for the response to check requests for isolation properties + * + */ +public class IsolationResult { + + Context ctx; + public NetContext nctx; + public Status result; + public Model model; + public Expr violating_packet,last_hop,last_send_time,last_recv_time,t_1; + public BoolExpr [] assertions; + + public IsolationResult(Context ctx,Status result, Expr violating_packet, Expr last_hop, Expr last_send_time, Expr last_recv_time,NetContext nctx, BoolExpr[] assertions, Model model){ + this.ctx = ctx; + this.result = result; + this.violating_packet = violating_packet; + this.last_hop = last_hop; + this.model = model; + this.last_send_time = last_send_time; + this.last_recv_time = last_recv_time; + this.assertions = assertions; + } +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/NetContext.java b/verigraph/src/it/polito/verigraph/mcnet/components/NetContext.java new file mode 100644 index 0000000..f0db902 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/NetContext.java @@ -0,0 +1,365 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Constructor; +import com.microsoft.z3.Context; +import com.microsoft.z3.DatatypeExpr; +import com.microsoft.z3.DatatypeSort; +import com.microsoft.z3.EnumSort; +import com.microsoft.z3.Expr; +import com.microsoft.z3.FuncDecl; +import com.microsoft.z3.IntExpr; +import com.microsoft.z3.Solver; +import com.microsoft.z3.Sort; +import it.polito.verigraph.mcnet.netobjs.DumbNode; +import it.polito.verigraph.mcnet.components.Core; +import it.polito.verigraph.mcnet.components.NetworkObject; + +/** + * Basic fields and other things required for model checking. + * + */ +public class NetContext extends Core{ + + + List<BoolExpr> constraints; + List<Core> policies; + + public HashMap<String,NetworkObject> nm; //list of nodes, callable by node name + public HashMap<String,DatatypeExpr> am; // list of addresses, callable by address name + public HashMap<String,FuncDecl> pf; + Context ctx; + public EnumSort node,address; + public FuncDecl src_port,dest_port,nodeHasAddr,addrToNode,send,recv; + public DatatypeSort packet; + + /* Constants definition + - used in the packet proto field */ + public final int HTTP_REQUEST = 1; + public final int HTTP_RESPONSE = 2; + public final int POP3_REQUEST = 3; + public final int POP3_RESPONSE = 4; + + /** + * Context for all of the rest that follows. Every network needs one of these + * @param ctx + * @param args + */ + public NetContext(Context ctx,Object[]... args ){ + super(ctx,args); + + } + + @Override + protected void init(Context ctx, Object[]... args) { + this.ctx = ctx; + nm = new HashMap<String,NetworkObject>(); //list of nodes, callable by node name + am = new HashMap<String,DatatypeExpr>(); // list of addresses, callable by address name + pf= new HashMap<String,FuncDecl>() ; + + + mkTypes((String[])args[0],(String[])args[1]); + + constraints = new ArrayList<BoolExpr>(); + policies = new ArrayList<Core>(); + + baseCondition(); + + } + + /** + * A policy is a collection of shared algorithms or functions used by multiple components + * (for instance compression or DPI policies etc). + * @param policy + */ + public void AddPolicy (NetworkObject policy){ + policies.add(policy); + } + + @Override + protected void addConstraints(Solver solver) { + BoolExpr[] constr = new BoolExpr[constraints.size()]; + solver.add(constraints.toArray(constr)); + for (Core policy : policies){ + policy.addConstraints(solver); + } + } + + private void mkTypes (String[] nodes, String[] addresses){ + //Nodes in a network + node = ctx.mkEnumSort("Node", nodes); + + for(int i=0;i<node.getConsts().length;i++){ + DatatypeExpr fd = (DatatypeExpr)node.getConst(i); + DumbNode dn =new DumbNode(ctx,new Object[]{fd}); + + nm.put(fd.toString(),dn); + } + + //Addresses for this network + String[] new_addr = new String[addresses.length+1]; + for(int k=0;k<addresses.length;k++) + new_addr[k] = addresses[k]; + + new_addr[new_addr.length-1] = "null"; + address = ctx.mkEnumSort("Address", new_addr); + for(int i=0;i<address.getConsts().length;i++){ + DatatypeExpr fd = (DatatypeExpr)address.getConst(i); + + + am.put(fd.toString(),fd); + } + + // Type for packets, contains (some of these are currently represented as relations): + // - src: Source address + // - dest: Destination address + // - origin: Node where the data originated. (Node) + // - body: Packet contents. (Integer) + // - seq: Sequence number for packets. (Integer) + // - options: A representation for IP options. (Integer) + + String[] fieldNames = new String[]{ + "src","dest","inner_src","inner_dest","origin","orig_body","body","seq","proto","emailFrom","url","options","encrypted"}; + Sort[] srt = new Sort[]{ + address,address,address,address,node,ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(), + ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkIntSort(),ctx.mkBoolSort()}; + Constructor packetcon = ctx.mkConstructor("packet", "is_packet", fieldNames, srt, null); + packet = ctx.mkDatatypeSort("packet", new Constructor[] {packetcon}); + + + for(int i=0;i<fieldNames.length;i++){ + pf.put(fieldNames[i], packet.getAccessors()[0][i]); // pf to get packet's function declarations by name + } + + + src_port = ctx.mkFuncDecl("sport", packet, ctx.mkIntSort()); + dest_port = ctx.mkFuncDecl("dport", packet, ctx.mkIntSort()); + + // Some commonly used relations + + // nodeHasAddr: node -> address -> boolean + + /* OUTPUT: + * declare-fun nodeHasAddr (Node Address) Bool + * declare-fun addrToNode (Address) Node + */ + + nodeHasAddr = ctx.mkFuncDecl("nodeHasAddr", new Sort[]{node, address},ctx.mkBoolSort()); + + + // addrToNode: address -> node + addrToNode = ctx.mkFuncDecl("addrToNode", address, node); + + + // Send and receive both have the form: + // source-> destination -> packet-> int-> bool + + + /*OUTPUT: + * declare-fun send (Node Node packet Int) Bool + * declare-fun recv(Node Node paket Int) Bool + */ + + + // send: node -> node -> packet-> int-> bool + send = ctx.mkFuncDecl("send", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort()); + + + // recv: node -> node -> packet-> int-> bool + recv = ctx.mkFuncDecl("recv", new Sort[]{ node, node, packet, ctx.mkIntSort()},ctx.mkBoolSort()); + + } + + /** + * Set up base conditions for the network + */ + private void baseCondition(){ + // Basic constraints for the overall model + Expr n_0 = ctx.mkConst("ctx_base_n_0", node); + Expr n_1 = ctx.mkConst("ctx_base_n_1", node); + Expr n_2 = ctx.mkConst("ctx_base_n_2", node); + Expr p_0 = ctx.mkConst("ctx_base_p_0", packet); + Expr p_1 = ctx.mkConst("ctx_base_p_1", packet); + IntExpr t_0 = ctx.mkIntConst("ctx_base_t_0"); + IntExpr t_1 = ctx.mkIntConst("ctx_base_t_1"); + + // Constraint1 send(n_0, n_1, p_0, t_0) -> n_0 != n_1 + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + 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)); + + // Constraint2 recv(n_0, n_1, p_0, t_0) -> n_0 != n_1 + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + 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)); + + // Constraint3 send(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkNot(ctx.mkEq( pf.get("src").apply(p_0), pf.get("dest").apply(p_0)))),1,null,null,null,null)); + + // Constraint4 recv(n_0, n_1, p_0, t_0) -> p_0.src != p_0.dest + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkNot(ctx.mkEq(pf.get("src").apply(p_0),pf.get("dest").apply(p_0)))),1,null,null,null,null)); + + // Constraint5 recv(n_0, n_1, p, t_0) -> send(n_0, n_1, p, t_1) && t_1 < t_0 + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkExists(new Expr[]{t_1}, + ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_1), + ctx.mkLt(t_1, t_0)),1,null,null,null,null)),1,null,null,null,null)); + + // Constraint6 send(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkAnd( ctx.mkGe((IntExpr)src_port.apply(p_0),(IntExpr)ctx.mkInt(0)), + ctx.mkLt((IntExpr)src_port.apply(p_0),(IntExpr) ctx.mkInt(MAX_PORT)))),1,null,null,null,null)); + + // Constraint7 recv(n_0, n_1, p, t_0) -> p.src_port > 0 && p.dest_port < MAX_PORT + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkAnd( ctx.mkGe((IntExpr)dest_port.apply(p_0),(IntExpr)ctx.mkInt(0)), + ctx.mkLt((IntExpr)dest_port.apply(p_0),(IntExpr) ctx.mkInt(MAX_PORT)))),1,null,null,null,null)); + + // Constraint8 recv(n_0, n_1, p_0, t_0) -> t_0 > 0 + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkGt(t_0,ctx.mkInt(0))),1,null,null,null,null)); + + // Constraint9 send(n_0, n_1, p_0, t_0) -> t_0 > 0 + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkGt(t_0,ctx.mkInt(0))),1,null,null,null,null)); + + // Extra constriants for supporting the VPN gateway + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null")))), + 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)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null"))), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)send.apply(n_0, n_1, p_0, t_0), + ctx.mkEq(this.pf.get("inner_dest").apply(p_0), this.am.get("null"))), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkNot(ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null")))), + 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)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.am.get("null"))), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0}, + ctx.mkImplies( + ctx.mkAnd((BoolExpr)recv.apply(n_0, n_1, p_0, t_0), + ctx.mkEq(this.pf.get("inner_dest").apply(p_0), this.am.get("null"))), + ctx.mkEq(this.pf.get("inner_src").apply(p_0), this.pf.get("inner_dest").apply(p_0))),1,null,null,null,null)); + + constraints.add( + ctx.mkForall(new Expr[]{n_0, n_1, p_0, t_0, n_2, p_1, t_1}, + ctx.mkImplies( + ctx.mkAnd( + ctx.mkLt(t_1, t_0), + (BoolExpr)send.apply(n_0, n_1, p_0, t_0), + (BoolExpr)this.pf.get("encrypted").apply(p_1), + (BoolExpr)recv.apply(n_2, n_0, p_1, t_1), + (BoolExpr)this.pf.get("encrypted").apply(p_0)), + ctx.mkAnd( + ctx.mkEq(this.pf.get("inner_src").apply(p_1), this.pf.get("inner_src").apply(p_0)), + ctx.mkEq(this.pf.get("inner_dest").apply(p_1), this.pf.get("inner_dest").apply(p_0)), + ctx.mkEq(this.pf.get("origin").apply(p_1), this.pf.get("origin").apply(p_0)), + ctx.mkEq(this.pf.get("orig_body").apply(p_1), this.pf.get("orig_body").apply(p_0)), + ctx.mkEq(this.pf.get("body").apply(p_1), this.pf.get("body").apply(p_0)), + ctx.mkEq(this.pf.get("seq").apply(p_1), this.pf.get("seq").apply(p_0)), + ctx.mkEq(this.pf.get("proto").apply(p_1), this.pf.get("proto").apply(p_0)), + ctx.mkEq(this.pf.get("emailFrom").apply(p_1), this.pf.get("emailFrom").apply(p_0)), + ctx.mkEq(this.pf.get("url").apply(p_1), this.pf.get("url").apply(p_0)), + ctx.mkEq(this.pf.get("options").apply(p_1), this.pf.get("options").apply(p_0)))),1,null,null,null,null) + ); + + + } + + /** + * Two packets have equal headers + * @param p1 + * @param p2 + * @return + */ + public BoolExpr PacketsHeadersEqual(Expr p1, Expr p2){ + return ctx.mkAnd(new BoolExpr[]{ + ctx.mkEq(pf.get("src").apply(p1), pf.get("src").apply(p2)), + ctx.mkEq(pf.get("dest").apply(p1), pf.get("dest").apply(p2)), + ctx.mkEq(pf.get("origin").apply(p1), pf.get("origin").apply(p2)), + ctx.mkEq(pf.get("seq").apply(p1), pf.get("seq").apply(p2)), + ctx.mkEq(src_port.apply(p1),src_port.apply(p2)), + ctx.mkEq(dest_port.apply(p1), dest_port.apply(p2)), + ctx.mkEq(pf.get("options").apply(p1),pf.get("options").apply(p2))}); + } + + /** + * Two packets have equal bodies + * @param p1 + * @param p2 + * @return + */ + public BoolExpr PacketContentEqual(Expr p1, Expr p2){ + return ctx.mkEq(pf.get("body").apply(p1), pf.get("body").apply(p2)); + } + + + /* seems to be useless + * +public Function failurePredicate (NetContext context) +{ + return (NetworkObject node) -> ctx.mkNot(context.failed (node.z3Node)); + +}*/ + + public BoolExpr destAddrPredicate (Expr p, DatatypeExpr address){ + return ctx.mkEq(pf.get("dest").apply(p),address); + } + + public BoolExpr srcAddrPredicate (Expr p, DatatypeExpr address){ + return ctx.mkEq(pf.get("src").apply(p),address); + } + +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/Network.java b/verigraph/src/it/polito/verigraph/mcnet/components/Network.java new file mode 100644 index 0000000..df1cece --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/Network.java @@ -0,0 +1,314 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Context; +import com.microsoft.z3.DatatypeExpr; +import com.microsoft.z3.Expr; +import com.microsoft.z3.IntExpr; +import com.microsoft.z3.Solver; +import com.microsoft.z3.Z3Exception; +import it.polito.verigraph.mcnet.components.Core; +import it.polito.verigraph.mcnet.components.NetContext; +import it.polito.verigraph.mcnet.components.NetworkObject; +import it.polito.verigraph.mcnet.components.Tuple; + +/**Model for a network, encompasses routing and wiring + * + * + */ +public class Network extends Core{ + + Context ctx; + NetContext nctx; + List<BoolExpr> constraints; + public List<NetworkObject> elements; + + + + public Network(Context ctx,Object[]... args) { + super(ctx, args); + } + + @Override + protected void init(Context ctx, Object[]... args) { + this.ctx = ctx; + this.nctx = (NetContext) args[0][0]; + constraints = new ArrayList<BoolExpr>(); + elements = new ArrayList<NetworkObject>(); + + } + + /**Composes the network linking the configured network objects + * + * @param elements + */ + public void attach (NetworkObject ... elements){ + for(NetworkObject el : elements) + this.elements.add(el); + } + + @Override + protected void addConstraints(Solver solver) { + try { + BoolExpr[] constr = new BoolExpr[constraints.size()]; + solver.add(constraints.toArray(constr)); + } catch (Z3Exception e) { + e.printStackTrace(); + } + } + + /** + * Specify host to address mapping. + * Handles the case in which we have more than one address for a node + * @param addrmap + */ + public void setAddressMappings(ArrayList<Tuple<NetworkObject,ArrayList<DatatypeExpr>>> addrmap){ + // Set address mapping for nodes. + for (Tuple<NetworkObject,ArrayList<DatatypeExpr>> entry : addrmap) { + NetworkObject node=entry._1; + List<DatatypeExpr> addr=entry._2; + Expr a_0 = ctx.mkConst(node+"_address_mapping_a_0",nctx.address); + ArrayList<BoolExpr> or_clause = new ArrayList<BoolExpr>(); + + // Constraint 1 addrToNode(foreach ad in addr) = node + for (DatatypeExpr ad : addr){ + constraints.add(ctx.mkEq(nctx.addrToNode.apply(ad), node.getZ3Node())); + or_clause.add(ctx.mkEq(a_0,ad)); + + // System.out.println("Constraints mapping: " + (ctx.mkEq(nctx.addrToNode.apply(ad), node.getZ3Node()))); + + } + BoolExpr[] orClause = new BoolExpr[or_clause.size()]; + + // Constraint 2nodeHasAddr(node, a_0) == Or(foreach ad in addr (a_0 == ad)) + // Note we need the iff here to make sure that we set nodeHasAddr to false + // for other addresses. + constraints.add(ctx.mkForall(new Expr[]{a_0}, + ctx.mkEq(ctx.mkOr(or_clause.toArray(orClause)), nctx.nodeHasAddr.apply(node.getZ3Node(), a_0)),1,null,null,null,null)); + + + } + //System.out.println("Constraints mapping: " + constraints); + } + + + + /** + * Don't forward packets addressed to node + * @param node + */ + public void saneSend(NetworkObject node){ + Expr n_0 = ctx.mkConst(node+"_saneSend_n_0", nctx.node); + Expr p_0 = ctx.mkConst(node+"_saneSend_p_0", nctx.packet); + IntExpr t_0 = ctx.mkIntConst(node+"_saneSend_t_0"); + // Constant: node + //Constraint send(node, n_0, p, t_0) -> !nodeHasAddr(node, p.dest) + constraints.add( + ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(),n_0, p_0, t_0), + ctx.mkNot((BoolExpr)nctx.nodeHasAddr.apply( node.getZ3Node(), + nctx.pf.get("dest").apply(p_0)))),1,null,null,null,null)); + } + + /** + * Node sends all traffic through gateway + * @param node + * @param gateway + */ + public void setGateway (NetworkObject node, NetworkObject gateway){ + // SetGateway(self, node, gateway): All packets from node are sent through gateway + Expr n_0 = ctx.mkConst(node+"_gateway_n_0", nctx.node); + Expr p_0 = ctx.mkConst(node+"_gateway_p_0", nctx.packet); + IntExpr t_0 = ctx.mkIntConst(node+"_gateway_t_0"); + + //Constraint send(node, n_0, p_0, t_0) -> n_0 = gateway + constraints.add( + ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies( + (BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), + ctx.mkEq(n_0,gateway.getZ3Node())),1,null,null,null,null)); + + // constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + // ctx.mkImplies((BoolExpr)nctx.recv.apply(n_0, node.getZ3Node(), p_0, t_0), + // ctx.mkEq(n_0,gateway.getZ3Node())),1,null,null,null,null)); + } + + /** + * Assigns a specific routing table to a network object. Routing entries in the form: address -> node + * @param node + * @param routing_table + */ + public void routingTable (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table){ + compositionPolicy(node,routing_table); + } + + /** + * Composition policies steer packets between middleboxes. + * @param node + * @param policy + */ + public void compositionPolicy (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> policy){ + //Policy is of the form predicate -> node + Expr p_0 = ctx.mkConst(node+"_composition_p_0", nctx.packet); + Expr n_0 = ctx.mkConst(node+"_composition_n_0", nctx.node); + Expr t_0 = ctx.mkIntConst(node+"_composition_t_0"); + + HashMap<String,ArrayList<BoolExpr>> collected = new HashMap<String,ArrayList<BoolExpr>>(); + HashMap<String,NetworkObject> node_dict = new HashMap<String,NetworkObject>(); + BoolExpr predicates; + for(int y=0;y<policy.size();y++){ + Tuple<DatatypeExpr,NetworkObject> tp = policy.get(y); + if(collected.containsKey(""+tp._2)) collected.get(""+tp._2).add(nctx.destAddrPredicate(p_0,tp._1)); + else{ + ArrayList<BoolExpr> alb = new ArrayList<BoolExpr>(); + alb.add(nctx.destAddrPredicate(p_0,tp._1)); + collected.put(""+tp._2,alb); + + } + node_dict.put(""+tp._2, tp._2); + + } + // System.out.println("collected: " + collected); + + //Constraintforeach rtAddr,rtNode in rt( send(node, n_0, p_0, t_0) && + //Or(foreach rtAddr in rt destAddrPredicate(p_0,rtAddr)) -> n_0 == rtNode ) + for (Map.Entry<String,ArrayList<BoolExpr>> entry : collected.entrySet()) { + BoolExpr[] pred = new BoolExpr[entry.getValue().size()]; + predicates = ctx.mkOr(entry.getValue().toArray(pred)); + + constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies(ctx.mkAnd((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), predicates), + ctx.mkEq(n_0, node_dict.get(entry.getKey()).getZ3Node())),1,null,null,null,null)); + /*System.out.println("cnstraints: " + (ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies(ctx.mkAnd((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), predicates), + ctx.mkEq(n_0, node_dict.get(entry.getKey()).getZ3Node())),1,null,null,null,null)));*/ + } + //System.out.println("constraints composition policy: " + constraints); + + } + + /** + * Routing entries are in the form: address -> node. Also allows packet to be sent to another box for further processing + * @param node + * @param routing_table + * @param shunt_node + */ + public void routingTableShunt (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table,NetworkObject shunt_node){ + compositionPolicyShunt(node,routing_table,shunt_node); + } + + /** + * Composition policies steer packets between middleboxes.Policy is in the form: predicate -> node + * @param node + * @param routing_table + * @param shunt_node + */ + public void compositionPolicyShunt (NetworkObject node,ArrayList<Tuple<DatatypeExpr,NetworkObject>> routing_table,NetworkObject shunt_node){ + Expr p_0 = ctx.mkConst(node+"_composition_p_0", nctx.packet); + Expr n_0 = ctx.mkConst(node+"_composition_n_0", nctx.node); + Expr t_0 = ctx.mkIntConst(node+"_composition_t_0"); + + HashMap<String,ArrayList<BoolExpr>> collected = new HashMap<String,ArrayList<BoolExpr>>(); + HashMap<String,NetworkObject> node_dict = new HashMap<String,NetworkObject>(); + BoolExpr predicates; + for(int y=0;y<routing_table.size();y++){ + Tuple<DatatypeExpr,NetworkObject> tp = routing_table.get(y); + if(collected.containsKey(""+tp._2)) collected.get(""+tp._2).add(nctx.destAddrPredicate(p_0,tp._1)); + else{ + ArrayList<BoolExpr> alb = new ArrayList<BoolExpr>(); + alb.add(nctx.destAddrPredicate(p_0,tp._1)); + collected.put(""+tp._2,alb); + } + node_dict.put(""+tp._2, tp._2); + } + + //Constraintforeach rtAddr,rtNode in rt( send(node, n_0, p_0, t_0) && + //Or(foreach rtAddr in rt destAddrPredicate(p_0,rtAddr)) -> n_0 == rtNode ) + for (Map.Entry<String,ArrayList<BoolExpr>> entry : collected.entrySet()) { + BoolExpr[] pred = new BoolExpr[entry.getValue().size()]; + predicates = ctx.mkOr(entry.getValue().toArray(pred)); + + constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies(ctx.mkAnd((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), predicates), + ctx.mkOr(ctx.mkEq(n_0, node_dict.get(entry.getKey()).getZ3Node()),ctx.mkEq(n_0, shunt_node.getZ3Node()))),1,null,null,null,null)); + } + + } + + // public void SimpleIsolation (NetworkObject node, ArrayList<DatatypeExpr> addresses){ + // Expr p = ctx.mkConst(node+"_s_p", nctx.packet); + // Expr n = ctx.mkConst(node+"_s_n", nctx.node); + // IntExpr t = ctx.mkInt(node+"_s_t"); + // + // BoolExpr[] a_pred= new BoolExpr[addresses.size()]; + // for(int y=0;y<addresses.size();y++){ + // DatatypeExpr de = addresses.get(y); + // a_pred[y] = ctx.mkOr(ctx.mkEq(nctx.pf.get("src").apply(p), de),ctx.mkEq(nctx.pf.get("dest").apply(p), de)); + // } + // + // constraints.add( + // ctx.mkForall(new Expr[]{p, n, t}, + // ctx.mkImplies((BoolExpr)nctx.recv.apply(n, node.getZ3Node(), p, t), + // ctx.mkOr(a_pred)),1,null,null,null,null)); + // constraints.add( + // ctx.mkForall(new Expr[]{p, n, t}, + // ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(), n, p, t), + // ctx.mkOr(a_pred)),1,null,null,null,null)); + // } + + + /** + * Set isolation constraints on a node. + * Doesn't need to be set but useful when interfering policies are in play. + * @param node + * @param adjacencies + * + */ + public void SetIsolationConstraint ( NetworkObject node, ArrayList<NetworkObject> adjacencies){ + + Expr n_0 = ctx.mkConst(node+"_isolation_n_0", nctx.node); + Expr p_0 = ctx.mkConst(node+"_isolation_p_0", nctx.packet); + IntExpr t_0 = ctx.mkInt(node+"_isolation_t_0"); + + BoolExpr[] adj = new BoolExpr[adjacencies.size()]; + for(int y=0;y<adjacencies.size();y++){ + NetworkObject no = adjacencies.get(y); + adj[y] = ctx.mkEq(n_0,no.getZ3Node()); + } + BoolExpr clause = ctx.mkOr(adj); + + constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies((BoolExpr)nctx.send.apply(node.getZ3Node(), n_0, p_0, t_0), + clause),1,null,null,null,null)); + constraints.add(ctx.mkForall(new Expr[]{n_0, p_0, t_0}, + ctx.mkImplies((BoolExpr)nctx.recv.apply(n_0, node.getZ3Node(), p_0, t_0), + clause),1,null,null,null,null)); + } + + /** + * Return all currently attached endhosts + * @return NetworkObject + */ + public List<String> EndHosts(){ + List<String> att_nos = new ArrayList<String>(); + for(NetworkObject el :elements){ + if(el.isEndHost){ + //System.out.println("el: "+el); + att_nos.add(el.getZ3Node().toString()); + } + } + return att_nos; + } +} diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/NetworkObject.java b/verigraph/src/it/polito/verigraph/mcnet/components/NetworkObject.java new file mode 100644 index 0000000..0438b04 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/NetworkObject.java @@ -0,0 +1,59 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import com.microsoft.z3.Context; +import com.microsoft.z3.DatatypeExpr; + +import it.polito.verigraph.mcnet.components.Core; + +/** Represents a generic network object. + * + * + */ +public abstract class NetworkObject extends Core{ + + public NetworkObject(Context ctx,Object[]... args) { + super(ctx,args); + } + + protected DatatypeExpr z3Node; + protected boolean isEndHost; + /** + * Get a reference to the z3 node this class wraps around + * @return + */ + abstract public DatatypeExpr getZ3Node(); + + public String toString(){ + return z3Node.toString(); + } + + //There is probably an error: z3Node.hashCode = 0 because AST.hashCode() has always hash=0 + /*public int hashCode(){ + return z3Node.hashCode(); +}*/ + + /** + * A simple way to determine the set of endhosts + * @return + */ + public boolean isEndHost(){ + return isEndHost; + } + + /** + * Wrap methods to set policy + * @param policy + * @throws UnsupportedOperationException + */ + void setPolicy (Object policy) throws UnsupportedOperationException{ + throw new UnsupportedOperationException(); + } +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/Result.java b/verigraph/src/it/polito/verigraph/mcnet/components/Result.java new file mode 100644 index 0000000..3bc6512 --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/Result.java @@ -0,0 +1,42 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +import com.microsoft.z3.BoolExpr; +import com.microsoft.z3.Context; +import com.microsoft.z3.Model; + +/**Data structure for the core of the response to a check request for data isolation property + * + */ +public class Result { + Context ctx; + public Model model; + public BoolExpr[] unsat_core; + + /** + * + * @param ctx + * @param model + */ + public Result(Context ctx, Model model){ + this.ctx = ctx; + this.model = model; + } + + /** + * + * @param ctx + * @param unsat_core + */ + public Result(Context ctx, BoolExpr[] unsat_core){ + this.ctx = ctx; + this.unsat_core = unsat_core; + } +}
\ No newline at end of file diff --git a/verigraph/src/it/polito/verigraph/mcnet/components/Tuple.java b/verigraph/src/it/polito/verigraph/mcnet/components/Tuple.java new file mode 100644 index 0000000..a6c3ece --- /dev/null +++ b/verigraph/src/it/polito/verigraph/mcnet/components/Tuple.java @@ -0,0 +1,34 @@ +/******************************************************************************* + * Copyright (c) 2017 Politecnico di Torino and others. + * + * All rights reserved. This program and the accompanying materials + * are made available under the terms of the Apache License, Version 2.0 + * which accompanies this distribution, and is available at + * http://www.apache.org/licenses/LICENSE-2.0 + *******************************************************************************/ +package it.polito.verigraph.mcnet.components; + +/** A data structure which is an utility to make a generic couple of objects with different types in Java + * + */ +public class Tuple<T, U> { + public final T _1; + public final U _2; + + + public Tuple(T arg1,U arg2) { + super(); + this._1 = arg1; + this._2 = arg2; + } + + public Tuple(){ + this._1 = null; + this._2 = null; + } + + @Override + public String toString() { + return String.format("(%s, %s)", _1, _2); + } +}
\ No newline at end of file |