related work + conclusion

7 files changed, 204 insertions, 48 deletions

diff --git a/chapters/04-related-work.tex b/chapters/04-related-work.tex
index 1f01b8e..9378dd3 100644
--- a/chapters/04-related-work.tex
+++ b/chapters/04-related-work.tex
@@ -1,4 +1,31 @@
 \chapter{Related Work}
 \label{ch:related-work}
 
-% This chapter discusses related literature and positions this work within the field.
+The field of neural network verification is a highly active research area, driven by the need to
+provide formal safety for artificial intelligence applications in safety-critical systems.
+Existing verification techniques can be classified into complete and incomplete methods.
+
+\paragraph{Complete solvers}
+Complete verification methods guarantee to either find a counterexample violating the property or
+prove that the property holds. Katz et al.~\cite{katz2017reluplex} presented \textit{Reluplex}, a
+pioneering SMT solver designed specifically for networks with ReLU activation functions. It extends
+the standard simplex method, originally created by Dantzig~\cite{dantzig1947simplex}, to handle ReLU
+constraints directly. Katz et al.~\cite{katz2019marabou} also presented \textit{Marabou}, successor
+of \textit{Reluplex}, a more modular and highly optimized framework that supports a wider range of
+activation functions.
+
+\paragraph{Incomplete solvers}
+Incomplete verification methods use abstract interpretation to soundly approximate neural networks.
+Wang et al.~\cite{wang2018efficientformalsafetyanalysis} presented \textit{Neurify}, a tool that
+utilizes symbolic interval analysis to compute tight bounds on neurons and prune ReLUs that are
+guaranteed to be stably active or inactive.
+
+\paragraph{Hybrid solvers}
+\textit{$\alpha$-$\beta$-CROWN} is a neural network verifier that combines a series of complete
+verification methods, based on branch-and-bound, and incomplete verification methods, based on
+bound-propagation: \textit{CROWN} (Zhang et al.~\cite{zhang2018efficient}), \textit{auto\_LiRPA}
+(Xu et al.~\cite{xu2020automatic}), \textit{$\alpha$-CROWN} (Xu et al.~\cite{xu2021fast}),
+\textit{$\beta$-CROWN} (Wang et al.~\cite{wang2021beta}), \textit{GenBaB} (Shi et
+al~\cite{shi2024genbab}), \textit{GCP-CROWN} (Zhang et al~\cite{zhang2022general}) and
+\textit{BICCOS} (Zhou et al.~\cite{zhou2024scalable}). Thanks to this hybrid approach, 
+\textit{$\alpha$-$\beta$-CROWN} achieved state-of-the-art perfomance and won VNNCOMP 2021-2025.
diff --git a/chapters/05-conclusion.tex b/chapters/05-conclusion.tex
index d90f15c..271c45a 100644
--- a/chapters/05-conclusion.tex
+++ b/chapters/05-conclusion.tex
@@ -1,4 +1,40 @@
-\chapter{Conclusion}
+\chapter{Conclusion and Future Work}
 \label{ch:conclusion}
 
-% This chapter provides concluding remarks and potentially directions for future work.
+In this thesis, we introduced \textbf{VEIN}, a novel framework for neural network verification with
+a particular focus on network equivalence checking. The key achievements of this work include:
+\begin{itemize}
+	\item The formalization and implementation of an ONNX-to-IN translation pipeline.
+	\item The design of interaction rules implementing symbolic constant folding, constant
+		propagation, and identity elimination.
+	\item A soundness proof of the reduction engine, demonstrating that each graph rewriting step
+		preserves the semantic of the original neural network.
+	\item An experimental evaluation verifying the effectiveness of VEIN on multiple benchmarks
+		across strict, epsilon, and argmax equivalence metrics.
+\end{itemize}
+
+While the current version of VEIN establishes a solid foundation for IN-based verification, several
+limitations remain to be addressed in future research. The future roadmap focuses on performance
+optimizations, modeling expressiveness and advanced interaction rules.
+
+\paragraph{Custom Reduction Engine}
+The current reduction engine relies on a modified version of the INPLA interpreter. While
+practical, it is prone to high memory overhead. A core objective of future work is to replace
+INPLA with a custom reduction engine written in Rust. Implementing the engine in Rust will provide:
+memory safety without garbage collection, high-performance concurrency and flexibility.
+
+\paragraph{Complex Agent Attributes}
+Currently, interaction net agents in VEIN are limited to simple scalar attributes. This restriction
+prevents the direct translation of complex operations into single agents. Future work will extend
+the framework to support complex attributes, such as tensors and boundary intervals.
+
+\paragraph{Advanced Interaction Rules and Symbolic ReLU Pruning}
+The interaction rules implemented in VEIN are currently limited to constant folding of linear
+operations. Non-linear activation functions, specifically ReLUs, are passed through without
+modification unless their inputs are concrete constants. To improve simplification efficiency, we
+plan to implement range analysis and interval arithmetic directly within the IN, substantially
+reducing the number of split constraints faced by the SMT solver.
+
+\paragraph{Integration with Specialized Solvers}
+The current evaluation of VEIN targets the Z3 solver, the intermediate SMT-LIB representation can be
+adapted to other backends like Marabou~\cite{katz2019marabou}.
diff --git a/chapters/background/01-neural-networks.tex b/chapters/background/01-neural-networks.tex
index 848f65a..a1ecad2 100644
--- a/chapters/background/01-neural-networks.tex
+++ b/chapters/background/01-neural-networks.tex
@@ -2,7 +2,7 @@
 \label{sec:neural-networks}
 
 A neural network is a computational model inspired by biological neural networks. It consists of
-connected nodes called neuron, introduced in its early form by Rosenblatt et al.~\cite{rosenblatt1958perceptron}.
+connected nodes called neuron, introduced in its early form by Rosenblatt~\cite{rosenblatt1958perceptron}.
 \textit{Multi-Layer Perceptrons} is an architecture composed of sequential layers, trained using
 backpropagation as popularized by Rumelhart et al.~\cite{rumelhart1986learning}.
 
diff --git a/chapters/background/03-satisfiability-modulo-theories.tex b/chapters/background/03-satisfiability-modulo-theories.tex
index bd90559..a55d54d 100644
--- a/chapters/background/03-satisfiability-modulo-theories.tex
+++ b/chapters/background/03-satisfiability-modulo-theories.tex
@@ -19,6 +19,6 @@ To represent a ReLU activation $y = \max(0, x)$ in LRA, we must introduce a disj
     (x > 0 \land y = x) \lor (x \le 0 \land y = 0)
 \end{equation}
 For a network with $N$ ReLU neurons, there are up to $2^N$ possible activation patterns. Solving the
-verification property requires the SMT solver, such as Z3 presented by Demura et al.~\cite{demoura2008z3},
+verification property requires the SMT solver, such as Z3 presented by De Moura et al.~\cite{demoura2008z3},
 to implicitly explore this branching search space.
 
diff --git a/chapters/core/03-benchmarks.tex b/chapters/core/03-benchmarks.tex
index 132b56d..a8c1317 100644
--- a/chapters/core/03-benchmarks.tex
+++ b/chapters/core/03-benchmarks.tex
@@ -3,18 +3,17 @@
 
 This section contains the benchmark data, illustrated in \textbf{\Cref{tab:benchmarks}}.
 
-VEIN was tested on a laptop Zenbook UX3402ZA with:
+VEIN was tested with the following hardware:
 \begin{itemize}
-	\item \textbf{CPU}: 12th Gen Intel Core i5-1240P
-	\item \textbf{RAM}: 8GiB
-	\item \textbf{SWAP}: 16GiB on NVMe
+	\item \textbf{CPU}: AMD Ryzen 7 5700x3D
+	\item \textbf{RAM}: 16GiB
 \end{itemize}
 using Hyperfine\footnote{\href{https://github.com/sharkdp/hyperfine}{\textbf{Hyperfine Github repository}}.}
 benchmarking tool. Hyperfine runs the test ten times, then reports the mean and standard deviation of
 execution time.
 
 \paragraph{Iris}
-Dataset of iris flowers presented by Fisher et al.~\cite{fisher1936iris}. It consists of three
+Dataset of iris flowers presented by Fisher~\cite{fisher1936iris}. It consists of three
 species of flower (\textit{Iris setosa}, \textit{Iris virginica} and \textit{Iris versicolor}) with fifty samples each. Each
 sample has four features: width and length of sepals and petals.
 \paragraph{Pendulum}
@@ -48,38 +47,38 @@ define three kinds of equivalence:
 	\centering
 	\begin{tabular}[t]{ccccc}
 		\hline
-		Benchmark & Equivalence & Direct [s] & VEIN [s] & Status \\
+		Benchmark & Equivalence & Time & Status \\
 		\hline
-		Iris (Stably Active) & Strict & 0.0 & 0.0 & X \\
-		Iris (Stably Active) & Epsilon & 0.0 & 0.0 & X \\
-		Iris (Stably Active) & Argmax & 0.0 & 0.0 & X \\
-		Iris (Stably Inactive) & Strict & 0.0 & 0.0 & X \\
-		Iris (Stably Inactive) & Epsilon & 0.0 & 0.0 & X \\
-		Iris (Stably Inactive) & Argmax & 0.0 & 0.0 & X \\
-		Iris (To Wide) & Strict & 0.0 & 0.0 & X \\
-		Iris (To Wide) & Epsilon & 0.0 & 0.0 & X \\
-		Iris (To Wide) & Argmax & 0.0 & 0.0 & X \\
-		Iris (To Deep) & Strict & 0.0 & 0.0 & X \\
-		Iris (To Deep) & Epsilon & 0.0 & 0.0 & X \\
-		Iris (To Deep) & Argmax & 0.0 & 0.0 & X \\
-		Pendulum & Strict & 0.0 & 88.427 ± 0.670 & SAT \\
-		Pendulum & Epsilon & 0.0 & 0.0 & X \\
-		Pendulum & Argmax & 0.0 & 0.0 & X \\
-		Double Integrator & Strict & 0.0 & 0.0 & X \\
-		Double Integrator & Epsilon & 0.0 & 0.0 & X \\
-		Double Integrator & Argmax & 0.0 & 0.0 & X \\
-		MNIST (Stably Active) & Strict & 0.0 & 0.0 & X \\
-		MNIST (Stably Active) & Epsilon & 0.0 & 0.0 & X \\
-		MNIST (Stably Active) & Argmax & 0.0 & 0.0 & X \\
-		MNIST (Stably Inactive) & Strict & 0.0 & 0.0 & X \\
-		MNIST (Stably Inactive) & Epsilon & 0.0 & 0.0 & X \\
-		MNIST (Stably Inactive) & Argmax & 0.0 & 0.0 & X \\
-		MNIST (To Wide) & Strict & 0.0 & 0.0 & X \\
-		MNIST (To Wide) & Epsilon & 0.0 & 0.0 & X \\
-		MNIST (To Wide) & Argmax & 0.0 & 0.0 & X \\
-		MNIST (To Deep) & Strict & 0.0 & 0.0 & X \\
-		MNIST (To Deep) & Epsilon & 0.0 & 0.0 & X \\
-		MNIST (To Deep) & Argmax & 0.0 & 0.0 & X \\
+		Iris (Stably Active) & Strict & 521.6ms ± 11.5ms & SAT \\
+		Iris (Stably Active) & Epsilon & 515.9ms ± 4.2ms & UNSAT \\
+		Iris (Stably Active) & Argmax & 519.5ms ± 6.0ms & UNSAT \\
+		Iris (Stably Inactive) & Strict & 581.9ms ± 6.2ms & UNSAT \\
+		Iris (Stably Inactive) & Epsilon & 593.8ms ± 6.9ms & UNSAT \\
+		Iris (Stably Inactive) & Argmax & 886.4ms ± 10.3ms & UNSAT \\
+		Iris (To Wide) & Strict & 595.4ms ± 11.3ms & UNSAT \\
+		Iris (To Wide) & Epsilon & 587.0ms ± 4.9ms & UNSAT \\
+		Iris (To Wide) & Argmax & 783.5ms ± 4.4ms & UNSAT \\
+		Iris (To Deep) & Strict & 581.4ms ± 6.6ms & UNSAT \\
+		Iris (To Deep) & Epsilon & 583.1ms ± 5.7ms & UNSAT \\
+		Iris (To Deep) & Argmax & 716.3ms ± 4.7ms & UNSAT \\
+		Pendulum & Strict & 43.276s ± 0.143s & SAT \\
+		Pendulum & Epsilon & 340.293s ± 2.843s & UNSAT \\
+		Pendulum & Argmax & 61.935s ± 0.148s & SAT \\
+		Double Integrator & Strict & 538.952s ± 7.207s & SAT \\
+		Double Integrator & Epsilon & 137.720s ± 0.419s & SAT \\
+		Double Integrator & Argmax & 618.705s ± 6.821s & SAT \\
+		MNIST (Stably Active) & Strict & 18.947s ± 0.034s & SAT \\
+		MNIST (Stably Active) & Epsilon & 18.980s ± 0.032s & UNSAT \\
+		MNIST (Stably Active) & Argmax & 18.906s ± 0.019s & UNSAT \\
+		MNIST (Stably Inactive) & Strict & 14.699s ± 0.024s & UNSAT \\
+		MNIST (Stably Inactive) & Epsilon & 14.702s ± 0.012s & UNSAT \\
+		MNIST (Stably Inactive) & Argmax & TIMEOUT & UNKNOWN \\
+		MNIST (To Wide) & Strict & 20.990s ± 0.181s & UNSAT \\
+		MNIST (To Wide) & Epsilon & 20.860s ± 0.022s & UNSAT \\
+		MNIST (To Wide) & Argmax & TIMEOUT & UNKNOWN \\
+		MNIST (To Deep) & Strict & 20.901s ± 0.027s & UNSAT \\
+		MNIST (To Deep) & Epsilon & 20.947s ± 0.035s & UNSAT \\
+		MNIST (To Deep) & Argmax & TIMEOUT & UNKNOWN \\
 	\end{tabular}
 	\caption{Benchmark table.}
 	\label{tab:benchmarks}
diff --git a/chapters/core/soundness-proof/03-soundness-of-interaction-rules.tex b/chapters/core/soundness-proof/03-soundness-of-interaction-rules.tex
index be0870d..26f7e13 100644
--- a/chapters/core/soundness-proof/03-soundness-of-interaction-rules.tex
+++ b/chapters/core/soundness-proof/03-soundness-of-interaction-rules.tex
@@ -525,7 +525,11 @@
 \begin{lemma}
 	For the \textit{Linear} and \textit{Dup} agents we have the interaction rule:
 	$$
-	\mathit{Linear}(z, q, r) \bowtie \mathit{Dup}(x, y) \Rightarrow \mathit{Linear}(z_1, q, r) \sim x; \mathit{Linear}(z_2, q, r) \sim y; \mathit{Dup}(z_1, z_2) \sim z \\
+	\begin{aligned}
+		\mathit{Linear}(z, q, r) \bowtie \mathit{Dup}(x, y) \Rightarrow
+		& \mathit{Linear}(z_1, q, r) \sim x; \mathit{Linear}(z_2, q, r) \sim y;	\\
+		& \mathit{Dup}(z_1, z_2) \sim z
+	\end{aligned}
 	$$
 	We need to show that the LHS and RHS are semantically equivalent:
 	$$
@@ -667,8 +671,9 @@
 	For the \textit{TermMul} and \textit{Dup} agents we have the interaction rule:
 	$$
 	\begin{aligned}
-		\mathit{TermMul}(a, b) \bowtie \mathit{Dup}(x, y) \Rightarrow & \mathit{TermMul}(a_1, b_1) \sim x; \mathit{TermMul}(a_2, b_2) \sim y; \\
-		& \mathit{Dup}(a_1, a_2) \sim a; \mathit{Dup}(b_1, b_2) \sim b\\
+		\mathit{TermMul}(a, b) \bowtie \mathit{Dup}(x, y) \Rightarrow
+		& \mathit{TermMul}(a_1, b_1) \sim x; \mathit{TermMul}(a_2, b_2) \sim y; \\
+		& \mathit{Dup}(a_1, a_2) \sim a; \mathit{Dup}(b_1, b_2) \sim b
 	\end{aligned}
 	$$
 	We need to show that the LHS and RHS are semantically equivalent:
@@ -717,7 +722,12 @@
 \begin{lemma}
 	For the \textit{TermReLU} and \textit{Dup} agents we have the interaction rule:
 	$$
-	\mathit{TermReLU}(z) \bowtie \mathit{Dup}(x, y) \Rightarrow \mathit{TermReLU}(z_1) \sim x; \mathit{TermReLU}(z_2) \sim y; \mathit{Dup}(z_1, z_2) \sim z \\
+	\begin{aligned}
+		\mathit{TermReLU}(z) \bowtie \mathit{Dup}(x, y) \Rightarrow
+		& \mathit{TermReLU}(z_1) \sim x; \\
+		&\mathit{TermReLU}(z_2) \sim y; \\
+		& \mathit{Dup}(z_1, z_2) \sim z
+	\end{aligned}
 	$$
 	We need to show that the LHS and RHS are semantically equivalent:
 	$$
@@ -763,7 +773,11 @@
 \begin{lemma}
 	For the \textit{TermConcrete} and \textit{Dup} agents we have the interaction rule:
 	$$
-	\mathit{TermConcrete}(k) \bowtie \mathit{Dup}(x, y) \Rightarrow \mathit{TermConcrete}(k) \sim x; \mathit{TermConcrete}(k) \sim y \\
+	\begin{aligned}
+		\mathit{TermConcrete}(k) \bowtie \mathit{Dup}(x, y) \Rightarrow
+		& \mathit{TermConcrete}(k) \sim x; \\
+		& \mathit{TermConcrete}(k) \sim y
+	\end{aligned}
 	$$
 	We need to show that the LHS and RHS are semantically equivalent:
 	$$
@@ -807,7 +821,11 @@
 \begin{lemma}
 	For the \textit{TermSymbolic} and \textit{Dup} agents we have the interaction rule:
 	$$
-	\mathit{TermSymbolic}(id) \bowtie \mathit{Dup}(x, y) \Rightarrow \mathit{TermSymbolic}(id) \sim x; \mathit{TermSymbolic}(id) \sim y \\
+	\begin{aligned}
+		\mathit{TermSymbolic}(id) \bowtie \mathit{Dup}(x, y) \Rightarrow
+		& \mathit{TermSymbolic}(id) \sim x; \\
+		& \mathit{TermSymbolic}(id) \sim y
+	\end{aligned}
 	$$
 	We need to show that the LHS and RHS are semantically equivalent:
 	$$
diff --git a/references.bib b/references.bib
index 303b83f..e3a73fc 100644
--- a/references.bib
+++ b/references.bib
@@ -150,4 +150,80 @@
 	journal={Department of Computer Science, The University of Iowa, Tech. Rep},
 	year={2016}
 }
-
+@misc{wang2018efficientformalsafetyanalysis,
+      title={Efficient Formal Safety Analysis of Neural Networks}, 
+      author={Shiqi Wang and Kexin Pei and Justin Whitehouse and Junfeng Yang and Suman Jana},
+      year={2018},
+      eprint={1809.08098},
+      archivePrefix={arXiv},
+      primaryClass={cs.LG},
+      url={https://arxiv.org/abs/1809.08098}, 
+}
+@incollection{dantzig1947simplex,
+  abstract = {In 1947, George Dantzig created a simplex algorithm to solve linear programs for planning and decision-making in large-scale enterprises. The algorithm's success led to a vast array of specializations and generalizations that have dominated practical operations research for half a century},
+  added-at = {2010-02-26T23:23:28.000+0100},
+  address = {Piscataway, NJ, USA},
+  author = {Nash, John C.},
+  biburl = {https://www.bibsonomy.org/bibtex/2b85e2108e8f7cc402a52577323035ad9/ytyoun},
+  booktitle = {Computing in Science and Engg.},
+  doi = {10.1109/5992.814654},
+  interhash = {5fb3b9e4a0e81f7811c917b86d1097cb},
+  intrahash = {b85e2108e8f7cc402a52577323035ad9},
+  issn = {1521-9615},
+  keywords = {algorithm magazine matrix simplex top.ten.algorithms},
+  number = 1,
+  pages = {29--31},
+  publisher = {IEEE Educational Activities Department},
+  timestamp = {2015-12-13T09:44:24.000+0100},
+  title = {The (Dantzig) Simplex Method for Linear Programming},
+  volume = 2,
+  year = 2000
+}
+@article{zhang2018efficient,
+  title={Efficient Neural Network Robustness Certification with General Activation Functions},
+  author={Zhang, Huan and Weng, Tsui-Wei and Chen, Pin-Yu and Hsieh, Cho-Jui and Daniel, Luca},
+  journal={Advances in Neural Information Processing Systems},
+  volume={31},
+  pages={4939--4948},
+  year={2018},
+  url={https://arxiv.org/pdf/1811.00866.pdf}
+}
+@article{xu2020automatic,
+  title={Automatic perturbation analysis for scalable certified robustness and beyond},
+  author={Xu, Kaidi and Shi, Zhouxing and Zhang, Huan and Wang, Yihan and Chang, Kai-Wei and Huang, Minlie and Kailkhura, Bhavya and Lin, Xue and Hsieh, Cho-Jui},
+  journal={Advances in Neural Information Processing Systems},
+  volume={33},
+  year={2020}
+}
+@inproceedings{xu2021fast,
+    title={{Fast and Complete}: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers},
+    author={Kaidi Xu and Huan Zhang and Shiqi Wang and Yihan Wang and Suman Jana and Xue Lin and Cho-Jui Hsieh},
+    booktitle={International Conference on Learning Representations},
+    year={2021},
+    url={https://openreview.net/forum?id=nVZtXBI6LNn}
+}
+@article{wang2021beta,
+  title={{Beta-CROWN}: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification},
+  author={Wang, Shiqi and Zhang, Huan and Xu, Kaidi and Lin, Xue and Jana, Suman and Hsieh, Cho-Jui and Kolter, J Zico},
+  journal={Advances in Neural Information Processing Systems},
+  volume={34},
+  year={2021}
+}
+@inproceedings{shi2024genbab,
+  title={Neural Network Verification with Branch-and-Bound for General Nonlinearities},
+  author={Shi, Zhouxing and Jin, Qirui and Kolter, Zico and Jana, Suman and Hsieh, Cho-Jui and Zhang, Huan},
+  booktitle={International Conference on Tools and Algorithms for the Construction and Analysis of Systems},
+  year={2025}
+}
+@article{zhang2022general,
+  title={General Cutting Planes for Bound-Propagation-Based Neural Network Verification},
+  author={Zhang, Huan and Wang, Shiqi and Xu, Kaidi and Li, Linyi and Li, Bo and Jana, Suman and Hsieh, Cho-Jui and Kolter, J Zico},
+  journal={Advances in Neural Information Processing Systems},
+  year={2022}
+}
+@inproceedings{zhou2024scalable,
+  title={Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes},
+  author={Zhou, Duo and Brix, Christopher and Hanasusanto, Grani A and Zhang, Huan},
+  booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
+  year={2024}
+}