检索结果-内蒙古大学图书馆

32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA)

作者： Yu, Shiwen Wang, Ting Wang, Ji Natl Univ Def Technol Coll Comp Sci & Technol Inst Quantum Informat Changsha Peoples R China Natl Univ Def Technol Coll Comp Sci & Technol Key Lab Software Engn Complex Syst State Key Lab High Performance Comp Changsha Peoples R China Natl Univ Def Technol Coll Comp Sci & Technol Key Lab Software Engn Complex Syst Changsha Peoples R China

ISBN: (纸本)9798400702211

Inferring loop invariants is one of the most challenging problems in program verification. It is highly desired to incorporate machine learning when inferring. This paper presents a Reinforcement Learning (RL) pruning framework to infer loop invariants over a general nonlinear hypothesis space. The key idea is to synergize the RL-based pruning and SMT solving to generate candidate invariants efficiently. To address the sparse reward problem in learning, we design a novel two-dimensional reward mechanism that enables the RL pruner to recognize the capability boundary of SMT solvers and learn the pruning heuristics in a few rounds. We have implemented our approach with Z3 SMT solver in the tool called LIPuS and conducted extensive experiments over the linear and nonlinear benchmarks. Experiment results show that LIPuS can solve the most cases compared to the state-of-the-art loop invariant inference tools such as Code2Inv, ICE-DT, GSpacer, SymInfer, ImplCheck, and Eldarica. Especially, LIPuS outperforms them significantly on nonlinear benchmarks.

关键词： reinforcement learning loop invariant program verification

来源：评论

学校读者我要写书评

暂无评论

LLM Meets Bounded Model Checking: Neuro-symbolic loop invariant Inference 24

LLM Meets Bounded Model Checking: Neuro-symbolic Loop Invari...

引用

39th ACM/IEEE International Conference on Automated Software Engineering (ASE)

作者： Wu, Guangyuan Cao, Weining Yao, Yuan Wei, Hengfeng Chen, Taolue Ma, Xiaoxing Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China Birkbeck Univ London Sch Comp & Math Sci London England

ISBN: (数字)9798400712487

ISBN: (纸本)9798400712487

loop invariant inference, a key component in program verification, is a challenging task due to the inherent undecidability and complex loop behaviors in practice. Recently, machine learning based techniques have demonstrated impressive performance in generating loop invariants automatically. However, these methods highly rely on the labeled training data, and are intrinsically random and uncertain, leading to unstable performance. In this paper, we investigate a synergy of large language models (LLMs) and bounded model checking (BMC) to address these issues. The key observation is that, although LLMs may not be able to return the correct loop invariant in one response, they usually can provide all individual predicates of the correct loop invariant in multiple responses. To this end, we propose a "query-filter-reassemble" strategy, namely, we first leverage the language generation power of LLMs to produce a set of candidate invariants, where training data is not needed. Then, we employ BMC to identify valid predicates from these candidate invariants, which are assembled to produce new candidate invariants and checked by off-the-shelf SMT solvers. The feedback is incorporated into the prompt for the next round of LLM querying. We expand the existing benchmark of 133 programs to 316 programs, providing a more comprehensive testing ground. Experimental results demonstrate that our approach significantly outperforms the state-of-the-art techniques, successfully generating 309 loop invariants out of 316 cases, whereas the existing baseline methods are only able to tackle 219 programs at best. The code is publicly available at https://***/SoftWiser-group/***.

关键词： loop invariant program verification large language model

来源：评论

学校读者我要写书评

暂无评论

Clause2Inv: A Generate-Combine-Check Framework for loop invariant Inference

Proceedings of the ACM on Software Engineering

引用

Proceedings of the ACM on Software Engineering 2025年第ISSTA期2卷 1009-1030页

作者： Weining Cao Guangyuan Wu Tangzhi Xu Yuan Yao Hengfeng Wei Taolue Chen Xiaoxing Ma Nanjing University Nanjing China Birkbeck University of London London United Kingdom

loop invariant inference is a fundamental, yet challenging, problem in program verification. Recent work adopts the guess-and-check framework, where candidate loop invariants are iteratively generated in the guess step and verified in the check step. A major challenge of this general framework is to produce high-quality candidate invariants in each iteration so that the inference procedure can converge quickly. Empirically, we observe that existing approaches may struggle with guessing the complete invariant due to the complexity of logical connectives, but usually, all the clauses of the correct loop invariant have already appeared in the previous guesses. This motivates us to refine the guess-and-check framework, resulting in a generate-combine-check framework, where the loop invariant inference task is divided into clause generation and clause combination. Specifically, we propose a novel loop invariant inference approach under the new framework, which consists of an LLM-based clause generator and a counterexample-driven clause combinator. As the clause generator, leverages LLMs to generate a multitude of clauses; as the clause combinator, leverages counterexamples from the previous rounds to convert generated clauses into invariants. Our experiments show that significantly outperforms existing loop invariant inference approaches. For example, solved 312 (out of 316) linear invariant inference tasks and 44 (out of 50) nonlinear invariant inference tasks, which is at least 93 and 16 more than the existing baselines, respectively. By design, the generate-combine-check framework is flexible to accommodate various existing approaches which are currently under the guess-and-check framework by splitting the guessed candidate invariants into clauses. The evaluation shows that our approach can, with minor adaptation, improve existing loop invariant inference approaches in both effectiveness and efficiency. For example, Code2Inv which solved 210 linear problems with an av

关键词： Program verification clause combination historical predictions loop invariant

来源：评论

学校读者我要写书评

暂无评论

Translation Validation of loop invariant Code Optimizations Involving False Computations 21st

Translation Validation of Loop Invariant Code Optimizations ...

引用

21st International Symposium on VLSI Design and Test (VDAT)

作者： Chouksey, Ramanuj Karfa, Chandan Bhaduri, Purandar Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 India

ISBN: (纸本)9789811074707;9789811074691

Code motion based optimizations are used quite often in electronic design automation (EDA) tools to improve the quality of synthesis results. Ensuring the correctness of such transformation is necessary for reliability of EDA tools. A value propagation (VP) based equivalence checking method of finite state machine with datapaths (FSMD) was proposed in [1] to specifically verify code motion across loops. In this work, we identify some scenarios involving loop invariant code motion where the VP based equivalence checking method fails to establish the equivalence between two actually equivalent FSMDs. We propose an enhancement over the VP based equivalence checking method [1] to overcome this limitation. Experimental results demonstrate that our method can handle the scenario where the VP based equivalence checking method fails.

关键词： Formal verification Translation validation Code motion Equivalence checking loop invariant FSMDs model

来源：评论

学校读者我要写书评

暂无评论

Full-program induction: verifying array programs sans loop invariants

引用

INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER 2022年第5期24卷 843-888页

作者： Chakraborty, Supratik Gupta, Ashutosh Unadkat, Divyesh Indian Inst Technol Comp Sci & Engn Main Gate Rd Mumbai 400076 Maharashtra India TCS Res 54-B Hadapsar Ind Estate Pune 411013 Maharashtra India

Arrays are commonly used in a variety of software to store and process data in loops. Automatically proving safety properties of such programs that manipulate arrays is challenging. We present a novel verification technique, called full-program induction, for proving (a sub-class of) quantified as well as quantifier-free properties of programs manipulating arrays of parametric size N. Instead of inducting over individual loops, our technique inducts over the entire program (possibly containing multiple loops) directly via the program parameter N. The technique performs non-trivial transformations of the given program and pre-conditions during the inductive step. The transformations assist in effectively reducing the assertion checking problem by transforming a program with multiple loops to a program which has fewer and simpler loops or is loop free. Significantly, full-program induction does not require generation or use of loop-specific invariants. To assess the efficacy of our technique, we have developed a prototype tool called Vajra. We demonstrate the performance of Vajra vis-a-vis several state-of-the-art tools on a large set of array manipulating benchmarks from the international software verification competition (SV-COMP) and on several programs inspired by algebraic functions that perform polynomial computations.

关键词： Full-program induction Inductive proof Hoare triple Array programs Difference program Difference pre-condition Quantified assertions loop invariant

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Program Construction and Verification Method Based on Partition Recursion and Morgan's Refinement Rules

引用

Wuhan University Journal of Natural Sciences 2023年第3期28卷 246-256页

作者： WANG Changjing CAO Zhongxiong YU Chuling WANG Changchang HUANG Qing ZUO Zhengkang College of Computer Information Engineering Jiangxi Normal UniversityNanchang 330022JiangxiChina College of Digital Industry Academy Jiangxi Normal UniversityShangrao 334000JiangxiChina

The traditional program refinement strategy cannot be refined to an executable program,and there are issues such as low verification reliability and *** solve the above problems,this paper proposes a nonlinear program construction and verification method based on partition recursion and Morgan’s refinement ***,we use recursive definition technique to characterize the initial *** specification is then transformed into GCL(Guarded Command Language)programs using loop invariant derivation and Morgan’s refinement ***,VCG(Verification Condition Generator)is used in the GCL program to generate the verification condition *** Isabelle theorem prover then validates the GCL program’s ***,the GCL code generates a C++executable program automatically via the conversion *** effectiveness of this method is demonstrated using binary tree preorder traversal program construction and verification as an *** method addresses the problem that the construction process’s loop invariant is difficult to obtain and the refinement process is insufficiently *** the same time,the method improves verification process automation and reduces the manual verification workload.

关键词： program construction partition recursion Morgan's refinement rules loop invariant VCG Isabelle theorem prover

来源：评论

学校读者我要写书评

暂无评论

Towards Automatic Deductive Verification of C Programs with Sisal loops Using the C-lightVer System

引用

AUTOMATIC CONTROL AND COMPUTER SCIENCES 2022年第7期56卷 669-687页

作者： Kondratyev, D. A. Russian Acad Sci Ershov Inst Informat Syst Siberian Branch Novosibirsk 630090 Russia

The C-lightVer system for deductive verification of C programs has been developed at the Institute of Informatics Systems of the Siberian Branch of the Russian Academy of Sciences (IIS SB RAS). C-kernel is an intermediate verification language in this system. The cloud parallel programming system (CPPS) is also developed at the IIS SB RAS. Cloud Sisal is the input language of the CPPS system. The main feature of the CPPS system is the implicit parallel execution based on the automatic parallelization of Cloud Sisal loops. Cloud-Sisal-kernel is an intermediate verification language in the CPPS system. Our goal is the automatic parallelization of such a superset of the C language that allows implementing automatic verification. Our solution is a superset of the C-kernel language such as the C-Sisal-kernel language. The first result presented in this article is an extension of C-kernel by Cloud-Sisal-kernel loops. As a consequence, the C-Sisal-kernel language is developed. The second result presented in this article is the extension of the C-kernel axiomatic semantics by an inference rule for Cloud-Sisal-kernel loops. This article also presents our approach to the problem of automating deductive verification in the case of definite iterations over data sequences. Such loops are called definite iterations. Our solution is a composition of a symbolic method of verification of definite iterations, verification condition metageneration, and mixed axiomatic semantics. The symbolic method of verification of definite iterations allows us to define inference rules for such loops without invariants. Symbolic replacement of definite iterations by recursive functions is the basis of this method. The resulting verification conditions using recursive functions correspond to the logical basis of the ACL2 prover. We use the ACL2 system based on computable recursive functions. Verification condition metageneration simplifies the implementation of new inference rules in the verificatio

关键词： Keywords deductive verification C-lightVer cloud parallel programming system symbolic method of verification of definite iterations loop invariant ACL2

来源：评论

学校读者我要写书评

暂无评论

On proving that an unsafe controller is not proven safe

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING 2024年 137卷

作者： Selvaraj, Yuvaraj Krook, Jonas Ahrendt, Wolfgang Fabian, Martin Zenseact Lindholmspiren 2 S-41756 Gothenburg Sweden Chalmers Univ Technol SciLifeLab Chalmersplatsen 4 S-41296 Gothenburg Sweden

Cyber-physical systems are often safety-critical and their correctness is crucial, such as in the case of automated driving. Using formal mathematical methods is one way to guarantee correctness and improve safety. Although these methods have shown their usefulness, care must be taken because modelling errors might result in proving a faulty controller safe, which is potentially catastrophic in practice. This paper deals with two such modelling errors in differential dynamic logic, a formal specification and verification language for hybrid systems, which are mathematical models of cyber-physical systems. The main contributions are to provide conditions under which these two modelling errors cannot cause a faulty controller to be proven safe, and to show how these conditions can be proven with help of the interactive theorem prover KeYmaera X. The problems are illustrated with a real world example of a safety controller for automated driving, and it is shown that the formulated conditions have the intended effect both for a faulty and a correct controller. It is also shown how the formulated conditions aid in finding a loop invariant candidate to prove properties of hybrid systems with feedback loops. Furthermore, the relation between such a loop invariant and the characterisation of the maximal control invariant set is discussed.

关键词： Hybrid systems Automated driving Formal verification loop invariant Theorem proving

来源：评论

学校读者我要写书评

暂无评论

loop invariant synthesis in a combined abstract domain

引用

JOURNAL OF SYMBOLIC COMPUTATION 2013年 50卷 386-408页

作者： Qin, Shengchao He, Guanhua Luo, Chenguang Chin, Wei-Ngan Chen, Xin Univ Teesside Sch Comp Middlesbrough TS1 3BA Cleveland England Beijing Univ Technol Coll Comp Sci Beijing Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Natl Univ Singapore Sch Comp Singapore 117548 Singapore

Automated verification of memory safety and functional correctness for heap-manipulating programs has been a challenging task, especially when dealing with complex data structures with strong invariants involving both shape and numerical properties. Existing verification systems usually rely on users to supply annotations to guide the verification, which can be cumbersome and error-prone by hand and can significantly restrict the usability of the verification system. In this paper, we reduce the need for some user annotations by automatically inferring loop invariants over an abstract domain with both shape and numerical information. Our loop invariant synthesis is conducted automatically by a fixed-point iteration process, equipped with newly designed abstraction mechanism, together with join and widening operators over the combined domain. We have also proven the soundness and termination of our approach. Initial experiments confirm that we can synthesise loop invariants with non-trivial constraints. (C) 2012 Elsevier B.V. All rights reserved.

关键词： loop invariant Fixpoint analysis Abstraction Combining analysis Shape analysis Numerical analysis Separation logic

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Analysis of loops With Relaxed Abstract Transformers

引用

IEEE TRANSACTIONS ON RELIABILITY 2020年第1期69卷 203-215页

作者： Yin, Banghu Chen, Liqian Liu, Jiangchao Wang, Ji Natl Univ Def Technol Sch Comp Sci Changsha 410000 Peoples R China Natl Univ Def Technol State Key Lab High Performance Comp Changsha 410000 Peoples R China

Numerical computation is often involved in software of embedded control systems, cyber-physical systems, artificial neural network systems, big data processing systems, etc. Automatically discovering numerical loop invariants is fundamental for checking the safety of such software. Abstract interpretation provides a framework to automatically discover sound invariants but which may be not precise enough due to over-approximations. One major source of precision loss is due to the limited linear expressiveness of most widely used numerical abstract domains and the widening operation. This becomes more serious when analyzing all variables simultaneously as a whole for programs that involve nonlinear behaviors. Based on the observation that the dependency among variables in a loop can be hierarchical, in this article, we propose a hierarchical static analysis to analyze a loop by utilizing relaxed abstract transformers. The main idea is to first partition all variables involved in a loop into different hierarchical layers, then compute invariants over the variables layer by layer in a bottom-up manner. During the iterative process, the computed invariants over lower layer variables are then used to relax transfer functions when analyzing the higher layer variables. One benefit of our method lies in that it can generate linear invariants to soundly enclose nonlinear behaviors in a loop. Finally, we present encouraging experimental results on benchmark programs involving nonlinear behaviors.

关键词： Abstract interpretation abstract transformer hierarchical analysis loop invariant relaxing operator static analysis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：