# CIPC: A Change Impact Propagation Computing Based Technique for Microservice Regression Testing Prioritization

Authors: Lizhe Chen; Xiang Yu; Ji Wu; Haiyan Yang
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Regression testing is the optimal technique that can be used in each iteration of microservice systems. However, regression testing prioritization is the only main method that gives better results. These techniques directly involve the processes of artifacts, data acquisition, analysis, and maintenance. The microservice systems have input data, which are difficult to obtain and control, while such processes are of high costs with impractical design. This paper gives a detailed study on testing prioritization technique, which is referred to as CIPC. As there are dependencies between services from API gateway logs, a novel CIPC algorithm is proposed, which is based on belief propagation. There are some rules that are directly affected by service changes. Therefore, the higher execution order of test case prioritizes CIPC, which is based on impact changes. Multiobjective prioritization algorithm is based on heuristic searching, in which sequence test cases are done by coverage. By evaluating the effectiveness of CIPC, the empirical study presents five microservice systems and four different techniques. The results describe that CIPC has improved fault detection rate with acceptable time and cost. The technique is more practical than typical artifacts, which are based on increments of system scales.


---

## Body

## 1. Introduction

Lightweight communication mechanism utilizes microservice due to its widespread design. Especially, this architecture pattern is widely preferred for cloud applications [1–3]. Additionally, the entire procedure assists in constructing and deploying microservice [4]. Through this mechanism, requirements of business expansion are completely satisfied.Furthermore, regression test is conducted in each cycle of microservice systems. Such test verifies whether former technical issues are fixed or not. Also identify any most probable obstacle during working or fixing [5]. However, a common approach for regression test is to rerun previously used cases, where it illustrates costs. Moreover, rapid repetition with numerous amounts of service is established, whereas the entire costs of repeated trial are assessed through this process. For instance, WeChat (social microservice system) offers thousands of amenities. Hence, this particular system might consume several months to perform the entire sort of regression assessments along with retest-all strategy [6]. Therefore, numerous techniques are practiced in order to optimize the system. Predominantly, to enhance trails efficiency and decrease overall expenses, several approaches are adopted. Such methodologies include prioritization, selection, and test suite minimization [7].Firstly, regression testing prioritization (RTP) deals with adjusting test cases in proper order. Through this procedure, a common goal is to evaluate desirable properties and improve fault detection rate [5]. Therefore, earliest spotted issue is kept on priority and run through whole system whether this is likely to be happen in other parts or not. As a result, a relationship is established between test cases and historical information. Moreover, artifacts or history data is incorporated in building relationship. Artifacts include specifications, strategy models, and code files. On the other hand, historical data compromised previous failure. Additionally, RTP procedure is composed of two-stage analysis and prioritization. In the analysis phase, historical data or artifacts are managed to retrieve evidence such as coverage, critical-rank, and change impacts, whereas prioritization phase and test cases are linked with information and arranged through former data. However, RTP practices consider that historical data is broad, reliable, and accessible. Furthermore, correlation amongst them is sustained through availability in continuous integration environments [8, 9].Although RTP based acquisition on data is difficult to initiate, still it is implemented for better response. Thus, a specific approach is applied to microservice regression testing. Practically, the system encounters three challenges while performing.(a)
Data AttainmentAs the microservice system works independently, it faces several issues while achieving artifacts and historical information from multiple teams. Thus, extra communication is acquired for gathering, which results in elevating the total cost. Additionally, the expense is increased through obedience with numerous security strategies.(b)
Data IntegrationHaving developments in methodologies, the procedure becomes more complex to integrate the data. Therefore, integrity, comprehensibility, and consistency of information are difficult. Consequently, the performance of RTP is severely affected.(c)
Sustaining RelationshipWith growth of system scale in uninterrupted environments, association amongst artifacts, history data, and test cases might become difficult to sustain. Due to large set of information, various issues hinder from building association between them.Hence, the above three main issues, which exist in RTP based techniques, are not practical in microservice regression testing.Furthermore, API gateway layer is a significant element of microservice systems, where it is utilized for centralized distribution of service requests [4]. Practically, in API mode, the gateway logs record the entreaties. However, requests from clients include applicant information, responder, time, and status code. For performance, bundles of statistical data are collected for further assessment. Additionally, attained requests submitted in API gateway logs are executed individually to prove service scheme dependencies. Moreover, regarding the system that is primarily based on dependencies, impact investigation is carried out, where the impact analysis depends on belief propagation strategy. Incase test cases are ranked on the basis of final output, and the above challenges can be governed easily. Thus, this motivates the approach, which is incorporated in paper. Change impact propagation computing mechanism is primarily taken from microservice regression test strategy CIPC.Initially, CIPC creates request-directed-graph (RDG) through proper counting frequency of invocations from API gateway logs. Secondly, change impact propagation is based on belief propagation algorithm. Additionally, the proposed algorithm is utilized to measure change impacts quantitatively from the RDG [10]. Thirdly, microservice experiment is represented as test path [11, 12], whereas test paths are matched in pairs based on results. Such comparison determines execution orders. Furthermore, a multiobjective prioritization algorithm based on heuristic searching is proposed. Thus, test path is prioritized by both service coverage and change impacts. Moreover, to estimate effectiveness of CIPC, experimental revisions are carried out. However, five systems are utilized to measure average percentage of fault detection (APFD) and time costs [5]. Beside this, four typical RTP techniques of three groups are nominated to match with CIPC such as artifacts-RTP, history-RTP, and control-RTP. Consequently, outcomes illustrate that CIPC enhances fault detection rate as compared with former procedures. Especially, less prioritization is observed in time-cost scenario by two magnitudes. Finally, measure escalates during continuous integration environment, where time-cost shows preferable level. This ensures system with reliable incomes of data.To sum up the introduction, leading contributions of this paper are as follows.(1)
Data utilized to prioritize test-cases are extracted from API gateway logs, while regression assessment evaluation phase information is collected from microservice.(2)
Change impacts are quantitatively calculated through mathematical approach.(3)
Single-objective and multiobjective prioritization are proposed to meet practical requirements.


## 2. Related Methodologies

### 2.1. Microservice Testing

Microservice testing comprises unit-testing, service-testing, and end-to-end testing [4]. However, unit testing is utilized to identify culpabilities in functions or classes. Additionally, this process is sustained by two experimental tools such as xUnit [13] and mockito [14]. In order to bypass user interference and rapid assessment, this service-testing is preferred. However, end-to-end testing focuses on behaviors of entire system to improve efficiency. Although several serious challenges were faced by this autonomous system, still service and end-to-end testing are designed to tackle them effectively. Particularly, this approach is concerned about researches and practices of microservice testing [4, 8], whereas test-cases in this research work include service and end-to-end based assessment.Furthermore, both procedures at the same interval involve multiple services and their invocations. So, high efficiencies are obtained through service and end-to-end analysis. For instance, consumer-driven based evaluation includes consumer, target, and stubbed-services [4]. Therefore, test cases of these two assessment possibilities are abstracted as self-possessed test paths of services, which are purely based on prioritization criteria [11, 12, 15–18].


### 2.2. Test Case Prioritization

Formal definition of regression testing prioritization problem is as follows:Definition 1.
(RTP issue).
Given:T, test-suite, PT, f, and set of all possible permutations of T, whereas f determines performance from PT to real numbers.
Problem: FindT’∈PT:(1)s.t.∀T″∈PTT″≠T′fT′≥fT″.
Definition1 illustrates main points of RPT. Objectives of equation focus on degree of qualitative model, where test cases satisfy prioritization strategies through designing function f, whereas “f, T” comparison-based sorting, heuristic searching, and algorithms approach exist [19].
Furthermore, RTP is emerging area in regression testing based research. However, artifacts procedures are distributed into two categories such as code and model based approaches [20, 21]. Firstly, code-based approaches principally deal with coverage information of test cases such as statement, branch, and path coverage [17, 22]. Such approaches involve source codes availability of system during analysis. Though multiple complex programming languages create challenges for microservice system, therefore, coding system depends on specific language to resolve the complexity of computing. Secondly, model-based methodologies establish association information amongst test-cases and models, whereas models are further integrated into system structures or system behaviors. This approach is utilized to prioritize test cases based on criticality, complexity, and defect density of models [23–25]. Hence, model-based methodology is more preferred than code-based techniques due to its practical viabilities. Beside these feasibilities, it also incorporates microservice system to be more dynamic, integrated, and consistent throughout the procedure.
In addition, several research works primarily focus on historical information specific scenarios. Research conducted by Azizi and Do [26] elucidates that test cases were ranked by changing historical data of artifacts in dynamic environment. However, sustaining changing trend of historical information is a difficult task in microservice systems, where location-based RTP procedure is recommended for embedded environment [27]. This technique emphasizes gravitation laws for high reliability after modification. Also, similarity-based RTP methodology is proposed for product line testing scenario [28]. Revision evaluated effectiveness of real and seeded fault detection in Ouriques [29]. Diverse prevailing RTP methods are compared to monitor the real-time efficiency of approach. Therefore, model-based analysis is compared to investigate influence of test-case on fault-detection rate. However, this approach is only preferable for specific circumstances. Generally, it is not applicable for all regression techniques in microservice regression testing.
With the advent of machine and deep learning approaches in recent years, numerous researchers applied these tactics to RTP [20]. The typical approaches are neural network based RTP approaches such as genetic algorithm and Bayesian network based RTP attitudes. Amongst them, methods based on neural network mainly extract features from system specifications [30]. Beside this, historical analysis records data to prioritize test cases [31]. Additionally, genetic algorithm approaches build some features such as module failure rate, code coverage, and optimum orders, whereas RTP tactics based on Bayesian network mainly combine white box information such as code-changes and code-coverage [32]. Generally, technological methodologies still count on codes, conditions, replicas, and historical statistics as inputs. Therefore, the system has numerous obstacles while performing acquisition, investigation, and sustaining as mentioned above.


### 2.3. Belief propagation

Belief propagation algorithm (BP) is a repetitive process for estimated interpretation based on graph structure. There are numerous applications of BP, which include forward propagation algorithm, Viterbi algorithm, decoding algorithms of low density parity check (LDPC), and turbo codes. Such methodologies are utilized for different sort of situation and scenario [10]. However, the core idea of BP algorithm is to transmit message in order to maintain communication through repeated iterations. Thus, it keeps updates confidence values of nodes. Generally, BP algorithm is as follows:(1)
Initialization: set the initial value of each node.(2)
Propagation: update all message values and node confidence values.(3)
Determining values are convergent. Incase standards are convergent, and inference results are obtained according to confidence values. Otherwise, we will jump back to step (2) and propagate iteratively.In recent years, studies on BP algorithm comprise application and optimization. According to its application, scholars predominantly focus on communication coding and signal processing. In order to reduce complexity of SCMA, dynamic edge assortment procedure based on BP algorithm is introduced. Through iterative calculation, range boundaries of nodes are detected [33]. However, nonlinear equalization method utilized neural network, where BP algorithm is applied to remove signal noises [34]. Additionally, for large-scale MIMO channel detection, belief propagation is used, which is purely based on deep neural network [35]. In optimization aspect, investigators primarily focus on implementation and convergence condition. Furthermore, LDPC along computational process assists in parallelization and merging memory access [36]. Beside this, convergence problem of BP and numerical polynomial-homotopy-continuation method revealed influence of structures. Therefore, parameters of graph models solved through fixed points [37].Literature study reveals that BP algorithm is not applied in microservice RTP, though the proposed work acquires to analyze impacts based on service dependencies from API gateway logs. Additionally, when it is transformed to directed graph, the process of impact analysis propagation from changed services to nodes of unchanged services. Thus alteration investigation is converted into graph based on intellectual problem.


## 2.1. Microservice Testing

Microservice testing comprises unit-testing, service-testing, and end-to-end testing [4]. However, unit testing is utilized to identify culpabilities in functions or classes. Additionally, this process is sustained by two experimental tools such as xUnit [13] and mockito [14]. In order to bypass user interference and rapid assessment, this service-testing is preferred. However, end-to-end testing focuses on behaviors of entire system to improve efficiency. Although several serious challenges were faced by this autonomous system, still service and end-to-end testing are designed to tackle them effectively. Particularly, this approach is concerned about researches and practices of microservice testing [4, 8], whereas test-cases in this research work include service and end-to-end based assessment.Furthermore, both procedures at the same interval involve multiple services and their invocations. So, high efficiencies are obtained through service and end-to-end analysis. For instance, consumer-driven based evaluation includes consumer, target, and stubbed-services [4]. Therefore, test cases of these two assessment possibilities are abstracted as self-possessed test paths of services, which are purely based on prioritization criteria [11, 12, 15–18].


## 2.2. Test Case Prioritization

Formal definition of regression testing prioritization problem is as follows:Definition 1.
(RTP issue).
Given:T, test-suite, PT, f, and set of all possible permutations of T, whereas f determines performance from PT to real numbers.
Problem: FindT’∈PT:(1)s.t.∀T″∈PTT″≠T′fT′≥fT″.
Definition1 illustrates main points of RPT. Objectives of equation focus on degree of qualitative model, where test cases satisfy prioritization strategies through designing function f, whereas “f, T” comparison-based sorting, heuristic searching, and algorithms approach exist [19].
Furthermore, RTP is emerging area in regression testing based research. However, artifacts procedures are distributed into two categories such as code and model based approaches [20, 21]. Firstly, code-based approaches principally deal with coverage information of test cases such as statement, branch, and path coverage [17, 22]. Such approaches involve source codes availability of system during analysis. Though multiple complex programming languages create challenges for microservice system, therefore, coding system depends on specific language to resolve the complexity of computing. Secondly, model-based methodologies establish association information amongst test-cases and models, whereas models are further integrated into system structures or system behaviors. This approach is utilized to prioritize test cases based on criticality, complexity, and defect density of models [23–25]. Hence, model-based methodology is more preferred than code-based techniques due to its practical viabilities. Beside these feasibilities, it also incorporates microservice system to be more dynamic, integrated, and consistent throughout the procedure.
In addition, several research works primarily focus on historical information specific scenarios. Research conducted by Azizi and Do [26] elucidates that test cases were ranked by changing historical data of artifacts in dynamic environment. However, sustaining changing trend of historical information is a difficult task in microservice systems, where location-based RTP procedure is recommended for embedded environment [27]. This technique emphasizes gravitation laws for high reliability after modification. Also, similarity-based RTP methodology is proposed for product line testing scenario [28]. Revision evaluated effectiveness of real and seeded fault detection in Ouriques [29]. Diverse prevailing RTP methods are compared to monitor the real-time efficiency of approach. Therefore, model-based analysis is compared to investigate influence of test-case on fault-detection rate. However, this approach is only preferable for specific circumstances. Generally, it is not applicable for all regression techniques in microservice regression testing.
With the advent of machine and deep learning approaches in recent years, numerous researchers applied these tactics to RTP [20]. The typical approaches are neural network based RTP approaches such as genetic algorithm and Bayesian network based RTP attitudes. Amongst them, methods based on neural network mainly extract features from system specifications [30]. Beside this, historical analysis records data to prioritize test cases [31]. Additionally, genetic algorithm approaches build some features such as module failure rate, code coverage, and optimum orders, whereas RTP tactics based on Bayesian network mainly combine white box information such as code-changes and code-coverage [32]. Generally, technological methodologies still count on codes, conditions, replicas, and historical statistics as inputs. Therefore, the system has numerous obstacles while performing acquisition, investigation, and sustaining as mentioned above.


## 2.3. Belief propagation

Belief propagation algorithm (BP) is a repetitive process for estimated interpretation based on graph structure. There are numerous applications of BP, which include forward propagation algorithm, Viterbi algorithm, decoding algorithms of low density parity check (LDPC), and turbo codes. Such methodologies are utilized for different sort of situation and scenario [10]. However, the core idea of BP algorithm is to transmit message in order to maintain communication through repeated iterations. Thus, it keeps updates confidence values of nodes. Generally, BP algorithm is as follows:(1)
Initialization: set the initial value of each node.(2)
Propagation: update all message values and node confidence values.(3)
Determining values are convergent. Incase standards are convergent, and inference results are obtained according to confidence values. Otherwise, we will jump back to step (2) and propagate iteratively.In recent years, studies on BP algorithm comprise application and optimization. According to its application, scholars predominantly focus on communication coding and signal processing. In order to reduce complexity of SCMA, dynamic edge assortment procedure based on BP algorithm is introduced. Through iterative calculation, range boundaries of nodes are detected [33]. However, nonlinear equalization method utilized neural network, where BP algorithm is applied to remove signal noises [34]. Additionally, for large-scale MIMO channel detection, belief propagation is used, which is purely based on deep neural network [35]. In optimization aspect, investigators primarily focus on implementation and convergence condition. Furthermore, LDPC along computational process assists in parallelization and merging memory access [36]. Beside this, convergence problem of BP and numerical polynomial-homotopy-continuation method revealed influence of structures. Therefore, parameters of graph models solved through fixed points [37].Literature study reveals that BP algorithm is not applied in microservice RTP, though the proposed work acquires to analyze impacts based on service dependencies from API gateway logs. Additionally, when it is transformed to directed graph, the process of impact analysis propagation from changed services to nodes of unchanged services. Thus alteration investigation is converted into graph based on intellectual problem.


## 3. Methodologies

CIPC resolves issue as given in Definition1 for microservice systems. This problem is tackled through two stages: change impact analysis and test path prioritization as displayed in Figure 1. Furthermore, inputs primarily comprise API gateway logs and test suite, while output is queue of test paths, which determine testing orders.Figure 1
Complete flowchart of prioritization analysis.The above illustration includes two activities: request directed graph generation and change impact propagation computing, where the model based on graph from API gateway logs is generated in earlier stage, while change impacts are created in the second phase through analysis.


### 3.1. Request Directed Graph Generation

In this approach, each record of API gateway logs comprises data such as requestor, responder, and tracing identifier. Through Service Registry, identifiers of requestor and responder are achieved [4]. Additionally, service status is properly observed through microservice frame, which includes Eureka of Netflix, ZooKeeper of Apache, and Nacos of Alibaba, while Service-Chain-Monitor key function is tracing the identity [4]. Besides that, alternative setup of microservice is utilized to monitor user session such as Open Zipkin of Twitter, CAT of VWAP, and Naver Pinpoint, where services request call by specific user sharing identical trace identity.Through accumulation records of logs, probability of interservice dependencies is calculated. However, service supplication is estimated, which is purely based on large number theorem. Statistical analysis of this approach is defined as follows.Definition 2.
(Service Dependencies)
Given a set S as all services of microservice system, ∀si, sj ∈ S (i ≠ j). Suppose invij symbolizes invocation from si to sj, and count(invij) denotes the number of tracing identifiers of all invij in API gateway logs. Incase count(invij) > 0, probability of si depending on sj is defined as follows:(2)w≈countinvij∑i≠kcountinvik+countinvki.
Based on formula (2), RDG can be defined as follows:Definition 3.
(Request directed graph, RDG)
RDG is a tuple (N, E), where N⊆S represents set of nodes. E = {eij| w(eij) ＞ 0, 1 ≤ i, j ≤ n∧i ≠ j} represents set of directed edges. eij symbolizes directed edge from node si to node sj with the weight w(eij), which is computed by formula (2).
From Definition3, RDG is generated from API gateway logs with Algorithm 1, where the algorithm scans logs for each record. Besides this evaluation, it assists in cross-examinations of service ID, updating nodes, and directed edges of RDG as given in lines 2 to 11, though function query_services recovers requester and responder info from service registries. Additionally, function find_or_new finds node or edge in directed graph, whereas function update is used to count the trace identifiers related to invocations or services with logs. Finally, at completion of browsing, weights of edges are updated through the approach based on formula (2) (lines 12 to 15) (Algorithm 1).Algorithm 1: RDG generation algorithm.
Declaration: generateRDG(logs, RDG).Parameters: logs(in); RDG(out).(1)
RDG.N, RDG.E←{}(2)
for eachl ∈ Ldo(3)
si, sj ← query_services(S, l)(4)
if si ≠ null then(5)
RDG.N.find_or_new(si)(6)
end if(7)
RDG.N.find_or_new(sj)(8)
update(sj.Count)(9)
eij←RDG.E.find_or_new(si, sj)(10)
update(eij.Count)(11)
end for(12)
for eachr ∈ RDG.E do(13)
si←r.Sender(14)
e.w←e.Count/si.Count(15)
end for


### 3.2. Change Impact Propagation Computing

Given service setS and modified version S′, it is convenient to achieve list of changed services. Service registries are represented as S′-S. Moreover, to measure impacts of nodes S′-S on other nodes, BP based algorithm is preferred, where updating and message propagation approach for nodes is proposed. Also, junction of repetitive process is analyzed as follows:(1). Node Updating. Meanwhile, there is no limit to sum of change impacts on all service nodes. Therefore, standard BP algorithm is inadequate in such cases. This approach defines “impact degree” to measure variation on service nodes, where impact degree of nodes S′-S is defined as integer 1, while upper limit value and influence level are not affected by fluctuations. At final stage, its impact degree is updated through messages from directed edge. However, proficient value should be maximal value of all messages. The formal definition is as follows:Definition 4.
(Impact Degree)
Assume 3 as definition of RDG. SupposeNi symbolize neighborhood of si and mji represents message from sj to si, where t denotes iteration cycle of message propagation. Then, impact degree pt(si)∈[0, 1] of si is recursively computed.(3)p0si=1,si∈S′−S0,si∉S′−S,(4)pt+1si=maxptsi,maxj∈Nimji.
Apparently, impact degree after message propagation must not be less than earlier message propagation, which is expressed aspt+1(si) ≥pt(si).
(2) Message propagation. In case of graph, directed edge is denoted as eij, where impact degree si will be propagated to sj based on weight w(eij). So, message is well defined in the following way.Definition 5.
(Message)
Definition for RDG is 3, whereeij ∈ RDG.E, and message mij propagated from sito sj:(5)mij=ptsi×weij.
Sincew(eij) ≤ 1, therefore, the message value will always be smaller than the existing impact level. This correlation is denoted as mij ≤ pt(si).
(3) Convergence Analysis. Classifications 3.3 and 3.4 indicate computing process of impact propagation. When there is no loop in directed graph, then RDG is acyclic display. When propagation sequences do not exceed the number of edges in the longest RDG path, then calculation is convergent. Additionally, there are some other types of loops in RDG. Therefore, updating series is unsatisfactory. In such case, it is categorized into two possible circumstances: changed services and static services in loops, respectively, discussed as follows:(i)
When there is nodes ∈ S′-S in the loop, then p0(s) = 1, where pt+1(s)≥pt(s), and pt(s) ≤1, then pt(s) = p0(s) = 1, impact amount of s is not rationalized through message propagations, whereas directed edge s at final phase does not subsidize to computing process and measured as disturbed. Meanwhile, loop is directly disconnected and transformed into directed acyclic graph. Hence, computing process converges, which is presented in Figure 2.(ii)
For nodes of loop, s ∉ S’-S, then p0(s) = 0. According to Definition 4, messages propagated on loop are not synchronized until loop collects peripheral messages. When there are multiple inputs, then output function Max relies on parameters value. Therefore, multiple input messages reach the loop in the same round through aligning iteration. However, computing process of loop is distributed into three phases:①
Computing all input messages: At this phase, message propagations in loop are not updated. So, it is transformed into directed acyclic graph, where computing process converges in this stage.②
Computing the message propagations in loop: As the input reaches loop in the same round, impact degrees are assigned according to formula (4). Through mathematical assessment, node sm with maximal impact degree is achieved, which is denoted by pt(sm). Since messages propagated in loop satisfy mij ＜pt(si), maximal value of messages in loop is less than pt(sm). Therefore, the impact level will not be synchronized with regard to how much messages propagate in loops. Furthermore, loop is disconnected from directed edge with sm and loop is removed, which leads to computing convergence.③
Computing all output messages: According to stage 2 outcomes, output messages in loop are computed directly based on formula (5). Schematic diagram of calculation-process is shown in Figure 3.
To summarize, impact degrees are computed through Definitions4 and 5, which are convergent. For the sake of simplicity, outcomes of variation propagation computing are directly placed in dictionary structure, where it is referred to as the change-impact-table (CIT). Also, pseudocodes CIT is created from RDG as presented in Algorithm 2. Firstly, impact degrees RDG for nodes (lines 1 to 3) are initialized according to S′-S. Secondly, line 4 is used for CIT. Thirdly, iterative computing iteration is used (lines 6 to 8). Moreover, lines 9 to 13 are utilized to update impact degree through messages. Finally, repetitive processes, where impact degrees are, keep constant for all nodes in CIT (line 14).Algorithm 2: Impact propagation algorithm.
Declaration: computeImpactPropagation (RDG, S’, CIT).Parameters: RDG (in); S’(in); CIT(out).(1)
for eachs ∈ RDG.N do(2)
s.p←1ifs ∈ S’-RDG.N else 0(3)
end for(4)
CIT←Table(RDG.N)(5)
do(6)
for eache ∈ RDG.E do(7)
e.m←e.w•e.start.p(8)
end for(9)
for eachs ∈ RDG.N do(10)
for eache ∈ RDG.E and e.end = sdo(11)
s.p←e.mife.m＞s.p(12)
end for(13)
end for(14)
while CIT.update(RDG.N)Figure 2
Loop-wise illustration when node services variates.Figure 3
No nodes of the loop are changed services.


### 3.3. Test Path Prioritization

Test path prioritization (TPH) is utilized to arrange test-paths based on change impact analysis (CIA) outcomes. However, TPH assessment is further categorized into two main activities.(1)
Comparing in pairs: this approach focuses on single-objective prioritization, where variation in test-path is compared in pair form.(2)
Heuristic searching: this methodology is purely based on multiobjective prioritization. Test-route along with impact variation and service coverage is performed through heuristic based searching.


#### 3.3.1. Comparing in Pairs

Single-objective prioritization is utilized to exploit impacts variation on test paths. Therefore, execution is performed earlier, because variation strongly influences test paths. Additionally, TPH procedure is considered to produce analysis queue, where test paths queue comprises two steps.(i)
Set the head of queue: test-path with numerous services is considered as head of queue.(ii)
Update tail of queue: test-path is usually closed to existing tail. Change impact is attached to queue as new tail, where it is determined through computing variation on test paths in pairs.Particular test suiteT and service set S, for test path tp ∈ T. Services contain tp which is composed of subset Stp of S. Through probing output CIT of change impact examination, impact level is achieved of service s ∈ Stp, denoted as CIT(s). Therefore, impact degrees of services in tp are composed of set Vtp = {CIT(s), s ∈ Stp}, whereas this approach emphasis is on test path tp variation, which depends on services. However, two test-paths tpa, tpb are compared in order to remove services with the same impact degree. Furthermore, based on set-operation, the proposed model is utilized to measure variations of impacts fluctuation as shown in Definition 6.Definition 6.
(Dissimilarity of change-impactsdc)
Given two test pathstpa and tpb, suppose (Stpa, Stpb) symbolize services tpa and tpb, respectively, where Vtpa = {CIT(s), s ∈ Stpa} and Vtpb = {CIT(s), s ∈ Stpb}, denote difference of change-impacts, which is defined as follows:(6)dctpa,tpb=elementmaxVtpa−Vtpa∩Vtpb−elementmaxVtpb−Vtpa∩Vtpb,where elementmax is an operator to recover maximal element of set V.(7)elementmaxV=v,V≠∅,∀vi∈V,v≥vi0,V=∅.
Since impact degree CIT(s)∈[0, 1], it is concluded that elementmax(V)∈[0, 1] and dc(tpa, tpb)∈[0, 1]. Additionally, pseudocodes are proposed for single-objective prioritization as shown in Algorithm 3. However, inputs of Algorithm 3 include CIT and test-suite, whereas the output comprises mainly assessment-based queue of test paths. Moreover, set of impact-degrees is initialized for every single test-route, and queue head is figured out through traversing test suite (lines 1 to 7). Finally, queue tail is updated consistently until the complete test route is added (lines 8 to 18).Algorithm 3: Single-objective prioritization algorithm.
Declaration: singlePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ Tdo(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
TQ.head ← tp(6)
end if(7)
end for(8)
T←T - {TQ.tail}(9)
whileT≠∅ do(10)
tc'←T[0](11)
for eachtc ∈ Tdo(12)
ifdc(TQ.tail, tc) > dc(TQ.tail, tc') then(13)
tc'←tc(14)
end if(15)
end for(16)
TQ.tail←tc'(17)
T←T - {TQ.tail}(18)
end while


#### 3.3.2. Hermitic Searching

Single-objective limits the relevancy of prioritization techniques, which are used to ignore the practical constraints, while regression testing multiobjective approaches are utilized in recent research [19]. Early maximization of structural coverage needs to increase the fault detection rate, and also prioritization techniques aim to optimize statement, branch, and path coverage [5]. Microservice regression testing will provide the coverage to use structural objectives, which should be applied on the objectives. Multiobjective prioritization of CIPC is considered to maximize the metrics, which include simplicity and service coverage.However, multiobjective prioritization is the two-step process, which is used to generate testing on queue. Also, every step needs to be regulated, while, in the first step, two options directly determine the head of testing queue. Therefore, selection of test route will maximize service coverage. Also, the increase has high impact on the related selected test path. In heuristic searching technique, the mentioned options are utilized. The second step will update test path to fix the heuristic search, which is based on quantitative measurement.According to Definition6, dc is applied to measure the altered impact, although the most suitable candidate test path increases the service coverage, which is used to test the queue. To find out the test path tp with its service set Stp, suppose the services of testing queue are denoted as STQ by using Jaccard distance [38] in between STQ and Stp. The maximization is as follows:Definition 7.
(Jaccard distance between two service sets,ds)
Give two service setsSa, Sb, where the diversity between Sa and Sb can be computed as follows:(8)dsSa,Sb=Sa∪Sb−Sa∩SbSa∪Sb.
Based on Definition7, ds(Sa, Sb)∈[0, 1], which has the specified value range of dc and ds, while dc and ds, the quantitative measurement, must need to increase heuristic searching, which can be computed as ds(STQ, Stp)- dc(TQ.tail, tp). The TQ.tail represents tail of the testing queue. However, Algorithm 4 is proposed for multiple objective prioritizations.
Algorithm4 is having similar metrics like input, output, and control structures in comparison with Algorithm 3. The main difference in Algorithm 4 is the head of testing queue, which selects the test path. This process increases the service coverage and tail of the queue continuously by using the rules from line 1 to 9, while the queue directly updates the value of ds–dc (lines 10 to 19).Algorithm 4: Multiobjective prioritization algorithm.
Declaration: multiplePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ T do(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
if tp.S.count() >TQ.head.S.count() then(6)
TQ.head ← tp(7)
end if(8)
end if(9)
end for(10)
T←T - {TQ.tail}(11)
whileT≠∅ do(12)
tc'←T[0](13)
for eachtc ∈ Tdo(14)
if ds(TQ.S, tp.S)-dc(TQ.tail, tp) > ds(TQ.S, tp’.S)-dc(TQ.tail, tp’) then(15)
tc'←tc(16)
end if(17)
end for(18)
TQ.tail←tc'(19)
T←T - {TQ.tail}(20)
end while


## 3.1. Request Directed Graph Generation

In this approach, each record of API gateway logs comprises data such as requestor, responder, and tracing identifier. Through Service Registry, identifiers of requestor and responder are achieved [4]. Additionally, service status is properly observed through microservice frame, which includes Eureka of Netflix, ZooKeeper of Apache, and Nacos of Alibaba, while Service-Chain-Monitor key function is tracing the identity [4]. Besides that, alternative setup of microservice is utilized to monitor user session such as Open Zipkin of Twitter, CAT of VWAP, and Naver Pinpoint, where services request call by specific user sharing identical trace identity.Through accumulation records of logs, probability of interservice dependencies is calculated. However, service supplication is estimated, which is purely based on large number theorem. Statistical analysis of this approach is defined as follows.Definition 2.
(Service Dependencies)
Given a set S as all services of microservice system, ∀si, sj ∈ S (i ≠ j). Suppose invij symbolizes invocation from si to sj, and count(invij) denotes the number of tracing identifiers of all invij in API gateway logs. Incase count(invij) > 0, probability of si depending on sj is defined as follows:(2)w≈countinvij∑i≠kcountinvik+countinvki.
Based on formula (2), RDG can be defined as follows:Definition 3.
(Request directed graph, RDG)
RDG is a tuple (N, E), where N⊆S represents set of nodes. E = {eij| w(eij) ＞ 0, 1 ≤ i, j ≤ n∧i ≠ j} represents set of directed edges. eij symbolizes directed edge from node si to node sj with the weight w(eij), which is computed by formula (2).
From Definition3, RDG is generated from API gateway logs with Algorithm 1, where the algorithm scans logs for each record. Besides this evaluation, it assists in cross-examinations of service ID, updating nodes, and directed edges of RDG as given in lines 2 to 11, though function query_services recovers requester and responder info from service registries. Additionally, function find_or_new finds node or edge in directed graph, whereas function update is used to count the trace identifiers related to invocations or services with logs. Finally, at completion of browsing, weights of edges are updated through the approach based on formula (2) (lines 12 to 15) (Algorithm 1).Algorithm 1: RDG generation algorithm.
Declaration: generateRDG(logs, RDG).Parameters: logs(in); RDG(out).(1)
RDG.N, RDG.E←{}(2)
for eachl ∈ Ldo(3)
si, sj ← query_services(S, l)(4)
if si ≠ null then(5)
RDG.N.find_or_new(si)(6)
end if(7)
RDG.N.find_or_new(sj)(8)
update(sj.Count)(9)
eij←RDG.E.find_or_new(si, sj)(10)
update(eij.Count)(11)
end for(12)
for eachr ∈ RDG.E do(13)
si←r.Sender(14)
e.w←e.Count/si.Count(15)
end for


## 3.2. Change Impact Propagation Computing

Given service setS and modified version S′, it is convenient to achieve list of changed services. Service registries are represented as S′-S. Moreover, to measure impacts of nodes S′-S on other nodes, BP based algorithm is preferred, where updating and message propagation approach for nodes is proposed. Also, junction of repetitive process is analyzed as follows:(1). Node Updating. Meanwhile, there is no limit to sum of change impacts on all service nodes. Therefore, standard BP algorithm is inadequate in such cases. This approach defines “impact degree” to measure variation on service nodes, where impact degree of nodes S′-S is defined as integer 1, while upper limit value and influence level are not affected by fluctuations. At final stage, its impact degree is updated through messages from directed edge. However, proficient value should be maximal value of all messages. The formal definition is as follows:Definition 4.
(Impact Degree)
Assume 3 as definition of RDG. SupposeNi symbolize neighborhood of si and mji represents message from sj to si, where t denotes iteration cycle of message propagation. Then, impact degree pt(si)∈[0, 1] of si is recursively computed.(3)p0si=1,si∈S′−S0,si∉S′−S,(4)pt+1si=maxptsi,maxj∈Nimji.
Apparently, impact degree after message propagation must not be less than earlier message propagation, which is expressed aspt+1(si) ≥pt(si).
(2) Message propagation. In case of graph, directed edge is denoted as eij, where impact degree si will be propagated to sj based on weight w(eij). So, message is well defined in the following way.Definition 5.
(Message)
Definition for RDG is 3, whereeij ∈ RDG.E, and message mij propagated from sito sj:(5)mij=ptsi×weij.
Sincew(eij) ≤ 1, therefore, the message value will always be smaller than the existing impact level. This correlation is denoted as mij ≤ pt(si).
(3) Convergence Analysis. Classifications 3.3 and 3.4 indicate computing process of impact propagation. When there is no loop in directed graph, then RDG is acyclic display. When propagation sequences do not exceed the number of edges in the longest RDG path, then calculation is convergent. Additionally, there are some other types of loops in RDG. Therefore, updating series is unsatisfactory. In such case, it is categorized into two possible circumstances: changed services and static services in loops, respectively, discussed as follows:(i)
When there is nodes ∈ S′-S in the loop, then p0(s) = 1, where pt+1(s)≥pt(s), and pt(s) ≤1, then pt(s) = p0(s) = 1, impact amount of s is not rationalized through message propagations, whereas directed edge s at final phase does not subsidize to computing process and measured as disturbed. Meanwhile, loop is directly disconnected and transformed into directed acyclic graph. Hence, computing process converges, which is presented in Figure 2.(ii)
For nodes of loop, s ∉ S’-S, then p0(s) = 0. According to Definition 4, messages propagated on loop are not synchronized until loop collects peripheral messages. When there are multiple inputs, then output function Max relies on parameters value. Therefore, multiple input messages reach the loop in the same round through aligning iteration. However, computing process of loop is distributed into three phases:①
Computing all input messages: At this phase, message propagations in loop are not updated. So, it is transformed into directed acyclic graph, where computing process converges in this stage.②
Computing the message propagations in loop: As the input reaches loop in the same round, impact degrees are assigned according to formula (4). Through mathematical assessment, node sm with maximal impact degree is achieved, which is denoted by pt(sm). Since messages propagated in loop satisfy mij ＜pt(si), maximal value of messages in loop is less than pt(sm). Therefore, the impact level will not be synchronized with regard to how much messages propagate in loops. Furthermore, loop is disconnected from directed edge with sm and loop is removed, which leads to computing convergence.③
Computing all output messages: According to stage 2 outcomes, output messages in loop are computed directly based on formula (5). Schematic diagram of calculation-process is shown in Figure 3.
To summarize, impact degrees are computed through Definitions4 and 5, which are convergent. For the sake of simplicity, outcomes of variation propagation computing are directly placed in dictionary structure, where it is referred to as the change-impact-table (CIT). Also, pseudocodes CIT is created from RDG as presented in Algorithm 2. Firstly, impact degrees RDG for nodes (lines 1 to 3) are initialized according to S′-S. Secondly, line 4 is used for CIT. Thirdly, iterative computing iteration is used (lines 6 to 8). Moreover, lines 9 to 13 are utilized to update impact degree through messages. Finally, repetitive processes, where impact degrees are, keep constant for all nodes in CIT (line 14).Algorithm 2: Impact propagation algorithm.
Declaration: computeImpactPropagation (RDG, S’, CIT).Parameters: RDG (in); S’(in); CIT(out).(1)
for eachs ∈ RDG.N do(2)
s.p←1ifs ∈ S’-RDG.N else 0(3)
end for(4)
CIT←Table(RDG.N)(5)
do(6)
for eache ∈ RDG.E do(7)
e.m←e.w•e.start.p(8)
end for(9)
for eachs ∈ RDG.N do(10)
for eache ∈ RDG.E and e.end = sdo(11)
s.p←e.mife.m＞s.p(12)
end for(13)
end for(14)
while CIT.update(RDG.N)Figure 2
Loop-wise illustration when node services variates.Figure 3
No nodes of the loop are changed services.


## 3.3. Test Path Prioritization

Test path prioritization (TPH) is utilized to arrange test-paths based on change impact analysis (CIA) outcomes. However, TPH assessment is further categorized into two main activities.(1)
Comparing in pairs: this approach focuses on single-objective prioritization, where variation in test-path is compared in pair form.(2)
Heuristic searching: this methodology is purely based on multiobjective prioritization. Test-route along with impact variation and service coverage is performed through heuristic based searching.


### 3.3.1. Comparing in Pairs

Single-objective prioritization is utilized to exploit impacts variation on test paths. Therefore, execution is performed earlier, because variation strongly influences test paths. Additionally, TPH procedure is considered to produce analysis queue, where test paths queue comprises two steps.(i)
Set the head of queue: test-path with numerous services is considered as head of queue.(ii)
Update tail of queue: test-path is usually closed to existing tail. Change impact is attached to queue as new tail, where it is determined through computing variation on test paths in pairs.Particular test suiteT and service set S, for test path tp ∈ T. Services contain tp which is composed of subset Stp of S. Through probing output CIT of change impact examination, impact level is achieved of service s ∈ Stp, denoted as CIT(s). Therefore, impact degrees of services in tp are composed of set Vtp = {CIT(s), s ∈ Stp}, whereas this approach emphasis is on test path tp variation, which depends on services. However, two test-paths tpa, tpb are compared in order to remove services with the same impact degree. Furthermore, based on set-operation, the proposed model is utilized to measure variations of impacts fluctuation as shown in Definition 6.Definition 6.
(Dissimilarity of change-impactsdc)
Given two test pathstpa and tpb, suppose (Stpa, Stpb) symbolize services tpa and tpb, respectively, where Vtpa = {CIT(s), s ∈ Stpa} and Vtpb = {CIT(s), s ∈ Stpb}, denote difference of change-impacts, which is defined as follows:(6)dctpa,tpb=elementmaxVtpa−Vtpa∩Vtpb−elementmaxVtpb−Vtpa∩Vtpb,where elementmax is an operator to recover maximal element of set V.(7)elementmaxV=v,V≠∅,∀vi∈V,v≥vi0,V=∅.
Since impact degree CIT(s)∈[0, 1], it is concluded that elementmax(V)∈[0, 1] and dc(tpa, tpb)∈[0, 1]. Additionally, pseudocodes are proposed for single-objective prioritization as shown in Algorithm 3. However, inputs of Algorithm 3 include CIT and test-suite, whereas the output comprises mainly assessment-based queue of test paths. Moreover, set of impact-degrees is initialized for every single test-route, and queue head is figured out through traversing test suite (lines 1 to 7). Finally, queue tail is updated consistently until the complete test route is added (lines 8 to 18).Algorithm 3: Single-objective prioritization algorithm.
Declaration: singlePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ Tdo(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
TQ.head ← tp(6)
end if(7)
end for(8)
T←T - {TQ.tail}(9)
whileT≠∅ do(10)
tc'←T[0](11)
for eachtc ∈ Tdo(12)
ifdc(TQ.tail, tc) > dc(TQ.tail, tc') then(13)
tc'←tc(14)
end if(15)
end for(16)
TQ.tail←tc'(17)
T←T - {TQ.tail}(18)
end while


### 3.3.2. Hermitic Searching

Single-objective limits the relevancy of prioritization techniques, which are used to ignore the practical constraints, while regression testing multiobjective approaches are utilized in recent research [19]. Early maximization of structural coverage needs to increase the fault detection rate, and also prioritization techniques aim to optimize statement, branch, and path coverage [5]. Microservice regression testing will provide the coverage to use structural objectives, which should be applied on the objectives. Multiobjective prioritization of CIPC is considered to maximize the metrics, which include simplicity and service coverage.However, multiobjective prioritization is the two-step process, which is used to generate testing on queue. Also, every step needs to be regulated, while, in the first step, two options directly determine the head of testing queue. Therefore, selection of test route will maximize service coverage. Also, the increase has high impact on the related selected test path. In heuristic searching technique, the mentioned options are utilized. The second step will update test path to fix the heuristic search, which is based on quantitative measurement.According to Definition6, dc is applied to measure the altered impact, although the most suitable candidate test path increases the service coverage, which is used to test the queue. To find out the test path tp with its service set Stp, suppose the services of testing queue are denoted as STQ by using Jaccard distance [38] in between STQ and Stp. The maximization is as follows:Definition 7.
(Jaccard distance between two service sets,ds)
Give two service setsSa, Sb, where the diversity between Sa and Sb can be computed as follows:(8)dsSa,Sb=Sa∪Sb−Sa∩SbSa∪Sb.
Based on Definition7, ds(Sa, Sb)∈[0, 1], which has the specified value range of dc and ds, while dc and ds, the quantitative measurement, must need to increase heuristic searching, which can be computed as ds(STQ, Stp)- dc(TQ.tail, tp). The TQ.tail represents tail of the testing queue. However, Algorithm 4 is proposed for multiple objective prioritizations.
Algorithm4 is having similar metrics like input, output, and control structures in comparison with Algorithm 3. The main difference in Algorithm 4 is the head of testing queue, which selects the test path. This process increases the service coverage and tail of the queue continuously by using the rules from line 1 to 9, while the queue directly updates the value of ds–dc (lines 10 to 19).Algorithm 4: Multiobjective prioritization algorithm.
Declaration: multiplePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ T do(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
if tp.S.count() >TQ.head.S.count() then(6)
TQ.head ← tp(7)
end if(8)
end if(9)
end for(10)
T←T - {TQ.tail}(11)
whileT≠∅ do(12)
tc'←T[0](13)
for eachtc ∈ Tdo(14)
if ds(TQ.S, tp.S)-dc(TQ.tail, tp) > ds(TQ.S, tp’.S)-dc(TQ.tail, tp’) then(15)
tc'←tc(16)
end if(17)
end for(18)
TQ.tail←tc'(19)
T←T - {TQ.tail}(20)
end while


## 3.3.1. Comparing in Pairs

Single-objective prioritization is utilized to exploit impacts variation on test paths. Therefore, execution is performed earlier, because variation strongly influences test paths. Additionally, TPH procedure is considered to produce analysis queue, where test paths queue comprises two steps.(i)
Set the head of queue: test-path with numerous services is considered as head of queue.(ii)
Update tail of queue: test-path is usually closed to existing tail. Change impact is attached to queue as new tail, where it is determined through computing variation on test paths in pairs.Particular test suiteT and service set S, for test path tp ∈ T. Services contain tp which is composed of subset Stp of S. Through probing output CIT of change impact examination, impact level is achieved of service s ∈ Stp, denoted as CIT(s). Therefore, impact degrees of services in tp are composed of set Vtp = {CIT(s), s ∈ Stp}, whereas this approach emphasis is on test path tp variation, which depends on services. However, two test-paths tpa, tpb are compared in order to remove services with the same impact degree. Furthermore, based on set-operation, the proposed model is utilized to measure variations of impacts fluctuation as shown in Definition 6.Definition 6.
(Dissimilarity of change-impactsdc)
Given two test pathstpa and tpb, suppose (Stpa, Stpb) symbolize services tpa and tpb, respectively, where Vtpa = {CIT(s), s ∈ Stpa} and Vtpb = {CIT(s), s ∈ Stpb}, denote difference of change-impacts, which is defined as follows:(6)dctpa,tpb=elementmaxVtpa−Vtpa∩Vtpb−elementmaxVtpb−Vtpa∩Vtpb,where elementmax is an operator to recover maximal element of set V.(7)elementmaxV=v,V≠∅,∀vi∈V,v≥vi0,V=∅.
Since impact degree CIT(s)∈[0, 1], it is concluded that elementmax(V)∈[0, 1] and dc(tpa, tpb)∈[0, 1]. Additionally, pseudocodes are proposed for single-objective prioritization as shown in Algorithm 3. However, inputs of Algorithm 3 include CIT and test-suite, whereas the output comprises mainly assessment-based queue of test paths. Moreover, set of impact-degrees is initialized for every single test-route, and queue head is figured out through traversing test suite (lines 1 to 7). Finally, queue tail is updated consistently until the complete test route is added (lines 8 to 18).Algorithm 3: Single-objective prioritization algorithm.
Declaration: singlePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ Tdo(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
TQ.head ← tp(6)
end if(7)
end for(8)
T←T - {TQ.tail}(9)
whileT≠∅ do(10)
tc'←T[0](11)
for eachtc ∈ Tdo(12)
ifdc(TQ.tail, tc) > dc(TQ.tail, tc') then(13)
tc'←tc(14)
end if(15)
end for(16)
TQ.tail←tc'(17)
T←T - {TQ.tail}(18)
end while


## 3.3.2. Hermitic Searching

Single-objective limits the relevancy of prioritization techniques, which are used to ignore the practical constraints, while regression testing multiobjective approaches are utilized in recent research [19]. Early maximization of structural coverage needs to increase the fault detection rate, and also prioritization techniques aim to optimize statement, branch, and path coverage [5]. Microservice regression testing will provide the coverage to use structural objectives, which should be applied on the objectives. Multiobjective prioritization of CIPC is considered to maximize the metrics, which include simplicity and service coverage.However, multiobjective prioritization is the two-step process, which is used to generate testing on queue. Also, every step needs to be regulated, while, in the first step, two options directly determine the head of testing queue. Therefore, selection of test route will maximize service coverage. Also, the increase has high impact on the related selected test path. In heuristic searching technique, the mentioned options are utilized. The second step will update test path to fix the heuristic search, which is based on quantitative measurement.According to Definition6, dc is applied to measure the altered impact, although the most suitable candidate test path increases the service coverage, which is used to test the queue. To find out the test path tp with its service set Stp, suppose the services of testing queue are denoted as STQ by using Jaccard distance [38] in between STQ and Stp. The maximization is as follows:Definition 7.
(Jaccard distance between two service sets,ds)
Give two service setsSa, Sb, where the diversity between Sa and Sb can be computed as follows:(8)dsSa,Sb=Sa∪Sb−Sa∩SbSa∪Sb.
Based on Definition7, ds(Sa, Sb)∈[0, 1], which has the specified value range of dc and ds, while dc and ds, the quantitative measurement, must need to increase heuristic searching, which can be computed as ds(STQ, Stp)- dc(TQ.tail, tp). The TQ.tail represents tail of the testing queue. However, Algorithm 4 is proposed for multiple objective prioritizations.
Algorithm4 is having similar metrics like input, output, and control structures in comparison with Algorithm 3. The main difference in Algorithm 4 is the head of testing queue, which selects the test path. This process increases the service coverage and tail of the queue continuously by using the rules from line 1 to 9, while the queue directly updates the value of ds–dc (lines 10 to 19).Algorithm 4: Multiobjective prioritization algorithm.
Declaration: multiplePrioritization (CIT, T, TQ).Parameters: CIT (in); T, test suite (in); TQ, testing queue(out).(1)
TQ←Queue()(2)
for eachtp ∈ T do(3)
tp.V←{CIT(s), s ∈ tp.S}(4)
if elementmax(tp.V) > elementmax(TQ.head.V) then(5)
if tp.S.count() >TQ.head.S.count() then(6)
TQ.head ← tp(7)
end if(8)
end if(9)
end for(10)
T←T - {TQ.tail}(11)
whileT≠∅ do(12)
tc'←T[0](13)
for eachtc ∈ Tdo(14)
if ds(TQ.S, tp.S)-dc(TQ.tail, tp) > ds(TQ.S, tp’.S)-dc(TQ.tail, tp’) then(15)
tc'←tc(16)
end if(17)
end for(18)
TQ.tail←tc'(19)
T←T - {TQ.tail}(20)
end while


## 4. Empirical Study

The experimentation is performed on Python 3.5, which accesses CIPC to collect five microservice systems for analysis. The subsections are used to describe case introduction, techniques, and evaluation metrics, while the empirical study investigates the below research questions:RQ Can CIPC improve the effectiveness of microservice regression testing prioritization?Moreover, CIPC is a more practical approach than typical artifacts, which is based on history data like RTP methods for microservice regression testing?


### 4.1. Case Introduction

The following five microservice systems need to be utilized in the empirical study:(1)
m-Ticket: a multi-end ticket system based on SpringBlade is an open source microservice framework, which is available at this link:https://github.com/chillzhuang/SpringBlade. These ticket services can be used in various fields such as transportation, accommodation, tourist attractions, movies, supporting service management, monitoring, and tracing.(2)
z-Shop: this is basically an oriented mall system based on Zheng, which is an open-source framework having availability at the address,https://github.com/shuzheng/zheng. However, the mentioned system provides one-stop management services for goods, stores, content promotion, orders, and logistics.(3)
Need: knowledge graph system needs to work on spring cloud, which provides functions like data collection, auxiliary analysis, information extraction, intelligent query, and other life cycle management services.(4)
KAS: this system checks data collection, processing services for domain literatures, importing, persistence, analysis, and also duplicate checking.(5)
JOA: the OA system primarily forms spring cloud, which comes up with functions like comprehensive information display, document circulation, process approval, plan management, organization personnel control, and fund services for the organization with multiple departments and secret levels.Table1 describes the number of logs, services, test cases, and faults of all mentioned cases. Faults of respective versions are collected from corresponding test reports. The a posteriori method should be utilized to adopt the experiment setup, where execution results and testing time are the main activities to prioritize test cases, while Table 1 represents m-ticket, z-shop, need, KAS, and JOA, which are relatively uncomplicated. The design documents, logs, and testing data of each version are collected, which meet the prerequisites of artifacts based on RTP techniques. In addition, JOA have relatively huge number of services, which involve data access permission and joint development of multiple teams. The artifacts directly based on RTP method cannot be applied on JOA.Table 1
Properties of each case.
SubjectNo. of servicesLogsNo. of versionsNo. of test casesNo. of faultsm-Ticket61140,00051182539z-Shop43520,0004913427Need1692,000,0004847781KAS20716,000,000645581096JOA60550,000,0009133564783


### 4.2. Techniques for Comparison

CIPC is compared with typical RTP methods, which consider technical support for three different groups of artifacts, while the artifacts are based on RTP and on control, respectively.(1)
WS-BPEL analysis (WA) [12]: this method relies on flow graph models, which are based on Web Service for Business Process Execution Language (WS-BPEL) [39]. The model’s construction has WS-BPEL dependence analysis to retrieve information between services to impact analysis. This approach computes the weights, where modification-affected services prioritize test paths accordingly having more alteration in accordance with highest weight.(2)
Accumulation of failures with weights from statistical analysis and correlation data (AF) [40]: this technique prioritizes test paths based on the weighted graphs from the statistical analysis of failure history and the correlation data among test paths. In the integrated environment, all the data need to be maintained.(3)
Service coverage (SC): these methods prioritize test paths, which has a total number of services. Therefore, multiple test paths cover the similar number of services.(4)
Changed service coverage (CC): the technique normally prioritizes test paths, which are based on the total number of services. These resources directly need to be covered. However, multiple test paths cover the same number of changed services, which are ordered randomly.In RTP methods, the SC and CC integrate to control the benchmark techniques. Empirical study will focus on comparing hermitic search of CIPC, which must adopt each case like CIPC-CP and CIPC-HS, respectively. The same computing resources are utilized for all RTP techniques to ensure the fairness of experimentation.


### 4.3. Evaluation Metrics

RTP evaluation metrics are as follows [5, 8].(1)
Average Percentage of fault detection (APFD): this technique needs to measure the efficiency of testing sequenceT. Let n be the size of T and let m represent the size of fault set F. TFi describes the order value of test case, by which the i-th fault is found. Therefore, APFD is computed in equation (9). Although the APFD higher value easily detects faults, however, the more efficient prioritization test cases are as follows: (9)APFD=1−∑i=1mTFimn+12n.(2)
Prioritization time costs (PTC): this approach measures the time costs of RTP technique to make use of prioritization process. Normally, PTC and APFD are both considered as NA. Since the intention of RTP is to reduce testing time costs, which contain prioritization time costs. However, RTP technique more practically spends less time cost.


## 4.1. Case Introduction

The following five microservice systems need to be utilized in the empirical study:(1)
m-Ticket: a multi-end ticket system based on SpringBlade is an open source microservice framework, which is available at this link:https://github.com/chillzhuang/SpringBlade. These ticket services can be used in various fields such as transportation, accommodation, tourist attractions, movies, supporting service management, monitoring, and tracing.(2)
z-Shop: this is basically an oriented mall system based on Zheng, which is an open-source framework having availability at the address,https://github.com/shuzheng/zheng. However, the mentioned system provides one-stop management services for goods, stores, content promotion, orders, and logistics.(3)
Need: knowledge graph system needs to work on spring cloud, which provides functions like data collection, auxiliary analysis, information extraction, intelligent query, and other life cycle management services.(4)
KAS: this system checks data collection, processing services for domain literatures, importing, persistence, analysis, and also duplicate checking.(5)
JOA: the OA system primarily forms spring cloud, which comes up with functions like comprehensive information display, document circulation, process approval, plan management, organization personnel control, and fund services for the organization with multiple departments and secret levels.Table1 describes the number of logs, services, test cases, and faults of all mentioned cases. Faults of respective versions are collected from corresponding test reports. The a posteriori method should be utilized to adopt the experiment setup, where execution results and testing time are the main activities to prioritize test cases, while Table 1 represents m-ticket, z-shop, need, KAS, and JOA, which are relatively uncomplicated. The design documents, logs, and testing data of each version are collected, which meet the prerequisites of artifacts based on RTP techniques. In addition, JOA have relatively huge number of services, which involve data access permission and joint development of multiple teams. The artifacts directly based on RTP method cannot be applied on JOA.Table 1
Properties of each case.
SubjectNo. of servicesLogsNo. of versionsNo. of test casesNo. of faultsm-Ticket61140,00051182539z-Shop43520,0004913427Need1692,000,0004847781KAS20716,000,000645581096JOA60550,000,0009133564783


## 4.2. Techniques for Comparison

CIPC is compared with typical RTP methods, which consider technical support for three different groups of artifacts, while the artifacts are based on RTP and on control, respectively.(1)
WS-BPEL analysis (WA) [12]: this method relies on flow graph models, which are based on Web Service for Business Process Execution Language (WS-BPEL) [39]. The model’s construction has WS-BPEL dependence analysis to retrieve information between services to impact analysis. This approach computes the weights, where modification-affected services prioritize test paths accordingly having more alteration in accordance with highest weight.(2)
Accumulation of failures with weights from statistical analysis and correlation data (AF) [40]: this technique prioritizes test paths based on the weighted graphs from the statistical analysis of failure history and the correlation data among test paths. In the integrated environment, all the data need to be maintained.(3)
Service coverage (SC): these methods prioritize test paths, which has a total number of services. Therefore, multiple test paths cover the similar number of services.(4)
Changed service coverage (CC): the technique normally prioritizes test paths, which are based on the total number of services. These resources directly need to be covered. However, multiple test paths cover the same number of changed services, which are ordered randomly.In RTP methods, the SC and CC integrate to control the benchmark techniques. Empirical study will focus on comparing hermitic search of CIPC, which must adopt each case like CIPC-CP and CIPC-HS, respectively. The same computing resources are utilized for all RTP techniques to ensure the fairness of experimentation.


## 4.3. Evaluation Metrics

RTP evaluation metrics are as follows [5, 8].(1)
Average Percentage of fault detection (APFD): this technique needs to measure the efficiency of testing sequenceT. Let n be the size of T and let m represent the size of fault set F. TFi describes the order value of test case, by which the i-th fault is found. Therefore, APFD is computed in equation (9). Although the APFD higher value easily detects faults, however, the more efficient prioritization test cases are as follows: (9)APFD=1−∑i=1mTFimn+12n.(2)
Prioritization time costs (PTC): this approach measures the time costs of RTP technique to make use of prioritization process. Normally, PTC and APFD are both considered as NA. Since the intention of RTP is to reduce testing time costs, which contain prioritization time costs. However, RTP technique more practically spends less time cost.


## 5. Results and Discussion

### 5.1. Data and Analysis

The data of the experimentation is presented in Table2. While APFD values range from 0.70 to 0.93 for CIPC-CP with having the mean value of 0.82, 0.83 up to 0.98, however, CIPC-HS mean value is formulated as 0.89, where CIPC achieves high fault detection rate in microservice regression testing. By comparing RTP techniques, where boxplots are drawn to represent the value distribution of APFD, therefore, Figure 4 apparently has smaller values of SC and CC in comparison with WA, AF, and CIPC. This means that RTP control methods are very less efficient in identifying faults. Coverage relationships are considered in between test paths and services to control RTP techniques. However, the artifacts and history based RTP methods are used to retrieve more information, which controls faults and change in impact. Information with the high probability of detecting faults need to be found by improving effectiveness of prioritization. In addition, RTP methods significantly improve efficiency of microservice regression testing.Table 2
APFD and PTC (minutes) of each RTP technique in each case.
Subject & versionsSCCCWAAFCIPC-CPCIPC-HSAPFDPTCAPFDPTCAPFDPTCAPFDPTCAPFDPTCAPFDPTCm-Ticketv20.330.010.360.010.7637.290.6515.520.700.180.840.18v30.350.010.410.010.7830.710.6715.210.780.200.850.20v40.380.010.350.010.7631.250.6815.100.750.220.880.22v50.460.010.520.010.9027.630.7415.890.750.250.890.25z-Shopv20.370.010.300.010.7320.220.6212.350.720.110.830.11v30.420.010.350.010.7917.820.6512.500.750.140.870.14v40.510.010.560.010.8919.030.8412.630.880.150.890.15Needv20.190.020.220.020.7897.220.7324.320.700.300.830.30v30.450.020.430.020.8879.320.8225.840.860.380.850.38v40.420.030.310.030.9265.240.8526.200.870.420.900.42KASv20.430.040.340.040.75124.100.7540.210.740.350.830.35v30.250.040.310.040.89109.750.8342.500.810.490.870.49v40.260.040.290.040.9085.680.6945.810.900.600.910.60v50.540.050.480.050.9480.100.6746.050.900.650.950.65v60.250.050.530.050.9274.950.8046.900.930.840.950.84JOAv20.280.090.300.09NANA0.7095.300.750.620.850.62v30.440.090.470.09NANA0.6892.250.780.650.830.65v40.450.110.470.11NANA0.8596.580.790.850.900.85v50.530.110.530.11NANA0.8390.140.840.920.900.93v60.540.120.580.12NANA0.8490.950.901.250.931.26v70.240.120.300.12NANA0.7695.610.921.400.961.42v80.480.130.320.13NANA0.8296.200.921.450.961.46v90.290.130.400.13NANA0.6695.450.921.570.981.59Figure 4
The boxplot of the APFD values of each RTP technique.Meanwhile, APFD, WA, AF, and CIPC values are similar, which means a direct change in impact propagation computing. However, regression testing prioritization must achieve high quality of effectiveness to detect faults, while the box height of CIPC-HS is much less than other contemporary techniques. Moreover, the fluctuation of APFD values of CIP-HS contains lower value in comparison with other methods. CIPC-HS try to adopt multiple objectives, which prioritize test paths to achieve adaptability.PTC values are given properly in Table2. Although PTC must have values of WA, AF, which is apparently much larger than SC, CC, and CIPC, the former are almost two orders of magnitude higher than the others. Therefore, results present WA, AF, where costs are higher than those of SC, CC, and CIPS.The control flow graph models are used to process, establish, analyze, and maintain the time cost for WA. However, AF also analyzes the relationships between fault history and test paths. The artifacts and history data seriously affect the processing performance. On the other hand, SC, CC, and CIPC need to prioritize time cost, which mainly covers the related queries. These services are used to take very small amount of time in every RTP technique. The artifacts, API gateway logs are compared with commonly structural approach to automate the CIPC. Therefore, data relationship cannot maintain and balance the whole process. Fault detection rate, SC, and CC are having vulnerabilities during implementation. In addition, achieving the expected fault detection rate, CIPC saves much more time in comparison with WA and AF after analyzing the different trends of prioritization time cost, which easily scales up the system. Different RTP methods represent various results, which are shown in Figure5. The horizontal axis directly arranges 5 cases according to the number of services from small to large value, while the vertical axis describes the mean value of PTC in every case. The numerical diversities of PTC methods having different values in the mentioned metrics like SC, CC, CIPC, WA, and AF. Two-line charts having various value ranges from vertical axis are drawn to facilitate the process. In Figure 5, the trends of prioritization time costs relatively need to increase with the passage of time. The proposed method increases the system scales, which is a very tough process. The JOA approach is having multiple teams, which must be engaged to obtain the related data of experimentation. The RTP techniques like WA and AF will never be applied to enhance the capabilities. However, the API gateway logs easily collect the information from evolution of microservice systems. The performance of CIPC is mainly determined to scale up the logs, which optimize the algorithms and computing resources, while the CIPC method is more practical than artifacts and history processes, which are based on RTP techniques like WA and AF. This approach uses to enhance the microservice regression testing.Figure 5
The changing trends of prioritization time costs with the system scales.The CIPC improve the effectiveness of microservice in regression testing. In addition, the above-mentioned challenges need to be solved with acceptable time cost.


### 5.2. Threats to Validity

In the empirical studies, there are some risks, which need to be tested on different experimentations, which mainly validate the two main aspects:(1)
Cases selection: during the practical experimentation factors like size, complexity will have limitations, which do not cover all types of microservice systems, while, at the same time, test case generation will deal with fault records. But the behavior will be comprehensive and will not affect the results. Therefore, different areas need to validate the scales and distribution characteristics.(2)
Comparison RTP techniques selection: RTP techniques are compared with the existing work. Therefore, validity risks must be introduced in the experimentation. However, WA and AF are typical RTP methods. In future, more contemporary techniques should be compared with the proposed solution.


## 5.1. Data and Analysis

The data of the experimentation is presented in Table2. While APFD values range from 0.70 to 0.93 for CIPC-CP with having the mean value of 0.82, 0.83 up to 0.98, however, CIPC-HS mean value is formulated as 0.89, where CIPC achieves high fault detection rate in microservice regression testing. By comparing RTP techniques, where boxplots are drawn to represent the value distribution of APFD, therefore, Figure 4 apparently has smaller values of SC and CC in comparison with WA, AF, and CIPC. This means that RTP control methods are very less efficient in identifying faults. Coverage relationships are considered in between test paths and services to control RTP techniques. However, the artifacts and history based RTP methods are used to retrieve more information, which controls faults and change in impact. Information with the high probability of detecting faults need to be found by improving effectiveness of prioritization. In addition, RTP methods significantly improve efficiency of microservice regression testing.Table 2
APFD and PTC (minutes) of each RTP technique in each case.
Subject & versionsSCCCWAAFCIPC-CPCIPC-HSAPFDPTCAPFDPTCAPFDPTCAPFDPTCAPFDPTCAPFDPTCm-Ticketv20.330.010.360.010.7637.290.6515.520.700.180.840.18v30.350.010.410.010.7830.710.6715.210.780.200.850.20v40.380.010.350.010.7631.250.6815.100.750.220.880.22v50.460.010.520.010.9027.630.7415.890.750.250.890.25z-Shopv20.370.010.300.010.7320.220.6212.350.720.110.830.11v30.420.010.350.010.7917.820.6512.500.750.140.870.14v40.510.010.560.010.8919.030.8412.630.880.150.890.15Needv20.190.020.220.020.7897.220.7324.320.700.300.830.30v30.450.020.430.020.8879.320.8225.840.860.380.850.38v40.420.030.310.030.9265.240.8526.200.870.420.900.42KASv20.430.040.340.040.75124.100.7540.210.740.350.830.35v30.250.040.310.040.89109.750.8342.500.810.490.870.49v40.260.040.290.040.9085.680.6945.810.900.600.910.60v50.540.050.480.050.9480.100.6746.050.900.650.950.65v60.250.050.530.050.9274.950.8046.900.930.840.950.84JOAv20.280.090.300.09NANA0.7095.300.750.620.850.62v30.440.090.470.09NANA0.6892.250.780.650.830.65v40.450.110.470.11NANA0.8596.580.790.850.900.85v50.530.110.530.11NANA0.8390.140.840.920.900.93v60.540.120.580.12NANA0.8490.950.901.250.931.26v70.240.120.300.12NANA0.7695.610.921.400.961.42v80.480.130.320.13NANA0.8296.200.921.450.961.46v90.290.130.400.13NANA0.6695.450.921.570.981.59Figure 4
The boxplot of the APFD values of each RTP technique.Meanwhile, APFD, WA, AF, and CIPC values are similar, which means a direct change in impact propagation computing. However, regression testing prioritization must achieve high quality of effectiveness to detect faults, while the box height of CIPC-HS is much less than other contemporary techniques. Moreover, the fluctuation of APFD values of CIP-HS contains lower value in comparison with other methods. CIPC-HS try to adopt multiple objectives, which prioritize test paths to achieve adaptability.PTC values are given properly in Table2. Although PTC must have values of WA, AF, which is apparently much larger than SC, CC, and CIPC, the former are almost two orders of magnitude higher than the others. Therefore, results present WA, AF, where costs are higher than those of SC, CC, and CIPS.The control flow graph models are used to process, establish, analyze, and maintain the time cost for WA. However, AF also analyzes the relationships between fault history and test paths. The artifacts and history data seriously affect the processing performance. On the other hand, SC, CC, and CIPC need to prioritize time cost, which mainly covers the related queries. These services are used to take very small amount of time in every RTP technique. The artifacts, API gateway logs are compared with commonly structural approach to automate the CIPC. Therefore, data relationship cannot maintain and balance the whole process. Fault detection rate, SC, and CC are having vulnerabilities during implementation. In addition, achieving the expected fault detection rate, CIPC saves much more time in comparison with WA and AF after analyzing the different trends of prioritization time cost, which easily scales up the system. Different RTP methods represent various results, which are shown in Figure5. The horizontal axis directly arranges 5 cases according to the number of services from small to large value, while the vertical axis describes the mean value of PTC in every case. The numerical diversities of PTC methods having different values in the mentioned metrics like SC, CC, CIPC, WA, and AF. Two-line charts having various value ranges from vertical axis are drawn to facilitate the process. In Figure 5, the trends of prioritization time costs relatively need to increase with the passage of time. The proposed method increases the system scales, which is a very tough process. The JOA approach is having multiple teams, which must be engaged to obtain the related data of experimentation. The RTP techniques like WA and AF will never be applied to enhance the capabilities. However, the API gateway logs easily collect the information from evolution of microservice systems. The performance of CIPC is mainly determined to scale up the logs, which optimize the algorithms and computing resources, while the CIPC method is more practical than artifacts and history processes, which are based on RTP techniques like WA and AF. This approach uses to enhance the microservice regression testing.Figure 5
The changing trends of prioritization time costs with the system scales.The CIPC improve the effectiveness of microservice in regression testing. In addition, the above-mentioned challenges need to be solved with acceptable time cost.


## 5.2. Threats to Validity

In the empirical studies, there are some risks, which need to be tested on different experimentations, which mainly validate the two main aspects:(1)
Cases selection: during the practical experimentation factors like size, complexity will have limitations, which do not cover all types of microservice systems, while, at the same time, test case generation will deal with fault records. But the behavior will be comprehensive and will not affect the results. Therefore, different areas need to validate the scales and distribution characteristics.(2)
Comparison RTP techniques selection: RTP techniques are compared with the existing work. Therefore, validity risks must be introduced in the experimentation. However, WA and AF are typical RTP methods. In future, more contemporary techniques should be compared with the proposed solution.


## 6. Conclusions and Future Work

This research study explains microservice regression testing technique, which is referred to as CIPC. The whole process of CIPC is discussed in detail, which verifies the effectiveness of the empirical study. The proposed solution retrieves service dependencies from API gateway layer logs and impact propagation calculation with directed graph. Also, prioritizing test paths needs to be compared in pairs or hermitic search. The process must be fully automatic and applicable for microservice system regression testing. In future, the two aspects, which include granularity of CIPC and service dependencies from API gateway logs, must give insight overview to improve accordingly. Also, CIPC is used in different fields and patterns like mesh service to collect more cases for empirical study.



---

*Source: 2912240-2021-11-23.xml*