Test Case Generation for Embedded Real-Time Software

Generating Test Cases for Embedded Real-Time Software

using Layered Activity Diagram

1

Prof. M. M. Ganeshwade

MIT College of engineering

Aurangabad, India.

Prof. Kirti Patil

MET’s BKC Institute of engineering

Nashik, India.

1

1

Abstract- The quality of software depends on the number of defects generated by the software and how it efficiently works. Software testing is a very important phase of software development life cycle. It is the process of finding defects by executing a program on a set of test cases and comparing the actual results with expected results. For generating the test cases, information regarding the implementation of system must be understood first, which can be taken from the models created in design phase. UML is widely accepted and used by industry for modeling and design of software and nowadays of embedded systems also. This paper presents a approach to generate the test cases from extended UML activity diagram for real-time embedded systems and prioritizing them to improve the efficiency and at the same time to reduce the high cost of the manual testing in design phase itself.

Keywords—SDLC, Software testing, Embeded real-time systems UML, Extended activity diagram.

1. Introduction

Software development life cycle mainly includes five phases: Requirement analysis, Design phase, Implementation, Testing and Delivery of product. To improve the quality and efficiency of product and to deliver the ‘RIGHT’ product in market maximum defects are recovered in testing phase itself. But why to wait up to testing phase? Is it possible to remove the defects in early phases of SDLC? Yes! Our approach will do it. It will be possible to test the system in the design phase itself. In the design phase we get the proper requirements and flow of the system. UML standards are very well known for creating the models of system. Past works of test case generation are mostly based on the software applications using different UML 1.x models. Our approach presents a novel method to generate the test cases automatically for the embedded real-time systems using an extended activity diagram model and test the system with mutation analysis by injecting faulty data. This approach will reduce the cost and effort of testing in the early phase of SDLC and Mutation analysis will improve the performance of system.

Nowadays, testing of embedded real-time systems is in boom. As the complexity and size of embedded real time software grow with every passing year, the time and effort required for adequate testing is growing at a very rapid rate. Test case design constitutes a large part of testing cost. It is generally agreed that manual testing is becoming a bottleneck and is a frequent cause of project delays especially for large programs. Therefore, automatic test case design has become important to ensure the quality of present day large embedded real time software and to contain the rapidly growing testing costs.

The rest of the paper is structured as follows: Section II reviews the related work. Section III explains extended activity diagram and embedded real-time system. Section IV explains the proposed approach. Section V comparison with previous work.

1. Literature survey

A lot of research is done using the different UML models. Cle´mentine Nebut [1] proposes automatic test case generation using Use case driven approach. In their approach, formalization of the requirements of a system is used to generate tests, in the context of object-oriented embedded software. Tests are evaluated in terms of statement coverage. M. Prasanna et al. and K.R. Chandran proposed automatic test case generation for object diagrams using genetic algorithm. Genetic Algorithm’s tree crossover has been proposed to bring out all possible test cases of a given object diagram with the help of banking example to improve the effectiveness of testing quality. Recently [2] they have introduced a novel method to generate automated test cases using class diagram with data flow approach. In this approach, the effectiveness of the test cases are evaluated by using a fault injection technique called Mutation Analysis. Nicha kosindrdecha, Jirapun daengdej [3] introduced a new test generation method, called “TGfMMD”, which aims to minimize cost and time while maximizing testing coverage. Paper introduces a new “3S” classification of test case generation techniques, Specification-based techniques, Sketch diagram-based techniques, Source code-based techniques.

Liu Xiaoming et al [4] have proposed their work in embedded software testing using symbolic execution. First translating the embedded program into an intermediate language program, which preserve all the necessary information from the origin embedded program and according hardware, then symbolic execute the intermediate language program to generate test cases automatically. Yin Yongfeng [5] proposed test case generation for embedded real time system using collaborative approach of extended class diagram, sequence diagram and activity diagram. And Amitranjan Gantait [6] proposed an approach for selecting test data based on analysis of the branch conditions of the decision nodes in the activity diagrams. Existing work have many approaches to automate the test cases from UML 1.x models. Therefore, there is a need for improvement of testing quality by considering activity diagrams using UML 2:0 and with higher level scope, that is, use case level for embedded systems.

The contribution of this project is thus to generate tests using extended UML 2.0 activity diagram for embedded real-time software and prioritizing the test cases that is cost effective.

III. Background

Extended activity diagram and Real-time embedded system

In this section, we present a few basic concepts and terminologies that are used in the rest of the paper.

The Unified Modeling Language (UML) is the industry-standard language for specifying, visualizing, constructing, and documenting the artifacts of software systems, as well as other non software systems. UML simplifies the complex process of software design, making a "blueprint” for construction, and is now the standard notation for software architecture [7]. The UML 2.0 includes fourteen kinds of diagrams, in this project only activity diagrams is used and analyzed. UML provides both the structural views and behavioral views of the system. Structural view includes class diagram, object diagram and behavioral view includes activity diagram, state chart diagram, sequence diagram etc. Activity diagram basically is used for business modeling, control and object flow modeling, complex operation modeling etc. Main advantage of this model is its simplicity and ease of understanding the flow of logic of the system. However, finding test information from activity diagram is a formidable task [8]. Reasons are attributed as follows: (a) activity diagram presents concepts at a higher abstraction level compared to other diagrams like sequence diagrams, class diagrams and hence, activity diagram contains less information compared to others, (b) presence of loop and concurrent activities in the activity diagram results in path explosion, and practically, it is not feasible to consider all execution paths for testing.

Starting with activity diagrams that contain a low level of detail called ‘high level’ or ‘upper layer’, which can span several business use cases. This gives a good overview of the chain of interactions between customers and partners and the business system. Later, more detailed in under layer steps the scenarios of business use cases can be described with activity diagrams. If a business use case is composed of several different scenarios, each is depicted in an activity diagram. Figure 1 gives summary of the constructs used in activity diagram.

Figure 1: Summery of constructs used in Activity Diagram

According to Kopetz, a real time computer system is a computer system in which the correctness of the system behavior depends not only on the logical results of the computations, but also on the physical instant at which these results are produced. As one of the object-oriented techniques, UML is basically suitable for real time system development. There are techniques within UML definition that are a natural fit for specifying and designing real-time systems. Use cases allow the designers to describe the way in which humans and external devices, interact with the system. Object sequence diagrams, describe for a given use case, the events which cause the interaction and the detailed system response, including timing. There are some main challenges in the design of real-time embedded system with UML, as follows:

• The definition of specific hardware elements and their characteristics;
• Specifying the time constraints at the object, task and hardware levels.
• Modeling the network.

Using the reference from [5] we are expanding the layers of activity diagram. Because of a complicated structure and concurrent processes in embedded system, testing becomes necessary. Here in embedded system core testing work is to verify the operation sequences of system. In this way, activity diagram is very useful to embedded software testing.

For better describing the complicated functions of embedded real-time system, we use layered activity diagrams in system function modeling.

• The uppermost layer activity diagram is the main work flow of SUT at higher abstraction level.
• The under layer activity diagrams expanded from active nodes of the upper layer activity are used to describe the sub-activity of SUT.

In this paper, we use the real-time extension of activity diagram to realize the dynamic modeling of test cases generation. The methods we use in extension are as follows. We add time labels to the description of actions in activity diagram as a supplement of attributes of action.

Def. 1: Atomic Function. The function can’t be decomposed and is determined and linear once being executed.

Def. 2: Combined Function. The function can be decomposed.

Def. 3: <Task> and <CombinedTask> Stereotype.

<Task> stereotype is used to describe the atomic function in activity diagram, while the <CombinedTask> stereotype is used to describe the combined function. Besides, we add tagged values to extend above two stereotypes.

• To <Task> stereotype, we use sequence diagram to describe the activity because the execution of atomic function is determined and linear. The definitions of added tagged values are as follows.

Task.ID = value //unique identification

Task.Period = value //period of task, 0 means timing

Task.StartTime = value//start time

Task.EndTime = value //end time

Task.Priority = value// priority

Task.Action={SequenceDiagram1}

//the activities described by sequence diagram

• To <CombinedTask> stereotype, we use use layered activity diagrams to describe the activity because the combined function can be decomposed.

The definitions of added tagged values are as follows.

CombinedTask.ID = value //unique identification

CombinedTask.Period = value //period of task

CombinedTask.StartTime=value//start time

CombinedTask.EndTime=value//end time

CombinedTask.Priority = value// priority

CombinedTask.Action={ActivityDiagrams}

//activities described by layered activity diagrams

Def. 4: Time Delay. In activity diagram, we use [Wait. time = value] to describe constrain condition of time delay.

Time delay is a null operation in fact and can be viewed as a waiting state. We define the time unit as millisecond owing to the reaction of embedded system is mainly in milliseconds.

Figure 2 shows that the activity b starts after c milliseconds when the activity a finished.

Figure 2: The description of Time Delay

Def. 5: Conditional Jump. During the testing process, some activities only can be activated when the previous activity is over and specific conditions have been satisfied. We use the method of adding conditional expression [Condition:Expression] on activity transfer to describe the conditional jump. In test cases generation, the conditional expression can be used as the precondition or post-condition of activities as showed in figure 3.

Figure 3: The description of Conditional Jump

IV. Proposed approach with a Case study

As shown in Figure 4,

Figure 4: Proposed Approach

Our technique is based on following steps-

a) Augmenting the activity diagram with necessary test information.

b) Converting activity diagram into activity graph

c) Identify all the activity flows in the activity graph

d) Prioritize the flows based on coverage of all transitions in the activity diagram

e) Generate the test cases.

f) Finally perform mutation analysis.

Figure 5 shows the example of work steps of passenger services, Upper layer activity diagram with proposed stereotype.

Starting with the Initial Node acceptance of the event passenger arrives sat check-in, and continues along the arrows of the control flow. The subsequent action passenger checks in means that at this point the activity ‘passenger checks in’ is processed. This is depicted in more detail in another activity diagram as is indicated by the ‘fork’ in the action symbol. If you follow the control flow, next you will come to a conditional branch or decision control flow can follow.

Figure 5: Example of Extended activity diagram with stereotypes

Otherwise, the passenger cannot fly and the task of passenger services is completed. This can be seen at the black dot with border—the activity final node.

After successful check-in you come to fork. All arrows that come from fork symbolize flows that are processed simultaneously. While the luggage is being loaded onto the airplane the passenger is boarding the airplane. At the fork the simultaneously processed flows are merged, meaning that only when the passenger is on the plane and the luggage has been loaded onto the plane, does the control flow continue below the join. In our example, one more action (7) and subsequent to that the final state (8) follow, meaning that after the passenger is on the plane and the luggage has been loaded onto the plane, the airplane can taxi toward the runway. You can see here that the last action airplane taxis toward runway is only defined as a single action as ‘”Task”, and all other are “CombinedTask” which need to elaborate in under layers more detail. Using the existing work from [8],

a. Augmenting the activity diagram with necessary test information.

To extract the information from activity diagram, we need to search all layers of activity diagrams and during the process of extracting , we should choose some value in the input data domain aiming at every input operation in activity, at the same time, we also should get the expected output from the analysis.

b. Converting activity diagram into activity

graph And

c. Identifying the flows

The algorithm of activity flow generation is as follows.

Firstly, we should set a stack to save the information of the nodes and migrations of test scenario and set a hash table to save the accessed migrations information which is started from some decision node in the activity diagram.

Secondly, we find the start node and copy it into the activity flow and save the current node to the stack which will be marked as NODE_A.

And then, we should check the migration information from NODE_A. There exist two cases for target node which will be marked as NODE_B.

 If the target node (marked as NODE_B) is a decision node, we should mark the accessed label of NODE_B as TRUE. To the next, we should choose a no-accessed path from decision node and mark the new target node as NODE_C. Now, we have got the migration (NODE_A->NODE_B->NODE_C) which will be copied into the activity flow and we should save all information of these nodes to stack.

Following that, we should copy the migration (NODE_B->NODE_C) into the hash table and mark the current node (NODE_C) as NODE_A.

 If the target node (marked as NODE_B) is not a decision node, we should copy the migration (NODE_A->NODE_B) into the test scenario and save all information of the two nodes to stack and mark the current node (NODE_B) as NODE_A.

Furthermore, the above step should be repeated until the end node is accessed. With popping up all information of nodes and migrations in turn from the current stack top to bottom, we will complete the extraction of one test scenario.

With repeating above steps, we can get all activity flows.

Following table shows the generated workflows:

Flow Id / Activity Flow
F1 / 1→2→3→4→9
F2 / 1→2→3→4→5→6→7→8

Table 1: Activity flows generation

d. Prioritize the flows

Here we are proposing a method to reduce the number of test cases without impacting the test coverage. If there is more than one combination of activity flows to cover the activity diagram, we use ‘weight’ of the flows to reduce number of test cases. Summary of our approach is as below:

• Find the minimum number of flows covering all the edges.
• If there is more than one combination (with same number) of flows covering all the edges we need to select the combination with highest flow ‘weights’.

We define weight of a flow to be the probability of execution of the activity flow. For our approach to work, we need to find the weights for all the flows in the activity graph. Once the flows are found as outlined in last section, these flows need to be sorted based on the weight of the flow. Business analysts or domain experts can directly assign it. Alternatively, it can be computed based on the weight of an edge, which needs to be entered in the activity diagram.