Martial Chabot

Laurence Pierre

A Customizable Monitoring Infrastructure for Hardware/Software Embedded Systems

The design of today's embedded systems requires a complex verification process. In particular, due to the strong hardware/software interdependence, debugging the embedded software is a demanding task. We have previously reported our results about the development of a framework that enables the Assertion-Based Verification (ABV) of temporal requirements for high-level reference models of such systems. In this paper, we describe conceptual and practical improvements of this monitoring infrastructure to give the user the possibility to customize and to optimize the verification process. Experimental results on industrial case studies illustrate the benefits of the approach.

Introduction

With the increasing complexity of systems on chips (SoC) and time-to-market pressure, rising the abstraction level to ESL (Electronic System Level) modeling is becoming indispensable. Platform-based design emerges as a new paradigm for the design and analysis of embedded systems [START_REF] Carloni | Platform-Based Design for Embedded Systems[END_REF]. In that context, SystemC TLM (Transaction Level Modeling) [START_REF] Grötker | System Design with SystemC[END_REF] is gaining acceptance, in particular because the simulation of TLM models is several orders of magnitude faster, thus considerably improving productivity in SoC design [START_REF] Klingauf | Why We Need Standards for Transaction-Level Modeling[END_REF]. SystemC [START_REF]IEEE Std 1666-2005[END_REF] is in fact a C++ library; a SystemC model is made of modules that have I/O ports and can run processes. They are interconnected using channels. A SoC model includes modules that are models of microprocessors (ISS, Instruction Set Simulator) which execute embedded software, busses, memories, hardware coprocessors like DSP (Digital Signal Processor), DMAs (Direct Memory Access, components that perform memory transfers),. . . In a transaction-level model (TLM), the details of communication among components are separated from the details of computation [START_REF] Cai | Transaction Level Modeling: An Overview[END_REF]. Transaction requests take place by calling interface functions of the channel models.

The challenge addressed here is Assertion-Based Verification (ABV) for complex SoCs modeled at the System level in SystemC TLM. Requirements to be verified at this level of abstraction express temporal constraints on the interactions (between hardware and software components) in the SoC. They can be formalized with a language such as the FL (Foundation Language) class of the IEEE standard PSL [START_REF]IEEE Std 1850-2005, Standard for Property Specification Language (PSL)[END_REF], which essentially represent linear temporal logic (LTL). In [START_REF] Pierre | A Tractable and Fast Method for Monitoring SystemC TLM Specifications[END_REF] we have presented a methodology that enables the runtime verification of PSL assertions for TLM specifications: assertion checkers (monitors) are automatically generated from PSL properties, and the design is instrumented with these monitors using an ad hoc observation mechanism. Then, the SystemC simulation is run as usual, and the assertion checkers dynamically report property violations, if any. In that context, simulation traces must be sampled according to communication actions involved in the assertions, hence the observation mechanism detects the communication functions calls and triggers the monitors accordingly. A prototype tool called ISIS has been developed; experimental results on industrial case studies have been reported in [START_REF] Pierre | Runtime Verification of Typical Requirements for a Space Critical SoC Platform[END_REF], [START_REF] Pierre | Integrating PSL Properties into SystemC Transactional Modeling -Application to the Verification of a Modem SoC[END_REF].

However, this original version of the tool offers few flexibility to the user. It is only possible to select, at the SystemC compile time, the assertions/monitors to be attached to the design. We present here conceptual extensions of the underlying observation model, and their implementation, that enable the designers -in particular the software developers -to customize and optimize the verification process and to get concise and easily analyzable verification results. the SystemC platform is used by the software designer to develop the application, but he usually does not wish to recompile the platform (or even has it only under executable form). Hence selecting the assertions to be attached to the design should be feasible at runtime, not at the SystemC compile time, more essentially, it should be possible to configure the instrumented simulation to take into account relationships between assertions to dynamically disable/enable monitors, thus clarifying and optimizing the verification, it should also be possible to store concise information about assertions activations, satisfactions, violations, and to easily analyze verification results.

Configuration without Platform Recompilation

The assertion checkers generated from the PSL expression of the requirements, and the observation mechanism, are SystemC modules that instrument the Sys-temC platform. ISIS takes as input the platform source files and an XML configuration file that specifies the selected assertions, and produces this instrumented design. With the original version of the tool, the user must execute again this procedure, and recompile the resulting platform, every time he wants to choose other requirements to be checked. The tool has been improved to generate an instrumented source code that import all the assertion checkers but enables their optional runtime instantiation, according to choices given in a configuration file.

Monitors Enabling/Disabling

The observation mechanism is based on a model, inspired from the observer pattern, that allows to observe the transactional actions in the system and to trigger the monitors when needed [START_REF] Pierre | A Tractable and Fast Method for Monitoring SystemC TLM Specifications[END_REF]. Each monitor is enclosed in a wrapper that observes the channels and/or signals involved in the property associated with this monitor; the channels/signals are observable objects (or Subjects).

Originally, the assertion checkers remain active all along the simulation. However, requirements are usually correlated (not by purely logical relations, that could be identified by subsumption detection [START_REF] Biere | Resolve and expand[END_REF], but by conceptual relations, determined by the designer). The tool has been enhanced to enable/disable monitors according to these relations. The model has been extended with a Verification Manager component, as described by the class diagram of Figure 2. A Manager can include a collection of wrappers, and takes care of the associated monitors. By means of a configuration file, the user specifies relations of the form A i R A j which express that, if assertion A i experiences violations, then checking assertion A j becomes worthless. The Manager can be configured such that, when it detects that the monitor of A i reports violations, either it only disables A i immediately (Level 1), or it also disables the monitor of A j (Level 2). As illustrated in section 3, this has two main advantages: simulation traces only include the most relevant information provided by the checkers, thus simplifying the interpretation of the verification results; the CPU time overhead induced by the checkers may be minimized, thus optimizing the verification process.

Database with Verification Results

To ease the analysis of the verification results, in addition to the textual verification reports, verification results are now stored in a database. To achieve this, the Monitor class has been extended with a member which is a vector of database entries (see Fig. 2). During a simulation, the monitor stores here the information about every assertion activation: start time, end time, status (pass or fail). This information is ultimately committed to the database. A post-processing tool extracts a concise and easily analyzable tabular representation of the results. Other post-processing tools e.g., for statistical analysis, are under development.

Experimental Results

Space High Resolution Image Processing

This case study (from Astrium) is an image processing platform that performs spectral compression, see Figure 3. It mainly includes two processors, leon a and leon b, two DMA components, memories, a FFT coprocessor, and an IO module. Process synchronization is ensured by software. A set of requirements has been defined for this platform, some of them are presented below:

-A 1 : DMA a must not be reconfigured before the end of a transfer.

-A 2 : The FFT must not be reconfigured before the end of a computation.

-A 3 (no loss of input data): Every input data packet must be transferred by DMA a to Mem a before the IO module generates a new interrupt. -A 4 (software not too slow): Every data packet stored in Mem a must be processed by leon a before being overwritten (note: Mem a is 32 MB large)

-A 5 (no loss of processed data): Each incoming data packet (read by DMA a from the IO module) must have a corresponding output packet (written by DMA b to the IO module), before 3 new incoming data packets are processed.

There are conceptual dependencies between these requirements. For example, if A 3 is violated (meaning that input data are lost), the results of A 5 become irrelevant because paying attention to the loss of output data is useless, the bug revealed by A 3 must first be Property A 2 however might still be enabled, to continue checking the interactions between leon b and its FFT coprocessor. Table 1 summarizes results for processing 10000 images, with configurations that can induce data loss: CPU times, total number of checkers activations (notifications on function calls), and of checkers actual triggerings. Column 1 is for the raw simulations, column 2 gives the full monitoring results (Level 0), column 3 corresponds to Level 1 of the Manager, columns 4 and 5 correspond to Level 2, with the management of one or several assertion correlations. Assertion A 4 is the most time-consuming one (it may require several thousands of concurrent monitor instances), configurations in which it may be disabled are optimum.

Avionics Flight Control Remote Module

This case study (from Airbus) is an avionics module dedicated to processing data from sensors and controlling actuators according to predefined flight laws. Certification issues and specific safety requirements must be taken into account. Properties are associated with the joint behaviour of the software and the DSP coprocessor (see Figure 4). This component stores and uses data that represent digital filter coefficients and analog input (ANI) calibration coefficients. Data integrity must be checked, to protect the device against SEU (Single Event Upset, change of state caused by energetic particles). Among the requirements:

-A 1 : Checksum computation must be performed every CHECKSUM PERIOD ms (the corresponding result is stored in the register STATUS of the DSP). -A 2 (ensures detection of potential checksum errors): The software must read the content of STATUS every CHECK PERIOD ms. -A 3 : When a checksum error is detected (wrong value in STATUS), the DSP function must be deactivated (within LIMIT ms). Those properties are clearly intercorrelated. Table 1 summarizes some results, for the processing of 25000 analog data coming from the ANI port, with configurations that can induce missed deadlines. Here full monitoring is not really time-consuming (about 2% CPU time overhead), therefore the benefit rather comes from the fact that the number of assertions triggerings significantly decreases, hence making the results more conveniently analyzable because avoiding irrelevant trigerrings means that only the most useful information appears in the simulation trace.

Conclusion

The results show that this version of the ABV tool can significantly improve the efficiency of the instrumented simulations (e.g., fifth column of the first row), and can produce more easily analyzable results, which is crucial to facilitate debug. On-going work includes the identification of correlations between monitoring results and specific patterns in the simulation traces.

Fig. 1 .

 1 Fig. 1. Customizable Assertion-Based Verification infrastructure

Fig. 2 .

 2 Fig. 2. Extended model -Verification manager

Fig. 3 .

 3 Fig. 3. Image processing case study The leon a processor configures the DMA a component to get the image from the IO module to Mem a where raw data are sub-sampled. Packets are then transferred to Mem b and a 2D-FFT is applied to obtain the corresponding spectrum. The resulting packets are then compressed by the leon b processor which configures DMA b to send the output packets back to the IO module.Process synchronization is ensured by software. A set of requirements has been defined for this platform, some of them are presented below:-A 1 : DMA a must not be reconfigured before the end of a transfer.-A 2 : The FFT must not be reconfigured before the end of a computation.-A 3 (no loss of input data): Every input data packet must be transferred by DMA a to Mem a before the IO module generates a new interrupt. -A 4 (software not too slow): Every data packet stored in Mem a must be processed by leon a before being overwritten (note: Mem a is 32 MB large)

Fig. 4 .

 4 Fig. 4. Flight control case study

Table 1 .

 1 activ. 1310 10 6 activ. 1310 10 6 activ. 461340 activ. 2.13 10 6 trigerrings 2.11 10 6 trig. 2.1 10 6 trig. Comparative results for various manager configurations

		Raw	Full	Violation	Level 2,	Several
		simulation	monitoring	detect. (Level 1) 1 correlation correlations
	Image				A3 R A5	∀j, A3 R Aj
	proc.	71.10 s	211.2 s	219 s	213.84 s	72.68 s
			1311 10 6 632 trig.
	Flight				A 1 R A 2	∀j, A 1 R A j
	control 52.41 s	53.5 s	52.84 s	52.57 s	52.52 s
			1.2 10 6 activ.	860000 activ.	500000 activ. 135000 activ.
			67 trigerrings	58 trigerrings	8 trigerrings 7 trigerrings


Benedikt Eberhardinger

Hella Seebach

Alexander Knapp

Wolfgang Reif

Towards Testing Self-Organizing, Adaptive Systems

Keywords: Self-Organizing Systems, Adaptive Systems, Software Engineering, Software Testing, Multi-Agent Systems, Quality Assurance

The characteristics of self-adaptive, self-organizing systems lead to a significant higher flexibility and robustness against a changing environment. This flexibility makes it hard to test these systems adequately. To assure their quality, however, it is inevitable to do so. We introduce a new approach for systematically testing these self-* systems based on a feedback control-oriented system architecture called Corridor Enforcing Infrastructure (CEI). Thus, it is possible to examine particular situations, where the system is forced to reorganize or adapt to new situations. This is where the self-* mechanisms come into play and can be tested separately.

Introduction

For many years, nature has been a source of inspiration for the design of information systems, e.g., in the research areas of artificial intelligence, multi-agent systems, and self-organizing systems. The core idea is to develop systems by using the so called self-* properties (self-healing, self-configuring, and self-optimizing), which correspond to biological mechanisms. The foundation of many of the self-* properties is self-organization (SO). SO enables a restructuring of the system and its components in order to conform to its environment to fulfill its goals. This new flexibility leads to challenges in engineering these systems. For example, the behavior can not be specified fully at design-time and adaptation decisions are moved to run-time. This makes it hard to assure that those systems fulfill their requirements, but even more necessary to take appropriate measures. In this connection testing plays a decisive role. The pivotal question is how to handle the state space of a self-organizing, adaptive systems (SOAS) which is developing in an evolutionary fashion during the execution of the system.

Our approach for testing is based on the Corridor Enforcing Infrastructure (CEI), an architectural pattern for SOAS. The CEI uses the concepts of feedback-loops to continuously observe and control the system if necessary. On that account monitoring is used to achieve situational awareness which is prerequisite to organize the system in a way to fulfill its requirements. The bulk of concepts and techniques used in the CEI for controlling and organizing the system is triggered by the violation of constraints. An error-free CEI will consequently guarantee a system that fulfills its requirements at every time. On this account, we claim that testing SOAS can be achieved by testing the CEI. Here we benefit from specific characteristics: we are able to reduce the relevant state space of the system to be tested tremendously and to gain a clear distinction between correct and incorrect behavior out of the concepts of the CEI-essential for evaluating the tests. SOAS are highly distributed systems-making them hard to test-and are interacting locally to solve problems. This locality is exploited in our approach, because many test cases focus on single agents or small agent groups of which the system is composed; this focus make it easier to execute and evaluate them.

In the following sections we will discuss related work and describe our approach for testing SOAS, which is based on concepts of the CEI that are introduced in Sec. 3 and concepts to reveal failures out of the CEI in Sec. 4.

Related Work

The necessity of testing adaptive systems has been recognized in the testing community [START_REF] Nguyen | Testing Techniques for Software Agents[END_REF][START_REF] Padgham | Model-based test oracle generation for automated unit testing of agent systems[END_REF][START_REF] Zhang | Model based testing for agent systems[END_REF] as well as in the community of adaptive systems [START_REF] Fredericks | Towards run-time testing of dynamic adaptive systems[END_REF][START_REF] Wotawa | Adaptive autonomous systems -from the system's architecture to testing[END_REF]. Both run-time and design-time approaches have considered indeterminism and the emergent behavior as main challenges for testing adaptive systems.

Run-time approaches for testing take up the paradigm of run-time verification [START_REF] Falcone | Runtime verification of component-based systems[END_REF][START_REF] Leucker | A brief account of runtime verification[END_REF][START_REF] Filieri | A formal approach to adaptive software: Continuous assurance of non-functional requirements[END_REF]. They shift testing into run-time to be able to observe and test, i.a., the adaption to new situations. Camara et al. [START_REF] Camara | Evaluation of resilience in self-adaptive systems using probabilistic model-checking[END_REF] are using these concepts to consider fully integrated systems. The authors simulate the environment of the system to investigate its adaptive capabilities, and to collect data about how the system reacts. The sampled data is then combined with a probabilistic model of the system and used as input for a model checker in order to evaluate given system properties. Similar approaches are taken by Ramirez et al. [START_REF] Ramirez | Automatically exploring how uncertainty impacts behavior of dynamically adaptive systems[END_REF]. They use the sampled data from a simulation to calculate a distance to expected values derived from the goal specification of the system.

Overall the run-time approaches are limited to test the fully integrated system and are only sampling, but not evaluating, data at run-time. We extend this simulation testing of a fully integrated system by a bottom-up testing strategy, starting from single agents, in order to cover testing in the whole software development life cycle. Furthermore, we are able to evaluate the runs online without complex model checking on the system level with the usage of the CEI.

Design-time approaches for testing adaptive systems [START_REF] Nguyen | Testing Techniques for Software Agents[END_REF][START_REF] Padgham | Model-based test oracle generation for automated unit testing of agent systems[END_REF][START_REF] Zhang | Model based testing for agent systems[END_REF] are focusing on specific subsets, e.g., the implementation of single agents. Zhang et al. [START_REF] Zhang | Model based testing for agent systems[END_REF] are focusing on testing the execution of plans of single agents and groups of agents. This focal point does not allow to evaluate adaptive or even self-organizing characteristics of the system, contrary to our approach.

In conclusion, testing adaptive systems is in focus of some research groups. However, none of them is extending the techniques to self-organizing systems which are able to form emergent behavior. We aim to deal with SO in all its facets and therefore combine run-and design-time testing techniques.

3 The Corridor Enforcing Infrastructure: Enabler for Systematic, Automatic Testing of SOAS

The CEI is an architectural pattern for SOAS, based on decentralized feedbackloops used to monitor and control single agents or small groups of agents in order to enforce that all system requirements are fulfilled at all times. The decentralization follows from a modular system structure where the system requirements are addressed to single or small groups of autonomous agents. An error-free CEI makes it unnecessary to test concrete system states, because the CEI guarantees that all states fulfill the system requirements. Consequently, only the CEI and its mechanisms must be tested instead of the whole SOAS en bloc, this significantly reduces the test effort.

The CEI is based on the concept of the corridor of correct behavior (CCB) which is formally introduced by Güdemann et al. [START_REF] Güdemann | A specification and construction paradigm for organic computing systems[END_REF]. The corridor is formed by all requirements, realized as constraints, of the considered system. An exemplary corridor is shown in Fig. 1. If all constraints are fulfilled, the system is inside the corridor. Otherwise, the system leaves the corridor, indicated by a flash in Fig. 1, this demands that the system is transitioned into a safe-mode. Furthermore, the system has to be reorganized to return to a state within the corridor; this is shown through the check mark in Fig. 1. An error would occur if a transition outside of the corridor is taken, indicated by a cross in Fig. 1. The CEI implementation of the CCB is based on a monitoring and controlling infrastructure. The monitoring infrastructure observes the system and detects a violation of the corridor; in some cases it can be (semi-)automatically generated from the requirement documents of the system, as shown by Eberhardinger et al. [START_REF] Eberhardinger | Model-driven synthesis of monitoring infrastructure for reliable adaptive multi-agent systems[END_REF]. The controlling infrastructure ensures that the system is transitioned into a safe mode when the constraints are violated and reorganizes the system that all requirements are fulfilled again.

The CEI and its mechanisms will be tested in order to validate that the SOAS fulfills all requirements at all times. Several failures can occur independently due to the SO mechanisms used in the controlling infrastructure, e.g., genetic algorithms or constraint solving. Our SOAS testing approach examines special situations where the system is confronted with environmental situations in which SO or adaptation is required and the CEI stressed. In the next section we will outline how to cope with this in our testing concepts in more detail.

Environmental Variation Scenarios: Forcing the CEI to Reveal Failures

To force the CEI to reveal failures we use test scenarios which stress this infrastructure. We apply a compositional test strategy which is geared to the classic testing strategies unit testing, integration testing, and system testing. Thus, we are able to form a test process for the whole development cycle. The nature of the mechanisms within the CEI are on adapting and reorganizing the system to react to its changing environment. Thus, we aim to automatically generate so called environmental variation scenarios (EVS) for testing the mechanisms of the CEI. For a single agent, this means in fact we want to validate that changes in the environment are detected via sensors used by the monitoring infrastructure and the agent adapts accordingly to fulfill its goals. The input for the agent can be simulated by mocking in the test system without setting up complex initial states. We automatically extract the EVS from the specification of the agents and use them for testing. For this purpose we have to take a closer look at the behavioral model (e.g., state machines) of the agents to derive a model of their interactions with the environment. To build the EVS from these models we use model checking techniques that find sequences in which the interaction between the agent and its environment leads to a violation of the CCB, illustrated by a flash in Fig. 1. Such a violation has to be detected by checking the system state according to the CCB through the monitoring-infrastructure. It must be pointed out that such violations are no failures of the CEI, but the CEI has to detect them and take the adequate actions.

The EVS are, as introduced, based on single agent situations. This means a fine-grained level of decomposition which also reflects the way the constraints of the CCB are defined and consequently the concepts of the CEI. To be able to test scenarios where several agents are interacting, we need to extend the EVS. Interactions are essential in testing, especially to cover SO mechanisms, since the results of these mechanisms mainly depend on interactions of the participating agents, which lead to restructuring and adaptation of these participating agents. This characteristic has to be reflected in the test scenarios for groups of agents on the agent interaction level. Interactions between agents in SOAS use different mechanisms, e.g., stigmergy or simple message passing. These interdependencies have to be taken into account to derive a scenario for a group of agents as well as for a fully integrated system under test. The interactions can be culled from the communication protocols of the system. The scenarios for single agents can now be connected via the possible interactions between agents. The result will be an interaction model for selected scenarios. Because of evolutionarily changing system structures, it is hard to predict which communication scenarios will be executed. But by focusing on the EVS for derivation of test cases, the resulting interaction scenarios are just small subsets of the overall system communication and therefore much more manageable in testing. In contrast to the tests for single and separated agents, the execution of EVS for groups of interacting agents can, in general, not be executed without a setup phase, because the mocked up environment is increasingly replaced by real, interacting agents. The needed structures or parameter settings of the mechanisms have to be initialized in a setup phase. This reflects the fact that the SO mechanisms are sometimes based on evolutionary algorithms, e.g., genetic algorithms can be used for calculating new interaction structures in an agent group and therefore the needed edge weights have to be trained initially before the execution of a test case.

Subsequent to single agent and agent interaction the next step is-analogously to classical system testing-to test the fully integrated system. All mockedup components will be replaced by real agents. To minimize the overhead for setup we combine test cases so that they can be executed in sequence. In order to connect the scenarios it is necessary that the system state of a completed test case matches with the needed system state a next test case. We use search-based techniques to retrieve the matching scenarios. Furthermore, it is of interest to test interleaving scenarios in the fully integrated system to evaluate interdependencies of the self-* mechanisms within the CEI. To form these scenarios we combine agents with the following specifics: agents which know each other, agents which are able to communicate with each other, and agents which cooperate.

Besides developing test strategies we aim at establishing a set of coverage metrics which are focused on the coverage of the CEI. These metrics are reflecting our approach on testing SOAS by using the CEI. Standard coverage metrics make statements on code fragments, logical elements in the code, or on control/program flow coverage. For our testing approach the significance of classical coverage metrics is no longer sufficient. Based on the concepts of input space partitioning we describe the expressiveness characteristics for the input domain. The metrics based on partitioning consequently give evidence on the coverage of each region separated by the defined characteristics. As already stated above the most important characteristics for the mechanisms in the CEI are based on changing environmental situations and interactions between agents. Consequently, we will use these features to partition the input space. Based on this partitioning different kinds of combinatorial metrics can be retrieved and used for SOAS. The resulting metrics are able to cope with indeterministic, evolutionary structures of SOAS by benefiting from the CEI concepts.

Conclusion & Outlook

We outlined an approach to cope with the complexity which arises from the flexibility of SOAS. For this purpose, we briefly introduced the architectural pattern called CEI that enables systematic, (semi-)automatic testing of SOAS. The concept of the CCB is used to form EVS. We generate these scenarios to accelerate the system to adapt and reorganize to new situations in order to investigate the CEI. To make a statement about the adequacy of the performed tests and to select concrete test cases, we introduced metrics in the context of the CEI. Overall, this constitutes a research agenda towards testing self-organizing, adaptive systems.

Fig. 1 .

 1 Fig. 1. Schematical state-based view of the corridor of correct behavior and the different phases of testing SOAS. INVCEI is the conjunction of all constraints of the system controlled by the CEI.


Miroslav Bures
email: buresm3@fel.cvut.cz

Change Detection System for the Maintenance of Automated Testing

Keywords: Test Automation, Automated Detection of Change, Maintenance of Test Scripts, Better Efficiency, Traceability, Change Management. 1

Maintenance of automated test scripts is one of the important factors leading to success and return of investment of the test automation projects. As the key prerequisite to maintain the scripts correctly, we need to be informed about all relevant changes in the project scope, specification or system under test to be able to reflect them in updates of the test scripts. In this paper we introduce a concept on how to track these changes in semi-automated way with acceptable additional effort. The proposed solution is based on automated detection of changes in test management and requirement management tools, combined with optional manual inputs and automated scanning of changes in system under test user interface.

INTRODUCTION

Automated testing represents a promising concept, how to organize the software testing more efficiently. By automation of repetitive, manual (and often intellectually uninteresting) tests, we can invest human effort better in testing of advanced combinations, risk-based testing or error-guessing techniques to generally increase the confidence, the system is tested well. Why the potential of automated testing is used only partially today?

One of the major issues is expensive and inaccurate maintenance of the created test scripts, when the system under test (let us use abbreviation SUT further on) is changing. This is a frequently reported issue, for example [START_REF] Rafi | Benefits and limitations of automated software testing: Systematic literature review and practitioner survey[END_REF] or [START_REF] Dustin | Implementing Automated Software Testing[END_REF].

Also a recent survey we have performed in the Czech Republic among 28 professionals in test automation (currently going to be published), confirms, that the maintenance of the automated test scripts is the most important issue influencing the return of investment (let us use abbreviation ROI further on).

This issue deserves our attention. By enhancing and optimizing of test automation methods, we make the ROI of this technology more probable and earlier. Process of maintenance of the automated test scripts starts with the identification of the scripts, which have to be updated, when the SUT changes. A simplified view on this process is outlined in Fig. 1. When prepared manually with insufficient documentation of the changes in source specification or system under test, the set of test scripts identified to update can be incomplete. It can also contain scripts, which are not needed to be updated. This results in overhead and possible wrong update of the scripts.

RELATED WORK

Maintenance of the test scripts has been addressed in literature by various approaches, in which we can basically identify two major streams. The first principal approach is based on a modelling work, where a system organizing automated tests to particular structure or taxonomy is presented, for instance [START_REF] Xie | Using a Pilot Study to Derive a GUI Model for Automated Testing[END_REF].

Although well structured organization of the test scripts can increase the efficiency, a general problem of the proposed models is that they are often not sufficiently flexible to fully adapt to real projects. Various states of test scripts organization and also technological limits on various diverse projects are often challenging the pure modelling-based proposals.

The second approach is based on a traceability often combined with a structuring framework. The idea of traceability is essential here. Generally the maintenance is easier, when we capture and maintain the links connecting the requirements, parts of design documentation, features of the implemented SUT and mainly the respective test scripts. Further in the text, we will be referring to this traceability system. For our purpose we have adopted and extended a generally accepted standard BDTM (Business Driven Test Management) [START_REF] Van Der Alast | TMap Next: Business Driven Test Management[END_REF] from TMap Next methodology [START_REF] Koomen | TMap Next for result-driven testing[END_REF]. In the previous work we can find also examples of traceability focused on structuring of the test scripts, for example [START_REF] Haswell | System, method, and article of manufacture for test maintenance in an automated scripting framework[END_REF].

The topic of change management has been also a subject of many studies, for instance [START_REF] Ibbs | Project Change Management System[END_REF], nevertheless a combination of change management and detection system with a system for the maintenance of test scripts is a topic not sufficiently covered in literature. We approach this key area as suitable subject of our research.

PROPOSED SOLUTION

Our solution focuses on two areas, where we can enhance a process of identification of the scripts to be updated: [START_REF] Rafi | Benefits and limitations of automated software testing: Systematic literature review and practitioner survey[END_REF] tracking the changes systematically to provide the test script developers with all relevant information for the update and (2) detect changes in the system under test automatically to give the test script developers additional information which can be used in the identification of the scripts. For these both tracks, we are using a model of traceability, which we explain later on.

Let us start with the first part, the systematic tracking of the changes in the specification. In accordance with our experience on usual software development projects, testing sub-team preparing the test scripts is not usually systematically informed about all relevant changes in the scope by a design team or by the project manager. For this reason, we propose a system to help all involved parts to reduce an overhead with collecting the relevant information and increase its accuracy.

The second part, automated detection of changes in the user interface, combines with the previous part. The aim is to have another source of reliable information on what has been changed in the SUT. In this stage, we limit our proposal to automated testing based on the simulation of user's actions in the front-end part of the SUT. With this focus, changes of SUT front-end bring essential information we need for update of the automated test scripts (which are using location of front-end elements to exercise test steps by them). Further on in this paper let us elaborate the first part, the systematic tracking of changes. The second part is currently in a stage of the conceptual design with aim to employ already existing solutions, if any of them will suit our purpose.

MODEL OF CHANGE TRACEABILITY

As we have introduced the idea of our enhancement, let us explain the basis on which the solution is based on. The first part of the model (Fig. 2) depicts mutual relations between specification, its changes, a part of changes that is known to test designers, the system under test, test scripts and their coverage and regression caused by changes (defects introduced to the other part of the system by implementing the changes). By DELTA we mean the change to be implemented. If the project organizes its change management properly, all DELTAs should be exactly specified by formal change requests. Nevertheless, the situation on many projects differs from this ideal and we have to find a solution which can deal with such a situation efficiently.

In our proposal we further focus on the following parts of the model: A set Complete delta (CD) represents all changes in the specification (formalized or existing in the minds of the software development team) which arises on the project in a current iteration. A common situation is, that the test design (or test maintenance) team has information only about the part of these changes, a set KD in the model. The aim of our proposal is to make the sets CD and KD equal (or much more the same) with a minimal effort. Then, the changes should be propagated to the System under test by the development sub-team (a set ID) and also to the updated automated test scripts by the test design team (a set IS). The reduction of the difference between CD and KD then significantly contributes to the accuracy of update of the IS. And together with this, we need to support the update process also from another line: a traceability of the changes to automated test scripts.

As we have mentioned already, for the test management purposes, it is generally very productive to organize the information on the project to be able to track, which requirements are designed by which part of design documentation, implemented by which features of the system under test and, mainly, covered by which test scripts. We have adopted this general concept, described for instance in BDTM [START_REF] Van Der Alast | TMap Next: Business Driven Test Management[END_REF] further for change identification and propagating the changes to automated test scripts. The principle is depicted in the Fig. 3. In addition to the BDTM, we emphasize more explicitly links to company business processes, which help us to work with this source of changes and allows us to align more clearly and exactly with the business part of the organization. Moreover, we have added the system of script organization, which represents taxonomy, name conventions, and physical organization of the automated test scripts, including optional organization of the test scripts by their reusable parts.

IMPLEMENTATION AND EXPERIMENTS

In the current stage of our solution, we are handling three possible sources of changes in the project:

(1) Requirements possibly stored in a test management tool. Current tools are offering functionalities for storing the requirements. We are detecting a change by loading the set of requirements several times as the project proceeds and are comparing them. The second possibility is a simple import of information on requirement change from the tool.

(2) Requirements stored in a separate requirement management tool, varying from a simple issue tracking tools, which can be used to capture and formalize the requirements, for example Redmine, to a specialized modelling tools, for example Sparx Enterprise Architect. Here, a process of change detection and import is the same as in the previous case.

(3) Changes detected directly by members of the test automation team. This is an important source of information, which has to be processed. The test designers can add and update this information in the traceability tree by a special front-end application.

An overview of the architecture is introduced in Fig. 4. The system is based on a shared repository, the Traceability data storage, whose core is the traceability tree, the model described in the previous chapter.

For the variants ( 1) and ( 2), we gather the data by specialized connectors, which are adapted to the particular tools. A side effect of the solution is a possible consistency check between the various systems storing the requirements, if there are more of them co-existing on the project. Then, the data aggregator and analyzer transform the data to the traceability structure. Currently, the system is in detailed design and implementation. The conceptual parts have been verified by simulation on real data in a SW development company, where a sufficient set of automated test scripts is available. We have compared a time needed to identify the changes to update the automated test scripts manually and its possible accuracy with a thorough detailed simulation, testing how this overhead and accuracy would be changed, when using the proposed concept. In this particular case, taking all initial overhead in account, time to identification would be reduced by 40% one year after roll-out of the proposed solution (in the situation that the test designers are really detecting the changes, not simply ignoring them). Then, changes not reflected in test design by lack of information or human mistake would be reduced by 85% in the same period, which is significant. This result encourages us to continue with implementation to get feedback from more experiments, despite the fact that in productive run we expect this result being lower due to overhead which can arise.

CONCLUSIONS AND FUTURE WORK

Our proposal aims to increase efficiency of automated testing by focusing on its key issue negatively influencing it: maintenance of the automated test scripts, particularly on its sub-problem, detection of change which we need to propagate in automated test scripts maintenance.

Our approach is based on automated detection of changes form design or test management tools, where the relevant information is stored, in combination with the support for test scripts maintenance team to propagate other information they acquire during the project meetings or communication on general. The main idea behind this concept is to aggregate possible all sources of information available and perform that with minimal effort and overhead.

The results of the first simulation on real data and also an initial feedback from various test managers and engineers in the Czech Republic leads to the conclusion that the proposed concept deserves further evolution and application on the several test automation project to refine and optimize the proposal in the upcoming period.

Fig. 1 .

 1 Fig. 1. Simplified process of identification of automated test scripts to update.

Fig. 2 .

 2 Fig. 2. Basic components of the conceptual model of the change traceability.

Fig. 3 .

 3 Fig. 3. The model of the change traceability: tracking metadata part.

Fig. 4 .

 4 Fig. 4. Conceptual schema of the solution.


Khaled El-Fakih
email: kelfakih@aus.edu

Tariq Salameh

Nina Yevtushenko
email: ninayevtushenko@yahoo.com

On Code Coverage of Extended FSM Based Test Suites: An Initial Assessment

Keywords: Extended FSM test suites, test coverage, case study

In this paper, we present an assessment of the fault coverage of several Extended FSM (EFSM) based test suites. More precisely, EFSM specifications and their corresponding Java implementations are considered. Mutants of these implementations are derived using the standard arithmetic, conditional, and relational mutation operators. The fault coverage of test suites derived by different EFSM based strategies are evaluated and obtained results are summarized.

Introduction and Summary

Extended Finite State Machines (EFSMs) provide a rigorous approach for the development of functional tests for reactive systems, protocols and software. As an EFSM specification expresses both the data-flow and the control-flow behavior of a system, test derivation from an EFSM can be done using traditional software test selection criteria, such as the well-known All-Uses criterion, or using other criteria such as the derivation of test suites (TSs) that cover all EFSM mutants with single transfer faults, called STF TS, or a test suite, with one test case, called Transition Tour (TT), that traverses each transition of the specification, or a test suite, called DSTS, with tests that for each transition of the specification, the test suite includes input sequences that traverse the transition appended with a set of input sequences that distinguish the ending state of the transition from all other states of the machine. Another possibility for test derivation is to randomly derive a test suite with one test case of a particular length, for example, a test case with the same length as an All-Uses test suite [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF], called Random All-Uses, or as investigated in this paper, the derivation of a test case of the same length as a DSTS test suite, called Random DSTS. In [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF] it is shown that a test suite that covers All-Uses may not detect all STF mutants of the EFSM specification and a test suite that covers all STF mutants of the specification may not satisfy the All-Uses criterion of the specification, etc. Thus, an empirical study is needed to assess the coverage of these test suites. For evaluating the code fault coverage, in this paper, four known EFSM specifications and corresponding Java code implementations are considered. Then All-Uses, STF, TT, DSTS test suites are derived and the coverage of these test suites is calculated using mutants of the Java implementations where code mutants are derived using the traditional arithmetic, logical, and conditional operators [START_REF] Ma | MuJava: An automated class mutation system[END_REF].

Major contributions of the conducted experiments can be summarized as follows:  All-Uses, STF, and TT test suites provide comparable (fault) coverage.  DSTSs outperform all other considered test suites.  Random-All-Uses and All-Uses test suites provide comparable coverage where DSTS test suites slightly outperform Random-DSTSs.  Test suites coverage of conditional faults is significantly higher than their coverage of mutants with arithmetic, logical, or relational faults.  Test suites coverage of mutants with relational faults is much less than that of the coverage of mutants with arithmetic, conditional or logical faults.  All-Uses and TT test suites both achieve comparable coverage of mutants with arithmetic faults; however, STF test suites have significantly lower coverage of arithmetic faults than All-Uses and TT test suites.  All considered test suites provide comparable coverage of conditional faults, also all test suites provide comparable coverage of logical (or relational) faults.

Empirical assessment studies related to code based data-flow, control-flow, mutation testing, and some specification based test selection criteria are studied in many papers which are mostly summarized in [START_REF] Jia | An anaylsis an survey of the development of mutation testing[END_REF] and [START_REF] Mathur | Foundations of Software Testing[END_REF]. For specifications modeled as EFSMs, a preliminary assessment of STF, TT, All-Uses, All-Predicates, double transfer faults and some random test suites has been recently presented in [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF]. The assessment is done based on the coverage of the test suites of EFSM mutants of the specification with single and double transfer faults. In this paper, unlike [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF], the considered test suites are assessed in terms of their coverage of code mutants of implementations of these specifications. Thus, the work allows us to compare the coverage of considered test suites w.r.t. known code based types of mutants. Further, in this paper, DSTS test suites are also considered in the assessment and the results show that such test suites outperform all other considered test suites. Finally, it is worth stating that the results obtained here are rather different than those in [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF]. For example, in [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF] it is found that All-Uses, TT, and STF test suites do not provide comparable coverage of EFSM mutants with single or double transfer faults while in this paper these test suites achieve comparable coverage of code mutants.

Preliminaries

The EFSM Model: Let X and Y be finite sets of inputs and outputs, R and V be finite disjoint sets of parameters and context variables, respectively. For x  X, R x  R denotes the set of input parameters and D Rx denotes the set of valuations of the parameters over the set R x . Similarly, for y  Y, R y  R denotes the set of output parameters and D Ry denotes the set of valuations of the parameters over the set R y . The set D V denotes the set of context variable valuations.

An EFSM [START_REF] Petrenko | Confirming configurations in EFSM Testing[END_REF] M over X, Y, R, V with the associated valuation domains is a pair (S, T) where S is a finite non-empty set of states and T is the set of transitions between states in S, such that each transition t  T is a tuple (s, x, P, op, y, up, s), where, s and s are the start and final states of the transition t, x  X is the input of transition t, y  Y is the output of transition t, P and up, op are functions defined over context varia-bles V and input parameters as follows:

P: D Rx  D V  {True, False } is the predi- cate of the transition t; up : D Rx  D V  D V is the context update function of transi- tion t; op : D Rx  D V  D Ry is the output parameter update function of transition t. A context variable valuation v  D V is called a context of M. A configuration of M is a tuple (s, v)
where s is a state and v is a context. Given input x and the input parameter valuations, a (parameterized) input is a tuple (x, p x ), where p x  D Rx . A sequence of inputs is also called an input sequence. An output sequence can be defined in a similar way. In this paper, hereafter, we consider deterministic complete EFSM specifications, i.e. for each input sequence there exists exactly one corresponding output sequence. If an EFSM is partial then a complete version of the machine is obtained by appropriately augmenting the machine will transitions with the null output.

Assume that EFSM M is at a current configuration (s, v) and the machine receives an input (x, p x ) such that (v, p x ) satisfies the guard P of an outgoing transition t = (s, x, P, op, y, up, s´). Then when receiving the input (x, p x ), the machine executes the update statements of t; produces the (parameterized) output where parameter values are provided by the output parameter function op, and moves to configuration (s´, v), where v = up(p x , v). Thus, such an execution of transition t can be represented as (s, v) -(x, p x )/(y, p y ) -> (s´, v´), where op(p x , v) = p y . Such a transition can also be written as ((s, v), (x, p x ), (y, p y ), (s´, v´)).

It is well known that not each transition with the start state s is executable at any configuration (s, v). A path is a sequence of consecutive transitions (s 1 , x 1 , P 1 , op 1 , y 1 , up 1 , s 2 )…. (s l , x l , P l , op l , y l , up l , s l ). A path is feasible or executable if there is a sequence of (executable) transitions (s 1 , v 1 ) -(x 1 , p x1 )/(y 1 , p y1 ) --(x l , p xl )/ (y l , p yl ) -> (s l , v l ) in EFSM M starting from configuration (s 1 , v 1 ). The input/output projection of such an executable path is the sequence of input/output pairs (x 1 , p x1 )/(y 1 , p y1 ) .. (x l , p xl )/ (y l , p yl ) and is called a trace of M starting from configuration (s 1 , v 1 ).

A test case is a (parameterized) input sequence of the EFSM specification. A test suite (TS) is a finite set of test cases. The length of a test suite TS is the total length of its corresponding test cases.

EFSM Based Test Suites:

Single Transfer Faults (STF) Test Suites: Given an EFSM M, a transition t = (s, x, P, op, y, up, s´) of an EFSM IUT M´ has a transfer fault if its final state is different from that specified by M, i.e., M´ has a transition (s, x, P, op, y, up, s´´), s´´ s´, s´´ S. Such M´ is a mutant of M with a transfer fault. EFSMs M and M´ are distinguishable if their initial configurations are distinguishable by an input sequence (or a test case) . In this case, we say that  kills M´. A test suite, called a STF test suite, covers single transfer faults of M, if for each mutant of M with a single transfer fault that is distinguishable from M, the test suite has at least one test case that kills such a mutant.

Transition Tour (TT) Test Suites: A TT test suite of M is an input sequence that starts at the initial configuration of M and traverses each transition of M.

EFSM Flow-Graph Based All-Uses Test Suites: All-Uses test suite is a set of test cases of EFSM M that cover the All-Uses of each context variable and every parameterized input of M. Such a test suite can be derived directly from M as illustrated in [START_REF] Bourhfir | Test cases selection from SDL specifications[END_REF] or from a flow-graph representation of M as illustrated in [START_REF] Ural | Test generation by exposing control and data dependencies within system specifications in SDL[END_REF].

Distinguishing Set Test Suites (DSTS): An input sequence  ij is a distinguishing sequence for states s i and s j of M if  ij distinguishes each pair of configurations (s i , v) and (s j , v), v, v  D V , of M. M is state reduced if each two different states of M are distinguishable. Given state s j  S of a state reduced EFSM M with n states, a set W j of input sequences is called a distinguishing set of state s j , if for any other state s i there exists a sequence   W j that distinguishes states s i and s j . Given distinguishing sets W = {W 0 , W 1 , .. , W n-1 } of states of M, a Distinguishing Sets Test Suite (DSTS) is a set of test cases that satisfies the following property. For every transition t = (s, x, P, op, y, up, s´) of M and each   W j , the TS has the input sequence .(x, p x )., where is the input sequence that takes M from the initial configuration to a configuration (s, v) such that (v, p x ) satisfies P of t.

Assessment Methodology, Results, and Further Work

We consider four known EFSM specifications, namely, complete EFSM versions the Initiator and Responder of the INRES protocol, the SCP, and the Cruise Control. The method has three steps. In Step 1, for each considered EFSM specification, all EFSM mutants of M with STF faults are derived and a corresponding STF test suite (with optimal or near optimal length) is derived as illustrated in [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF]. Moreover, for every specification, a corresponding flow-graph representation annotated with definitions and uses of variables is constructed and then a corresponding All-Uses test suite is derived from the obtained flow-graph as illustrated in [START_REF] El-Fakih | On studying the effectiveness of extended finite state machine based test selection criteria[END_REF] based on related work [START_REF] Ural | Test generation by exposing control and data dependencies within system specifications in SDL[END_REF]. In Step 2, three corresponding Java code implementations are developed by three different software engineers, based on the EFSM specification and its textual description, under the following coding rules. State variables cannot be explicitly or implicitly introduced in an implementation, for example, no state variables and no flags indicating state variables can be used; moreover, no labels and no Go-to statements can be used. In addition, names of context variables, inputs and outputs with their parameters of the EFSM specification should be preserved in a code implementation. Each implementation should be implemented as one function that inputs a string separated by a delimiter "," representing an input sequence to the function and returns as an output a string representing the output response of the implementation to the input sequence. A Reader/Writer class is used in all implementations that handles reading/writing the input and the output strings in order to separate reading and writing outputs from the function that implements the specification and thus, code mutants are only derived from the function that implements the specification. We note that before deriving mutants, each Java implementation is thoroughly tested using all the considered test suites written in JUnit. In Step 3, 1-Order Java code mutants are derived using the Java arithmetic, relational, conditional, logical-shift, and assignment operators shown in List 1. As usual, 1-Order code mutants are considered to alleviate problems related to the coupling effect of using N-order mutants, when N > 1. Afterwards, the fault detection capabilities (fault coverage) of each considered test suite of a given EFSM specification is measured as (J killed / J Mutants )×100, where J Mutants denotes the number of derived mutants of the Java implementation and J killed is the number of these mutants killed by the given test suite. MuClips [START_REF]MuClipse -Mutation Testing tool for Eclipse[END_REF], MuJava [START_REF] Ma | MuJava: An automated class mutation system[END_REF], and JUnit are used for the automatic derivation of mutants, execution of test suites, and for determining fault coverage. Fig. 2 shows the coverage of all considered test suites using arithmetic, conditional, logical, and relational operators. According to these results, there is a significant difference between the coverage per mutation operator, for example, the coverage of conditional faults is 15.3, 23.5, and 32.5 percent higher than the coverage of mutants with arithmetic, logical, or relational faults. In addition, the coverage of relational faults is much less than the coverage of mutants with arithmetic, conditional and logical faults. Fig. 3 depicts the coverage of each test suite per each mutation operator. According to these results, it is clear that there is a huge difference, approximately by 16 percent, of the coverage of arithmetic faults by the STF test suites in comparison with the All-Uses and TT test suites. As expected, the All-Uses (data-flow based) test suites coverage of arithmetic faults is higher than that of STF (control-flow based) test suites; however, we were surprised that TT test suites provide comparable (even slightly higher) coverage of arithmetic faults as the All-Uses test suites. All considered test suites provide comparable coverage of conditional faults. Also, all test suites achieve comparable coverage of logical (or relational) faults.

List 1 .

 1 Selected Mutation Operators [4]: (AORB) Arithmetic Operator Replacement, (AORS) Arithmetic Operator Replacement-Shortcut, (AOIS) Arithmetic Operator Insertion -Shortcut, (AOIU) Arithmetic Operator Insertion -Unary, (COI) Conditional Operator Insertion, (COD) (Conditional Operator Deletion, (LOI) Logical Operator Insertion. Results: This part contains the results of all conducted experiments. Fig. 1 includes the coverage of the All-Uses, STF, TT, and DSTS test suites. These results clearly show that the All-Uses and STF have almost the same coverage, TTs slightly outperforms (approximately by 2%) All-Uses and STF test suites. However, DSTSs outperform all other test suites by at least 5%. This pattern is almost the same for each considered example. These results clearly show the importance of using state identifiers based test suites in EFSM based test derivation.

Fig. 1 . 2 .Fig. 3 .

 123 Fig. 1. Coverage of test suites Fig. 2. Results per mutation operator