This is the paper given by my tutor, because I have the habit of conveniently deleting files, so I published this article to the Nuggets community for backup, the original address is: Automatic Inference of Code Transforms for Patch Generation., MY translation skills are poor at present. If there is any problem with translation, I hope to point it out in the comment section and make common progress 😊

Paper: Fan Long, Peter Amidon, and Martin Rinard. 2017. Automatic Inference of Code Transforms for Patch Generation. In Proceedings of 2017 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, Paderborn,Germany, September 4-8, 2017 (ESEC/FSE ’17), 13 pages. doi.org/10.1145/310…

Abstract

We propose a new system, Genesis, that processes manual patches to automate inference code transformation for automated patch generation. The results we present describe the effectiveness of the Genesis inference algorithm and the complete Genesis patch generation system working on patches and defects from 372 real Java projects. To our knowledge, Genesis is the first system for automatically infering patch generation transitions or searching for candidate patches from previously successful patch Spaces.

keywords

Patch generation, code conversion, search space reasoning

1. Introduction

Automated patch generation systems promise to significantly reduce the amount of manual work required to diagnose, debug, and fix software defects. The standard generation and validation approach starts with a set of test cases in which at least one test case reveals a defect. It deploys a set of transformations to generate a search space for candidate patches, and then runs the generated patches on test cases to find the appropriate patches that produce the correct output for all test cases. All previous build and validation systems use a set of manual transformations to fix bugs in the scope of these transformations.

Genesis

We introduced Genesis, a novel system for inference code transformation for automated patch generation systems. Given a set of correct manually generated patches extracted from a revisable history library, Genesis generalizes a subset of the patches and extrapolates from that transformations that can generate efficient search space candidate patches. As a result, Genesis was able to combine patches from many developers and draw lessons from them to generate a variety of efficient patch-making strategies. In a program not seen before, Genesis has been very successful in bug-fixing inferred transformation applications. Genesis is, to our knowledge, the first system to automatically infer patch generation transitions or search the candidate patch space based on previously successful patches.

Transformations: Each Genesis transformation has two template abstract syntax trees (ASTs). A template AST matches the code in the original program. Another template, AST, specifies the replacement code to generate patches. The template AST contains template variables that match the subtrees or subforests in the original or patched code. Template variables enable transformations to abstract away application-specific details to capture common patterns implemented by multiple patches extracted from different applications.

Generators: Many useful patches do not simply rearrange existing code and logic; they also introduce new code and logic. Thus, the Genesis transformation implements partial pattern matching, where the replacement template AST contains free template variables that did not matchin the original code. Each free template variable is associated with a generator that systematically generates new candidate code components for the free variable. This technique enabled Genesis to synthesize new code and logic in candidate patches, enabling it to generate the right patches for previously invisible applications, which was critical for Genesis.

Using ILP search space inference: When designing a patch search space, the key is to make an inherent trade-off between coverage and traceability. On the one hand, the search space needs to be large enough to contain the correct patches (coverage) for the target defect class; On the other hand, the search space needs to be small enough so that the patch generation system can effectively explore the space and find the right patches (traceability).

Genesis solved this problem by constructing and solving integer linear programs (ILP) whose solutions maximized the number of training patches covered by the inferred search space while limiting the number of candidate patches that the search space could generate, within bounds.

Transformational reasoning

Next, we will give an overview of the Genesis transformation reasoning algorithm through an example. Genesis uses a set of trained artificial patches to infer a set of patch-generating transformations. In our example, the training set consists of 963 manual patches, each filtered from 356 GitHub repositories.

Patch sampling and generalization: The Genesis inference algorithm is trained using a sample subset of the training set. For each subset, it applies a generalization algorithm to infer the transformations that can be used to generate candidate patches. Figure 1 shows a subset of the patches in this example: The first patch decomposes the statement mapperTypeElement== NULL into an if conditional statement. The second patch will have a clause subject! =null to form a statement that returns a value. The third patch will use the clause Material. GetMaterials (getTypeId())! =null is merged into an if conditional statement. These patches come from three different applications, mapstruct, ModelMappe, and Bukki. In Figure 1, Genesis generalizes these patches to extrapolate into P1, which, when applied, generates all three sampled patches and other patches for other applications.

Template structure: There is a template for each transformation. In our example, the template is V0 ==> ((V3) OP2 (NULL))op1(V0) (Figure 1 shows this template as a graph). The transformation has an initial template AST T0, which matches the Boolean expression V0 in the unpatched program. V0 must appear in the function body (if all training patches have modified the if condition, then T0 will reflect a more specific context). The transformation also has a replacement template, AST T1, which replaces the matching Boolean expression V0 with a patch for the form ((V3) OP2 (NULL)) OP1 (V0). Here V3, OP2, and op1 are template variables that do not match. Each such variable is associated with a generator that enumerates the candidate code components of the variable.

Generator constraints: Generator constraints control the components that the generator will enumerate. Generator constraints for op2 and OP1 (OP2 ∈ {==,! =} and op1 ∈ {, &&, | |}) only specified enumeration set of operators. The V3 generator constraint controls the AST subtree of the V3 enumeration. V3 ∈ Expr indicates that V3 is an expression, and nodes(V3) ⊆ Call∪Var indicates that V3 can only contain method calls or variable references. | V3 | 2 indicates that most V3 can contain 2 or less AST node.

Vars (V3) ⊆ M indicates that any variables that appear in V3 must also appear in the matching template AST V0 (where M represents the node set in the original matching code). | vars (V3) | 1 or less V3 only appears in a variable. Calls (V3) ⊆ M and | calls (V3) | 2 or less similar, show that constraint in V3 method calls that may occur.

As illustrated by these generator constraints, the Genesis patch generalization algorithm derives the minimum general-purpose Genesis transformation from all sampled training patches. This strategy is critical to achieving a precise target transformation that generates a manageable number of patches in the patch search space.

Candidate transitions: Genesis repeatedly samples the training patch to obtain candidate transitions (from which Genesis will select the selected transitions it used to generate the patch). In our example, the candidate transformations include the previous transformation P1 as well as a transformation (P2) that adds a conditional (ternary) operator to protect the evaluation of the expression from NP defects; A transformation (P3) adds an if-return or if-continue statement to skip calculations that trigger AN NP defect; Transformation P4 replaces a random expression with a new expression. The new expression may contain binary operators, conditional operators, and up to six variables and six method calls from the enclosing function.

But not all of these transformations are equally useful. For example, P4 is an overly generic transformation that can generate such a large patch search space that Genesis cannot search effectively. On the other hand, P1, P2, and P3 are more targeted — because they are extrapolated from conceptually similar training patches, each therefore generates a much smaller search space, but contains the correct patch. P1, P2, and P3 effectively complement each other — the search space they generate has relatively few common patches.

Search spatial reasoning: To get a set of efficient transformations, Genesis had to discard overly generic transformations such as P4 in favor of complementary, efficient target transformations such as P1, P2, and P3. Genesis uses a set of validation patches selected from training patches to drive transformation selection. Genesis first calculates the number of validation patches generated by each candidate transformation and the size of the search space generated by each candidate transformation when applied to the pre-patch code for each validation patch.

The matrix in Figure 2 gives the numbers of the four candidate transformations P1, P2, P3, and P4, as well as the three validation patches VP1, VP2, and VP3. Each number in the matrix is the number of candidate patches generated when transforming the pre-patch code applied to validate the patch. The bold green number indicates that a validation patch can be generated when the transformation is applied to the patch’s pre-patched code. These numbers highlight the trade-off between coverage and traceability provided by the candidate patches. For manageable search Spaces, P1, P2, and P3 each generate a validation patch. In contrast, P4 can generate two validation patches, but at the cost of a large unmanageable search space.

Using the information in the matrix, Genesis developed an integer linear program (ILP) that maximizes the number of validation patches that can be generated by a selected transform, but is constrained by the total number of generation candidate patches for all selected transforms. Coverage validation cases are less than 5×10^4. In our example, ILP selects P1, P2, and P3 as the selected transforms and excludes P4.

Patch generation: For NP defects in the DataflowJavaSDK revision C06125 (shown at the bottom of Figure 1), Genesis first uses a defect location technique to generate a potentially sorted list of statements to change. The resulting sorting list includes the if condition shown in the lower left corner of Figure 1. Genesis then applies all selected transformations, including P1, to the if condition to generate candidate patches.

Figure 1 shows how Genesis applies P1 to the if condition. Here, the patch will V3 instance variables into the union, op2 instantiated as = =, op3 for | |, to break down the statement unions = = null makes it become one of the most primitive if statements. When union is null, the patch causes the enclosing function innerGetOnly() to return a predefined default value (instead of mistakenly throwing a nullpointer exception). This patch validates correctly (generating the correct output for all inputs in the DataflowJavaSDK JUnit test suite) and is consistent with the manual patches developed for the defect.

3. The implementation

We used Genesis in Java programs, parsed Java programs with spoon libraries in this experiment, and currently support any Java application that uses the Maven project management system and JUnit testing framework.

Given a program P, a test set, at least one defect exposed in P, and an inferential search space P, Genesis first uses a defect location algorithm to identify a sorted list of suspected locations (such as AST fragments) in P related to defects. For each suspect AST fragment S, Genesis applied each transformation in P to generate candidate patches. It validates each candidate patch against the test cases, and if all the test cases pass, it is appended to the generated patch list. Genesis was designed to use arbitrary defect location algorithms. Our current implementation is based on suspicious locations known from stack traces of test sets that trigger Java exceptions. Genesis applies its inferred transformation to each suspect statement in the ranking defect location list. For each transformation, Genesis calculates the cost score, which is the average number of candidate patches that the transformation needs to generate to cover the validation case. For each suspect statement, Genesis prioritizes a candidate patch generated by a transformation with a lower cost score.

4. Experimental results

We use Genesis to reason about the search space for patches and generate patches for three types of defects in Java programs: null pointer (NP), out of bounds (OOB), and class cast (CC). Genesis uses a training set of 483 NP patches, 199 OOB patches, and 287 CC patches from 356 open source applications and extrapolates a search space generated by 108 transformations.

Our benchmark defects included 20 NP, 13 OOB, and 16 CC defects from 41 open source applications. All of the benchmark applications were collected from GitHub and amounted to 235K lines of code. Through 108 inferred conversions, Genesis generated correct patches for 21 of 49 defects (11 NP, 6 OOB, and 4 CC defects).

PAR was an old Java patch generation system that used hand-defined patch templates. Let’s compare it to the Genesis. For the same baseline set, the PAR template generates the correct patches for 10 defects (specifically, 7 NP and 4 OOB defects).

We attribute these results to the transformation trade-offs of navigation patches that Genesis automated inference algorithms can navigate at a certain scale. Genesis uses hundreds of candidate transformations to achieve an efficient search space generated by dozens to more than 100 selection transformations — far more than previous generation and validation systems. By deploying so many transformations, Genesis was able to capture a wide range of patch patterns and ensure traceability and coverage of the final patch search space by selecting the transformations.

5. To summarize

Previous generation and validation patch generation systems used a fixed set of transformations defined by the developer. By automatically infering transformations from successful human patches, Genesis made it possible to automatically patch vulnerabilities in new applications using the expertise and patching strategies of developers around the world.

6. Main contributions of this paper

  • Use template AST and generator for transformation: We use template AST and generator to propose new variables for free template variables. These transformations enable Genesis to abstract out patch and application-specific details to capture common patterns and strategies that exist in multiple patches drawn by different applications. Generators enable Genesis to synthesize the new code and logic needed to get the correct fixes for bugs that appear in large-scale real-world applications.

  • Patch generalization: We propose a new patch generalization algorithm that automatically generates transformations that capture common patch generation patterns in a given set of patches. This transformation can generate all given patches and other patches that have the same pattern in the same or other applications.

  • Search space reasoning: We propose a novel search space reasoning algorithm. Starting with a set of training patches, the algorithm deduces a set of transformations that together generate a search space for candidate patches with good coverage and ease of handling. The inference algorithm includes a new sampling algorithm that can identify “promising” subsets of the training patch for generalization, as well as ilP-based solutions to the final search space selection problem.

  • Complete system and experimental results: We provide a complete patch generation system, including bug location and candidate patch evaluation algorithms, which use inferential search space to automatically patch defects in large-scale real-world applications. We also present the experimental results of the complete system.

Genesis is, to our knowledge, the first system to automatically infer patch generation transitions or search the candidate patch space based on previously successful patches. All experimental data (including genesis source code, reasoning template and generate the patch) are available from http://groups.csail.mit.edu/pac/patchgen/.

7. References

[1] Fan Long and Martin C. Rinard. 2016. An analysis of the search spaces for generate and validate patch generation systems. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14 to 22, 2016. 702-713.

[2] Dataflow Java SDk. github.com/GoogleCloud… .

(2017).

[3] JUnit. junit.org/. (2017).