ProceedingsInternational Workshop on
Empirical Software Engineering in Practice 2010
(IWESEP 2010)
Nara, Japan, December 7-8, 2010

Sponsored by
StagE Project, MEXT JapanFoundation for Nara Institute of Science and Technology
Microsoft Research
Osaka University
Nara Institute of Science and Technology (NAIST)In cooperation with
SIG Software Science, Information and Systems Society, IEICESIG Software Engineering, IPSJ

Table of Contents
Preface ............................................................................................................................ iv
Organization .................................................................................................................. vi

Keynote Address
Empirical Software Engineering and Measurement at Microsoft .....................................3
Thomas Zimmermann

Project Management
Process Fragment Based Process Complexity with Workflow Management Tables ........7
Masaki Obana, Noriko Hanakawa, Norihiro Yoshida and Hajimu Iida
Applying Outlier Deletion to Analogy Based Cost Estimation.......................................13
Masateru Tsunoda, Akito Monden, Mizuho Watanabe,
Takeshi Kakimoto and Ken-ichi Matsumoto
A Survey of Public Datasets for Comparative Effort Prediction Studies ........................19
Sousuke Amasaki and Tomoyuki Yokogawa

Faults and Verification
Reconstructing Fine-Grained Versioning Repositories with
Git for Method-Level Bug Prediction .............................................................................27
Hideaki Hata, Osamu Mizuno and Tohru Kikuno
Reachability Analysis of Probabilistic Timed Automata
Based on an Abstraction Refinement Technique ............................................................33
Takeshi Nagaoka, Akihiko Ito, Toshiaki Tanaka,
Kozo Okano and Shinji Kusumoto
Fault-prone Module Prediction Using Contents of Comment Lines ...............................39
Osamu Mizuno and Yukinao Hirata

iiProcess Analysis
A Preliminary Study on Impact of Software Licenses on Copy-and-Paste Reuse ..........47
Yu Kashima, Yasuhiro Hayase, Norihiro Yoshida,
Yuki Manabe and Katsuro Inoue
Using Program Slicing Metrics for the Analysis of Code Change Processes .................53
Raula Gaikovina Kula, Kyohei Fushida, Norihiro Yoshida and Hajimu Iida
Flexibly Highlighting in Replaying Operation History ...................................................59
Takayuki Omori and Katsuhisa Maruyamaiii

Preface
It is our great pleasure to welcome everyone to the International Workshop on
Empirical Software Engineering in Practice 2010 (IWESEP 2010). Our workshop is tofoster the development of the area by providing a forum where young researchers andpractitioners can report on and discuss their new research results and applications in thearea of empirical software engineering. The workshop encourages the exchange of ideas
within the international community so as to be able to understand, from an empirical
viewpoint, strengths and weaknesses of technology in use and new technologies, withthe expectation of furthering the more generic field of software engineering.
IWESEP has received 13 submission including 12 regular papers and 1 tool
demonstration proposal. After the careful evaluations of the program committee, 8
regular papers and 1 tool demonstration have been accepted to be presented at theworkshop. The papers cover a variety of topics, including project management, fault
prediction, formal verification and analysis of software development process. In
addition, the program includes a keynote speech by Dr. Thomas Zimmermann. We hopethat these proceedings will serve as a valuable reference for researchers and developers.
In addition, we hold the MSR School in Asia as the tutorial at IWESEP 2010. The
MSR School in Asia provides an overview of the Mining Software Repositories (MSR)
filed and an opportunity to learn the techniques used in this field. MSR is a rapidly
growing field that holds an annual tutorial and a co-located working conference at theInternational Conference on Software Engineering (ICSE) every year. We have invited
some of the top researchers, Dr. Ahmed Hassan, Dr. Sunghun Kim, and Dr. Thomas
Zimmermann, in the MSR field to give the tutorial.
Finally, on behalf of the program committee and the organizing committee, we thankyou for attending IWESEP 2010 and hope that you will we enjoy the workshop. We
would like to take this opportunity to thank the organizers who spend considerable timereviewing publications and preparations for this workshop.

iv

We hope you will have a great time and an unforgettable experience at the
IWESEP2010.
Akinori Ihara, Nara Institute of Science and Technology, Japan
IWESEP 2010 General Chair
Takashi Ishio, Osaka University, Japan
IWESEP2010 Program Chairv

Organization
General Chair
Akinori Ihara (Nara Institute of Science and Technology, Japan)
Program Chair
Takashi Ishio (Osaka University, Japan)
Publication Chair
Kyohei Fushida (Nara Institute of Science and Technology, Japan)
Publicity Co-Chair
Sunghun Kim (Hong Kong University of Science and Technology, China)
Masataka Nagura (Hitachi, Ltd., Japan)
Emad Shihab (Queen’s University, Canada)
Registration Chair
Masateru Tsunoda (Nara Institute of Science and Technology, Japan)
Local Arrangements Chair
Norihiro Yoshida (Nara Institute of Science and Technology, Japan)viProgram Committee
Bram Adams (Queen’s University, Canada)
Sousuke Amasaki (Okayama Prefectural University, Japan)
Christian Bird (Microsoft Research, USA)
Ahmed E. Hassan (Queen’s University, Canada)
Hideaki Hata (Osaka University, Japan)
Shinpei Hayashi (Tokyo Institute of Technology, Japan)
Israel Herraiz (University Alfonso X el Sabio, Spain)
Yasutaka Kamei (Queen’s University, Canada)
Masa Katahira (JAXA, Japan)
Shinji Kawaguchi (JAMSS, Japan)
Jacky Keung (NICTA, Australia)
Hua Jie Lee (University of Melbourne, Australia)
Shinsuke Matsumoto (Kobe University, Japan)
Koji Toda (Nara Institute of Science and Technology, Japan)
Hidetake Uwano (Nara National College of Technology, Japan)
Rodrigo Vivanco (University of Manitoba, Canada)
Thomas Zimmermann (Microsoft Research, USA)

vii

Keynote Address12Keynote Address
Empirical Software Engineering and Measurement at Microsoft
Thomas Zimmermann (Microsoft Research / University of Calgary)

Abstract:
Software engineering is an data rich activity: changes to source code are recorded inversion archives, bugs are reported to issue tracking systems, and communications arearchived in e-mails and newsgroups. The Empirical Software Engineering and
Measurement (ESM) group at Microsoft Research analyzes such data to better
understand various software development issues from an empirical perspective. In thistalk, I will highlight our research themes and activities using examples from ourresearch on socio technical congruence, bug reporting and triaging, and data-driven
software engineering. I will highlight our unique ability to leverage industrial data anddevelopers and the ability to make near term impact on Microsoft via the results of ourstudies. The work presented in this talk has been done by Chris Bird, Brendan Murphy,
Nachi Nagappan, myself, and many others who have visited our group over the past
years.

3

4

Project Management56Process Fragment Based Process Complexity with
Workflow Management Tables
Masaki Obana1 , Noriko Hanakawa2 , Norihiro Yoshida1 , Hajimu Iida1
1

Nara Institute Science and Technology
2

Hannan University

masaki-o@is.naist.jp, hanakawa@hannan-u.ac.jp, yoshida@is.naist.jp, iida@itc.naist.jp
process complexity based on the number of unplanned process
fragments, the number of simultaneous execution processes, andthe number of developers' groups. It can be used to visualize how
process complexity increases as actual development processproceeds.

ABSTRACTThe actual software development processes deviate from initialmodel planned at early stage. One of the reasons is that additional
processes get triggered by urgent changes of software
specifications. Such additional processes increase the complexityof the whole development process, and possibly decrease theproduct quality. In this paper, we propose a novel complexity
measure of software process, which based on the number ofprocess fragments, the number of simultaneous process fragments,
and the number of developers’ groups. Proposed processcomplexity is applied to two industrial projects in order to show
the usefulness of this measure. As a result, we found that thehigher value of process complexity indicates higher risk of
products' faults.

An aim of measuring process complexity is to prevent softwarefrom becoming low quality product. A process complexity isderived from a base process and process fragments. A baseprocess means an original process that was planned at the
beginning of a project. Process fragments mean additional andpiecemeal processes that are added to the base process on the wayof a project. Process fragment occurs by urgent changes ofcustomers’ requirement, or sudden occurrence of debugging faults.
Process fragments can be extracted from actual workflow
management tables which are popular in Japanese industrial
projects. We especially focus on simultaneous execution ofmultiple processes to model the process complexity. Simultaneous
execution of multiple processes is caused by adding process
fragments on the way of a project. Finally, we perform an
industrial case study in order to show the usefulness of processcomplexity. In this case study, we found that process complexity
indicated the degree of risk of post-release faults.

Categories and Subject Descriptors
D.2.9 [Software Engineering]: Management: software processmodelsGeneral Terms
Management, Measurement.

Keywords
Process complexity, risk management, a workflow management
table, change of customers’ demand.

Section 2 shows related work about process metrics, and risk
management. The process complexity is proposed in section 3.
Section 3 also describes how the proposed complexity would be
used in industrial projects. Case studies of two projects are shownin section 4. In section 5, we discuss a way of risk management
using the process complexity. Summary and future works aredescribed in Section 6.

1. Introduction
In software development projects, large gaps between planneddevelopment processes and actual executed development
processes exist. Even if a development team has originallyselected the waterfall model unplanned small processes are often
triggered as shown in the following examples.
i.

One activity of waterfall-based process is changed into newiterative process because of urgent specification changes.

ii.

Developers design GUI using a new prototype development
process at design phase.

iii.

In an incremental development process, developers correct
defects in the previous release while developers are
implementing new functions in current release.

2. Related Work
Many software development process measurement techniques
have been proposed. CMM [1] is a process maturity model by
Humphrey. Five maturity levels of organizations have been
proposed in CMM. When a maturity level is determined, various
values of parameters (faults rate in total test, test density, review
density) are collected. In addition, Sakamoto et al. proposed a
metrics for measuring process improvement levels [2]. The
metrics were applied to a project based on a waterfall processmodel. Theses process measurement metrics’ parameters include
the number of times of review execution and the number of faults
in the reviewed documents. The aim of these process
measurement techniques is improvement of process maturity of anorganization, while our research aims to measure processcomplexity of a project, not organization. Especially, changes ofprocess complexity in a project clearly are presented by ourprocess complexity.

That is, the waterfall-based process at planning time is often
gradually transformed into the combination of the original
waterfall-based process and several unplanned small processes(hereinafter referred to as process fragments). In consequence,
actual development processes are more complicated than plannedone (see also Figure 1).
In this paper, we firstly assume that complicated process
decreases product quality, and then propose a new metric for7

Many researches of process modeling techniques have been everproposed. Cugola et al. proposed a process modeling languagethat describes easily additional tasks [3]. Extra tasks are easily
added to a normal development process model using the modelinglanguage. Fuggetta et al. proposed investigated problems about
software development environments and tools oriented on various
process models [4]. These process modeling techniques are useful
to simulate process models in order to manage projects. However,these process modeling techniques make no mention of processcomplexity in a project.

Plan phase
Analysis

DesignImplement

Test

Analysis

DesignImplement

Test

A baseProcess

Analysis phase
Process
fragments
A part of function is next version.

A fragmentprocess
A part of function is developedby the prototype.
Design phase

In a field of industrial practices, Rational Unified Process (RUP)
has been proposed [5]. The RUP has evolved in integrating
several practical development processes. The RUP includes Spiralprocess model, use-case oriented process model, and risk oriented
process model. Moreover, the RUP can correspond to the latest
development techniques such as agile software development,
and .NET framework development. Although problems ofmanagement and scalability exist, the RUP is an efficient
integrated process for practical fields. The concept of the various
processes integration is similar to our process fragments
integration, while the RUP is a pre-planned integration processes.
The concept of our process complexity is based on more flexible
model considering changes of development processes during a
project execution. Our process complexity focuses on changes ofan original development process by process fragments, andregarded as a development processes change.

Analysis

DesignImplement

Test
Process
fragments

Re-design by requirement A coordinated design with othersystems is executed. later.
definition mistake.
Implement
phase

Analysis

DesignImplement

Test
Process
fragments

A part of function is re-designed andre-implemented by the requirement
definition mistake.

A part of function to the next
version for the delivery date.

Test phase

Garcia et al. evaluated maintainability and modifiability ofprocess models using new metrics based on GQM [6]. They focus
on additional task as modifiability. The focus of additional task issimilar to our concept of process complexity. Although theirresearch target is theoretical process models, and our researchtarget is practical development processes. In this way , there wasno studies for measuring complexity of process during a project aslong as we examined it. Therefore, the originality of our proposedcomplexity may be high.

Analysis

DesignImplement

Test

The re-design, the re-implement, andthe re-test are executed for the
performance improvement.

Process
fragments

Figure 1 A concept of process fragments
does not mean simple refinement of a base process, but rather may
separately executes from a base process execution.

3. Proposed Metrics Based on Process
fragment
3.1 Process fragment

Figure1 shows an example of process fragment. At the planningphase, it is a simple development process that consists of analysis
activity, design activity, implementation activity, and testing
activity. In many cases, because of insufficient information, amanager often makes a rough simple process (macro process)rather than a detailed process (micro process) [7]. However,information about software increases as a project progresses, andthe original simple process changes to more complicatedprocesses. In the case of Figure 1, at the analysis phase, an
unplanned prototype process was added to the original process
because of customers’ requests. As a result of analysis phase,
implementations of some functions were shifted to next version
development because of constraints of resources such as time, cost,and human. The process fragments were shown at the Figure1 as
small black boxes. In the design phase, because customers
detected miss-definitions of system specifications that were
determined in the previous analysis phase, a process for reworkingof requirement analysis was added to the development process.
Moreover, the manager shifted the development of a combination
function with the outside system when the outside system wascompleted. During the implementation phase, several reworks ofdesigns occurred. In the test phase, reworks of designs occurredbecause of low performance of several functions.

In software development, a manager makes a plan of a single
development process like a waterfall process model at the
beginning of a project. However, the planned single processusually continues to change until the end of the project. For
example, at the beginning of a project, a manager makes a plan
based on a waterfall process model. However the original process
is changed to an incremental process model because several
functions’ development is shifted to next version’s development.
Moreover, at the requirement analysis phase, prototyping process
may be added to an original process in order to satisfy customers’
demands. If multiple releases like an incremental process model
exist, developers have to implement new functions whiledevelopers correct detects that were caused in the previous
version’s development. In this paper, we call the original process“a base process”, we call the additional process “a process
fragment”. While original process is a process that was planned at
the beginning of a project, a process fragment is a process that is
added to the original process on the way of a project.
͆ Fragment” means piecemeal process. Process fragments are
simultaneously executed with a base process. Process fragment8

current
Activity

current

Apr.1 May 1 Jun.1 Jul.1

A
B
C

Activity

fragments have finished, the fragments’ executions may harmfully
influence products and process at the latter half of the project.
Therefore, the proposed complexity is accumulation of all process
fragments.

Apr.1 May 1 Jun.1 Jul.1

A
B

Base
process

The process complexity basically depends on three elements; thenumber of group of the i-th process fragment on time t:
Num_dev(t)i, the number of simultaneous processes of the i-th
process fragment on time t: L(t)i, and ratio of an executing periodof the i-th process fragment for the whole period of project time t:term(t)i. Granularity of group of developer(Num_dev(t)i) depends
on the scale of process fragments. If a process fragment is indetail of every hour, a group simply correspond to a person. If
process fragment is large such as design phase, a group unit will
be an organization such as SE group and programmer group. The
group of developers will be carefully discussed in future research.
The ratio of an executing period of the i-th process fragment for
the whole period of project time t (term(t)i) means impact scale ofa process fragment. If a process fragment is very large, forexample an executing period of the process fragment is almost
same as the whole period of a project, the process fragment will
influence largely the project. In contrast, if a process fragment isvery small, for example an executing period is only one day, theprocess fragment will not influence a project so much.

C
D
E
F

A table on Apr. 1

Added onMay 1

A table on Jun. 1

Figure 2 Extracting process fragments from
configuration of a workflow management table
Process fragments are caused by urgent customers’ requests,
design errors, combination with outside systems on the way ofdevelopment. Various sizes of process fragments exist. A small
process fragment includes only an action such as document
revision. A large process fragment may include more activities forexample, a series of developing activities; design activity,
implementation activity, and test activity.

3.2 Calculation of process complexity
3.2.1 Extracting process fragments

In short, when more and larger scale process fragments are
simultaneously executed, a value of process complexity becomeslarger. When fewer and smaller scale process fragments
simultaneously are executed, a value of process complexity
becomes smaller. Values of the parameters of equation (1) areeasily extracted from configuration management data of aworkflow management table.

Process complexity is calculated based on process fragments.
Process fragments are identified from a series of workflow
management table. That is a continuator revised along the project.
Figure 2 shows two versions of a workflow management table.
Each column means a date, each row means an activity. A seriesof A, B, C activities is a base process. D, E, F activities are added
to the base process on May 1. Therefore, D, E, F activities areprocess fragments. On Jun. 1, the base process and three process
fragments are simultaneously executed. In this way, process
fragments can be identified from configuration management of aworkflow management table. Difference between current version
and previous version of a workflow management table means
process fragments. Of course, the proposed complexity isavailable in various development processes such as an agile
process as long as managers manage process fragments in various
management charts.

3.3 Setting a base process and extracting
process fragments
At the beginning of a project, a base process is determined. If aplanned schedule is based on a typical waterfall process modelsuch as the base process in Figure 1, the parameters’ values ofprocess complexity are t=0, N(㸮)=1, Num_dev (㸮)=3 (SE groupdeveloper group, customer group), L( 㸮 )=1, and term ( 㸮 )=1.
Therefore the value of process complexity PC(0) =3.
As a project progresses, unplanned process fragments areoccasionally added to the base process at time t1. A manager
registers the process fragments as new activities to the workflow
management table. The manager also assigns developers to the
new activities. Here, we assume that the planned period of a baseprocess is 180 days. A manager adds two activities to theworkflow management table. The period of each additional
activity is planned as 10 days. Therefore the total number ofprocess N (t1) = 3, and the process complexity is calculated asfollows;

3.2.2 Definition of process complexity
Process complexity is defined by the following equation.
N(t )PC ( t )¦ ( Num _ dev(t )iu L( t ) i u term ( t ) i )i 1…..(1)

PC(t): process complexity on time tN(t): the total number of process on time t
Num_dev(t)i: the number of group of developers of the i-th process
fragment on time t
L(t)i: the number of simultaneous processes of the i-th process fragmenton time t. But the i-th fragment is eliminated from these(1) for i = 1 (a base process)x Num_dev(t1) = 3
x L(t1)1 = 3
x term(t1)1 = 180/180 = 1.0(2) for i = 2 (the first process fragment )x Num_dev(t1)2 = 1
x L(t1)2= 3
x term(t1)2 = 10/180 = 0.056(3) for i = 3 (the second process fragment )x Num_dev(t1)3 = 1
x L(t1)3 = 3
x term(t1)3= 10/180 = 0.056

multiplications in L(t).
term(t)i: ratio of an executing period of the i-th process fragment for thewhole period of the project on time t, that is, if term(t)i is near 1, a
executing period of the process fragment is near the whole periodof the project.

Basically, proposed process complexity is the accumulation of allprocess fragments including finished processes. The reason of theaccumulation is that the proposed complexity’s target is a wholeproject, not a spot timing of a project. For example, many process
fragments occur at the first half of a project. Even if the process

9

Time

Process1

Kick off

October
Requirement analysis

UI design

Programming

Combination test

System test

Operations test

Process1

Kick off

Requirement analysis

UI design

November
Programming

Combination test

System test

Operations test

Process2
Process1

Kick off

Requirement analysis

PrototypeUI design

Process2

Kick off

Requirement analysis

PrototypeUI design

Process2

Combination test

Programming

Two functions were redeveloped.

Process1

Four functions are made by the prototype.

The connect functions redeveloped.

Operations test

Process3

Analysis

Design Programming

Process4

Analysis

DesignProgramming

Prototype

January
System test

Combination test

Test

Programming Test

System test

February
Operations test

Process3

Analysis

DesignProgramming

Test

Process4

Analysis

DesignProgramming

Test

Process5 Analysis

DesignProgramming Test

Figure 3 A variation of development process of the HInT project
Finally, a value of process complexity at t=t1 can be calculated as
PC(t1) = 9.000 +0.168+ 0.168 = 9.336.

㻯㼛㼙㼜㼘㼑㼤㼕㼠㼥㻡㻜

Two functions werereworked at the
combination test phase.

㻠㻜㻟㻜

4.1 The HInT project㻞㻜

The first project’s name is HInT (Hannan Internet communication
Tool). The HInT project developed a web-based educational
portal system. The development began from October 2007, therelease of the HInT was April 2008. Because the workflow
management table was updated every week, 20 versions of theworkflow management table are obtained. At the beginning of the
project, the number of activities in the workflow table was 20. At
the end of the project, the number of activities reached to 123.
Each activity had a planned schedule and a practice result ofexecution. Figure 3 shows a rough variation of development
process of the project. At the beginning of the project, the shapeof the development process was completely a waterfall process.
However, at the UI design phase, a prototype process was added
to the waterfall process. In the prototype process, four trial
versions were presented to customers. At the combination test
phase, developers and customers found significant errors ofspecifications and two process fragments were added to thedevelopment process in haste. Reworks such as re-design, reimplement, and re-test for the specification errors continued until
the operation test phase. At the system test phase, an error of afunction connecting with an outside system occurred and a newprocess fragment was introduced to the development process. The
introduced process fragment consists of various activities such as
investigating network environments, investigating specification of
the outside system, and revising the programs. These activities
continued until the delivery timing.

Prototype process atthe design phase
The connect function
was revised at thesystem test phase.
㻞㻜㻜㻤㻛㻞

㻞㻜㻜㻤㻛㻝

㻞㻜㻜㻤㻛㻝

㻞㻜㻜㻣㻛㻝㻞

㻞㻜㻜㻣㻛㻝㻞

㻞㻜㻜㻣㻛㻝㻝

㻞㻜㻜㻣㻛㻝㻝

㻞㻜㻜㻣㻛㻝㻜

㻞㻜㻜㻣㻛㻝㻜

㻜㻞㻜㻜㻣㻛㻝㻜

㻝㻜㻞㻜㻜㻤㻛㻟

The process complexity has been applied to two practical projects.

㻞㻜㻜㻤㻛㻟

4. Application to Two Industrial Projects㻞㻜㻜㻤㻛㻞

In this way, the value of PC(t) at any value of time t can becalculated based on workflow management table.

Figure 4 Process complexity of the HInT project

4.2 The p-HInT project
The p-HInT is a lecture support system for large-scale lectureswith mobile terminals [8][9]. A base process of the p-HInT
project was an incremental development process. We released thep-HInT product four times from April 2008 through April 2010. A
development process of the each release included analysis phase,
design phase, implement phase, and test phase. At the first version
development, basic functions and infrastructure implementation
were planned in detail. However, the manager determined only
rough design of next versions’ functions. At the second version
development, new four functions were developed while thedevelopers fixed defects that had been introduced at the previous
version’s development. Of course, the debugging works were notplanned in the original schedule. At the third version development,
product refactoring was executed because the design of the
product became too complicated for introduction of new functions
and also for debugging works. At the fourth version development,
customers requested new functions that were not discussed at therequirement analysis phase. The customers said that the requested
new functions were more important than the functions that wereoriginally planned at the beginning of the project. At same time,
performance improvement work for some functions in theprevious releases was made at the fourth version development.

Figure 4 shows process complexity of the HInT project. At the
beginning of the project, the value of process complexity was very
low while the value of the process complexity increased as the
project progresses. In particular, after the system test phase, four
processes were simultaneously executed. Then processcomplexity increased to 44.167.

10

㻞㻡㻜

㻯㼛㼙㼜㼘㼑㼤㼕㼠㼥㻞㻜㻜㼂㼑㼞㼟㼕㼛㼚㻝
㻾㼑㼘㼑㼍㼟㼑

㻝㻡㻜

Process complexity㻣㻜㼜㻙㻴㻵㼚㼀㼂㻝
㻢㻜㼜㻙㻴㻵㼚㼀㻌㼂㻟㻡㻜㼂㼑㼞㼟㼕㼛㼚㻞
㻾㼑㼘㼑㼍㼟㼑

Process complexity 㸣㻝㻞㻜㼜㻙㻴㻵㼚㼀㼂㻝
㻝㻜㻜㼜㻙㻴㻵㼚㼀㻌㼂㻞㼜㻙㻴㻵㼚㼀㻌㼂㻟
㻤㻜
㻴㻵㼚㼀
㻢㻜

㼜㻙㻴㻵㼚㼀㻌㼂㻞
㻴㻵㼚㼀

㻠㻜
㻟㻜

㼂㼑㼞㼟㼕㼛㼚㻟
㻾㼑㼘㼑㼍㼟㼑

㻝㻜㻜

㻠㻜

㻞㻜
㻝㻜

㻡㻜

㻞㻜

Week

㻝

㻞㻜㻜㻥㻛㻢

㻞㻜㻜㻥㻛㻡

㻞㻜㻜㻥㻛㻠

㻞㻜㻜㻥㻛㻟

㻞㻜㻜㻥㻛㻞

㻞㻜㻜㻥㻛㻝

㻞㻜㻜㻤㻛㻝㻞

㻞㻜㻜㻤㻛㻝㻝

㻞㻜㻜㻤㻛㻥

㻞㻜㻜㻤㻛㻝㻜

㻞㻜㻜㻤㻛㻤

㻞㻜㻜㻤㻛㻣

㻞㻜㻜㻤㻛㻢

㻞㻜㻜㻤㻛㻡

㻞㻜㻜㻤㻛㻠

㻞㻜㻜㻤㻛㻟

㻞㻜㻜㻤㻛㻞

㻞㻜㻜㻤㻛㻝

㻞㻜㻜㻣㻛㻝㻞

㻞㻜㻜㻣㻛㻝㻝

㻞㻜㻜㻣㻛㻝㻜

㻜

Time

㻜

㻜
㻟

㻡

㻣

㻥

㻝㻝

㻝㻟

㻝㻡

㻝㻣

㻝㻥

Figure 6 Process complexitiesof the four project㻞㻝㻞㻟Figure 7 Patterns of growth ofprocess complexity

in the version 3 of the p-HInT, the value of process complexity
was 35.10.

Figure 5 Process complexity of the p-HInT project
The process complexity of the p-HInT project was measured until
June 2009. The number of items listed in the workflow table was
31. The items were divided into activities that were executable oneach week. Figure 5 shows a result of the measurement of processcomplexity.

On the first half of the third version development, the value ofprocess complexity did not increase because of a productrefactoring activity. Developers concentrated to the productrefactoring work. However, on the latter half of the third version,
problems such as low performance of the released functions andmiss data connection with outside systems occurred. Because
process fragments for fixing the problems were added, the valueof process complexity increased to 182.26.

In addition, each project has a feature of a process complexity
growth pattern. Figure 7 shows the patterns of the projects. A
maximum value of process complexity of each project is set to
100%. The value of process complexity of the version 1 of the pHInT increased suddenly on the first half of the project. In version
2 of the p-HInT, the value of complexity largely increased at two
timings; at the first half of the project, and at the end of the project.
In addition, in version 3 of the p-HInT, the value of complexity
gradually increased. The value of complexity of the HInT projectincreased at the latter half of the project. We call these patterns as"growth patter on early stage type", "growth patter on early andlate stage type, "growth patter smoothly type", and "growth patteron late stage type". The "growth patter on early stage type" often
occurs when a concept of development and development methods
are changed on the first half of a project. In the version 2 of the pHInT, debugging activities for the previous version’s faults were
set to highest priority activities on the first half of the project. The
process of the version 2 largely changed. Moreover, theunreasonable executions of the debugging activities caused
occurrences of new faults on the latter half of the project.
Therefore, addition of the debugging activities for the new faults
caused the increase of the value of process complexity on thelatter half of the project. On the other hand, in the HInT project,
developers presented the product demonstration to customers at
the system test phase. As a result, several specification errors andcustomers’ demand changes were clarified. Therefore, many
activities such as re-design, re-implement, re-test were added tothe development process. The process fragments such as the rework activities caused the increase of process complexity on thelatter half of the project.

5. Discussion

Therefore, we propose a way of evaluating project risk using thechanges of process complexity. The project risk is as follows;

At the begging of the project, the value of process complexity waslow (3.0) because the original development process is a simple
incremental process. At November 2007, because the original
process was divided into each process for each function, the valueof the process complexity increases to about 45.0.
At the release time of the first version, the value was 63.48. In thesecond version development, processes of improving performancefor the released functions were added to the original process. Thatis, developers had to revise the released functions while thedevelopers had to implement new functions as originally plannedat the beginning of the project. The value of the processcomplexity increased to 127.56.
At the test phase of the second version, some specification errors
came to light. For fixing the specification errors, several process
fragments were added and the value of process complexity
increased again.

We discuss usefulness of process complexity. Process complexity
has a role of capturing dynamic processes as a project progresses.
If the values of process complexity for the beginning of a project
and the end of a project don’t differ so much, we can interpret thatthe project was a stable because the project may have been
executed smoothly without large changes. In contrast, if a value ofprocess complexity largely increased, we can interpret that the
project was unstable due to large changes. Figure 6 showschanges of the values of process complexity of the two projects.
We regard each version of the p-HInT as one project. The fourth
version development of the p-HInT is excluded because all data
extracting the workflow management table was not prepared.

Risk

Rank u Variation………..(2)

Risk: Project Risk
Rank: growth patter patterns of process complexity:"growth patter smoothly type": 1,"growth patter on early stage type" : 2,"growth patter on late stage type" : 3,"growth patter on early and late stage type” : 4.
Variation: gap of values of process complexity between at the
beginning of a project and at the end of a project.

If a value of Risk is large, we can judge the project high risk. Rank
shows growth patter patterns of process complexity. The patternof "growth patter smoothly type" is most stable. The pattern of"growth patter on early stage type" is relatively stable. The reason
is that developers can cope with the process changes on the firsthalf of a project. Because the changes occur on the early stage,

It became clear change of process complexity of each project inFigure 6. Projects with large increase of process complexity areversion 1 and version 2 of the p-HInT project, and the HInT
project. Each increase value is 63.48, 47.28, and 41.17. In contrast,

11

developers have time for arranging their works. In contrast,
changes on the latter half of a project such as "growth patter onlate stage type" have high risk. Because developers have little
time for arranging their works, developers are confused insimultaneous executions of processes for the changes and an
original process. The pattern of "growth patter on early and latestage type” is worst. Because the additional works on the first halfof a project influence the works on the latter half of a project.
Managers may add the additional works in unplanned on the firsthalf of a project. In addition, Variation means a gap value ofprocess complexity between at the beginning of a project and at
the end of a project. Of course, a small value of Variation is better.
In this way, by calculating a value of Risk, we evaluate whether a
project is complicated or not. A detailed way of determining avalue of Rank will be discussed in future.

Risk
㻞㻜㻜
㻝㻡㻜

Specific gravity of failures㻝㻤㻥㻚㻝㻞

㻞㻜㻜㻝㻞㻢㻚㻥㻢

㻝㻞㻟㻚㻡㻝

㻝㻜㻜

㻝㻜㻜
㻡㻜

㻡㻜

㻟㻡㻚㻝

㻝㻡㻢

㻝㻡㻜
㻤㻞

㻤㻤
㻟㻣

㻜

㻜
㼜㻙㻴㻵㼚㼀㻌㼂㻝 㼜㻙㻴㻵㼚㼀㻌㼂㻞 㼜㻙㻴㻵㼚㼀㻌㼂㻟㻴㻵㼚㼀

Figure 8 Project risks of thefour projects㼜㻙㻴㻵㼚㼀㻌㼂㻝 㼜㻙㻴㻵㼚㼀㻌㼂㻞 㼜㻙㻴㻵㼚㼀㻌㼂㻟㻴㻵㼚㼀

Figure 9 Specific gravity of
failures of the four projects

6. Summary
We proposed process complexity model for risk management insoftware development. The process complexity is calculated byprocess fragments derived from a workflow management table. In
addition, project risk metric has been also proposed. The projectrisk is calculated by changes of process complexity during a
project. We applied the process complexity and the project risk
metrics to two industrial projects. As a result, the project risk
values have a weak relation with specific gravity of failures.
Therefore, managers can predict the quality of released productwhen the workflow management table is revised.

Figure 8 shows results of project risks of the four projects. The
project risk of the version 2 of the p-HInT is highest. The version
3 of the p-HInT has lowest risk. Figure 9 shows specific gravity of
failures occurred after release. The specific gravity failure is
calculated by the number of failure and importance level of failure.
The importance level means strength of impact on a product. As
Table 1, we classified the failures into five important levels; SS, S,
A, B, C. SS means most strong impact like system-down. C
means weakest impact like GUI’s improvement. The specificgravity of the failures is a value that multiplied the number of
failures and the importance level. In the calculation, we set up thata constant of SS is 5, a constant of S is 4, a constant of A is 3, aconstant of B is 2, and a constant of C is 1. For example, a valueof specific gravity of the p-HInT version 1 is calculated by “5*2 +4*3 + 3*19 +2*1 + 1*1”. The value is 82. In the same way, thespecific gravity of failure of the p-HInT version 2 is 88, one of pHInT version 3 is 37, and one of HInT is 156.

In future, we will apply the process complexity and the projectrisk metrics to many industrial projects. We will clarify the
relationships between project risk and specific gravity of failures.
Then, we will determine value of thresholds of the project risk.

7. REFERENCES[1] Humphrey Watts S.1989. Managing the software process.
Addison-Wesley Professional, USA.
[2] Sakamoto, K., Tanaka, T., Kusumoto, S., Matsumoto, K.,
and Kikuno T. 2000. An Improvement of Software Process
Based on Benefit Estimation. IEICE Trans. Inf. & Syst.(inJapanese ), J83-D-I(7), pp.740-748.
[3] Cugola, G. 1998. Tolerating Deviations in Process Support
Systems via Flexible Enactment of Process Models, IEEE
Transaction of Software Engineering, Vol. 24, No. 11,
pp.982-1001.
[4] Fuggetta, A. and Ghezzi, C. 1994. State of the art and open
issuesinprocess-centeredsoftwareengineering
environments, Journal of Systems and Software, Vol. 26, No.
1, pp.53-60.
[5] Kruchten, R. 2000. The Rational Unified Process, AddisonWesley Professional, USA.
[6] Garcia, F., Ruiz, F., Piattini, M. 2004. Definition andempirical validation of metrics for software process models,
Proceedings of the 5th International Conference Product
Focused Software Process Improvement (PROFES'2004),
pp.146-158.
[7] Obana, M., Hanakawa, N., Iida, H. 2010. Process complexity
metrics based on fragment process on workflow management
tables, Proceeding of the Software Engineering Symposium 
SES2010 (in Japanese), pp.89-96.
[8] Hanakawa, N., Yamamoto, G., Tashiro, K., Tagami, H.,
Hamada, S. 2008.
p-HInT: Interactive Educational
environment for improving large-scale lecture with mobile
game terminals, Proceedings of the16th International
Conference on Computers in Education (ICCE'2008),
pp.629-634.
[9] Hanakawa, N., Obana, M. 2010. Mobile game terminal based
interactive education environment for large-scale lectures,
Proceeding of the Eighth IASTED International Conferenceon Web-based Education (WBE2010)

Comparing Figure 8 with Figure 9, Spearman rank correlation
coefficient is 0.4. Therefore, we confirmed a weak relationshipbetween the values of project risk and the value of specific gravity
of failures. The version 3 of the p-HInT is not only lowest risk but
also lowest specific gravity of failure. In addition, if a value of the
project risk is high, the specific gravity of failure will be high.
That is, possibility of occurrence of strong impact failures
becomes high as a value of project risk is more. In the HInT
project, because customers suddenly requested new functions,many process fragments were added to the process on the latter
half of the project. A value of the project risk increased at thelatter half of the project. As a result, many significant failureswith SS rank occurred after release.
In this way, by the project risk we can predict possibility of failure
occurrences after release. A most useful feature of the project risk
is early prediction before start of executions of processes. The
prediction is possible when a workflow management table isrevised by adding process fragments. The possibility of the early
prediction in the project risk is most different from productmetrics. Product metrics is calculated by the already complicatedproduct. However, the project risk can prevent a project frombecoming high risk. It is useful for managers to judge whether
new process fragments are added.
Table 1 Failures after releases of the four projects
㻿㻿 㻿 㻭 㻮 㻯㼜㻙㻴㻵㼚㼀㻌㼂㼑㼞㼟㼕㼛㼚㻝 㻞 㻟 㻝㻥 㻝 㻝㼜㻙㻴㻵㼚㼀㻌㼂㼑㼞㼟㼕㼛㼚㻞 㻝㻜 㻢 㻠 㻝 㻜㼜㻙㻴㻵㼚㼀㻌㼂㼑㼞㼟㼕㼛㼚㻟 㻟 㻟 㻞 㻝 㻞㻴㻵㼚㼀㻝㻠 㻝㻞 㻝㻞 㻝 㻜12
            () 



* + ,              !
"#              !
"#              !
"#$%& &'#) $%& &'#$* &- ,%& &'#) )$   $ 

-       ..  )  )$- /0.0 "#              !
"#

))$  %&)- &&'#$$  %& &'#   $ #        $      $                   $ !   %                                    $      /)):              $        E                       
 $ !                                
$ !  H              $   

                                       !       "  !       #                                                   $     %      $               $                   $                                 &   '   (  #  )*+,     

@  $         $    
     /?+: I     $                          $  E                             A   $                      J         $               $          (                        I             #      -). /       :; "     <    
=>? /     :; @ $   @   "     <    "     "    (   (   

A   $            %        $  
     !               !          K     #        $ !          !                         !                 />:/?+:        J                                                    

! "                      $        

#$ %&'(%'&A              $                          B               /):/?C:/)*: '          /?.:                        />:/C:/?D:/)?:/)): E           $                                A           !            "  ! 
?

 @  &"F   G

13      #   H&HL   /M:                   
H&HL           $                                 #$   "


E                                                   $           /?>:%      $            $                    $                E       $   K N     /.:         K             $                                $ 



 

S



S



 



 

 

 

S

 

S

 

S

S

S

S

S



S



S

 



 

 

 

S

 

S

 

S

S

S

S

S



S



S

 

 

 

 

 

S

 

S

 

       
)



 ?





)#

B D#        Q      B O#   B                 
 $         

 


  Q       








D#







O#

-$ '(*%*%'&.'Q       $                @                 

%                 $ #                                       !                      /?):#
J          K          /?+:             
         />:  #, H                            /*  ?: A     R     K          ;  -, A       Q   $                     $           $ !             K 
$                 /C:/?D:/)): HK  $                       *#         K                $          $ ! K         $ ! K    E$          E        P   A   ?           $                         K   
#                     





-    A             &'       #          H   /?.:  &'        
&'                        &'               E          # $ I       K         #                     
$ !   E
         
%%"% /):         $                
                                     # 
  /?:    (            /)?:                $   -  -  #         ;)$ &*' +%%'&                        S     S         H  )         
H  D            H  O           H  M             H >      
   

"     

?#H    /?+:      GAH      B #                                                &     J             =   />:  "  !       E   K   $      B      #    #                 ), A   $            $           $ #             $         E  

14                               %            -$#   D#      $ 
   )      /?>:I          )E                    !   #   $             
 !  #  %     $       $                                                   $ /0       !                                  !                          G   !              E               !        O T                # E  !                                              -$)  0A         $         $ !  J            $ !         $ !
            HN     /.:       K    !                               $    V         $ !         K  $             K  $        

"  !                            !              !      A         E U   />:           E U ?#        )#             $       D#                   O#         
 $ #      M#                    D#     

E     #       #  DG      !    $        B ;!
O    







0 

 








>#

E  $                     "                       #V       $            $     (     Q         

Q 



 !

    











C#

  B  !            $         $       ?>M  M,     #
H           K  T  #      $            K  $       /C:/?D:%  K  $             K  $     
    $   $          I  B D#       
    $ ! K               T         $       K #        $           A          
  

 

M#

!            #   O   $        -$- &  1 1

H  K    "           B N  #;

 B ;         

)

)

D

"  !                     I   $  "  !   $ E     #      #                   @ !                    "  !                                    #"  !                  #         $              K          #  A    "  !    (                 
(                              ??    %                                                                              $  %             %       !                  $            $ E   )              K  ?#     $       )#       15

2$ 34%&
2$#   

2$-    4   (           ;

A                                              H&HL     /M:       H &   H  
L  H&HL#      $                   )*         $      ?.+. )**O        $    H                        ..              A             
/??: $                    # -                                   
H&HL         B   $     -   B 
        #H     $          /??: -   B    E   & 
          IW@L      #
E        $           E    M.D $ 2$) 5   ?-      B  %                    I                 $ #                       $ #)%                  DA    K                 ?)*E      B    B #          /?*:#                 B   

O

(              D M(                    >H ? M     ?*   E    ?*                       #(         ;

A                       # E  (  #   "    '   (  #/O: "  (  '       #/+: &   '   (  #/?O:?-      B  %                )(            ?
)* E         B            B               Q                 B ;#    Q 
 
 

      











+#

D

  Q  (                  ) 







.#

O

(                      Q  
Q







?*#

M

H ?O   ?*    Q  Q  *    Q  Q  Q  * Q      

6$ (*&%(%'&(        A   )  A   D A   )                             -               $ T    $                  $ T  K A               ?*       A   D                             V                   A  D                    A              #H      M,    K          

??#

G                                          J                      /D:/?*:"    ?              I            ?***           *      ?# H    
   ?      H                 /?M:       @ )M# /O:                  @ )M#                                 E   #     #            # (         )*+,      MD,   " 

16 )$5   '     
 1 

5  
$( 
$(  1       1 

5  
05( 
05(5  
0(5 
0(55  
%5( 
%5(     

V  

D>+*

?>*C ?>>.D,

M.M.,

.?)C,

M+*M,

)?*D>,

.?>.,

***,

V  !  D)M)

?DCO ?D+*C,

MM.+,

.CDM,

M>>C,

?+.M>,

+>D>,

CCM,

"  ! 

DMO.

?>*D ?>)O*,

>*O*,

.)>?,

M+O+,

)*C?C,

.)*?,

?)?,

DDC?

?>?? ?MO>.,

>)M*,

??*DM,

M++*,

)?>DM,..*M,

O>M,  !   -$'     
 1 

   5     1       1 

5  
$( 
$(

5  
05( 
05(5  
0(5 
0(55  
%5( 
%5(V  !  -   

O)+
*+*,

)DO
*+**

)+.,
**>

D>,
*+*,>?,
*OD?O,*C*

)*+,
**+

MD,
**>

"  ! -   

?D?
**+

O
*M+

OM,*+*

*+,*)M

?D,
*OD

*O,
*CO

D),
*?.

*D,
*+O

-   

D*.
*+*

O
*C*?)),
**>).,
*)*

?.?,
**>

*+,
*+M

>*,
*OD

CO,*CC  !   !                                          ?D,J         D),                   %          #    !                                          >,    $                            $                   $                              H&HL          
    "  !                  !                  E                                     
                                                 H&HL   #          A   "  !             H&HL     A        "  !                                  E  !                  !                                                !                

8$ !&'9* &A         H ( $  A -   V L  A     L 
   X H   &#  ))C***DO  )*?*       "  (   H   H    A     - V  %        

:$ ;&

/?: E  G  H   )***EH A (  E &  (      ! $      M ? DM>+                           $      $ A                    H&HL        $ /): &  &?.+?$      
J 

@  /D: &     G   ")**?             YE      %& !  '    $  ( ! OD ?O +>D+CD

7$ '&*(%'&                                    E                                                /O:  H - J  H  Z?.+>$     )      !& $ T

17

/M:    H &   H  L H&HL#)**OH&HL( ;&      H&HL

/?O: " K  X A
 " %K  =  VK  J?..O''   -  H ( " %& !     $  )C ? D?>/>: =  F =    &  F   ')**+E U;
@ H    E &  H ( ' ( +  $  DO O OC?
O+O

/?M: "[ \ =  F[    ")**ME H @ $ % I   H B  -   "  ' ( +  $  D? . 
CMOC>>

/C: =   "   ( @  $ '  H   ")**DE(  E G E  A 
B    &  @  +  '    !
           A   V   F )**D )D?)OM

/?>: % V "  E =   V &" A " =  A  "  =)**CA(  '   Y '    J  
E   ( '  +   '    !   &      ! $       & -. "   H  H   )**C D+O
D.)

/+: =    & " -  H @ G  H   ")**? E  H  ' "  + ' $  ?O+ D +?+M/?C: H  '  @  E?.++ G     ;              ' ( +  $  ?O ?) COD
CMC

/.: G   '  "  ")***# '&     
  !      ' #!   @  J /?*: G  )**M HX%K  &
( " Y +  '    ! $      & -('.    H )**M DO

/?+: H  X X =  & -)**+E(  E 
H ( ( % ( 
+       ! $      ! $      -/'. G K L   " )**+ )MD)/??: G    "   ()**>          H&HL-    ;      +   '    !   &     ! $      -'. ' F    & K H )**> CM+O/?.: H   "  H   ?..C(   $      ' ( +  $  
)D ?) CD>COD/?): "   ( "  H I   I  L  )**+          
 A      ;E   ( %& !    $  +? M >CD>.*/)*: H    =  I -?..M"  G E   ( H -   ( '( +  $  )? ) ?)>?DC/)?: A E A   &  &  E)**.I                    $  #!    D> C ?*D)M?*DDD

/?D: "   ( "  V    H)**DE'   E   W E  '    ( +   '    !   &     ! $      -'. '   H   )**D ?**?*.

/)):     I  'F  ?...E(  H
E   H ( (     ! $      O ) ?DM?M+18

A Survey of Public Datasets for Comparative Effort
Prediction Studies
Sousuke Amasaki

Tomoyuki Yokogawa

Okayama Prefectural University
111 Kuboki, Soja
Okayama, Japan

Okayama Prefectural University
111 Kuboki, Soja
Okayama, Japanamasaki@cse.oka-pu.ac.jp

t-yokoga@cse.oka-pu.ac.jp

ABSTRACT
Background: In the past survey, available public datasets for effort prediction study were listed up. In addition, using sufficientnumber of datasets and statistical tests was recommended for valid
comparative effort prediction study. Aim: This paper aims to identify a set of useful public datasets in terms of comparative effort
prediction study. Method: We sieved 38 public datasets listed in
the past study and PROMISE repository with respect to their availability, variety of features, and applicability of statistical practice.
Results: Only 12 public datasets were found to be available anduseful for simple models. For complex models 8 of 12 datasets
were specified. Among 8 datasets, only 3 datasets could keep original sample size and feature scale. This is because newly proposed
effort prediction methods usually try to improve performance byusing a multiple predictors and many datasets included categoricalfeatures with a level which was not found frequently. To obtain
more datasets, it was needed to adapt remained 5 datasets by casereduction, feature reduction, or numeric conversion. Conclusions:
It is difficult to compare multiple effort prediction methods with alarge number of public datasets along with good statistical practice.
However, selected datasets must be used for valid study at least.

Categories and Subject Descriptors

authors identified 31 datasets freely available to researchers frompublications.
One of criticisms for cost estimation papers is the small number ofdatasets used for evaluation. In [11], it is thus recommended to use
more public datasets shown in [14] and [3]. However, examinationof that listing is needed because comparative effort prediction study
was not considered in [14] and [3]. For example, existence of sizerelated metric such as lines of code(LOC), Function Points(FP),and effort record was not checked while those are essential information for models.
In this paper, we thus examined datasets listed in PROMISE repository[3] and [14] in order to specify common datasets available anduseful for comparative effort prediction study. As a result of examination, 12 datasets were found to be available and useful for simple
models. For complex models 8 of 12 datasets were specified. For
valid study, these datasets must be used at least.

2.

COMPARATIVE STUDY DESIGN

In comparative study, the followings must be considered.
• Simple and Complex models

D.29 [Software Engineering]: Cost Estimation• Benchmark

General Terms
Economics• Evaluation procedure

1. INTRODUCTION
Software cost estimation is still popular and important researcharea. To evaluate performance of a proposed software estimation
model construction method, datasets from real projects are used in
an experiment.
Although it is usually difficult to obtain a dataset from real projects,
we can find public datasets in the past study. There are many public
datasets available to researchers for model evaluation. PROMISE
repository[3] now serves 18 downloadable datasets. In [14], theMost of newly proposed software estimation model construction
methods utilized predictors in order to improve predictive performance. For example, feature weighting method[1] for Estimation
by Analogy(EbA)[18] was proposed to improve EbA by weighing
effects of predictors differently. We called models with multiple
features complex models in this paper. On the other hand, simple
models including only effort and size-related metric are also popular because it is easy to evaluate new methods and to use in caseof small sample size. Both types of models are important but theirrequirements for dataset are different. We thus selected datasets for
simple and complex models differently.
Benchmark is important for comparative study to evaluate how
well performance of a newly proposed model is. For this purpose,conventional models such as linear regression and EbA are often
used. In fact, most comparative study used one of these methods
as benchmark. Kitchenham recommended to confirm whether a
new proposed model outperformed linear regression at least[11].
Both models can be used for simple and complex models. In this19

study, we thus supported that linear regression and EbA are used as
benchmarks.

datasets.
In the following sections, remained 31 datasets were examined.

In comparative study, two types of cross-validation[7] were often used as evaluation procedure: leave-one-out and K-fold crossvalidation (CV). Leave-one-out CV can be used for smaller datasets
and it is preferable to K-fold CV in terms of variety of datasets. It
was also recommended in [11] because of its deterministic property.
On the other hand, K-fold CV is preferable to leave-one-out CV
in terms of evaluation reliability because an estimate obtained using leave-one-out CV has high variance, leading unreliable estimates[5]. Furthermore, some performance measures for effort estimation study cannot be differentiated when leave-one-out CV isadopted. In each round of leave-one-out CV, one test case is used
for calculating performance measures. That is, MMRE and MdMRE[17] of each test set always have identical value. In case of K-fold
CV, MMRE and MdMRE have different values if each test set has
more than 2 cases.
In [11], bootstrapping[6] was also recommended for performancecomparison based on statistical tests. On the other hand, Kohavi
recommended 10-fold CV after comparing to bootstrap[13]. Furthermore, property of resampling with replacement used in bootstrapping seems unsuitable for EbA. When a replicated project isplaced in both training and test sets, identical project is always selected as the nearest neighbor in EbA. If the number of neighbors
is set to 1 for EbA, EbA can estimate exact effort for replicatedprojects.
In this study, we considered 10 × 10-fold CV followed with t-test
as evaluation procedure in order to avoid inflated Type I error[4].

3. DATASETSIn this study, we examined published datasets served on PROMISE
repository[3] at November 2010 or listed in [14]. PROMISE repository serves datasets as readable text file which can include comments. From this repository, we selected datasets which contain acomment regarding information of projects or a citation they wereused. Datasets from [14] were collected from three journals: Transactions on Software Engineering, Information & Software Technology, and Journal of Systems & Software. After removing duplicates, we prepared an initial set of 38 datasets shown in Table
1.

4.

SELECTION FOR SIMPLE MODELS

Simple models usually estimate effort from single size-related metric such as KSLOC(kilo source LOC) and FP. Thus, size-related
metric must be included in a dataset. Sample size is also importantfor evaluation procedure and reliability of results.
Datasets were selected by evaluation criteria related to these points.

4.1

Effort and Size Records

Third and fourth columns of Table 1 show whether a dataset includes effort and size records. Here, unavailable 7 datasets in theprevious section were ignored and blanks were placed.
We found that 6 datasets did not include effort or size metric. ID
25, 26, and 27 did not include effort records. These datasets only
included KSLOC and size related-metrics such as the number ofscreens and were used to construct sizing models[15]. ID 5 included 3 features: actual effort, expert estimates, and company labels. ID 18 and 19 only included actual effort and experts estimates.
These datasets were not suitable for comparative effort estimation
study because an expert estimate was rarely used as the only predictor in a software estimation model.

4.2

Sample Size

In many situations, a fitted regression model is likely to be reliable
when the number of predictors p (the number of candidate predictors if using variable selection) is less than m/10 or m/20, wherem is total sample size[7]. Following this rule, at least, a dataset has
to include more than 10 projects in case of simple models. Furthermore, the size of training subsets becomes smaller when the sizeof training set in evaluation procedure is considered. In case of 10fold CV, sample size N must be N > 12 because 9/10 · N > 10
must be held.
To make performance measures such as MMRE and PRED(25)[17]
reliable, the size of test set must be larger as described in Section 2.
If the size of test set must be always equal or larger than 3, though
performance measure based on 3 results is still less precise and lessfine-grained, sample size must be equal or larger than 30 because
1/10 · N ≥ 3 must be held.

We then checked these datasets in terms of availability. First andsecond columns of Table 1 show whether a dataset can be obtained
actually from referenced papers in [14] or PROMISE repository. If
both columns of a dataset were marked as ‘N’, this dataset is noteasily available.

Fifth column of Table 1 shows whether a dataset has the sufficientnumber of projects. Here, we marked as ‘Y’ if a dataset had 30
or more projects; otherwise we marked as ‘N’ with its size. This
column indicated that 13 datasets were too small to be used in comparative effort prediction study.

We found that 7 datasets were not easily obtained from referenced
papers and PROMISE repository. ID 3, 4, and 30 were not shownin an original paper[2] cited in [14] and this paper said that an oldbook published in 1986 contains these datasets. We assessed ID
12 as unavailable though it was registered in PROMISE repository. This is because the number of features in this dataset was very
fewer than that described in a referenced paper[18]. The number offeatures was 29 according to [18] while dataset held on PROMISE
repository included only 6 features (excluding logarithm of effort
and size.) Referenced papers of the others did not have a dataset,a pointer to a paper, nor a book which may include corresponding

Finally, 12 public datasets were remained for comparative effort
prediction study of simple models.

20

5.

SELECTION FOR COMPLEX MODELS

Complex models assume multiple predictors. For instance, CART
selects and combines predictors so that a software effort estimation
model achieves higher prediction accuracy. Sample size is more
important for reliable evaluation of complex models. Furthermore,types of candidate predictors are also important. If there is discretevariables, using k-fold CV may be difficult.

ID
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Name
Abran-Robillard
Albrecht-Gaffney
Bailey-Basili
Belady-Lehmann
Shepperd-CartwrightBT-software-houses
BT-systemX
COCOMO
CSC
Desharnais
DoladoFinnishHastings-Sajeev
Heiat-Heiat
ICL
Jørgensen97-A
Jørgensen97-B
Jørgensen04-X
Jørgensen04-Y
Kemerer
MERMAID1
MERMAID2
Misic-Tesic
Miyazaki et al.1
Miyazaki et al.2
Miyazaki et al.3
Miyazaki et al.5
Moser-etal
Telecom
Wingfield
WSD1
WSD2
cocomonasa_v1
cocomo_sdr
Maxwell
NASA93usp05
usp05ft

Paper
Y
Y
N
N
Y
Y
Y
N
Y
N
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
N
N
N

Table 1: Public datasets from [14] and [3]
PROMISE Effort Size Sample Size
N
Y
Y
N(21)
Y
Y
Y
N(24)
N
N
N
Y
N
N
Y
Y
N(10)
N
Y
Y
N(10)
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
N(24)
N
N
Y
Y
N(8)
N
Y
Y
Y
N
Y
Y
N(10)
N
Y
Y
N(16)
N
Y
Y
N(20)
N
Y
N
N
Y
N
Y
Y
Y
N(15)
N
N
Y
Y
Y
N
Y
Y
N(7)
Y
Y
Y
Y
N
N
Y
N
N
Y
N
N
Y
N
Y
Y
Y
Y
Y
Y
N(18)
N
N
N
Y
Y
Y
Y
Y
Y
Y
N(12)
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y

We evaluated 12 datasets selected in the previous section by criteria
related to these points.

5.1 Multiple Features
Complex models utilize multiple features. Therefore datasets must
include multiple features for comparative effort prediction study.
Seventh column of Table 1 shows whether a dataset includes atleast one feature other than KSLOC and FP-variants. The number following ’Y’ indicates the number of features. For example,
Desharnais (ID 10) has 7 features because unadjusted and adjusted
FP were ignored and elements such as Transactions were counted.
Inappropriate features such as duration were also ignored.
As a result, all 12 datasets were remained.

5.2 Sample Size
Usually the size of datasets for complex models must be larger thanthat for simple models. For instance, if linear regression models

21

Multiple Features

Categorical

Y(16)
Y(2)
Y(7)

Y(16)
Y(2)
Y(1)

Y(1)

N

Y(1)

Y(1)

Y(7)

Y(1)

Y(1)

Y(1)

Y(15)

Y(15)

Y(22)
Y(20)
Y(14)
Y(12)

Y(22)
Y(20)
Y(14)
Y(12)

using size-metric and one feature as predictors are considered as
benchmark, a dataset must include more than 23 projects according
to the rule described in subsection 4.2.
Here, we left all 12 public datasets because they all have equal
or more than 30 projects and complex models based on linear regression with two predictors can be constructed at least. Althoughadditional samples might be needed for other models, we did notconsider that case here.

5.3

Categorical Features

Ten-fold CV can be applied to a dataset with categorical features if
each training subset includes all levels of each categorical featureincluded in corresponding testing subset. To satisfy this condition,
each level of a categorical feature must be found in more than N/10
records. If there is categorical feature with a level which was foundless than N/10 times, case reduction, feature reduction, or numeric
conversion is needed.

Moser-etal has one categorical feature representing project characteristics. If case reduction is applied, the size of this dataset becomes lower than 30. Concatenation of levels or numeric conversion cannot be applied because it is nominal scale. Feature reduction makes this dataset inappropriate for complex models because
it has only one feature.
CSC has two categorical features representing clients and projecttypes. Case reduction decreased the size of this dataset to 106. It
also reduced the numbers of client types and project types to 1 and
2, respectively. Thus, one categorical feature of project types wasremained. In [12], the authors considered simple models and used
several types of partitioning based on categorical features. On theother hand, we considered complex models and thus case reduction
was prefer to feature reduction.
In the second group, all datasets have multiple categorical featureswith a level which was found less than N/10 times. It is difficult
to adapt these datasets to comparative study by case reduction. Because there are many categorical features and case reduction basedon a categorical feature may influence on the other features. Furthermore, large portion of cases may be reduced for satisfying equal
to or more than N/10 cases for all levels. Concatenation and feature reduction are also difficult because there is no general way for
all possible effort estimation models. Thus, numeric conversion
was first considered for this group.
Most of categorical features in COCOMO(ID 8), cocomonasa_v1(ID 33), and NASA93(ID 36) were COCOMO or COCOMO II attributes. For these attributes, adjustment factors were often used in
the past study. With adjustment factors, 10-fold CV can be applied
to COCOMO and cocomonasa_v1.

22

As a result, 9 datasets were remained.

5.4

Detailed Examination

Desharnais, Heiat-Heiat, MERMAID2, and Miyazaki1 are preferable to the other datasets. Because they could keep original sample
size and feature scale. Here, we examined 4 datasets selected interms of usefulness and reliability. Since Desharnais has alreadybeen examined in [11], we examined other 3 datasets.

5.4.1

Heiat-Heiat dataset[8]This dataset came from projects completed for private and publicorganizations in Billings, Montana. There was no missing value.
These projects were selected on the basis of 6 attributes so that thedataset consists of homogeneous projects.
Figure 1 shows a scatterplot of FP and Effort for all 35 projects.
There are no apparent skewness, no heteroscedacity, and no outlier.

●

350

Miyazaki1 has one categorical feature representing companies. For
this dataset, case reduction is useless because there is no level withmore than N/10 records. Concatenation of levels or numeric conversion cannot be applied because this feature is nominal scale andthere is no knowledge of relations among companies. Thus, weconcluded that feature reduction is the best way for comparative
study. We think that this feature has too many levels for sample
size and is useless for estimation.

Many features in usp05 and usp05ft datasets(ID 37 and 38) werecategorical with many levels and it is difficult to determine the way
for adapting it to comparative study. Thus, we concluded that 10fold CV cannot be applied for these datasets.

●
●

●

300

CSC(ID 9), Miyazaki1(ID 24), and Moser-etal(ID 28) datasets haveone or two categorical features with a level which was found lessthan N/10 times. These categorical features were not used as predictor in original papers[12, 15, 16].

Maxwell(ID 35) dataset contains ordinal features and nominal features. Numeric conversion can be applied to ordinal features. Fourout of 7 nominal features have a level which was found less than
N/10 times. All of them were looked important and feature reduction was not preferable to case reduction. Case reduction based onthese features reduced the size of this dataset from 62 to 46. Threenominal features were also removed because they have only one
level in this reduced dataset.

●

●

●

●
●

●
●

●
● ●

50

●
● ●
●

●
●
●
●

●

●

●
●

250

In the first group, Desharnais(ID 10) and MERMAID2(ID 22) have
one categorical feature which satisfies the condition for levels. A
categorical feature of Desharnais dataset has three levels each ofwhich was found in more than one-eighths of records. A categoricalfeature of MERMAID2 dataset also has two levels each of which
was found in at least one-thirds of records. Thus, they can be used
for comparative study as is.

Effort• many categorical variables are included(6 datasets).

200• a few categorical variable(s) are included(5 datasets) andNASA93(ID 36) dataset included some nominal scale features having a level which was found less than N/10 times. For development mode among these features, case reduction is helpful because
this feature can satisfy N/10 rule by removing one level with 3
projects. Other nominal features were looked as less important forsoftware estimation models. In fact, they were not used in the past
study. Thus, we concluded that NASA93 dataset can be used after
numeric conversion, small case reduction, and feature reduction are
applied.

150

Eighth column in Table 1 shows whether a dataset includes categorical feature(s) and the number of them. Datasets having categoricalfeatures can be classified into two groups:

●

●

● ●
●

●

●

●

●

100

150

200

250

300

FP

Figure 1: Heiat-Heiat dataset

This dataset included a feature representing the sum of total number of corrected relationships at data stores and total number of30000Effort5.4.2 Miyazaki1 dataset[15]0This dataset came from 48 projects in 20 companies. There is no
missing value. All systems were newly developed except for one
project, in which more than half of its code was adapted from anexisting system[15].

N
N
E
E
EE
EE
E NE
E
E
E
EE E
E
E
0

N
N

N

N

500

1000

1500

AdjFP

Figure 3: Mermaid2 dataset (N = New projects, E = Enhancement Projects)

●

1500

N

E
10000

Thus, we concluded that this dataset was inappropriate for comparative effort prediction study in terms of variety of features.

50000

data flows which connect the system to external entities. Heiat etal. proposed this metric, called REIO, as alternative measure of
size such as LOC[8]. In fact, REIO and LOC were highly correlated (Spearman’s ρ is 0.93.) These facts imply that the difference
between simple and complex models will be subtle.

500

Effort1000

From these characteristics, we concluded this dataset was sometimes inappropriate for comparative effort prediction study. Because this dataset is too small to perform 10-fold CV when missing
values must be removed. We determined to leave this dataset.
Table 2 shows remained 8 datasets. Size and the number of features are from reduced datasets. Marks ‘FR’, ‘CR’, and ‘NC’ indicate feature reduction, case reduction, and numeric conversion,respectively.

●

●

0

●
●
●
●
●
●●
● ● ●● ●
●●●
●●
●●
● ●●
●
●●●●
● ●●
●●●●
●
●
●

0

●

●

●

100

200

300

400

As a result of examination, available 38 public datasets were decreased to 12 datasets for simple models and to 8 datasets for complex models.

KLOC

Figure 2: Miyazaki1 dataset

6.

Figure 2 shows a scatterplot of KLOC and Effort. There is one
outlier. There is skewness and small heteroscedacity. It looks as if
all projects except for the outlier have similar relationships between
size and effort.

DISCUSSIONIn subsection 5.3, several types of preprocessing was applied todatasets in order to adapt them to comparative effort prediction
study. These preprocessing have drawbacks.

Six continuous features in this dataset can be classified into threepairs with respect to their semantic similarity. Features of each pair
were also highly correlated. Even if a half of features were dropped
by a software estimation model construction method, the others still
remain.

The problems of case reduction are decreasing of size and changeof population. In this study all selected datasets have sufficientnumber of projects and the size was not problem. Case reductionin this study was based on categorical feature having a level which
was found less than N/10 times. Thus, population was changed but
it becomes more homogeneous. Homogeneity of dataset is considered as important property for effort estimation.

In this study, we concluded that the dataset may be useful for comparative effort prediction study because there is room for model
selection and optimization.

Most of reduced features in this study were due to case reduction.
Thus, dropped features seemed less important at least for reduced
homogeneous datasets.

5.4.3 MERMAID2 dataset[10]Although using adjustment factors is like a calibration, not construction of software estimation model, it was popular method for
dealing COCOMO drivers. Numeric conversion of ordinal scales
was also popular though this conversion implicitly assumes linear
relationship among levels. To manage these problems, feature subset selection may be useful. When all selected categorical featuressatisfy N/10 rule, these features can be used as is.

This dataset has one categorical feature representing new projects
and enhancement projects. Here, dividing the dataset into two
project types is not appropriate approach because the number of
new projects is less than 10.
There is two missing values on a categorical value. If raw FP is
used instead of adjusted FP, other 2 projects must also be removed
because of missing values. Figure 3 shows a scatterplot of adjusted
FP and Effort of 28 projects. The dataset has two outliers[10].
There is skewness and heteroscedacity.

23This study did not use technique concatenating levels though using
it instead of case reduction may also be useful. Because it is difficult to automate concatenation process because human decisionTable 2: Selected Datasets for Complex Models
No. Name
Size Features FR CR NC
8 COCOMO
63
16
X
9 CSC
106 1
X
X
10 Desharnais
77
7
22 MERMAID230
1
24 Miyazaki1
48
6
X
33 cocomonasa_v1 60
15X
35 Maxwell
46
19
X
X
X
36 NASA93
90
16
X
X
X

plays an important role as shown in [9].

7. CONCLUSION
In this paper, we examined the list of public datasets in [14] andPROMISE repository. As a result, we found 12 of 38 datasets were
only appropriate for comparative effort prediction study of simple
models. For complex models, this number was decreased to 8.
Among 8 datasets, only 3 datasets could keep original sample sizeand feature scale. We thus concluded that using one or two public
datasets is insufficient but there is not so many datasets suitable forcomparative study.
To make effort prediction study of complex models more comparable, we recommend to use those 3 datasets at first. In practicalview, CSC and MERMAID2 has too few features to evaluate complex models such as CART though. In this case, it is recommended
to consider remained 5 datasets next to Desharnais. The fact thatmany datasets need to be changed for use implies that repositories
like PROMISE should provide detailed and recommend preprocessing sequence for removing heterogeneity among comparative
studies.

8. REFERENCES[1] M. Auer and S. Biffl. Increasing the accuracy and reliabilityof analogy-based cost estimation with extensive projectfeature dimension weighting. In Proc. of the 2004
International Symposium on Empirical Software Engineering(ISESE’04), pages 147–155, 2004.
[2] R. D. Banker, H. Chang, and C. F. Kemerer. Evidence on
economies of scale in software development. Informationand Software Technology, 36:275–282, 1994.
[3] G. Boetticher, T. Menzies, and T. Ostrand. PROMISE
repository of empirical software engineering data.
http://promisedata.org/repository, West
Virginia University, Department of Computer Science, 2007.
[4] R. R. Bouckaert. Choosing between two learning algorithms
based on calibrated tests. In Proc. of 20th International
Conference on Machine Learning, pages 51–58, 2003.
[5] B. Efron. Estimating the error rate of a prediction rule:
Improvement of cross-validation. Journal of the American
Statistical Association, 78:316–330, 1983.
[6] B. Efron and R. J. Tibshirani. An Introduction to the
Bootstrap. Chapman & Hall, 1993.
[7] F. E. Harrel. Regression Modeling Strategies. Springer, 2001.
[8] A. Heiat and N. Heiat. A model for estimating efforts
required for developing small-scale business applications.
Journal of Systems and Software, 39:7–14, 1997.
[9] B. Kitchenham. A procedure for analyzing unbalanced

24

datasets. IEEE Trans. on Software Engineering,24(4):278–301, 1998.
[10] B. Kitchenham. The question of scale economies in software— why cannot researchers agree? Information and Software
Technology, 44(1):13–24, 2002.
[11] B. Kitchenham and E. Mendes. Why comparative effort
prediction studies may be invalid. In Proc. of PROMISE
Workshop 2009, 2009.
[12] B. Kitchenham, S. Pfleeger, B. McColl, and S. Eagan. An
empirical study of maintenance and development estimation
accuracy. Journal of Systems and Software, 64:57–77, 2002.
[13] R. Kohavi. A study of cross-validation and bootstrap for
accuracy estimation and model selection. In Proc. ofInternational Joint Conference on AI, pages 1137–1145,
1995.
[14] C. Mair, M. Shepperd, and M. Jørgensen. An analysis of data
sets used to train and validate cost. In Proc. of 1stInternational Workshop on Predictor Models in Software
Engineering(PROMISE’05), 2005.
[15] Y. Miyazaki and M. Terakado. Robust regression fordeveloping software estimation models. Journal of Systems
and Software, 27(1):3–16, 1994.
[16] S. Moser, B. Henderson-Sellers, and V. B. Mišić. Costestimation based on business models. Journal of Systems andSoftware, 49:33–42, 1999.
[17] D. Port and M. Korte. Comparative studies of the model
evaluation criterions MMRE and PRED in software costestimation research. In Proc. of 2nd International
Symposium on Empirical Software Engineering and
Measurement (ESEM’08), 2008.
[18] M. Shepperd and C. Schofield. Estimating software project
effort using analogies. IEEE Trans. on Software Engineering,23(11):736–743, 1997.

Faults and Verification

25

26

Reconstructing Fine-Grained Versioning Repositories with
Git for Method-Level Bug Prediction
Hideaki Hata

Osamu Mizuno

Tohru Kikuno

Dept.of Information Systems
Engineering
Osaka University
Osaka, Japan

Dept. of Information Science
Kyoto Institute of Technology
Kyoto, Japan

Dept.of Information Systems
Engineering
Osaka University
Osaka, Japanh-hata@ist.osaka-u.ac.jp

o-mizuno@kit.ac.jp

ABSTRACT
Change metrics derived from software repositories are known tobe effective for bug prediction. However, bug prediction basedon change metrics is limited to ﬁle-level because existing SCM
repositories stores ﬁle histories. To tackle ﬁne-grained (methodlevel) bug prediction, we try to establish ﬁne-grained versioning forrepositories. This paper presents an automatic technique constructing software repositories that can manage method histories. We utilize Git, one software conﬁguration management (SCM) systems,
and reconstruct ﬁne-grained versioning repositories from existing
repositories. We utilize these method-level versioning repositories
for method-level bug prediction with one eclipse related project.
The result shows that method-level change metrics are effective formethod-level bug prediction.

Categories and Subject Descriptors
D.2.7 [Software Engineering]: Distribution, Maintenance, andEnhancement—Version control; D.2.8 [Software Engineering]: Metrics; D.2.9 [Software Engineering]: Management—Software conﬁguration management

General Terms
Management

Keywords
ﬁne-grained versioning, software repository, bug prediction, methodlevel, Git, software evolution

1. INTRODUCTION
Software conﬁguration management (SCM) repositories have been
widely targeted for many research areas because of their rich product and process related data. Bug prediction is one of those researchareas. Many studies reported that change metrics derived from software repositories are effective for bug prediction [9, 11, 13, 20, 23,
25].

kikuno@ist.osaka-u.ac.jp

SCM systems can track the history of ﬁles and record, for example, existence periods, previous operations, and the reasons of
the changes. Therefore, change metrics, such as age, number ofchanges, bug ﬁxes are easily available from software repositories.
Previous studies conducted ﬁle-level bug prediction based on ﬁlehistories. In this paper, we tackle method-level bug prediction
based on method histories because we think it is easy to localize
bugs if the size of predicted modules is smaller.
From existing software repositories, seeing method histories is not
so easy. It is reported that though there are lots of refactorings,
which include the ﬁle relocations and method signature changes,
developers do not always leave in commit logs enough information
describing the changes they did in commit logs [21]. Since general repositories do not control method histories explicitly, we cannot obtain rich information for methods as for ﬁles. In this paper,
we prepare method-level version control repositories before miningchange metrics.
The concept of ﬁne-grained version control can be seen in Orwell [27] as method-level version control in object-oriented programming. Though several tools have been proposed to support
ﬁne-grained versioning, no such a tool has been actually integrated
within widely used SCM systems [6]. Since existing repositories
remain ﬁle-level versioning, what we have to do is converting existing repositories into ﬁne-grained versioning repositories. Though
there are some studies tackling extraction of method histories from
repositories, we try not only to extract method histories but also
to controlling method histories. For the purpose of converting, we
utilize Git, one SCM system.
Herraiz et al. presented software repository evolution from CVS,
Subversion to Git, and insisted that those improvements made repositories research friendly [16]. Bird et al. studied both promiseand peril of Git [3]. Though Git is known for the decentralization of source code management, we found that Git architectureis also useful for our purpose. “Directed acyclic graph (DAG),”“origin analysis,” and “revisionist history,” which are Git features
explained by Bird et al. [3], are also desirable for our purpose. In
addition, “snapshots” is also an important feature.
The rest of the paper is structured as follows. Section 2 introduces
four Git features, which is important for our purpose of reconstruction. Then, Section 3 presents a technique of reconstructing repositories from existing repositories based on Git. Section 4 shows usefulness of our ﬁne-grained versioning repositories with a case study
with an open source project. In addition, we utilize ﬁne-grained
versioning for method-level bug prediction. Section 5 introduces

27

(a) Difference-based storing (Subversion)

Figure 3: Retaking snapshots without changing commit DAG
own ancestor, the graph is a directed acyclic graph (DAG). Figure
2 shows an example of commit DAG. As shown in the example,
merging commits have more than one parent commit. As seen in
Figure 1 (b), each version of one ﬁle is stored in each snapshot separately. Each commit knows its snapshot. The orders or relationsof ﬁle versions are kept as DAG of commits relation.

(b) Storing snapshots (Git)
Figure 1: Differences in storing version data

2.3 Origin analysis

Figure 2: A subgraph of the Git DAG of commits leading up to
2.1 release 1 of Android
related work. Finally, we concluded this paper in Section 6.

As explained by Bird et al., Git tracks the ﬁle content history [3].
Therefore, ﬁles with the same content but different names or locations in the parent and child commits are found as a renamed or
moved ﬁle. This origin analysis is not limited to identical content
but also similar content. When ﬁle paths are changed, often ﬁlescontent are also modiﬁed. Even in such cases, Git is able to detect relationships between changes if the ﬁle contents are similar
enough. Origin analysis is conducted by checking that the amountof deletion of the original content and insertion of new content islarger than the threshold, which is set to 50% of the size of smallerﬁles (original or modiﬁed). Therefore, if deletion or insertion isless than 50%, two ﬁles in parent and child commits are detected
as moving or renaming. The threshold value can be changed. With
this feature, developer can recognize the renaming and moving.

2. GIT FEATURES
Recently Git attracted the attention of some researchers [3, 14, 16].
Though decentralization is one of the main characteristics compared to Subversion, there are some other distinctions. In this section, we introduce four Git features that are desirable for reconstructing ﬁne-grained versioning repositories.

2.1 Snapshots
One of the major differences between Git and Subversion (or CVS)
is the way it stores version data. Figure 1 shows an example ofversion control of three ﬁles. The ﬁle A is changed in version 2
and version 3, the ﬁle B is changed in version 3 and 4, and the ﬁle
C is changed in version 2. Subversion stores a set of ﬁles and thechanges made to each ﬁle over time, as illustrated in Figure 1 (a).
Figure 1 (b) shows how Git stores data. Git stores each snapshotof what all ﬁles look like at each commit. To be efﬁcient, if ﬁleshave not changed, Git does not store the ﬁles but stores links to theprevious ﬁles that have been already stored. What is import is thateach ﬁle is stored without begin connected to ﬁles in the previous
version.

2.2 DAGAs explained in [3], parent-child relation in commits is represented
as a graph in Git. A commit have more than or equal to one parent except for the initial commit. Since no commit cannot be its

28

2.4 Rewriting histories
Bird et al. introduced rewritable Git histories from the aspect of
DAG changing [3]. Git allows a repository owner to rearrange DAG
retaining each snapshot. This rewriting is commonly conducted tosimplify commit relation. In addition to that rewriting, it is also
possible to change snapshots by calling ﬁlter-branch command1 .
As shown in Figure 3, each snapshot can be changed retaining its
DAG. One of the uses of this rewriting is getting rid of a subset of
unnecessary ﬁles.

3. REPOSITORY RECONSTRUCTIONAs seen in Section 2, there are some features in Git different from
Subversion. We found that these features are desirable for our purpose of reconstructing ﬁne-grained versioning repositories. In thisSection, ﬁrst we show the fundamental idea of our approach, andthen we explain our technique and its implementation.

3.1 Idea
For ﬁne-grained (method-level) version control, what we have to do
is making each method controllable in repositories. Since repositories are able to control ﬁle histories, it is possible to control method1This command is not limited to changing snapshots retaining
DAG. It is also possible to change DAG.

moving of methods correspond to moving ﬁles. If a method isdeleted in a commit and reappear in later commit, Git can output
its history including disappearing periods. As described in Section
2.3, the origin analysis is conducted based on ﬁle content similarity.
Based on the threshold of content similarity, corresponding methods are identiﬁed. If two methods are highly similar, it is rational
to detect them as corresponding methods. However, they might
be corresponding methods in spite of not high similarity. In Section 4.1, we manually investigate whether found method origins arecorrect or not.
Figure 4: Retaking a snapshot for method storing

3.3 Implementation
Though existing repositories are not in Git system, it is possible
to convert them to Git repositories for most SCM systems, as explained as ninth promise of Git in [3]. Therefore we can concentrate on reconstruction of Git repositories. In this paper, we target
repositories of software written in Java language. As stated in Section 2.4, ﬁlter-branch command can be used for our purpose with a–tree-ﬁlter option. With this option, each snapshot appears in working directory and we can retake a snapshot after conducting someprocedure. For our purpose, we copy the methods before retaking
the snapshots. For locating the methods in Java ﬁles, we used thesource code analysis tool MASU2 , which is an open source tool. It
utilizes ANTLR for parsing source code [1].

4. ANALYSIS

Figure 5: File structure

histories if each method is stored as a ﬁle. As explained in Section
2.1, Git stores existing ﬁles at each commit as a snapshot. In addition, it is possible to retake snapshots without changing commit
history relation as stated in Section 2.4.
Figure 4 shows a concept of our approach. We retake each snapshot and replace it with a snapshot that includes additional method
ﬁles. This replacement enables us to control method histories liketraditional ﬁle histories. In original snapshot S , there exist originalﬁles F , G, and H . To retake snapshot S  , methods exist in each ﬁleare copied and stored as ﬁles. Each snapshot is retaken separately
without retaining ﬁle-level and method-level relations. Relations
between methods will be detected by Git origin analysis. If methods are moved or renamed, the corresponding methods should be
detected automatically, and method histories are managed by Git.

3.2 Technique
To retake the snapshots, we have to obtain the list of Java ﬁles thatexist in the original snapshots. From each Java ﬁle, exiting methods
are extracted and copied to individual ﬁles.
For storing method ﬁles, ﬁle structures are designed as Figure 5.
Here, we explain the case of Java language. Each java ﬁle is saved
as it is (ﬁle-name.java in Figure 5); if there are methods in the ﬁle,a directory named as the ﬁle’s name (ﬁle-name) is created; ﬁles ofmethods are saved in the directory; these ﬁles are named by their
method signatures. For simplicity, we limited to methods in toplevel classes in this paper. Methods in inner classes or anonymousclasses are ignored. In addition, abstract methods are not stored.
Directories and ﬁles in gray space of Figure 5 are newly preparedfor new snapshots.
Changes of method signatures correspond to ﬁle name changes and29

In this Section, we investigate the usefulness of ﬁne-grained versioning repositories. First, we examine whether Git origin analysis is useful for method-level origin analysis. Next, we conducted
method-level bug prediction based on method-level change metrics.
We targeted the WTP incubator project in Eclipse3 for the analysis.
This project is written in Java and is maintained with Git4 . We
cloned the Git repository on the 15th November, 2010.

4.1 Origin analysis evaluation
Git detects origins of methods after changing names or location of
the methods. When contents of methods are modiﬁed, detectionof corresponding methods is conducted by calculating similarityof potential method pairs. If similarity is greater than or equal tothreshold, the potential method pairs are detected as renamed methods as stated in Section 2.3. Users can change the threshold.
In this Section, we classify the method pairs according to similarity
values to see the impact of the threshold and investigate whether
detected method pairs seem to be correct or not. To know whether it
is correct matching or not, we investigate every matching methods
based on their method signatures and method paths. Since it is
difﬁcult to distinguish correct matches from mismatches perfectly,
we count the number of obvious mismatches.
As shown in Figure 6, the found method matches are classiﬁed
based on similarity values from 0% to 100% at 10% intervals. To
see the impact of the text size for the similarity calculation, theresult is summarized separately, (a) different lines (deletion lines+ insertion lines) is less than 10, and (b) the others. Dark graybars represent the numbers of detected obvious mismatches, andthe numbers of other matches are represented as light gray bars.
2

http://sourceforge.net/projects/masu/
http://www.eclipse.org/webtools/incubator/
4
http://git.eclipse.org/c/webtools/org.
eclipse.webtools.incubator.git/
3

Table 1: Change metrics collected in this paper
Metrics
NCHG
NFIX
NAUTH
AGE
ITVAL_{MAX, MIN}
LOC_{ADD, DEL}
NCHG_BUG_INTRO
NCHG_BUG_COPL(a) different lines < 10

NCHG_SIG
NCHG_FILE
NCHG_PCK
IS_FAULTY

Description
Number of individual changes
Number of bug ﬁxes
Number of authors
Existing period
Period of {maximum, minimum}
interval between commits
Some of {added, deleted} lines ofcode between ﬁrst and last revisions
Number of changes that is incommits that include bug-introducingchanges to other methods
Number of changes that is incommits that include changes to othermethods (change coupling)
Number of method signature changes
Number of ﬁle name changes
Number of package changes
Faulty or not. Dependent variable inprediction models

Table 2: Results of the 10-fold cross validation(b) different lines >= 10
Figure 6: Method matches based on a threshold

After checking manually, we found that automatic method matching based on Git works relatively well. There is a large number ofmethod pairs whose similarity value is 100%, which means thesemethods have been renamed without being modiﬁed. There are few
obvious mismatches if the similarity is greater than 20% whether
the number of different lines is less than 10 or not.
Though the results of origin analysis evaluation may depend on
projects or applications, line-based matching works relatively well
as shown by Kim [19]. We think this is because there should be
few cases where a newly created method is similar in content toa deleted method when the created and the deleted methods are
independent of each other. We think that developers tend to commit
simple changes, that is, the number of matching candidates is small
and matching pairs are easy to ﬁnd, not to confuse module histories.

4.2 Bug Prediction Based on Method History
Table 1 shows metrics we collected in this paper. The threshold oforigin analysis is the default value (50%). This means that methods
are regarded as newly created if most lines (>50%) are changed
when names or locations of the methods are changed. In this paper,
ﬁle-level bug prediction is also conducted to evaluate method-levelbug prediction. For ﬁle-level bug prediction, the same metrics inTable 1 are collected except for NCHG_SIG.
Whether modules are faulty or not is decided by using the SZZ
algorithm [26]. We obtained bug reports from the bug databases(Bugzilla) under the following conditions. The type of these faults
is “bugs”; therefore, these faults do not include any enhancements
or functional patches. The status of faults is either “resolved”, “veriﬁed”, or “closed”, and the resolution of faults is “ﬁxed”. This30(a) Method-level
Model
Recall Precision
Naive Bayes
0.704
0.030
Logistic regression
0.556
0.750
J48
0.593
1

F1
0.057
0.638
0.744

(b) File-level
Model
Recall Precision
Naive Bayes
0.778
0.073
Logistic regression
0.111
0.286
J48
0.389
0.875

F1
0.134
0.160
0.538

means that the collected faults have already been ﬁxed and havebeen resolved, and thus ﬁxed revisions should be included in theentire repository. The severity of the faults is either “BLOCKER”,“CRITICAL”, or “MAJOR” in order to remove trivial bugs. Herraiz categorized these severity categories as important and the others without ENHANCEMENT as non-important [15].
We conducted a 10-fold cross validation on a snapshot with the tag,v20090510. There are 4, 733 methods including 27 faulty methods, and there exist 698 ﬁles including 18 faulty ﬁles in this snapshot. We adopted the WEKA data mining toolkit [29] for building
bug prediction models. We built the following three models: naive
Bayes, logistic regression, and J48. For the evaluation of the experiment, we use three measures: Recall
PP( T PT+F), Precision( T PT+F), and F1 ( 2×recall×precision)5 .
NPrecall+precision
Table 2 shows the method-level and ﬁle-level results. The precision
values of naive Bayes are low because of lots of false positive. As
a result, F1 values of naive Bayes are low. Though the ratio offaulty modules per entire modules in method-level is lower thanﬁle-level, F1 values in method-level are superior to ﬁle-level fromlogistic regression and J48 models. Those two models achieved
more than 0.63 F1 values. Though bug prediction is conducted on
only one project, it seems that method-level change metrics may beeffective for method-level bug prediction.

5. RELATED WORK5
TP (true positive), TN (true negative), FP (false positive), FN(false negative)

Table 3: Comparison of method history analysis
Method/Tool/Authors
JDiff [2]C-REX [12]Origin analysis [8]Objective
detection of structural changes
assessment of change propagation tools
detection of merging & splitting

Relationship analysis target
namecalls, tokens
name, code metrics, calls

S. Kim et al. [19]UMLDiff [31]RefactoringCrawler [7]Weißgerber and Diel [28]SemDiff [5]LSdiff [17]
AURA [30]This paper

detection of renaming
detection of structural changes
detection of refactorings
detection of refactorings
recommending adaptive changes
detection & representation of systematic changes
detection of structural changes
ﬁne-grained versioning

name, code metrics, calls, text
name, structure
tokens, structure
name, structure, text
name, calls, structure
name, calls, structure
calls, text
text

Bug prediction based on change metrics. Graves et al.
have studied software change history and found that if modules
were changed many times, the modules tended to contain faults [9].
In addition, they found that if modules had not changed for one
year, the rate of the modules containing faults would be low. Nagappan and Ball examined code churn, which is a measure of theamount of code change, and showed that relative code churn ishighly predictive of defect density [22]. Ostrand et al. showedthat fault and modiﬁcation history of the ﬁle from previous release
could be predictive of faults in the next release of a system [23].
Schröter et al. have studied the correlation with past failure component history and failure-prone components [25]. They analyzed
SCM repositories and bug-tracking systems to extract the failurecomponent’s usage pattern, and applied some prediction models tocompare the results. Hassan and Holt computed the ten most faultprone modules after evaluating four heuristics: most frequently
modiﬁed, most recently modiﬁed, most frequently ﬁxed, and mostrecently ﬁxed [11]. Kim et al. have tried to predict the fault densityof entities using previous faults localities based on the observationthat most faults do not occur uniformly [20]. Ratzinger et al. investigated the interrelationship between previous refactoring andfuture software defects [24]. Hassan predicted faults using the entropy of code changes [10].

Method history analysis. Table 3 shows the related work about
method history analysis. JDiff is a tool of identifying differencesof Java structure between changes [2]. In method level, it identiﬁes
insertion and deletions. C-REX is a tool for C [12]. Its architecture
is similar to Git-base system in the point of origin analysis timing.
Method origins are found between snapshots. Merging and splitting are detected by origin analysis [8]. Detection of renames istackled in [19, 31]. Refactorings are detected in [7, 28]. SemDiff
detects adaptations to client programs [5]. LSdiff detects method
relations and infers change rules [17]. AURA can detect one-tomany and many-to-one change rules [30].
The main objective of the proposed system is not the identiﬁcationof method histories but the controlling the method histories. We intend to make the system a research platform like BEAGLE in origin
analysis [8]. Our Git-based system has the following advantages:• Method histories can be seen as SCM logs since data are
stored in Git repositories.
• Incremental reconstruction is possible. Additional new commits can be stored in reconstructed repositories.

31

StoringXML
BEAGLE repository(relational database)XML
Git• Relations between methods are not stored explicitly. Git does
not store relations between ﬁles, but stores snapshots andcommit DAGs. This enables us to see necessary method histories when we need. If we do not trace method histories beyond renames, Git show us the method histories before andafter renaming separately. This is important for a researchplatform because there should not be an unique relation between methods in two sequential commit. A method, which
is identiﬁed as merged method by origin analysis, may be
identiﬁed as many-to-one changed method by AURA, andmight be a clone of other methods. Though this paper evaluate the performance of Git origin analysis, it is possible
to identify different relations by different technique if we
replace Git origin analysis with them. Consequently, code
clone genealogies [18] and documenting program changes[4], for example, can be conducted on the system.

6. CONCLUSION
Lots of studies examined and investigated the power of change metrics mined from software repositories. File-level change metrics arewidely studied and those effectiveness is shown so far. To proceed
to method-level bug prediction, we choose to enrich repositories by
converting them to ﬁne-grained versioning repositories. This paper
contributes to the following:• A technique of reconstructing method-level version control
repositories from existing repositories is presented.
• Method-level change metrics are collected and used for bug
prediction on a real software project.

Since lots of SCM repositories can be converted to Git repositories, lots of existing repositories can be converted to ﬁne-grained
versioning repositories. Since reconstructed repositories are also
Git repositories, there is no additional labor to mine change metrics compared to natural Git repositories.
With reconstructed repositories, method-level change metrics canbe easily collected. In addition, bug location using the SZZ algorithm can be conducted on method-level. As a result, we canrealize method-level bug prediction. The result of one real software project shows that method-level change metrics are effective
for method-level bug prediction.

7. REFERENCES[1] Antlr. http://www.antlr.org/.

[2] T. Apiwattanapong, A. Orso, and M. J. Harrold. A
differencing algorithm for object-oriented programs. In Proc.
of 19th IEEE International Conference on Automated Softw.
Engg., pages 2–13, Washington, DC, USA, 2004. IEEE
Computer Society.
[3] C. Bird, P. C. Rigby, E. T. Barr, D. J. Hamilton, D. M.
German, and P. Devanbu. The promises and perils of mining
git. In Proc. of 6th International workshop on Mining
software repositories, pages 1–10, Washington, DC, USA,2009. IEEE Computer Society.
[4] R. P. Buse and W. R. Weimer. Automatically documenting
program changes. In Proc. of 25th IEEE/ACM International
Conference on Automated Softw. Engg., ASE ’10, pages
33–42, New York, NY, USA, 2010. ACM.
[5] B. Dagenais and M. P. Robillard. Recommending adaptivechanges for framework evolution. In Proc. of 30th
International Conference on Softw. Engg., pages 481–490,
New York, NY, USA, 2008. ACM.
[6] A. De Lucia, F. Fasano, R. Oliveto, and D. Santonicola.
Improving context awareness in subversion throughﬁne-grained versioning of java code. In Proc. of 9th
international workshop on Principles of software evolution,
pages 110–113, New York, NY, USA, 2007. ACM.
[7] D. Dig, C. Comertoglu, D. Marinov, and R. Johnson.
Automated detection of refactorings in evolving components.
In Proc. of 20th European Conference on Object-Oriented
Programming, pages 404–428. Springer, 2006.
[8] M. W. Godfrey and L. Zou. Using origin analysis to detectmerging and splitting of source code entities. IEEE Trans.
Softw. Eng., 31(2):166–181, 2005.
[9] T. L. Graves, A. F. Karr, J. Marron, and H. Siy. Predicting
fault incidence using software change history. IEEE Trans.
Softw. Eng., 26(7):653–661, 2000.
[10] A. E. Hassan. Predicting faults using the complexity of codechanges. In Proc. of 31st International Conference on Softw.
Engg., pages 78–88, Washington, DC, USA, 2009. IEEE
Computer Society.
[11] A. E. Hassan and R. C. Holt. The top ten list: Dynamic fault
prediction. In Proc. of 21st International Conference on
Softw. Maintenance, pages 263–272, Washington, DC, USA,2005. IEEE Computer Society.
[12] A. E. Hassan and R. C. Holt. Replaying development history
to assess the effectiveness of change propagation tools.
Empirical Softw. Engg., 11:335–367, September 2006.
[13] H. Hata, O. Mizuno, and T. Kikuno. Fault-prone module
detection using large-scale text features based on spamﬁltering. Empirical Softw. Engg., 15(2):147–165, 2010.
[14] L. Hattori and M. Lanza. Mining the history of synchronouschanges to reﬁne code ownership. In Proc. of 6thInternational workshop on Mining software repositories,
pages 141–150, Washington, DC, USA, 2009. IEEE
Computer Society.
[15] I. Herraiz, D. M. German, J. M. Gonzalez-Barahona, and
G. Robles. Towards a simpliﬁcation of the bug report form in
eclipse. In Proc. of 5th International workshop on Mining
software repositories, pages 145–148. ACM, 2008.
[16] I. Herraiz, G. Robles, and J. M. Gonzalez-Barahona.
Research friendly software repositories. In Proc. of the joint
international and annual ERCIM workshops on Principles ofsoftware evolution (IWPSE) and software evolution (Evol)workshops, pages 19–24, New York, NY, USA, 2009. ACM.
[17] M. Kim and D. Notkin. Discovering and representing

32

systematic code changes. In Proc. of 31st International
Conference on Softw. Engg., pages 309–319, Washington,
DC, USA, 2009. IEEE Computer Society.
[18] M. Kim, V. Sazawal, D. Notkin, and G. Murphy. An
empirical study of code clone genealogies. In Proc. of the10th European software engineering conference held jointlywith 13th ACM SIGSOFT international symposium on
Foundations of software engineering, pages 187–196, New
York, NY, USA, 2005. ACM.
[19] S. Kim, K. Pan, and E. J. Whitehead, Jr. When functions
change their names: Automatic detection of origin
relationships. In Proc. of 12th Working Conference on
Reverse Engineering, pages 143–152, Washington, DC,
USA, 2005. IEEE Computer Society.
[20] S. Kim, T. Zimmermann, E. J. Whitehead Jr., and A. Zeller.
Predicting faults from cached history. In Proc. of 29th
International Conference on Softw. Engg., pages 489–498,
Washington, DC, USA, 2007. IEEE Computer Society.
[21] E. Murphy-Hill, C. Parnin, and A. P. Black. How we refactor,
and how we know it. In Proc. of 31st International
Conference on Softw. Engg., pages 287–297, 2009.
[22] N. Nagappan and T. Ball. Use of relative code churnmeasures to predict system defect density. In Proc. of 27th
International Conference on Softw. Engg., pages 284–292,
2005.
[23] T. J. Ostrand, E. J. Weyuker, and R. M. Bell. Predicting thelocation and number of faults in large software systems.
IEEE Trans. Softw. Eng., 31(4):340–355, 2005.
[24] J. Ratzinger, T. Sigmund, and H. Gall. On the relation of
refactorings and software defect prediction. In Proc. of 5thInternational workshop on Mining software repositories,
pages 35–38. ACM New York, NY, USA, 2008.
[25] A. Schröter, T. Zimmermann, and A. Zeller. Predicting
component failures at design time. In Proc. of ACM/IEEE
international symposium on Empirical software engineering,
pages 18–27, New York, NY, USA, 2006. ACM.
[26] J. Śliwerski, T. Zimmermann, and A. Zeller. When dochanges induce ﬁxes? (on Fridays.). In Proc. of 2ndInternational workshop on Mining software repositories,
pages 24–28, 2005.
[27] D. Thomas and K. Johnson. Orwell: A conﬁguration
management system for team programming. In Proc. of 3rd
conference on object oriented programming languages andapplications, pages 135–141. ACM, 1988.
[28] P. Weißgerber and S. Diehl. Identifying refactorings fromsource-code changes. In Proc. of 21st IEEE/ACM
International Conference on Automated Softw. Engg., pages
231–240, Washington, DC, USA, 2006. IEEE Computer
Society.
[29] I. H. Witten and E. Frank. Data Mining: Practical Machine
Learning Tools and Techniques. Morgan Kaufmann, 2
edition, 2005.
[30] W. Wu, Y.-g. Guéhéneuc, G. Antoniol, and M. Kim. AURA:
A hybrid approach to identify framework evolution. In Proc.
of 32nd International Conference on Softw. Engg., 2010.
[31] Z. Xing and E. Stroulia. UMLDiff: an algorithm forobject-oriented design differencing. In Proc. of 20th
IEEE/ACM International Conference on Automated Softw.
Engg., pages 54–65, New York, NY, USA, 2005. ACM.

Reachability Analysis of Probabilistic Timed Automata
Based on an Abstraction Reﬁnement Technique
Takeshi Nagaoka, Akihiko Ito, Toshiaki Tanaka, Kozo Okano, Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University{t-nagaok,a-ito,tstanaka,okano,kusumoto}@ist.osaka-u.ac.jp

ABSTRACT
Model checking techniques are considered as promising techniquesfor veriﬁcation of information systems due to their ability of exhaustive checking. Well-known state explosion, however, mightoccur in model checking of large systems. In order to avoid it, several abstraction techniques have been proposed. Some of them arebased on CounterExample-Guided Abstraction Reﬁnement (CEGAR) technique proposed by E. Clarke et al.. This paper proposesa reachability analysis technique for probabilistic timed automata.
In the technique, we abstract time attributes of probabilistic timed
automata by our abstraction technique proposed in our previous
work. Then, we apply probabilistic model checking to the generated abstract model which is just a markov decision process (MDP)
with no time attributes. Also, our technique can produce a counterexample as a set of paths when a given model does not satisfy a
speciﬁcation. The paper also provides some experimental results
on applying our method to IEEE 1394, FireWire protocol. Experimental results show our algorithm can reduce the number of states
and total execution time dramatically compared to one of existing
approaches.

Keywords
Probabilistic Timed Automaton, CEGAR, Model Checking, Realtime System, Formal Veriﬁcation

1. INTRODUCTION
Model checking[1] techniques are considered as promising techniques for veriﬁcation of information systems due to their abilityof exhaustive checking. For veriﬁcation of real-time systems suchas embedded systems, timed automata are often used. On the other
hand, probabilistic model checking[2, 3, 4] can evaluate performance, dependability and stability of information processing systems with random behaviors. In recent years, probabilistic models with real-time behaviors, called probabilistic timed automata(PTA) attract attentions. As well as traditional model checking
techniques, however, state explosion is thought to be a major hurdle
for veriﬁcation of probabilistic timed automata.

Clarke et al. proposed an abstraction technique called CEGAR(CounterExample-Guided Abstraction Reﬁnement)[5]. In the CEGAR technique, we use a counter example (CE) produced by amodel checker as a guide to reﬁne abstracted models. In [6], wehave proposed an abstraction algorithm for timed automata basedon CEGAR. In this algorithm, we generate ﬁnite transition systems
as abstract models where all time attributes are removed. The reﬁnement modiﬁes the transition relations of the abstract model sothat the model behaves correctly even if we don’t consider the clock
constraints.
This paper proposes a reachability analysis technique for probabilistic timed automata. In the technique, we abstract time attributes of probabilistic timed automata by applying our abstraction technique for timed automata proposed in [6]. Then, we apply
probabilistic model checking to the generated abstract model which
is just a markov decision process (MDP) with no time attributes.
The probabilistic model checking algorithm calculates summationof occurrence probability of all paths which reach to a target state
for reachability analysis. For probabilistic timed automata, however, we have to consider required clock constraints for such paths,
and choose the paths whose required constraints are compatible.
Since our abstract model does not consider the clock constraints,
we add a new ﬂow where we check whether all paths used for probability calculation are compatible. Also, if they are not compatible,
we transform the model so that we do not accept such incompatible
paths simultaneously.
This paper also provides some experimental results on applying
our method to some examples. Experimental results show our algorithm can reduce the number of states and total execution time
dramatically compared to one of existing approaches.
Several papers including Paper [2, 3, 4] have proposed probabilistic
model checking algorithms. These algorithms, however, don’t provide CEs when properties are not satisﬁed. Our proposed method
provides a CE as a set of paths based on k-shortest paths search.
This is a major contribution of our method. The proposed method
also performs model checking considering compatibility problem.
Few approaches resolve the compatibility problem. Our approachalso shows the efﬁciency via performing experiments.
The organization of the rest paper is as follows. Sec.2 provides
some deﬁnitions and lemmas as preliminaries. Sec.3 describes our
proposed abstraction technique for the probabilistic timed automaton. Sec.4 gives some experimental results. Finally, Sec.5 concludes the paper and gives future works.

33

2. PRELIMINARY
2.1 Clock and ZoneLet C be a ﬁnite set of clock variables which take non-negative realvalues (R≥0 ). A map ν : C → R≥0 is called a clock assignment.
The set of all clock assignments is denoted by RC≥0 . For any ν ∈
and
d
∈
R
we
use
(ν
+
d)
to
denotetheclock
assignmentRC≥0≥0deﬁned as (ν + d)(x) = ν(x) + d for all x ∈ C. Also, we use r(ν)
to denote the clock assignment obtained from ν by resetting all of
the clocks in r ⊆ C to zero.
D EFINITION 2.1. Syntax and semantics of a differential inequality E on a ﬁnite set C of clocks is given as follows:
E ::= x − y ∼ a | x ∼ a,where x, y ∈ C, a is a literal of a real number constant, and∼∈ {≤, ≥, <, >}. Semantics of a differential inequality is thesame as the ordinal inequality.
D EFINITION 2.2. Clock constraints c(C) on a ﬁnite set C ofclocks is deﬁned as follows: A differential inequality in on C is anelement of c(C). Let in1 and in2 be elements of c(C), in1 ∧ in2
is also an element of c(C).
A zone D ∈ c(C) is described as a product of ﬁnite differential
inequalities on clock set C, which represents a set of clock assignments that satisfy all the inequalities. In this paper, we treat a zone
D as a set of clock assignments ν ∈ RC
≥0 (For a zone D, ν ∈ Dmeans the assignment ν satisﬁes all the inequalities in D).

2.2 Probability Distribution

A discrete probability distribution on a ﬁnite set Q is given as
the function μ : Q → [0, 1] such that Σq∈Q μ(q) = 1. Also,
support(μ) is a subset of Q such that ∀q ∈ support(μ).μ(q) > 0
holds.

A Markov Decision Process (MDP)[7] is a markov chain with nondeterministic choices.
D EFINITION 2.3. A markov decision process M DP is 3-tuple(S, s0 , Steps), where S is a ﬁnite set of states, s0 ∈ S is an initialstate, and Steps ⊆ S × A × Dist(S) is a probabilistic transition
relation where Dist(S) is a probability distribution over S.
In our reachability analysis procedure, we transform a given PTA
into a ﬁnite MDP, and perform probabilistic veriﬁcation based on
the Value Iteration[8] technique.











ҍ



Figure 1: An Example of a PTA

2.4

Timed Automaton

D EFINITION 2.4. A timed automaton A is a 6-tuple (A, L, l0 ,C, I, T ), where A is a ﬁnite set of actions, L is a ﬁnite set of locations, l0 ∈ L is an initial location, C is a ﬁnite set of clocks,
I ⊂ (L → c(C)) is a mapping from locations to clock constraints,
called a location invariant, and T ⊂ L × A × c(C) × R × L isa set of transitions, where c(C) is a clock constraint, called guards
and R = 2C is a set of clocks to reset.
D EFINITION 2.5. Given a timed automaton A = (A, L, l0 , C,
I, T ), let S ⊆ L × RC
≥0 be a set of whole states of A . The initial state of A shall be given as (l0 , 0C ) ∈ S. For a transition(l1 , a, g, r, l2 ) ∈ T , the following two transitions are semanticallydeﬁned. The former one is called an action transition, while thelatter one is called a delay transition.
a,g,r

l1 −→ l2 , g(ν), I(l2 )(r(ν))
a(l1 , ν) ⇒ (l2 , r(ν)),∀d ≤ d I(l1 )(ν + d )d(l1 , ν) ⇒ (l1 , ν + d)

D EFINITION 2.6. For timed automaton A = (A, L, l0 , C, I, T ),an inﬁnite transition system is deﬁned according to the semantics
of A , where the model begins with the initial state.

2.5

2.3 Markov Decision Process

Probabilistic Timed Automaton

A PTA is a kind of a timed automaton extended with probabilistic
behavior. In the PTA, a set of probabilistic distributions is usedinstead of a set T of discrete transitions on the timed automaton.
D EFINITION 2.7. A probabilistic timed automaton P T A is a
6-tuple (A, L, l0 , C, I, prov), where A is a ﬁnite set of actions, L
is a ﬁnite set of locations, l0 ∈ L is an initial location, C is a ﬁnite set of clocks, I ⊂ (L → c(C)) is a location invariant andprob ⊆ L × A × c(C) × Dist(2C × L) is a ﬁnite set of probabilistic transitions, where c(C) represents a guard condition, andDist(2C × L) represents a ﬁnite set of probability distributions p.
The Distribution p(r, l) ∈ Dist(2C ×L) represents the probabilityof resetting clock variables in r and also moving to the location l;

2.3.1 Adversary
An MDP has non-deterministic transitions called action. To resolve
the non-determinism, an adversary is used. The adversary requires
a ﬁnite path on an MDP, and decides a transition to be chosen at thenext step.

Figure 1 shows an example of a PTA. In the ﬁgure, from the location a, the control moves to the location b with the probability
0.5 and also moves to the location c letting the value of the clock x
reset to zero with the probability 0.5.

2.3.2 Value Iteration
A representative technique of model checking for an MDP is Value
Iteration[8]. The Value Iteration technique can obtain both of maximum and minimum probabilities of reachability and safety properties, respectively. At each state, Value Iteration can select an appropriate action according to the property to be checked. Therefore,
the technique can obtain the adversary as well as the probability.

34

D EFINITION 2.8. Semantics of a probabilistic timed automaton
P T A = (A, L, l0 , C, I, prob) is given as a timed probabilistic
system T P SP T A = (S, s0 , T Steps) where, S ⊆ L × RC is a setof states, s0 = (l0 , 0C ) is an initial state, and T Steps ⊆ S ×
A ∪ R≥0 × Dist(S) is composed of action transitions and delaytransitions, where 
a) action transition
if a ∈ A and there exists (l, a, g, p) ∈ prob such that g(ν)
and I(l )(r(ν)) for all (r, l ) ∈ support(p), ((l, ν), a, μ) ∈T Steps where for all (l , ν  ) ∈ S
p(r, l ).
μ(l , ν  ) =  
   ƚƌƵĞ 

  

  

r⊆C∧ν  =r(ν)ĨĂůƐĞ
 



b) delay transition
if d ∈ R≥0 , and for all d ≤ d, I(l)(ν + d ), ((l, ν), d, μ) ∈T Steps where μ(l, ν + d) = 1.

Figure 2: A General CEGAR Technique 
In this paper, using a location l and a zone D, we describe a set ofsemantic states as (l, D) = {(l, ν) | ν ∈ D}.

ƚƌƵĞ 

D EFINITION 2.9. A path ω with length of n on a timed probabilistic system T P SP T A = (S, s0 , T Steps, L ) is denoted as follows.
d ,μ

d ,μ

0 0
1 1
(l1 , ν1 ) −→...
ω = (l0 , ν0 ) −→dn−1 ,μn−1−→  
        

(ln , νn )   

, where (li , νi ) ∈ S for 0 ≤ i ≤ n and ((li , νi ), di , μ) ∈ T Steps∧((li , νi + di ), 0, μi ) ∈ T Steps ∧ (li+1 , νi+1 ) ∈ support(μi ) for0 ≤ i ≤ n − 1.
For model checking of a probabilistic timed automaton, we extract
a number of paths and calculate a summation of their occurrence
probabilities in order to check the probability of satisfying a given
property. The important point is that we have to choose a set ofpaths which are compatible with respect to time elapsing.
L EMMA 2.1. If a set Ω of paths on a timed probabilistic system
T P SP T A satisﬁes the following predicate isCompatible, then allof the paths over Ω are said to be compatible.
isCompatible(Ω) =
⎧
 α
β
⎪
(li = liβ ∧ dα
⎪true, if ∀i ≤ min(Ω)
i = di )⎪⎪⎪βαω ,ω ∈Ω⎪⎪⎪∧ω α =ω β
⎪
⎪
⎪
⎪
or
there
existsi≤ min(Ω) such that
⎪
⎪

 α β
⎪
β
⎨
(li = li ∧ dα=dβi ∧ (ljα= ljβ ∧ dαi
j = dj )),j≤iω α ,ω β ∈Ω⎪⎪∧ω α =ω β
⎪
⎪

⎪
⎪
⎪
and also
isCompatible(Ω )
⎪
⎪
⎪

Ω
⎪
Ω ∈2 ∧⎪⎪
Ω =Ω∧|Ω |≤2⎪⎪⎩false, otherwise.
In Lemma2.1, we give the predicate isCompatible for a set Ω ofpaths on a timed probabilistic system. In the lemma, we let pathsin Ω be compatible if there is no contradiction with respect to time
elapsing at the branching point of all the paths in Ω, and also if
the compatibility is kept for every subset of Ω which contains morethan two paths.

2.6 CounterExample-Guided Abstraction Reﬁnement
2.6.1 General CEGAR TechniqueSince model abstraction sometimes over-approximates an originalmodel, we may obtain spurious CEs which are infeasible on the35

  ĨĂůƐĞ 



  

Figure 3: Our CEGAR Technique for Reachability Analysis of
a Probabilistic Timed Automaton
original model. Paper[5] gives an abstraction reﬁnement framework called CEGAR (CounterExample-Guided Abstraction Reﬁnement) (Fig.2).
In the algorithm, at the ﬁrst step (called Initial Abstraction), it generates an initial abstract model. Next, it performs model checking
on the abstract model. In this step, if the model checker reports thatthe model satisﬁes a given speciﬁcation, we can conclude that theoriginal model also satisﬁes the speciﬁcation, because the abstract
model is an over-approximation of the original model. If the model
checker reports that the model does not satisfy the speciﬁcation,
however, we have to check whether the CE detected is spurious or
not in the next step (called Simulation). In the Simulation step, if
we ﬁnd that the CE is valid, we stop the loop. Otherwise, we haveto reﬁne the abstract model to eliminate the spurious CE, and repeat
these steps until valid output is obtained.

2.6.2

CEGAR Technique for a Timed Automaton

In [6], we have proposed the abstraction reﬁnement technique fora timed automaton based on the framework of CEGAR. In this approach, we remove all the clock attributes from a timed automaton. If a spurious CE is detected by model checking on an abstract
model, we transform the transition relation on the abstract model sothat the model behaves correctly even if we don’t consider the clock
constraints. Such transformation obviously represents the difference of behavior caused by the clock attributes. Therefore, the ﬁnite number of application of the reﬁnement algorithm enables us
to check the given property without the clock attributes. Since ourapproach does not restore the clock attributes at the reﬁnement step,
the abstract model is always a ﬁnite transition system without theclock attributes.

3.

PROPOSED APPROACH

In this section, we will present our abstraction reﬁnement techniquefor a probabilistic timed automaton. In the technique, we use theabstraction reﬁnement technique for a timed automaton proposed









 
 

 !
 
 


"#
$%$"



















Figure 4: An Initial Abstract Modelin [6]. In addition, we resolve the compatibility problem shown in
Sec.2.5 by performing a backward simulation technique and generating additional location to distinguish the required condition forevery incompatible path. Figure 3 shows our abstraction reﬁnement
framework. As shown in the ﬁgure, we add another ﬂow where we
resolve the compatibility problem.
Our abstraction requires a probabilistic timed automaton P T A anda property to be checked as its inputs. The property is limited by the
PCTL formula P<p [true U err]. The formula represents a property
that the probability of reaching to states where err (which means
an error condition in general) is satisﬁed, is less than p.

3.1 Initial Abstraction
The initial abstraction removes all the clock attributes from a given
probabilistic timed automaton as well as the technique in The generated abstract model over-approximates the original probabilistic
timed automaton.
D EFINITION 3.1. For a given probabilistic timed automaton
P T A = (A, L, l0 , C, I, prob), a markov decision processˆˆ P T A = (Ŝ, ŝ0 , Steps)
is produced as its abstract model,
M DP
ˆ = { (s, a, p) | (s, a, g, p) ∈where Ŝ = L, ŝ0 = l0 , and Steps
prob }
Figure 4 shows an initial abstract model for the PTA shown in Fig.1
As shown in the ﬁgure, the abstract model is just an MDP where allof the clock constraints are removed though we keep a set of clock
reset as a label of transitions.

3.2 Model Checking
In model checking, we apply Value Iteration[8] into the markov
decision process obtained by abstraction and calculate a maximum
reachability probability. Also, it decides an action to be chosen at
every state as an adversary. If the obtained probability is less than p,
we can terminate the CEGAR loop and conclude that the property
is satisﬁed.
Although Value Iteration can calculate a maximum reachability
probability, it cannot produce concrete paths used for the probability calculation. To obtain the concrete paths, we use an approach
proposed in [9] which can produce CE paths for PCTL formulas.
The approach translates a probabilistic automaton into a weighted
digraph. And we can obtain at most k paths by performing kshortest paths search on the graph.
ˆ PTA =D EFINITION 3.2. A path ω̂ on an abstract model M DPˆ(Ŝ, ŝ0 , Steps) for P T A = (A, L, l0 , C, I, prob) is given as follows,ω̂ = ŝ0

a0 ,p0 ,r0−→ ŝ1

a1 ,p1 ,r1−→ . . .

an−1 ,pn−1 ,rn−1

−→

ŝn

36


 
 


 !

 





"#
$%$"







& 



Figure 5: Products of zones obtained by Forward and Backward Simulationˆ ∧, where ŝi ∈ Ŝ for 0 ≤ i ≤ n and (ŝi , ai , pi ) ∈ Steps(ri , ŝi+1 ) ∈ support(pi ) for 0 ≤ i ≤ n − 1.
As deﬁned in Def. 3.2, we associate a set r of clock reset with apath on an abstract model in order to show the difference of r overthe probabilistic distribution p.
For the abstract model shown in Fig.4, Value Iteration outputs 1.0
as the probability that it reaches to the state d from the state a. On
the other hand, k-shortest paths search (k ≥ 2) detects two paths
τ,0.5,{}

τ,1.0,{}

τ,0.5,{x:=0}

τ,1.0,{}

ω̂ α = a −→ b −→ d and ω̂ β = a−→c −→ d,where τ represents a label for transitions with no label in the ﬁgure.

3.3

Simulation

3.4

Abstraction Reﬁnement

Simulation checks whether all the paths obtained by k-shortest paths
search are feasible or not on the original probabilistic timed automaton. We use the simulation algorithm proposed in [6] If there
is at least one path which is infeasible on the original PTA, we proceed to the abstraction reﬁnement step.

In this step, we reﬁne the abstract model so that the given spurious CE also becomes infeasible on the reﬁned abstract model. We
can use the algorithm proposed in [6]. Since the algorithm of [6]performs some operations on transitions of a timed automaton, we
replace such operations by those on probability distributions of aprobabilistic timed automaton.

3.5

Compatibility Checking

When all the paths obtained by k-shortest paths search are feasible
and a summation of occurrence probabilities of them is greater thanp, we also have to check whether all the paths are compatible or not.
In this compatibility checking step, at each location of the paths, wehave to obtain a condition (zone) which is reachable from the initialstate and also reachable to the last state along with the path. Next,
we check the compatibility of such conditions among all paths. To
obtain such conditions, we have to perform both forward simulation
shown in Sec. 3.3 and backward simulation for each path, andmerge the results. For the result of forward simulation, we canreuse the result obtained in the Simulation step. Then we check thecompatibility based on Lemma 2.1. Paper[10] shows the algorithmof compatibility checking in detail. In the algorithm, we check thecompatibility of such products of zones at every location of thepaths.
Figure 5 shows the products of zones obtained by both forward andbackward simulation for two paths ω̂ α and ω̂αβ in Sec.3.2. For theω̂path ω̂ α , the product zone at a is given as Dc,0= (x == y ∧ x <Table 1: Experimental Result
D(μs)
5
10
20

p
1.09×10−1
3.28×10−1
1.26×10−2
3.79×10−2
1.85×10−4
5.56×10−4

Digital Clocks[3]T ime(s)State M EM (M B)
20.90
297,232
10.2
20.89
297,23210.2
54.80
685,232
21.7
54.82
685,23221.7
176.93 1,461,232
41.0
177.46 1,461,232
41.0

Result
false
true
false
true
false
true

 








 & 



4.

'










(
䢞)

*䢞)



Heap(M B)
8.0
8.0
8.0
8.0
64.0
8.0

EXPERIMENTS

We have implemented a prototype of our proposed approach with
Java, and performed some experiments. Though the prototype cancheck the compatibility of a given set of paths, currently it cannot
deal with the model transformation.



' 
&



ҍ

Proposed Approach
T ime(s) Loop State
4.19
10
37
3.60
9
36
8.16
19
134
6.57
15
115
1186.08
47
477
31.32
32
435

abstract model outputs 0.5 as the maximum probability.







Result
false
true
false
true
false
true

*

(
䢞) & *䢞) &1), which means a zone which is reachable from the initial state
and also can move to d. Similarly, for the path ω̂ β , the product
ω̂ β
ω̂ α
ω̂ β
= (x == y ∧ y > 1). Since Dc,0and Dc,0zone is given as Dc,0αcontradict each other, we can conclude that the paths ω̂ and ω̂ β
are incompatible each other.

The prototype performs k-shortest paths search and simulation concurrently in order to reduce execution time. By implementing thealgorithms concurrently, we have not to wait until all of k paths aredetected, i.e. if a path is detected by the k-shortest paths searchalgorithm, we can immediately apply simulation and (if needed)
abstraction reﬁnement procedures. Also, our prototype continues
the k-shortest search algorithm when a spurious CE is detected andthe reﬁnement algorithm is applied. If other paths which do not
overlap with the previous spurious CEs, are detected, we can apply simulation and reﬁnement algorithms to it again. This helps us
reduce the number of CEGAR loop.

3.6 Model Transformation

4.1

*

Figure 6: A Transformed PTA

When the compatibility check procedure decides a given set Ω̂ ofpaths is incompatible at i-th location, our proposed algorithm resolves the incompatibility by reﬁning behaviors from the i-th location. Our algorithm uses Dcω̂ which is a product of results offorward and backward simulation for a path ω̂ ∈ Ω̂. It duplicatesω̂
locations which are reachable from the zone Dc,iby an action associated with the i-th distribution pi . Also it constructs transition
relations so that the transformation becomes equivalent transformation. For example, transition relations from a duplicated location are duplicated if the relations are executable from the invariant associated with the duplicated location. Detailed Algorithms totransform the model are given in [10].
Figure 6 shows the transformed PTA by applying the model transformation procedure for the paths ω̂ α and ω̂ β . The locations b1
and c1 are duplicated locations based on the path ω̂ α and the zoneω̂ β
= (x == y ∧ x < 1) on the location a. We associate invariDc,0βω̂ants to b1 and c1 based on zones which are reachable from Dc,0through transitions from a to b, and from a to c, respectively. Also,
we duplicate a transition from b to d as the transition from b1 to d
because the transition is feasible from the invariant of b1 . On theother hand, we do not duplicate a transition from c to d because thetransition is not feasible from the invariant of c1 . Similarly, locations b2 and c2 are duplicated locations based on the path ω̂ β andω̂ βthe zone Dc,0
. Locations b3 and c3 are generated as complementsof the invariant associated with each duplicated location in order topreserve the equivalence.

By transforming the original PTA in such a way, if we remove allclock constraints from the model in Fig.6, Value Iteration on its

37

Goal of the Experiments

The goal of this experiment is to check that our approach, which
also searches a CE, is performed within realistic time. In this experiment, we evaluated the performance of our proposed approachwith regard to execution time, memory consumption, and qualities of obtained results. As a target for comparison, we chose theapproach of Digital Clocks[3], which is considered as a basic approach, where they approximate clock evaluations of a PTA by integer values.

4.2

ExampleWe used a case study of the FireWire Root Contention Protocol[11]as an example for this experiment. This case study concerns theTree Identify Protocol of the IEEE 1394 High Performance Serial
Bus (called “FireWire”) which takes place when a node is addedor removed from the network. In the experiment, we checked theprobability that a leader is not selected within a given deadline. The
probabilistic timed automaton for the example is composed of twoclock variables, 11 locations, and 24 transitions.

4.3

Procedure of the Experiments

In this experiment, we checked the property that “the probability
that a leader cannot be elected within a given deadline is less thanp.” We considered three scenarios where the parameter deadline
is 5, 10, 20 μs, respectively. Also, for each scenario, we conducted
two experiments where the value of p is 1.5 times as an approximate
value of the maximum probability obtained by the Digital Clocks
approach[3] and a half of it, respectively. In the proposed approach,
we searched at most 5000 paths by letting the parameter k of the kshortest paths search algorithm be 5000. For evaluation of existing
approach, we used the probabilistic model checker PRISM[12].

Future work includes completion of implementation. General DBM
does not support not operator[13]; so we have to investigate efﬁcient algorithms for the not operator.

Table 2: Analysis of Counter Example Paths
D(μs)
5
10
20

p
1.0938×10−1
1.2635×10−2
1.8500×10−4

P ath
7
43
2534

P robability
1.2500×10−1
1.2695×10−2
1.8501×10−4

CC(ms)
0.7
5.9
296.9

Acknowledgments

The experiments were performed under Intel Core2 Duo 2.33 GHz,
2GB RAM, and Fedora 12 (64bit).

4.4 Results of the Experiments

The results are shown in Table 1. The column of D means the valueof deadline. For each approach, columns of Results, T ime,
and States show the results of model checking, execution time ofwhole process, and the number of states constructed, respectively.
The column M EM in the columns of the Digital Clocks shows thememory consumption of PRISM. The columns Loop and Heap in
the columns of the proposed approach show the number of CEGAR
loops executed and the maximum heap size of the Java Virtual Machine (JVM) which executes our prototype, respectively.
Table 1 shows that for all cases we can dramatically reduce thenumber of states and obtain correct results. Moreover, we can reduce the execution time more than 80 percent except for the casewhen deadline = 20μs and p = 1.85 × 10−4 . In this case, however, the execution time drastically increases.
Table 2 shows the results of analysis of CE paths obtained when
the results of model checking are false. The columns of P ath,
P robability and CC show the number of CE paths, the summationof occurrence probability of them, and execution time for compatibility checking, respectively. For this example, the obtained sets of
CE paths are compatible in every case.

4.5 Discussion
From the results shown in Table 1, we can see that our proposed
approach is efﬁcient with regard to both execution time and thenumber of states. Especially, the number of states decrease dramatically. The execution time is also decreased even though we perform model checking several times shown in the column of Loop.
On the other hand, in the case when deadline = 20μs and p =1.85 × 10−4 , the execution time increases drastically. We thinkthat as shown in Table 2 we have to search 2534 paths and thiscauses the increase of execution time especially for k-shortest paths
search. A more detailed analysis shows that the execution time fork-shortest paths search accounts for 1123 seconds of total execution time of 1186 seconds. Also, the results shows that the JVM
needs 64MB as its heap size in this case. This is because compatibility checking for 2534 of paths needs a large amount of thememory. From the results, we have to resolve a problem of thescalability when the number of candidate paths for a CE becomeslarge.

5. CONCLUSION
This paper proposed the abstraction reﬁnement technique for a probabilistic timed automaton by extending the existing abstraction reﬁnement technique for a timed automaton. The main contributionof this work is generation of a CE. Also, the experimental results
show the efﬁciency of our technique compared to one of existing
approaches.

38

This work is being conducted as a part of Stage Project, the Development of Next Generation IT Infrastructure, supported by Ministry of Education, Culture, Sports, Science and Technology, as
well as Grant-in-Aid for Scientiﬁc Research C(21500036), as wellas grant from The Telecommunications Advancement Foundation.

6.

REFERENCES[1] E. M. Clarke, O. Grumberg, and D. A. Peled, editors. Modelchecking. MIT Press, 1999.
[2] M. Kwiatkowska, G. Norman, J. Sproston, and F. Wang.
Symbolic model checking for probabilistic timed automata.
Information and Computation, 205(7):1027–1077, 7 2007.
[3] M. Kwiatkowska, G. Norman, and J. Sproston. Performance
analysis of probabilistic timed automata using digital clocks.
Int. Journal on Formal Methods in System Design,
29(1):33–78, 7 2006.
[4] M. Kwiatkowska, G. Norman, and D. Parker. Stochastic
games for veriﬁcation of probabilistic timed automata. In
Proc. of the 7th Int. Conf. on Formal Modeling and Analysis
of Timed Systems (FORMATS’09), volume 5813 of LNCS,
pages 212–227, 9 2009.
[5] E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, and V. Helmut.
Counterexample-guided abstraction reﬁnement for symbolicmodel checking. Journal of the ACM, 50(5):752–794, 2003.
[6] T. Nagaoka, K. Okano, and S. Kusumoto. An abstraction
reﬁnement technique for timed automata based on
counterexample-guided abstraction reﬁnement loop. IEICE
Transactions on Information and Systems,
E93-D(5):994–1005, 5 2010.
[7] C. Derman, editor. Finite-State Markovian Decision
Processes. New York: Academic Press, 1970.
[8] D. P. Bertsekas. Dynamic programming and optimal control.
Athena Scientiﬁc, 1995.
[9] H. Aljazzar and S. Leue. Directed explicit state-space searchin the generation of counterexamples for stochastic model
checking. IEEE Transactions on Software Engineering,36(1):37–60, 1 2010.
[10] A. Ito, T. Nagaoka, K. Okano, and S. Kusumoto.
Reachability analysis for probabilistic timed system based on
timed abstraction reﬁnement technique (in japanese). In
IEICE Technical Report, volume 109, pages 85–90, 3 2010.
[11] M. Kwiatkowska, G. Norman, and J. Sproston. Probabilistic
model checking of deadline properties in the ieee1394
ﬁrewire root contention protocol. Formal Aspects ofComputing, 14(3):295–318, 4 2003.
[12] A. Hinton, M. Kwiatkowska, G. Norman, and D. Parker:.
PRISM: A tool for automatic veriﬁcation of probabilistic
systems. In Proc. of the 12th Int. Conf. on Tools andAlgorithms for the Construction and Analysis of Systems(TACAS’06), volume 3920, pages 441–444, 2006.
[13] A. David, J. Hakansson, K G. Larsen, and P. pettersson.
Model checking timed automata with priorities using dbm
subtraction. In Proc. of the 4th Int. Conf. on Formal
Modelling and Analysis of Timed Systems, pages 128–142,
2006.

Fault-prone Module Prediction Using Contents ofComment Lines
Yukinao Hirata

Osamu Mizuno

Kyoto Institute of Technology
Matsugasaki Goshokaido-cho, Sakyo-ku
Kyoto 606-8585, Japan

Kyoto Institute of Technology
Matsugasaki Goshokaido-cho, Sakyo-ku
Kyoto 606-8585, Japano-mizuno@kit.ac.jp

y-hirata@se.is.kit.ac.jp

ABSTRACT
Comment lines in the software source code include descriptionsof codes, usage of codes, copyrights, unused codes, comments,and so on. From the viewpoint of fault-prone module prediction,comment lines may have useful information for faulty modules aswell as in code lines. In fault-proneness ﬁltering approach, which
we have been proposed based on text ﬁltering technique, comment
lines and code lines in a source code modules are regarded as text
without any distinction. For better prediction results of fault-prone
modules, the effects of the comment lines on prediction should be
investigated. This study conducts experiments using Eclipse data
sets to reveal the effects of comment lines on the fault-pronenessﬁltering. The result of experiments was somehow unexpected: prediction using comment lines shows better recall and precision thanthat of code lines.

tion by introducing a text-mining technique. This paper introduces
a new idea for fault-prone module detection. The idea is inspired
from a spam e-mail ﬁltering technique. Spam ﬁlters are usually implemented as a generic text discriminator. We thus tried to apply ageneric text discriminator to the fault-prone detection. We call ourapproach “fault-prone ﬁltering.” In fault-prone ﬁltering, we consider a software module as an e-mail message, and assume that allof the software modules belong to either fault-prone(FP) modules
or not-fault-prone(NFP) modules. After learning of existing FP and
NFP modules, we can classify a new module into either FP or NFP
by applying a spam ﬁlter. One advantage of such a statistical approach is that we do not have to investigate source code modules indetail. We do not measure any metrics explicitly, but implicitly ourapproach measures only one metric: frequency of tokens found in
the source code.

Although we have conﬁrmed usefulness of our approach, there areseveral remaining issues. One issue is effect of comment lines.
D.2.5 [Software Engineering]: Testing and Debugging; D.2.7 [Software
Previous implementation of fault-prone ﬁltering did not distinguishEngineering]: Distribution, Maintenance, and Enhancement; D.2.9
the comment lines and code lines. This is because the source code
[Software Engineering]: Management
module is passed into text ﬁlter without any modiﬁcation. However, since code lines and comment lines have different roles inGeneral Terms
source code modules, we need to consider such difference in the
Measurement
fault-prone ﬁltering. We expect to improve the prediction accuracyof fault-prone ﬁltering by using information obtained from comment lines.
1. INTRODUCTION
Fault-prone prediction is one of the most mature areas of softTo do so, we conducted an experiment to conﬁrm the effect of comware engineering. The prediction of faulty software modules isment lines in the source code modules to the fault-prone ﬁltering.
important for both the reduction of development cost and the asThe result of experiment showed that comment lines have almost
surance of software quality. Much research has been conducted
the same capability as code lines to predict fault-prone modules.
so far [1, 3, 4, 6–13, 16]. Most research used some kind of software metrics, such as program complexity, size of modules, objectoriented metrics, etc., and constructed mathematical models to cal2. OBJECTIVE
culate fault-proneness. This approach is usually based on a hy2.1 Fault-prone module ﬁltering
pothesis that the more complex module the more bugs. However,
The basic idea of fault-prone ﬁltering is inspired by spam mail ﬁlsuch a hypothesis is not always true. For example, although manytering. In spam e-mail ﬁltering, the spam ﬁlter ﬁrst trains both spam
if-sentences increase program complexity,and ham e-mail messages from the training data set. Then, an incoming e-mail is classiﬁed into either ham or spam by the spam
We thus tried to break through the conventional fault-prone predicﬁlter.

Categories and Subject Descriptors

This framework is based on the fact that spam e-mail usually includes particular patterns of words or sentences. From the viewpoint of source code, a similar situation usually occurs in faulty
software modules. That is, similar faults may occur in similar contexts. We thus guessed that similar to spam e-mail messages, faulty
software modules have similar patterns of words or sentences. To
obtain such features, we adopted a spam ﬁlter in fault-prone module prediction.

39

Faulty

Intuitively speaking, we try to introduce a new metric as a faultprone predictor. The metric is “frequency of particular words”. In
detail, we do not treat a single word, but use combinations of words
for the prediction. Thus, the frequency of a certain length of words
is the only metric used in our approach.
We then try to apply a spam ﬁlter to identiﬁcation of fault-prone
modules. We named this approach as “fault-prone ﬁltering”. Thatis, a learner ﬁrst trains both faulty and non-faulty modules. Then,a new module can be classiﬁed into fault-prone or not-fault-proneusing a classiﬁer.

Non-faulty

Comment lines
in faulty modules

In this study, we deﬁne a software module as a Java class ﬁle.

ft
Mcom

Comment lines
in non-faulty
modules

Tokenize andlearn

Tokenize andlearn

Faulty comment
corpusNon-faulty
comment
corpusnf
Mcom

2.2 Effect of comment lines
In this paper, we call “comments” in the source code module ascomment lines, and call other lines as “code lines”.
Code lines describe a list of operations that developers would liketo realize on computers. Comment lines include descriptions ofcode lines, usage of methods or modules. Code lines are written ina speciﬁc programming language, but comment lines are written ina free form.
Previous implementation of fault-prone ﬁltering did not distinguishthe comment lines and code lines. This is because the source code
module is passed into text ﬁlter without any modiﬁcation. However, since code lines and comment lines have different roles insource code modules, we need to consider such difference in thefault-prone ﬁltering.
For example, comments are usually placed near the difﬁcult codes.
Therefore, learning the contents of comment lines may be useful toidentify the bug-related part in modules. We expect to improve theprediction accuracy of fault-prone ﬁltering by using comment lines
effectively.

3. IMPLEMENTATION OF FAULT-PRONEFILTER
In the previous studies [14, 15], we used a ready-made open-source
text classiﬁer, CRM114 [19]. However, use of ready-made software
hides essential information in experiments. We thus implement atext classiﬁer from scratch for this experiment.

Figure 1: Learning procedureand double quotations as a separator in the comment lines. Consequently, a code piece output("Hello, world!"); is tokenized into 2 tokens, “output” and “"Hello, world"”, incode lines, but is tokenized into 3 tokens, “output”, “Hello”,
and “world” in comment lines.

3.2

Step 1 Tokens are extracted from faulty and non-faulty modules.
The number of occurrence for each token in faulty and nonfaulty modules are counted. For a given token t, the following two hash functions can be deﬁned:• nonf aulty(t): The occurrence of token t in all nonfaulty modules.
• f aulty(t): The occurrence of token t in all faulty modules.

3.1 Tokenization
First of all, inputs of fault-prone ﬁlter must be tokenized. Codelines are tokenized by the Java syntax scanner as follows:
1. Strings with alphabets, numeric characters, and period
2. Operators in Java language
3. Strings with single quotations
4. Strings with double quotations
Other characters, spaces, commas, braces, colons, semicolons, andso on, are used as a separator to make tokens.
As for the comment lines, tokenization is done by similar mannerwith the case of code lines. However, since it is difﬁcult to determine the end of quoted strings in comment lines, we treat single

40

Learning algorithm

The algorithm of learning and classiﬁcation is the same as that of[5].

Step 2 We construct a hash table to obtain the probability, Pf t|t ,by equation (1) that a module that includes the token t is
faulty. Here, Nnf denotes the number of non-faulty modules
and Nf t denotes the number of faulty modules. We call thishash table as a corpus.
«„
2 × nonf aulty(t)rnf = min 1,
Nnf«„
f aulty(t)rf t = min 1,
Nf t
««
„
„
rf t
(1)
Pf t|t = max 0.01, min 0.99,
rnf + rf t

3.3

Classiﬁcation algorithm

The classiﬁcation process is also based on Graham’s algorithm [5].

Table 1: Target projects
Project
EclipseVersion
2.0
2.1
Number of modules
6,729
7,888
Number of faulty
975
854
modules(14.5%)(10.8%)
Number of non5,754
7,034
faulty modules(85.5%)(89.2%)
Total lines of code
1,267,350 1,564,872
Comment lines
475,486
577,033(37.5%)(36.9%)
Code lines
791,864
987,839(62.5%)(63.1%)M

A new
Java source code
moduleMcom
Comment lines
in a module

Mcode
Code lines
in a module

Faultycomment
corpusFaulty code
corpusClassiﬁcation

Classiﬁcation

Non-faulty
comment
corpusActualNon-faulty
code
corpus
Probability tofaultyProbability tofaultyFigure 2: Classiﬁcation procedure
Step 1 For a new module, distinct tokens are extracted. In thisstudy, we use all extracted tokens. Here, we count the number of tokens, n, for the next step1 .
Step 2 According to the equation (2), the probability Pf t is calculated. We determine whether a module is fault-prone or not.
If Pf t ≥ 0.9, the module is determined as fault-prone.
Qn
i=1 Pf t|ti
Q
Qn
Pf t = n
(2)
P
+
f
t|t
i
i=1
i=1 (1 − Pf t|ti )To both comment lines and code lines, we separately apply thisclassiﬁcation algorithm. Intuitive description of the classiﬁcation
procedure is shown in Figure 2.

4. EXPERIMENT
4.1 Target project

Table 2: Classiﬁcation result matrix
Classiﬁed
non-fault-prone
fault-prone
non-faulty True negative (TN) False positive (FP)faultyFalse negative (FN) True positive (TP)available on the Web. Many researchers can use the same data set
and compare their approaches. The data set includes the values ofsoftware complexity metrics shown and fault data collected by the
SZZ algorithm [18] for each class ﬁle, that is, software modules.
The data is obtained from Eclipse version 2.0, 2.1, and 3.0. The
number of modules in Eclipse 2.0, 2.1 and 3.0 are 6,729, 7,888 and
10,593, respectively.

4.2

Evaluation measures

Table 2 shows a classiﬁcation result matrix. True negative (TN)shows the number of modules that are classiﬁed as non-fault-prone,
and are actually non-faulty. False positive (FP) shows the numberof modules that are classiﬁed as fault-prone, but are actually nonfaulty. On the contrary, false negative shows the number of modules that are classiﬁed as non-fault-prone, but are actually faulty.
Finally, true positive shows the number of modules that are classiﬁed as fault-prone which are actually faulty.
In order to evaluate the results, we prepare two measures: recall,precision. Recall is the ratio of modules correctly classiﬁed as
fault-prone to the number of entire faulty modules Recall is deﬁned
by equation (3).
Recall =In order to conduct experiments, we prepare a data set obtained
from Eclipse project by Zimmermann [2,20], which is called promise2.0a data set. In the data set, 31 complexity metrics as well as thenumber of pre- and post-release faults are deﬁned and collected.
Although promise-2.0a includes metrics collected from both ﬁlesand packages, we used the metrics from ﬁles for this study. One ofadvantages to use promise-2.0a from Eclipse is that it is publicly
1

We can use a limited number of tokens here. To do so, among
those extracted tokens, most characteristic n tokens, t1 · · · tn aredetermined. In more detail, Cx = abs(0.5 − Pf t|tx ) is calculated
for each token tx , and we select n tokens with the largest Cx s bydescending order. For calculation of Cx , if a token t is a never seen
one, we assume that Pf t|t = 0.4. Based on the pre-experiment, wefound that the prediction performance does not differ if we use, forexample, 20 characteristic tokens. But for simplicity, we used all
tokens in this experiment.

41

3.0
10,5931,568(14.8%)
9,025(85.2%)
2,098,034
788,055(37.6%)
1,309.979(62.4%)TP
TP + FN(3)

Precision is the ratio of modules correctly classiﬁed as fault-prone
to the number of entire modules classiﬁed fault-prone. Precision isdeﬁned by equation (4).
Precision =TP
TP + FP(4)

Accuracy is the ratio of correctly classiﬁed modules to the entire
modules. Accuracy is deﬁned by equation (5).
Accuracy =TP + TNTN + TP + FP + FN

(5)Since recall and precision are in the trade-off, F1 -measure is used
to combine recall and precision. F1 -measure is deﬁned by equation

Table 3: Result of prediction: (comment, 2.0, 2.1)
Prediction
non-fault-prone fault-prone
Actual not faulty
5,952
1,082
faulty508
346

MJava source code
modulesNon-faulty

FaultyFaultyJava source code
modulesNon-faultyJava source code
modules

M ft

M nf

FaultyFaultyNon-faulty

Comment lines
in faulty modules

Code lines
in faulty modules

ft
Mcom

ft
Mcode

Comment lines
in non-faulty
modulesnf
Mcom

Table 4: Result of prediction: (code, 2.0, 2.1)
Prediction
non-fault-prone fault-prone
Actual not faulty
5,711
1,323
faulty492
362

Non-faulty

Table 5: Result of prediction: (comment, 2.0, 3.0)
Prediction
non-fault-prone fault-prone
Actual not faulty
7,625
1,400
faulty835
733

Code lines
in non-faulty
modulesnf
McodeTable 6: Result of prediction: (code, 2.0, 3.0)
Prediction
non-fault-prone fault-prone
Actual not faulty
7,477
1,548
faulty934
634

Figure 3: Getting modules
(6).
F1 =

2 × recall × precision
recall + precision(6)

By using code and comment corpuses, Mcode and Mcom areclassiﬁed.

In this deﬁnition, recall and precision are evenly weighed.

4.3 Application to Eclipse
In this section, we describe a procedure of experiments.
We obtained the source code modules from tar archives of corresponding Eclipse versions. We can deﬁne faulty and non-faulty
source code modules by the metric “post-release failure (post)” inpromise-2.0a. If post > 0, a module is faulty; otherwise nonfaulty. Based on the faulty/non-faulty information, we divide sourcecode modules into “faulty” and “non-faulty”, represented f t andnf , respectively. Moreover, we separate a module into code andcomment lines for each source code module. This procedure isshown in Figure 3.
Here, let Mcode and Mcom be code lines and comment lines extracted from a module M , respectively. In the classiﬁcation withcode lines, we use only Mcode as training and test data. Similarly,
we use only Mcom in the classiﬁcation with comment lines.
The following procedure was conducted in this experiment:
1. For the learning step, we ﬁrst pick up a version of Eclipse
project as a training data set. We then divide the training
data set into faulty and non-faulty. For each faulty module,ft
Mcodeis extracted and conducted learning for a faulty codeft
is extracted and learnt in a faulty
corpus. Similarly, Mcomcomment corpus. For non-faulty modules, the same procenf
nf
dure for Mcodeand Mcomis performed.
2. For the classiﬁcation step, we pick up the other version of
Eclipse project as a testing data set. The, the testing data
set is applied to the classiﬁcation procedure. For each module in the testing data set, Mcode and Mcom are extracted.

42

In this experiment, we use versions 2.0 and 2.1 for training and versions 2.1 and 3.0 for testing, since it is natural to use older version
for training and newer version for testing. These training pairs areused for different targets: code lines or comment lines. We thus
prepare six experiment 3-tuples denoted by (target, training, testing): (code, 2.0, 2.1), (comment, 2.0, 2.1), (code, 2.0, 3.0), (comment, 2.0, 3.0), (code, 2.1, 3.0), and (comment, 2.1, 3.0).
The results of six prediction experiments are shown in Tables 3 –8.

4.4

Result of experiment

A summary of experimental results are shown in Table 9. Boldﬁgures show the best result. We can ﬁnd following three ﬁndings
from Table 9:
1. Predicted results with comment lines have better F1 ’s thanthat of code lines.

Table 7: Result of prediction: (comment, 2.1, 3.0)
Prediction
non-fault-prone fault-prone
Actual not faulty
7,563
1,462
faulty986
582
Table 8: Result of prediction: (code, 2.1, 3.0)
Prediction
non-fault-prone fault-prone
Actual not faulty
7,883
1,142
faulty1,133435

Table 11: Number of modules without comments
versionfaultynon-faulty
2.0
3 (0.31%) 34 (0.59%)
2.1
0 (0%)
0 (0%)
3.0
0 (0%)
3 (0.03%)

Table 9: Summary of experimental results (Threshold = 0.9)
Train Test
Target
Acc.
Rec.
Prec.
F1
2.0
2.1 Comment 0.798 0.405 0.242 0.303
Code0.770 0.424 0.215 0.285
All
0.782 0.419 0.228 0.294
2.0
3.0 Comment 0.789 0.467 0.344 0.396
Code
0.766 0.404 0.291 0.338
All
0.777 0.420 0.312 0.358
2.1
3.0 Comment 0.769 0.371 0.285 0.322
Code
0.785 0.277 0.276 0.277
All
0.781 0.289 0.274 0.281

Table 12: Comparison with Zimmermann’s result [20]Train Test
Target
Acc.
Rec.
Prec.
F1
2.0
2.1
Comment
0.789 0.419 0.234 0.300
Code0.755 0.438 0.204 0.279
Zimmermann 0.890 0.191 0.478 0.273
2.0
3.0
Comment
0.776 0.492 0.328 0.394
Code0.747 0.415 0.270 0.327
Zimmermann 0.861 0.171 0.613 0.267
2.1
3.0Comment
0.738 0.416 0.260 0.320
Code
0.768 0.292 0.254 0.272
Zimmermann 0.864 0.139 0.717 0.233

Table 10: Summary of experimental results (Threshold = 0.5)
Train Test
Target
Acc.
Rec.
Prec.
F1
2.0
2.1 Comment 0.789 0.419 0.234 0.300
Code0.755 0.438 0.204 0.279
All
0.778 0.426 0.224 0.294
2.0
3.0 Comment 0.776 0.492 0.328 0.394
Code0.747 0.415 0.270 0.327
All0.770 0.430 0.304 0.356
2.1
3.0 Comment 0.738 0.416 0.260 0.320
Code
0.768 0.292 0.254 0.272
All
0.769 0.302 0.259 0.279
2. Recalls are usually higher than precisions.
In Table 9, we show results of regular fault-prone ﬁltering, that is,predictions using both comment lines and code lines. Rows “All”
show the results.
As we described in subsection 3.3, the threshold of probability todetermine as fault-prone is 0.9. Since we guessed that this threshold is too high, we conducted another experiments using threshold of 0.5. The summarized result is shown in Table 10. Because
we decrease the threshold to determine fault-prone, the number offault-prone modules is increased. Consequently, recalls are relatively higher than that of Table 9.

5. DISCUSSIONS
The result in Tables 9 and 10 are unexpected for us. The result indicates that using only comment lines can achieve a certain extent
of prediction accuracy. Furthermore, it is better than that of codelines from the viewpoint of F1 . We can also see that prediction
results using both code and comment show the intermediate result
between that of comment lines and code lines. However, the evaluation measures are very close between comment lines and codelines. We expected that there is more difference between them. We
guess a reason for this result as follows: We used only one revision
for training. This may decrease the accuracy of fault-prone ﬁltering. The fault-prone ﬁltering originally aims to utilize historicalinformation of texts in the source code modules. When we adopt
such data, we may get different result with this. In order to investigate the effects of comment lines in more detail, we will conduct
further research using historical data.
One concern on this experiment is the number of modules that do
not include comments. We cannot deal with modules without comments correctly in the prediction with comment lines. Table 11shows the number of modules without comment lines for each version. We can see that there is few modules without comment lines.

43

On the other hand, we need to compare with the other fault-prone
prediction approach. The most appropriate subject of comparison
is Zimmermann’s result [20] since the data we used in this study
is quoted their paper. The result of comparison is summarized inTable 12. Table 12 shows that Zimmermann’s approach has higher
precision than ours, but our approach has higher recall. At least,
from the viewpoint of F1 , we can say that our approach is as accurate as that of [20]. For another comparison, we compare withthe results obtained by Shihab et al. [17]. Table 13 shows the results. We can see that their result is similar to the result of Zimmermann’s. That is, we guess that software metrics based approaches
tend to achieve high precision, whereas spam ﬁlter based approachhigh recall. In further research, we need to analyze why our approach shows high recall.

6.

CONCLUSIONSIn this study, we tried to investigate the effects of comment lines
in the source code modules on the accuracy of fault-prone ﬁltering,which is a text-classiﬁcation based fault-prone module prediction
method. We conducted experiments using Eclipse data sets to reveal the effects of comment lines on the fault-prone ﬁltering. The
result of experiments was somehow unexpected: prediction using
comment lines shows better recall and precision than that of codelines.
Future work includes more experiments using entire historical datain the repository. In this study, we only used comment lines only,
but logs in SCM can be a good candidate of input for fault-prone
ﬁltering. On the other hand, analysis to identify important tokens
for fault-prone modules is an interesting future research. We are
currently tackling this issue.

7.

ACKNOWLEDGMENTS
Table 13: Prediction results obtained by Shihab et al. [17]Version Acc.
Rec.
Prec.
2.0
0.875 0.285 0.663
2.1
0.898 0.158 0.600
3.0
0.869 0.257 0.641

This research is partially supported by the Japan Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Young Scientists (B), 20700025, 2008–2010.

8. REFERENCES[1] P. Bellini, I. Bruno, P. Nesi, and D. Rogai. Comparing
fault-proneness estimation models. In Proc. of 10th IEEE
International Conference on Engineering of Complex
Computer Systems, pages 205–214, 2005.
[2] G. Boetticher, T. Menzies, and T. Ostrand. PROMISE
Repository of empirical software engineering datarepository. http://promisedata.org/, West Virginia University,
Department of Computer Science, 2007.
[3] L. C. Briand, W. L. Melo, and J. Wust. Assessing theapplicability of fault-proneness models acrossobject-oriented software projects. IEEE Trans. on Software
Engineering, 28(7):706–720, 2002.
[4] G. Denaro and M. Pezze. An empirical evaluation of
fault-proneness models. In Proc. of 24th International
Conference on Software Engineering, pages 241–251, 2002.
[5] P. Graham. Hackers and Painters: Big Ideas from theComputer Age, chapter 8, pages 121–129. O’Reilly Media,
2004.
[6] L. Guo, B. Cukic, and H. Singh. Predicting fault prone
modules by the dempster-shafer belief networks. In Proc. of
18st International Conference on Automated Software
Engineering, pages 249–252, 2003.
[7] T. M. Khoshgoftaar and E. B. Allen. Logistic regression
modeling of software quality. International Journal of
Reliability, Quality and Safety Engineering, 6(4):303–317,
1999.
[8] T. M. Khoshgoftaar and E. B. Allen. Controlling overﬁtting
in classiﬁcation tree models of software quality. Empirical
Software Engineering, 6(1):59–79, 2001.
[9] T. M. Khoshgoftaar, E. B. Allen, and J. Deng. Using
regressin trees to classify fault-prone software modules.
IEEE Trans. on Reliability, 51(4):455–462, 2002.
[10] T. M. Khoshgoftaar and N. Seliya. Software quality
classiﬁcation modeling using SPRINT decision tree
algorithm. In Proc. of 14th International Conference on
Tools with Artiﬁcial Intelligence, pages 365–374, 2002.
[11] T. M. Khoshgoftaar and N. Seliya. Comparative assessmentof software quality classiﬁcation techniques: An empirical
study. Empirical Software Engineering, 9:229–257, 2004.
[12] T. M. Khoshgoftaar, R. Shan, and E. B. Allen. Using
product, process, and execution metrics to predict fault-prone
software modules with classiﬁcation trees. In Proc. of 5thIEEE International Symposium on High Assurance Systems
Engineering, pages 301–310, 2000.
[13] T. Menzies, J. Greenwald, and A. Frank. Data mining static
code attributes to learn defect predictors. IEEE Trans. on
Software Engineering, 33(1):2–13, January 2007.
[14] O. Mizuno and T. Kikuno. Training on errors experiment todetect fault-prone software modules by spam ﬁlter. In Proc.
of 6th joint meeting of the European software engineering
conference and the ACM SIGSOFT symposium on thefoundations of software engineering, pages 405–414, 2007.
[15] O. Mizuno and T. Kikuno. Prediction of fault-prone softwaremodules using a generic text discriminator. IEICE Trans. on
Information and Systems, E91-D(4):888–896, 2008.
[16] N. Seliya, T. M. Khoshgoftaar, and S. Zhong. Analyzing

44

software quality with limited fault-proneness defect data. In
Proc. of 9th IEEE International Symposium on
High-Assurance Systems Engineering, pages 89–98, 2005.
[17] E. Shihab, Z. M. Jiang, W. M. Ibrahim, B. Adams, and A. E.
Hassan. Understanding the impact of code and process
metrics on post-release defects: a case study on the eclipse
project. In Proceedings of the 2010 ACM-IEEE International
Symposium on Empirical Software Engineering and
Measurement, ESEM ’10, pages 4:1–4:10, New York, NY,
USA, 2010. ACM.
[18] J. Śliwerski, T. Zimmermann, and A. Zeller. When dochanges induce ﬁxes? (on Fridays.). In Proc. of 2ndInternational workshop on Mining software repositories,
pages 24–28, 2005.
[19] W. S. Yerazunis. CRM114 – the Controllable Regex
Mutilator. http://crm114.sourceforge.net/.
[20] T. Zimmermann, R. Premrai, and A. Zeller. Predicting
defects for eclipse. In Proc. of 3rd International Workshop
on Predictor models in Software Engineering, 2007.

Process Analysis

45

46

A Preliminary Study on Impact of Software Licenses on
Copy-and-Paste Reuse
Yu Kashima

Graduate School ofInformation Science andTechnology, Osaka University

Yasuhiro Hayase

Faculty of Information
Sciences and Arts, Toyo
University

Norihiro Yoshida

Graduate School ofInformation Science, Nara
Institute of Science andTechnology

hayase@toyo.jp
y-kasima@ist.osakayoshida@is.naist.jp
u.ac.jp
Yuki Manabe
Katsuro Inoue
Graduate School ofInformation Science andTechnology, Osaka University

Graduate School ofInformation Science andTechnology, Osaka University

y-manabe@ist.osakau.ac.jp

inoue@ist.osaka-u.ac.jp

ABSTRACT
Source code of open-source software is permitted to be reused
when and only when the conditions of its license are satisﬁed. There are many diﬀerent conditions for reusing, sincevarious open-source licenses are used. Therefore, the licenseof the source code may aﬀect the frequency of reusing or
the property of the software for which the source is reused.
To identify the relationship between software license andreusing, we are planning to classify copy-and-pasted codefragments based on the license of the fragments. This paper presents a preliminary and manual investigation on asmall source ﬁle set. The result indicates that the licenseof a fragment aﬀects the quantity and the license of copied
fragments.

Categories and Subject Descriptors
K.5.1 [LEGAL ASPECTS OF COMPUTING]: Hardware / Software Protection—Licensing; K.6.3 [MANAGEMENT OF COMPUTING AND
INFORMATION SYSTEMS]: Software Management—
Software Selection

General Terms
Legal Aspects, Experimentation

Keywords
Software License, Open Source Software, Reuse, Copy and
Paste

1. INTRODUCTION

Source code of open source software (i.e. OSS) is available for anyone to modify or redistribute. According to thegrowth of OSS development [16], software developers canreuse huge amount of OSS source code nowadays.
Everyone has to adhere to the license of a software productwhen he/she obtains or uses the product. The license ofa product expresses the intent of the right holder; Several
OSS licenses require the derivative works to apply the same
license of the original product, i.e. copyleft1 . Since diﬀerent
right holders have diﬀerent intents, many OSS licenses areused.
Software reuse is recognized as a practice for reducing the development cost and improving the product quality. Software
reuse happens at several levels of granularity; from simple
copy and paste of code snippet, to whole the inclusion, tosubsystem reuse.
Software reuse must adhere the license of the reused product.
Furthermore, developers must pay attention not to violate
the licenses of the product they are developing by reusing
other software.
OSS licenses have diﬀerent attitudes toward reuse.[14] For
example, the GNU General Public Licenses (GPL)[5] requires derivative works, including a product that contains acode fragment copied from a GPL product, to be distributed
under the GPL. On the other hand, the BSD license[13] only
requires that the copyright notice, the license text and thedisclaimer are retained. Thus, the reused product must be
carefully selected to not conﬂict with the license of a productunder development.
Consequently, software license may aﬀect the frequency ofcode reuse or the variety of the derived products. For instance, the source code distributed under a copyleft license
may be reused less frequently and reused in narrow a variety of software products, compared to non-copyleft license147

http://www.gnu.org/copyleft/ (accessed Oct 2010)

source code. To the knowledge of the available, there is noquantitative study of CnP reuses from the point of view ofsoftware license.
This paper presents a preliminary study on the impact of
the software licenses on CnP reuse on a small data set.
The preliminary experiment intends to assess the processof evaluating CnP source code based on the software license. The target of the experiment is Java source code
distributed in Debian GNU/Linux lenny[3]. We investigatedcopy-and-pasted code fragments that are distributed under
three major licenses; the 3-clause BSD license (BSD3), the
GPL Version 2 or later (GPLv2+) and the Apache License
2.0 (Apachev2)[1]. To detect copy-and-pasted code fragments, CCFinder[10] and LNR ﬁltering criterion are used.
Result of the experiment shows that source code distributed
under the BSD3 or the Apachev2 is more frequently reusedthan the GPLv2 code. On the other hand, Apachev2 andGPL code has a trend to be reused in code distributed under speciﬁc licenses. Through the preliminary experiment,
we conﬁrmed that the process of evaluation is eﬀective andapplicable for large data set.
The rest of this paper is organized as follows. Section 2 explains background of this study. Section 3 illustrates design
and result of the experiment, and Section 4 interprets theresult of the experiment. Section 5 discusses about the validity of the experiment, ﬁnally, Section 6 shows the conclusionand future remarks.

2. SOFTWARE LICENSE AND REUSING
Nowadays, many open-source licenses are used; for instance,
the Open Source Initiative oﬃcially approves 67 licenses 2 .
This section illustrates three of most major licenses, 3-clause
BSD license (BSD3), Apache License 2.0 (Apachev2) and
GNU General Public License version 2 (GPLv2) from theperspective of a developer who makes a derivation product.
From the point of view of a developer, diﬀerent licenses mean
diﬀerent restrictions.
When a developer makes a derivative work from a BSD3
product, the former should retain the copyright notice andthe full text of the license.
If a developer makes a derivative work from an Apachev2
product, all copyrights, patents, trademarks, and attribution notices should be retained in the new product. Moreover, changed ﬁle also should have notices of the modiﬁcation.
When a developer makes a derivation from a GPLv2 product, the whole derivation must be distributed under the
GPLv2 and, changed ﬁle should have notices of the modiﬁcation.

^ϯ

ŶW

'W>

'W>

ŶW

^ϯ

Figure 1: Reusing source code in a diﬀerent license
product

reuse source code of OSS products since the source code iseasily available.
Copy-and-paste (CnP) is one of the most frequently performed methods of reuse. In CnP reuse, source code iscopied, modiﬁed if needed, and ﬁnally, used as a part ofnew product.[11, 14]
When reusing existing software, both the license of the product being reused and of the developing product must be
satisﬁed. In case the two licenses are incompatible, bothcannot be satisﬁed simultaneously. For example, Apachev2
products cannot be incorporated into the GPLv2 products,
since several requirements in the Apachev2 conﬂict with aclause in GPLv2.3
Furthermore, even if the licenses do not conﬂict, an OSS
product cannot be reused if license of the developing product cannot be changed. For example, GPLv2 source code
cannot be incorporated into a BSD3 product. In contrast,
BSD3 source code can be incorporated into a GPLv2 product because the restrictions of the BSD3 are included in the
GPLv2. (Figure 1)

2.2

Impact of Software License on Copy andPaste Reuse

As described above, the license of the reused product is themain concern to software reuse. If a license of source code
doesn’t match a developing product, the source code cannot
be reused in the developing product unless the license of thedeveloping product is changed. Therefore, it is clear that thereusability of software depends on not only functionality or
quality, but also license of the software.
Whether reusing source code by CnP is allowed or not depends on its license. As previously explained, when a developer reuses source code, the developer must observe thesource codes license. Licenses with very restrictive terms(i.e. GPL) might make it diﬃcult to satisfy their condition,
while licenses with more relaxed conditions have easier tomeet requirements.
We make the following assumptions:

2.1 OSS License and Reuse
Software reuse is recognized as a practical method for developing high quality software with low cost. A developer can2
http://www.opensource.org/licenses
2010)(accessed

Oct48• source code with a relaxed license is reused under various licenses.
3
http://www.gnu.org/licenses/license-list.html (accessed Oct 2010)Table 1: kept packages and excluded packages
kept packages excluded packages
antlr3antlr
asm3
asm, asm2
db4.6
db4.2, db4.3
junit4junit
tomcat6
tomcat5.5• source code with a relaxed license is reused more frequently than source code under a strict license.

3. EXPERIMENT

Table 2: Distribution of licenses in all ﬁles of theanalysis target
License Name
#File
Apachev2
16350 GPLv2+
8160 
LesserGPLv2.1+
6534
GPLnoVersion,GPLv2+,LinkException
5887
GPLv2
3222
BSD3
2181 
GPLv2,ClassPathException
1498
No description specifying license in the ﬁle 15813
Fail to analyze the description
6862
SeeFile2786

The goal of this study is an investigation of the impact of licenses on CnP reuse in OSS. To achieve the goal, we need toanalyze actual OSS to identify the relationship between licenses and CnP reuse. In this paper, we analyzed the source
ﬁles of OSS in order to validate our method.
This study focused only source code reuse across applications. We believe that the impact of license on source code
reuse within an application is small. Because, even though
there are CnP between ﬁles under diﬀerent license, a license
problem occurred by these ﬁles must be resolved.

3.1 Analysed CodeWe selected a part of the source ﬁles of Debian/GNU Linux
as our analysis target for the following reasons:• Various licenses are used by it.
• It includes diﬀerent type of software.
First, we downloaded the packages contained in the main
section of Debian/GNU Linux; second, we extracted the content of the “.tar.gz” ﬁles; ﬁnally, we selected the source code
written in Java(.java) the target of our analysis. Consequently, the analysis target consisted of 77452 ﬁles (8530896
LOC) from 452 packages.
Note that we kept one of several packages having diﬀerent
versions respectively and excluded the others in the analysis
target. For example, between asm, asm2 and asm3, we kept
asm3 and excluded asm and asm2 from the analysis target.
Table 1 shows the kept packages and the excluded packages.

3.2 Experiment Method
Figure 2 shows an overview of the method of this experiment.

Step 1 We identiﬁed the licenses of each ﬁle by analyzing the description specifying its licenses in the ﬁle.
We used Ninka[7] to identify the licenses. Ninka is atool which analyzes descriptions specifying licenses ina source ﬁle and identiﬁes speciﬁed licenses. The reason why Ninka was used in this step is that Ninka is astate-of-art license identiﬁcation tool and more precise
than other existing license identiﬁcation tools such as
FOSSology[8]. Note that not only a source ﬁle but also49

a package can have a license. According to the Debian
Policy[4], Each package has a ’copyright’ ﬁle specifying
the license of the package. However, this step didn’t
use this ’copyright’ ﬁle because the license of source
ﬁles in the package does not always correspond to thelicense of the package[6, 8].
Step 2 We extracted the clone sets[10] created by copyand-paste. A clone set is an equivalence class of theclone-relation. The clone-relation is deﬁned as an equivalence relation. The clone-relation holds between twocode portions if (and only if) they are the same sequence. A code fragment which is similar to anotheris called code-clone. We give a detailed description of
the method for extracting clone sets in Section 3.3.
Step 3 We extracted clone sets including a code fragment
under speciﬁc license A, and we classiﬁed and counted
the code fragments in these clone set based on theirlicense. Since the source of the CnP cannot be retrieved from code clones, the direction of CnP was notconsidered in this experiment.

Due to time limitation, we investigated only some licenses
that are widely used and diﬀer from each other in the condition on CnP reuse. Table 2 shows the abbreviated namesof the licenses ranked in descending order by the number ofﬁles under it in the analysis target. Licenses marked with acheck are the ones we investigated. Table 3 shows the fullnames of the licenses in Table 2. When we show a versionof license, “v<number>” follows. In addition, if users canchoose this version or any later, “+” follows. Furthermore, if
user can choose several licenses, usable license names follow
after “,”.
We analyzed Apachev2, GPLv2+ and BSD3 as Table 2 shows.
Apachev2 is used by the largest number of ﬁles in the analysis target; GPLv2+ and GPL derivatives are counted in
the second. BSD3 is used by the largest number of ﬁles
except ﬁles under Apachev2 or licenses which conditions
like GPLv2+ such as “LesserGPLv2.1+”, “GPLnoVersion,
GPLv2+, LinkException”, “GPLv2+”.

3.3

CnP Detection

We used CCFinder[10] for detecting code fragments createdby CnP. CCFinder is a code-clone detection tool. We canƵŶŬŶŽǁŶ

>ŝĐĞŶƐĞ>ŝĐĞŶƐĞůĂƐƐŝĨǇŝŶŐĂƐĞĚŽŶ>ŝĐĞŶƐĞ

ĞƚĞĐƚŝŶŐΘW/ĚĞŶƚŝĨǇŝŶŐ>ŝĐĞŶƐĞ

>ŝĐĞŶƐĞ>ŝĐĞŶƐĞ>ŝĐĞŶƐĞ
EĂŵĞηŽĚĞ
ůŽŶĞ



ϭϬ



ϯ

͙͘

͙͘

^ŽƵƌĐĞ&ŝůĞ^Ğƚ

Figure 2: Overview of evaluation method

Table 3: License name abbreviations
Abbreviation
Apache
BSD3ClassPathException
CPL
GPL
LesserGPL
LibraryGPL
LinkException
MITX11noNoticeMPL
MX4jLicense
publicDomain
SeeFilesubversion

Name
Apache Public License
Original BSD minus advertisement clause
GNU Classpath License
Common Public License
General Public License
Lesser General Public License
Library General Public License
GPL linking exception
MIT License/X11License
Mozilla Public License
MX4J License
Public Domain
File Points to another where the its license is
Subversion License

extract code fragments copied and pasted by detecting codeclones.
In this experiment, when we detect CnP from the analysis
target, we detected code-clone ignoring the identiﬁer names,
because we wanted to detect code fragments in which identiﬁer names changed after the CnP.
Additionally, we used LNR to ﬁlter clone set involving codefragment created by CnP from extracted clone set. LNR is
the number of tokens of non repeated elements in a codefragment. A code fragment which LNR is small might includes only variable declarations, assignments or getter/setter
declarations. These code fragments are called language speciﬁc clones. By contrast, if the LNR of a code fragment
is large, the code fragment has higher classes to be createdby CnP. Therefore, in this experiment, we presumed that aclone set is created by CnP if the average of LNR of codefragments is over some speciﬁc value. This value was set at
50, because our experience shown that 50 is an appropriate
value to exclude language speciﬁc clones.

3.4 Results

Table 4: Distribution of code fragments havingclone-relation to ﬁles under BSD3
License Name
#Fragments
BSD3
613
GPLv2+
20
Apachev2
16
LibraryGPLv2+
14
GPLv2,ClassPathException
1
LesserGPLv2.1+
1

Table 5: Distribution of code fragments havingclone-relation to ﬁles under Apachev2
License Name
#Fragments
Apachev2
1533
Apachev1.1
316
LesserGPLv2.1+
42
MPLv1 133
BSD329
MX4JLicensev1
16
GPLv2+
4
LibraryGPLv2+
3
MPLv1 02
MITX11noNotice2
publicDomain
1subversion+
1
EPLv1
1

We found that CnP fragments tend to have the same license. In the case of BSD3, code fragments under BSD3
account for 92% of all code fragments. Similarly, in the caseof Apachev2, code fragments under Apachev2 account for
77% of all. In the case of GPLv2+, code fragments underGPLv2+ account for 48% of all.

Table 4 shows the number of code fragments under eachlicense; Table 5 shows the case of Apachev2; Table 6 shows
the case of GPLv2+.

In the case of Apachev2, code fragments under Apachev1.1
account for 16% of all. Similarly, in the result of GPLv2+,“GPLnoVersion, GPLv2+, LinkException” account for 41%
of all.

Table 7 shows the number of code fragments, ﬁles and theratio of code fragments to ﬁles of BSD3, Apachev2 andGPLv2+. We can see from Table 7 that the order arranged
in descending order of number of code fragments comparedto number of ﬁles is BSD3, Apachev2, GPLv2+.

If we evaluate the results from the point of view of the number of licenses, Apachev2 has CnP relationship to the largest
number of licenses. Apachev2 has CnP relationship to 13 licenses. BSD3 and also GPLv2+ have CnP relationship to 6
licenses.

50

Table 6: Distribution of code fragments havingclone-relation to ﬁles under GPLv2+
License Name
#Fragments
GPLv2+
268
GPLnoVersion,GPLv2+,LinkException
225
BSD3
28
LibraryGPLv2+
20
Apachev2
4
LesserGPLv2.1+
4

Table 7: Number of code fragments and ﬁles#Fragments #File #Fragments/#File
BSD3
665
2181
0.304906
Apachev2
1983 16350
0.121284
GPLv2+
549
8160
0.067279

There are many open source licenses as described in Section
2, the developers of the OSS have to select a license fromthe many available. The result of the investigation may becontributory to license selection.
This experiment is a preliminary study. Therefore, we planto perform an experiment on a larger analysis target. It is
possible to detect CnP in larger source code because we cansplit a set of source code to decrease their size as possible
as to analyze by CCFinder, and merge these results. On
the other hand, identifying license of code fragment in large
object is also possible. Because Ninka analyzes ﬁles one by
one.

5.

4. DISCUSSION
In the result of Apachev2, there is large number of codefragments having CnP relationship to code fragments under
Apachev1.1. We believe that Apachev1.1 has been changing
to Apachev2 currently because Apachev1.1 is an old versionof Apachev2.
GPLv2+ has the smallest number of #Fragments/#File intable 7. This result shows that GPLv2+ is reused less frequently than BSD3 and Apachev2. We believe that codefragments under other licenses are copied into code underGPLv2+, however, there is little case that a code fragment
under GPLv2+ is copied into code under another license notin the GPL family. We believe the reasons are:• Copy-and-Pasting a code fragment under GPLv2+ tocode under another license except GPLv2+ and GPLv3
violates the condition of GPLv2+.
• Copy-and-Pasting a code fragment under Apachev2 orBSD3 in code under GPLv2+ is permitted.
• Copy-and-Pasting a code fragment under GPL family such as LesserGPL or “GPLnoVersion, GPLv2+,
LinkException” and changing their license to GPL ispermitted.
Code fragments under BSD3 or Apachev2 are reused more
frequently than code fragments under GPLv2+. We believethat it is easier to satisfy the conditions of the BSD3 or the
Apachev2 than these of the GPLv2+. In fact, code fragments under the Apachev2 have CnP relationship to codefragments under more licenses than code fragments under
the GPLv2+. Therefore, we suggest that code fragments
under Apachev2 are copy-and-pasted frequently into code
under another license.
In section 3.4, we shown that all licenses share the common
characteristic that code fragments under each of the own
license have the highest proportion in each result of investigations. We suggest that there are many cases that codefragments are copy-and-pasted to code fragments created bya developer in same development organization.

51

THREAT TO VALIDITY

It is possible that the result of the experiment depends
on the CnP detection capability of code clone detection
tool CCFinder[10]. We are motivated to use CCFinder inthe experiment because one of main application of code
clone detection tool is CnP detection, and the usefulnessof CCFinder is shown in Bellon’s benchmark[2]. As future
work, comparative experiments with other available code
clone detection tools (e.g., CP-Miner[12]) should be performed.
The result of the experiment also depends on the characteristic of metric LNR and its threshold value. We use themetric LNR to exclude language-dependent clones (e.g., repeated setter/getter invocations in Java programs). As future work, we should perform the experiments to show theeﬀect of threshold values of metric LNR. RNR[9] is anothermetric to exclude language-dependent clones. Currently, weare planning to perform the comparative experiment with
LNR and RNR.
Ninka is employed to identify the licenses of source ﬁles. We
believe that using Ninka is valid because the accuracy of
Ninka is good; In [7], recall was 82% and the precision was
96%.
However, Ninka cannot detect a license if a source ﬁle contains no description about license. In addition, Ninka also
cannot detect a license if the license is not registered in
the database. In this experiment, source ﬁles that Ninka
couldn’t detect their license are removed from the target ofdetecting CnP. Hence, source ﬁles which were not detected
their license didn’t inﬂuence results.
The analysis target is a small portion of source ﬁles in Debian GNU/Linux. Therefore, this result may include a lotof sampling error. For this reason, we believe that applying
this result to general OSS is not acceptable.

6.

CONCLUSION AND FUTURE WORKThis paper performed a preliminary study on impact of software licenses on CnP reuse. Open-source Java source codein Debian/GNU Linux was analyzed and classiﬁed basedon their license. In particular, copied code fragments that
relate to the source ﬁles distributed under 3-clause BSD license, Apache License version 2.0 or GPL version2 or lator
were analyzed.
The result of the experiment shows that most of the codefragments are copied to ﬁles distributed under same licenseor relative licenses that is designed by same organization.
On the other hand, comparing to BSD3 and GPLv2+, Apachev2
code fragments are copied into ﬁles that are distributed under a various licenses. By contrast, almost all GPLv2+ code
are copied between the ﬁles distributed under the GPL family licenses.
We are planning a large scale experiment. Especially, the all
source code and licenses in OSS products in Debian GNU/Linux
is a target of the experiment.
This paper focused on clone sets created by CnP. Thus, thedirection of copying is not identiﬁed. To clarify the true
impact of the license to copy-and-pasting, origin analysis isrequired to know the direction.
To identify the developing organization or the developer who
copied a fragment is also important to clarify the impact.
In this experiment, we didn’t discriminate between code
clone generated by copy-and-pasted and code clone generated by including library in source form. Discriminatingthese code clone, it will be clear that diﬀerence of an impactof license on their cases. Therefore, we plan to retrieve code
clone generated by including library’s source code using with
FCFinder[15].

7. ACKNOWLEDGMENTS
This work has been supported by Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Young Scientists(B) (No.21700031), and Grant-in-Aid for Research Activity
start-up (No.22800040).

8. REFERENCES[1] Apache Software Foundation. Apache license, version
2.0. http://www.apache.org/licenses/LICENSE-2.0
Accessed Oct 2010.
[2] S. Bellon, R. Koschke, G. Antoniol, J. Krinke, and
E. Merlo. Comparison and evaluation of clone
detection tools. IEEE Trans. Softw. Eng., 33(9):577–591, Sept. 2007.
[3] Debian Project. Debian gnu/linux.
http://www.debian.org/ Accessed Oct 2010.
[4] Debian Project. Debian policy manual.
http://www.debian.org/doc/debian-policy/
Accessed Oct 2010.
[5] Free Software Foundation. GNU general public license.
http://www.gnu.org/licenses/gpl.html Accessed
Oct 2010.
[6] D. M. German, M. Di Penta, and J. Davies.
Understanding and auditing the licensing of open
source software distributions. ICPC ’10, pages 84–93,
2010.
[7] D. M. German, Y. Manabe, and K. Inoue. A
sentence-matching method for automatic license
identiﬁcation of source code ﬁles. In ASE 2010, pages
437–446, 2010.
[8] R. Gobeille. The fossology project. In Proceedings ofthe 2008 international working conference on Mining
software repositories, MSR ’08, pages 47–50, New
York, NY, USA, 2008. ACM.

52

[9] Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue.
Method and implementation for investigating code
clones in a software system. Information & Software
Technology, 49(9-10):985–998, 2007.
[10] T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: A
multilinguistic token-based code clone detection
system for large scale source code. IEEE Transactions
on Software Engineering, 28:654–670, 2002.
[11] J. Li, R. Conradi, C. Bunse, M. Torchiano, O. P. N.
Slyngstad, and M. Morisio. Development withoﬀ-the-shelf components: 10 facts. IEEE Software,
26:80–87, 2009.
[12] Z. Li, S. Lu, S. Myagmar, and Y. Zhou. Cp-miner:ﬁnding copy-paste and related bugs in large-scale
software code. IEEE Trans. Soft. Eng., 32(3):176 –
192, March 2006.
[13] Open Source Initiative. The BSD license. http://www.opensource.org/licenses/bsd-license.php
Accessed Oct 2010.
[14] M. Ruﬃn and C. Ebert. Using open source software in
product development: A primer. IEEE Software,21(1):82–86, 2004.
[15] Y. Sasaki, T. Yamamoto, Y. Hayase, and K. Inoue.
Finding ﬁle clones in freebsd ports collection. In
Mining Software Repositories (MSR), 2010 7th IEEE
Working Conference on, pages 102 –105, 2010.
[16] W. Scacchi. Free/open source software development:
recent research results and emerging opportunities. In
ESEC/FSE 2007, pages 459–468, 2007.

Using Program Slicing Metrics for the
Analysis of Code Change Processes
Raula Gaikovina Kula, Kyohei Fushida, Norihiro Yoshida, and Hajimu Iida
Graduate School of Information Science, Nara Institute of Science and Technology
Takayamacho 8916-5, Ikoma, Nara 630-0101, JAPAN{raula-k,kyohei-f,yoshida}@is.naist.jp, iida@itc.naist.jp

A number of studies have outlined issues relating common
software process improvement assessment methodologies such as
CMMI[2] and ISO 9000 [3] [4] [5] [6]. Much of the issues relate
to cost of assessment and implementation, especially for small
software organizations [7]. In addition, these generic processes
assessments are sometimes tedious and not specifically tailored.
Other demotivators are higher management support, training,awareness, allocation of resources, staff involvement, experienced
staff and defined software improvement process implementation
methodology is critical for software process improvement [8].

ABSTRACTSoftware Process Improvement is increasingly becoming a major
activity for most software development organizations due to thebenefits seen in the cost and business value. Software processassessments, however, can be tedious, complicated and costly.
This research explores alternative assessments by analysis of finegrained processes with its related source code characteristics.
This approach attempts to propose program slicing metrics forcode changes in a software project. Using the wxWidgets
software project as the case study, through project artifacts suchas issue tracking system and change logs, this research explored
relationships between code characteristics and its fined grained
processes.

There has been several related work into trying to make themodels easier and better to use. Yoo [9] suggests a model thatcombines CMMI and ISO methods. Amburst [10] takes adifferent approach by treating software as manufacturing productlines, therefore making the processes systematic and generic.
An alternative measure of software processes can be done throughthe inspection of process execution histories. Performed at thedeveloper’s level, these measures are referred to as fine-grained
processes ‘micro processes’. Related research has been done by
Morisaki el al [11]. This approach analyzes the quality of finegrained processes by studying the process execution histories
such as change logs. This is called Micro Process Analysis (MPA).
Quality of the process is measured by the execution sequence andoccurrences of missing or invalid sequences.

This research contributes to the development of assessment tools
to assist with Software Process Improvement. It opens
possibilities for assessment tools for fine-grained software
processes.

Categories and Subject Descriptors
D.2.8 [Software Engineering]

Program Slicing is a concept first described by Weiser [12] as amethod to study the behavior of source code through the flow
dependency and control dependency relationship amongstatements. Program slicing metrics can be utilized various
applications such as software inspection, which can be used toreduce defects at a fine-grained level [13]. Other related works
have used program slicing metrics to classify bugs. Pan et. al. [14]showed that program slicing metrics work as well as conventional
bug classification methodologies.
This research proposes
program slicing based metrics to describe code changes.

General Terms
Experimentation

Keywords
Program Slicing, Code Change Process, Micro Process Analysis

1. INTRODUCTION
1.1 Background and Related Works

Combining both fields, our research aims better understand finegrained software process by studying MPA and their code change
characteristics using program slicing techniques. Our previous
research with MPA and program slicing techniques [15] had
focused particularly on the bug fixing process and analyses of the
program slicing metrics were performed at file level. The research
indicated that there is indeed a relationship between how the
micro processes are executed and code-based characteristics suchas McCabe’s Cyclomatic Complexity (CC) [16] and lines of code
(LoC).

The related works are divided into two parts 1) Software Process
Assessment and 2) Program Slicing.
Improvement of software processes in software development isseen as a major activity for larger software organizations as
benefits are seen in the cost and business value of improvement
efforts, as well as the yearly improvement in productivity ofdevelopment, early defect detection and maintenance, and fastertime to market [1].

53To understand the micro processes behind code fixes we
inspected the workflows of how fixes and changes are
implemented in a software project. Inspecting the workflow of thebugs and patches in the tracking system we can be able to groupand categorize code changes. Since each project has its own
tailored workflow, we used workflows tailored to the project.

1.2 Research Objective
Our motivation is to present a simple alternative model forsoftware process improvement at the micro level. Current models
of process assessment are at the software life cycle level andrequire complicated assessments with highly trained assessors.
More specifically, this research is part of a proof of concept
towards a prediction model based on source code properties.

2.2 Characterization of Code Changes using
Program Slicing Metrics.

Building from our previous works [16][18], this paper explores
program slicing metrics specifically at function level, with the aim
to improve from our work by only including functions edited
during a code change. Also previous works focused on bug fixes
and the bug fixing process, however, it was found that bug fixes,
enhancements and patches are not clearly categorized. Therefore
this research we broadened our scope to all code changes and themicro processes that they follow.

To assess the bug characteristics, program slicing metrics are usedin this approach to describe code change characteristics. This
research looks to use program slicing as measure of the codechanges.
In this research we refer to editedfunction as functions that areedited during a code change. This is the criterion of the programslice. Back slice functions of a program slice as functions that theedited function is dependent on. For forward slice functions werefer to functions that the edited function has an effect on. This is
illustrated in Figure 1 below.

Based on our objective and considering code characteristics are
the properties of a program slice, we formulated and tested thefollowing research questions: RQ1: Do Code changes with similar micro process execution
have similar code characteristics?

CodeChangeAnalysis
Function

BackSlice RQ2: Are Program slicing metrics useful when finding a
relationship between code change processes and codecharacteristics?

Function

Section 2 presents the methodology as well as the proposed
approach. Section 3 then explains the experiment using theapproach and tools to carry out the experiments. Section 3 alsopresents the results of the experiments. Section 4 is a discussion
and analysis of the results as well as future work. Finally, section
5 outlines the conclusion.

Source+Code

Function
Edited+Function

Function
Edited+functions+
during+a+Code+Change

2. METHODOLOGY
2.1 Code Change Processes

ForwardSlice

Function

Function

Figure 1. Example of BackSlice and ForwardSlice for a
program slice

This research focuses on the day to day processes performed in
the development of software. This paper limits its data collectionof code change information from the following two repositories:

2.3 Code Change Extraction and Analysis

1) Issue Tracking Repository

The analysis of the code change process includes 3 steps: 1) microprocess extraction and analysis and 2) code based metrics
extraction and analysis, and 3) grouping and comparing data.
Details of each step are described as follows:

Typically a software development team uses a system to manage
bugs and patches in a medium to large scale project. Trac is awiki and issue tracking system Trac is used to track progress ofany type of changes to the source code. This research utilized theTrac Management System 1 to help track all the code changes in asoftware project.

1) Micro process extraction and analysis:
This step involves data mining and extraction of code chance
related attributes from both the source code repository and theissue tracking system. From the source code repository for eachfix, the functions that were edited were extracted along with thedate of edit. During the extraction, the exact affected functions are
retrieved by comparing the fixed change set revision against theprevious revision.

2)Source Code Repository
The source code repository refers the system manages changes tosource code in a software project. The two main system used is
the Subversion (SVN) and Concurrent Versioning System (CVS).
For this research, both SVN and CVS repositories were used togather data on bug characteristics.

2) Code Based Metrics:
This step involves analysis of the code using the program slicing
metrics. The following explains in detail how each metric wasused to for bug classification. Our previous work [17] used1

http://trac.edgewall.org/

54

Figure 2. The micro process workflow of code change in wxWidgets ( http://trac.wxWidgets.org/wiki/wxTracWorkflow).
Cyclomatic Complexity (CC) and Lines of code (LoC) as bug
characteristic metrics. These two metrics were originally chosen
as CC would be an attempt to measure the complexity of thefunction and LoC to measure the size of the change. In thisresearch we use CC, however, we replaced LoC with counting thenumber of functions as a similar measure of size. Also we havesome non-program slicing metrics to compare effectiveness.

Equation 4 states that NumEditFunc is the total number of edited
functions. This metric is used to count how many functions areedited in a code change. This is non program slicing metric.
x Number of Back and Forward Slice functions:

BackSliceC ount

f

(5)

f

(6)

f backslice

The follow metrics were proposed and used:

FunctionSl iceCountx Edited Function CC:
This is a non-program slicing metric.If editedfunction is defined
as a set of functions that were edited during a code change andCC(f) is the Cyclomatice Complexity (CC) of a function,
EditedFuncCC metric is defined as:

EditedFunc CC

 CC ( f )f editedfunc tionf  forwardSli ce

Equations 5 and 6 illustrate that by taking the cardinality of the
backSlice and forwardSlice in relation to the editedfunction, we
can count how many functions were associated with the codechange. This metric is used to count the functions that are either
depend and are dependent on a code change.

(1)3) Groupings and comparing data:x Back and Forward CC slice functions:

After grouping the code changes based on their micro process
execution we applied the metrics formulated in the previous step.
We then analyze to find trends and relationships between microprocess execution and the metrics.

Equations 2 and 3 show the calculation of how a backSliceCC and
fwdSlice is calculated. As explained in Figure 1, BackSlice andforwardSlice results of when each editedfunction is sliced to findits depending and dependant functions. The CC for all associatedfunctions for all editedfunctions are combined to give the resultant
CC for the code change.

BackSliceC C

3. CASE STUDY: WXWIDGETS

f  forwardSli ce(3)

To test the methodology we conducted our case study using theOpen Source Software wxWidgets 2 WxWidgets is a C++ librarythat lets developers create applications for Windows, OS X, Linuxand UNIX on 32-bit and 64-bit architectures, as well as several
mobile phones platforms including Windows Mobile, iPhone
SDK and embedded GTK+.

editedfunc tion

(4)

The program slicing tool CodeSurfer [18] was used to generate
the program slices. Our java based extraction tool acted as a web
spider searching and parsing the online data repositories. Data CC ( f )(2)f backSlice

FwdSliceCC

 CC ( f )x Number of Edited Functions:

NumEditFun c

255

http://www.wxWidgets.org/

was extracted from the wxWidgets Trac system and source code
repository. 3

follow the trend as code changes with more than three changes
have lower BackSliceCC edited. As seen, there is a trend that as
the number of status changes increases with CC.

3.1 Findings

Figure 5 also suggests the correlation between the change status
count and the number of functions edited. Similar to the CC
metrics, it seems the number of functions increase as the numberof times a status changes increase. Furthermore, with the program
slicing based metrics BackSliceCount and ForwardSliceCountalso support the trend.

3.1.1 Data Extraction and Selection
We analyzed wxWidgets version 2.8.11 (as of 04/16/2010) which
had a size of 620389 lines of code containing 23203 functions.
Using our data extraction tool we analyzed 660662 change sets
(Revision changesets 1 – 64005). The criteria for change set
selection was based on the following factors 1)The code fix was
linked to the wxWidgets Trac, therefore having a issue
identification number and 2).The code fix contained functions thatexisted in the wxWidgets version that was sliced. 507 change setspassed this criteria and therefore used for analysis.

4. DISCUSSION
4.1 Threats to Validity
Firstly the main threats to validity would be the accuracy of thedata extracted as well as statistical analysis of the groupings. Stillas a proof of concept, we are more interested in a correlation
between program slicing metrics and micro processes. It isenvisioned that once a reliable set of metrics is found, further
methods of statistical tests can be applied to prove the validity ofthe data. We also hope to test across more different software
projects.

3.1.2 Micro Processes of Code Changes

CodeChangeStatusCountno+changes

One

Two

Three

Four+or+More

4%

Another threat is that the data analyzed are related to the software
release version analyzed. In addition, CodeSurfer does not handle
interface related code. When performing the data extraction, weonly realized that out 660662 change sets, only 500 code sets
were related to the version that we are analyzing. This is probably
due to disappearance of functions or files or interface related codechanges.

13%
11%

50%
22%

Finally code changing workflows are tailored specific therefore
the status counts and complexity of micro processes will differ
from organization to organization.
Figure 3. Status change for code change

4.2 Evaluation

Figure 2 illustrates the workflow used by wxWidget developers
when dealing with a code change, this is regardless of being a bug
or a patch or an enhancement model. Using this model we can see
the states of the process of implementing a new code change. Thechange states are: new, confirmed, closed, reopened, info_needed,
port needed and new info_needed new. As shown in Figure 3
using our extraction tool we were able to for each fix, find thenumber of status changes.

When looking at the workflow of wxWidgets in Figure 2, theworkflow seems to be tedious it can be assumed that since 50%
just use one state change, it does contradict the need for such acomplex workflow.
Another interesting discussion point is the determination of thecomplexity of a code change based on its code changes.
According to normal micro process analysis (MPA) [11] a normalchange entails the following sequence: 1) reporting andconfirmation of an issue, 2) assignment to developers, 3) Testing
and applying code changes 4) closing of the issue. Findings
however, suggest maybe the steps maybe be skipped. Causes
could be single developer assignment and working on codechange, being a simple fix or such events are not reported into thesystem. Further work will involve further investigation of theexact type of status change and to identify what are the ‘normal’state change for a typical code change.

3.1.3 Grouping and comparing Code Changes
Using the grouping of the status counts as outlined in Figure 3, wethen applied our proposed program slicing metrics. The results areillustrated in both Figures 4 and 5.
Figure 4 shows the proposed metrics used to compare andmeasure the sum of the CC of the functions affected. Startingfrom the left, the first graph shows the sum of the CC of thefunctions. However, when looking at the other two graphs, theprogram slice metrics for BackSliceCC in particular does not3

When applying the proposed metrics to the code changes basedon their status counts we found an interesting correlation.
Although not statistically proven, the number of functions
increases as the change status increases. This was even evident in
non-program slicing metrics of sum CC of edited functions andnumber of edited functions. Again further work is proposed toinvestigate

http://trac.wxWidgets.org/ andhttp://svn.wxWidgets.org/viewvc/wx/wxWidgets/

56

30

Code Change editedfunction CC

Code Change BackSlice

Code Change FowardSlice

25
20
15
CC

CC

CC

80
70
60
50
40
30
20
10
0

10
5
0

no
changes

one

two

no
changes

three four and
more

one

two

300
250
200
150
100
50
0

three four and
more

no
one
changesNumber of change status

number of status change

twothree four andmorenumber of status change

Code Change editedfunction Countnochangesone

twothree four and
more

100
90
80
70
60
50
40
30
20
10
0

Code Change BackSlice Count

250

Code Change ForwardSlice Count200
functions

100
90
80
70
60
50
40
30
20
10
0

f unctions

f unctions

Figure 4. Graphs showing the CC of edited and program sliced functions grouped by status count of code change

150
100
50

no
changesone

number of change status

twothree four and
more

0
no
one
changesnumber of change status

twothree four andmorenumber of status change

Figure 5. Graphs showing the number of edited and program sliced functions grouped by status count of code change

this further. However this correlation is not consistent with the
CC metrics as seen with ForwardSliceCC. Again further casestudies and other metrics may be proposed to better evaluate thesetrends.

Further investigation will be performed to find out the exact statechanges. Moreover, formulating and testing additional program
slicing metrics. Once usable metrics are established, othersoftware projects can be used as case studies.

4.3 Testing Hypothesis and Future Work

5. CONCLUSION

When referring to the research questions RQ1 was proven correct
as we see a relationship between the complexity of the microprocesses and the program slicing metrics of the affected code.
Results showed that for RQ2, more current results have mixed
results as BackSliceCC did not follow a relationship. However it
may be due to being a bad metric as other program slicing metrics
showed the trend. Therefore RQ2 still is not fully proven to betrue.

The main objective of the research is to provide a proof ofconcept that there is indeed a relationship between a code change
attributes and how its related processes are executed. The results
suggest there is a correlation between how much of thecomplexity of the micro process and its program slicing metrics.
Further work is proposed to refine the metrics as well as test on
other similar software projects.
It is envisioned that the research will contribute to a better
understanding and classification of code changes based on thenature of code, therefore using the nature of the code to suggest
improvement of software processes at the micro level.

In regards to the objective, this research contributes to thefeasibility of the relationship of micro processes of code changes
and their code based characteristics. This can be implemented bya framework that will help assist developers identify code changes
that have a high likelyhood of having complicated microprocesses.

ACKNOWLEDGMENTS
Special thanks to Shinji Kawaguchi for his contribution to thisresearch in MPA. This work is being conducted as a part of the
StagE project, The Development of Next-Generation IT
Infrastructure, supported by the Ministry of Education, Culture,

This work is showing promise as it agrees with previous work that
there is a correlation between code-based characteristics and
MPA.

57

9001:2000 and CMMI by ISO-certified organizations", The
Journal of Systems and Software 79, n.7, pp. 954-961, 2006.

Sports, Science and Technology. This research was also
supported by Japan Society for the Promotion of Science, Grantin-Aid for Scientific Research (No.22500027), and Grant-in-Aid
for Research Activity start-up (No.22800040 and 22800043).

[10]. O. Armbrust, M. Katahira, Y. Miyamoto, J. Münch, H.
Nakao, and A. O. Campo, "Scoping software process lines",
Softw. Process , v.14, n.3, pp.181-197, May, 2009.

REFERENCES[1]. J. Herbsleb, A. Carleton, J. Rozum, J. Siegel and D. Zubrow,"Benefits of CMM-Based Software Process Improvement:
Initial Results", (CMU/SEI-94-TR-13). Pittsburgh, Pa.:
Software Engineering Institute, Carnegie Mellon University,
1994.

[11]. S. Morisaki and H. Iida, "Fine-Grained Software Process
Analysis to Ongoing Distributed Software Development", 1stWorkshop on Measurement-based Cockpits for Distributed
Software and Systems Engineering Projects (SOFTPIT 2007),
pp.26-30, Munich, Germany, Aug., 2007.

[2]. K. K. Margaret and J. A. Kent, "Interpreting the CMMI: A
Process Improvement Approach", Auerbach Publications,(CSUE Body of Knowledge area: Software Quality
Management), 2003.

[12] M. Weiser, "Program slicing", In Proceedings of the 5thInternational Conference on Software Engineering. (ICSE).
IEEE Press, Piscataway, NJ, pp.439-449, Mar. 09 - 12, 1981[13]. P. Anderson, T. Reps, T. Teitelbaum, M. Zarins, "ToolSupport for Fine-Grained Software Inspection," IEEE
Software, pp. 42-50, July/August, 2003

[3]. C. H. Schmauch, "ISO 9000 for Software Developers", 2nd.
ASQ Quality Press, 1995.

[14]. K. Pan, S. Kim, E. J. Whitehead, Jr., "Bug Classification
Using Program Slicing Metrics", Source Code Analysis andManipulation, IEEE International Workshop, pp.31-42, 2006[4]. S. Beecham, T. Hall and A. Rainer, "Software processproblems in twelve software companies: an empiricalanalysis", Empirical Software Engineering, v.8, pp. 7-42,
2003.
[5]. N. Baddoo and T. Hall, "De-Motivators of software process
improvement: an analysis of practitioner's views", Journal of
Systems and Software, v.66, n.1, pp. 23-33, 2003.

[15]. R. G. Kula, K. Fushida, S. Kawaguchi, and H. Iida,͆Analysis of Bug Fixing Processes Using Program Slicing
Metrics,'' in Product-Focused Software Process Improvement
PROFES 2010, vol. LNCS 6156, pp. 032-046, June 2010.

[6]. M. Niazi, M. A. Babar, "De-motivators for software process
improvement: an analysis of Vietnamese practitioners' views",
in Product Focused Software Process Improvement PROFES
2007, LNCS, v.4589, pp. 118-131, 2007.

[16]. A. Watson and T. McCabe, "Structured testing: A testing
methodology using the cyclomatic complexity metric",
National Institute of Standards and Technology, Gaithersburg,MD, (NIST) Special Publication, pp.500-235, 1996.

[7]. J.G. Brodman and D.L. Johnson, "What small businesses andsmall organizations say about the CMMI", In Proceedings ofthe 16th International Conference on Software Engineering(ICSE), IEEE Computer Society, pp. 331 – 340, 1994[17]. R. G. Kula, ``Using Program Slicing Metrics for the
Analysis of Bug Fixing Processes,'' Master thesis, Institute of
Science and Technology, Nara, Japan, 2010.
[18]. P. Anderson , M. Zarins, "The CodeSurfer Software
Understanding Platform", Proceedings of the 13th
International Workshop on Program Comprehension, pp.147148, May 15-16, 2005[8]. A. Rainer and T. Hall, "Key success factors for implementing
software process improvement: a maturity-based analysis",
Journal of Systems and Software v.62, n.2, pp.71-84, 2002.
[9]. C. Yoo, J. Yoon, B. Lee, C. Lee, J. Lee, S. Hyun and C. Wu,"A unified model for the implementation of both ISO

58

Flexibly Highlighting in Replaying Operation History
Takayuki Omori

Katsuhisa Maruyama

Dept. of Computer Science
Ritsumeikan University
Kusatsu, Shiga, Japan

Dept. of Computer Science
Ritsumeikan University
Kusatsu, Shiga, Japan

takayuki@fse.cs.ritsumei.ac.jp

maru@cs.ritsumei.ac.jp
determine how highlights are drawn by switching existinghighlight plug-ins or creating new ones. Accordingly, theextended version of OperationReplayer facilitates his/her
examination of operation history.

ABSTRACTIn empirical software engineering, historical information ofsoftware development is one of significant facets since knowledge
derived from such information can improve quality of software
product and development process. In these years, several tools
recording actual operations on integrated development
environments have been proposed. They are promising for
improving correctness of examining operation history. However,
it is necessary to narrow a range of targets to be examinedbecause of variety and massiveness of recorded operations. We
proposed OperationReplayer which supports examining operation
history by enabling to replay past operations as if they are been
performing right now. This paper proposes a highlight plug-in,which extends OperationReplayer. Users can rapidly identify
target operations of their examinations by using their own
highlight plug-ins. This paper also describes a case study to show
usefulness of the proposed flexible highlighting.

2. OperationReplayerThis section describes an examination task of operation history byusing OperationReplayer. The highlight plug-in mechanism isalso described.

operation
history
restored+source+code

Categories and Subject Descriptors
D.2.6 [Software Engineering]: Programming Environments –
integrated environments.

control+buttons

General Terms

time&line+bars

Experimentation, Management, Human Factors.

Keywords

Figure 1. Screenshot of extended OperationReplayer

Software evolution, Integrated development environment, Finegrained changes, Software process analysis.

2.1 Examination of Operation History

1. INTRODUCTION

Figure 1 shows a screenshot of the extended version of
OperationReplayer. Appearance of the window is similar between
the original and extended one.

In empirical software engineering field, analyzing history ofsoftware development is an essential approach to improve
software quality and productivity. Several methods for recording
actual operations on integrated development environments (IDEs)
have been proposed[1-3]. Since the methods enable replaying
recorded operations, we can examine them and attain precise
historical information. However, such examination is fault-prone
and time-consuming because of variety and massiveness ofrecorded operations. To address this problem, this paper proposes
flexible visual abstraction in addition to simply replaying past
operations. This work promotes our previous work of
OperationReplayer[1] and introduces plug-in mechanism to it for
constructing a flexible time-series visual summary called ahighlight. A user (who replays past edits) can easily identify
noteworthy operations by seeing highlights on time-line bars, if
the prepared highlights are appropriate for his/her purpose. The
original OperationReplayer provides static drawing of highlights.
On the other hand, its extended version allows the user to

A user can replay past operations in a single source file on asingle replayer window. He/she can change the focal time bypushing control buttons, selecting an operation from the operation
history, or specifying the time on the time-line bars. The content
of source code is restored in conjunction with the focal time. For
the two time-line bars, the upper one denotes a project life-time,
and the lower one shows detailed information within a specified
time-period of the project life-time. In the extended
OperationReplayer, these time-line bars are drawn based on ahighlight plug-in the user constructs.
We assume that an operation-history examination is iteratively
performed with different views. This is because operation historyis versatile. Determining a suitable highlight is difficult and needs
a number of trials-and-errors. Therefore, the user repeats
installing (switching and creating) his/her highlight plug-in andreplaying operations to examine them. After doing iterative
processes, he/she attains visual abstraction (highlights) more

59

suitable for his/her purpose. Thus, flexible highlighting isessential for the examination of the operation history.

2.2 Highlight Plug-in
too+many+highlights+(in+40+min.)A highlight plug-in is implemented as an extension forhighlightPoint extension point of OperationReplayer. Using
APIs provided by OperationReplayer, the plug-in can accessvarious kinds of information on recorded operations, such as thetime when the operation was performed, the name of thedeveloper who performed the operation, the deleted/inserted
string, and the offset where the operation was performed.
Moreover, OperationReplayer provides APIs for accessing any
snapshot of source code in the past and its syntactical information.
To display highlights on the time-line bars, the plug-in
instantiates SpotHighlight and/or RangeHighlight.
These instances are responsible for drawing lines and rectangles
corresponding to times and time-periods specified on the time-line
bars.

(a) Highlights including many noises (1st trial)

six+refactorings (blue+highlights)(b) Detecting intensive refactoring operations (3rd trial)
Figure 2. Case study
To assess that the highlight plug-in is truly improved through thisexperiment, we manually examined operations around intensive
highlights reported by the highlight plug-ins in 2nd and 3rd trials.
Actually, we intuitively extracted several time-periods based on
our understanding for the reported highlights, and then checked if
each period involves true refactorings. We did not examine
highlights reported in the 1st trial since it created too many
worthless highlights.

3. Case Study
To show usefulness of flexible highlighting proposed here, wehave created a highlight plug-in and used it to examine actual
operation history. In this case study, the purpose of thisexamination is to distinguish periods for intensive refactoringfrom ones for other modifications. We checked if the createdhighlight plug-in has been improved in three trials.

As a result, in the 2nd and 3rd trials, the highlight plug-in totally
detected 66 and 47 refactoring periods, respectively. In both thetrials, 16 true refactoring periods were detected among them.
Besides, 50 and 31 faulty periods were respectively reported. The
precision rates are 24% (16/66) and 34% (16/47), respectively.
From these experimental results, the precision was improved withlittle effort (inserting and deleting source code) although theexperiment is quite limited. Here, we were supposed to count the
total number of periods for real refactorings within thedevelopment and show recall rates in this experiment. However,
we could not precisely count it due to vast numbers of recorded
operations.

1st trial: In the operation history, all refactoring operations
invoked by Eclipse's menu items are held as instances of
TriggeredOperations. The initial plug-in simply creates
SpotHighlight instances corresponding to the operations,which are colored with blue (blue highlights). In addition, alloperations that delete any character (the length of the deleted text
is not zero) are colored with cyan (cyan highlights). The highlightplug-in has 49 lines of source code. We applied this highlightplug-in to all operations recorded in real software development.
As a result, the plug-in created a large number of highlights
including noises shown on the window. The noises obscured true
refactorings. Figure 2(a) shows a part of the time-line bar
resulting from this trial.

4. Conclusion
This paper proposed an operation replayer with a mechanism
supporting flexible highlighting. It allows users to flexibly change
visual abstraction of operation history on a window ofOperationReplayer. We are planning to extend it to effectively
treat histories of multiple source files and developers. Enhancing
flexibility and scalability of visualization is also future work.

2nd trial: To reduce the noise, we removed the cyan highlights (asingle line of source code was deleted). Instead, to detect move
operations of fields and methods which are frequently done inrefactorings, cut and paste operations are colored with red andorange, respectively (six lines of source code were inserted). We
applied this new version of the plug-in to the same recorded
operations. The result was better than one in the 1st trial; however
it still includes many noises. By replaying operations aroundseveral blue highlights, we found some of the highlights involve"organize/add imports" operations that do not seem tobe refactorings.

5. REFERENCES[1] Omori, T. and Maruyama, K. 2009. Identifying Stagnation
Periods in Software Evolution by Replaying Editing
Operations. In Proceedings of 16th Asia-Pacific Software
Engineering Conference, 389-396.
[2] Robbes, R. and Lanza, M. 2007. A Change-based Approachto Software Evolution. Electronic Notes in TheoreticalComputer Science (ENTCS), 166:93-109.

3rd trial: To further reduce noisy highlights, we improved thealgorithm related to blue highlights. Finally, the plug-in detects
operations of which labels are same as Eclipse's "Refactor"
submenu items and colors them with blue (ten lines of sourcecode were inserted). Applying this plug-in, we detected a possible
refactoring period with intensive blue (deeply colored) lines
shown in Figure 2(b). Each of these lines indicates a "rename"refactoring operation.

[3] Hattori, L., Lungu, M., and Lanza, M. 2010. Replaying Past
Changes in Multi-developer Projects. In Proceedings of
IWPSE-EVOL 2010, 13-22.

60