Harnessing Test-Oriented Knowledge Graphs for Enhanced Test Function Recommendation

Abstract

Application Programming Interfaces (APIs) have become common in contemporary software development. Many automated API recommendation methods have been proposed. However, these methods suffer from a deficit of using domain knowledge, giving rise to challenges like the “cold start” and “semantic gap” problems. Consequently, they are unsuitable for test function recommendation, which recommends test functions for test engineers to implement test cases formed with various test steps. This paper introduces an approach named TOKTER, which recommends test functions leveraging test-oriented knowledge graphs. Such a graph contains domain concepts and their relationships related to the system under test and the test harness, which is constructed from the corpus data of the concerned test project. TOKTER harnesses the semantic associations between test steps (or queries) and test functions by considering literal descriptions, test function parameters, and historical data. We evaluated TOKTER with an industrial dataset and compared it with three state-of-the-art approaches. Results show that TOKTER significantly outperformed the baseline by margins of at least 36.6% in mean average precision (MAP), 19.6% in mean reciprocal rank (MRR), and 1.9% in mean recall (MR) for the top-10 recommendations.

1. Introduction

Utilizing Application Programming Interfaces (APIs) is common in software development. Studies indicate that approximately half of the method calls in Java projects are API-related [1]. Harnessing the power of APIs for programming is of great value. Nevertheless, it is difficult for developers to master the knowledge of all APIs in a library. Therefore, to find proper APIs to use, engineers must study API documentation and other relevant documents and even search for online help. The study in [2] shows that effective understanding and use of APIs depend on domain concepts, API usage patterns, and API execution facts such as inputs, outputs, and side-effects [2]. Most existing API recommendation methods utilize API usage patterns [3,4,5] and API execution facts [6] that are collected from historical data sets. Some API recommendation studies are called with knowledge graphs [7,8] but only utilize Mashup-API co-invocation patterns and service category attributes [7] or properties of the third-party libraries (e.g., version, groupID and language) [8]. These studies do not use domain knowledge, such as domain concepts and the semantic relations among them, while these are the key concerns in knowledge-graph-based tasks [9,10].

Like API recommendations, test function recommendations focus on recommending test function(s) to realize a given test step as a query. However, there exist fundamental differences between recommending test functions and APIs. First, test functions are used in a confined domain, i.e., for testing a specific System Under Test (SUT), whereas APIs (e.g., standard and third-party libraries) are used in a more open application context. Second, test functions embody domain knowledge in more implicit ways; as discussed in our previous study [11], test functions from industrial datasets have significantly fewer words to describe their functionalities than methods from standard API libraries, and a test function library is not intended to be used externally for testing other systems.

Since test functions are used in more confined domains and are usually developed to test a specific software product, as opposed to using APIs from libraries for programming, test engineers often search for test functions by reading through existing test scripts or obtaining helps from senior peers. Hence, test function recommendations usually face the challenge called “cold start”, a phenomenon where effective inferences are hindered by insufficient historical data. Numerous API recommendation methods depend on historical data, e.g., feature request history [3], Stack Overflow posts [4], and clickthrough data from search engines [12]. These methods work well when historical data are abundant; otherwise, their performances significantly degrade. According to the study reported in [4], utilizing only API documentation as a data source is 16.9% as effective as compared to utilizing both Stack Overflow posts and API documentation. Since domain knowledge can compensate for the insufficiency of historical data effectively [13,14], it is a valuable solution to overcome the “cold start” challenge.

The second challenge is called “semantic gap”, which denotes that gaps exist between the description of a test step and the description(s) of test function(s) implementing the test step [4,11]. One of the main causes of the semantic gap is that different engineers express concepts or test behaviors in different words, though they are equivalent in semantics. For example, “Synchronous Digital Hierarchy” and its abbreviation “SDH” are both used in the test step and test function description. Recommending testing functions becomes difficult without such domain knowledge that “SDH” and “Synchronous Digital Hierarchy” are synonymous. The other reason is that the words or phrases used in test steps and test function descriptions are different but semantically related. For example, as we observed in the Huawei data set, the test step “create an EPL service” is implemented by test function “create_eth” whose description is “create an Ethernet service”. Misunderstanding might happen when a test engineer does not know that the “EPL service” is a type of “Ethernet service”. In the past, efforts have been made to overcome the semantic gap using latent semantic analysis but still failed to recommend test functions accurately due to the lack of historical data [11].

To address the aforementioned two challenges, we propose an approach named TOKTER for a test function recommendation based on a test-oriented knowledge graph capturing domain knowledge about the system under test (SUT) and test harness. The domain knowledge about SUT comprises domain concepts that specify its functionalities, business flows, data definitions, etc., and their relations (e.g., synonymy, hyponymy, and association). The domain knowledge about the test harness refers to the structure in which a specific testing project is developed and managed, e.g., test cases, test steps, test functions and their parameters, and the relations among these artifacts. TOKTER first constructs a test-oriented knowledge graph using the corpus data of a given test project, then recommends test functions based on the constructed knowledge graph by using the semantic relations between test steps (i.e., query) and test functions according to the literal descriptions, test function parameters, and historical occurrences.

To evaluate TOKTER, we choose BIKER [4], CLEAR [5], and SRTEF [11] as the comparison baselines and employ an industrial dataset from our industrial partner Huawei. We use the metrics of Mean Reciprocal Rank (MRR), Mean Average Precision (MAP), and Mean Recall (MR) to evaluate their performance. Results show that TOKTER achieved 0.743 in MAP, 0.824 in MRR, and 0.804 in MR for the top-10 recommendation results and significantly outperformed the baselines by more than 36.6% in MAP, 19.6% in MRR, and 1.9% in MR.

Contributions. (1) We propose a knowledge-graph-based test function recommendation approach, which utilizes both domain knowledge about the SUT and test harness; (2) we propose three types of meta-paths explicitly designed for test-oriented knowledge graphs, description-based, parameter-based, and history-based meta-paths, to discover candidate test functions from different perspectives; (3) we implement TOKTER as an open-source tool (https://anonymous.4open.science/r/TOKTER-78DE (accessed on 7 March 2024)); and (4) we evaluate TOKTER with an industrial dataset and demonstrate that it is practically useful and advances all the baselines.

Structure. Section 2 describes the background. TOKTER is presented in Section 3. We present the experimental design in Section 4, followed by experiment results and analyses in Section 5. The related work is described in Section 6, and the paper is concluded in Section 7.

2. Background

Knowledge graph offers a practical and effective way for capturing and representing concepts and relations among concepts, which is often specified with the Resource Description Framework (RDF) standard, whereby a node corresponds to an entity or concept, and an edge between two nodes denotes a relation between the corresponding entities or concepts. Its formal definition is given as follows.

Definition 1

(Knowledge Graph). A knowledge graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is a directed graph where $\mathcal{V}$ is the set of entities and $\mathcal{E}$ is the set of edges among entities. Each edge has the form of (head entity, relation, tail entity) (denoted as $<e_h,r,e_t>$), indicating a relation of r from entity $e_h$ to entity $e_t$.

For example, (cat, kind of, mammal) declares that a cat is a kind of mammal. As a heterogeneous network, a knowledge graph can contain multiple types of entities and relations. Knowledge graphs have been widely applied, for instance, in search engines [10,15], recommending systems [16,17], and question answering systems [9,18], etc.

There are two kinds of knowledge graphs: cross-domain (or generic) ones, e.g., Freebase [19], DBpedia [20], and YAGO [21], and domain-specific ones, e.g., MovieLens [22]. The test function recommendation needs a domain-specific knowledge graph to capture the links between domain knowledge and a confined specific test project instead of these public cross-domain knowledge graphs. In current studies of constructing domain-specific knowledge graphs, despite the adoption of complex, trained linguistic analyzers (e.g., dependency parser), manual work by domain experts is still indispensable to achieve good results [23,24,25].

To facilitate the construction of a knowledge graph, a network schema has been introduced to specify the structure of a knowledge graph at a meta-level (schema-level) [26] and to define types of entities and relations. Its formal definition is provided as follows.

Definition 2

(Network Schema). A network schema, denoted as $T_G=(\mathcal{A},\mathcal{R})$, is a meta template for a knowledge graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with the entity-type mapping $\Phi :\mathcal{V}\to \mathcal{A}$ and the relation-type mapping $\Psi :\mathcal{E}\to \mathcal{R}$, which is a directed graph defined over entity types $\mathcal{A}$, with edges as relations from $\mathcal{R}$.

For example, the bibliographic information network is a typical knowledge graph, also known as a heterogeneous information network [26]. It contains four types of entities: papers (P), venues (i.e., conferences/journals) (C), authors (A), and terms (T). Each paper $p\in P$ has links to a set of authors, a venue, a set of words as terms in the title, a set of citing papers, and a set of cited papers. The network schema for this bibliographic information network is shown in Figure 1a.

In a knowledge graph, a meta-path is a sequence of relations connecting more than two entities. As shown in Figure 1b, the author and paper can be connected via $Author\stackrel{writing}{\to }Paper\stackrel{published-by}{\to }Venue\stackrel{publishing}{\to }Paper$ path. For a given author, this meta-path identifies papers published in the same venue as the author’s publications. In this meta-path, $Author$ represents the category of entities rather than individual authors; then, such a path is called a meta-path. Its formal definition is given below.

Definition 3

(Meta-path). A meta-path $\mathcal{P}={\mathcal{A}}_0\stackrel{{\mathcal{R}}_1}{\to }{\mathcal{A}}_1\stackrel{{\mathcal{R}}_2}{\to }\cdots \stackrel{{\mathcal{R}}_k}{\to }{\mathcal{A}}_k$ is a path defined on the graph of network schema $T_G=(\mathcal{A},\mathcal{R})$. A meta-path defines a new composite relation ${\mathcal{R}}_1,{\mathcal{R}}_2,\cdots ,{\mathcal{R}}_k$ between type ${\mathcal{A}}_0$ and ${\mathcal{A}}_k$, where ${\mathcal{A}}_i\in \mathcal{A}$ and ${\mathcal{R}}_i\in \mathcal{R}$ for $i=0,1,\cdots ,k$. Informative meta-paths in a knowledge graph are often engineered manually based on domain knowledge or expertise [27].

3. Approach

As shown in Figure 2, TOKTER first constructs the test-oriented knowledge graph based on the corpus data, e.g., test function and SUT documentations and historical test cases (Section 3.1) from a given test project. Then, TOKTER links the query to the knowledge graph and finds path instances with meta-paths defined in the network schema. After computing scores between the query and test functions within the path instances, TOKTER ranks candidate test functions as recommendation results (Section 3.2). After introducing TOKTER, we use an illustrative example to describe the process of a testing function recommendation (Section 3.3).

3.1. Constructing the Test-Oriented Knowledge Graph

3.1.1. Specification

In this section, we define the network schema of the test-oriented knowledge graph, as shown in Figure 3. This test-oriented knowledge graph captures the domain knowledge about the SUT and test harness. The domain knowledge about the SUT refers to domain concepts and their relations in the SUT domain, e.g., synonymy, hyponymy, and association, which have been extensively used in the literature [28,29]. A synonymy relation of two words indicates whether the senses of the two words represent the near identity. For example,“SDH” and “Synchronous Digital Hierarchy” are both domain concept entities in a knowledge graph. Although they differ in the description text, both refer to the same type of equipment. It is easy for humans with domain knowledge to determine that “SDH” is an abbreviation of “Synchronous Digital Hierarchy”, and there is a synonymous relation between these two entities (

Table 1. Relations in the test-oriented knowledge graph.

Relation	Description
$DC\stackrel{syn}{⟷}DC$	Two domain concepts are synonymous.
$DC\stackrel{hyp}{⟷}DC$	One domain concept is a type of the other.
$DC\stackrel{asso}{⟷}DC$	Two domain concepts are associated.
$TF/TS/FP\stackrel{rel}{⟷}DC$	A test function, test step, or function parameter is related to a domain concept.
$TF\stackrel{impl}{⟷}TS$	A test step is implemented by a test function.
$TF\stackrel{cont}{⟷}FP$	A test function contains a function parameter.

). However, it is very difficult for a recommendation algorithm to identify such synonymy relations automatically. A hyponymy relation of two entities A and B is the inclusiveness sense relation that means A is a kind or type of B. For example, because “Java code” is a kind of “program code”, we can identify the hyponymy relation between these two entities. An association relation between two domain concept entities indicates that they are semantically related and can have certain interactions in the domain. For example, there is an association relation between two domain concept entities: “precomputing” and “business path”. That means the domain concepts of “precomputing” and “business path” may interact in the testing domain, e.g., “precomputing the business paths for the ETH service”.

Test-harness domain knowledge refers to connected test artifacts, e.g., test functions and their parameters, test steps of historical test cases, and relations among these artifacts. TOKTER captures three types of entities: the test step, test function, and function parameter. Since test functions implement test behaviors of test steps, there exist implementation relations between test functions and test steps. A test function has a relation of containment with function parameters, which are the necessary part of the test function specification.

Moreover, relations need to be established between domain concept entities from the SUT domain and entities of test steps, test functions, and function parameters from the test harness, which are named related_to_dc relations where “dc” abbreviates “domain concept”.

3.1.2. Overall Process

Constructing a test-oriented knowledge graph involves entity recognition and relation extraction (Figure 2). The process’s input includes test function and SUT documentations, and historical test cases. Test function documentation describes test functions and their parameters. SUT documentation provides the necessary information about functional interfaces, data definitions, and operations of the SUT so that tests can be conducted. A historical test case has been used to test the SUT and has sequential literal test steps. Each test step has the test function(s) that implement its test behavior. For instance, as shown in

Table 2. An example test case.

operate(“Select a port to create an SDH service.”) {

@sdh1= @sdh.create_sdh()

}

expect(“Confirm whether the service was created successfully.”) {

@sdh1.query_sdh()

}

operate(“Create another SDH service through the same port.”) {

@sdh2= @sdh.create_sdh()

}

expect(“Check if the service failed to be created.”) {

@sdh2.query_sdh()

}

operate(“Delete all SDH services.”) {

@sdh.delete_sdh()

}

, the test case aims to test the creation, querying, and deletion of two SDH services via five test steps. Each test step describes the test behavior in natural language and a test function that implements the behavior. Based on such information, TOKTER recognizes entities and extracts relations among the recognized entities.

3.1.3. Entity Recognition

Since test engineers have already implemented the test functions and specified the test function documentation, test function entities and function parameter entities can be accurately identified by parsing the test function documentation. Similarly, test step entities can be identified by parsing the provided historical test cases.

The recognition of domain concepts from SUT documentation, on the other hand, is a typical NLP problem in domain-specific knowledge-graph construction [23,30,31,32]. We first use mutual information and branch entropy to obtain a list of domain concept candidates and then, with the aid of domain experts, filter out irrelevant domain concepts and supplement the necessary ones that are not identified or even not present in SUT documentation. Mutual information refers to the degree of correlation between word x and word y in the same phrase w [33], which can be computed with the following formula:

$$MI\left(w\right)=MI(x,y)={log}_2\frac{p(x,y)}{p\left(x\right)p\left(y\right)}$$

(1)

where $p\left(x\right)$, $p\left(y\right)$ represent the probability of word x, y appearing in the corpus, respectively; $p(x,y)$ represents the probability of words x and y appearing in the corpus together. A greater mutual information value between words x and y indicates a greater correlation and a greater possibility that phrase w can be treated as a domain phrase.

Branch entropy measures the diversity and complexity of domain phrases by calculating the entropy of their adjacent words [34]. A domain phrase has left-branch and right-branch entropy to specify the diversity of its left and right adjacent words, respectively. The minimal one is chosen as its branch entropy of a domain phrase, a common way for calculating branch entropy [34], as shown below:

$$BE\left(w\right)=min(B{E}_L\left(w\right),B{E}_R\left(w\right))$$

(2)

The left-branch entropy $B{E}_L$ and right-branch entropy $B{E}_R$ can be computed with the following formula:

$$B{E}_L\left(w\right)=-\sum _{w_l\in s_l}p(w_l\mid w)logp(w_l\mid w)$$

(3)

$$B{E}_R\left(w\right)=-\sum _{w_r\in s_r}p(w_r\mid w)logp(w_r\mid w)$$

(4)

where $s_l$ (or $s_r$) denotes the set of left (or right) adjacent words of w; $p(w_l\mid w)$ (or $p(w_r\mid w)$) denotes the probability that $w_l$ (or $w_r$) is the left (or right) adjacent word of domain phrase w. A bigger branch entropy tells more various words adjacent to w, thus a greater possibility that w is a domain phrase. After calculating $MI\left(w\right)$ and $BE\left(w\right)$, we use the formula below to calculate scores of candidate domain phrase w:

$$S_{dp}\left(w\right)=MI\left(w\right)\times BE\left(w\right)$$

(5)

Ranking by $S_{dp}\left(w\right)$ makes it easier for domain experts to validate if candidate domain phrases are true domain concepts during a review process. Domain experts can also supplement domain concepts when needed.

3.1.4. Relation Extraction

As summarized in Table 1, TOKTER needs to extract six types of relations: synonymy, hyponymy, association, related_to_dc, implementation, and containment. We use a rule-based approach to extract them from the corpus, i.e., the test functions and SUT documentations, and the historical test cases. In relation extraction, we treat these corpus data as unstructured texts as we use the dependency parser to obtain dependency trees from sentences in the corpus, a common practice in ontology construction [35,36].

A synonymy relation $DC\stackrel{syn}{⟷}DC$ means that the two domain concepts are synonymous. The most commonly applied synonymy knowledge base is BabelNet [37], which is a semantic network connecting about 22 million entities, with each entity expressing a given meaning and its related synonyms. Synonymy relations are across different languages, making it more suitable for situations where both Chinese and English words exist. TOKTER first uses BabelNet to obtain all synonyms of the domain concept entities identified in the entity extraction phase. Note that synonyms of domain concept entities also need to be domain concept entities.

A hyponymy relation $DC\stackrel{hyp}{⟷}DC$ means that one domain concept is a type of the other. An association relation $D{C}_1\stackrel{asso}{⟷}D{C}_2$ is a relation between two domain concept entities, denoting a communication path (also called a link) between them. In this paper, the extraction of hyponymy and association relations uses the same rule based on the results of a dependency parser, which identifies the dependencies between words in a sentence [38]. The two domain concept entities, $D{C}_1$ and $D{C}_2$, have a hyponymy relation when they satisfy the following rule:

$$\left\{\begin{array}{c}ter{m}_2\stackrel{amod/nn}{\to }ter{m}_1\\ ter{m}_1+ter{m}_2=D{C}_1\\ ter{m}_2=D{C}_2\end{array}\right.$$

(6)

This rule tells that if $D{C}_1$ has $ter{m}_1$ and $ter{m}_2$ and $D{C}_2$ is $ter{m}_2$, there should be an amod (adjectival modifier) or nn (noun compound modifier) grammatical relation between $ter{m}_1$ and $ter{m}_2$, then a hyponymy relation can be identified between $D{C}_1$ and $D{C}_2$. Notice that the amod and nn grammatical relations are widely used in knowledge-graph construction [10,39,40].

Figure 4 shows the dependency tree of the sentence “Create a static tunnel and specify the interface type as ETH subinterface”. In this dependency tree, three hyponymy relations can be extracted based on the above rule: $‘‘statictunne{l}^{\prime \prime }\stackrel{hyp}{⟷}‘‘tunne{l}^{\prime \prime }$, $‘‘interfacetyp{e}^{\prime \prime }\stackrel{hyp}{⟷}‘‘typ{e}^{\prime \prime }$, and $‘‘ETHsubinterfac{e}^{\prime \prime }\stackrel{hyp}{⟷}‘‘subinterfac{e}^{\prime \prime }$.

Two domain concept entities $D{C}_1$ and $D{C}_2$ can have an association relation ($D{C}_1\stackrel{asso}{⟷}D{C}_2$) if there is a $dobj$ (direct object) or $nsubj$ (nominal subject) grammatical relation between them. They are widely used grammatical relations in knowledge graph construction [10,39,40].

$$D{C}_1\stackrel{dobj/nsubj}{\to }D{C}_2$$

(7)

Figure 5 shows the dependency trees of two sentences: “delete the SDH service” (Figure 5a) and “confirm whether the service was created successfully” (Figure 5b). In the dependency trees, two association relations can be extracted based on the following dobj and nsubj grammatical relations: $‘‘delet{e}^{\prime \prime }\stackrel{dobj}{⟷}‘‘servic{e}^{\prime \prime }$ and $‘‘servic{e}^{\prime \prime }\stackrel{nsubj}{⟷}‘‘create{d}^{\prime \prime }$.

Relation $TF/TS/FP\stackrel{rel}{⟷}DC$ indicates whether an entity of test function (TF), test step (TS), or function parameter (FP) is related to a domain concept entity (DC). TOKTER segments the descriptions of test steps, test functions, and function parameters at first into a set of phrases by using the word segmentation tool HanLP [41]. For any segmented phrase $s{p}_i$, if there is a domain concept entity $dce$ matches, i.e., $s{p}_i$ is literally identical to the name of $dce$, then a related_to_dc relation between $s{p}_i$ and $dce$ would be constructed.

Implementation relation $TF\stackrel{impl}{⟷}TS$ and containment relation $TF\stackrel{cont}{⟷}FP$ are explicitly specified and can be extracted from the historical test cases and test function documentation for a given test project directly.

3.2. Recommending Test Functions

3.2.1. Meta-Paths

To enable test function recommendation with test-oriented knowledge graphs, we design three types of meta-paths based on the defined schema, description-based, parameter-based, and history-based meta-paths, to capture semantic links from a query to test functions (

Table 3. All types of meta-paths of TOKTER.

Meta-Path	Semantics	Type
$Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}TF$ $Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}TF$	Extract test functions whose functional descriptions are semantically related to the query	description-based
$Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}FP\stackrel{cont}{⟷}TF$ $Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}FP\stackrel{cont}{⟷}TF$	Extract test functions whose parameters are semantically related to the query	parameter-based
$Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}TS\stackrel{impl}{⟷}TF$ $Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}TS\stackrel{impl}{⟷}TF$	Extract test functions historically used to implement some test steps that are semantically related to the query	history-based

).

Using description-based meta-paths, we can recommend semantically similar test functions regarding function descriptions. The starting node and target node of a description-based meta-path are the query Q and the test function $TF$, respectively, which remain unchanged. Domain concept entities are in-between nodes, which entail semantics between the query and the test function. In this paper, we categorize the use of domain concept entities as 1-hop and 2-hop, common configurations in the literature [42]. $Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}TF$ is a 1-hop description-based meta-path as it only uses a single domain concept entity to connect Q and $TF$. $Q\stackrel{rel}{⟷}DC1\stackrel{\ast }{⟷}DC2\stackrel{rel}{⟷}TF$ is a 2-hop description-based meta-path as it sequentially uses two different domain concept entities to connect Q and $TF$, and the relation between these two entities can be synonymy, hyponymy, or association, which is represented with the “*”.

For parameter-based and history-based meta-paths, domain concept entities connect the query Q to function parameters $FP$ and test steps $TS$, respectively. The use of domain concept entities is also categorized into 1-hop and 2-hop configurations. With parameter-based meta-paths, we can recommend test functions whose parameters are semantically related to the query. With history-based meta-paths, we can recommend test functions that have previously implemented some test steps similar to the given query.

3.2.2. Test Function Recommendation with Meta-Paths

In recommending test functions, TOKTER first segments a given query (i.e., a literal test step) into a set of query phrases. If any query phrase matches a domain concept entity in the knowledge graph, a related_to_dc relation between it and the query is constructed, implying that the query is linked to the knowledge graph. After that, all such links can be identified such that path instances of meta-paths $(p_1,p_2,\dots ,p_n)$, donated as P, are retrieved from the knowledge graph to connect a given query Q to a given test function $TF$. TOKTER then calculates the score between Q and the test function $TF$ with the following formula to decide its ranking:

$$\begin{array}{c}\hfill Score(Q,TF)=\frac{ndl(Q,P)\ast ndl(TF,P)\ast wrc\left(P\right)}{ndl\left(Q\right)\ast ndl\left(TF\right)}\\ \hfill whereP=f(Q,TF)\end{array}$$

(8)

where $ndl\left(Q\right)$ and $ndl\left(TF\right)$ are the total numbers of domain concept entities linked to query Q and test function $TF$ in the knowledge graph, respectively; $f(Q,TF)$ is a search process that would return path instances P matched with meta-paths according to Q and $TF$, as shown in Algorithm 1. The function $MaxLen$ calculates the maximum length of all meta-paths M. $p.endnode$ returns the end node of path p. $G.neiberhoods$ returns all neighboring nodes of $start$ in the knowledge graph G. $MatchMetaPath$ is used to determine whether the path $p+n$ matches one of the meta-paths M. This algorithm belongs to depth-first traversal algorithms, incorporating pruning techniques.

Algorithm 1 Path Instances Search Algorithm

Identifier: PathSearch(G, M, Q, $TF$, p) Input: knowledge graph G, mate-paths M, query Q, test function $TF$, temporary path p Output: path instances P 1: $max\_len\leftarrow MaxLen\left(M\right)$ 2: if  $p=\left\{\right\}$  then 3:     $p\leftarrow \left\{Q\right\}$ 4: if  $len\left(p\right)\ge max\_len$  then 5:     return P 6: $start\leftarrow p.endnode$ 7: for  $n\leftarrow G.neiberhoods\left(start\right)$  do 8:       if $MatchMetaPath(p+n,M)$ then 9:             $P\leftarrow p+n$ 10:     else 11:           $P\leftarrow PathSearch(G,M,Q,TF,p)$

$wrc\left(P\right)$ is the total weights of relations captured in P. $ndl(Q,P)$ and $ndl(TF,P)$ only count the numbers of domain concept entities linked to Q and $TF$ which appear in path set P, respectively. $wrc\left(P\right)$ calculates relation weights for path set P with the formula below:

$$wrc\left(P\right)=\frac{1}{\left|P\right|}\sum _{p\in P}^P\prod _{r_j\in r\left(p\right)}weight\left(r_j\right)$$

(9)

where $\left|P\right|$ is the number of path instances in P, $r\left(p\right)$ is the set of all relations that appeared in path p, and $weight\left(r_j\right)$ denotes the weight for relation $r_j$ in $r\left(p\right)$. Indeed, different types of relations do not have the same semantic importance. For the relations listed in Table 1, since the related_to_dc relation is extracted when two entities have the same text and the implementation and containment relations are explicitly specified in documents, these three ones have the least uncertainty and thus have the biggest weights. The other three relations (i.e., synonymy, hyponymy, and association relations) are difficult to extract with 100% certainty due to the use of NLP techniques. In particular, the association relation is inherently uncertain since it would be extracted only when a $dobj$ or $nsubj$ grammatical relation is present in a dependency tree. Therefore, we give relations of the synonymy and hyponymy relations smaller weights and the association relation the smallest weight, as shown below:

$$weight\left(r\right)=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}\mathrm{r}\mathrm{is}\mathrm{a}related\_to\_dc/implementation/\hfill \\ \hfill & containment/synonymy\mathrm{relation}\hfill \\ \frac{1}{2},\hfill & \mathrm{if}\mathrm{r}\mathrm{is}\mathrm{a}hyponymy\mathrm{relation}\hfill \\ \frac{1}{3},\hfill & \mathrm{if}\mathrm{r}\mathrm{is}\mathrm{an}association\mathrm{relation}\hfill \end{array}\right.$$

(10)

In the end, we rank any test function $TF$ for given query Q by using the score function $Score(Q,TF)$ and obtain the top-10 test functions as recommendation results.

3.3. Example

In order to describe the process of test function recommendation more clearly, we give a small illustrative example containing all types of entities and relations, as shown in Figure 6. The example contains 8 domain concept entities, 4 test function entities, 1 test step entity, and 1 function parameter entity. Furthermore, there are 1 synonym relation, 2 hyponymy relations, 1 association relation, 13 related_to_dc relations, 1 implementation relation, and 1 containment relation among these entities.

For the given test step “create an SDH service” (Q), three related_to_dc relations ($Q\stackrel{rel}{⟷}create\left(DC\right)$, $Q\stackrel{rel}{⟷}SDH\left(DC\right)$, and $Q\stackrel{rel}{⟷}service\left(DC\right)$) can be established with the test-oriented knowledge graph after word segmentation. After that, TOKTER searches all path instances of meta-paths from given query Q to each test function $TF$. For example, from the query Q to the test function “create_sdh” ($TF$), there are five different path instances that conform to the meta-paths as shown in

Table 4. Path instances that conform to the meta-paths.

Path Instance	Meta-Path
$Q\stackrel{rel}{⟷}service\left(DC\right)\stackrel{rel}{⟷}create\_sdh\left(TF\right)$	$Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}TF$
$Q\stackrel{rel}{⟷}create\left(DC\right)\stackrel{rel}{⟷}create\_sdh\left(TF\right)$	$Q\stackrel{rel}{⟷}DC\stackrel{rel}{⟷}TF$
$Q\stackrel{rel}{⟷}service\left(DC\right)\stackrel{asso}{⟷}create\left(DC\right)\stackrel{rel}{⟷}create\_sdh\left(TF\right)$	$Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}TF$
$Q\stackrel{rel}{⟷}SDH\left(DC\right)\stackrel{syn}{⟷}SynchronousDigitalHierarchy\left(DC\right)\stackrel{rel}{⟷}create\_sdh\left(TF\right)$	$Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}TF$
$Q\stackrel{rel}{⟷}create\left(DC\right)\stackrel{asso}{⟷}service\left(DC\right)\stackrel{rel}{⟷}create\_sdh\left(TF\right)$	$Q\stackrel{rel}{⟷}DC\stackrel{\ast }{⟷}DC\stackrel{rel}{⟷}TF$

. According to the $Score(Q,TF)$ (Equation (8)), we can calculate that the score between Q and the test function “create_sdh” ($TF$) is 0.733. Similarly, we can calculate the score between Q and the other three test functions (“create_eth”, “create_eth_path” and “query_sdh”) to be 0.407, 0.407, and 0.714. Thus, we can obtain the list of recommendation results by sorting the scores. The test function “create_sdh” with the highest score is exactly the ground truth.

4. Experiment Design

Baseline. To evaluate TOKTER, we select three baselines. BIKER [4] is a classic approach in API recommendation and is often used as a baseline in the literature [5,11,43]. BIKER exploits Stack Overflow posts and API documentation and tackles the task-API knowledge gap. BIKER uses a word embedding model to represent question (query) text and API description text. CLEAR [5] embeds the whole sentence of queries and Stack Overflow posts with a Bidirectional Encoder Representation from Transformers (BERT) model that can preserve the semantic-related sequential information. CLEAR is a state-of-the-art approach in API recommendation. We select CLEAR because it uses BERT and, hence, ensembles the performance of Large Language Models (LLM) on test function recommendations. We implemented and trained CLEAR according to the model settings described in [5]. SRTEF [11] exclusively recommends test functions based on weighted description similarity and scenario similarity. The former employs the Deep Structured Semantic Model (DSSM) to assess the relatedness between test steps and test functions based on their literal descriptions. The scenario similarity is calculated by considering both test scenarios and test function usage scenarios. We selected SRTEF as one of the baselines because it is the closest to TOKTER as both focus on test function recommendation.

Dataset. The dataset we use is from our industrial partner Huawei. The collaboration context is about testing a Network Cloud Engine-Transport (Huawei, Shenzhen, China) product, one of the components enabling the transformation of a transport network towards modern software-defined networking. The dataset consists of historical test cases, test function documentation, and SUT documentation. There are 6514 historical test cases implemented in Ruby, and each test case has 8.7 test steps on average. Since some test steps are included in more than one test case, there are, in total, 9924 unique test steps. Each test step contains one or several sentences written in Chinese embedded with some English terms and is implemented by 2.9 test functions on average.

Table 5. The number of test functions to implement a test step.

Test Functions for Implementing a Test Step	Test Step	Percentage
1	3559	35.9%
2	2030	20.4%
3	1376	13.9%
4	1064	10.7%
More than 4	1895	19.1%

shows the number of test functions used to realize a test step. According to the statistics, we randomly select 500 test steps with the corresponding test functions proportionally as testing data to evaluate TOKTER, including 180 test steps implemented by one test function, 102 test steps implemented by two test functions, 70 test steps implemented by three test functions, 53 test steps implemented by four test functions, and 95 test steps implemented by more than five test functions. The test set is exactly the same as in our previous study SRTEF [11].

The test function documentation contains 967 test functions. Each test function has a corresponding description in Chinese to explain its functionality and usage. There are a total of five documents related to the SUT. These documents encompass interface descriptions and functionality usages. We consider them as unstructured texts, which contain, in total, 109,978 sentences comprising 728,065 words.

Metrics. To compare TOKTER with the baseline approaches in terms of their effectiveness, we employ three metrics, Mean Average Precision (MAP), Mean Reciprocal Rank (MRR), and Mean Recall (MR), which are the classical metrics for information retrieval [44] and have been frequently used in software engineering studies [3,4,45,46,47,48,49]. MAP can be calculated with the following formula:

$$A{P}_q=\frac{1}{\left|T_q\right|}\sum _{i=1}^{\left|T_q\right|}\frac{i}{positio{n}_i}$$

(11)

$$MAP=\frac{1}{\left|Q_s\right|}\sum _{q\in Q_s}A{P}_q$$

(12)

where $T_q$ represents the set of test functions that actually implement the test step (corresponding to query q), and $\left|T_q\right|$ is the size of the test function set. $positio{n}_i$ represents the position or order at which the ith test function of $T_q$ appears in the recommendation list. For MAP, $Q_s$ represents all queries, and $\left|Q_s\right|$ is the number of those queries. For each query q in $Q_s$, the average precision $A{P}_q$ is calculated using Equation (11), and Equation (12) computes the mean of the $AP$ of all queries.

MRR can be calculated with the following formula:

$$MRR=\frac{1}{\left|Q_s\right|}\sum _{q\in Q_s}\frac{1}{ran{k}_q}$$

(13)

where $ran{k}_q$ is the ranking of the first test function in $T_q$ for query q.

MR can be calculated with the following formula:

$$MR=\frac{1}{\left|Q_s\right|}\sum _{q\in Q_s}\frac{\left|R_q\cap T_q\right|}{\left|T_q\right|}$$

(14)

where $\left|R_q\cap T_q\right|$ is the number of test functions for query q, and $\left|T_q\right|$ is the number of test functions that actually implement q.

Since in recommendation tasks, top-matched results are of great interest in practice, we evaluate TOKTER and the baselines with their top-10 recommendation results, which is commonly applied in API recommendation studies [3,45].

Statistical Test. We use the non-parametric Wilcoxon signed-rank test [50], which has been widely used in API recommendation studies [4,5] to test whether there are statistically significant differences in the effectiveness and time cost of different approaches or strategies, with a significance level of 0.05. We also use the Spearman correlation analysis to assess the correlation between recommendation time and the number of domain concept entities connected to the query.

Tool Implementation. The tool contains two functionalities, test-oriented knowledge graph construction and test function recommendation, both implemented in Python. For the construction of the test-oriented knowledge graph, TOKTER utilizes the NLP tool HanLP [41] for segmentation and dependency parsing, along with the NetworkX tool [51] for representing and storing knowledge graphs. For the test function recommendation, TOKTER implements the algorithm that searches for path instances matching the meta-path on the constructed knowledge graph in Python. It then ranks and recommends all test functions based on the scores of all path instances. We implement TOKTER as an open-source tool.

Experiment Execution. For training the CLEAR baseline, we utilized cloud computing resources (running about 20 h on NVIDIA V100 GPU (Nvidia Corporation, Santa Clara, CA, USA) and Intel Golden 6240 CPU (Intel Corporation, Santa Clara, CA, USA) with CentOS 7.6 system). Due to the substantial scale of the BERT model used in CLEAR, fine-tuning the pre-trained BERT model on the dataset is time-consuming. The process of recommending test functions using the four methods was conducted on a PC equipped with AMD Ryzen 7 1700X CPU (AMD, Santa Clara, CA, USA), running Windows 10 (64-bit).

Research Questions (RQs). RQ1: How effective is TOKTER compared with the three baseline approaches? These baselines use different models (i.e., word embedding, BERT, and DSSM) to measure the semantic similarity between two sentences (e.g., queries, test steps) and improve the recommendation effectiveness with historical data. TOKTER relies on a test-oriented knowledge graph and uses meta-paths to recommend test functions. With RQ1, we aim to assess TOKTER’s effectiveness in recommending test functions, which justifies the need to employ a knowledge graph and the meta-paths.

RQ2: How is the time performance of TOKTER compared with the three baselines? To test the efficiency of TOKTER, we compared its time performance with the three baseline approaches. Furthermore, we discussed the factors that influence recommendation time.

RQ3: How does the size of the knowledge graph affect the effectiveness and time cost of TOKTER? Recall that TOKTER relies on domain experts to select relevant candidates of domain concept entities automatically identified by TOKTER and identify those missed by TOKTER. Consequently, the size of the test-oriented knowledge graph, to a certain extent, relates to the manual effort required from domain experts. Hence, we propose this RQ to study how the size of the knowledge graph affects the effectiveness of TOKTER.

RQ4: How effective are different meta-paths at contributing to TOKTER? Recall that TOKTER uses different types of meta-paths: description-based, parameter-based, and history-based meta-paths. With this RQ, we aim to investigate how using different meta-paths can influence the test function recommendation effectiveness and time cost of TOKTER.

5. Results and Analyses

In this section, we first describe the test-oriented knowledge graph generated by TOKTER (Section 5.1), followed by answering each RQ in Section 5.2, Section 5.3, Section 5.4 and Section 5.5.

5.1. Test-Oriented Knowledge Graph Generated with TOKTER

Descriptive statistics of the generated test-oriented knowledge graph are summarized in

Table 6. Descriptive statistics of the generated test-oriented knowledge graph.

Item	Count
Test function entities	967
Function parameter entities	3038
Test step entities	9424
Domain concept entities	1678
Synonymy relations	203
Hyponymy relations	290
Association relations	6750
Related_to_dc relations	57,462
Implementation relations	26,238
Containment relations	3038

. From the table, we can see that, after extracting entities and relations from the test function library, we obtained, in total, 967 test functions with 3038 function parameters. From the test case library (historical test cases), TOKTER extracted 9924 unique test steps, 500 of which were used as testing data. Hence, the remaining 9424 test steps were incorporated as test step entities in the test-oriented knowledge graph.

TOKTER initially acquired 8931 candidates of domain concept entities (Section 3.1.3). After a review process by two domain experts, 1536 suitable cases were selected, and 142 were added. In fact, the ranking metric ($S_{dp}\left(w\right)$ defined in Formula (5)) has been very helpful for filtering domain concept entities. Domain experts selected 56 domain concepts from the top 100 candidates and 474 domain concepts from the top 1000 candidates. The average $S_{dp}\left(w\right)$ for the selected 1536 domain concepts is 1469.27, while the average $S_{dp}\left(w\right)$ for all candidates is 658.559. Eventually, we obtained 1678 (1536 + 142) domain concept entities. The review process took two days, which is acceptable to our industrial partner. We also want to point out that this review process is a one-time effort. When the knowledge graph needs to be updated, it is just about updating the domain concepts in the knowledge graph (mostly adding new domain concepts), followed by the automatic extraction of relations with TOKTER.

After entity recognition, TOKTER extracts relations (Section 3.1.4), which resulted in 203 synonymy, 290 hyponymy, 6750 association, 57,462 related_to_dc, 26,238 implementation, and 3038 containment relations. Note that domain experts do not need to check these relations manually.

5.2. RQ1: Evaluating TOKTER’s Effectiveness

To answer this RQ, we evaluated TOKTER with all meta-paths applied by comparing it with the three baselines in terms of their performance on the same industrial dataset (Section 4). Results are presented in

Table 7. Effectiveness of TOKTER and the baseline approaches.

Approach	MAP	MRR	MR
BIKER	0.365	0.518	0.602
SRTEF	0.544	0.689	0.753
CLEAR	0.527	0.603	0.789
TOKTER	0.743	0.824	0.804

.

From Table 7, we observe that TOKTER performed the best, followed by SRTEF and CLEAR with comparable performance, and BIKER, which performed the worst. This is because BIKER’s word embedding model is weaker in capturing semantics than the DSSM model employed by SRTEF and the BERT model used by CLEAR. We conducted the Wilcoxon signed-rank test to compare the performances of TOKTER and the baselines with the 500 queries (we used the SPSS tool to perform these tests, and the results were also put into the open source repository). Results show that TOKTER achieves significantly better performance than all baselines (p < 0.05). The standard deviations of the average precision (AP) metric for the BIKER, SRTEF, CLEAR, and TOKTER methods on 500 test queries are 0.121, 0.122, 0.132, and 0.134, respectively, which are quite small. TOKTER performed the best (0.743 in MAP, 0.824 in MRR, and 0.804 in MR) because it explores semantic relations between queries and test functions by utilizing domain knowledge capturing relations among domain concepts from the SUT and test steps, test functions, and their parameters of a test project. Moreover, TOKTER searches for semantically matched test functions comprehensively from descriptions, function parameters, and historical data via the meta-paths.

5.3. RQ2: Evaluating TOKTER’s Time Performance

To answer this RQ, we collected time spent by TOKTER and the three baselines on preparation and recommendation. Results are presented in

Table 8. Time cost of TOKTER and the baseline approaches—RQ2.

Approach	Training/Caching	Recommendation
BIKER	0.02 h	2.4 s/query
SRTEF	2.17 h	0.041 s/query
CLEAR	20 h	0.057 s/query
TOKTER	0.19 h	0.647 s/query

.

During the setup phase, the primary task for the three baselines is training their respective models. In the case of TOKTER, the time cost for setup is mainly about caching all paths in the test-oriented knowledge graph to accelerate the recommendation. As shown in Table 8, TOKTER took a shorter setup time than CLEAR and SRTEF. CLEAR’s training time is the longest due to the significantly large scale of the BERT model (with 134 million parameters) used in CLEAR.

Regarding the recommendation time, from the table, we can see that TOKTER, SRTEF, and CLEAR took less than one second per query, while BIKER took 2.4 s per query. The main reason is that BIKER transforms each word in a text description into a word vector using its word embedding model, which requires a looped comparison for each word in the sentence. SRTEF and CLEAR, instead, represent queries, test steps, and test functions as vectors, and comparing vectors is computationally efficient. TOKTER searches for relevant test functions through the test-oriented knowledge graph, which requires a bit longer time than SRTEF and CLEAR. However, 0.6 s per query is acceptable in industrial practice.

The distribution of recommendation time for each query is shown in Figure 7. We can observe from the figure that TOKTER is relatively consistent, with recommendation time clustering around 0.4–0.8 s. Only 10 out of 500 cases have 1.2–2.0 s spent. We notice that there are 53 cases for which TOKTER performed very efficiently (within the range of 0.2–0.4 s). After carefully checking these cases, we noticed that there are relatively few connections between queries and domain concept entities in the test-oriented knowledge graph.

Furthermore, we conducted a Spearman’s Rank Correlation analysis between recommendation time and the number of nodes linked to Q, i.e., $ndl\left(Q\right)$, in the knowledge graph, which are all domain concept entities, ranging from 1 to 17. The correlation coefficient is 0.891 (p-value < 0.05), indicating a significant and very strong positive correlation. It is also easy to understand that the more entities connected to a query, the more paths need to be searched, resulting in a longer recommendation time.

5.4. RQ3: Impact of the Knowledge Graph Size

To answer this RQ, we evaluate the effectiveness and time cost of TOKTER when being configured with test-oriented knowledge graphs at different scales. As shown in Table 6, among the four types of entities in the knowledge graph, the proportion of domain concept entities is roughly 11%, which is the smallest. Once the test function library and historical test cases are determined, the quantities of test functions, parameters, and test steps remain constant across different knowledge graphs. Therefore, knowledge graph construction’s quality and time cost depend solely on the domain concept entities. Thus, variations in the size of the knowledge graph are reflected in the number of included domain concept entities.

In real projects, it is often seen that some domain concepts are more frequently used than others. In the domain of the SUT of this work, the minimum frequency of domain concepts is 9; the maximum is 48,547; the average is 530.01; and the median is 102. The frequency distribution of domain concepts is shown in Figure 8. More frequently used domain concepts are typically given priority in the construction of knowledge graphs. Therefore, we sort all valid domain concepts in descending order of the frequencies of their occurrences in the corpus. After that, we sequentially selected the top 10%, top 20%, …, and 100% of the domain concepts to form 10 test-oriented knowledge graphs.

Table 9. Effectiveness and time cost of TOKTER across 10 test-oriented knowledge graphs of various sizes.

Top% Domain Concepts	MAP	MRR	MR	Time *
10%	0.111	0.116	0.115	0.210
20%	0.439	0.474	0.462	0.496
30%	0.623	0.687	0.659	0.574
40%	0.691	0.766	0.727	0.606
50%	0.706	0.780	0.754	0.621
60%	0.733	0.810	0.787	0.627
70%	0.731	0.809	0.786	0.639
80%	0.743	0.823	0.804	0.640
90%	0.748	0.829	0.808	0.643
100%	0.743	0.824	0.802	0.647

* Time is measured in seconds.

summarizes the effectiveness and time cost of TOKTER with test-oriented knowledge graphs of various sizes. Results show that with 10% of domain concepts, TOKTER only achieved ≈0.11 MAP, MRR, and MR. As the size of the graph increases, TOKTER’s effectiveness rapidly improves, implying that the completeness of the domain concepts in the knowledge graph has a great impact on TOKTER’s recommendation. Regarding the time cost (i.e., recommendation time), along with the increase in the number of domain concept entities in the knowledge graph, TOKTER’s recommendation time gets longer. This is because queries can be connected to more domain concept entities, leading to a growth in the number of path instances from the queries to test functions based on meta-paths, which need to be calculated.

From Figure 9, we can easily notice that the size of the knowledge graph increases to ≈60%, TOKTER’s effectiveness and time cost gains stabilize. We further conducted the Wilcoxon signed-rank test to compare the difference in the effectiveness and time cost of TOKTER when being combined with the knowledge graphs of two adjacent sizes (e.g., 0.2 and 0.3 of Top% domain concepts). Results show that once the size of the knowledge graph increases to ≈60%, the change in recommendation effectiveness is no longer significant. However, the recommendation time increases significantly with the increase in the knowledge graph’s scale. This message is important as it implies that there is a diminishing marginal benefit of continuously enriching the domain concepts in the test-oriented knowledge graph. Specifically, with ≈30% of the domain concepts, TOKTER can already achieve 83.3% of the optimal results in MAP, MRR, and MR. This observation is close to the Pareto principle, also known as the 80–20 rule, specifying that 80% of consequences come from 20% of the causes. This observation is useful as it helps determine the sufficiency level of the domain concepts while constructing the test-oriented knowledge graph, especially considering that manual effort from domain experts is required to verify domain concepts automatically extracted by TOKTER.

5.5. RQ4: Meta-Paths’ Contributions to TOKTER’s Performance

To answer this RQ, we set up TOKTER with seven various meta-path strategies, which are all possible combinations of one, two, or all three meta-path types, as listed in

Table 10. TOKTER’ performance with various meta-path strategies.

Meta-Path Strategies	MAP	MRR	MR	Time *
Only description-based	0.392	0.451	0.455	0.133
Only parameter-based	0.184	0.196	0.209	0.105
Only history-based	0.671	0.748	0.741	0.584
Description- and parameter-based	0.438	0.505	0.519	0.156
Parameter- and history-based	0.676	0.753	0.747	0.623
Description- and history-based	0.736	0.815	0.799	0.641
All	0.743	0.824	0.804	0.647

* Time is measured in seconds.

.

Table 10 shows that using any type of meta-paths alone is less effective than using all. In comparing the use of a single type of meta-paths, TOKTER with the parameter-based meta-path alone achieved the worst recommendation result, and TOKTER with only history-based meta-path achieved the best. We further conducted the Wilcoxon signed-rank test on data collected from the 500 queries. Results show that using all meta-paths is significantly better than all other strategies; the history-based strategy contributes statistically significantly more than the parameter-based and description-based strategies regarding all effectiveness metrics; and introducing the description-based strategy leads to a significant improvement in TOKTER’s effectiveness. Moreover, introducing the parameter-based strategy does not lead to a significant improvement because function parameters complement function descriptions, and the parameter-based meta-paths are expected to be combined with description-based ones to create positive effects on TOKTER’s performance. Regarding the time cost, TOKTER with the history-based strategy used significantly more time than those without, as expected.

5.6. Threats to Validity

Internal validity. TOKTER’s test-oriented knowledge graph construction heavily relies on NLP techniques, such as segmentation and dependency parsing. These tools, including HanLP we used, do not achieve 100% accuracy. However, TOKTER still remains highly effective because NLP techniques are relatively mature, and their inaccuracies are generally minimal. Outputs that are not precise still fall within the acceptable range in practice. Moreover, TOKTER is robust, as evidenced by the results for RQ3 (Section 5.4); when slightly reducing the size of the knowledge graph, there is minimal effect on the effectiveness of the recommendations.

External validity. In our experiment, we only employed one dataset of one domain, i.e., Network Cloud Engine-Transport. However, the methodology of TOKTER itself is general; it can be applied for other domains as long as three types of data are available: test function documentation, SUT documentation, and historical test cases. Though TOKTER only supports processing texts in Chinese, as the entity recognition and rule-based relation extraction in the knowledge graph construction process are language-independent, and the metrics (e.g., mutual information and branch entropy) and rules involved are language-agnostic, TOKTER can easily support other natural languages, as long as proper segmentation tools and dependency parsers are available.

Construct validity. This refers to the suitability of our evaluation metrics. We use MAP, MRR, and MR for comparing TOKTER and the baselines. These metrics are classical evaluation metrics for information retrieval [44] and are widely used for software engineering research [3,4,46,47,48,49].

6. Related Work

In the literature, SRTEF [11] is presented for recommending test functions based on the weighted description and scenario similarity. However, due to the absence of domain knowledge utilization, SRTEF fails to address the challenges of “cold start” and “semantic gap” (see Section 1), especially when dealing with insufficient historical data.

Many works have been proposed in API recommendation. For instance, Thung et al. [3] proposed to learn from issue management and version control systems and compare the literal description of a requested feature with the literal description of the API method. Rahman et al. [45] proposed recommending a ranked list of API classes for a given query in natural language based on keyword-API mappings mined from Stack Overflow questions and corresponding answers. Rahman et al. [52] further proposed NLP2API to automatically identify relevant API categories for queries in natural language, such that a query statement can be organized with the obtained API categories to improve API recommendation performance. Raghothaman et al. [12] proposed the tool SWIM to rank APIs with a statistical word alignment model based on the clickthrough data from the Bing search engine and provide code snippets to illustrate the usage of ranked APIs. Gu et al. [53] proposed DeepAPI, which adapts a Recurrent Neural Network (RNN) Encoder–Decoder model to transfer a word sequence (a user query) into a fixed-length context vector based on which a sequence of APIs will be recommended.

Works have been proposed to use knowledge graphs for API recommendation. For instance, Wang et al. [7] proposed an unsupervised API recommendation approach utilizing deep random walks on a knowledge graph constructed from Mashup-API co-invocation patterns and service category attributes. Zhao et al. [8] proposed KG2Lib, which leverages a knowledge-graph-based convolutional network and utilizes libraries called by projects to make recommendations. The knowledge graph in KG2Lib only includes properties of the third-party libraries (e.g., version, groupID). Kwapong et al. [54] presented a knowledge-graph framework built from web API and mashup data as side information for API recommendation. These entities (e.g., tags, categories) and relationships (e.g., “belongs_to”, “invokes”) in their knowledge graph are extracted from structured information and do not involve domain knowledge.

All these related works do not incorporate domain knowledge. TOKTER, however, greatly benefits from incorporating domain knowledge, allowing for more precise recommendations of test functions.

7. Conclusions and Future Work

In this paper, we introduce TOKTER, an approach designed to automatically recommend suitable test functions for natural language test steps using a test-oriented knowledge graph. This knowledge graph captures the domain knowledge of the software under test and its test harness. To recommend test functions, TOKTER has three types of meta-paths, i.e., description-based, parameter-based, and history-based meta-paths. We compared TOKTER’s performance with three state-of-the-art approaches with a real industrial dataset from Huawei. The results indicate that TOKTER significantly outperforms all baselines and has a practically acceptable recommendation time. We found that as the size of the knowledge graph increases, TOKTER’s effectiveness rapidly improves, implying that the completeness of the domain concepts in the knowledge graph has a great impact on TOKTER’s recommendation. As the size of the knowledge graph increases to about 60%, TOKTER’s effectiveness gains stabilize. We found that a few high-frequency domain concepts play a very significant role in the test function recommendation. Specifically, with about 30% of the high-frequency domain concepts, TOKTER can already achieve 83.3% of the optimal results in MAP, MRR, and MR. This observation is valuable as it aids in assessing the adequacy of domain concepts when constructing the test-oriented knowledge graph. Furthermore, we observed that TOKTER achieves optimal results with all types of meta-paths, and history-based meta-paths contribute the most to the cost-effectiveness of TOKTER. TOKTER requires manual effort from domain experts, as well as corpus data about SUT, which is the more preferable scenario. In the future, we plan to distill knowledge from LLMs to aid in constructing the knowledge graph, thus reducing the workload of domain experts.