Verification of bounded Petri nets using integer programming

Model checking based on the causal partial order semantics of Petri nets is an approach widely applied to cope with the state space explosion problem. One of the ways to exploit such a semantics is to consider (finite prefixes of) net unfoldings—themselves a class of acyclic Petri nets—which contain enough information, albeit implicit, to reason about the reachable markings of the original Petri nets. In [19], a verification technique for net unfoldings was proposed, in which deadlock detection was reduced to a mixed integer linear programming problem. In this paper, we present a further development of this approach. The essence of the proposed modifications is to transfer the information about causality and conflicts between the events involved in an unfolding, into a relationship between the corresponding integer variables in the system of linear constraints. Moreover, we present some problem-specific optimisation rules, reducing the search space. To solve other verification problems, such as mutual exclusion or marking reachability and coverability, we adopt Contejean and Devie's algorithm for solving systems of linear constraints over the natural numbers domain and refine it, by taking advantage of the specific properties of systems of linear constraints to be solved. Another contribution of this paper is a method of re-formulating some problems specified in terms of Petri nets as problems defined for their unfoldings. Using this method, we obtain a memory efficient translation of a deadlock detection problem for a safe Petri net into an LP problem. We also propose an on-the-fly deadlock detection method. Experimental results demonstrate that the resulting algorithms can achieve significant speedups.

Distributed Symbolic Bounded Property Checking

In this paper we describe an algorithm for distributed, BDD-based bounded property checking and its implementation in the verification tool SymC. The distributed algorithm verifies larger models and returns results faster than the sequential version.The core algorithm distributes partitions of the state set to computation nodes after reaching a threshold size. The nodes proceed with image computation on the nodes asynchronously. The main scalability problem of this scheme is the overlap of state set partitions. We present static and dynamic overlap reduction techniques.     

Towards the Semantics and Verification of BPEL4WS

In this paper, we discuss the semantics of BPEL4WS language which is a de facto standard for specifying and execution workflow specification for web service composition and orchestration. We propose a language μ-BPEL that includes most primitive and structured activities of BPEL4WS, and define its semantics. As the Timed Automata (TA) is powerful in designing real-time models with multiple clocks and has well developed automatic tool support, we define a map from μ-BPEL into composable TA. Therefore, the properties we want to check can be verified in TA network correspondingly. Furthermore, we prove that the mapping from μ-BPEL to TA is a simulation, which means that the TA network simulates correctly the corresponding μ-BPEL specification. The case study with model checker Uppaal shows that our method is effective, and a Java supporting tool based on Uppaal model checker engine has been developed.     

Verification and validation of Bayesian knowledge-bases

Knowledge-base V&V primarily addresses the question: “Does my knowledge-base contain the right answer and can I arrive at it?” One of the main goals of our work is to properly encapsulate the knowledge representation and allow the expert to work with manageable-sized chunks of the knowledge-base. This work develops a new methodology for the verification and validation of Bayesian knowledge-bases that assists in constructing and testing such knowledge-bases. Assistance takes the form of ensuring that the knowledge is syntactically correct, correcting “imperfect” knowledge, and also identifying when the current knowledge-base is insufficient as well as suggesting ways to resolve this insufficiency. The basis of our approach is the use of probabilistic network models of knowledge. This provides a framework for formally defining and working on the problems of uncertainty in the knowledge-base.

In this paper, we examine the project which is concerned with assisting a human expert to build knowledge-based systems under uncertainty. We focus on how verification and validation are currently achieved in .     

太阳辐射计检定用多维工作台的研制

针对太阳辐射计量仪表进行检定的需要,提出了一种具有四个自由度功能动作的多维检定工作台。工作台在与太阳模拟器联合,可同时对两块待栓仪表的参数误差进行检定。在对太阳高度角和方位角的研究基础上,阐述了工作台旋转机构、升降机构、俯仰机构和转臂机构的设计过程,并对工作台的控制系统进行了说明。测试结果表明多维工作台各级转动误差小于0．05°,由倾角仪和步进电机组成的台面水平控制误差在±10’以内,满足设计指标要求。     

电子政务软件可靠性评测方法初探

电子政务已经成为政府工作自动化和智能化的重要手段。近年来,中国电子政务软件市场获得了前所未有的发展机遇。随着电子政务软件的飞速发展,软件可靠性成为了建设电子政务的重要指标。软件可靠性测试是保证软件可靠性的有效方法。目前,国内对于电子政务的可靠性研究才刚刚起步,其可靠性测试一般都交给第三方机构。分析当前电子政务软件的可靠性测试特点,基于Musa和Nelson两种可靠性模型提出了一种电子政务软件的可靠性评测方法,从可靠性的评估测试和验证测试两方面具体分析阐述了方法的流程,并使用工具实现。最后用具体案例对方法进行了分析说明。     

基于IP核技术的SoC设计

随着集成电路的发展,基于IP(Intellectual Property)核的设计方法成为片上系统设计的必然之选。IP核的建模不仅有助于重复使用而缩短设计周期,还能增强设计的安全保护。因此,迅速将知识产权(IP)硬化并建立精确的实现模型,是设计基于IP核技术的系统芯片(System onChip,SoC)的必要条件。     

SoC功能验证的特点和方法

简要分析了传统集成电路（ASIC）验证方法的特点以及将这些方法应用于系统级芯片（SoC）验证时所面临的问题。在此基础上，论述说明了模块级验证是提高SoC验证效率的基础；而基于随机测试激励的验证方法能够提升SoC的功能验证的覆盖率。另外，还介绍了用于SoC功能验证的关键方法，包括断言和RTL形式验证，Farm，随机化测试激励和功能覆盖等。     

冲击能力验证中可疑数据的分析

阐述了冲击能力验证产生可疑数据的原因，并通过试验作了验证。试验表明，由于使用的JB30B摆锤式冲击试验机在摆锤铅垂时，冲击刀刃到垂直支撑面的距离公差过小，且砧座之间跨距公差过大，造成了金属夏比能力验证在高能量级组数据出现了可疑数据的现象。就冲击试验现行的有关国家标准对这两项指标的规定作了比较与分析，提出了建议。     

Classifying and detecting anomalies in hybrid knowledge-based systems

The increasing need for hybrid Knowledge-Based Systems (KBS) that accommodate more complex applications has led to the need for new verification concerns that are more specific to the hybrid representation using objects and rule-based inference. Traditionally, verification of expert systems has focused solely on rule-based inference systems. Hybrid KBSs present additional verification problems not found in traditional rule-based systems. This paper is an investigation into the anomalies that may be present in a hybrid representation that warrant detection for the verification of the KBS. Many anomalies are due to the interaction of the component parts of the hybrid KBS. For example, subsumption anomalies arise due to an interaction between inheritance of objects and rule-based inference. In this paper, we extend the context of subsumption anomalies and introduce additional types of anomalies that may be present in the KBS. The goal of this research is to make hybrid KBSs more reliable by detecting such anomalies.