Testing real-time systems using genetic algorithms

The development of real-time systems is an essential industrial activity whose importance is increasing. The most important analytical method to assure the quality of real-time systems is dynamic testing. Testing is the only method which examines the actual run-time behaviour of real-time software, based on an execution in the real application environment. Dynamic aspects like the duration of computations, the memory actually needed, or the synchronization of parallel processes are of major importance for the correct function of real-time systems and have to be tested. A comprehensive investigation of existing software test methods shows that they mostly concentrate on testing for functional correctness. They are not suited for an examination of temporal correctness which is essential to real-time systems. Very small systems show a wide range of different execution times. Therefore, existing test procedures must be supplemented by new methods, which concentrate on determining whether the system violates its specified timing constraints. In general, this means that outputs are produced too early or their computation takes too long. The task of the tester is to find the inputs with the longest or shortest execution times to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, genetic algorithms can be used to find the inputs with the longest or shortest execution times automatically. The fitness function is the execution time measured in processor cycles. Experiments using genetic algorithms on a number of programs with up to 1511 LOC and 843 integer input parameters have successfully identified new longer and shorter paths than had been found using random testing or systematic testing. Genetic algorithms are able therefore to check large programs and they show considerable promise in establishing the validity of the temporal behaviour of real-time software.     

Verifying Timing Constraints of Real-Time Systems by Means of Evolutionary Testing

Many industrial products are based on the use of embedded computer systems. Usually, these systems have to fulfil real-time requirements, and correct system functionality depends on their logical correctness as well as on their temporal correctness. In order to verify the temporal behavior of real-time systems, previous scientific work has, to a large extent, concentrated on static analysis techniques. Although these techniques offer the possibilty of providing safe estimates of temporal behavior for certain cases, there are a number of cases in practice for which static analysis can not be easily applied. Furthermore, no commercial tools for timing analysis of real-world programs are available. Therefore, the developed systems have to be thoroughly tested in order to detect existing deficiencies in temporal behavior, as well as to strengthen the confidence in temporal correctness. An investigation of existing test methods shows that they mostly concentrate on testing for logical correctness. They are not specialised in the examination of temporal correctness which is also essential to real-time systems. For this reason, existing test procedures must be supplemented by new methods which concentrate on determining whether the system violates its specified timing constraints. Normally, a violation means that outputs are produced too early, or their computation takes too long. The task of the tester therefore is to find the input situations with the longest or shortest execution times, in order to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, evolutionary computation can be used to automatically find the inputs with the longest or shortest execution times. This automatic search for accurate test data by means of evolutionary computation is called evolutionary testing. Experiments using evolutionary testing on a number of programs with up to 1511 LOC and 5000 input parameters have successfully identified new longer and shorter execution times than had been found using other testing techniques. Evolutionary testing, therefore, seems to be a promising approach for the verification of timing constraints. A combination of evolutionary testing and systematic testing offers further opportunities to improve the test quality, and could lead to an effective test strategy for real-time systems.     

基于程序不变量计算软件可靠性

现有的计算软件可靠性的方法采用测试的输入/输出结果,但这些数据并不能真实地反映软件内部的真实行为,如测试中会出现假性正确的情况以及测试不能显示一个输入有多个错误的输出情况.试图通过程序不变量来计算软件的可靠性,程序不变量可以描述程序的性质.首先选取测试用例集,动态地获取程序不变量,再从这些不变量中提取失效数据,最后,基于Nelson模型计算软件的可靠性.作为实验,对西门子程序包计算软件的可靠性.采用随机、分支覆盖和分块覆盖这3种不同的测试方法得到程序不变量,据此计算程序的可靠性.为了检查结果的可行性,采用传统方法计算这些软件的可靠性.两种可靠性比较后显示:它们的差别很小,而且不依赖于对测试方法的选择.通过进一步的方差分析得知,用所提出的方法计算的可靠性比用现有的方法计算的可靠性具有更小的波动,即更平稳.因此,前者更接近系统的真实可靠性.结论说明,可用程序不变量来计算软件的可靠性.     

Measurement based analysis of temporal behaviour as support for scheduling problems in parallel and distributed real-time systems

Static analysis, based on scheduling techniques, provides the most typical approach for validation of real-time systems. However, in the case of complex real-time systems such as parallel and distributed systems, many simplifications are made in order to make analysis tractable. This means that even if the system can be statically validated, the real behaviour of the system in execution may be different enough from its theoretical behaviour to make it invalid. In these cases, an analysis based on measurement of the system in execution constitutes an invaluable aid to the static analysis. This article describes a methodology for the analysis of the temporal behaviour of parallel and distributed real-time systems with end-to-end constraints. The analysis is based on the measurement of a prototype of the system in execution and is supported by a behavioural model. The main components of the model are the sequences of activities throughout the system tasks (transactions), which are carried out in response to input events, causing the corresponding output events. Thus, the temporal behaviour of the system is viewed as a set of real-time transactions competing for the available resources. This article also includes experimental results of applying the methodology to the analysis of a well-known case study.     

Stability analysis of nonlinear multi-agent relay tracking systems over a finite time interval

ABSTRACT

This paper explores the stability of a class of multi-agent systems with proposed relay tracking strategy over a finite time interval. In this paper, agents are deployed in an area to monitor and track the intruded targets. According to proposed relay tracking strategy, the tracking agents and their communication topologies switch during the whole tracking process. This results in impulsive effects on the overall tracking errors. The relationship of finite time interval against desired overall tracking errors and control parameter is derived quantitatively for the multi-agent relay tracking system. Moreover, stability conditions for the system with disturbances and impulsive effects are obtained. Performance of proposed relay tracking strategy and correctness of derived results on stability over finite time intervals are demonstrated by a set of simulations.     

UCov: a user‐defined coverage criterion for test case intent verification

The goal of regression testing is to ensure that the behaviour of existing code, believed correct by previous testing, is not altered by new program changes. This paper argues that the primary focus of regression testing should be on code associated with (1) earlier bug fixes and (2) particular application scenarios considered to be important by the developer or tester. Existing coverage criteria do not enable such focus, for example, 100% branch coverage does not guarantee that a given bug fix is exercised or a given application scenario is tested. Therefore, there is a need for a new and complementary coverage criterion in which the user can definea test requirement characterizing a given behaviour to be covered as opposed to choosing from a pool of pre‐defined and generic program elements. This paper proposes this new methodology and calls it UCov, a user‐defined coverage criterion wherein a test requirement is an execution pattern of program elements, and possibly predicates, that a test case must satisfy. The proposed criterion is not meant to replace existing criteria, but to complement them as it focuses the testing on important code patterns that could go untested otherwise. UCov supports test case intent verification. For example, following a bug fix, the testing team may augment the regression suite with the test case that revealed the bug. However, this test case might become obsolete due to code modifications not related to the bug. But if a test requirement characterizing the bug was defined by the user, UCov would determine that test case intent verification failed. The UCov methodology was implemented for the Java platform, was successfully applied onto 10 real‐life case studies and was shown to have advantages over JUnit. The implementation comprises the following tools: (1) TRSpec: allows the user to easily specify complex test requirements; (2) TRCheck: checks whether user‐defined test requirements were satisfied, that is, supports test case intent verification; and (3) TRMigrate: migrates user‐defined test requirements to subsequent versions of a given program. Copyright © 2016 John Wiley & Sons, Ltd.     

Testing robot controllers using constraint programming and continuous integration

ContextTesting complex industrial robots (CIRs) requires testing several interacting control systems. This is challenging, especially for robots performing process-intensive tasks such as painting or gluing, since their dedicated process control systems can be loosely coupled with the robot’s motion control.ObjectiveCurrent practices for validating CIRs involve manual test case design and execution. To reduce testing costs and improve quality assurance, a trend is to automate the generation of test cases. Our work aims to define a cost-effective automated testing technique to validate CIR control systems in an industrial context.MethodThis paper reports on a methodology, developed at ABB Robotics in collaboration with SIMULA, for the fully automated testing of CIRs control systems. Our approach draws on continuous integration principles and well-established constraint-based testing techniques. It is based on a novel constraint-based model for automatically generating test sequences where test sequences are both generated and executed as part of a continuous integration process.ResultsBy performing a detailed analysis of experimental results over a simplified version of our constraint model, we determine the most appropriate parameterization of the operational version of the constraint model. This version is now being deployed at ABB Robotics’s CIR testing facilities and used on a permanent basis. This paper presents the empirical results obtained when automatically generating test sequences for CIRs at ABB Robotics. In a real industrial setting, the results show that our methodology is not only able to detect reintroduced known faults, but also to spot completely new faults.ConclusionOur empirical evaluation shows that constraint-based testing is appropriate for automatically generating test sequences for CIRs and can be faithfully deployed in an industrial context.     

The influence of computerized feedback on overconfidence in knowledge

Abstract

Subjects were tested on general knowledge questions. They had to give their answer to each question and to state their level of confidence in its correctness. This was done under four conditions: by a paper and pencil test with and without feedback; and by computerized testing, again, with and without feedback. All in all, subjects demonstrated overconfidence in their knowledge under all conditions. However, feedback by a computerized system was effective in reducing the overconfidence level. The implications of this finding to the domain of computer-based educational systems is discussed.     

A Formal Interpretation of Software Testing as Inductive Inference

Software testing can be viewed as an inductive inference process during which the tester attempts to deduce software properties from its behaviour on a finite number of test cases. This paper investigates the foundation of software testing by interpreting the axioms of test adequacy criteria as properties of inductive inference. The interpretation manifests the conservative and simplest hypothesis nature of the induction underlying software testing. It also yields results relating adequate testing to software correctness and reliability. The convergence of the inductive inference process is proved to be a condition of the correctness of tested software. By measuring the convergence according to the probability of an inference result being correct up to a given error rate, a new approach to software reliability estimation is proposed, which differs from existing ones in taking software complexity into account.     

Search based algorithms for test sequence generation in functional testing

ContextThe generation of dynamic test sequences from a formal specification, complementing traditional testing methods in order to find errors in the source code.ObjectiveIn this paper we extend one specific combinatorial test approach, the Classification Tree Method (CTM), with transition information to generate test sequences. Although we use CTM, this extension is also possible for any combinatorial testing method.MethodThe generation of minimal test sequences that fulfill the demanded coverage criteria is an NP-hard problem. Therefore, search-based approaches are required to find such (near) optimal test sequences.ResultsThe experimental analysis compares the search-based technique with a greedy algorithm on a set of 12 hierarchical concurrent models of programs extracted from the literature. Our proposed search-based approaches (GTSG and ACOts) are able to generate test sequences by finding the shortest valid path to achieve full class (state) and transition coverage.ConclusionThe extended classification tree is useful for generating of test sequences. Moreover, the experimental analysis reveals that our search-based approaches are better than the greedy deterministic approach, especially in the most complex instances. All presented algorithms are actually integrated into a professional tool for functional testing.     

Defining a test coverage criterion for model-level testing of FBD programs

ContextThe Programmable Logic Controller (PLC) is being integrated into the automation and control of computer systems in safety–critical domains at an increasing rate. Thoroughly testing such software to ensure safety is crucial. Function Block Diagram (FBD) is a popular data-flow programming language for PLC. Current practice often involves translating an FBD program into an equivalent C program for testing. Little research has been conducted on coverage of direct testing a data-flow program, such as an FBD program, at the model level. There are no commonly accepted structural test coverage criteria for data-flow programs. The objective of this study is to develop effective structural test coverage criterion for testing model-level FBD programs. The proposed testing scheme can be used to detect mutation errors at the logical function level.ObjectiveThe purpose of this study is to design a new test coverage criterion that can directly test FBD programs and effectively detect logical function mutation errors.MethodA complete test set for each function and function block in an FBD program are defined. Moreover, this method augments the data-flow path concept with a sensitivity check to avoid fault masking and effectively detect logical function mutation errors.ResultsPreliminary experiments show that this test coverage criterion is comprehensive and effective for error detection.ConclusionThe proposed coverage criterion is general and can be applied to real cases to improve the quality of data-flow program design.     

Automated test generation technique for aspectual features in AspectJ

ContextAspect-oriented programming (AOP) has been promoted as a means for handling the modularization of software systems by raising the abstraction level and reducing the scattering and tangling of crosscutting concerns. Studies from literature have shown the usefulness and application of AOP across various fields of research and domains. Despite this, research shows that AOP is currently used in a cautious way due to its natural impact on testability and maintainability.ObjectiveTo realize the benefits of AOP and to increase its adoption, aspects developed using AOP should be subjected to automated testing. Automated testing, as one of the most pressing needs of the software industry to reduce both effort and costs in assuring correctness, is a delicate issue in testing aspect-oriented programs that still requires advancement and has a way to go before maturity.MethodPrevious attempts and studies in automated test generation process for aspect-oriented programs have been very limited. This paper proposes a rigorous automated test generation technique, called RAMBUTANS, with its tool support based on guided random testing for the AspectJ programs.ResultsThe paper reports the results of a thorough empirical study of 9 AspectJ benchmark programs, including non-trivial and larger software, by means of mutation analysis to compare RAMBUTANS and the four existing automated AOP testing approaches for testing aspects in terms of fault detection effectiveness and test effort efficiency. The results of the experiment and statistical tests supplemented by effect size measures presented evidence of the effectiveness and efficiency of the proposed technique at 99% confidence level (i.e. p < 0.01).ConclusionThe study showed that the resulting randomized tests were reasonably good for AOP testing, thus the proposed technique could be worth using as an effective and efficient AOP-specific automated test generation technique.     

PHOEBE: an automation framework for the effective usage of diagnosis tools in the performance testing of clustered systems

The identification of performance issues and the diagnosis of their root causes are time‐consuming and complex tasks, especially in clustered environments. To simplify these tasks, researchers have been developing tools with built‐in expertise for practitioners. However, various limitations exist in these tools that prevent their efficient usage in the performance testing of clusters (e.g. the need of manually analysing huge volumes of distributed results). In a previous work, we introduced a policy‐based adaptive framework (PHOEBE) that automates the usage of diagnosis tools in the performance testing of clustered systems, in order to improve a tester's productivity, by decreasing the effort and expertise needed to effectively use such tools. This paper extends that work by broadening the set of policies available in PHOEBE, as well as by performing a comprehensive assessment of PHOEBE in terms of its benefits, costs and generality (with respect to the used diagnosis tool). The performed evaluation involved a set of experiments in assessing the different trade‐offs commonly experienced by a tester when using a performance diagnosis tool, as well as the time savings that PHOEBE can bring to the performance testing and analysis processes. Our results have shown that PHOEBE can drastically reduce the effort required by a tester to do performance testing and analysis in a cluster. PHOEBE also exhibited consistent behaviour (i.e. similar time‐savings and resource utilisations), when applied to a set of commonly used diagnosis tools, demonstrating its generality. Finally, PHOEBE proved to be capable of simplifying the configuration of a diagnosis tool. This was achieved by addressing the identified trade‐offs without the need for manual intervention from the tester. Copyright © 2017 John Wiley & Sons, Ltd.     

New approaches for passive testing using an Extended Finite State Machine specification

This paper presents two new approaches for passive testing using an Extended Finite State Machine (EFSM) specification. The state of the art of passive testing shows us that all the methods for detection of errors based on EFSMs try to match the trace to the specification. Indeed, one searches a state succession in the specification machine that is able to generate the trace observed on the implementation. Using this approach, processing is performed on the specification and the trace remains in the background since no operation is applied to it. This made us realise that focusing our efforts on the trace could be beneficial and has given as result two approaches presented in this paper that extract information from the specification and then work on the trace. Thus, they take a different direction than the previous methods. We first present an approach to test traces by using invariants resulting from the specification. We formally define these invariants and we see how to extract them. We also discuss their ability to detect errors appearing in the implementation. This approach is able to test the data flow, but not in a very satisfactory way. This is the reason for a second approach seeking to apply a set of constraints to the trace. We develop in detail its principles. Both approaches are applied to a Simple Connection Protocol (SCP) and the results of preliminary experiments are presented.     

The formal-CAFE methodology and model checking patterns in the specification of e-commerce systems

Electronic commerce is an important application that has evolved significantly recently. However, electronic commerce systems are complex and difficult to be correctly designed. Guaranteeing the correctness of an e-commerce system is not an easy task due to the great amount of scenarios where errors occur, many of them very subtle. In this work we presents a methodology that uses formal-method techniques, specifically symbolic model checking, to design electronic commerce applications and to automatically verify them. Also, a model checking pattern hierarchy has been developed—it specifies patterns to construct and verify the formal model of e-commerce systems. We consider this research the first step to the development of a framework, which will integrate the methodology, an e-commerce specification language based on business rules, and a model checker. Adriano Pereira received the B.S. and M.S. degrees in computer science in 2000 and 2002, respectively, and he is currently pursuing the Ph.D. degree in computer science from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His current interests are on performance analysis and modeling of e-business and distributed systems, and formal methods. Mark Song received the B.S., M.S. and Ph.D. degrees in computer science from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His current interests are on distributed systems and formal methods – especially BMC (Bounded Model Checking). Gustavo Franco received the B.S. and M.S. degrees in computer science in 2001 and 2004, respectively, from the Federal University of Minas Gerais, Belo Horizonte, Brazil. His research was on modeling the user behavior of e-business and distributed systems, and formal methods. Actually his current interests are on software engeneering and project management of IT projects.     

Knowledge management initiatives in software testing: A mapping study

ContextSoftware testing is a knowledge intensive process, and, thus, Knowledge Management (KM) principles and techniques should be applied to manage software testing knowledge.ObjectiveThis study conducts a survey on existing research on KM initiatives in software testing, in order to identify the state of the art in the area as well as the future research. Aspects such as purposes, types of knowledge, technologies and research type are investigated.MethodThe mapping study was performed by searching seven electronic databases. We considered studies published until December 2013. The initial resulting set was comprised of 562 studies. From this set, a total of 13 studies were selected. For these 13, we performed snowballing and direct search to publications of researchers and research groups that accomplished these studies.ResultsFrom the mapping study, we identified 15 studies addressing KM initiatives in software testing that have been reviewed in order to extract relevant information on a set of research questions.ConclusionsAlthough only a few studies were found that addressed KM initiatives in software testing, the mapping shows an increasing interest in the topic in the recent years. Reuse of test cases is the perspective that has received more attention. From the KM point of view, most of the studies discuss aspects related to providing automated support for managing testing knowledge by means of a KM system. Moreover, as a main conclusion, the results show that KM is pointed out as an important strategy for increasing test effectiveness, as well as for improving the selection and application of suited techniques, methods and test cases. On the other hand, inadequacy of existing KM systems appears as the most cited problem related to applying KM in software testing.     

Manual test case derivation from UML activity diagrams and state machines: A controlled experiment

ContextIt is a difficult and challenging task to fully automatize model-based testing because this demands complete and unambiguous system models as input. Therefore, in practice, test cases, especially on the system level, are still derived manually from behavioral models like UML activity diagrams or state machines. But this kind of manual test case derivation is error-prone and knowing these errors makes it possible to provide guidelines to reduce them.ObjectiveThe objective of the study presented in this paper therefore is to examine which errors are possible and actually made when manually deriving test cases from UML activity diagrams or state machines and whether there are differences between these diagram types.MethodWe investigate the errors made when deriving test cases manually in a controlled student experiment. The experiment was performed and internally replicated with overall 84 participants divided into three groups at two institutions.ResultsAs a result of our experiment, we provide a taxonomy of errors made and their frequencies. In addition, our experiment provides evidence that activity diagrams have a higher perceived comprehensibility but also a higher error-proneness than state machines with regard to manual test case derivation. This information helps to develop guidelines for manual test case derivation from UML activity diagrams and state machines.ConclusionMost errors observed were due to missing test steps, conditions or results, or content was written into the wrong field. As activity diagrams have a higher perceived comprehensibility, but also more error-prone than state machines, both diagram types are useful for manual test case derivation. Their application depends on the context and should be complemented with clear rules on how to derive test cases.     

不变量的程序潜在错误预测

随着软件系统变得越来越复杂和庞大,软件中的安全缺陷也急剧增加,系统中的隐含错误也在逐渐增多.提出一种基于不变量的程序潜在错误预测方法,首先采用支持向量机对程序属性所产生的非函数依赖程序不变量进行学习并产生机器学习模式,然后运用该机器学习模式对需预测的程序进行属性分类,并揭示出代码可能存在的潜在错误,最后通过实验验证该方法是有效的.     

Statechart testing method for aircraft control systems

A number of current control systems for aircraft have been specified with statecharts. The risk of failures requires the use of a formal testing approach to ensure that all possible faults are considered. However, testing the compliance of an implementation of a system to its specification is dependent on the specification method and little work has been reported relating to the use of statechart-specific methods. This paper describes a modification of a formal testing method for extended finite-state machines to handle the above problem. The method allows one to demonstrate correct behaviour of an implementation of some system, with respect to its specification, provided certain specific requirements for both of them are satisfied. The case study illustrates these and shows the applicability of the method. By considering the process used to develop the system it is possible to reduce the size of the test set dramatically; the method to be described is easy to automate. Copyright © 2001 John Wiley & Sons, Ltd.