Bottoms Up for CHCs: Novel Transformation of Linear Constrained Horn Clauses to Software Verification

• URL: http://arxiv.org/abs/2404.15215v1
• Date: Tue, 23 Apr 2024 16:46:27 GMT
• Title: Bottoms Up for CHCs: Novel Transformation of Linear Constrained Horn Clauses to Software Verification
• Authors: Márk Somorjai, Mihály Dobos-Kovács, Zsófia Ádám, Levente Bajczi, András Vörös,
• Abstract summary: Constrained Horn Clauses (CHCs) have conventionally been used as a low-level representation in formal verification. We propose an alternative bottom-up approach for linear CHCs, and evaluate the two options in the open-source model checking framework THETA.
• Score: 0.09786690381850355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constrained Horn Clauses (CHCs) have conventionally been used as a low-level representation in formal verification. Most existing solvers use a diverse set of specialized techniques, including direct state space traversal or under-approximating abstraction, necessitating purpose-built complex algorithms. Other solvers successfully simplified the verification workflow by translating the problem to inputs for other verification tasks, leveraging the strengths of existing algorithms. One such approach transforms the CHC problem into a recursive program roughly emulating a top-down solver for the deduction task; and verifying the reachability of a safety violation specified as a control location. We propose an alternative bottom-up approach for linear CHCs, and evaluate the two options in the open-source model checking framework THETA on both synthetic and industrial examples. We find that there is a more than twofold increase in the number of solved tasks when the novel bottom-up approach is used in the verification workflow, in contrast with the top-down technique.

Related papers

• CoSIGN: Few-Step Guidance of ConSIstency Model to Solve General INverse Problems [3.3969056208620128]
  We propose to push the boundary of inference steps to 1-2 NFEs while still maintaining high reconstruction quality. Our method achieves new state-of-the-art in diffusion-based inverse problem solving.
  arXiv  Detail & Related papers  (2024-07-17T15:57:50Z)
• Weakly Supervised Co-training with Swapping Assignments for Semantic Segmentation [21.345548821276097]
  Class activation maps (CAMs) are commonly employed in weakly supervised semantic segmentation (WSSS) to produce pseudo-labels. We propose an end-to-end WSSS model incorporating guided CAMs, wherein our segmentation model is trained while concurrently optimizing CAMs online. CoSA is the first single-stage approach to outperform all existing multi-stage methods including those with additional supervision.
  arXiv  Detail & Related papers  (2024-02-27T21:08:23Z)
• FlowPG: Action-constrained Policy Gradient with Normalizing Flows [14.98383953401637]
  Action-constrained reinforcement learning (ACRL) is a popular approach for solving safety-critical resource-alential related decision making problems. A major challenge in ACRL is to ensure agent taking a valid action satisfying constraints in each step.
  arXiv  Detail & Related papers  (2024-02-07T11:11:46Z)
• PSDiff: Diffusion Model for Person Search with Iterative and Collaborative Refinement [59.6260680005195]
  We present a novel Person Search framework based on the Diffusion model, PSDiff. PSDiff formulates the person search as a dual denoising process from noisy boxes and ReID embeddings to ground truths. Following the new paradigm, we further design a new Collaborative Denoising Layer (CDL) to optimize detection and ReID sub-tasks in an iterative and collaborative way.
  arXiv  Detail & Related papers  (2023-09-20T08:16:39Z)
• Small Object Detection via Coarse-to-fine Proposal Generation and Imitation Learning [52.06176253457522]
  We propose a two-stage framework tailored for small object detection based on the Coarse-to-fine pipeline and Feature Imitation learning. CFINet achieves state-of-the-art performance on the large-scale small object detection benchmarks, SODA-D and SODA-A.
  arXiv  Detail & Related papers  (2023-08-18T13:13:09Z)
• Q-SHED: Distributed Optimization at the Edge via Hessian Eigenvectors Quantization [5.404315085380945]
  Newton-type (NT) methods have been advocated as enablers of robust convergence rates in DO problems. We propose Q-SHED, an original NT algorithm for DO featuring a novel bit-allocation scheme based on incremental Hessian eigenvectors quantization. We show that Q-SHED can reduce by up to 60% the number of communication rounds required for convergence.
  arXiv  Detail & Related papers  (2023-05-18T10:15:03Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  We propose two novel formulations that enable the development of computational efficient solvers based the alternating principle. The proposed solvers offer computational efficiency, theoretical convergence guarantees, local minima complexity with the number of views, and exceptional accuracy as compared with the state-of-the-art techniques.
  arXiv  Detail & Related papers  (2023-03-28T10:17:51Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  We generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers. Our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark.
  arXiv  Detail & Related papers  (2022-08-11T10:31:28Z)
• ReAct: Temporal Action Detection with Relational Queries [84.76646044604055]
  This work aims at advancing temporal action detection (TAD) using an encoder-decoder framework with action queries. We first propose a relational attention mechanism in the decoder, which guides the attention among queries based on their relations. Lastly, we propose to predict the localization quality of each action query at inference in order to distinguish high-quality queries.
  arXiv  Detail & Related papers  (2022-07-14T17:46:37Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.