Geometric-inspired algorithm for solving the general problem of finding the largest l_p ball centered at a point x for a union of polytopes which form a polyhedral complex. This algorithm is provably correct for p equal or larger than 1. Primary application found in certifying the adversarial robustness of multilayer ReLu networks. Created by Matt Jordan and Justin Lewis.
Check out our paper on arXiv: Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes.
Some example results:
| Maximal l_2 projections | Network Input Partioning |
|---|---|
 |
 |
- 09/13/2019: Version 0.2 refactor deployed
- 09/03/2019: Accepted (poster) to NeurIPS 2019
- 06/11/2019: Contributed Talk at ICML Workshop on Security and Privacy of Machine Learning
- 03/20/2019: ArXiv Release and Version 0.1 deployed
- Computing the minimal distance adversarial example under L2 and L∞ norms. That is, given a classifier f and an input x, GeoCert computes the δ with minimal Lp norm such that f(x) ≠ f(x+δ).
- Answering the decision problem of robustness. Given a classifier f, an input x and a radius ε, answer the decision problem: "Does there exist a point y with ||y-x||p ≤ ε such that f(y)≠ f(x)?"
- Recalling that ReLU neural networks are piecewise linear, GeoCert can be leveraged to exactly count the number of linear regions intersecting a specified Lp ball.
- 2D_example.ipynb: Basic example using a binary classifier on 2-dimensional inputs to demonstrate the primary functionalities of GeoCert
- MNIST_example.ipynb: More fleshed-out example, where the classifier is trained to distinguish between 1's and 7's from the MNIST Dataset.
These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.
Requisite python packages are contained within the file requirements.txt. The mister_ed adversarial example toolbox is used to compute upper bounds. This is maintained as a subrepository within this one.
GeoCert makes many many calls to linear program solvers (in the
- Clone the repository:
$ git clone https://github.com/revbucket/geometric-certificates $ cd geometric-certificates - Install requirements:
$ pip install -r requirements.txt
With the codebase installed, run the ipython notebooks provided to get your hands on the algorithm and visualize its behaviour. As an example:
$ cd examples
$ jupyter notebook 2D_example.ipynb- Matt Jordan- University of Texas at Austin
- Justin Lewis- University of Texas at Austin
This project is licensed under the MIT License - see the LICENSE.md file for details