Safety and robustness properties are highly required for neural networks deployed in safety-critical applications. Current complete verification techniques of these properties suffer from the lack of efficiency and effectiveness. In this article, we present an efficient complete approach to verify safety and robustness properties of neural networks through incrementally determinizing activation states of neurons. The key idea is to generate constraints via layerwised splitting that make activation states of hidden neurons become deterministic efficiently. These constraints are then utilized for refining inputs systematically so that abstract analysis over the refined input can be more precise. Our approach decomposes a verification problem into a set of subproblems via layerwised input space splitting. The property is then checked on each subproblem, where the activation states of at least one hidden neurons will be determinized. Further checking is accelerated by constraint-guided input refinement. We have implemented a parallel tool called LayerSAR to verify safety and robustness properties of ReLU neural networks in a sound and complete way, and evaluated it extensively on several benchmark sets. Experimental results show that our approach is promising, compared with complete tools, such as Planet, Neurify, Marabou, ERAN, Venus, Venus2, and nnenum in verifying safety and robustness properties on the benchmarks.
14 August 2019 in IEEE Transactions on Reliability
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.
Whether a counterexample is genuine or spurious fundamentally influences the effectiveness and completeness of loop invariant inference, which is a core component of automated program verification. However, reliably determining the validity of a counterexample remains a challenging task. In this paper, we present a systematic evaluation of large language models (LLMs) on this problem. We construct a benchmark of program states that serve as counterexamples, categorized into three representative types: (i) pre-states of inductive counterexamples derived from LLM-proposed invariants and (ii–iii) boundary states derived from correct inductive invariants, where the states themselves either violate (ii) or satisfy (iii) the program’s precondition. Ground-truth labels are established using a state-of-the-art program verifier. We evaluate multiple LLMs under diverse prompting strategies. Our results show that LLMs perform well on the first two types of counterexamples in the benchmark but poorly on the third. Moreover, LLMs are substantially more accurate in classifying spurious counterexamples than genuine ones. These findings offer valuable guidance for future research on LLM-assisted loop invariant inference.
Recognizing defects in source code through deep learning methods has become an important research subject for improving software quality. Although Transformer-based models such as CodeBERT have demonstrated impressive performance improvement in defect prediction tasks, models relying on single-structured input data, such as sequences, have limited ability to capture the code's structural features. Treating code simply as text overlooks essential information such as control dependencies, data dependencies, and syntactic structures inherent in the code. This paper proposes the Heterogeneous Discrete Code Graph (HDCG), which assigns structural information to code tokens from multiple perspectives. We also introduce an improved transformer model FINEGATE that leverages HDCG to guide self-attention. The experiments demonstrate that FINEGATE can effectively predict source code defects and perform fine-grained defect localization.