# An Intelligent Method for C++ Test Case Synthesis Based on a Q-Learning Agent
## 2 Materials and Methods
### Test Case Synthesis Algorithm  
The test case synthesis Algorithm 3 uses the memory of a previously trained agent in the form of a Q-table. After the training phase is completed, the Q-table contains the expected utility values for each state-action pair, accumulated over multiple episodes of interaction with the environment. The next step is to synthesize TCs in the nearly exploitation mode using the previously described policies. In this mode, the agent no longer updates the Q-values. The Q-table is used to synthesize sequences of actions. The action selection policy may be \(\epsilon\)-greedy Equation (4) or Boltzmann (Softmax, Equation (5)). The synthesis process stops once the achieved coverage exceeds that of the original test case, or when no further actions are available in the current state, or the rollback limit is exceeded. ```
**Algorithm 3** Test Case Synthesis Algorithm
```
1:Input:
2:\(\mathcal{Q}\)
3:\(TC_{o}\)
4:\(maxRollback\)
5:\(\tau>0\)
6:\(\varepsilon\in[0;1]\)
7:Output:
8:\(TC\)
9:Body:
1:\(TC\leftarrow\oslash\)
10:\(tc\leftarrow\oslash\)
11:\(k\leftarrow\text{Extract}(\mathcal{Q})\)
12:\(C_{orig}\gets GetCoverage(TC_{o})\)
13:\(\mathcal{A}\leftarrow\text{GetActionSpace}(TC_{o})\)
14:\(\mathcal{C}_{t}\leftarrow\oslash\)
15:while\(C_{t}<C_{orig}\)and not is\(\text{Over}(\mathcal{A})\)do
16: local\(rollback\gets 0\)
17: local\(s_{t}\gets Suffix_{k}(TC)\)
18: local\(a_{t}\gets 0\)
19:while\(rollback<maxRollback\)do
20:if\(\varepsilon\)! = 0 then
21:\(a_{t}\leftarrow\varepsilon Greedy(Q,s_{t},\mathcal{A},\varepsilon)\)
22:elseif\(\tau!=0\)then
23:\(a_{t}\gets [PERSON](Q,s_{t},\mathcal{A},\tau)\)
24:else
25:\(a_{t}\gets Rand(\mathcal{A})\)
26:endif
27:\(TC\gets TC\#a_{t}\)
28:if\(isValid(TC)\)then
29:\(\mathcal{A}_{episode}\leftarrow\mathcal{A}_{episode}/a_{t}\)
30:break
31:else
32:\(TC\gets TC/a_{t}\)
33:\(rollback\gets rollback+1\)
34:endif
35:endif
36:endwhile
37:if\(rollback>maxRollback\)then
38:break
39:endif
40:\(C_{t}\gets GetCoverage(TC)\)
41:if\(C_{t}>C_{orig}\)then
42:break
43:endif
44:endwhile
45:returnTC ```
**Algorithm 3** Test Case Synthesis Algorithm
```
1:Initialize local TC
2: Extract maximal call history depth from Q-Table
3:Initialize Coverage of the original TC
4: Extract action space from original TC
5:Initialize current TC coverage
6: While action space is not over
7: Initialize rollback counter
8: Initialize current state using Equation (2)
9: Initialize current action
10: While rollback counter less than threshold
11: If policy is eGreedy
12: Selection eGreedy action from action space
13: If policy is Softmax
14: Selection Softmax action from action space
15: Else
16: Selection random action from action space
17: End if
18: Append action to TC
19: Execute and check if TC runs normally
20: If TC is broken remove the action from the space
21: Exit nested while loop
22: Else
23: Rollback the action from TC
24: Increment the rollback counter
25: End if
26: End while loop
27: If maxRollback reached, then
28: Exit while loop
29: End if
30: Compute local coverage of TC
31: If local coverage is bigger than coverage of original TC
32: Exit while loop
33: End if
34: End while loop
35: Return TC ```

**Algorithm 4** Test Case Synthesis Algorithm

### Method of Intelligent Test Case Synthesis

#### 2.11.1 Conceptual Pipeline

This study presents an intelligent method for synthesizing TC for C++ libraries, which integrates a Q-learning agent and the test case synthesis Algorithm 3. The method consists of the following conceptual stages:

1. API Instrumentation. At the preparatory stage, which precedes the execution of the pipeline, static instrumentation of the target C++ library is performed as described in Section 2.11.2. 2. Function Call Tracing. During the execution of the original TCs, we log the sequences of API calls, including function signatures, objects, call contexts, and arguments. These traces are then used as the basic action space for training the agent. The tracing mechanism, as well as API instrumentation, is described in [37]. 3. Q-learning Agent Training.