{'fraction_non_alphanumeric': 0.023688885964335066, 'fraction_numerical': 0.0058564190300717245, 'mean_word_length': 4.7394259818731115, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Automatic Test Case Generation Method based on SysML Activity Diagram

Model-Based Systems Engineering (MBSE) is a new method to engineer the modern large, complex systems. MBSE has a good guarantee for system reliability and it can improve the efficiency of system development. So, MBSE has received extensive attention from academia and industry. SysML is an auxiliary language for MBSE. SysML activity diagram can model the behavior of the system. In this paper, we use SysML activity diagram to generate test case. There are two main things in our work. One is that we have designed an automated SysML activity diagram test case generation method. Second, we develop a test case generation tool to support related applications in the industry.


Introduction
People prefer to use Model-Based Systems Engineering (MBSE) instead of traditional software engineering to engineer the modern large, complex systems. MBSE [1…3] applies the modeling method into the system engineering and uses the model to support activities such as system requirements, designs, analysis, verifications and confirmations. A MBSE methodology is used to support a series of related processes, methods and tools for complying with the laws of MBSE. Systems Modeling Language (SysML) is a support language to using MBSE. SysML [4,5] is a graphical language defines semantics for the structure, behavior, requirements and parametric models of the system.
Model-Based Testing [6…8] is an important part of quality assurance in MBSE. As the complexity of system grow, more and more time and manpower are required for testing. Manual testing is so labor-intensive and error-prone that it is necessary to develop automatic testing techniques in some circumstance. In Model-Based Testing, test case derived from a model can detect bugs in deep paths and guarantee test case coverage requirements. So, Model-Based Testing is an effective way to improve test efficiency and reduce test costs.
A lot of researches have been done on Model-Based Testing and test case generation method. Chen [9] using a modified DFS (depth-first search) algorithm to generate a set of paths from the Activity Diagram according to the simple path coverage criteria. Then they obtained the minimum set of test cases by comparing the set of paths obtained in the previous step with the execution traces obtained by running the source program with random test cases. However, this method may not meet the test sufficiency requirement. Wang [10] proposed an approach based on Gray-Box method to generate test cases from UML Activity Diagrams. However, they gave no method to automatically generate test  [11] proposed a model called ITM. Activity diagrams can be transformed into ITM for testing. The advantage of using ITM is that it can simplify the process of extracting and analyzing test scenarios based on the coverage criteria. However, it also has limitations on processing activity diagrams with complex concurrent structures. Yin [12] proposed an algorithm to transform unstructured activity diagram into a model called IBM. Compared IBM with unstructured activity diagrams, IBM generates test case more convenient. However, in the process of model transformation, the semantics of the activity diagram changed, some scenarios have changed and may cause other problems.
In this paper, we design a method to generate test case automatically from SysML activity diagram. The previous research of Model-Based testing mainly focused on UML models and there is not a lot of research achievement on SysML models. However, SysML can be applied to modeling for complex systems, especially embedded systems. Therefore, we chose SysML as research field.
By summarizing the existing research results, we found that existing test case generation algorithms base on SysML or UML have some limitations. When the structure of the activity diagram is complex, these algorithms are not feasible, the generated test case set does not meet the sufficient requirement. Moreover, the existing research results are difficult to apply to practice, resulting in the lack of automated tools in the industry. In this paper, we aim at the automated test case generation method base on SysML activity diagram. This method automatically analyses the structure of the activity diagram and generate test case. The generated test case set guarantee the sufficient requirement. Based on this method, we have also developed a tool called SysML Activity Diagram Test Case Generation (SATCG) tool to support related applications in industry that can improve test efficiency.
The paper is organized as follow: In next section, we introduce SysML activity diagrams and present four test adequacy criteria for SysML activity diagram. In section 3, we design an algorithm to analyse the structure of activity diagrams automatically. In section 4, we introduce the test case generation method and two test path generation algorithms used in the method. In section 5, we introduce the tool SATCG and run a case to show the test case generation process. The related works and some conclusions are given in the last section.

Basic concepts and definitions
In this section we introduce the activity diagram formal definition and present three test adequacy criteria. There are two types of edges: control flow and object flow. Control flow edges represent the process of executing token passing in AD and object flow edges are used to show the flow of data between the activities in AD. Edges defines the relationship between nodes such that:

Test case formal definition
Test cases derived from activity diagrams are considered as an abstract test suite. A system under test can not executed abstract test suite directly. In activity diagram, the test case is a sequence of nodes form the InitialNode to the ActivityFinalNode, indicating the running process form the beginning to the end of the system. The test case is defined as follow: In this formula, ∈ , ∈ .

Test adequacy criteria
As an essential part of any testing method, test adequacy criterion specifies the requirement of a particular software testing. The adequacy criteria of activity diagrams are based on the matching between the paths of activity diagrams and the program execution traces of the implementation codes. They mainly deal with the coverage of elements in activity diagrams. The definition of test adequacy is given in [13] as a measurement function. To generate test cases for an activity diagram, we consider the following three test adequacy criteria: • Node Coverage requires all nodes in the activity diagram be covered.

•
Edge Coverage requires all edges in the activity diagram be covered.

•
Basic Path Coverage requires all basic paths in the activity diagram be covered.

Activity diagram structure analyse
Due to the variety types of activity node types, we can model complex scenes, which leads to the complexity activity diagram structure. As shown in Figure 1, the activity diagram in Figure 1 has a complex structure. The conventional method treats the activity diagram as a directed graph. The test path generation algorithm is based on the Depth-First Search algorithm. Such a path generation algorithm has certain limitations: it can't generate concurrent structure's test case well. Our goal is to propose a generalized path generation method that can handle activity diagrams of many complex structures. Based on this goal, we must first fully analyse the structures of the activity diagram.

Loop module
As shown in Figure 3，the loop module is like a while loop statement in the programming language. The nodes in the loop module will execute multiple times.

Concurrent module
In SysML activity diagrams, there are four different concurrent structures. There is a fork-join structure in Figure 4(a). Fork-join means all concurrent threads must be executed and summarized before proceeding to the next activity node. The fork-merge structure is shown in Figure 4(b). For these concurrent threads in fork-merge structure, if one of the concurrent thread finishes executing, others thread will be interrupted. As long as one concurrent thread finishes executing, the activity diagram will continue to execute.
The third type is fork-flowfinal structure. As shown in Figure 4(c), one concurrent thread has a FlowFinalNode, this concurrent thread only has a concurrency relationship with other concurrent threads. The execution of the activity diagram is not affected by this thread.
The last type is multi-starting structure. As shown in Figure 4(d), there are two nodes with zero indegree. These zero in-degree nodes are usually ReceiveSignalNode. These zero in-degree nodes have a concurrent relationship with other nodes in the activity diagram.

Activity diagram modular algorithm
We found that the basic structure in the activity diagram are decision module and loop module. We can use the basic structure to decompose the activity diagram. The decomposed activity diagram consists of several basic structural modules. To analyse the structure of activity diagram automatically, we designed an activity diagram module algorithm. The algorithm takes activity diagrams as input and output as a branch set.
We use the SysML model as input, then convert the model into a directed graph and we use adjacency lists to store the directed graph.

8.
FindSubBranch(subBranch i ); 9. End; We use Algorithm1 and Algorithm2 to analyse the AD's structure. Algorithm 1 puts the nodes that InitialNode and the InitialNode can reach into a branch, then searches for other zero in-degree nodes. Next, Algorithm 1 puts a zero in-degree node into a new branch until all zero in-degree nodes in activity diagram are added to the branches. But the BranchSet we get from Algorithm 1 may not be the final result, due to the branch may contain concurrent structures. Algorithm 2 will be called to find the sub-branch until the branch cannot be modular, so Algorithm 2 is an algorithm of recursive structure. When we create a new branch, we will record the father branch and branch level of the branch. If the branch levels of the two branches are equal and the parent branches are the same, then two branches have a concurrent relationship.
We use Algorithm 1 and Algorithm to analyse the activity diagram in Figure 1. The results is shown in Table 1. We can get 6 branches, through the father branch and branch level, we can find branches with concurrent relationship. If the parent branches of the two branches are the same and the branch levels are equal, then the two branches have concurrent relationship. In this activity diagram, there are three pairs of branches with concurrent relationships: branch1 and branch2, branch3 and branch4, branch5 and branch6. The concurrency types of these three pairs are multi-starting, fork-flowfinal, fork-join.

Test case generation
In this section, we will detail the steps to generate the activity diagram test path, then introduce the test path algorithm of basic structure and concurrent structure.

Test case generation method
We proposed an automatic test case generation method. Test case set we get from activity diagram meet the test sufficiency requirements. This method describes the specific process of test case generation. The process can be divided into the following steps: • Step 1. We use Algorithm 1 and Algorithm 2 to analysis the structure of input activity diagram, we can get several modularized branches. • Step 2. Save modularized branches to two sets, set 1 store branches without child branches and set 2 store branches with child branches. • Step 3. Use basic structure test path generation algorithm to generate test paths for branches in set 1. • Step 3. Use concurrent structure test path generation algorithm to generate test paths for branches in set 1. • Step 4. For a branch in set 2, if the test path for all child branches of a branch has been generated, then generate test path for this branch. • Step 5. In set 2, generate test path for branches with concurrent relationship. Step 6. Jump to Step 4 until the test path for all branches is generated.

•
Step 7. Get the test case for input activity diagram. The basic structure test path generation algorithm and the concurrent structure test path generation algorithm are used in the process of generating test case. Through the result of the modularization of the activity diagram, we can know the relationship between the branches and use the corresponding test path generation algorithm to generate the test path of the branch. Next content we will detail the two test path generation algorithms. In Algorithm 3, loopCount is a list that stores the number of node traversal in the loop module. When the number of traversals of a node is specified, the number of entries of the loop module in which the node is located is limited. Usually, you only need to specify the number of traversals of one node in the loop module. If there are multiple loop modules in a branch, each loop module needs to specify the number of loop module entries. C(node) is a function that finds the number of traversals that the node is specified for. If the number of traversals for node is not specified, the function returns a value of ∞.

Concurrent structure test path generation
Algorithm 4 is used for generating test paths test path in concurrent structure. The algorithm is based on the idea of permutation, it can generate test paths for the four concurrent structures summarized above. The input to the algorithm consists of two paths, path1 and path2 and a concurrent type cType. Algorithm 4 Concurrent structure test path generation Input: path1, path2, cType path.add(node); 20. node = node.next;

End;
In Algorithm 4, the generated case paths are saved in concurrentPathSet. nodeA.next represents the next node of nodeA in path1. path1Final is the last node in path1, path2Final is the last node in path2. Procedure concurrentPathGeneration is a program that generates concurrent test paths for path1 and path2. Lines 5 and 9 in the algorithm are used to determine if path1 and path2 have been traversed. If the concurrent type is fork-merge, then the algorithm only needs to complete the traversal of one of path1 and path2. If the concurrent type is fork-join, both path1 and path2 need to complete the traversal. If the concurrent type is fork-flowfinal and the algorithm has completed the traversal of one path, if the path contains the FlowFinalNode, then the algorithm needs to complete the traversal of another path. If the concurrent type is multi-starting, then the algorithm only needs to complete the traversal of one of path1 and path2.

An automatic tool for test case generation
In the previous section, we proposed a test case generation method based on SysML model. In this section, we introduce the tool SATCG and run a case to show the test case generation process.

Tool introduction
SATCG is developed in Java. It takes SysML activity diagrams as input. The tool consists of the following modules: activity diagram pretreatment, test path generation, test path reduction, test data generation and test case generation.
Tool interface is shown in Figure 5.