CN117130645A - Automatic program repairing method and system based on large language model and completion engine - Google Patents

Abstract

The invention belongs to the field of program repair, and specifically relates to an automatic program repair method and system based on a large language model and a completion engine. First, the large language model is used to provide the probability of the next identifier in the generated patch code, and then the completion engine is queried. , modify the probability list by dynamically zeroing out the probability of an invalid identifier, picking from the new probability list to select the next identifier. In addition, given the completion engine's ability to provide code completion suggestions, when the completion engine only provides a candidate identifier suffix to complete the context, we use that identifier. This not only allows the method proposed in this patent to generate efficient, uncommon and long identifier patch codes, but also reduces the workload of large language models required to iteratively generate long identifier names.

Description

Automatic program repair method and system based on large language model and completion engine

Technical field

The invention belongs to the field of program repair, and specifically relates to an automatic program repair method and system based on a large language model and a completion engine.

Background technique

As software systems become more complex, so do software vulnerabilities. Traditional state-of-the-art automated program repair tools are mainly based on manual repair templates to match defective code and apply corresponding code patches. While superior to other traditional techniques, such tools can only fix bug types within preset templates and cannot generalize to new vulnerability types.

With the development of deep learning technology, researchers have built automatic program repair tools based on deep learning based on neural machine translation architecture. For example, the existing technology CN116755753A uses a trained neural machine translation model to convert defective codes into correct codes by learning defective codes and repair codes captured from code libraries submitted by open source projects. However, the training sets of these tools may be limited in size and also contain irrelevant or noisy data, reducing the accuracy of model pre-training.

Recently, with the development of large-scale language model technology, more and more studies have proven its role in helping developers complete various coding tasks. It can also be directly applied in automated program repair work to generate patch codes. However, most large-scale language models treat programs as logical entities composed of sequences of identifiers, which means that they do not understand the underlying semantic constraints of the target programming language. This results in the generation of a large amount of invalid patch code, thereby reducing the usefulness of the technique.

Contents of the invention

In order to solve the above problems, this patent proposes an automated program repair method based on a large language model and a programming language automatic completion engine. It generates more effective patch code by integrating the large language model with the completion engine, and uses artificial intelligence technology to enhance automation. Accuracy and availability of program fixes. The completion engine can parse incomplete program code and reason about code semantics in a highly fault-tolerant manner. The autoregressive identifier generation process for large language models can be likened to the work of a human developer writing code, where a completion engine can provide real-time updates to check whether parts of the code written by humans/large language models are valid. Its technical solution is,

An automatic program repair method based on large language models and completion engines, including the following steps:

S1. Use a large language model to generate the identifier library T (t ₁ , t ₂ ,...t _n ) of the patch code and the corresponding probability P (p ₁ , p ₂ ,...p _n );

S2. Sample the identifiers in the identifier library T in the set order, obtain the identifier _ti (1≤i≤n), and check whether the record corresponding to the identifier is stored in the memory: if the sampled identifier If the symbol t _i has a record hit in the memory, there is no need to call the completion engine 1. It can be retained or directly pruned according to the situation; if the sampled identifier t _i is not hit in the memory, the completion engine 1 is called. Engine 1 generates a completion result based on the sampled identifier _ti , the current program code context and the current caret position. If the result is not unknown and the completion result is empty, it is determined that the current sampled identifier _ti is rejected. By setting the probability p _i (1≤i≤n) corresponding to the sampled identifier _ti to zero, the pruning operation is completed and the memory record is updated. Otherwise, the current sampled identifier _ti is determined to be adopted, and the memory record is updated. , continue to sample the identifiers in the identifier library T, and repeat step S2 until all identifiers in the identifier library T are sampled;

S3. The completion engine 2 automatically completes the identifier string for the updated identifier library T to provide a series of candidate completion identifiers as a continuation of the adopted identifier string candidate, using the updated The identifier library repeats steps S1-S3 until all identifier strings are completed to form a complete patch code.

Preferably, a large language model is used to provide the identifier library T (t ₁ , t ₂ ,...t _n ) and the corresponding probability library P (p ₁ , p ₂ ,...p _n ) for generating patch codes, and the identifier library T And the corresponding probability library P is mapped to the search space, and sampling is performed from high to low according to the probability.

Preferably, the pruning operation is: the pruning module sets the probability p _i (1≤i≤n) corresponding to the identifier _ti (1≤i≤n) in the search space to zero; when the probability of a certain identifier is When zero, no sampling is performed.

Preferably, the process of sampling and judging each identifier library T in step S2 does not involve the large language model generating a new identifier library again, that is, step S2 only judges the current output result of the large language model.

Preferred, patch code production method:

First, use the <SPAN> identifier as a shielding code to replace the vulnerable code block to form a prototype patch;

A large language model is then used to synthesize a fix code block from the context of the code surrounding the vulnerability location to replace the <SPAN> identifier.

Preferably, in step S2, the memory stores identifiers that are known to be infeasible or/and feasible. The identifier is hit in the following three situations:

If a rejected record in the memory is hit, it is determined that the current identifier is unavailable, and the pruning module directly prunes the search space;

If the prefix tree Trie of the rejected identifier in the memory is hit, check whether any identifier in the hit record is the prefix of the newly generated _ti (1≤i≤n). If so, the pruning module directly prunes the search space. branch operation and resample from the identifier library T;

If a hit is made to a feasible record stored in memory, the adopted identifier needs to be retained.

Preferably, in step S2, the process of pruning the search space is:

First, the candidate next identifier is sampled according to the mapping between the identifier library T given by the large language model and the corresponding probability P, the current program code body is updated accordingly, and the caret is moved to the newly sampled identifier. After t _i (1≤i≤n);

Then, based on the currently generated identifier string result, the completion engine 1 is called to check the current string result; if the result is not unknown and the completion is not completed, it means that the currently produced identifier cannot form a further candidate continuation. , therefore, through the pruning module, the probability p _i (1≤i≤n) corresponding to the identifier _ti (1≤i≤n) in the search space is set to zero to perform the pruning operation, and the identifier library is re-used. T is sampled and the next loop is executed; otherwise, the current identifier is considered feasible.

Preferably, in step S2, the memory constructs a prefix tree of rejected identifiers. The specific steps are: if an identifier is rejected, it means that a candidate continuation cannot be formed after the identifier to obtain a statically valid patch code. , then any identifier with such a prefix should be rejected, build and continuously update a prefix tree of all rejected identifiers given the program code body and caret position, and check whether any identifier in it is newly generated The prefix of the next identifier; if so, resample from T.

Preferably, in step S3, the active completion operation steps are:

Gets the completion result based on the given program code body and the current caret position, and checks whether the current identifier string is unknown; if so, the result will be set to an empty string, which means no additional completions will be generated. Complete; otherwise, calculate the common prefix of all completion results, adjust the completion results to adapt to the vocabulary requirements of the language model, and return the results.

An automatic program repair system based on a large language model and a completion engine, including a large language model, a pruning module, a completion engine one and a completion engine two;

The large language model is used to provide the identifier library T (t ₁ , t ₂ ,...t _n ) and the corresponding probability P (p ₁ , p ₂ ,...p _n ) that generate the patch code, and combine the identifier library T and the corresponding The probability P is mapped to the search space;

The pruning module is used to check whether the sampled identifier _ti (1≤i≤n) in the identifier library T hits the content in the memory, and prunes the search space according to the situation;

When the identifier _ti does not hit the memory, the completion engine obtains the memory query result and performs a completion operation on the identifier string. If the completion result is not unknown and the completion result is empty, the pruning module is triggered. Perform search space pruning, otherwise identifier _ti is adopted;

The completion engine 2 actively completes the identifier string to provide a series of candidate completion identifiers as a continuation of the currently hit identifier string candidate, and generates a completion result.

Compared with the existing technology, this application has the following beneficial effects:

1) The method proposed in this patent is aimed at repairing a single vulnerability. The patch is carried out on the premise that accurate location of the fault code has been provided, and the patch code is obtained by changing the consecutive codes pointed out by the location. Furthermore, the method proposed in this patent can be extended to patch multiple vulnerable codes by using a separate padding identifier to replace the code at the faulty code location, and using a large language model to generate replacement code. The method proposed in this patent can be directly applied to general-purpose programming languages while introducing minimal overhead, and can use the completion engine to proactively complete the generation of current patch code identifiers without the need to call large language models multiple times.

2) The method proposed in this patent first uses a large language model to provide the probability of the next identifier in the generated patch code, and then queries the completion engine to modify the probability list by dynamically returning the probability of invalid tokens to zero, starting from the new probability Select the next identifier in the list. In addition, given the completion engine's ability to provide code completion suggestions, when the completion engine only provides a candidate identifier suffix to complete the context, we use that identifier. This not only allows the method proposed in this patent to generate efficient, uncommon and long identifier patch codes, but also reduces the workload of large language models required to iteratively generate long identifier names.

Description of the drawings

Figure 1 is a flow chart of this application.

Figure 2 is a diagram of an embodiment of the present application.

Detailed ways

The following detailed description is illustrative and is intended to provide further explanation of the present application. Unless otherwise defined, all technical and scientific terms used herein have the same meanings commonly understood by one of ordinary skill in the art to which this application belongs. It should be noted that the terms used herein are only for describing specific embodiments and are not intended to limit the exemplary embodiments according to the present application.

An automatic program repair method based on large language models and completion engines, including the following steps:

S1. Use a large language model to provide the identifier library T (t ₁ , t ₂ ,...t _n ) and the corresponding probability library P (p ₁ , p ₂ ,...p _n ) for generating patch codes, and combine the identifier library T and The corresponding probability library P is mapped to the search space, and sampling is performed from high to low according to the probability.

S2. Sample the identifiers in the identifier library T in the set order, obtain the identifier _ti (1≤i≤n), and check whether the record corresponding to the identifier is stored in the memory: if the sampled identifier If the symbol t _i has a record hit in the memory, there is no need to call the completion engine 1, and the pruning operation is performed directly; if the sampled identifier t _i is not hit in the memory, the completion engine 1 is called, and the pruning operation is performed directly according to the sample. The identifier _ti , the current program code context and the current caret position are used to generate a completion result. If the result is not unknown and the completion result is empty, it is determined that the currently sampled identifier _ti is rejected, and the sampled identifier is The probability p _i (1≤i≤n) corresponding to symbol _ti is set to zero, the pruning operation is completed and the memory record is updated, otherwise it is determined that the currently sampled identifier _ti is adopted, and the memory record is updated, and the identifier is continued. The identifiers in the identifier library T are sampled, and step S2 is repeated until all identifiers in the identifier library T are sampled. Step S2 can be regarded as an identifier sampling inner loop process.

If the result is not unknown and the completion result is empty, the completion engine's logic for judging the condition is equivalent to:

(1) Assume that the sampled _ti is available, put it behind the generated code string to form the identifier string S`.

(2) Hand S` to completion engine 1 to determine whether S` is legal. If S` is legal, then either t <sub>i</sub> is the last word (the completion result is unknown), or possible continuations can be generated based on S` (the completion result is not empty); otherwise, if the completion engine Once the generated result is not unknown and the completion result is empty, it means that S` is illegal, that is, it is inappropriate to put _ti after the generated identifier string, that is, _ti is rejected.

(3) Determine whether _ti is rejected or accepted based on the result in (2).

The pruning operation is: the pruning module sets the probability p _i (1≤i≤n) corresponding to the identifier _ti (1≤i≤n) in the search space to zero; when the probability of a certain identifier is zero, It is not sampled.

The process of sampling and judging each identifier library T in step S2 does not involve the large language model regenerating a new identifier library, that is, step S2 only judges the current output result of the large language model.

When the memory stores known feasible identifiers, if the sampled identifier _ti (1≤i≤n) has a record hit in the memory, there is no need to call the completion engine 1 and the pruning operation is performed directly.

The memory stores the prefix tree of known-rejected identifiers, known-adopted identifiers, and known-rejected identifiers. The identifier record is hit in the following three situations:

(1) If a rejected record in the memory is hit, it is determined that the current identifier t _i (1≤i≤n) is not available. The pruning module directly performs pruning operation on the search space and continues to extract the identifier from the identifier library T. sampling.

(2) If the adopted record in the memory is hit, it is determined that the current identifier _ti (1≤i≤n) is available, the probability of the current identifier is maintained, and sampling from the identifier library T is continued.

(3) If the prefix tree Trie of the rejected identifier in the memory is hit, check whether any identifier in the hit record is the prefix of the newly generated identifier string. If so, the pruning module directly prunes the search space. , and resample from the identifier library T;

The memory constructs a prefix tree of rejected identifiers. The specific steps are: if an identifier is rejected, which means that no candidate continuation can be formed after the identifier to obtain a statically valid patch code, then any prefix with such a of identifiers should all be rejected, construct and continuously update a prefix tree of all rejected identifiers for a given program code body and caret position, and check whether any identifier in it is a prefix of the newly generated next identifier ; If so, resample from T.

If the identifier of the current sample is not stored in the memory, the completion engine 1 is called to generate the completion result based on the sample identifier _ti (1≤i≤n), the current program code context and the current caret position. If the result is not unknown and the completion result is empty, it is determined that the currently sampled identifier t _i is rejected, and pruning is completed by setting the probability p _i (1≤i≤n) corresponding to the sampled identifier t _i to zero. Operate and update the memory record, otherwise it is determined that the identifier _ti of the current sample is adopted, and the memory record is updated.

S3. The completion engine 2 actively completes the identifier string to provide a series of possible completion identifiers as a continuation of the currently hit identifier string candidate, and repeats step S1- using the updated identifier library. S3 until all identifier strings are completed to form a complete patch code.

Patch code production method:

First, use the <SPAN> identifier as a shielding code to replace the vulnerable code block to form a prototype patch;

A large language model is then used to synthesize a fix code block from the context of the code surrounding the vulnerability location to replace the <SPAN> identifier.

In step S3, obtain the completion result based on the given program code body and the current caret position, and check whether the current identifier string is unknown; if so, the result will be set to an empty string, which means there will be no Generate additional completions; otherwise, compute the common prefix of all completion results, adjust the completion results to fit the language model's vocabulary requirements, and return the results.

The entire steps S1-S3 can be regarded as a large outer loop.

An automatic program repair system based on a large language model and a completion engine, including a large language model, a pruning module, a completion engine one and a completion engine two;

The large language model is used to provide the identifier library T (t ₁ , t ₂ ,...t _n ) and the corresponding probability P (p ₁ , p ₂ ,...p _n ) that generate the patch code, and the identifier library T and the corresponding The probability P is mapped to the search space;

The pruning module is used to check whether the sampled identifier _ti (1≤i≤n) in the identifier library T hits the content in the memory, and prunes the search space according to the situation;

When the identifier _ti does not hit the memory, the completion engine obtains the memory query result and performs a completion operation on the identifier string. If the completion result is not unknown and the completion result is empty, the pruning module is triggered. Search space pruning is performed, otherwise identifier _ti is adopted.

The completion engine 2 actively completes the identifier string to provide a series of candidate completion identifiers as a continuation of the currently hit identifier string candidate, and generates a completion result.

The embodiment, as shown in Figure 2, shows the process of patch code generation proposed in this patent.

The generation process consists of two inner and outer loops forming a large loop. The large loop continuously uses the collaboration between the large language model and the completion engine to generate new identifiers to update the generated results.

First, the outer loop applies the currently generated identifier as the input of the large language model (① in Figure 2). The large language model returns the given currently sampled identifier library T (String, Name, End,...) and the corresponding The probability library P (91%, 3%, 0.2%,...) maps the identifier library T and the corresponding probability library P to the search space of the inner loop, and the sampling is performed from high to low according to the probability. Then, enter the identifier sampling phase of the inner loop, repeat the identifier sampling process from the search space, check its feasibility, and prune the search space until the identifier is adopted.

Each time the identifier library T is sampled to obtain _ti (1≤i≤n), first check whether the identifier _ti hits the content in the memory (② in Figure 2). The memory stores known feasible or infeasible identifier record. The memory record of infeasible identifiers includes our custom prefix tree data structure (Trie), which will be introduced in the following content.

When the sampled identifier _ti hits an infeasible record in the memory, the search space is pruned by setting the probability p _i (1≤i≤n ₎ of this identifier ti to zero (③ in Figure 2), And the next sampling operation will be performed on the updated search space. In this way, the same identifier will not be sampled again during the identifier selection phase, avoiding useless operations. If the sampled identifier _ti does not hit the storage content in the memory (that is, the identifier Name is not stored in the memory), the completion engine 1 is called. According to the sampled identifier _ti , the current program code context and the current caret position, generate the completion result. If the result is not unknown and the completion result is empty, it is determined that the currently sampled identifier t _i is rejected, and the probability p _i corresponding to the sampled identifier t _i is determined (1≤i≤n ) is set to zero, complete the pruning operation and update the memory record, otherwise it is determined that the identifier _ti of the current sample is adopted, and the memory record is updated. In both cases, the memory is updated (⑤ in Figure 2). After accepting the identifier t _i (⑥ in Figure 2), we further use the completion engine 2 to try to actively complete the identifier string (⑦ in Figure 2).

When the inner loop is in progress, the large language model is not involved in generating a new identifier library again, that is, the inner loop only judges the current output result of the large language model.

Finally, the method proposed by this patent appends all newly generated accepted identifiers to the current generation and starts a new cycle until a complete patch code is generated. The loop stops when the model generates a special flag indicating the end.

In order to alleviate the efficiency drop caused by the sampling test and pruning operation loop during the inner loop process and speed up the search process, the method proposed in this patent applies memory technology to reduce the frequency of calling the completion engine for analysis.

Memory mainly fulfills the following three functions:

(1) Remember rejected identifiers:

Fixing vulnerabilities in practice requires generating a large number of samples, which means that the same program code body and current caret position may appear repeatedly in the pruning operation. Therefore, we can be pruned by judging during the sampling process. The dropped identifiers are stored in the memory and the probability of rejected identifiers is set to zero, thereby speeding up the pruning process.

(2) Remember the adopted identifier:

In addition to rejected identifiers, we can also store previously accepted identifiers in memory, thereby avoiding a call to the completion engine and directly determining that the identifier is available.

(3) Construct a prefix tree of rejected identifiers:

It is common in language models that many identifiers in a language model vocabulary may be a prefix of another identifier. Obviously, if an identifier is rejected, meaning that no possible continuation can be formed after that identifier to obtain a statically valid patch code, then any identifier with such a prefix should be rejected. Therefore, we build and continuously update a prefix tree (denoted as a Trie) of all rejected identifiers for a given program code body and caret position, and check whether any identifier in it is a prefix of the newly generated next identifier . If so, jump directly to the next iteration and avoid further analysis.

The above descriptions are only preferred embodiments of the present application and are not intended to limit the present application. For those skilled in the art, the present application may have various modifications and changes. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of this application shall be included in the protection scope of this application.

Claims (10)

1. An automatic program repair method based on a large language model and completion engine, which is characterized by including the following steps: S1. Use a large language model to generate the identifier library T (t ₁ , t ₂ ,...t _n ) of the patch code and the corresponding probability P (p ₁ , p ₂ ,...p _n ); S2. Sample the identifiers in the identifier library T in the set order, obtain the identifier _ti (1≤i≤n), and check whether the record corresponding to the identifier is stored in the memory: if the sampled identifier If the symbol t _i has a record hit in the memory, there is no need to call the completion engine 1. It can be retained or directly pruned according to the situation; if the sampled identifier t _i is not hit in the memory, the completion engine 1 is called. Engine 1 generates a completion result based on the sampled identifier _ti , the current program code context and the current caret position. If the result is not unknown and the completion result is empty, it is determined that the current sampled identifier _ti is rejected. By setting the probability p _i (1≤i≤n) corresponding to the sampled identifier _ti to zero, the pruning operation is completed and the memory record is updated. Otherwise, the current sampled identifier _ti is determined to be adopted, and the memory record is updated. , continue to sample the identifiers in the identifier library T, and repeat step S2 until all identifiers in the identifier library T are sampled; S3. The completion engine 2 automatically completes the identifier string for the updated identifier library T to provide a series of candidate completion identifiers as a continuation of the adopted identifier string candidate, using the updated The identifier library repeats steps S1-S3 until all identifier strings are completed to form a complete patch code. 2. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that the identifier library T and the corresponding probability library P are mapped to the search space, and the sampling is carried out according to the probability Size proceeds from high to low. 3. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that the pruning operation is: the pruning module removes the identifier _ti (1≤i ≤n) the corresponding probability p _i (1≤i≤n) is set to zero; when the probability of a certain identifier is zero, it is not sampled. 4. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that, in the process of sampling and judging each identifier library T in step S2, the large language model is not involved again. Generate a new identifier library, that is, step S2 only judges the current output result of the large language model. 5. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that the patch code production method: First, use the <SPAN> identifier as a shielding code to replace the vulnerable code block to form a prototype patch; A large language model is then used to synthesize a fix code block from the context of the code surrounding the vulnerability location to replace the <SPAN> identifier. 6. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that in step S2, the memory stores identifiers that are known to be infeasible or/and feasible. Being hit is divided into the following three situations: If a rejected record in the memory is hit, it is determined that the current identifier is unavailable, and the pruning module directly prunes the search space; If the prefix tree Trie of the rejected identifier in the memory is hit, check whether any identifier in the hit record is the prefix of the newly generated _ti (1≤i≤n). If so, the pruning module directly prunes the search space. branch operation and resample from the identifier library T; If a hit is made to a feasible record stored in memory, the adopted identifier needs to be retained. 7. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that in step S2, the process of pruning the search space is: First, the candidate next identifier is sampled according to the mapping between the identifier library T given by the large language model and the corresponding probability P, the current program code body is updated accordingly, and the caret is moved to the newly sampled identifier. After t _i (1≤i≤n); Then, based on the currently generated identifier string result, the completion engine 1 is called to check the current string result; if the result is not unknown and the completion is not completed, it means that the currently produced identifier cannot form a further candidate continuation. , therefore, through the pruning module, the probability p _i (1≤i≤n) corresponding to the identifier _ti (1≤i≤n) in the search space is set to zero to perform the pruning operation, and the identifier library is re-used. T is sampled and the next loop is executed; otherwise, the current identifier is considered feasible. 8. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that, in step S2, the memory constructs a prefix tree of rejected identifiers, and the specific steps are: If an identifier is rejected, it means that no candidate continuation can be formed after the identifier to obtain statically valid patch code, then any identifier with such a prefix should be rejected, building and continuously updating the given program code body. and a prefix tree of all rejected identifiers at the caret position, and checks whether any identifier in it is a prefix of the newly generated next identifier; if so, resamples from T. 9. An automatic program repair method based on a large language model and a completion engine according to claim 1, characterized in that in step S3, the active completion operation steps are: Gets the completion result based on the given program code body and the current caret position, and checks whether the current identifier string is unknown; if so, the result will be set to an empty string, which means no additional completions will be generated. Complete; otherwise, calculate the common prefix of all completion results, adjust the completion results to adapt to the vocabulary requirements of the language model, and return the results. 10. An automatic program repair system based on a large language model and a completion engine, characterized by including a large language model, a pruning module, a completion engine one and a completion engine two; The large language model is used to provide the identifier library T (t ₁ , t ₂ ,...t _n ) and the corresponding probability P (p ₁ , p ₂ ,...p _n ) that generate the patch code, and combine the identifier library T and the corresponding The probability P is mapped to the search space; The pruning module is used to check whether the sampled identifier _ti (1≤i≤n) in the identifier library T hits the content in the memory, and prunes the search space according to the situation; When the identifier _ti does not hit the memory, the completion engine obtains the memory query result and performs a completion operation on the identifier string. If the completion result is not unknown and the completion result is empty, the pruning module is triggered. Perform search space pruning, otherwise identifier _ti is adopted; The completion engine 2 actively completes the identifier string to provide a series of candidate completion identifiers as a continuation of the currently hit identifier string candidate, and generates a completion result.