summaryrefslogtreecommitdiffstats
path: root/docs/developer/design
diff options
context:
space:
mode:
Diffstat (limited to 'docs/developer/design')
-rw-r--r--docs/developer/design/images/verigraph.pngbin0 -> 207401 bytes
-rw-r--r--docs/developer/design/verigraph.rst43
2 files changed, 43 insertions, 0 deletions
diff --git a/docs/developer/design/images/verigraph.png b/docs/developer/design/images/verigraph.png
new file mode 100644
index 0000000..dfcd586
--- /dev/null
+++ b/docs/developer/design/images/verigraph.png
Binary files differ
diff --git a/docs/developer/design/verigraph.rst b/docs/developer/design/verigraph.rst
index 91d5a36..d364091 100644
--- a/docs/developer/design/verigraph.rst
+++ b/docs/developer/design/verigraph.rst
@@ -5,3 +5,46 @@
Parser verigraph
=================
+This document provides a description of VeriGraph, a formal verification tool for service graphs.
+
+.. contents::
+ :depth: 3
+ :local:
+
+Overview
+--------
+Given a service graph, which can include stateful network functions and their configurations
+(e.g., filtering rules for firewalls, and blacklists for anti-spamming filters), VeriGraph can
+accurately and quickly check reachability properties in the graph (e.g. if a particular flow of
+packets can go from one node of the graph to another node).
+
+VeriGraph exploits Satisfiability Modulo Theories (SMT) and the general-purpose SMT solver Z3.
+It includes a library of network function models.
+
+Architecture
+------------
+VeriGraph exploits two sub-modules:
+
+- **Z3**, the SMT solver developed by Microsoft
+- **Neo4JManger**, a module that can store service graphs into a *Neo4J* graph-oriented database
+
+Neo4JManager can also extract from a service graph all the VNF chains that are
+relevant for checking the reachability properties of that graph.
+
+How the tool works
+------------------
+VeriGraph accepts JSON service graph descriptions that include endpoints, VNF instances, logical
+directed links connecting them, and VNF configurations.
+
+When VeriGraph receives a service graph and a reachability property to verify, it forwards the graph
+to Neo4JManager and asks Neo4JManager to extract the chains that connect the nodes addressed by the
+property to be checked. For each one of these chains, VeriGraph builds a set of first order logic
+formulas that represent a mathematical model of the forwarding behavior of the chain.
+This model takes into account the forwarding behavior of the links and of the VNFs included in the chain,
+taking into consideration their configurations. If the formulas that make up the model are satisfiable,
+this means that it is possible for a packet to traverse the chain from one end to the other.
+VeriGraph passes this model to Z3 which checks its satisfiability.
+Based on the satisfiability result of the formulas that model the different paths, VeriGraph finally
+derives the overall result (reachability property satisfied or not).
+
+.. image:: /images/verigraph.png