We believe that this work represents a first step in applying formal analysis and verifi-cation techniques to machine learning based on support vector machines. We envisage a number of challenging research topics as subject for future work. Generating adver-sarial examples to machine learning methods is important for designing more robust classifiers [11,41,45] and we think that the completeness of robustness verification of linear binary classifiers (cf. Section3) could be exploited for automatically detecting adversarial examples in linear multiclass SVM classifiers. The main challenge here is to design more precise, ideally complete, techniques for abstracting multi-classification based on binary classification. Adversarial SVM training is a further stimulating re-search challenge. Mirman et al. [23] put forward an abstraction-based technique for adversarial training of robust neural networks. A similar approach could also work for SVMs, namely applying abstract interpretation to SVM training models rather than to SVM classifiers.
Acknowledgements. We are grateful to the anonymous referees for their helpful re-marks. The doctoral fellowship of Marco Zanella is funded by Fondazione Bruno Kes-sler (FBK), Trento, Italy. This work has been partially funded by the University of Padova, under the SID2018 project “Analysis of STatic Analyses (ASTA)” and by the Italian Ministry of Research MIUR, under the PRIN2017 project no. 201784YSZ5
“AnalysiS of PRogram Analyses (ASPRA)”.
References
1. G. Anderson, S. Pailoor, I. Dillig, and S. Chaudhuri. Optimization and abstraction: A syn-ergistic approach for analyzing neural network robustness. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI2019), pages 731–744. ACM, 2019.
2. B. Biggio, I. Corona, B. Nelson, B. I. P. Rubinstein, D. Maiorca, G. Fumera, G. Giacinto, and F. Roli. Security evaluation of support vector machines in adversarial environments. In Y. Ma and G. Guo, editors, Support Vector Machines Applications, pages 105–153. Springer, 2014.
3. B. Biggio, B. Nelson, and P. Laskov. Support vector machines under adversarial label noise.
In Proceedings of the 3rd Asian Conference on Machine Learning (ACML2011), pages 97–
112, 2011.
4. N. Carlini and D. A. Wagner. Towards evaluating the robustness of neural networks. In Proc.
of 2017 IEEE Symposium on Security and Privacy (SP2017), pages 39–57, 2017.
5. C.-C. Chang and C.-J. Lin. Libsvm: A library for support vector machines. ACM Trans.
Intell. Syst. Technol., 2(3):27:1–27:27, May 2011.
6. P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL1977), pages 238–252. ACM, 1977.
7. N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, 2000.
8. R. Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Proc.
15th Intern. Symp, on Automated Technology for Verification and Analysis (ATVA2017), pages 269–286, 2017.
9. T. Gehr, M. Mirman, D. Drachsler-Cohen, P. Tsankov, S. Chaudhuri, and M. T. Vechev. AI2:
safety and robustness certification of neural networks with abstract interpretation. In Proc.
2018 IEEE Symposium on Security and Privacy (SP2018), pages 3–18, 2018.
10. I. Goodfellow, P. McDaniel, and N. Papernot. Making machine learning robust against ad-versarial inputs. Commun. ACM, 61(7):56–66, 2018.
11. I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples.
In Proc. International Conference on Learning Representations (ICLR2015), 2015.
12. D. Gopinath, G. Katz, C. S. Pasareanu, and C. Barrett. DeepSafe: A data-driven approach for assessing robustness of neural networks. In Proceedings of the 16th Int. Symp. on Automated Technology for Verification and Analysis (ATVA2018), pages 3–19, 2018.
13. E. Goubault and S. Putot. A zonotopic framework for functional abstractions. Formal Meth-ods in System Design, 47(3):302–360, 2015.
14. C.-W. Hsu and C.-J. Lin. A comparison of methods for multiclass support vector machines.
IEEE Trans. Neur. Netw., 13(2):415–425, 2002.
15. X. Huang, M. Kwiatkowska, S. Wang, and M. Wu. Safety verification of deep neural net-works. In Proc. Intern. Conf. on Computer Aided Verification (CAV2017), pages 3–29.
Springer, 2017.
16. G. Katz, C. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Proc. Intern. Conf. on Computer Aided Verification (CAV2017), pages 97–117. Springer, 2017.
17. A. Kurakin, I. J. Goodfellow, and S. Bengio. Adversarial machine learning at scale. In Proceedings of the 5th International Conference on Learning Representations (ICLR2017), 2017.
18. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
19. F. Leofante and A. Tacchella. Learning in physical domains: Mating safety requirements and costly sampling. In Proc. of the Conference of the Italian Association for Artificial Intelligence, pages 539–552. Springer, 2016.
20. F. Messine. Extentions of affine arithmetic: Application to unconstrained global optimiza-tion. J. Universal Computer Science, 8(11):992–1015, 2002.
21. A. Min´e. Relational abstract domains for the detection of floating-point run-time errors. In Proc. European Symposium on Programming (ESOP2004), pages 3–17. Springer, 2004.
22. A. Min´e. Tutorial on static inference of numeric invariants by abstract interpretation. Foun-dations and Trends in Programming Languages, 4(3-4):120–372, 2017.
23. M. Mirman, T. Gehr, and M. Vechev. Differentiable abstract interpretation for provably robust neural networks. In Proc. of the International Conference on Machine Learning (ICML2018), pages 3575–3583, 2018.
24. G. P. Nam, B. J. Kang, and K. R. Park. Robustness of face recognition to variations of illu-mination on mobile devices based on SVM. KSII Transactions on Internet and Information Systems, 4(1):25–44, 2010.
25. F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. VanderPlas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.
26. L. Pulina and A. Tacchella. An abstraction-refinement approach to verification of artificial neural networks. In Proc. of the Intern. Conf. on Computer Aided Verification (CAV2010), pages 243–257. Springer, 2010.
27. L. Pulina and A. Tacchella. Challenging SMT solvers to verify neural networks. AI Com-mun., 25(2):117–135, 2012.
28. F. Ranzato. Complete abstractions everywhere (invited paper). In Proceedings of the 14th International Conference on Verification, Model Checking, and Abstract Interpretation (VM-CAI’13), LNCS vol. 7737, pages 15–26. Springer, 2013.
29. F. Ranzato and M. Zanella. Robustness verification of support vector machines.http://arxiv.
org/abs/1904.11803, CoRR arXiv, April 2019.
30. F. Ranzato and M. Zanella. SAVer GitHub Repository. https://github.com/
svm-abstract-verifier, 2019.
31. G. Singh, T. Gehr, M. Mirman, M. P¨uschel, and M. T. Vechev. Fast and effective robust-ness certification. In Advances in Neural Information Processing Systems 31: Proc. Annual Conference on Neural Information Processing Systems 2018, (NeurIPS2018), pages 10825–
10836, 2018.
32. G. Singh, T. Gehr, M. P¨uschel, and M. Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Lang., 3(POPL2019):41:1–41:30, Jan. 2019.
33. I. Skalna and M. Hlad´ık. A new algorithm for Chebyshev minimum-error multiplication of reduced affine forms. Numerical Algorithms, 76(4):1131–1152, Dec 2017.
34. I. C. Society. IEEE standard for binary floating-point arithmetic. Institute of Electrical and Electronics Engineers, New York, 1985. Note: Standard 754–1985.
35. J. Stolfi and L. H. de Figueiredo. Self-Validated Numerical Methods and Applications.
Brazilian Mathematics Colloquium Monograph, IMPA, Rio de Janeiro, Brazil, 1997.
36. J. Stolfi and L. H. de Figueiredo. Affine arithmetic: Concepts and applications. Numerical Algorithms, 37(1):147–158, Dec 2004.
37. T. B. Trafalis and R. C. Gilbert. Robust support vector machines for classification and com-putational issues. Optimisation Methods and Software, 22(1):187–198, 2007.
38. Y. Vorobeychik and M. Kantarcioglu. Adversarial machine learning. In Synthesis Lectures on Artificial Intelligence and Machine Learning, volume 12(3), pages 1–169. Morgan &
Claypool Publishers, August 2018.
39. S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana. Formal security analysis of neural net-works using symbolic intervals. In Proceedings of the 27th USENIX Conference on Security Symposium, (SEC2018), pages 1599–1614. USENIX Association, 2018.
40. T. Weng, H. Zhang, H. Chen, Z. Song, C. Hsieh, L. Daniel, D. S. Boning, and I. S. Dhillon.
Towards fast computation of certified robustness for ReLU networks. In Proceedings of the 35th International Conference on Machine Learning, (ICML2018), pages 5273–5282, 2018.
41. H. Xiao, B. Biggio, B. Nelson, H. Xiao, C. Eckert, and F. Roli. Support vector machines under adversarial label contamination. Neurocomputing, 160:53–62, 2015.
42. H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: A novel image dataset for benchmark-ing machine learnbenchmark-ing algorithms. CoRR arXiv, abs/1708.07747, 2017.
43. H. Xu, C. Caramanis, and S. Mannor. Robustness and regularization of support vector ma-chines. Journal of Machine Learning Research, 10:1485–1510, 2009.
44. M. Zajac, K. Zolna, N. Rostamzadeh, and P. O. Pinheiro. Adversarial framing for image and video classification. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI2019), 2019.
45. Z. Zhao, D. Dua, and S. Singh. Generating natural adversarial examples. In Proc. 6th International Conference on Learning Representations (ICLR2018), 2018.
46. Y. Zhou, M. Kantarcioglu, B. Thuraisingham, and B. Xi. Adversarial support vector machine learning. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD2012), pages 1059–1067. ACM, 2012.