A simplification of a real‐time verification problem

We revisit the problem of real‐time verification with dense‐time dynamics using timeout and calendar‐based models and simplify this to a finite state verification problem. We introduce a specification formalism for these models and capture their behaviour in terms of semantics of timed transition systems. We discuss a technique, which reduces the problem of verification of qualitative temporal properties on infinite state space of a large fragment of these timeout and calender‐based transition systems into that on clock‐less finite state models through a two‐step process comprising of digitization and finitary reduction. This technique enables us to verify safety invariants for real‐time systems using finite state model checking avoiding the complexity of infinite state (bounded) model checking and scale up models without applying techniques from induction‐based proof methodology. In the same manner, we verify timeliness properties. Moreover, we can verify liveness for real‐time systems, which are not possible by using induction with infinite state model checkers. Copyright © 2016 John Wiley & Sons, Ltd.     

Worst‐case execution time analysis for a Java processor

In this paper, we propose a solution for a worst‐case execution time (WCET) analyzable Java system: a combination of a time‐predictable Java processor and a tool that performs WCET analysis at Java bytecode level. We present a Java processor, called JOP, designed for time‐predictable execution of real‐time tasks. The execution time of bytecodes, the instructions of the Java virtual machine, is known to cycle accuracy for JOP. Therefore, JOP simplifies the low‐level WCET analysis. A method cache, which fills whole Java methods into the cache, simplifies cache analysis. The WCET analysis tool is based on integer linear programming. The tool performs the low‐level analysis at the bytecode level and integrates the method cache analysis. An integrated data‐flow analysis performs receiver‐type analysis for dynamic method dispatches and loop‐bound analysis. Furthermore, a model checking approach to WCET analysis is presented where the method cache can be exactly simulated. The combination of the time‐predictable Java processor and the WCET analysis tool is evaluated with standard WCET benchmarks and three real‐time applications. The WCET friendly architecture of JOP and the integrated method cache analysis yield tight WCET bounds. Comparing the exact, but expensive, model checking‐based analysis of the method cache with the static approach demonstrates that the static approximation of the method cache is sufficiently tight for practical purposes. Copyright © 2010 John Wiley & Sons, Ltd.     

Evolutionary algorithms for the multi‐objective test data generation problem

Automatic test data generation is a very popular domain in the field of search‐based software engineering. Traditionally, the main goal has been to maximize coverage. However, other objectives can be defined, such as the oracle cost, which is the cost of executing the entire test suite and the cost of checking the system behavior. Indeed, in very large software systems, the cost spent to test the system can be an issue, and then it makes sense by considering two conflicting objectives: maximizing the coverage and minimizing the oracle cost. This is what we did in this paper. We mainly compared two approaches to deal with the multi‐objective test data generation problem: a direct multi‐objective approach and a combination of a mono‐objective algorithm together with multi‐objective test case selection optimization. Concretely, in this work, we used four state‐of‐the‐art multi‐objective algorithms and two mono‐objective evolutionary algorithms followed by a multi‐objective test case selection based on Pareto efficiency. The experimental analysis compares these techniques on two different benchmarks. The first one is composed of 800 Java programs created through a program generator. The second benchmark is composed of 13 real programs extracted from the literature. In the direct multi‐objective approach, the results indicate that the oracle cost can be properly optimized; however, the full branch coverage of the system poses a great challenge. Regarding the mono‐objective algorithms, although they need a second phase of test case selection for reducing the oracle cost, they are very effective in maximizing the branch coverage. Copyright © 2011 John Wiley & Sons, Ltd.     

Automatic test case generation from Simulink/Stateflow models using model checking

Model‐based test generation techniques based on random input generation and guided simulation do not satisfy the demands of high test coverage and completeness guarantees as required by safety‐critical applications. Recently, test generation techniques based on model checking have been reported to bridge this gap. To evaluate the effectiveness of these techniques, an in‐house tool suite, AutoMOTGen, has been developed for Simulink/Stateflow and applied on real‐life case studies at General Motors. This paper outlines the test generation methodology of AutoMOTGen and gives a comparative study with a commercial, primarily random input‐based, test generation tool on the same set of examples. The results indicate that in terms of coverage, model checking‐based techniques complement the random input‐based techniques. In addition, they provide proofs for unreachability that can aid in debugging the models. Therefore, it is recommended that model checking‐based tools be utilized to complement and enhance the effectiveness of model‐based testing methods in safety‐critical systems engineering. Copyright © 2013 John Wiley & Sons, Ltd.     

Exploiting Object Escape and Locking Information in Partial-Order Reductions for Concurrent Object-Oriented Programs

Explicit-state model checking tools often incorporate partial-order reductions to reduce the number of system states explored (and thus the time and memory required) for verification. As model checking techniques are scaled up to software systems, it is important to develop and assess partial-order reduction strategies that are effective for addressing the complex structures found in software and for reducing the tremendous cost of model checking software systems. In this paper, we consider a number of reduction strategies for model checking concurrent object-oriented software. We investigate a range of techniques that have been proposed in the literature, improve on those in several ways, and develop five novel reduction techniques that advance the state of the art in partial-order reduction for concurrent object-oriented systems. These reduction strategies are based on (a) detecting heap objects that are thread-local (i.e., can be accessed by a single thread) and (b) exploiting information about patterns of lock-acquisition and release in a program (building on previous work). We present empirical results that demonstrate upwards of a hundred fold reduction in both space and time over existing approaches to model checking concurrent Java programs. In addition to validating their effectiveness, we prove that the reductions preserve LTL_?X properties and describe an implementation architecture that allows them to be easily incorporated into existing explicit-state software model checkers.     

Formal methods applied to high‐performance computing software design: a case study of MPI one‐sided communication‐based locking

There is a growing need to address the complexity of verifying the numerous concurrent protocols employed in the high‐performance computing software. Today's approaches for verification consist of testing detailed implementations of these protocols. Unfortunately, this approach can seldom show the absence of bugs, and often results in serious bugs escaping into the deployed software. An approach called Model Checking has been demonstrated to be eminently helpful in debugging these protocols early in the software life cycle by offering the ability to represent and exhaustively analyze simplified formal protocol models. The effectiveness of model checking has yet to be adequately demonstrated in high‐performance computing. This paper presents a case study of a concurrent protocol that was thought to be sufficiently well tested, but proved to contain two very non‐obvious deadlocks in them. These bugs were automatically detected through model checking. The protocol models in which these bugs were detected were also easy to create. Recent work in our group demonstrates that even this tedium of model creation can be eliminated by employing dynamic source‐code‐level analysis methods. Our case study comes from the important domain of Message Passing Interface (MPI)‐based programming, which is universally employed for simulating and predicting anything from the structural integrity of combustion chambers to the path of hurricanes. We argue that model checking must be taught as well as used widely within HPC, given this and similar success stories. Copyright © 2009 John Wiley & Sons, Ltd.     

Flow‐sensitive runtime estimation: an enhanced hot spot detection heuristics for embedded Java just‐in‐time compilers

Java just‐in‐time compilers often compile only hot methods because the compilation overhead is a part of the running time. This requires precise and efficient hot spot detection, which includes distinguishing hot methods from cold ones, detecting them as early as possible, and paying a small detection overhead. Hot spot detection is especially important in embedded applications because they show more of a start‐up phase behavior of a regular application where methods are not executed heavily, so the hot methods are not definite. Because a long‐running method is likely to be a hot method, we can detect a hot method by measuring its running time during interpretation. However, precise measurement of the running time during execution is too expensive, especially in embedded systems, so many counter‐based heuristics have been proposed to estimate it such as Oracle's HotSpot heuristic. One problem is that although the overhead of these heuristics is low, they do not estimate the running time precisely, which may lead to imprecise hot spot detection.This paper proposes a new hot spot detection heuristic called flow‐sensitive runtime estimation, which can estimate the running time more precisely than others with a relatively low overhead. It only counts important bytecode instructions dynamically, but it can obtain the precise count of all interpreted bytecode instructions with a simple arithmetic calculation. We also propose a static analysis technique to predict those hot methods which spends a huge execution time once invoked, so as to compile them at their first invocation. Our experimental results show that these techniques can improve the performance by as much as an average of 7.4% compared with the HotSpot heuristic for the benchmarks when they run once, which is often regarded as showing the start‐up phase behavior. Even for real embedded Java applications such as the digital TV Java Xlet applications, our techniques can improve the user response time by an average of 7.1%. Copyright © 2015 John Wiley & Sons, Ltd.     

A development methodology for embedded systems based on RT-DEVS

This work is concerned with modelling, analysis and implementation of embedded control systems using RT-DEVS, i.e. a specialization of classic discrete event system specification (DEVS) for real-time. RT-DEVS favours model continuity, i.e. the possibility of using the same model for property analysis (by simulation or model checking) and for real time execution. Special case tools are reported in the literature for RT-DEVS model analysis and design. In this work, temporal analysis of a model exploits a translation in Uppaal timed automata for exhaustive verification. For large models a simulator was realized in Java which directly stems from RT-DEVS operational semantics. The same concerns are at the basis of a real-time executive. The paper describes the proposed RT-DEVS development methodology and clarifies its implementation status. The approach is demonstrated by applying it to an embedded system example which is analyzed through model checking and implemented in Java. Finally, research directions which deserve further work are indicated.     

Enhancing OSGi with real‐time Java support

OSGi was designed with embedded systems in mind, its current support is insufficient for coping with one main characteristic of many embedded systems: real‐time performance. This article analyzes different key issues in providing OSGi with real‐time Java performance covering motivational issues, and different integration ways and challenges stemming from the integration. It also contributes a general framework for introducing real‐time performance in OSGi, which is called the real‐time for OSGi framework. The framework uses real‐time Java virtual machines and the real‐time specification for Java. The adoption of this framework allows cyber‐physical systems to experience real‐time Java performance in their applications. The framework introduces several integration levels for OSGi and real‐time specification for Java, and specific real‐time OSGi services. An empirical implementation was carried out using standard software, which was extended with the new defined services. Copyright © 2012 John Wiley & Sons, Ltd.     

程序模型检查器综述

模型检查实际程序设计语言编写的程序是近年来程序验证领域的研究热点之一,出现了一批针对C,C++或Java语言的程序模型检查器原型.总结了程序模型检查中的主要问题及相关技术,以是否使用中间建模语言为标准,对现有程序模型检查器进行了分类,并具体地介绍了一些代表性工具中的模型获取及化简技术,最后展望了程序模型检查器未来的研究方向.     

Grammatical and context‐sensitive error correction using a statistical machine translation framework

Producing electronic rather than paper documents has considerable benefits such as easier organizing and data management. Therefore, existence of automatic writing assistance tools such as spell and grammar checker/correctors can increase the quality of electronic texts by removing noise and correcting the erroneous sentences. Different kinds of errors in a text can be categorized into spelling, grammatical and real‐word errors. In this article, we present a language‐independent approach based on a statistical machine translation framework to develop a proofreading tool, which detects grammatical errors as well as context‐sensitive spelling mistakes (real‐word errors). A hybrid model for grammar checking is suggested by combining the mentioned approach with an existing rule‐based grammar checker. Experimental results on both English and Persian languages indicate that the proposed statistical method and the rule‐based grammar checker are complementary in detecting and correcting syntactic errors. The results of the hybrid grammar checker, applied to some English texts, show an improvement of about 24% with respect to the recall metric with almost similar value for precision. Experiments on real‐world data set show that state‐of‐the‐art results are achieved for grammar checking and context‐sensitive spell checking for Persian language. Copyright © 2012 John Wiley & Sons, Ltd.     

An enhanced role model for alleviating the role‐binding anomaly

Roles and role models have received much attention as useful concepts for developing highly reusable and dynamically evolvable systems. Role models belong to the category of collaboration‐based development techniques, but most of the existing approaches to role models do not explicitly incorporate the core principle of collaboration‐based developments as an essential property of their primary design goals. Consequently, the existing approaches still suffer from a problematic phenomenon that the structural and behavioral constraints defined in a role system can be violated during the role‐binding stage. We call such a problematic phenomenon the role‐binding anomaly. In order to alleviate the role‐binding anomaly, we propose an enhanced role model, in which all role instances and core objects can exist by themselves, namely, they can be developed, executed, and tested independently. Roles and core classes can be bound to each other at the instance level. In addition, the role system describes and encapsulates the behavior for dynamic reconfigurations among role instances. The enhanced role model is designed so as to be meaningful with respect to software engineering principles, rather than dynamic evolution. It also facilitates role model implementation using general programming languages (i.e. not supporting dynamic specialization) such as Java. To illustrate how the proposed role model makes such benefits, we develop a set of Java classes necessary for implementing the enhanced role model in the form of a Java package role, and present a simplified automatic teller machine system as an example application. Copyright © 2002 John Wiley & Sons, Ltd.     

Integration of control system design and implementation over the internet using the Jini technology

This paper describes an approach for the integration of control system software design, testing, and implementation over the Internet using the Java and Jini technologies. Process models and control systems are remotely designed and tested in a virtual laboratory (also called the virtual world), and then implemented in a physical plant (also called the real world) through an integrated environment. Although control system and process model designers and real‐site operators are geographically dispersed they work together as a team over the Internet to provide the maintenance support to all the authorized industrial processes. As a consequence, time and money can both be saved because there is no need for an expert of the control software supplier to travel to the site of the real plant and conduct on‐site implementation. A generic control system life cycle model is presented first in this paper. Then three enabling technologies including Java, Jini and WWW are briefly introduced. Taking advantage of the Java, Jini and WWW technologies, an Internet‐based general infrastructure is proposed to remotely facilitate process modelling, control system design, simulation, validation and on‐site implementation. An integrated environment is established to implement the infrastructure. A water tank with a liquid level control system is refereed as a case study to illustrate how the prototype of the integrated environment works over the Internet. Further work and the conclusions are given at the end. Copyright © 2003 John Wiley & Sons, Ltd.     

Object‐oriented processing of Java source code

Code transformation and analysis tools provide support for software engineering tasks such as style checking, testing, calculating software metrics as well as reverse‐ and re‐engineering. In this paper we describe the architecture and the applications of JTransform, a general Java source code processing and transformation framework. It consists of a Java parser generating a configurable parse tree and various visitors (transformers, tree evaluators) which produce different kinds of outputs. While our framework is written in Java, the paper further opens an opportunity for a new generation of XML‐based source code tools. Copyright © 2004 John Wiley & Sons, Ltd.     

Checking JML specifications using an extensible software model checking framework

The use of assertions to express correctness properties of programs is growing in practice. Assertions provide a form of lightweight checkable specification that can be very effective in finding defects in programs and in guiding developers to the cause of a problem. A wide variety of assertion languages and associated validation techniques have been developed, but run-time monitoring is commonly thought to be the only practical solution. In this paper, we describe how specifications written in the Java Modeling Language (JML), a general purpose behavioral specification and assertional language for Java, can be validated using a customized model checker built on top of the Bogor model checking framework. Our experience illustrates the need for customized state-space representations and reduction strategies in model checking frameworks in order to effectively check the kind of strong behavioral specifications that can be written in JML. We discuss the advantages and tradeoffs of model checking relative to other specification validation techniques and present data that suggest that the cost of model checking strong specifications is practical for several real programs. This is an extended version of the paper Checking Strong Specifications Using An Extensible Model Checking Framework that appeared in Proceedings of the 10th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2004. This work was supported in part by the U.S. Army Research Office (DAAD190110564), by DARPA/IXO’s PCES program (AFRL Contract F33615-00-C-3044), by NSF (CCR-0306607) by Lockheed Martin, and by Rockwell-Collins.     

Accurate garbage collection in uncooperative environments revisited

Implementing a concurrent programming language such as Java by means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces development time—as many low‐level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on a wide range of platforms. For garbage‐collected languages, however, they are not a perfect match as no support is provided for accurately discovering pointers to heap‐allocated data on thread stacks. We evaluate several previously published techniques and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java‐to‐C/C++ compiler using GCC as a back‐end compiler. Our extensive experimental results confirm that lazy pointer stacks outperform existing approaches: we provide a speedup of 4.5% over Henderson's accurate collector with a 17% increase in code size. Accurate collection is essential in the context of real‐time systems, we thus validate our approach with the implementation of a real‐time concurrent garbage collection algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

Discrete‐time network‐based control under scheduling and actuator constraints

This paper is concerned with the solution bounds for discrete‐time networked control systems via delay‐dependent Lyapunov–Krasovskii methods. Solution bounds are widely used for systems with input saturation caused by actuator saturation or by the quantizers with saturation. The time‐delay approach has been developed recently for the stabilization of continuous‐time networked control systems under the round‐robin protocol and under a weighted try‐once‐discard protocol, respectively. Actuator saturation has not been taken into account. In the present paper, for the first time, the time‐delay approach is extended to the stability analysis of the discrete‐time networked control systems under both scheduling protocols and actuators saturation. The communication delays are allowed to be larger than the sampling intervals. A novel Lyapunov‐based method is presented for finding the domain of attraction. Polytopic uncertainties in the system model can be easily included in our analysis. The efficiency of the time‐delay approach is illustrated on the example of a cart–pendulum system. Copyright © 2014 John Wiley & Sons, Ltd.     

Composing and scheduling service‐oriented applications in time‐triggered distributed real‐time Java environments

During the last decade, the number of distributed application domains with temporal requirements has significantly augmented, arising the necessity of exploring new concepts and paradigms that allow, on the one hand, the development of dynamic and flexible distributed applications and, on the other hand, the reusability of code. Service‐oriented paradigms have been successfully applied to distributed environments, increasing their flexibility and allowing the reusability of their components. Besides, distributed real‐time Java technologies have shown to be a good candidate to deploy real‐time distributed applications. This paper presents a model for service‐oriented applications on a time‐triggered distributed real‐time Java environment, focusing on the definition of the temporal model of an application and its schedulability, applying and evaluating this model in real‐time service‐oriented composition algorithms. Copyright © 2012 John Wiley & Sons, Ltd.     

Model‐centric software architecture reconstruction

Much progress has been achieved in defining methods, techniques, and tools for software architecture reconstruction (SAR). However, less progress has been achieved in constructing reasoning frameworks from existing systems that support organizations in architecture analysis and design decisions. These reasoning frameworks are necessary, for example, to assemble existing components and deploy them in new system configurations. We propose a model‐centric approach where this kind of reasoning is driven by the analysis of quality attribute scenarios. The scenarios and the related quality attribute models guide the SAR effort by focusing on the elicitation of model relevant artifacts. The approach further drives the model construction towards the analytical support of What If scenarios that explore responses stimulated by new requirements, such as new deployments of existing components. The paper provides two real‐world case studies. The first case study introduces the model‐centric reconstruction approach in the context of a large satellite tracking system. The second case study provides the construction of a time performance model for an existing embedded system in the automotive industry. The model allows us to perform cost‐efficient predictions of component assemblies in new customer configurations. Copyright © 2005 John Wiley & Sons, Ltd.     

JRF-E: using model checking to give advice on eliminating memory model-related bugs

According to modern relaxed memory models, programs that contain data races need not be sequentially consistent. Executions that are not sequentially consistent may exhibit surprising behavior such as operations on a thread occurring in a different order than indicated by the source code, or different threads having inconsistent views of updates of shared variables. Java Racefinder (JRF) is an extension of Java Pathfinder (JPF), a model checker for Java bytecode. JRF precisely detects data races as defined by the Java memory model and can thus be used to verify sequential consistency. We describe an extension to JRF, JRF-Eliminator (JRF-E), that analyzes information collected during model checking, specifically counterexample traces and acquiring histories, and provides advice to the programmer on how to eliminate detected data races from a program. Once data races have been eliminated, standard model checking and other verification techniques that implicitly assume sequential consistency can be soundly employed to verify additional properties.