smt-based verification

**SMT-Based Verification** (Satisfiability Modulo Theories) is the **application of SMT solvers to verify properties of neural networks** — encoding the network as a set of logical constraints and using automated theorem provers to check whether any input within a specified region can violate a desired property. **How SMT Verification Works** - **Encoding**: Each neuron is encoded as a set of linear arithmetic constraints (weights, biases, activations). - **ReLU Encoding**: $y = ReLU(x)$ encoded as: $y geq 0$, $y geq x$, and $(y = 0 lor y = x)$. - **Property**: The negation of the desired property is added as a constraint. - **Solver**: If the SMT solver finds the problem UNSAT (unsatisfiable), the property is verified. **Why It Matters** - **Exact**: SMT verification provides exact (complete) answers — no over-approximation looseness. - **Reluplex**: The Reluplex algorithm (Katz et al., 2017) extends DPLL(T) for ReLU networks. - **Scalability**: Limited to small-to-medium networks (hundreds to low thousands of neurons) due to computational cost. **SMT Verification** is **theorem proving for neural networks** — using logical solvers to formally prove or disprove safety properties.