An action-based formal model for concurrent real-time systems

Action systems are a formalism for representing concurrent behaviours, based on interleaved atomic actions. We show how this model can be used to represent time-consuming, pre-emptible actions with real-time constraints. A development procedure is described which captures the steps programmers typically undertake in the design of real-time multi-tasking systems.     

IPTES: A concurrent engineering approach for real-time software development

The constantly increasing concurrency, complexity, and risks associated with the industrial development of real-time embedded computer systems has been approached in different ways in recent years. In Esprit project no. EP5570, called IPTES, a methodology and a supporting environment to support the Boehm's spiral process are being developed. The prototyping environment will enable the specification, development, and verification of executable system models so that different parts of the system may represent different modeling levels and yet can be executed as a total system. Concurrent engineering problems in connection with multi-supplier, distributed software development are also addressed in the IPTES environment. In the IPTES project the concept of heterogeneous prototyping is proposed as a solution. Each of the development teams may use relatively abstract models of the other parts of the systems as a testbed (environment model) for their own part, yet they can proceed developing their own part full speed by means of advancing the maturity of their part to the next abstraction level(s). The IPTES environment provides a set of tools to help in the process of creating, analyzing, and testing distributed heterogeneous prototypes.     

基于可拓学的自适应软件形式化方法

可拓学的核心是建立灵活变通地应对不确定变化和灵感涌现的适应性模型。讨论引入可拓理论去描述、分析和评价软件系统的自适应性质、范围和程度的可能性。用基元描述软件实体,将软件系统构造成基元网,利用拓展分析、可拓变换和优度评价等定性与定量相结合的方法揭示了自适应软件系统的动态性质,并形成了一种自适应软件形式化方法。     

Towards UML-based formal specifications of component-based real-time software

UML-RT is achieving increasing popularity as a modeling language for real-time applications. Unfortunately UML-RT is not formally well defined and it is not well suited for supporting the specification stage: e.g., it does not provide native constructs to represent time and non-determinism. UML+ is an extension of UML that is formally well defined and suitable for expressing the specifications of real-time systems (e.g., the properties of a UML+ model can be formally verified). However, UML+ does not support design and development. This article addresses the translation of UML+ into UML-RT, thus posing the basis for a development framework where UML+ and UML-RT are used together, in order to remove each other’s limitations. Specifications are written using UML+, they are automatically verified by means of formal methods, and are then converted – through a semi-automatic process – in an equivalent UML-RT model that becomes the starting point for the implementation.     

A formal method to real-time protocol interoperability testing

Interoperability testing is an important technique to ensure the quality of implementations of network communication protocol. In the next generation Internet protocol, real-time applications should be supported effectively. However, time constraints were not considered in the related studies of protocol interoperability testing, so existing interoperability testing methods are difficult to be applied in real-time protocol interoperability testing. In this paper, a formal method to real-time protocol interoperability testing is proposed. Firstly, a formal model CMpTIOA （communicating multi-port timed input output automata） is defined to specify the system under test （SUT） in real-time protocol interoperability testing; based on this model, timed interoperability relation is then defined. In order to check this relation, a test generation method is presented to generate a parameterized test behavior tree from SUT model; a mechanism of executability pre-determination is also integrated in the test generation method to alleviate state space explosion problem to some extent. The proposed theory and method are then applied in interoperability testing of IPv6 neighbor discovery protocol to show the feasibility of this method.     

航空机载嵌入式控制软件需求建模的形式化工程方法

嵌入式控制软件是现代航空飞行器的核心部件之一。构建软件需求的形式化规约精确地刻画人们对软件期望的功能和运行场景,是确保此类安全攸关软件质量的根本途径。在工业界,形式化需求建模的大规模应用尽管有成功的案例,但仍面临众多的困难。其根本性难点在于缺少一种系统化的工程方法来引导工业界软件实践者,从原始需求开始最终完成形式化需求规约,并能确认该规约真实、充分地反映了人们对软件期望的功能。针对上述挑战,提出了一种面向机载控制软件需求建模的形式化工程方法ACSDL-MV,以形式化方法为理论基础,结合软件需求工程的基本原理,引导工程人员从原始需求出发以演化式的过程逐步完成需求规约的构建;定制了航空控制软件的形式化描述语言ACSDL,用以构建形式化规约;为了确认软件需求规约准确、充分地描述了人们对软件期望的功能,该方法给出了基于图形的静态审查和基于模型的动态模拟技术。在航空发动机公司中的实验结果表明,该方法相比传统方法探测到了更多的潜在错误。     

A formal framework for software product lines

ContextA Software Product Line is a set of software systems that are built from a common set of features. These systems are developed in a prescribed way and they can be adapted to fit the needs of customers. Feature models specify the properties of the systems that are meaningful to customers. A semantics that models the feature level has the potential to support the automatic analysis of entire software product lines.ObjectiveThe objective of this paper is to define a formal framework for Software Product Lines. This framework needs to be general enough to provide a formal semantics for existing frameworks like FODA (Feature Oriented Domain Analysis), but also to be easily adaptable to new problems.MethodWe define an algebraic language, called SPLA, to describe Software Product Lines. We provide the semantics for the algebra in three different ways. The approach followed to give the semantics is inspired by the semantics of process algebras. First we define an operational semantics, next a denotational semantics, and finally an axiomatic semantics. We also have defined a representation of the algebra into propositional logic.ResultsWe prove that the three semantics are equivalent. We also show how FODA diagrams can be automatically translated into SPLA. Furthermore, we have developed our tool, called AT, that implements the formal framework presented in this paper. This tool uses a SAT-solver to check the satisfiability of an SPL.ConclusionThis paper defines a general formal framework for software product lines. We have defined three different semantics that are equivalent; this means that depending on the context we can choose the most convenient approach: operational, denotational or axiomatic. The framework is flexible enough because it is closely related to process algebras. Process algebras are a well-known paradigm for which many extensions have been defined.     

实时多任务软件高可靠性测评方法

为了克服传统可靠性测试方法在验证高可靠性指标时测试持续期太长的困难,针对实时多任务软件的特点,提供了一种融基于体系结构的系统可靠性建模、最大熵原理、贝叶斯统计推断为一体的多级高可靠性测评方法。数值仿真表明,该方法在不降低验证测试置信水平的基础上,能有效缩短验证测试持续期。     

rCOS: a formal model-driven engineering method for component-based software

Model-driven architecture (MDA) has become a main stream technology for software-intensive system design. The main engineering principle behind it is that the inherent complexity of software development can only be mastered by building, analyzing and manipulating system models. MDA also deals with system complexity by providing component-based design techniques, allowing independent component design, implementation and deployment, and then system integration and reconfiguration based on component interfaces. The model of a system in any stage is an integration of models of different viewpoints. Therefore, for a model-driven method to be applied effectively, it must provide a body of techniques and an integrated suite of tools for model construction, validation, and transformation. This requires a number of modeling notations for the specification of different concerns and viewpoints of the system. These notations should have formally defined syntaxes and a unified theory of semantics. The underlying theory of the method is needed to underpin the development of tools and correct use of tools in software development, as well as to formally verify and reason about properties of systems in mission-critical applications. The modeling notations, techniques, and tools must be designed so that they can be used seamlessly in supporting development activities and documentation of artifacts in software design processes. This article presents such a method, called the rCOS, focusing on the models of a system at different stages in a software development process, their semantic integration, and how they are constructed, analyzed, transformed, validated, and verified.     

A formal framework for real-time information flow analysis

We view Multi-Level Secure (MLS) real-time systems as systems in which MLS real-time tasks are scheduled and execute, according to a scheduling algorithm employed by the system. From this perspective, we develop a general trace-based framework that can carry out a covert-timing channel analysis of a real-time system. In addition, we propose a set of covert-timing channel free policies: If a system satisfies one of our proposed security policies, we demonstrated that the system can achieve a certain level of real-time information flow security. Finally, we compare the relative strength of the proposed covert-timing channel free security policies and analyze whether each security policy can be regarded as a property (a set of execution sequences).     

A formal framework for on-line software version change

The usual way of installing a new version of a software system is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An online software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. While a number of implementations of online version change systems have been described in the literature, little investigation has been done on its theoretical aspects. We describe a formal framework for studying online software version change. We give a general definition of validity of an online change, show that it is in general undecidable and then develop sufficient conditions for ensuring validity for a procedural language     

A formal process for evaluating COTS software products

A software product evaluation process grounded in mathematics and decision theory can effectively determine product quality and suitability with less risk and at lower cost than conventional methods     

A prototyping language for real-time software

PSDL is a language for describing prototypes of real-time software systems. It is most useful for requirements analysis, feasibility studies, and the design of large embedded systems. PSDL has facilities for recording and enforcing timing constraints, and for modeling the control aspects of real-time systems using nonprocedural control constraints, operator abstractions, and data abstractions. The language has been designed for use with an associated prototyping methodology. PSDL prototypes are executable if supported by a software base containing reusable software components in an underlying programming language (e.g. Ada)     

A formal semantics for concurrent systems with a priority relation

Summary A formal semantics for the COSY path expressions with a priority relation is proposed. It turns out that in the general case the full aspects of behaviours of systems specified by such expressions cannot be modeled by vector firing sequences (a standard semantics for the case without priorities), although vector firing sequences (but without interpretation as causality relations) can correctly be extended for expressions with priorities, and some (but not all) aspects of behaviours, like deadlockfreeness and adaquacy properties, can be defined in terms of vector firing sequences. To describe the behaviours of the COSY priority path expressions entirely, a new semantics, called the multiple firing sequence semantics, is introduced and some its properties are proved.Main part of this work was done during the author's visit at the Institute of Electronic Systems, Aalborg University Centre, Aalborg, DenmarkOn leave from the Warsaw Technical University, Poland     

A formal semantics for debugging synchronous message passing-based concurrent programs

During a human-exoskeleton collaboration, the interaction torque on exoskeleton resulting from the human cannot be clearly determined and conducted by normal physical models. This is because the torque depends not only on direction and orientation of both human-operator and exoskeleton but also on the physical properties of each operator. In this paper, we present our investigations on the relationship between the interaction torques with the dynamic factors of the human-exoskeleton systems using state-of-the-art learning techniques （nonparametric regression techniques） and provide control applications based on the findings. Exper- imental data was collected from various human-operators when they were attached to the designed exoskeleton to perform unconstraint motions with and without control. The results showed that regardless of how the ex- periments were done and which learning method was chosen, the resulting interaction could be best represented by time varying non-linear mappings of the operator＇s angular position, and the exoskeleton＇s angular position, velocity, and acceleration during locomotion. This finding has been applied to advanced controls of the lower exoskeletal robots in order to improve their performance while interacting with human.     

A formal semantics for debugging synchronous message passing-based concurrent programs

In this paper, we propose a semantic framework to debug synchronous message passing-based con- current programs, which are increasingly useful as parallel computing and distributed systems become more and more pervasive. We first design a concurrent programming language model to uniformly represent exist- ing concurrent programming languages. Compared to sequential programming languages, this model contains communication statements, i.e., sending and receiving statements, and a concurrent structure to represent com- munication and concurrency. We then propose a debugging process consisting of a tracing and a locating procedure. The tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating bugs. We provide for the tracing procedure a struc- tural operational semantics to represent synchronous communication and concurrency. The locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure, generates a fix equation, and tries to fix the bug by solving the fix equation. We also propose a structural operational semantics for the locating procedure. We supply two examples to test our proposed operational semantics.     

A comparison of tools for teaching formal software verification

We compare four tools regarding their suitability for teaching formal software verification, namely the Frege Program Prover, the Key system, Perfect Developer, and the Prototype Verification System (PVS). We evaluate them on a suite of small programs, which are typical of courses dealing with Hoare-style verification, weakest preconditions, or dynamic logic. Finally we report our experiences with using Perfect Developer in class.     

形式化技术应用于软件逆工程的实践研究

形式化技术为软件逆工程提供严格和完备的理论基础,但应用于实践的非常少。介绍了一种将形式化方法应用于逆工程的具体实现方法,应用最强后条件的形式化技术对命令语言进行逆工程的具体初步实践,分三阶段对源程序进行抽象以得到严格保证正确性和一致性的软件结构规格说明,并且给出了具体的实现方法。     

LwTool: A data processing toolkit for building a real-time pressure mapping smart textile software system

Pressure mapping smart textile is a new type of sensing modality that transforms the pressure distribution over surfaces into digital ”image” and ”video”, that has rich application scenarios in Human Activity Recognition (HAR), because all human activities are linked with force change over certain surfaces. To speed up its application exploration, we propose a toolkit named LwTool for the data processing, including: (a) a feature library, including 1830 ready-to-use temporal and spatial features, (b) a hierarchical feature selection framework that automatically picks out the best features for a new application from the feature library. As real-time processing capability is important for instant user feedback, we emphasize not only on good recognition result but also on reducing time cost when selecting features. Our library and algorithms are validated on Smart-Toy and Smart-Bedsheet applications, an 89.7% accuracy for Smart-Toy and an 83.8% accuracy for Smart-Bedsheet can be achieved (10-fold cross-validation) using our feature library. Adopting the feature selection algorithm, the processing speed is increased by more than 3 times while maintaining high accuracy for both two applications. We believe our method could be a general and powerful toolkit in building real-time recognition software systems for pressure mapping smart textile.