FixMorph

Program Transformation, Patch Backporting, Code Transplantation

Whenever a bug or vulnerability is detected in the Linux kernel, the kernel developers will endeavour to fix it by introducing a patch into the mainline version of the Linux kernel source tree. However, many users run older “stable” versions of Linux, meaning that the patch should also be “backported” to one or more of these older kernel versions. This process is error-prone and there is usually a long delay in publishing the backported patch. Based on an empirical study, we show that around 8% of all commits submitted to Linux mainline are backported to older versions, but often more than one month elapses before the backport is available. Hence, we propose a patch backporting technique that can automatically transfer patches from the mainline version of Linux into older stable versions. Our approach first synthesizes a partial transformation rule based on a Linux mainline patch. This rule can then be generalized by analysing the alignment between the mainline and target versions. The generalized rule is then applied to the target version to produce a backported patch. We have implemented our transformation technique in a tool called FixMorph and evaluated it on 350 Linux mainline patches. FixMorph correctly backports 75.1% of them. Compared to existing techniques, FixMorph improves both the precision and recall in backporting patches. Apart from automation of software maintenance tasks, patch backporting helps in reducing the exposure to known security vulnerabilities which have not been fixed.

Publication

Automated Patch Backporting in Linux (Experience Paper)

30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2021, 12 pages

Ridwan Shariffdeen, Xiang Gao, Gregory J Duck, Shin Hwei Tan, Julia Lawall, Abhik Roychoudhury
(One-line Abstract) Patch backporting technique that can automatically transfer patches from the mainline version of Linux into older stable versions
Note: Our artifact was awarded the "Distinguished Artefact Award" at (ISSTA) 2021
Note: Our paper is now available on ACM digital library, link

Approach

Given a pair of reference/donor program versions Pa and Pb and a target/host program Pc to apply the transformation, FixMorph first extracts the syntactic edits between Pa and Pb to learn a transformation that generalizes the change in the code. Second, using evolution history (i.e. version control history) and/or clone detection FixMorph localize the correct location to apply the transformation from Pa to Pc. Next, analysing the abstract syntax trees of Pa and Pc, FixMorph generates an alignment between the two versions to adapt the learnt transformation. Based on the alignment the transformation will be customized with namespace adaptations, code evolution (i.e. importing missing dependencies). Finally, the transformation will be enforced to source-level changes using LLVM/Clang front-end infrastructure. Finally, the changes will be verified for syntactic correctness using static-analysers.

Tool

Implemented in Python and C++, this github repository contains the source for FixMorph and the scripts for the data sets, including test suites, that we used for our experiments.

Dependencies

LLVM - 10.0
Clang - 10.0
Python - 3.7

Source Files

Github Repository

Docker Image

Dockerhub Repository
Docker image only with the tool can be obtained using the tag 16.04
Docker image with scripts to reproduce the experiments can be obtained using the tag issta21

Data-Set

Classification Data-Set

To investigate the patch backporting effort required for a developer, we manually inspect the backported patches. We choose to study only the patches backported from a specific version (i.e., v3.8). We label commits based on the difficulty of backporting using the classification specified in the paper.

Evaluation Data-Set

We build our dataset in the form of patch pairs (P_mainline, P_stable), where P_mainline is the patch committed to the mainline version of Linux Kernel, and P_stable is the patch backported to an stable version. We build our dataset according to the following criteria:

Patch P_mainline was submitted to the mainline during 2011-2019 and versions below 5.0
To generate typed ASTs, the mainline version should be compilable before and after introducing P_mainline, stable version should be compilable before P_stable, and we omit the subjects for which we cannot generate complete ASTs
Our prototype only supports modification to *.c files, not header files, hence the patch should only modify *.c files. Further to reduce the complexity, we select patches affecting a single *.c file.
If P_mainline has been backported to multiple versions, we select the oldest one as P_stable which represents the most challenging task

CVE Data-Set

Using the same criteria above we randomly selected 30 patches that fix CVEs reported during 2014-2019. Note that the 30 CVE patches are disjoint from the 350 patches in our main dataset.

Classification Data-Set Evaluation Data-Set CVE Data-Set

Evaluation Results

We compare FixMorph performance with Linux Diff utilities and our own implementation of SYDIT. A gist of the results from our evaluation is given below, for full set of details please refer the paper. All experiments are conducted on a Dell Power Edge R530 withIntel(R) Xeon(R)CPU E5-2660 processor and 64GB RAM.

Patch Type	Patch Count	FixMorph			patch - No Context			patch - Context			SYDIT
Patch Type	Patch Count	Accuracy	Precision	Recall	Accuracy	Precision	Recall	Accuracy	Precision	Recall	Accuracy	Precision	Recall
Type-I	1	100%	100%	100%	100%	100%	100%	100%	100%	100%	0%	0%	0%
Type-II	235	87%	95%	91%	53%	77%	63%	77%	99%	78%	38%	46%	69%
Type-III	9	78%	100%	78%	0%	0%	0%	0%	0%	0%	22%	29%	50%
Type-IV	30	63%	86%	70%	0%	0%	0%	0%	0%	0%	20%	38%	30%
Type-V	75	43%	78%	48%	0%	0%	0%	0%	0%	0%	0%	0%	0%
Total	350	75%	92%	80%	36%	71%	42%	52%	82%	59%	28%	44%	43%

Artifacts

We provide a replication package for our experiments with FixMorph on the selected data-set in a Docker container, which consists of setup scripts/configuration files to re-run the experiments. The Docker environment consists of all dependencies for FixMorph, LLVM, and other dependencies to build the programs in our data-set.

You can access the replication package via Dockerhub at this link (use the tag issta21) by using the following command:

docker pull rshariffdeen/fixmorph:issta21

You can also download the source to build the image on your own using the source from Github, and the following command:

docker build -t rshariffdeen/fixmorph .

Patches - Linux Stable Versions

We list below the following artifacts for some of the experiment in our evaluation section of the paper; the developer patch from the mainline, the generated patch by FixMorph for the target, and the manually ported patch by developer.

Full List

You can download the full list of patches generated from our experiments using the following links

CVE Patches Main Patches

Sample List

Original Patch (Reference)
Mainline Commit: 19454462

drivers/usb/class/cdc-acm.c
430a431

+   if ((status != -ENOENT) || (urb->actual_length == 0))

Ported Patch (Manual)
Stable Commit: 291625aa

drivers/usb/class/cdc-acm.c
429a430

+   if ((urb->status != -ENOENT) || (urb->actual_length == 0))

Generated Patch (FixMorph)

drivers/usb/class/cdc-acm.c
429a430

+   int status = urb->status;
+   if ((status != -ENOENT) || (urb->actual_length == 0))

Original Patch (Reference)
Mainline Commit: 61894b02

drivers/dma-buf/sw_sync.c
222c222

-   return (fence->seqno > parent->value) ? false : true;

+   return !__dma_fence_is_later(fence->seqno, parent->value);

Ported Patch (Manual)
Stable Commit: fc839ecb

drivers/dma-buf/sw_sync.c
222c222

-   return (fence->seqno > parent->value) ? false : true;

+   return !__fence_is_later(fence->seqno, parent->value);

Generated Patch (FixMorph)

drivers/dma-buf/sw_sync.c
222c222

+ static inline bool __dma_fence_is_later(u32 f1, u32 f2) {
+ 	return (int)(f1 - f2) > 0;
+ }

-   return (fence->seqno > parent->value) ? false : true;

+   return !__dma_fence_is_later(fence->seqno, parent->value);

Original Patch (Reference)
Mainline Commit: 0b1d250a

drivers/usb/serial/io_ti.c
1676a1677,1682

+  if (port_number >= edge_serial->serial->num_ports) {
+       dev_err(dev, "bad port number %d\n", port_number); 
+       goto exit;  
+   }

Ported Patch (Manual)
Stable Commit: 23b94d65

drivers/usb/serial/io_ti.c
1683a1684,1689

+  if (port_number >= edge_serial->serial->num_ports) {
+       dev_err(&urb->dev->dev, "bad port number %d\n", port_number); 
+       goto exit;  
+   }

Generated Patch (FixMorph)

drivers/dma-buf/sw_sync.c
222c222

+  struct device *dev; 
+  dev = &edge_serial->serial->dev->dev;

+  if (port_number >= edge_serial->serial->num_ports) {
+       dev_err(dev, "bad port number %d\n", port_number); 
+       goto exit;  
+   }

FixMorph

Publication

Automated Patch Backporting in Linux (Experience Paper)

30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2021, 12 pages

Approach

Tool

Dependencies

Source Files

Docker Image

Data-Set

Classification Data-Set

Evaluation Data-Set

CVE Data-Set

Evaluation Results

Artifacts

Patches - Linux Stable Versions

Full List

Sample List

People

Principal Investigators

Developers

Contributors

FixMorph

Publication

Automated Patch Backporting in Linux (Experience Paper)

30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2021, 12 pages

Approach

Tool

Dependencies

Source Files

Docker Image

Data-Set

Classification Data-Set

Evaluation Data-Set

CVE Data-Set

Evaluation Results

Artifacts

Patches - Linux Stable Versions

Full List

Sample List

Patch #1

Patch #2

Patch #3

People

Principal Investigators

Developers

Contributors