Skip to content

Latest commit

 

History

History
77 lines (50 loc) · 3.69 KB

README.md

File metadata and controls

77 lines (50 loc) · 3.69 KB
Raw

GeoCert

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
example mnist_reconstr

News

  • 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

Primary Contents

Functions:

  • 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.

Examples:

  • 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.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Dependencies

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 $\ell_\infty$ case) or LCQP solvers (in the $\ell_2$) case. We use the Gurobi Optimizer for this. Visit their homepage to acquire a free academic license.

Installing

  1. Clone the repository: 
    $ git clone https://github.com/revbucket/geometric-certificates
$ cd geometric-certificates
  2. Install requirements: 
    $ pip install -r requirements.txt

Running the tests

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

Authors

  • Matt Jordan- University of Texas at Austin
  • Justin Lewis- University of Texas at Austin

License

This project is licensed under the MIT License - see the LICENSE.md file for details