Verification and validation of an intelligent tutorial system

This paper presents the results of a verification and validation process for an intelligent system. The system being studied is an Intelligent Tutorial that employs fuzzy logic and multiagent systems. Software engineering techniques were used in the verification process, while the validation exploited both qualitative and quantitative techniques.     

Verification and validation of safety applications based on PLCopen safety function blocks

Functional Safety is a major concern in the design of automation systems today. Many of those systems are realized using Programmable Logic Controllers (PLCs) programmed according to IEC 61131-3. PLCopen - as IEC 61131 user organization - semi-formally specified a set of software function blocks to be used in safety applications according to IEC 61508. In the presented work, formal models in the form of timed automata for the safety function blocks (SFBs) are constructed from the semi-formal specifications. The accordance of the formalized blocks to the specification is verified using model checking. Furthermore, their behaviour is validated against specified test cases by simulation. The resulting verified and validated library of formal models is used to build a formal model of a given safety application - built from SFBs - and to verify and validate its properties.     

Event-driven grammars: relating abstract and concrete levels of visual languages

In this work we introduce event-driven grammars, a kind of graph grammars that are especially suited for visual modelling environments generated by meta-modelling. Rules in these grammars may be triggered by user actions (such as creating, editing or connecting elements) and in their turn may trigger other user-interface events. Their combination with triple graph transformation systems allows constructing and checking the consistency of the abstract syntax graph while the user is building the concrete syntax model, as well as managing the layout of the concrete syntax representation. As an example of these concepts, we show the definition of a modelling environment for UML sequence diagrams. A discussion is also presented of methodological aspects for the generation of environments for visual languages with multiple views, its connection with triple graph grammars, the formalization of the latter in the double pushout approach and its extension with an inheritance concept. This is a revised and extended version of a paper presented at the ICGT’04 conference, see [21].     

基于Agent仿真模型的校核与验证研究

首先对国内外基于Agent仿真模型的校核与验证方面的发展情况进行了述评;然后,提出了一个完整的基于Agent仿真模型的校核与验证框架,该方案中包括表面验证、参数灵敏度分析、模型校准与运行时验证;最后以环境经济政策仿真模型中的校核与验证为例对该框架进行了简单说明。     

Verification and validation of RANS maneuvering simulation of Esso Osaka: effects of drift and rudder angle on forces and moments

The present work covers rigorous verification and validation of a Reynolds averaged Navier–Stokes (RANS) code applied to a maneuvering problem covering the “static rudder” and “pure drift” conditions. The objectives are: (1) to apply the RANS technology together with the Chimera grid technique to compute the hydrodynamic forces acting on the bare hull and the appended hull of the tanker Esso Osaka during simple maneuvers; (2) to provide detailed information about the levels of verification and validation for the integral quantities; (3) to develop a procedure for generation of the systematically refined Chimera grids, which are used for the verification; and (4) to provide information about the trends in the forces and moments when the rudder and drift angles are varied. The flow problem is solved by the general-purpose RANS code CFDSHIP-IOWA, which is run in steady mode. The effect of the free surface is neglected and the two-equation k–ω model, models the turbulence. The verification and validation are performed by means of one of the latest approaches. It takes both the numerical and experimental uncertainties and errors into account, when the method is validated. The verification and validation of the forces and moments show that fair levels of verification and validation are established for most of the considered cases. A brief summary of the levels validation says that the bare hull results are validated at levels from 4.2% to 9.3%. For the appended hull the levels of validation for the rudder forces and the overall forces and moments range from 3.4% to 28.0% and from 6.3% to 37.2% for the “static rudder” and “pure drift” conditions, respectively. Further, it appears that even though validation is not achieved for all the cases, the method is generally capable of capturing the overall behavior of the integral quantities when the rudder and drift angles are varied.     

Propagation of constraints along model transformations using triple graph grammars and borrowed context

Fundamental properties of model transformations based on triple graph grammars (TGGs) have been studied extensively including syntactical correctness, completeness, termination and functional behavior. But up to now, it is an open problem how domain specific properties that are valid for a source model can be preserved along model transformations such that the transformed properties are valid for the derived target model. This question shows up in enterprise modeling. Here, modeling activities related to different domains are handled by different parties, and their models need to be consistent and integrated into one holistic enterprise model later on. So, support for decentralized modeling processes is needed. One technical aspect of the needed support in this case is the (bidirectional) propagation of constraints because that enables one party to understand and check the constraints of another party. Therefore, we analyze in the framework of TGGs how to propagate constraints from a source model to an integrated model and, afterwards, to a target model, such that, whenever the source model satisfies the source constraint, also the integrated and target model satisfy the corresponding integrated and target constraint. In our main new results we show under which conditions this is possible.     

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 .     

Specifying behavioral semantics of UML diagrams through graph transformations

The Unified Modeling Language (UML) has been widely accepted as a standard for modeling software systems from various perspectives. The intuitive notations of UML diagrams greatly improve the communication among developers. However, the lack of a formal semantics makes it difficult to automate analysis and verification. This paper offers a graphical yet formal approach to specifying the behavioral semantics of statechart diagrams using graph transformation techniques. It supports many advanced features of statecharts, such as composite states, firing priority, history, junction, and choice. In our approach, a graph grammar is derived automatically from a state machine to summarize the hierarchy of states. Based on the graph grammar, the execution of a set of non-conflict state transitions is interpreted by a sequence of graph transformations. This facilitates verifying a design model against system requirements. To demonstrate our approach, we present a case study on a toll-gate system.     

Lightweight and static verification of UML executable models

Executable models play a key role in many software development methods by facilitating the (semi)automatic implementation/execution of the software system under development. This is possible because executable models promote a complete and fine-grained specification of the system behaviour. In this context, where models are the basis of the whole development process, the quality of the models has a high impact on the final quality of software systems derived from them. Therefore, the existence of methods to verify the correctness of executable models is crucial. Otherwise, the quality of the executable models (and in turn the quality of the final system generated from them) will be compromised. In this paper a lightweight and static verification method to assess the correctness of executable models is proposed. This method allows us to check whether the operations defined as part of the behavioural model are able to be executed without breaking the integrity of the structural model and returns a meaningful feedback that helps repairing the detected inconsistencies.     

Automating image segmentation verification and validation by learning test oracles

An image segmentation algorithm delineates (an) object(s) of interest in an image. Its output is referred to as a segmentation. Developing these algorithms is a manual, iterative process involving repetitive verification and validation tasks. This process is time-consuming and depends on the availability of experts, who may be a scarce resource (e.g., medical experts). We propose a framework referred to as Image Segmentation Automated Oracle (ISAO) that uses machine learning to construct an oracle, which can then be used to automatically verify the correctness of image segmentations, thus saving substantial resources and making the image segmentation verification and validation task significantly more efficient. The framework also gives informative feedback to the developer as the segmentation algorithm evolves and provides a systematic means of testing different parametric configurations of the algorithm. During the initial learning phase, segmentations from the first few (optimally two) versions of the segmentation algorithm are manually verified by experts. The similarity of successive segmentations of the same images is also measured in various ways. This information is then fed to a machine learning algorithm to construct a classifier that distinguishes between consistent and inconsistent segmentation pairs (as determined by an expert) based on the values of the similarity measures associated with each segmentation pair. Once the accuracy of the classifier is deemed satisfactory to support a consistency determination, the classifier is then used to determine whether the segmentations that are produced by subsequent versions of the algorithm under test, are (in)consistent with already verified segmentations from previous versions. This information is then used to automatically draw conclusions about the correctness of the segmentations. We have successfully applied this approach to 3D segmentations of the cardiac left ventricle obtained from CT scans and have obtained promising results (accuracies of 95%). Even though more experiments are needed to quantify the effectiveness of the approach in real-world applications, ISAO shows promise in increasing the quality and testing efficiency of image segmentation algorithms.     

复杂工程建模和模拟的验证与确认

综述国内外建模和模拟(Modeling and Simulation,MS)的验证与确认(Verification and Validation,VV)的相关概念、术语、规范、置信度评估方法和应用等方面的发展和研究进展,概括MS的VV中的几个关键问题,构建复杂工程MS的VV的知识指南,为MS的VV技术真正走向应用提供参考.     

Early verification and validation of mission critical systems

Complex software and systems are pervasive in today’s world. In a growing number of fields they come to play a critical role. In order to provide a high assurance level, verification and validation (V&V) should be considered early in the development process. This paper shows how this can be achieved based on a goal-oriented requirements engineering framework which combines complementary semi-formal and formal notations. This allows the analyst to formalize only when and where needed and also preserves optimal communication with stakeholders and developers. For the industrial application of the methodology, a supporting toolbox was developed. It consist of a number of tightly integrated tools for performing V&V tasks at requirements level. This is achieved through the use of (1) a roundtrip mapping between the requirements language and the specific formal languages used in the underlying formal tools (such as SAT or constraint solvers) and (2) graphical views using domain-based representations. This paper will focus on two major and representative tools: the Refinement Checker (about verification) and the Animator (about validation).     

系统建模与仿真应用的校验、确认与验收

以美国国防部（DoD）近年来对建模与仿真（M＆S）应用所做的校验、确认与验收（VV＆A）研究工作为基础,介绍了关于M＆S应用的校验、确认、验收、鉴定等概念;结合软件工程的3P指标提出一种通用的形式化表示的M＆S应用VV＆A框架;讨论了M＆S应用可信度指标的层次化体系的建立与评价方法,引入了Kiviat图;最后介绍了一个用于M＆S可信度评价的计算机软件平台——EE（Evaluation Environment,评价环境）。     

Generic and reflective graph transformations for checking and enforcement of modeling guidelines

In the automotive industry, the model driven development of software, today considered as the standard paradigm, is generally based on the use of the tool MATLAB Simulink/Stateflow. To increase the quality, the reliability, and the efficiency of the models and the generated code, checking and elimination of detected guideline violations defined in huge catalogs has become an essential task in the development process. It represents such a tremendous amount of boring work that it must necessarily be automated. In the past we have shown that graph transformation tools like Fujaba/MOFLON allow for the specification of single modeling guidelines on a very high level of abstraction and that guideline checking tools can be generated from these specifications easily. Unfortunately, graph transformation languages do not offer appropriate concepts for reuse of specification fragments—a MUST, when we deal with hundreds of guidelines. As a consequence we present an extension of MOFLON that supports the definition of generic rewrite rules and combines them with the reflective programming mechanisms of Java and the model repository interface standard Java Metadata Interface (JMI).     

联邦开发过程中的校核、验证与确认（VV＆A）

对联邦的VV＆A不仅能够使每一步的工作得到跟踪和衡量,还使每一步能够减少多余的工作量,巩固需要加强的工作,明确开发人员的角色和职责,从而使人力、时间、资金等资源得到更加有效率的利用,仿真的结果变得更加可预测和准确,在很大程度上减少了编程的风险.联邦成员描述了仿真模型的各对象类、交互类、相关的属性、参数等信息,而联邦是各联邦成员的有机集成,构成具有特定功能的仿真系统.因此,联邦成员的正确性是联邦正确性的前提,决定了仿真系统的成败.在VV＆A的过程中,最好采用一些自动化工具以便于工作,同时要根据具体仿真系统的实际情况来确定VV＆A所需要作的工作.     

A meta-heuristic solution for automated refutation of complex software systems specified through graph transformations

One of the best approaches for verifying software systems (especially safety critical systems) is the model checking in which all reachable states are generated from an initial state. All of these states are searched for errors or desirable patterns. However, the drawback for many real and complex systems is the state space explosion in which model checking cannot generate all the possible states. In this situation, designers can use refutation to check refusing a property rather than proving it. In refutation, it is very important to handle the state space for finding errors efficiently. In this paper, we propose an efficient solution to implement refutation in complex systems modeled by graph transformation. Since meta-heuristic algorithms are efficient solutions for searching in the problems with very large state spaces, we use them to find errors (e.g., deadlocks) in systems which cannot be verified through existing model checking approaches due to the state space explosion. To do so, we employ a Particle Swarm Optimization (PSO) algorithm to consider only a subset of states (called population) in each step of the algorithm. To increase the accuracy, we propose a hybrid algorithm using PSO and Gravitational Search Algorithm (GSA). The proposed approach is implemented in GROOVE, a toolset for designing and model checking graph transformation systems. The experiments show improved results in terms of accuracy, speed and memory usage in comparison with other existing approaches.     

A sound and complete theory of graph transformations for service programming with sessions and pipelines

Graph transformation techniques, the Double-Pushout (DPO) approach in particular, have been successfully applied in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this paper, we propose a theory of graph transformations for service programming with sophisticated features such as sessions and pipelines. Through graph representation of CaSPiS, a recently proposed process calculus, we show how graph transformations can cope with advanced features of service-oriented computing, such as several logical notions of scoping together with the interplay between linking and containment. We first exploit a graph algebra and set up a graph model that supports graph transformations in the DPO approach. Then, we show how to represent CaSPiS processes as hierarchical graphs in the graph model and their behaviors as graph transformation rules. Finally, we provide the soundness and completeness results of these rules with respect to the reduction semantics of CaSPiS.     

The VALU3S ECSEL project: Verification and validation of automated systems safety and security

Manufacturers of automated systems and their components have been allocating an enormous amount of time and effort in R&D activities, which led to the availability of prototypes demonstrating new capabilities as well as the introduction of such systems to the market within different domains. Manufacturers need to make sure that the systems function in the intended way and according to specifications. This is not a trivial task as system complexity rises dramatically the more integrated and interconnected these systems become with the addition of automated functionality and features to them. This effort translates into an overhead on the V&V (verification and validation) process making it time-consuming and costly. In this paper, we present VALU3S, an ECSEL JU (joint undertaking) project that aims to evaluate the state-of-the-art V&V methods and tools, and design a multi-domain framework to create a clear structure around the components and elements needed to conduct the V&V process. The main expected benefit of the framework is to reduce time and cost needed to verify and validate automated systems with respect to safety, cyber-security, and privacy requirements. This is done through identification and classification of evaluation methods, tools, environments and concepts for V&V of automated systems with respect to the mentioned requirements. VALU3S will provide guidelines to the V&V community including engineers and researchers on how the V&V of automated systems could be improved considering the cost, time and effort of conducting V&V processes. To this end, VALU3S brings together a consortium with partners from 10 different countries, amounting to a mix of 25 industrial partners, 6 leading research institutes, and 10 universities to reach the project goal.     

Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference

In this paper we will present a graph-transformation based method for the verification of heterogeneous first order logic (FOL) and Euler/Venn proofs. In previous work, it has been shown that a special collection of directed acyclic graphs (DAGs) can be used interchangeably with Euler/Venn diagrams in reasoning processes. Thus, proofs which include Euler/Venn diagrams can be thought of as proofs with DAGs where steps involving only Euler/Venn diagrams can be treated as particular DAG transformations. Here we will show how the characterization of these manipulations can be used to verify Euler/Venn proofs. Also, a method for verifying the use of heterogeneous Euler/Venn and FOL reasoning rules will be presented that is also based upon DAG transformations .     

建模与仿真的校核与验证技术综述

系统建模与仿真是人类认识世界的三大方法之一。随着系统仿真技术的不断发展,建模与仿真在军事、经济等方面发挥着日益重要的作用。与此同时,人们也逐步认识到建模与仿真的可信度问题,对模型与仿真正确性和可信度的要求也越来越高。校核与验证（V＆V）技术是系统仿真技术的关键技术之一,用于评价模型与仿真的可信度。首先介绍建模与仿真（M＆S）的VV＆A的基本概念和重要作用,然后详细介绍非正规的、静态的和正规的校核与验证技术并分析各自的特点,最后论述M＆S生命周期中V＆V活动的实施及V＆V技术的适用范围。