article

Generic patch inference

Authors:

Jesper Andersen,

Julia L. LawallAuthors Info & Claims

Automated Software Engineering, Volume 17, Issue 2

Pages 119 - 148

https://doi.org/10.1007/s10515-010-0062-z

Published: 01 June 2010 Publication History

Abstract

A key issue in maintaining Linux device drivers is the need to keep them up to date with respect to evolutions in Linux internal libraries. Currently, there is little tool support for performing and documenting such changes.

In this paper we present a tool, spdiff, that identifies common changes made in a set of files and their updated versions, and extracts a generic patch performing those changes. Library developers can use our tool to extract a generic patch based on the result of manually updating a few typical driver files, and then apply this generic patch to other drivers. Driver developers can use it to extract an abstract representation of the set of changes that others have made.

Our experiments on recent changes in Linux show that the inferred generic patches are more concise than the corresponding patches found in commits to the Linux source tree while being safe with respect to the changes performed in the provided driver files.

References

[1]

Andersen, J.: Semantic patch inference. Ph.D. dissertation, University of Copenhagen, Feb. 2010.

Google Scholar

[2]

Chawathe, S.S., Rajaraman, A., Garcia-Molina, H., Widom, J.: Change detection in hierarchically structured information. In: SIGMOD '96: Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pp. 493-504. ACM Press, New York (1996).

Digital Library

Google Scholar

[3]

Conchon, S., Filliâtre, J.-C.: Type-safe modular hash-consing. In: ACM SIGPLAN Workshop on ML, Portland, Oregon, September 2006, supersedes (Filliâtre, 2000). {Online}. Available: http://www.lri.fr/filliatr/ftp/publis/hash-consing2.ps

Crossref

Google Scholar

[4]

Filliâtre, J.-C.: Hash consing in an ML framework. LRI, Université Paris Sud, Research Report 1368, September 2000. {Online}. Available: http://www.lri.fr/~filliatr/ftp/publis/hash-consing.ps.gz

Google Scholar

[5]

Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C.V., Loingtier, J.-M., Irwin, J.: Aspect-oriented programming. In: ECOOP'97--Object-Oriented Programming, 11th European Conference. Jyväskylä, Finland. Lecture Notes in Computer Science, vol. 1241, pp. 220-242. Springer, Berlin (1997).

Google Scholar

[6]

Kim, M., Notkin, D., Grossman, D.: Automatic inference of structural changes for matching across program versions. In: ICSE '07: Proceedings of the 29th International Conference on Software Engineering, Washington, DC, USA, pp. 333-343. IEEE Computer Society, Los Alamitos (2007).

Crossref

Google Scholar

[7]

MacKenzie, D., Eggert, P., Stallman, R.: Comparing and Merging Files With Gnu Diff and Patch, Network Theory Ltd., Jan. 2003, unified Format section, http://www.gnu.org/software/diffutils/ manual/html_node/Unified-Format.html

Google Scholar

[8]

Neamtiu, I., Foster, J.S., Hicks, M.: Understanding source code evolution using abstract syntax tree matching. SIGSOFT Softw. Eng. Notes 30(4), 1-5 (2005).

Digital Library

Google Scholar

[9]

Padioleau, Y., Lawall, J.L., Muller, G.: Understanding collateral evolution in Linux device drivers. In: The first ACM SIGOPS EuroSys Conference (EuroSys 2006), Leuven, Belgium, Apr. 2006, pp. 59-71.

Crossref

Google Scholar

[10]

Padioleau, Y., Lawall, J., Hansen, R.R., Muller, G.: Documenting and automating collateral evolutions in Linux device drivers. In: Eurosys 2008, Glasgow, Scotland, Mar. 2008, pp. 247-260.

Crossref

Google Scholar

[11]

Weissgerber, P., Diehl, S.: Identifying refactorings from source-code changes. In: ASE '06: Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering, Washington, DC, USA, pp. 231-240. IEEE Computer Society, Los Alamitos (2006).

Crossref

Google Scholar

Cited By

View all

Yu ZMartinez MChen ZBissyandé TMonperrus M(2023)Learning the Relation Between Code Features and Code Transforms With Structured PredictionIEEE Transactions on Software Engineering10.1109/TSE.2023.327538049:7(3872-3900)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3275380
Dilhara MDig DKetkar AGrundy JPollock LPenta M(2023)PyEvolve: Automating Frequent Code Changes in Python ML SystemsProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00091(995-1007)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00091
Pan RLe VNagappan NGulwani SLahiri SKaufman M(2021)Can Program Synthesis be Used to Learn Merge Conflict Resolutions?Proceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00077(785-796)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00077
Show More Cited By

Index Terms

Generic patch inference
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Software management
        Software maintenance
2. Software and its engineering
  1. Software creation and management
    1. Software development techniques
    2. Software post-development issues

Recommendations

Generic Patch Inference
ASE '08: Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering

A key issue in maintaining Linux device drivers is the need to update drivers in response to evolutions in Linux internal libraries. Currently, there is little tool support for performing and documenting such changes. In this paper we present a tool, ...
Impact of tool support in patch construction
ISSTA 2017: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis

In this work, we investigate the practice of patch construction in the Linux kernel development, focusing on the differences between three patching processes: (1) patches crafted entirely manually to fix bugs, (2) those that are derived from warnings ...
A tool for converting Linux device drivers into Solaris compatible binaries
Research Articles

The Linux operating system is quickly becoming a standard, attracting a wide user community and supporting a broad variety of applications and devices. Other vendors, such as Sun, have provided Linux-compatible system call interfaces to their kernels, ...

Reviews

Reviewer: Bernard Kuc

Let's say you are working on a large code base, when you happen to make a change to a core interface and find yourself changing hundreds of dependent files. Unluckily, the changes are a bit too involved for a simple search and replace. What the authors propose is a method for automatically identifying the replacement pattern from a sample set of changed files, and then applying the pattern automatically throughout the code base. Depending on your background, you may actually see the above scenario as an indication that some major refactoring is needed. If a small change causes many files to need to be changed, then obviously there must have been a bit too much copy and paste development at some point in the past. However, not all domains are suited to whole-scale refactoring. Device driver development on Linux, the domain chosen by the authors, is one such example. Distributed ownership of similar code implies that any change in internal libraries will have to be applied by numerous contributors. The authors present a tool that, given a subset of files in pairs of pre-change and post-change files, will extract a generic abstract representation of the change that can then be replicated throughout the code base. Starting with a formal presentation of their algorithm, the authors describe their implementation and provide example runs against actual patches applied to the Linux source tree. They demonstrate the types of changes that their tool can successfully abstract and the types of changes where it fails. In summary, the paper presents a simple yet effective-albeit a bit dangerous-timesaving tool. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image Automated Software Engineering

Automated Software Engineering Volume 17, Issue 2

June 2010

96 pages

ISSN:0928-8910

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yu ZMartinez MChen ZBissyandé TMonperrus M(2023)Learning the Relation Between Code Features and Code Transforms With Structured PredictionIEEE Transactions on Software Engineering10.1109/TSE.2023.327538049:7(3872-3900)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TSE.2023.3275380
Dilhara MDig DKetkar AGrundy JPollock LPenta M(2023)PyEvolve: Automating Frequent Code Changes in Python ML SystemsProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00091(995-1007)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00091
Pan RLe VNagappan NGulwani SLahiri SKaufman M(2021)Can Program Synthesis be Used to Learn Merge Conflict Resolutions?Proceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00077(785-796)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00077
Koyuncu ALiu KBissyandé TKim DKlein JMonperrus MLe Traon Y(2020)FixMiner: Mining relevant fix patterns for automated program repairEmpirical Software Engineering10.1007/s10664-019-09780-z25:3(1980-2024)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.1007/s10664-019-09780-z
Sivaraman AZhang TVan den Broeck GKim MAtlee JBultan TWhittle J(2019)Active inductive logic programming for code searchProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00044(292-303)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00044
Zhen YZhang WDai ZMao JChen Y(2018)Is It Possible to Automatically Port Kernel Modules?Proceedings of the 9th Asia-Pacific Workshop on Systems10.1145/3265723.3265732(1-8)Online publication date: 27-Aug-2018
https://dl.acm.org/doi/10.1145/3265723.3265732
Monperrus M(2018)Automatic Software RepairACM Computing Surveys10.1145/310590651:1(1-24)Online publication date: 23-Jan-2018
https://dl.acm.org/doi/10.1145/3105906
Wang SLo DJiang L(2016)AutoQueryAutomated Software Engineering10.1007/s10515-014-0170-223:3(393-425)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s10515-014-0170-2
Uquillas Gómez VDucasse SKellens A(2014)Supporting streams of changes during branch integrationScience of Computer Programming10.1016/j.scico.2014.07.01296:P1(84-106)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1016/j.scico.2014.07.012
Kapur PCossette BWalker R(2010)Refactoring references for library migrationACM SIGPLAN Notices10.1145/1932682.186951845:10(726-738)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869518
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations