Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3453483.3454064acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
research-article
Open access

Provable repair of deep neural networks

Published: 18 June 2021 Publication History

Abstract

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. If the safety specification is over a finite set of points, our Provable Point Repair algorithm can find a provably minimal repair satisfying the specification, regardless of the activation functions used. For safety specifications addressing convex polytopes containing infinitely many points, our Provable Polytope Repair algorithm can find a provably minimal repair satisfying the specification for DNNs using piecewise-linear activation functions. The key insight behind both of these algorithms is the introduction of a Decoupled DNN architecture, which allows us to reduce provable repair to a linear programming problem. Our experimental results demonstrate the efficiency and effectiveness of our Provable Repair algorithms on a variety of challenging tasks.

References

[1]
2019. A collection of pre-trained, state-of-the-art models in the ONNX format. https://github.com/onnx/models Accessed: 2019-05-01.
[2]
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. TensorFlow: A System for Large-Scale Machine Learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI). https://www.usenix.org/conference/osdi16/technical-sessions/presentation/abadi
[3]
Mohammed Alshiekh, Roderick Bloem, Rüdiger Ehlers, Bettina Könighofer, Scott Niekum, and Ufuk Topcu. 2018. Safe Reinforcement Learning via Shielding. In Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17211
[4]
Greg Anderson, Shankara Pailoor, Isil Dillig, and Swarat Chaudhuri. 2019. Optimization and abstraction: a synergistic approach for analyzing neural network robustness. In 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). https://doi.org/10.1145/3314221.3314614
[5]
David P Baron. 1972. Quadratic programming with quadratic constraints. Naval Research Logistics Quarterly, 19, 2 (1972).
[6]
Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya V. Nori, and Antonio Criminisi. 2016. Measuring Neural Net Robustness with Constraints. In Advances in Neural Information Processing Systems 29 (NeurIPS). https://proceedings.neurips.cc/paper/2016/hash/980ecd059122ce2e50136bda65c25e07-Abstract.html
[7]
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. 2018. Verifiable Reinforcement Learning via Policy Extraction. In Advances in Neural Information Processing Systems 31 (NeurIPS). https://proceedings.neurips.cc/paper/2018/hash/e6d8545daa42d5ced125a4bf747b3688-Abstract.html
[8]
Kathleen Zhou Benjamin Granger, Marta Yu. 2014. Optimization with absolute values. https://optimization.mccormick.northwestern.edu/index.php/Optimization_with_absolute_values
[9]
Dirk Beyer. 2016. 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). https://doi.org/10.1007/978-3-662-49674-9_55
[10]
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. End to End Learning for Self-Driving Cars. arxiv:1604.07316. arxiv:1604.07316
[11]
Rudy Bunel, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and Pawan Kumar Mudigonda. 2018. A Unified View of Piecewise Linear Neural Network Verification. In Advances in Neural Information Processing Systems 31 (NeurIPS). https://proceedings.neurips.cc/paper/2018/hash/be53d253d6bc3258a8160556dda3e9b2-Abstract.html
[12]
Leonardo Mendonça de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). https://doi.org/10.1007/978-3-540-78800-3_24
[13]
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. 2009. ImageNet: A large-scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). https://doi.org/10.1109/CVPR.2009.5206848
[14]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT). https://doi.org/10.18653/v1/n19-1423
[15]
Rüdiger Ehlers. 2017. Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks. In 15th International Symposium on Automated Technology for Verification and Analysis (ATVA). https://doi.org/10.1007/978-3-319-68167-2_19
[16]
Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz. 2019. Decoupling Gating from Linearity. arxiv:1906.05032. arxiv:1906.05032
[17]
Marc Fischer, Mislav Balunovic, Dana Drachsler-Cohen, Timon Gehr, Ce Zhang, and Martin T. Vechev. 2019. DL2: Training and Querying Neural Networks with Logic. In 36th International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research, Vol. 97). http://proceedings.mlr.press/v97/fischer19a.html
[18]
Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin T. Vechev. 2018. AI2: Safety and Robustness Certification of Neural Networks with Abstract Interpretation. In 2018 IEEE Symposium on Security and Privacy (SP). https://doi.org/10.1109/SP.2018.00058
[19]
Ben Goldberger, Guy Katz, Yossi Adi, and Joseph Keshet. 2020. Minimal Modifications of Deep Neural Networks using Verification. In 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR). 73, https://easychair.org/publications/paper/CWhF
[20]
Richard Gonzales. 2019. Feds Say Self-Driving Uber SUV Did Not Recognize Jaywalking Pedestrian In Fatal Crash. NPR. https://www.npr.org/2019/11/07/777438412/feds-say-self-driving-uber-suv-did-not-recognize-jaywalking-pedestrian-in-fatal- Accessed: 2020-06-06.
[21]
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press. http://www.deeplearningbook.org
[22]
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2015. Explaining and Harnessing Adversarial Examples. In 3rd International Conference on Learning Representations (ICLR). arxiv:1412.6572
[23]
Divya Gopinath, Mengshi Zhang, Kaiyuan Wang, Ismet Burak Kadron, Corina S. Pasareanu, and Sarfraz Khurshid. 2019. Symbolic Execution for Importance Analysis and Adversarial Generation in Neural Networks. In 30th IEEE International Symposium on Software Reliability Engineering, (ISSRE). https://doi.org/10.1109/ISSRE.2019.00039
[24]
LLC Gurobi Optimization. 2020. Gurobi Optimizer Reference Manual. http://www.gurobi.com
[25]
Boris Hanin and David Rolnick. 2019. Complexity of Linear Regions in Deep Networks. In 36th International Conference on Machine Learning (ICML) (Proceedings of Machine Learning Research, Vol. 97). http://proceedings.mlr.press/v97/hanin19a.html
[26]
Boris Hanin and David Rolnick. 2019. Deep ReLU Networks Have Surprisingly Few Activation Patterns. In Advances in Neural Information Processing Systems 32 (NeurIPS). https://proceedings.neurips.cc/paper/2019/hash/9766527f2b5d3e95d4a733fcfb77bd7e-Abstract.html
[27]
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. 2019. Natural Adversarial Examples. arxiv:1907.07174. arxiv:1907.07174
[28]
Alex Hern. 2017. Facebook translates ’good morning’ into ’attack them’, leading to arrest. https://www.theguardian.com/technology/2017/oct/24/facebook-palestine-israel-translates-good-morning-attack-them-arrest Accessed: 2020-06-06.
[29]
Kashmir Hill. 2020. Wrongfully Accused by an Algorithm. New York Times. https://www.nytimes.com/2020/06/24/technology/facial-recognition-arrest.html Accessed: 2020-06-06.
[30]
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. 2017. Safety Verification of Deep Neural Networks. In 29th International Conference on Computer Aided Verification (CAV). https://doi.org/10.1007/978-3-319-63387-9_1
[31]
Forrest N. Iandola, Matthew W. Moskewicz, Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. 2016. SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and < 1MB model size. arxiv:1602.07360. arxiv:1602.07360
[32]
Kyle D. Julian, Mykel J. Kochenderfer, and Michael P. Owen. 2018. Deep Neural Network Compression for Aircraft Collision Avoidance Systems. arxiv:1810.04240. arxiv:1810.04240
[33]
Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. 2017. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In 29th International Conference on Computer Aided Verification (CAV). https://doi.org/10.1007/978-3-319-63387-9_5
[34]
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. The Marabou Framework for Verification and Analysis of Deep Neural Networks. In 31st International Conference on Computer Aided Verification (CAV). https://doi.org/10.1007/978-3-030-25540-4_26
[35]
Sebastian Kauschke, David Hermann Lehmann, and Johannes Fürnkranz. 2019. Patching Deep Neural Networks for Nonstationary Environments. In International Joint Conference on Neural Networks (IJCNN). https://doi.org/10.1109/IJCNN.2019.8852222
[36]
Ronald Kemker, Marc McClure, Angelina Abitino, Tyler L. Hayes, and Christopher Kanan. 2018. Measuring Catastrophic Forgetting in Neural Networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16410
[37]
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. Identifying Medical Diagnoses and Treatable Diseases by Image-Based Deep Learning. Cell, 172, 5 (2018), issn:0092-8674 https://doi.org/10.1016/j.cell.2018.02.010
[38]
Leonid Genrikhovich Khachiyan. 1979. A polynomial algorithm in linear programming. In Doklady Akademii Nauk. 244.
[39]
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017. ImageNet classification with deep convolutional neural networks. Commun. ACM, 60, 6 (2017), https://doi.org/10.1145/3065386
[40]
Yann LeCun, Corinna Cortes, and CJ Burges. 2010. MNIST handwritten digit database. http://yann.lecun.com/exdb/mnist
[41]
Dave Lee. 2016. US opens investigation into Tesla after fatal crash. BBC. https://www.bbc.co.uk/news/technology-36680043 Accessed: 2020-06-06.
[42]
Lei Ma, Felix Juefei-Xu, Fuyuan Zhang, Jiyuan Sun, Minhui Xue, Bo Li, Chunyang Chen, Ting Su, Li Li, Yang Liu, Jianjun Zhao, and Yadong Wang. 2018. DeepGauge: multi-granularity testing criteria for deep learning systems. In 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE). https://doi.org/10.1145/3238147.3238202
[43]
Lei Ma, Fuyuan Zhang, Jiyuan Sun, Minhui Xue, Bo Li, Felix Juefei-Xu, Chao Xie, Li Li, Yang Liu, Jianjun Zhao, and Yadong Wang. 2018. DeepMutation: Mutation Testing of Deep Learning Systems. In 29th IEEE International Symposium on Software Reliability Engineering (ISSRE). https://doi.org/10.1109/ISSRE.2018.00021
[44]
Norman Mu and Justin Gilmer. 2019. MNIST-C: A Robustness Benchmark for Computer Vision. arxiv:1906.02337. arxiv:1906.02337
[45]
Augustus Odena, Catherine Olsson, David G. Andersen, and Ian J. Goodfellow. 2019. TensorFuzz: Debugging Neural Networks with Coverage-Guided Fuzzing. In 36th International Conference on Machine Learning (ICML). http://proceedings.mlr.press/v97/odena19a.html
[46]
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. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32 (NeurIPS). https://proceedings.neurips.cc/paper/2019/hash/bdbca288fee7f92f2bfa9f7012727740-Abstract.html
[47]
Kexin Pei, Yinzhi Cao, Junfeng Yang, and Suman Jana. 2017. DeepXplore: Automated Whitebox Testing of Deep Learning Systems. In 26th Symposium on Operating Systems Principles (SOSP). https://doi.org/10.1145/3132747.3132785
[48]
Gagandeep Singh. 2019. ETH Robustness Analyzer for Neural Networks (ERAN). https://github.com/eth-sri/eran Accessed: 2019-05-01.
[49]
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev. 2019. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3, POPL (2019), https://doi.org/10.1145/3290354
[50]
Anton Sinitsin, Vsevolod Plokhotnyuk, Dmitriy Pyrkin, Sergei Popov, and Artem Babenko. 2020. Editable Neural Networks. In 8th International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=HJedXaEtvS
[51]
Matthew Sotoudeh and Aditya V. Thakur. 2019. Computing Linear Restrictions of Neural Networks. In Advances in Neural Information Processing Systems 32 (NeurIPS). https://proceedings.neurips.cc/paper/2019/hash/908075ea2c025c335f4865f7db427062-Abstract.html
[52]
Matthew Sotoudeh and Aditya V. Thakur. 2021. Provable Repair of Deep Neural Networks. arxiv:2104.04413.
[53]
Matthew Sotoudeh and Aditya V. Thakur. 2021. SyReNN: A Tool for Analyzing Deep Neural Networks. In 27th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). https://doi.org/10.1007/978-3-030-72013-1_15
[54]
Youcheng Sun, Min Wu, Wenjie Ruan, Xiaowei Huang, Marta Kwiatkowska, and Daniel Kroening. 2018. Concolic testing for deep neural networks. In 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE). https://doi.org/10.1145/3238147.3238172
[55]
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. 2014. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations (ICLR). arxiv:1312.6199
[56]
Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. 2018. DeepTest: automated testing of deep-neural-network-driven autonomous cars. In 40th International Conference on Software Engineering (ICSE). https://doi.org/10.1145/3180155.3180220
[57]
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, and Patrick D. McDaniel. 2018. Ensemble Adversarial Training: Attacks and Defenses. In 6th International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=rkZvSe-RZ
[58]
Xiaofei Xie, Lei Ma, Felix Juefei-Xu, Minhui Xue, Hongxu Chen, Yang Liu, Jianjun Zhao, Bo Li, Jianxiong Yin, and Simon See. 2019. DeepHunter: a coverage-guided fuzz testing framework for deep neural networks. In 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA). https://doi.org/10.1145/3293882.3330579
[59]
He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan. 2019. An inductive synthesis framework for verifiable reinforcement learning. In 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). https://doi.org/10.1145/3314221.3314638

Cited By

View all
  • (2025)PRG4CNN: A Probabilistic Model Checking-Driven Robustness Guarantee Framework for CNNsEntropy10.3390/e2702016327:2(163)Online publication date: 3-Feb-2025
  • (2025)BIRDNN: Behavior-Imitation Based Repair for Deep Neural NetworksNeural Networks10.1016/j.neunet.2024.106949183(106949)Online publication date: Mar-2025
  • (2025)Accelerating constraint-based neural network repairs by example prioritization and selectionFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-024-3902-x19:4Online publication date: 1-Apr-2025
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
June 2021
1341 pages
ISBN:9781450383912
DOI:10.1145/3453483
This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. Bug fixing
  2. Deep Neural Networks
  3. Repair

Qualifiers

  • Research-article

Funding Sources

Conference

PLDI '21
Sponsor:

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)971
  • Downloads (Last 6 weeks)36
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)PRG4CNN: A Probabilistic Model Checking-Driven Robustness Guarantee Framework for CNNsEntropy10.3390/e2702016327:2(163)Online publication date: 3-Feb-2025
  • (2025)BIRDNN: Behavior-Imitation Based Repair for Deep Neural NetworksNeural Networks10.1016/j.neunet.2024.106949183(106949)Online publication date: Mar-2025
  • (2025)Accelerating constraint-based neural network repairs by example prioritization and selectionFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-024-3902-x19:4Online publication date: 1-Apr-2025
  • (2024)GNNs also deserve editing, and they need it more than onceProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3694623(61727-61746)Online publication date: 21-Jul-2024
  • (2024)AutoRIC: Automated Neural Network Repairing Based on Constrained OptimizationACM Transactions on Software Engineering and Methodology10.1145/369063434:2(1-29)Online publication date: 4-Sep-2024
  • (2024)Context-Aware Fuzzing for Robustness Enhancement of Deep Learning ModelsACM Transactions on Software Engineering and Methodology10.1145/368046434:1(1-68)Online publication date: 24-Jul-2024
  • (2024)Keeper: Automated Testing and Fixing of Machine Learning SoftwareACM Transactions on Software Engineering and Methodology10.1145/367245133:7(1-33)Online publication date: 13-Jun-2024
  • (2024)MetaRepair: Learning to Repair Deep Neural Networks from Repairing ExperiencesProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3680638(1781-1790)Online publication date: 28-Oct-2024
  • (2024)Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate RepresentationProceedings of the ACM on Programming Languages10.1145/36564278:PLDI(1239-1263)Online publication date: 20-Jun-2024
  • (2024)Interpretability Based Neural Network RepairProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680330(908-919)Online publication date: 11-Sep-2024
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media