2021

Provable Repair of Deep Neural Networks

Sotoudeh, Matthew, Thakur, Aditya V.

Understand

Deep Neural Networks (DNNs) have grown in popularity over the past decade and are now being used in safety-critical domains such as aircraft collision avoidance.

This has motivated a large number of techniques for finding unsafe behavior in DNNs.
In contrast, this paper tackles the problem of correcting a DNN once unsafe behavior is found.
We introduce the provable repair problem, which is the problem of repairing a network N to construct a new network N' that satisfies a given specification.

Built on

Decoupling Gating from Linearity
Original
Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz. 2019 · 1906
Earlier work this paper cites.
MNIST-C: A Robustness Benchmark for Computer Vision
Original
Norman Mu and Justin Gilmer. 2019 · 1906
Earlier work this paper cites.
Natural Adversarial Examples
Original
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. 2019 · 1907
Earlier work this paper cites.
Advanced calculus
Lynn Harold Loomis and Shlomo Sternberg. 1968 · 1968
Earlier work this paper cites.
Quadratic programming with quadratic constraints
David P Baron. 1972 · 1972
Earlier work this paper cites.
A polynomial algorithm in linear programming. In Doklady Akademii Nauk , Vol. 244. Russian Academy of Sciences
Leonid Genrikhovich Khachiyan. 1979 · 1979
Earlier work this paper cites.
Concrete Mathematics: A Foundation for Computer Science, 2nd Ed
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994 · 1994
Earlier work this paper cites.
Z3: An Efficient SMT Solver. In 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)
Leonardo Mendonça de Moura and Nikolaj Bjørner. 2008 · 2008
Earlier work this paper cites.
ImageNet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. 2009 · 2009
Earlier work this paper cites.
MNIST handwritten digit database
Yann LeCun, Corinna Cortes, and CJ Burges. 2010 · 2010
Earlier work this paper cites.
Optimization with absolute values
Kathleen Zhou Benjamin Granger, Marta Yu. 2014 · 2014
Earlier work this paper cites.
Intriguing properties of neural networks. In 2nd International Conference on Learning Representations (ICLR)
Original
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014 · 2014
Earlier work this paper cites.
Explaining and Harnessing Adversarial Examples. In 3rd International Conference on Learning Representations (ICLR)
Original
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015 · 2015
Earlier work this paper cites.
TensorFlow: A System for Large-Scale Machine Learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI)
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2016 · 2016
Earlier work this paper cites.
Measuring Neural Net Robustness with Constraints. In Advances in Neural Information Processing Systems 29 (NeurIPS)
Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya V. Nori, and Antonio Criminisi. 2016 · 2016
Earlier work this paper cites.
Reliable and Reproducible Competition Results with BenchExec and Witnesses (Report on SV-COMP 2016). In 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)
Dirk Beyer. 2016 · 2016
Earlier work this paper cites.
End to End Learning for Self-Driving Cars
Original
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba. 2016 · 2016
Earlier work this paper cites.
Deep Learning
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016 · 2016
Earlier work this paper cites.
SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <1MB model size
Original
Forrest N. Iandola, Matthew W. Moskewicz, Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. 2016 · 2016
Earlier work this paper cites.
Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks. In 15th International Symposium on Automated Technology for Verification and Analysis (ATVA)
Rüdiger Ehlers. 2017 · 2017
Earlier work this paper cites.

Similar

Safety Verification of Deep Neural Networks. In 29th International Conference on Computer Aided Verification (CAV)
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. 2017 · 2017
Cited alongside, same era.
Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In 29th International Conference on Computer Aided Verification (CAV)
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. 2017 · 2017
Cited alongside, same era.
ImageNet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017 · 2017
Cited alongside, same era.
Automatic differentiation in PyTorch
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017 · 2017
Cited alongside, same era.
DeepXplore: Automated Whitebox Testing of Deep Learning Systems. In 26th Symposium on Operating Systems Principles (SOSP)
Kexin Pei, Yinzhi Cao, Junfeng Yang, and Suman Jana. 2017 · 2017
Cited alongside, same era.
Safe Reinforcement Learning via Shielding. In Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)
Mohammed Alshiekh, Roderick Bloem, Rüdiger Ehlers, Bettina Könighofer, Scott Niekum, and Ufuk Topcu. 2018 · 2018
Cited alongside, same era.
Verifiable Reinforcement Learning via Policy Extraction. In Advances in Neural Information Processing Systems 31 (NeurIPS)
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. 2018 · 2018
Cited alongside, same era.
A Unified View of Piecewise Linear Neural Network Verification. In Advances in Neural Information Processing Systems 31 (NeurIPS)
Rudy Bunel, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. 2018 · 2018
Cited alongside, same era.
AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation. In 2018 IEEE Symposium on Security and Privacy (SP)
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. 2018 · 2018
Cited alongside, same era.
Deep Neural Network Compression for Aircraft Collision Avoidance Systems
Original
Kyle D. Julian, Mykel J. Kochenderfer, and Michael P. Owen. 2018 · 2018
Cited alongside, same era.
Measuring Catastrophic Forgetting in Neural Networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)
Ronald Kemker, Marc McClure, Angelina Abitino, Tyler L. Hayes, and Christopher Kanan. 2018 · 2018
Cited alongside, same era.
Identifying Medical Diagnoses and Treatable Diseases by Image-Based Deep Learning
Daniel S. Kermany, Michael Goldbaum, Wenjia Cai, Carolina C.S. Valentim, Huiying Liang, Sally L. Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, Justin Dong, Made K. Prasadha, Jacqueline Pei, Magdalene Y.L. Ting, Jie Zhu, Christina Li, Sierra Hewett, Jason Dong, Ian Ziyar, Alexander Shi, Runze Zhang, Lianghong Zheng, Rui Hou, William Shi, Xin Fu, Yaou Duan, Viet A.N. Huu, Cindy Wen, Edward D. Zhang, Charlotte L. Zhang, Oulan Li, Xiaobo Wang, Michael A. Singer, Xiaodong Sun, Jie Xu, Ali Tafreshi, M. Anthony Lewis, Huimin Xia, and Kang Zhang. 2018 · 2018
Cited alongside, same era.

Then

Symbolic Execution for Importance Analysis and Adversarial Generation in Neural Networks. In 30th IEEE International Symposium on Software Reliability Engineering, (ISSRE)
Divya Gopinath, Mengshi Zhang, Kaiyuan Wang, Ismet Burak Kadron, Corina S. Pasareanu, and Sarfraz Khurshid. 2019 · 2019
Later among the works it cites.
Deep ReLU Networks Have Surprisingly Few Activation Patterns. In Advances in Neural Information Processing Systems 32 (NeurIPS)
Boris Hanin and David Rolnick. 2019b · 2019
Later among the works it cites.
The Marabou Framework for Verification and Analysis of Deep Neural Networks. In 31st International Conference on Computer Aided Verification (CAV)
Guy Katz, Derek A. Huang, Duligur Ibeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljic, David L. Dill, Mykel J. Kochenderfer, and Clark W. Barrett. 2019 · 2019
Later among the works it cites.
Patching Deep Neural Networks for Nonstationary Environments. In International Joint Conference on Neural Networks (IJCNN)
Sebastian Kauschke, David Hermann Lehmann, and Johannes Fürnkranz. 2019 · 2019
Later among the works it cites.
TensorFuzz: Debugging Neural Networks with Coverage-Guided Fuzzing. In 36th International Conference on Machine Learning (ICML)
Augustus Odena, Catherine Olsson, David G. Andersen, and Ian J. Goodfellow. 2019 · 2019
Later among the works it cites.
PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32 (NeurIPS)
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019 · 2019
Later among the works it cites.
ETH Robustness Analyzer for Neural Networks (ERAN)
Gagandeep Singh. 2019 · 2019
Later among the works it cites.
An abstract domain for certifying neural networks
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. 2019 · 2019
Later among the works it cites.
Computing Linear Restrictions of Neural Networks. In Advances in Neural Information Processing Systems 32 (NeurIPS)
Matthew Sotoudeh and Aditya V. Thakur. 2019 · 2019
Later among the works it cites.
DeepHunter: a coverage-guided fuzz testing framework for deep neural networks. In 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA)
Xiaofei Xie, Lei Ma, Felix Juefei-Xu, Minhui Xue, Hongxu Chen, Yang Liu, Jianjun Zhao, Bo Li, Jianxiong Yin, and Simon See. 2019 · 2019
Later among the works it cites.
An inductive synthesis framework for verifiable reinforcement learning. In 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. 2019 · 2019
Later among the works it cites.
Minimal Modifications of Deep Neural Networks using Verification. In 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR) , Vol. 73
Ben Goldberger, Guy Katz, Yossi Adi, and Joseph Keshet. 2020 · 2020
Later among the works it cites.
Feds Say Self-Driving Uber SUV Did Not Recognize Jaywalking Pedestrian In Fatal Crash
Richard Gonzales. 2019 · 2020
Later among the works it cites.
Gurobi Optimizer Reference Manual
LLC Gurobi Optimization. 2020 · 2020
Later among the works it cites.
Facebook translates ’good morning’ into ’attack them’, leading to arrest
Alex Hern. 2017 · 2020
Later among the works it cites.
Wrongfully Accused by an Algorithm
Kashmir Hill. 2020 · 2020
Later among the works it cites.
US opens investigation into Tesla after fatal crash
Dave Lee. 2016 · 2020
Later among the works it cites.
Editable Neural Networks. In 8th International Conference on Learning Representations (ICLR)
Anton Sinitsin, Vsevolod Plokhotnyuk, Dmitriy Pyrkin, Sergei Popov, and Artem Babenko. 2020 · 2020
Later among the works it cites.
SyReNN: A Tool for Analyzing Deep Neural Networks. In 27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS)
Matthew Sotoudeh and Aditya V. Thakur. 2021 · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…