Automatic Patch Generation with Context-based Change Application

Automatic Patch Generation with Context-based Change Application

Paper

Jindae Kim, Sunghun Kim

Goal:

1. I am collecting changes from human-written patches for new patch candidate generation.
2. Automatic patch generation technique leveraging human-written patches with our context-based change application technique used by ConFix.

Summary:

• An effective patch generation technique should have a large search space with a high probability that patches for bugs are included, and it also needs to locate such patches effectively. Confix collects abstract AST changes from human-written patches, providing resources for patch generation. Then, using only matching context only, Confix selects a necessary change for a possible fixed location. Also, Confix filters out undesirable locations to fix using the info that the location has not been changed in human-written patches.

Points:

1. The problem with APR is search space size and navigation.
   1. To solve the problem, mining changes from human-written patches has been trying, but it makes navigation for the patch more difficult since the changes are very sparse.
   2. Confix, use context-based change application technique to generate patch candidates.
      1. AST context applies collected change to a possible fixed location only if their AST contents are matched
      2. ConFix compares AST contexts defined by parent, left, and right nodes of a change and a location and applies the change to a target location only if their contexts are matched.
2. Change Collection
   1. Collecting changes generally applicable to other location
   2. We extract AST form since source code can be easily affected by specific user styles.
   3. Following some steps, dependent on how changes are collected
3. Change Extraction
   1. Each hunk is extracted and converted to an individual AST subtree change.
   2. Collect separate individual changes rather than the whole patch to use repetitiveness of changes.
   3. To extract changes, use the differencing tool, generates AST subtree edit operation, combine node edit operation into trees
      1. AST node type and node value indicate a specific identifier, literals, or operators; the edit operation preserves the AST structure of the inserted code fragment
4. Change conversion
   1. Extracted edit operations need to be independent and applicable form.
      1. The type needs to be changed as a single change
         1. divide operation more
         2. extends operation
         3. remove any operation if a changed AST is a subtree of another operation’s changed AST
         4. Find all inserted-delete pairs applied to the same location and combine them.
   2. Need to normalize the user-defined identifiers.
      1. By normalizing user-defined names, we can increase the reusability of collected changes since we can apply a change regardless of the availability of user-defined names.
      2. The technique normalizes user-defined names with two principles: consistency and order-preserving
      3. By normalizing user-defined names, we can increase the reusability of collected changes since we can apply a change regardless of the availability of user-defined names.
      4. At the time of change concretization, the collected information works as requirements for each abstract name which ConFix should consider when it assigns a concrete name for the abstract name.
   3. Change Context Identification
      1. After individual changes are obtained from source code patches, the next step is identifying the AST contexts of the changes.
      2. By identifying the context of the target location, we can avoid meaningless modifications and more frequent changes.
      3. To define AST context, use nearby nodes of a changed AST subtree
         1. The parent node represents the location where a changed code fragment belongs.
         2. The left and Right nodes indicate code fragments before and after the changed code fragment.
         3. Using fingerprinting technique
         4. Dyck Word Hash
            1. represents the parent-child relationship of nodes
            2. Compare two nodes’ hash values to check whether they are the roots of two type-isomorphic AST subtrees.
            3. For fast comparison
      4. PLRTH and PLRT
         1. left node indicates code before the changed code frame; the right node indicates code after the changed code fragment
         2. PTLRH context, we also examine whether the change and the location have the same code fragment before and after them, while PLRT context only checks which kind of code fragments exist before and after the change and the location.
         3. PTLRH context constrains the search area too much; we can expand the search area with PLRT context.
         4. Exception
         5. Block node does not mean too much; use its parent node as a type.
         6. Move operations primarily consider the old location’s context, but store the new location’s context to use it as an additional constraint of move changes.
5. Change Application
   1. Target Location Context Identification
      1. The target location is also an AST node to which a change will be applied
      2. To identify the location context is compatible with change contexts, using PLR nodes we can identify location contexts for changes
         1. Except for insert, another operation has an old AST subtree so it is applicable
         2. The inserted context is identified from New AST which is inserted. We need a different type, based on the assumption that a subtree is inserted near a location. Insert Before and Insert After contexts are the contexts for cases in which a new AST subtree is inserted before and after node N. Node C indicates the actual location where a subtree will be inserted
6. Change Selection
   1. retrieve changes with the same context from a changing pool
   2. Categorized by their context, only store unique changes with their frequency
   3. choose one of the selections and mimic human-written changes by selecting any of the changes on the list
      1. The random selection, strategy is not decided specifically
7. Change Concretiziation
   1. Replacing all normalized identifiers with concrete name
      1. Do not fully specify the strategy yet how ConFix concretizes a change since various strategies can be used
      2. Since the type of normalized variables and signature of normalized methods are also stored during change collection, we can consider a strategy that assigns an existing variable name to a normalized variable (if the type is compatible)
      3. Since change is concretized, apply it to the target location
8. Patch generation
   1. Generate-and-validate process
   2. Starts with the PTLRH pool to narrow down the search area for patch generation, switch to PLRT if the patch generation failed at the above level
   3. Identify target location, retrieves changes having the same context as the selected location, apply it to the target location
   4. Lastly, tries different name assignments by predefined max trials
      1. To prevent spoiled validation due to wrong name assignment
   5. Pass -> termination; Fail -> continues with another change
   6. When it reaches the max candidate, moves to the next change pool
9. Target Location Identification
   1. Confix leverages both fault localization and change context to identify target locations from given buggy code
      1. Identifies all AST nodes which belong to the statement as potential target locations
      2. filters out all target locations having context not included in the current change pool
      3. Identify fail and pass a group
         1. The first pick from the fail-only group, if there is no location, starts from the pass-fail group
         2. Failing test cases have a much higher priority
      4. Prior target location has if, method invocation, infix expression, or return statement since it influences the whole execution
10. Change Selection
    1. ConFix selects one of the retrieved changes for the current target location and chooses the most frequent change
    2. Even if it is in the same context, change might not be applicable
       1. In case of replacement operation, one more location should be selected
       2. Therefore, ConFix randomly selects one of the target locations with a matching context
          1. If there is not, discard the change
    3. Code might not be compilable, so ConFix goes through the verification steps
       1. Examine all change-location pairs since a change that was applicable in another location might not be applicable in other locations
       2. Considering all pairs and compiling is beneficial rather than since it is not expensive to recompile source code with a small modification
11. Change Concretization
    1. Concretizing selected change for the target location
    2. ConFix collects concrete names of variables, types, and methods from the given buggy code and decides which names are within the scope
    3. To find a concrete method for a normalized method, ConFix identifies compatible methods from collected methods available at a target location
    4. Abstract signature
       1. method signature with normalized types
       2. The purpose of this is to find a concrete method with the same abstract signature, then it will not cause a compile error
    5. Assignable type
       1. Consider both type compatibility and the number of variables of the types
          1. Normalized types are considered wildcard characters, which means that they can be assignable to either normalized types or JSL types.
          2. ConFix only considers a type as assignable to another type if there exist enough variables for assignment.
       2. the compatibility of a normalized and a concrete method is defined by their abstract signatures and assignable types
          1. The concrete method first considers local methods, then global methods with the assumption that local methods are more closely related to buggy code
          2. Once a concrete method for a normalized method is selected and assigned, ConFix update types are matched due to method assignment
          3. Randomly assigns one of the assignable concrete types for each normalized type
          4. Assigns concrete variables to normalized variables
       3. There is one additional treatment for update type changes which updates an identifier with another identifier
          1. Assume the update change is meaningful when the new name is similar to the old one, so calculate the Levenshtein distance between the identifier and concrete name
       4. In case of no type-compatible assignment
          1. Change concretization is considered failed and no patch candidate is generated
12. Evaluation
    1. Collected changes with PTLRH and PTLR contexts from Apache Commons Collections (collections), Derby (derby), Hadoop (hadoop), Ivy (ivy) and Lucene (lucene) projects.
       1. we selected a completely different set of projects for change resources from the projects in Defects4j dataset.
       2. For each context, there are averages 1.91 and 16.25 changes in PTLRH and PLRT change pools respectively
    2. We built change pools and obtained coverage information of all buggy codes before we applied ConFix to each bug.
       1. Change pool and coverage information is given to ConFix
13. Results
    1. Compilation of one Java file is much cheaper than test execution even if only a few failing test is executed. Therefore ConFix can find a patch within a reasonable time.
    2. Acceptable and Plausible
    3. We did not set a time budget, however, ConFix generated all the patches within two hours
    4. ConFix generated 71 patches
       1. which are greater than other techniques - ssFix(60), Nopol(33), jGenProg(19), jKali(18), HDRepair(16) and ACS(7)
       2. generated 13 acceptable patches, which is significantly higher than valid patches generated by HDRepair(5), ACS(3), jGenProg(3), jKali(1), and Nopol(0). One exception is ssFix, which generated 20 valid patches, higher than ConFix.
    5. ssFix
       1. We verified ssFix-generated patches again and found that two valid patches (C1, M79) are not acceptable patches.
    6. ConFix was able to find necessary changes and the right fix locations with its patch generation strategy
    7. Informative Patches
       1. Although plausible patches are not acceptable when it is compared to human-written patches, they might be given as debugging hints for developers.
       2. we manually analyzed 58 plausible patches and checked whether these patches are informative.
14. Are PLRTH and PLRT really helpful?
    1. With PTLRH contexts, ConFix explores a much narrower area in its candidate space
       1. Consequently, it might also lose the chance that actual patches are included in the area
    2. Among 71 generated patches, 81% of the patches (58/71) are generated by changes from PTLRH change pools. In terms of acceptable patches, using PLRT context only gives two more acceptable patches, and PTLRH change pool still works for 85% of the acceptable patches (11/13).
    3. ConFix generated two acceptable patches which take 15% of all acceptable patches under both types of context. These PLRT acceptable patches are all semantically equivalent to human-written patches, which means that they addressed issues in the same way as humans did. Therefore PLRT context can also provide practical constraints to mimic the developer’s changes and produce acceptable patches.
15. Threats to validity
    1. Our evaluation results might be different if we used other collected changes from different human-written patches.
    2. There exists another issue that bugs from five projects might not be representative
    3. Manual assessment of patches could be another issue, since we do not have domain knowledge and the judgment about patches might be subjective and biased.
16. Related Works
    1. The difference is that ConFix uses AST contexts to select one of the changes, while ssFix considers the syntactic relation of code fragments to given buggy code.
    2. Identifying AST contexts is less costly than deriving SMT constraints, but these contexts still provide syntactic information which also implies some of the program semantics, although it does not fully represent the program’s semantics like SMT constraints.
    3. ConFix differs from these previous techniques due to the point that it can automatically collect abstract individual changes on a large scale and it uses them to generate patch candidates, instead of generating patch candidates with several pre-defined modifications or mutation operations with limited resources of code fragments
17. Studies on Human-written patches
    1. changes in bug fixes are repetitive, and smaller changes are even more repetitive
    2. There exist other studies on changes and source code’s uniqueness which imply the potential of techniques leveraging 17 existing code fragments or changes
    3. Empirical evaluation of ConFix and fixability analysis results imply that we can obtain necessary changes for new bug fixes from existing patches.
18. Change Collection and Application
    1. we may consider using these code transfer techniques to develop new methods for patch candidate generation in ConFix
    2. it is possible to apply high-level ideas such as collecting abstract changes with their AST contexts regardless of adjustment
19. Conclusion
    1. We may try to generate patches with multiple changes to improve partial patches up to acceptable patches or use more sophisticated concretization methods to effectively generate high-quality patches.

Knowledge:

• Context-based Change Application Technique: a technique to generate candidate patches
• ConFix can expand its search space by collecting more changes, while it can navigate through them effectively with the guidance of context

Terminology:

• Hunk: Single changes including deletion and addition, may have multiple in a single commit

Questions:

• Why PLRTH and PLRT: The paper mentioned it is for reducing the search space. Is it the most efficient way to do it?
• I don’t understand the part about fault localization. Is it possible to localize the fault using AST context? Does it just localize fault according to the collected change?
• What if AST differencing tools work maliciously?