More Web Proxy on the site http://driver.im/

research-article

Automatic clustering of code changes

Authors:

Patrick Kreutzer,

Bjoern M. Eskofier,

Michael PhilippsenAuthors Info & Claims

MSR '16: Proceedings of the 13th International Conference on Mining Software Repositories

Pages 61 - 72

https://doi.org/10.1145/2901739.2901749

Published: 14 May 2016 Publication History

Abstract

Several research tools and projects require groups of similar code changes as input. Examples are recommendation and bug finding tools that can provide valuable information to developers based on such data. With the help of similar code changes they can simplify the application of bug fixes and code changes to multiple locations in a project. But despite their benefit, the practical value of existing tools is limited, as users need to manually specify the input data, i.e., the groups of similar code changes.

To overcome this drawback, this paper presents and evaluates two syntactical similarity metrics, one of them is specifically designed to run fast, in combination with two carefully selected and self-tuning clustering algorithms to automatically detect groups of similar code changes.

We evaluate the combinations of metrics and clustering algorithms by applying them to several open source projects and also publish the detected groups of similar code changes online as a reference dataset. The automatically detected groups of similar code changes work well when used as input for LASE, a recommendation system for code changes.

References

[1]

G. M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In SJCC'67: Spring Joint Computer Conf., pages 483--485, Atlantic City, NJ, Apr. 1967.

Digital Library

[2]

P. Andritsos and V. Tzerpos. Information-Theoretic Software Clustering. IEEE Trans. on Softw. Eng., 31(2):150--165, Feb. 2005.

Digital Library

[3]

N. Anquetil, C. Fourrier, and T. C. Lethbridge. Experiments with Clustering As a Software Remodularization Method. In WCRE'99: Working Conf. on Reverse Eng., pages 235--255, Atlanta, GA, Oct. 1999.

Digital Library

[4]

B. S. Baker. On Finding Duplication and Near-duplication in Large Software Systems. In WCRE'95: Working Conf. on Reverse Eng., pages 86--95, Toronto, Canada, July 1995.

Digital Library

[5]

M. Barnett, C. Bird, J. Brunet, and S. Lahiri. Helping Developers Help Themselves: Automatic Decomposition of Code Review Changesets. In ICSE'15: Intl. Conf. on Softw. Eng., Florence, Italy, May 2015.

Digital Library

[6]

I. D. Baxter, A. Yahin, L. Moura, M. Sant'Anna, and L. Bier. Clone Detection Using Abstract Syntax Trees. In ICSM'98: Intl. Conf. on Softw. Maintenance, pages 368--377, Bethesda, MD, Nov. 1998.

Digital Library

[7]

M. Belkin and P. Niyogi. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6): 1373--1396, June 2003.

Digital Library

[8]

L. Bergroth, H. Hakonen, and T. Raita. A Survey of Longest Common Subsequence Algorithms. In SPIRE'00: String Processing and Inf. Retrieval Symp., pages 39--48, A Coruna, Spain, Sep. 2000.

Digital Library

[9]

D. Beyer and A. Noack. Clustering Software Artifacts Based on Frequent Common Changes. In IWPC'05: Intl. Workshop on Program Comprehension, pages 259--268, St. Louis, MO, May 2005.

Digital Library

[10]

A. Corazza, S. D. Martino, V. Maggio, and G. Scanniello. Investigating the Use of Lexical Information for Software System Clustering. In CSMR'11: European Conf. on Soft. Maintenance and Reengineering, pages 35--44, Oldenburg, Germany, March 2011.

Digital Library

[11]

T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algorithms. The MIT Press, Cambridge, MA, 3rd edition, 2009.

Digital Library

[12]

M. Dias, A. Bacchelli, G. Gousios, D. Cassou, and S. Ducasse. Untangling Fine-Grained Code Changes. In SANER'15: Intl. Conf. on Softw. Analysis, Evolution, and Reengineering, pages 341--350, Montréal, Canada, March 2015.

[13]

N. Dragan, M. L. Collard, M. Hammad, and J. I. Maletic. Using Stereotypes to Help Characterize Commits. In ICSM'11: Intl. Conf. on Softw. Maintenance, pages 520--523, Williamsburg, VA, Sep. 2011.

Digital Library

[14]

M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD'96: Intl. Conf. on Knowledge Discovery and Data Mining, pages 226--231, Portland, OR, Aug. 1996.

[15]

J. Falleri, F. Morandat, X. Blanc, M. Martinez, and M. Monperrus. Fine-grained and accurate source code differencing. In ASE'14: Intl. Conf. Automated Softw. Eng., pages 313--324, Västerås, Sweden, Sep. 2014.

Digital Library

[16]

B. Fluri and H. C. Gall. Classifying Change Types for Qualifying Change Couplings. In ICPC'06: Intl. Conf. on Program Comprehension, pages 35--45, Athens, Greece, June 2006.

Digital Library

[17]

B. Fluri, E. Giger, and H. C. Gall. Discovering Patterns of Change Types. In ASE'08: Intl. Conf. on Automated Softw. Eng., pages 463--466, L'Aquila, Italy, Sep. 2008.

Digital Library

[18]

B. Fluri, M. Wuersch, M. Pinzger, and H. Gall. Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction. IEEE Trans. Softw. Eng., 33(11):725--743, Nov. 2007.

Digital Library

[19]

A. L. N. Fred and A. K. Jain. Combining Multiple Clusterings Using Evidence Accumulation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 27(6):835--850, June 2005.

Digital Library

[20]

W. Gan and D. Li. Optimal Choice of Parameters for a Density-Based Clustering Algorithm. In Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, volume 2639 of Lecture Notes in Computer Science, pages 603--606. Springer Berlin Heidelberg, 2003.

Digital Library

[21]

J. C. Gower and G. J. S. Ross. Minimum Spanning Trees and Single Linkage Cluster Analysis. Applied Statistics, 18(1):54--64, 1969.

[22]

M. Hashimoto, A. Mori, and T. Izumida. A Comprehensive and Scalable Method for Analyzing Fine-Grained Source Code Change Patterns. In SANER'15: Intl. Conf. on Softw. Analysis, Evolution and Reengineering, pages 351--360, Montréal, Canada, March 2015.

[23]

K. Herzig and A. Zeller. The Impact of Tangled Code Changes. In MSR'13: Working Conf. on Mining Software Repositories, pages 121--130, San Francisco, CA, May 2013.

Digital Library

[24]

Y. Higo and S. Kusumoto. Identifying Clone Removal Opportunities Based on Co-evolution Analysis. In IWPSE'13: Intl. Workshop on Principles on Software Evolution, pages 28--37, Saint Petersburg, Russia, Aug. 2013.

Digital Library

[25]

A. Hindle, D. M. German, M. W. Godfrey, and R. C. Holt. Automatic Classication of Large Changes into Maintenance Categories. In ICPC'09: Intl. Conf. on Program Comprehension, pages 30--39, Vancouver, Canada, May 2009.

[26]

A. Hinneburg and H.-H. Gabriel. DENCLUE 2.0: Fast Clustering Based on Kernel Density Estimation. In IDA'07: Intl. Conf. on Intelligent Data Analysis, pages 70--80, Ljubljana, Slovenia, Sep. 2007.

Digital Library

[27]

D. S. Hirschberg. A Linear Space Algorithm for Computing Maximal Common Subsequences. Commun. ACM, 18(6):341--343, June 1975.

Digital Library

[28]

J. Hopcroft and R. Tarjan. Algorithm 447: Efficient Algorithms for Graph Manipulation. Commun. ACM, 16(6):372--378, June 1973.

Digital Library

[29]

A. Hora, N. Anquetil, S. Ducasse, and M. Valente. Mining System Specific Rules from Change Patterns. In WCRE'13: Working Conf. on Reverse Eng., pages 331--340, Koblenz, Germany, Oct. 2013.

[30]

J. Jacobellis, N. Meng, and M. Kim. Cookbook: In Situ Code Completion Using Edit Recipes Learned from Examples. In ICSE'14: Intl. Conf. Softw. Eng., pages 584--587, Hyderabad, India, May 2014.

Digital Library

[31]

P. Jia, J. Yin, X. Huang, and D. Hu. Incremental Laplacian Eigenmaps by Preserving Adjacent Information Between Data Points. Pattern Recogn. Lett., 30(16): 1457--1463, Dec. 2009.

Digital Library

[32]

L. Jiang, G. Misherghi, Z. Su, and S. Glondu. DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones. In ICSE'07: Intl. Conf. on Softw. Eng., pages 96--105, Minneapolis, MN, May 2007.

Digital Library

[33]

T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A Multilinguistic Token-based Code Clone Detection System for Large Scale Source Code. IEEE Trans. on Softw. Eng., 28(7):654--670, July 2002.

Digital Library

[34]

D. Kawrykow. Enabling Precise Interpretations of Software Change Data. Master's Thesis, School of Computer Science, McGill University, Montreal, Aug. 2011.

[35]

B. W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49(2):291--307, Feb. 1970.

[36]

S. Kim, K. Pan, and E. E. J. Whitehead, Jr. Memories of Bug Fixes. In SIGSOFT'06/FSE-14: Intl. Symp. on Foundations of Softw. Eng., pages 35--45, Portland, OR, Nov. 2006.

Digital Library

[37]

S. Kim, E. J. Whitehead, Jr., and Y. Zhang. Classifying Software Changes: Clean or Buggy? IEEE Trans. on Softw. Eng., 34(2):181--196, March 2008.

Digital Library

[38]

J. Li and M. D. Ernst. CBCD: Cloned Buggy Code Detector. In ICSE'12: Intl. Conf. on Softw. Eng., pages 310--320, Zürich, Switzerland, June 2012.

Digital Library

[39]

Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code. In OSDI'04: Symp. on Opearting Systems Design & Implementation, pages 289--302, San Francisco, CA, Dec. 2004.

Digital Library

[40]

O. Maqbool and H. Babri. Hierarchical Clustering for Software Architecture Recovery. IEEE Trans. on Softw. Eng., 33(11):759--780, Nov. 2007.

Digital Library

[41]

N. Meng, L. Hua, M. Kim, and K. S. McKinley. Does Automated Refactoring Obviate Systematic Editing? In ICSE'15: Intl. Conf. Softw. Eng. - Volume 1, pages 392--402, Florence, Italy, May 2015.

Digital Library

[42]

N. Meng, M. Kim, and K. S. McKinley. LASE: Locating and Applying Systematic Edits by Learning from Examples. In ICSE'13: Intl. Conf. Softw. Eng., pages 502--511, San Francisco, CA, May 2013.

Digital Library

[43]

S. Needleman and C. Wunsch. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. J. Molecular Biol., 48(3):443--453, March 1970.

[44]

S. Negara, M. Codoban, D. Dig, and R. E. Johnson. Mining Fine-grained Code Changes to Detect Unknown Change Patterns. In ICSE'14: Intl. Conf. on Softw. Eng., pages 803--813, Hyderabad, India, May 2014.

Digital Library

[45]

H. A. Nguyen, A. T. Nguyen, T. T. Nguyen, T. N. Nguyen, and H. Rajan. A Study of Repetitiveness of Code Changes in Software Evolution. In ASE'13: Intl. Conf. on Automated Softw. Eng., pages 180--190, Palo Alto, CA, Nov. 2013.

Digital Library

[46]

H. A. Nguyen, T. T. Nguyen, J. G. Wilson, A. T. Nguyen, M. Kim, and T. N. Nguyen. A Graph-based Approach to API Usage Adaptation. In OOPSLA'10: Proc. Intl. Conf. Object-Oriented Progr., Systems, Languages & Appl., pages 302--321, Reno/Tahoe, NV, Oct. 2010.

Digital Library

[47]

T. T. Nguyen, H. A. Nguyen, N. H. Pham, J. Al-Kofahi, and T. N. Nguyen. Recurring Bug Fixes in Object-oriented Programs. In ICSE'10: Intl. Conf. on Softw. Eng. - Volume 1, pages 315--324, Cape Town, South Africa, May 2010.

Digital Library

[48]

J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, 22 (8):888--905, Aug. 2000.

Digital Library

[49]

M. Stoerzer, B. G. Ryder, X. Ren, and F. Tip. Finding Failure-inducing Changes in Java Programs Using Change Classification. In SIGSOFT'06/FSE-14: Intl. Symp. on Foundations of Softw. Eng., pages 57--68, Portland, OR, Nov. 2006.

Digital Library

[50]

J. W. Tukey. Exploratory Data Analysis. Addison-Wesley, Reading, MA, 1977.

[51]

S. Van Dongen. Graph Clustering Via a Discrete Uncoupling Process. SIAM J. on Matrix Analysis and Applications, 30(1):121--141, Feb. 2008.

Digital Library

[52]

A. Vanya, L. Hofland, S. Klusener, P. Van De Laar, and H. Van Vliet. Assessing Software Archives with Evolutionary Clusters. In ICPC'08: Intl. Conf. on Program Comprehension, pages 192--201, Amsterdam, The Netherlands, June 2008.

Digital Library

[53]

U. Von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4):395--416, 2007.

Digital Library

[54]

S. Wang, D. Lo, and X. Jiang. Understanding Widespread Changes: A Taxonomic Study. In CSMR'13: European Conf. on Softw. Maintenance and Reengineering, pages 5--14, Genova, Italy, March 2013.

Digital Library

[55]

T. A. Wiggerts. Using Clustering Algorithms in Legacy Systems Remodularization. In WCRE'97: Working Conf. on Reverse Eng., pages 33--43, Amsterdam, The Netherlands, Oct. 1997.

Digital Library

[56]

M. J. Zaki and W. Meira Jr. Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press, New York, NY, 2014.

[57]

T. Zhang, M. Song, J. Pinedo, and M. Kim. Interactive Code Review for Systematic Changes. In ICSE'15: Intl. Conf. Softw. Eng. - Volume 1, pages 111--122, Florence, Italy, May 2015.

Digital Library

Cited By

Sejfia ADas SShafiq SMedvidović NRoychoudhury APaiva AAbreu RStorey M(2024)Toward Improved Deep Learning-based Vulnerability DetectionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3608141(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3608141
Zhou DWu YPeng XZhang JLi Z(2024)Revealing code change propagation channels by evolution history miningJournal of Systems and Software10.1016/j.jss.2023.111912208:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.jss.2023.111912
Karatzas MDiamantopoulos TSymeonidis A(2024)Extracting Fix Patterns for Static Analysis Violations Based on Collective Developer KnowledgeSoftware: Practice and Experience10.1002/spe.3384Online publication date: 24-Oct-2024
https://doi.org/10.1002/spe.3384
Show More Cited By

Index Terms

Automatic clustering of code changes
1. Information systems
  1. Information systems applications
    1. Data mining
      1. Clustering
2. Software and its engineering
  1. Software notations and tools
    1. Software libraries and repositories

Recommendations

Mining fine-grained code changes to detect unknown change patterns
ICSE 2014: Proceedings of the 36th International Conference on Software Engineering

Identifying repetitive code changes benefits developers, tool builders, and researchers. Tool builders can automate the popular code changes, thus improving the productivity of developers. Researchers can better understand the practice of code ...
A C/C++ Code Vulnerability Dataset with Code Changes and CVE Summaries
MSR '20: Proceedings of the 17th International Conference on Mining Software Repositories

We collected a large C/C++ code vulnerability dataset from open-source Github projects, namely Big-Vul. We crawled the public Common Vulnerabilities and Exposures (CVE) database and CVE-related source code repositories. Specifically, we collected the ...
Evolution-Based Tabu Search Approach to Automatic Clustering

Traditional clustering algorithms (e.g., the K-means algorithm and its variants) are used only for a fixed number of clusters. However, in many clustering applications, the actual number of clusters is unknown beforehand. The general solution to this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MSR '16: Proceedings of the 13th International Conference on Mining Software Repositories

May 2016

544 pages

ISBN:9781450341868

DOI:10.1145/2901739

General Chair:
Miryung Kim
University of California, Los Angeles
,
Program Chairs:
Romain Robbes
University of Chile, Chile
,
Christian Bird
Microsoft Research

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

ACM: Association for Computing Machinery
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\DATC: IEEE Computer Society
TCSE: IEEE Computer Society's Tech. Council on Software Engin.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 May 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICSE '16

Sponsor:

ACM
SIGSOFT
IEEE-CS\DATC
TCSE

ICSE '16: 38th International Conference on Software Engineering

May 14 - 22, 2016

Texas, Austin

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
919
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sejfia ADas SShafiq SMedvidović NRoychoudhury APaiva AAbreu RStorey M(2024)Toward Improved Deep Learning-based Vulnerability DetectionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3608141(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3608141
Zhou DWu YPeng XZhang JLi Z(2024)Revealing code change propagation channels by evolution history miningJournal of Systems and Software10.1016/j.jss.2023.111912208:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.jss.2023.111912
Karatzas MDiamantopoulos TSymeonidis A(2024)Extracting Fix Patterns for Static Analysis Violations Based on Collective Developer KnowledgeSoftware: Practice and Experience10.1002/spe.3384Online publication date: 24-Oct-2024
https://doi.org/10.1002/spe.3384
Bittner PSchultheiß AGreiner SMoosherr BKrieter STinnes CKehrer TThüm T(2023)Views on Edits to Variational SoftwareProceedings of the 27th ACM International Systems and Software Product Line Conference - Volume A10.1145/3579027.3608985(141-152)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1145/3579027.3608985
Garg PSengamedu S(2022)Synthesizing code quality rules from examplesProceedings of the ACM on Programming Languages10.1145/35633506:OOPSLA2(1757-1787)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563350
Sarhan QAhmed BBures MZamli K(2022)Software Module Clustering: An In-Depth Literature AnalysisIEEE Transactions on Software Engineering10.1109/TSE.2020.304255348:6(1905-1928)Online publication date: 1-Jun-2022
https://doi.org/10.1109/TSE.2020.3042553
Koryabkin DIgnatyev V(2022)Automatic Mining of Code Fix Patterns from Code Repositories2022 Ivannikov Memorial Workshop (IVMEM)10.1109/IVMEM57067.2022.9983967(27-34)Online publication date: 23-Sep-2022
https://doi.org/10.1109/IVMEM57067.2022.9983967
Herbold STrautsch ALedel BAghamohammadi AGhaleb TChahal KBossenmaier TNagaria BMakedonski PAhmadabadi MSzabados KSpieker HMadeja MHoy NLenarduzzi VWang SRodríguez-Pérez GColomo-Palacios RVerdecchia RSingh PQin YChakroborti DDavis WWalunj VWu HMarcilio DAlam OAldaeej AAmit ITurhan BEismann SWickert AMalavolta ISulír MFard FHenley AKourtzanidis STuzun ETreude CShamasbi SPashchenko IWyrich MDavis JSerebrenik AAlbrecht EAktas EStrüber DErbel J(2022)A fine-grained data set and analysis of tangling in bug fixing commitsEmpirical Software Engineering10.1007/s10664-021-10083-527:6Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10664-021-10083-5
Nowack VBowes DCounsell SHall THaraldsson SWinter EWoodward J(2021)Expanding Fix Patterns to Enable Automatic Program Repair2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE52982.2021.00015(12-23)Online publication date: Oct-2021
https://doi.org/10.1109/ISSRE52982.2021.00015
Noda KYokoyama HKikuchi S(2021)Sirius: Static Program Repair with Dependence Graph-Based Systematic Edit Patterns2021 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME52107.2021.00045(437-447)Online publication date: Sep-2021
https://doi.org/10.1109/ICSME52107.2021.00045
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents