Efficiently solving quantified bit-vector formulas

In recent years, bit-precise reasoning has gained importance in hardware and software verification. Of renewed interest is the use of symbolic reasoning for synthesising loop invariants, ranking functions, or whole program fragments and hardware circuits. Solvers for the quantifier-free fragment of bit-vector logic exist and often rely on SAT solvers for efficiency. However, many techniques require quantifiers in bit-vector formulas to avoid an exponential blow-up during construction. Solvers for quantified formulas usually flatten the input to obtain a quantified Boolean formula, losing much of the word-level information in the formula. We present a new approach based on a set of effective word-level simplifications that are traditionally employed in automated theorem proving, heuristic quantifier instantiation methods used in SMT solvers, and model finding techniques based on skeletons/templates. Experimental results on two different types of benchmarks indicate that our method outperforms the traditional flattening approach by multiple orders of magnitude of runtime.     

Symbolic Techniques in Satisfiability Solving

Recent work has shown how to use binary decision diagrams for satisfiability solving. The idea of this approach, which we call symbolic quantifier elimination, is to view an instance of propositional satisfiability as an existentially quantified proposition formula. Satisfiability solving then amounts to quantifier elimination; once all quantifiers have been eliminated, we are left with either 1 or 0. Our goal in this work is to study the effectiveness of symbolic quantifier elimination as an approach to satisfiability solving. To that end, we conduct a direct comparison with the DPLL-based ZChaff, as well as evaluate a variety of optimization techniques for the symbolic approach. In comparing the symbolic approach to ZChaff, we evaluate scalability across a variety of classes of formulas. We find that no approach dominates across all classes. While ZChaff dominates for many classes of formulas, the symbolic approach is superior for other classes of formulas. Once we have demonstrated the viability of the symbolic approach, we focus on optimization techniques for this approach. We study techniques from constraint satisfaction for finding a good plan for performing the symbolic operations of conjunction and of existential quantification. We also study various variable-ordering heuristics, finding that while no heuristic seems to dominate across all classes of formulas, the maximum-cardinality search heuristic seems to offer the best overall performance. ★A preliminary version of the paper was presented in SAT'04. Supported in part by NSF grants CCR-9988322, CCR-0124077, CCR-0311326, IIS-9908435, IIS-9978135, EIA-0086264, ANI-0216467, and by BSF grant 9800096.     

LTL satisfiability checking

We report here on an experimental investigation of LTL satisfiability checking via a reduction to model checking. By using large LTL formulas, we offer challenging model-checking benchmarks to both explicit and symbolic model checkers. For symbolic model checking, we use CadenceSMV, NuSMV, and SAL-SMC. For explicit model checking, we use SPIN as the search engine, and we test essentially all publicly available LTL translation tools. Our experiments result in two major findings. First, most LTL translation tools are research prototypes and cannot be considered industrial quality tools. Second, when it comes to LTL satisfiability checking, the symbolic approach is clearly superior to the explicit approach.     

印刷体数学公式重构技术的研究

数学公式重构是公式识别的重要环节,目前相关的研究还很欠缺.基于MathML提出了一种印刷体数学公式重构的方法.在已实现的公式符号识别与结构分析程序所生成的公式关系树基础上,将公式关系树重构为MathML文档,并设计公式编辑器,实现了公式的再编辑和重用.实验表明,这种重构方法对印刷体数学公式具有较好的适应性和较高的准确率.     

Properties of a predicate transformer of the VRS system

Models specified in the language of basic protocols are considered. These models are attribute transition systems, and their states are defined by formulas of multisort first-order predicate calculus over system attributes. Attributes of simple numeric and symbolic types, functional types, and queues are allowed. Assignment operators, queue update operators, and arbitrary formulas are used in postconditions of basic protocols. To pass from one state to another, a predicate transformer is constructed as a function of formula transformation. The following main property of the predicate transformer is proved: it calculates the strongest postcondition for symbolic states.     

包含依赖输入分支程序的符号化WCET分析

符号化WCET(worst-case execution time)分析是用符号表达式表示任务的最大执行时间:表达式中包含了参数.通过在运行时刻快速确定表达式值,符号化WCET分析可以更精确地估算WCET.提出了一种针对其分支直接依赖于输入数据的程序的符号化WCET分析方法.首先对Blieberger方法进行扩充,使得WCET符号表达式能够表达依赖输入分支,然后利用程序的控制依赖图对符号表达式进行化简,从而产生带条件的WCET符号表达式,即不同的条件对应不同的符号表达式.与已有方法不同,符号化WCET公式直接依赖于输入参数,使得运行时的WCET估算更加简单直接.     

Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK)

In this article, I focus on the robustness of geometric programs (e.g., Delaunay triangulation, intersection between surfacic or volumetric meshes, Voronoi-based meshing …) w.r.t. numerical degeneracies. Some of these geometric programs require “exotic” predicates, not available in standard libraries (e.g., J.-R. Shewchuk’s implementation and CGAL). I propose a complete methodology and a sample Open Source implementation of a toolset (PCK: Predicate Construction Kit) that makes it reasonably easy to design geometric programs free of numerical errors. The C++ code of the predicates is automatically generated from its formula, written in a simple specification language. Robustness is obtained through a combination of arithmetic filters, expansion arithmetics and symbolic perturbation.As an example of my approach, I give the formulas and PCK source-code for the 4 predicates used to compute the intersection between a 3d Voronoi diagram and a tetrahedral mesh, as well as symbolic perturbations that provably escapes the corner cases. This allows to robustly compute the intersection between a Voronoi diagram and a triangle mesh, or the intersection between a Voronoi diagram and a tetrahedral mesh. Such an algorithm may have several applications, including surface and volume meshing based on Lloyd relaxation.     

Scaling symbolic execution using staged analysis

Recent advances in constraint solving technology and raw computation power have led to a substantial increase in the effectiveness of techniques based on symbolic execution for systematic bug finding. However, scaling symbolic execution remains a challenging problem. We present a novel approach to increase the efficiency of symbolic execution for systematic testing of object-oriented programs. Our insight is that we can apply symbolic execution in stages, rather than the traditional approach of applying it all at once, to compute abstract symbolic inputs that can later be shared across different methods to test them systematically. For example, a class invariant can provide the basis of generating abstract symbolic tests that are then used to symbolically execute several methods that require their inputs to satisfy the invariant. We present an experimental evaluation to compare our approach against KLEE, a state-of-the-art implementation of symbolic execution. Results show that our approach enables significant savings in the cost of systematic testing using symbolic execution.     

Strategies for scalable symbolic execution-driven test generation for programs

With the advent of advanced program analysis and constraint solving techniques,several test generation tools use variants of symbolic execution.Symbolic techniques have been shown to be very effective in path-based test generation;however,they fail to scale to large programs due to the exponential number of paths to be explored.In this paper,we focus on tackling this path explosion problem and propose search strategies to achieve quick branch coverage under symbolic execution,while exploring only a fraction...     

一个统一的程序验证框架

本文提出了一个简单的方法，其中程序和其性质都由一个逻辑：时序逻辑中的公式表示．文中给出了一个程序的转换模块的定义，提出了时序执行语义的概念．它是一个时序公式，精确地说明了一个程序．将时序逻辑作为规范语言，程序正确性就意味着说明程序的公式蕴含说明性质的公式，其中蕴含即为一般的逻辑蕴含．因此，本文的方法为并发程序的规范及验证提供了一个统一的框架．它允许充分利用现有的用于证明并发系统时序性质的各种完全证明系统．一个缓冲系统的简单例子用来说明本文的方法．此例子表明本文的方法是可行的.     

控制系统校正环节优化设计的计算机辅助分析

结合共轭梯度法,借助于MATLAB软件,提出一种控制系统校正环节优化设计的新方法.该方法利用了MAT-LAB软件中的符号数学工具箱、控制系统工具箱和优化设计工具箱,使设计简单、快捷,提高了编程效率.     

基于路径分析和信息熵的错误定位方法

软件错误定位是一项耗时又费力的工作,因此如何提高软件错误定位的自动化程度一直以来都是软件工程领域研究的热点.现有的基于频谱的错误定位方法很少利用程序的上下文信息,而程序的上下文信息对错误定位至关重要.针对此问题,本文提出了一种基于路径分析和信息熵的错误定位方法FLPI.该方法在基于频谱信息技术的基础上,通过对所有执行路径中的数据依赖关系进行分析来引入执行上下文信息,同时利用信息熵理论将测试事件信息引入到可疑语句的怀疑度计算公式中,以提高错误定位的精度和效率.为了评价该方法的有效性,基于一组基准程序和开源程序进行实验验证.实验结果表明,本文所提方法FLPI能够有效地提高错误定位的精度和效率.     

Symbolic Communication Set Generation for Irregular Parallel Applications

Communication set generation significantly influences the performance of parallel programs. However, studies seldom give attention to the problem of communication set generation for irregular applications. In this paper, we propose communication optimization techniques for the situation of irregular array references in nested loops. In our methods, the local array distribution schemes are determined so that the total number of communication messages is minimized. Then, we explain how to support communication set generation at compile-time by introducing some symbolic analysis techniques. In our symbolic analysis, symbolic solutions of a set of symbolic expression are obtained by using certain restrictions. We introduce symbolic analysis algorithms to obtain the solutions in terms of a set of equalities and inequalities. Finally, experimental results on a parallel computer CM-5 are presented to validate our approach.     

Computer generation of robot dynamics equations and the related issues

Two programs have been developed using the computer algebra system REDUCE to generate the dynamics equations of motion for robot manipulators. One of these programs is based on a Lagrange formulation and the other utilizes a recursive Newton-Euler formulation. Both programs produce equivalent scalar symbolic expressions for the generalized actuator forces, but the program based on the recursive Newton-Euler formulation is more efficient for the generation of equations. These programs have been used to generate the dynamics equations of manipulators with as many as six degrees of freedom. The efficiency of computing forces using the generated scalar symbolic expressions is compared with the efficiency of a numerical algorithm (implemented in FORTRAN '77) based on the recursive Newton-Euler formulation. Force computation by the method of symbolic equations is shown to be more efficient than the numerical recursive Newton-Euler algorithm. The technique of symbolic equations is also better adapted to multi-CPU processing.     

Computing with Impure Numbers: Automatic Consistency Checking and Units Conversion Using Computer Algebra

This note shows how computer-algebra systems may be used to include symbolic physical units in computer calculations, with automatic detection of dimensionally-inhomogeneous formulas and automatic conversion of inconsistent units in a dimensionally-homogeneous formula. Inhomogeneity errors are a prevalent type that is undetected in traditional programming languages, and the user is relieved of the tedious, error-prone units-conversion process.     

Symbolic Cache Analysis for Real-Time Systems

Caches impose a major problem for predicting execution times of real-time systems since the cache behavior depends on the history of previous memory references. Too pessimistic assumptions on cache hits can obtain worst-case execution time estimates that are prohibitive for real-time systems. This paper presents a novel approach for deriving a highly accurate analytical cache hit function for C-programs at compile-time based on the assumption that no external cache interference (e.g. process dispatching or DMA activity) occurs. First, a symbolic tracefile of an instrumented C-program is generated based on symbolic evaluation, which is a static technique to determine the dynamic behavior of programs. All memory references of a program are described by symbolic expressions and recurrences and stored in chronological order in the symbolic tracefile. Second, a cache hit function for several cache architectures is computed based on a cache evaluation technique. Our approach goes beyond previous work by precisely modelling program control flow and program unknowns, modelling large classes of cache architectures, and providing very accurate cache hit predictions. Examples for the SPARC architecture are used to illustrate the accuracy and effectiveness of our symbolic cache prediction.     

A symbolic manipulator for automated verification of reactive systems with heterogeneous data types

In this paper, we present the design and implementation of the Composite Symbolic Library, a symbolic manipulator for model checking systems with heterogeneous data types. Our tool provides a common interface for different symbolic representations, such as BDDs, for representing Boolean logic formulas and polyhedral representations for linear arithmetic formulas. Based on this common interface, these data structures are combined using a disjunctive composite representation. We propose several heuristics for efficient manipulation of this composite representation and present experimental results that demonstrate their performance. We used an object-oriented design to implement the Composite Symbolic Library. We imported the CUDD library (a BDD library) and the Omega Library (a linear arithmetic constraint manipulator that uses polyhedral representations) to our tool by writing wrappers around them which conform to our symbolic representation interface. Our tool supports polymorphic verification procedures which dynamically select symbolic representations based on the input specification. Our symbolic representation library can be used as an interface between different symbolic libraries, model checkers, and specification languages. We expect our tool to be useful in integrating different tools and techniques for symbolic model checking, and in comparing their performance.     

Mathematical programming models and algorithms for engineering design optimization

Mathematical programming provides general tools for engineering design optimization. We present numerical models for simultaneous analysis and design optimization (SAND) and multidisciplinary design optimization (MDO) represented by mathematical programs. These models are solved with numerical techniques based on the feasible arc interior point algorithm (FAIPA) for nonlinear constrained optimization. Even if MDO is a very large optimization problem, our approach reduces considerably the computer effort. Several tools for very large problems are also presented. The present approach is very strong and efficient for real industrial applications and can easily interact with existing simulation engineering codes.