# Code Similarity and Location-Awareness Automatic Program Repair
## 3 Our Approach
### Patch Generation
#### 3.2.2 Genetic Programming Based on Code Similarity  
In this section, we give an automatic program repair approach for genetic programming based on code similarity as follows:  
(1) Localization process: First, use the fault localization tool to obtain a list of suspicious locations. Then, the suspicious locations are screened according to the preset minimum and maximum suspicious location numbers. Finally, combine these suspicious locations into a suspicious space.  
(2) Population initialization: The initial population is created by means of code similarity, where each individual program has the same suspicious space.  
(3) Mutation process: First, a parent variant is selected from the current population by fitness value. Then, different suspicious locations and operators are selected from the suspicious space and the operation space, respectively. Next, set the ingredient space and select the fixing ingredient. Finally, create a program variant and repeat the process until you exceed the specified number of mutations. Among them, operators and repair ingredients are selected by uniform random selection. The method of weighted random selection is adopted for the selection of suspicious locations. The probability calculation for each suspicious location is shown in Formula (3):  
\[P_{w}(sl_{i})=\frac{sv_{i}}{\sum\limits_{j=1}^{n}sv_{j}} \tag{3}\]  
where \(sl_{i}\) represents the \(i\)th suspicious location. \(sv_{i}\) represents the suspicious value of the \(i\)th suspicious location. \(n\) is the total number of suspicious positions. \(P_{w}(sl_{i})\) represents the probability of selecting the suspicious location \(sl_{i}\).  
(4) Crossover process: First, a child variant and a parent variant are randomly selected. Second, select a modified suspect location in the suspect space of the variant. Then, truncate the node corresponding to the suspect location on the two variants of the abstract syntax tree and swap the subtree. Finally, repeat the above steps until the maximum number of mutations is reached. This is a non-standard version of the crossover, and the reason for this crossover is that some mutations can cause irreparable damage to the program's functionality, which provides a way to preserve the original functionality of the program. Crossover of the nodes of the abstract syntax tree can effectively prevent the generation of code that does not conform to the compilation rules.  
(5) Selection process: First, stop the fix and output the patch if a variant passes all test cases; otherwise, record the number of failed test cases. Then, the fitness values of the variants are calculated based on similarity and the number of failed test cases. Finally, repeat the procedure until all the variants have been verified and a new generation population is selected according to the fitness value. In this paper, automatic program repair is regardedas a minimization problem. A program variant with a lower fitness value has a higher probability of being selected. The fitness function is shown in Formula (4):  
\[\begin{split} Fitness(v_{i})=&\frac{|\left\{t\in T\mid(v_{i })\;Failing\;(t)\right\}|}{Sim_{v_{i}}(v_{i},v_{0})}\end{split} \tag{4}\]  
where \(\mathit{Fitness}(v_{i})\) represents the fitness function of the variant \(v_{i}\). \(v_{i}\) and \(v_{0}\) respectively represent the \(i\)th program variant and the original program. \(T\) stands for test case set, \(t\) stands for test case, and \(Failing(t)\) stands for failed test case; \(Sim_{v_{i}}(v_{i},v_{0})\) represents the similarity between the program variant \(v_{i}\) and the original program \(v_{0}\). \(Sim_{v_{i}}(v_{i},v_{0})\) is shown in Formula (5):  
\[\begin{split} Sim_{v_{i}}(v_{i},v_{0})=\frac{\sum\limits_{i=1}^{n }Sim_{s_{l_{i}}}}{n}\end{split} \tag{5}\]  
where \(s_{l_{i}}\) represents the \(i\)th suspicious location. \(Sim_{s_{l_{i}}}\) represents the similarity between the variant \(v_{i}\) and the code area where the original program \(v_{0}\) is located in the suspect location \(s_{l_{i}}\).