Takeshi Kakimoto, Akito Monden, Yasutaka Kamei, Haruaki Tamada, Masateru Tsunoda, and Ken-ichi
Matsumoto, ̀̀Using Software Birthmarks to Identify Similar Classes and Major Functionalities,'' In
Proceedings of the 3rd International Workshop on Mining Software Repositories (MSR2006) Mining
Challenge 2006, pp.171-172, May 2006. (Shanghai, China)

Using Software Birthmarks to Identify
Similar Classes and Major Functionalities
Takeshi Kakimoto Akito Monden Yasutaka Kamei
Haruaki Tamada Masateru Tsunoda Ken-ichi Matsumoto
Nara Institute of Science and Technology
8916-5 Takayama Ikoma Nara Japan 630-0192{takesi-k, akito-m, yasuta-k, harua-t, masate-t, matumoto}@is.naist.jp
ABSTRACTSoftware birthmarks are unique and native characteristics of every
software component. Two components having similar birthmarks
indicate that they are similar in functionality, structure and implementation. Questions addressed in this paper include: Whichare similar class files? Can they be gathered into one class file?
What are major functionalities among class files? To answer tothese questions, this paper analyzed the similarity of birthmarks
for all pairs of classes in ArgoUML, and visualized them using
Multi-Dimensional Scaling (MDS). As a result, three pairs of very
similar class files, which seem to be made by copy-and-paste
programming, were identified. Also, four major functionalities
were identified in the MDS space.

Categories and Subject Descriptors
D.2.8 [Software Engineering]: Metrics – Product Metrics; K.6.3[Management of Computing and Information Systems]: Software Management – Software maintenance;

General Terms
Measurement, Experimentation

Keywords
software birthmark, multi-dimensional scaling

TARGET OSS PROJECTArgoUML (written in Java)MINING AREA
- Change impact, propagation coupling analysis(2) What are major functionalities among class files?
This question needs to be answered when one joins a project andtries to understand the mapping between class files and their functionalities.

INPUT DATA
From 1,432 class files of ArgoUML release 0.20, 61 classes having more than 30 lines of source code were chosen as an input
dataset.

1. APPROACH AND TOOLS USED
1.1 Birthmark
Java birthmarks[1] are unique and native characteristics of every
Java class files. Originally, birthmarks are used to detect the stolen (i.e. illegally copied) Java class files across two different projects. In this paper we use birthmarks to find similar class files ina project to help maintenance activities.
We used a Java birthmark tool called jbirth1 to extract four typesof birthmarks from each class file: (1) constant values in field
variables (CVFV birthmark), (2) sequence of method calls (SMCbirthmark), (3) an inheritance structure (IS birthmark), and (4)used classes (UC birthmark). Two class files having similarbirthmarks indicate that they are similar in functionality, structure
and implementation.
To compute the similarity between two class files p and q in termsof their birthmarks, we used the following definition [1].
Definition (Similarity) Let f(p) = (p1, …, pn) and f(q) = (q1, …,qn) be birthmarks with length n, extracted from class files p and q.
Let s be the number of pairs (pi, qi)’s such that pi = qi (1 ≤ i ≤ n).
Then, similarity between f(p) and f(q) is defined by: s/n·100.

- Architecture and design quality analysis

1.2 Multi-Dimensional Scaling (MDS)MINING QUESTIONS

After computing the similarity of birthmarks for all pairs of 61
class files, we used MDS to visualize their relationships. Major
functionalities can be identified as clusters in the MDS space. We
used SPSS as a MDS tool.

The following two questions are addressed in this paper.
(1) Which are similar class files?
This question needs to be answered when one wants to refactor aJava program. Similar class files are often refactored into oneclass file to improve software maintainability. Also, when onemodifies a class file, he/she often needs to find similar class files
that need to be modified as well.
Copyright is held by the author/owner(s). MSR'06, May 22-23, 2006,
Shanghai, China. ACM 1-59593-085-X/06/0005.

2. RESULTS AND INTERPRETATIONS
2.1 Finding Similar Class Files
Table 1 shows pairs of classes that had high-similarity birthmarks(similarity > 0.9). As we investigated their source code, each pair1

http://se.naist.jp/jbirth/ui.explorer.ExplorerPopup

1.5
1.00.5

uml.cogni ti ve.cri tics. Init
cogniti ve.ToD oI tem

cognitive.Resol vedCritic
ui. ProjectBrow ser
cogni tive.ui.ToDoPane
ui .A boutBox
uml .ui. UM LA ddD ialog
uml.ui .SourcePathTableM odel
ui. TabResults
um l. ui.TabTaggedValues
um l. generator.ParserD ispl ayui .D etailsPane
cognitive.ui .W i zStepChoiceui.SettingsTabL ayout ui. Setti ngsT abEnvironmentui .SettingsTabA ppearance
cogni tive.ui.W izStepTextField
cogniti ve.ui. W i zStepConfi rm
ui .Setti ngsTabPreferences
persistence.PGM LParser
cognitive.ui. W i zStepCue
ui. SettingsTabU serWizStep

SettingsTab0.0
uml .ui.behavior.com mon_ behavi or.PropPanel Reception
uml.di agram.state.ui. UM LStateDiagram
uml .ui.foundation. core.PropPanelAssociationClass-0.5

um l .ui.foundation.core. PropPanelGeneralization
uml .ui.TabD ocum entati on
uml.ui .behavior. state_ machines.PropPanel Transiti on
um l. ui.behavior.use_ cases. PropPanelExtend-1.0

uml .ui. behavior.comm on_ behavior.PopupM enuN ew Action

PropPanelcogniti ve.ui.D ismissToDoItemD ialog
uml.generator.ui. Cl assGenerationD ialog
um l .diagram. ui.FigA ssociation
ui. Fi ndD ial og
uml.diagram .sequence.ui.Fi gCl assi fi erRole
uml.di agram .static_ structure. ui.FigCom ment

diagramuml.reveng. java.JavaLexer
cogni tive.ui.A ddToDoItemD ialog
um l.di agram. collaboration.ui. Fi gCl assi fierRol e-1.5-2-1012Figure 1. Relationship among class files in MDS space based on similarity of birthmark.
Table 1. Pair of classes having high similarity birthmarks.
Class pairs
uml.ui.behavior.collaborations.PropPanelCollaboration
uml.ui.behavior.use_cases.PropPanelUseCase
uml.ui.behavior.collaborations.PropPanelMessage
uml.ui.behavior.state_machines.PropPanelTransition
uml.ui.foundation.core.PropPanelClass
uml.ui.foundation.core.PropPanelAssociationClass

similarity
96.09
93.91
92.78

had very similar functionality, structure and implementation. It
can be considered that these pairs were made by copy-and-paste
programming, and can be refactored so as to reduce the duplicatedcode.

2.2 Finding Major Functionalities
Figure 1 shows relationship among classes in the MDS space.
Classes having similar birthmarks are located in near space, andclasses having dissimilar birthmarks are located far apart. From
Figure 1, we could identify the following four major functionalities.
• Most of classes at the lower right part (“diagram” circle) wererelated to diagram (e.g. FigAssociation class, FigUseCaseclass.)• Classes at the lower left part (“PropPanel” circle) were related
to PropPanel (e.g. PropPanelAttribute class, PropPanelOperation class.)• Classes related to WizStep were in “WizStep” circle (e.g.
WizStepConfirm class.)• Classes related to SettingsTab were in “SettingsTab” circle(e.g. SettingsTabEnvironment class.)
All these functionalities were identified by finding clusters andsimilar file names in the MDS space. We believe that using birthmarks together with MDS is useful to understand the relations
between class files and to roughly recognize their functionalities.

3. CONCLUSIONSThis paper analyzed the similarity of birthmarks for all pairs ofclasses in ArgoUML, and visualized them using MDS. As a result,three pairs of very similar class files were identified. Also, fourmajor functionalities (diagram, PropPanel, WizStep and SettingsTab) were identified in the MDS space.

4. ACKNOWLEDGMENTS
This work is supported by the EASE (Empirical Approach toSoftware Engineering) project of the Comprehensive Development of e-Society Foundation Software program of the Ministryof Education, Culture, Sports, Science and Technology of Japan.

5. REFERENCES[1] Tamada, H., Nakamura, M., Monden, A., Matsumoto, K.
Java birthmark –Detecting the software theft. IEICE Transactions on Information and Systems, E88-D, 9 (Sept. 2005),
2148-2158