This report summarizes the 3rd International Verification of Neural Networks Competition (VNN-COMP 2022), held as a part of the 5th Workshop on Formal Methods for ML-Enabled Autonomous Systems (FoMLAS), which was collocated with the 34th International Conference on Computer-Aided Verification (CAV). VNN-COMP is held annually to facilitate the fair and objective comparison of state-of-the-art neural network verification tools, encourage the standardization of tool interfaces, and bring together the neural network verification community. To this end, standardized formats for networks (ONNX) and specification (VNN-LIB) were defined, tools were evaluated on equal-cost hardware (using an automatic evaluation pipeline based on AWS instances), and tool parameters were chosen by the participants before the final test sets were made public. In the 2022 iteration, 11 teams participated on a diverse set of 12 scored benchmarks. This report summarizes the rules, benchmarks, participating tools, results, and lessons learned from this iteration of this competition.

背景信息：在过去几年中，机器学习（ML）一直是许多创新的核心。然而，包括在所谓的“安全关键”系统中，例如汽车或航空的系统已经被证明是非常具有挑战性的，因为ML的范式转变为ML带来完全改变传统认证方法。目的：本文旨在阐明与ML为基础的安全关键系统认证有关的挑战，以及文献中提出的解决方案，以解决它们，回答问题的问题如何证明基于机器学习的安全关键系统？'方法：我们开展2015年至2020年至2020年之间发布的研究论文的系统文献综述（SLR），涵盖了与ML系统认证有关的主题。总共确定了217篇论文涵盖了主题，被认为是ML认证的主要支柱：鲁棒性，不确定性，解释性，验证，安全强化学习和直接认证。我们分析了每个子场的主要趋势和问题，并提取了提取的论文的总结。结果：单反结果突出了社区对该主题的热情，以及在数据集和模型类型方面缺乏多样性。它还强调需要进一步发展学术界和行业之间的联系，以加深域名研究。最后，它还说明了必须在上面提到的主要支柱之间建立连接的必要性，这些主要柱主要主要研究。结论：我们强调了目前部署的努力，以实现ML基于ML的软件系统，并讨论了一些未来的研究方向。

当与分支和界限结合使用时，结合的传播方法是正式验证深神经网络（例如正确性，鲁棒性和安全性）的最有效方法之一。但是，现有作品无法处理在传统求解器中广泛接受的切割平面限制的一般形式，这对于通过凸出凸松弛的加强验证者至关重要。在本文中，我们概括了结合的传播程序，以允许添加任意切割平面的约束，包括涉及放宽整数变量的限制，这些变量未出现在现有的结合传播公式中。我们的广义结合传播方法GCP-crown为应用一般切割平面方法}开辟了一个机会进行神经网络验证，同时受益于结合传播方法的效率和GPU加速。作为案例研究，我们研究了由现成的混合整数编程（MIP）求解器生成的切割平面的使用。我们发现，MIP求解器可以生成高质量的切割平面，以使用我们的新配方来增强基于界限的验证者。由于以分支为重点的绑定传播程序和切削平面的MIP求解器可以使用不同类型的硬件（GPU和CPU）并行运行，因此它们的组合可以迅速探索大量具有强切割平面的分支，从而导致强大的分支验证性能。实验表明，与VNN-Comp 2021中最佳工具相比，我们的方法是第一个可以完全求解椭圆形的基准并验证椭圆21基准的两倍的验证者，并且在oval21基准测试中的最佳工具也明显超过了最先进的验证器。广泛的基准。 GCP-Crown是$ \ alpha $，$ \ beta $ -Crown验证者，VNN-COMP 2022获奖者的一部分。代码可在http://papercode.cc/gcp-crown上获得

神经网络已广泛应用于垃圾邮件和网络钓鱼检测，入侵预防和恶意软件检测等安全应用程序。但是，这种黑盒方法通常在应用中具有不确定性和不良的解释性。此外，神经网络本身通常容易受到对抗攻击的影响。由于这些原因，人们对可信赖和严格的方法有很高的需求来验证神经网络模型的鲁棒性。对抗性的鲁棒性在处理恶意操纵输入时涉及神经网络的可靠性，是安全和机器学习中最热门的主题之一。在这项工作中，我们在神经网络的对抗性鲁棒性验证中调查了现有文献，并在机器学习，安全和软件工程领域收集了39项多元化研究工作。我们系统地分析了它们的方法，包括如何制定鲁棒性，使用哪种验证技术以及每种技术的优势和局限性。我们从正式验证的角度提供分类学，以全面理解该主题。我们根据财产规范，减少问题和推理策略对现有技术进行分类。我们还展示了使用样本模型在现有研究中应用的代表性技术。最后，我们讨论了未来研究的开放问题。

我们考虑了认证深神经网络对现实分布变化的鲁棒性的问题。为此，我们通过提出一个新型的神经符号验证框架来弥合手工制作的规格和现实部署设置之间的差距模型。这种环境引起的一个独特的挑战是，现有的验证者不能紧密地近似sigmoid激活，这对于许多最新的生成模型至关重要。为了应对这一挑战，我们提出了一个通用的元算象来处理乙状结肠激活，该乙状结激素利用反示例引导的抽象细化的经典概念。关键思想是“懒惰地”完善Sigmoid函数的抽象，以排除先前抽象中发现的虚假反示例，从而确保验证过程中的进展，同时保持状态空间较小。 MNIST和CIFAR-10数据集的实验表明，我们的框架在一系列具有挑战性的分配变化方面大大优于现有方法。

深度神经网络（DNN）的巨大进步导致了各种任务的最先进的性能。然而，最近的研究表明，DNNS容易受到对抗的攻击，这在将这些模型部署到自动驾驶等安全关键型应用时，这使得非常关注。已经提出了不同的防御方法，包括：a）经验防御，通常可以在不提供稳健性认证的情况下再次再次攻击; b）可认真的稳健方法，由稳健性验证组成，提供了在某些条件下的任何攻击和相应的强大培训方法中的稳健准确性的下限。在本文中，我们系统化了可认真的稳健方法和相关的实用和理论意义和调查结果。我们还提供了在不同数据集上现有的稳健验证和培训方法的第一个全面基准。特别是，我们1）为稳健性验证和培训方法提供分类，以及总结代表性算法的方法，2）揭示这些方法中的特征，优势，局限性和基本联系，3）讨论当前的研究进展情况TNN和4的可信稳健方法的理论障碍，主要挑战和未来方向提供了一个开放的统一平台，以评估超过20种代表可认真的稳健方法，用于各种DNN。

基于基于不完整的神经网络验证如冠的绑定传播非常有效，可以显着加速基于神经网络的分支和绑定（BAB）。然而，绑定的传播不能完全处理由昂贵的线性编程（LP）求解器的BAB常规引入的神经元分割限制，导致界限和损伤验证效率。在这项工作中，我们开发了一种基于$ \ beta $ -cra所做的，一种基于新的绑定传播方法，可以通过从原始或双空间构造的可优化参数$ \ beta $完全编码神经元分割。当在中间层中联合优化时，$ \ Beta $ -CROWN通常会产生比具有神经元分裂约束的典型LP验证更好的界限，同时像GPU上的皇冠一样高效且并行化。适用于完全稳健的验证基准，使用BAB的$ \ Beta $ -CROWN比基于LP的BAB方法快三个数量级，并且比所有现有方法更快，同时产生较低的超时率。通过早期终止BAB，我们的方法也可用于有效的不完整验证。与强大的不完整验证者相比，我们始终如一地在许多设置中获得更高的验证准确性，包括基于凸屏障破碎技术的验证技术。与最严重但非常昂贵的Semidefinite编程（SDP）的不完整验证者相比，我们获得了更高的验证精度，验证时间较少三个级。我们的算法授权$ \ alpha，\ \β$ -craft（Alpha-Beta-Crown）验证者，VNN-Comp 2021中的获胜工具。我们的代码可在http://papercode.cc/betacrown提供

由于它们在计算机视觉，图像处理和其他人领域的优异性能，卷积神经网络具有极大的普及。不幸的是，现在众所周知，卷积网络通常产生错误的结果 - 例如，这些网络的输入的小扰动可能导致严重的分类错误。近年来提出了许多验证方法，以证明没有此类错误，但这些通常用于完全连接的网络，并且在应用于卷积网络时遭受加剧的可扩展性问题。为了解决这一差距，我们在这里介绍了CNN-ABS框架，特别是旨在验证卷积网络。 CNN-ABS的核心是一种抽象细化技术，它通过拆除卷积连接，以便在这种方式创造原始问题的过度逼近来简化验证问题;如果产生的问题变得过于抽象，它会恢复这些连接。 CNN-ABS旨在使用现有的验证引擎作为后端，我们的评估表明它可以显着提高最先进的DNN验证引擎的性能，平均降低运行时间15.7％。

We present AI 2 , the first sound and scalable analyzer for deep neural networks. Based on overapproximation, AI 2 can automatically prove safety properties (e.g., robustness) of realistic neural networks (e.g., convolutional neural networks).The key insight behind AI 2 is to phrase reasoning about safety and robustness of neural networks in terms of classic abstract interpretation, enabling us to leverage decades of advances in that area. Concretely, we introduce abstract transformers that capture the behavior of fully connected and convolutional neural network layers with rectified linear unit activations (ReLU), as well as max pooling layers. This allows us to handle real-world neural networks, which are often built out of those types of layers.We present a complete implementation of AI 2 together with an extensive evaluation on 20 neural networks. Our results demonstrate that: (i) AI 2 is precise enough to prove useful specifications (e.g., robustness), (ii) AI 2 can be used to certify the effectiveness of state-of-the-art defenses for neural networks, (iii) AI 2 is significantly faster than existing analyzers based on symbolic analysis, which often take hours to verify simple fully connected networks, and (iv) AI 2 can handle deep convolutional networks, which are beyond the reach of existing methods.

We study the problem of training and certifying adversarially robust quantized neural networks (QNNs). Quantization is a technique for making neural networks more efficient by running them using low-bit integer arithmetic and is therefore commonly adopted in industry. Recent work has shown that floating-point neural networks that have been verified to be robust can become vulnerable to adversarial attacks after quantization, and certification of the quantized representation is necessary to guarantee robustness. In this work, we present quantization-aware interval bound propagation (QA-IBP), a novel method for training robust QNNs. Inspired by advances in robust learning of non-quantized networks, our training algorithm computes the gradient of an abstract representation of the actual network. Unlike existing approaches, our method can handle the discrete semantics of QNNs. Based on QA-IBP, we also develop a complete verification procedure for verifying the adversarial robustness of QNNs, which is guaranteed to terminate and produce a correct answer. Compared to existing approaches, the key advantage of our verification procedure is that it runs entirely on GPU or other accelerator devices. We demonstrate experimentally that our approach significantly outperforms existing methods and establish the new state-of-the-art for training and certifying the robustness of QNNs.

在过去的几年中，连续的深度学习模型（称为神经普通微分方程（神经odes））受到了广泛关注。尽管它们迅速产生影响，但对于这些系统缺乏正式的分析技术。在本文中，我们考虑了具有不同架构和层次的一般神经odes类，并引入了一种新颖的可及性框架，可以对其行为进行正式分析。为神经ODE的可及性分析而开发的方法是在称为NNVODE的新工具中实现的。具体而言，我们的工作扩展了现有的神经网络验证工具以支持神经ODE。我们通过分析包括用于分类的神经ODE的一组基准以及控制和动态系统的一组基准来证明我们方法的功能和功效，包括评估我们方法对我们方法在现有软件工具中的功效和能力的评估。如果可以这样做，则连续的时间系统可达性文献。

作为神经网络（NNS）越来越多地引入安全关键域，在部署之前越来越需要在部署之前正式验证NNS。在这项工作中，我们专注于NN等效的正式验证问题，其旨在证明两个NNS（例如原件和压缩版本）显示等效行为。已经提出了两种方法：混合整数线性编程和间隔传播。虽然第一种方法缺乏可扩展性，但后者仅适用于结构性相似的NN，其重量变化很小。我们纸张的贡献有四个部分。首先，我们通过证明epsilon-andatience问题是突出的，我们表现出理论结果。其次，我们扩展了Tran等人。单个NN几何路径枚举算法以多个NN的设置。在第三步中，我们实现了扩展算法，用于等价验证，评估其实际使用所需的优化。最后，我们执行比较评估，显示我们的方法优于前一种最先进的现有技术，两者，用于等效验证以及反例查找。

We present an approach for the verification of feed-forward neural networks in which all nodes have a piece-wise linear activation function. Such networks are often used in deep learning and have been shown to be hard to verify for modern satisfiability modulo theory (SMT) and integer linear programming (ILP) solvers.The starting point of our approach is the addition of a global linear approximation of the overall network behavior to the verification problem that helps with SMT-like reasoning over the network behavior. We present a specialized verification algorithm that employs this approximation in a search process in which it infers additional node phases for the non-linear nodes in the network from partial node phase assignments, similar to unit propagation in classical SAT solving. We also show how to infer additional conflict clauses and safe node fixtures from the results of the analysis steps performed during the search. The resulting approach is evaluated on collision avoidance and handwritten digit recognition case studies.

Existing neural network verifiers compute a proof that each input is handled correctly under a given perturbation by propagating a symbolic abstraction of reachable values at each layer. This process is repeated from scratch independently for each input (e.g., image) and perturbation (e.g., rotation), leading to an expensive overall proof effort when handling an entire dataset. In this work, we introduce a new method for reducing this verification cost without losing precision based on a key insight that abstractions obtained at intermediate layers for different inputs and perturbations can overlap or contain each other. Leveraging our insight, we introduce the general concept of shared certificates, enabling proof effort reuse across multiple inputs to reduce overall verification costs. We perform an extensive experimental evaluation to demonstrate the effectiveness of shared certificates in reducing the verification cost on a range of datasets and attack specifications on image classifiers including the popular patch and geometric perturbations. We release our implementation at https://github.com/eth-sri/proof-sharing.

在过去的十年中，神经网络（NNS）已被广泛用于许多应用程序，包括安全系统，例如自主系统。尽管采用了新兴的采用，但众所周知，NNS容易受到对抗攻击的影响。因此，提供确保此类系统正常工作的保证非常重要。为了解决这些问题，我们介绍了一个修复不安全NNS W.R.T.的框架。安全规范，即利用可满足的模型理论（SMT）求解器。我们的方法能够通过仅修改其重量值的一些重量值来搜索新的，安全的NN表示形式。此外，我们的技术试图最大程度地提高与原始网络在其决策边界方面的相似性。我们进行了广泛的实验，以证明我们提出的框架能够产生安全NNS W.R.T.的能力。对抗性的鲁棒性特性，只有轻度的准确性损失（就相似性而言）。此外，我们将我们的方法与天真的基线进行比较，以证明其有效性。总而言之，我们提供了一种算法以自动修复具有安全性的算法，并建议一些启发式方法以提高其计算性能。当前，通过遵循这种方法，我们能够产生由分段线性relu激活函数组成的小型（即具有多达数百个参数）的小型（即具有多达数百个参数）。然而，我们的框架是可以合成NNS W.R.T.的一般框架。一阶逻辑规范的任何可决定片段。

随着神经网络的不断扩展，对其财产的完整和合理验证的需求变得至关重要。近年来，确定二进制神经网络（BNN）在布尔逻辑中具有等效的表示，并且可以使用诸如SAT求解器之类的逻辑推理工具进行正式分析。但是，迄今为止，只能将BNN转换为SAT公式。在这项工作中，我们介绍了真实表深卷积神经网络（TTNETS），这是一个新的sat-odsody型号，首次是现实价值的重量。此外，它通过构造承认，在稳健性验证设置中，包括调节后和拖延性，包括后调整功能。后一种属性导致比BNN更紧凑的SAT符号编码。这使使用一般SAT求解器的使用使属性验证更加容易。我们证明了TTNET关于形式鲁棒性属性的值：TTNET在具有可比的计算时间的所有BNN的验证精度上优于验证的准确性。更普遍地，它们代表了所有已知的完整验证方法之间的相关权衡：TTNET在快速验证时间内实现了高验证的精度，并且没有超时。在这里，我们正在探索TTNET的概念证明，以实现非常重要的应用（稳健性的完整验证），我们相信这个新颖的实现的网络构成了对功能正式验证需求不断增长的实际响应。我们假设TTNET可以应用于各种基于CNN的架构，并将其扩展到其他属性，例如公平性，故障攻击和精确规则提取。

最近，图形神经网络（GNN）已应用于群集上的调整工作，比手工制作的启发式方法更好地表现了。尽管表现令人印象深刻，但仍然担心这些基于GNN的工作调度程序是否满足用户对其他重要属性的期望，例如防止策略，共享激励和稳定性。在这项工作中，我们考虑对基于GNN的工作调度程序的正式验证。我们解决了几个特定领域的挑战，例如网络，这些挑战比验证图像和NLP分类器时遇到的更深层和规格更丰富。我们开发了拉斯维加斯，这是基于精心设计的算法，将这些调度程序的单步和多步属性验证的第一个通用框架，它们结合了抽象，改进，求解器和证明传输。我们的实验结果表明，与以前的方法相比，维加斯在验证基于GNN的调度程序的重要特性时会达到显着加速。

深度神经网络的鲁棒性对于现代AI支持系统至关重要，应正式验证。在广泛的应用中采用了类似乙状结肠的神经网络。由于它们的非线性，通常会过度评估乙状结肠样激活功能，以进行有效的验证，这不可避免地引入了不精确度。已大量的努力致力于找到所谓的更紧密的近似值，以获得更精确的验证结果。但是，现有的紧密定义是启发式的，缺乏理论基础。我们对现有神经元的紧密表征进行了彻底的经验分析，并揭示它们仅在特定的神经网络上是优越的。然后，我们将网络紧密度的概念介绍为统一的紧密度定义，并表明计算网络紧密度是一个复杂的非convex优化问题。我们通过两个有效的，最紧密的近似值从不同的角度绕过复杂性。结果表明，我们在艺术状态下的方法实现了有希望的表现：（i）达到高达251.28％的改善，以提高认证的较低鲁棒性界限； （ii）在卷积网络上表现出更为精确的验证结果。

Deep neural networks have achieved impressive experimental results in image classification, but can surprisingly be unstable with respect to adversarial perturbations, that is, minimal changes to the input image that cause the network to misclassify it. With potential applications including perception modules and end-to-end controllers for self-driving cars, this raises concerns about their safety. We develop a novel automated verification framework for feed-forward multi-layer neural networks based on Satisfiability Modulo Theory (SMT). We focus on safety of image classification decisions with respect to image manipulations, such as scratches or changes to camera angle or lighting conditions that would result in the same class being assigned by a human, and define safety for an individual decision in terms of invariance of the classification within a small neighbourhood of the original image. We enable exhaustive search of the region by employing discretisation, and propagate the analysis layer by layer. Our method works directly with the network code and, in contrast to existing methods, can guarantee that adversarial examples, if they exist, are found for the given region and family of manipulations. If found, adversarial examples can be shown to human testers and/or used to fine-tune the network. We implement the techniques using Z3 and evaluate them on state-of-the-art networks, including regularised and deep learning networks. We also compare against existing techniques to search for adversarial examples and estimate network robustness.

分析深神经网络对输入扰动的最坏情况的性能等于解决一个大规模的非凸优化问题，过去的几项工作提出了凸出的放松作为有希望的替代方案。但是，即使对于合理的神经网络，这些放松也无法处理，因此必须在实践中被较弱的放松所取代。在这项工作中，我们提出了一种新型的操作员分裂方法，该方法可以将问题直接解决至高精度的凸松弛，从而将其拆分为经常具有分析溶液的较小的子问题。该方法是模块化的，范围为非常大的问题实例，并损害了与GPU加速的快速并行化的操作。我们展示了我们在图像分类和强化学习设置以及神经网络动力学系统的可及性分析中界定大型卷积网络最差的方法的方法。