| CARVIEW |
FixMorph
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
Dependencies
- LLVM - 10.0
- Clang - 10.0
- Python - 3.7
Source Files
Docker Image
Dockerhub RepositoryDocker 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 (Pmainline, Pstable), where Pmainline is the patch committed to the mainline version of Linux Kernel, and Pstable is the patch backported to an stable version. We build our dataset according to the following criteria:- Patch Pmainline 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 Pmainline, stable version should be compilable before Pstable, 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 Pmainline has been backported to multiple versions, we select the oldest one as Pstable 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 | 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:issta21docker 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 linksCVE Patches Main Patches
Sample List
|
Original Patch (Reference) Mainline Commit: 19454462 |
drivers/usb/class/cdc-acm.c |
|
|
Ported Patch (Manual) Stable Commit: 291625aa |
drivers/usb/class/cdc-acm.c |
|
| Generated Patch (FixMorph) |
drivers/usb/class/cdc-acm.c |
|
Original Patch (Reference) Mainline Commit: 61894b02 |
drivers/dma-buf/sw_sync.c |
|
|
Ported Patch (Manual) Stable Commit: fc839ecb |
drivers/dma-buf/sw_sync.c |
|
| Generated Patch (FixMorph) |
drivers/dma-buf/sw_sync.c |
|
Original Patch (Reference) Mainline Commit: 0b1d250a |
drivers/usb/serial/io_ti.c |
|
|
Ported Patch (Manual) Stable Commit: 23b94d65 |
drivers/usb/serial/io_ti.c |
|
| Generated Patch (FixMorph) |
drivers/dma-buf/sw_sync.c |