Classification of Java Programsin SPARS-J

Kazuo Kobori, Tetsuo Yamamoto,
Makoto Matsusita and Katsuro Inoue
Osaka University

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

1

Contents
Background
SPARS-J
Reuse

Similarity measurement techniques
Characteristic metrics method
Inclusive relation method

Examples of its application
Summaries and Future Works

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

2

Background
SPARS-J is the web-based search engine forsupport of Software Reuse (for Java)A lot of parts are managed in this systemsource codes from open-source projects and public access files
repository which stores 130,000 classes

Components are classified by functions.
In order to evaluate use-relation of every function
Similar components may have the same functions

Measurement of similarity between Components is needed.

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

3ReuseSimilar components are made by Reuse
Reuse is roughly divided into following two:
1. Reused as it is.
Components are copied and used as it is.
Some elements may be changed.

2. Reused by changing code.
Components are copied and used with additional
codes.
Some methods and some variables are mainly added.

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

4

Similarity measurement technique
Character string comparisonhas so far been used for similar comparison of programs
the high analysis cost per one comparison
Hugeness of the total number of times of comparison

It is unsuitable for SPARS-J

We need much lower cost method
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University5Similarity measurement techniquein SPARS-J
Characteristic metrics method
In order to grasp Reuse as it isMetrics show the constitution of a component
Metric is integer
Only comparison of metrics is used for a similarity measurement
reduction of calculation cost

Inclusive relation method
In order to grasp Reuse by minor change
By using the code clone information between components, weanalyze inclusive relation
It has a scalability which can bear practical analysis.
Analysis against millions of lines in practical time.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

6

Characteristic Metrics
Characteristic metrics is measured from twoviewpoints.
Complexity
number of methods, cyclomatic number, and etc.
It shows a structural characteristic.

Token-composition
number of appearances of each token.
Token ＝ Reserved + Symbol + Operator + Identifier（96 types）
（49）
（9）
（37）
（１）
It shows a surface characteristic.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University7Extraction of Characteristic Metrics
public class sample {int a , b , s ;char c ;value

N of Cyclomatic

2

N of method
・・・

public void main ( ) {c=‘m’;
if ( c = = ‘ m ’ ) {s = sum ( a , b ) ;}else {s = a + b;}

Complexity

N of interface

Token

Value

int

public void sum ( int p , int q ) {return ( p + q ) ;}}・・・void

identifer
TtotalSoftware Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University8Extraction of Characteristic Metrics
public class sample {int a , b , s ;char c ;valueN of Cyclomatic

2

N of method

2

N of interface

Token・・・・・・

public void main ( ) {c=‘m’;
if ( c = = ‘ m ’ ) {s = sum ( a , b ) ;}else {s = a + b;}

Complexity

Complexity
metrics

0Valueint

public void sum ( int p , int q ) {return ( p + q ) ;}
}

・・・

void

identifer
TtotalSoftware Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

9Extraction of Characteristic Metrics
public class sample {int a , b , s ;char c ;2N of method

2・・・Token

Complexity
metrics

0

N of interface

Valueint3

void

2identifer

23

Ttotal75・・・}

N of Cyclomatic・・・

public void sum ( int p , int q ) {return ( p + q ) ;}value・・・

public void main ( ) {c=‘m’;
if ( c = = ‘ m ’ ) {s = sum ( a , b ) ;}else {
s = a + b;}

Complexity

Token
composition
metrics

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

10Judge Condition -1Step1: We set thresholds of each complexity metrics
Metricthreshold

N of Cyclomatic0

N of methods

1

N of method calls

2

Nesting depth

1

N of classes

0

N of interfaces

0

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

11Judge Condition -1We make hash key byComplexity metrics
Hash Key ＝(24bit)

8bit

8bit

8bit

metricA

metricB

metricC

If we judge new component P Hash Key of Cp.P＝[10.62.125]
 Thresholds of metric[A,B,C]＝[0.0.1][10.62.124][10.62.125] We search these 3 keys
[10.62.126]
We make Hash Table in which Hash Key
corresponds to components[ 0. 0. 0]= null・・・[ 10. 62.124]= Cp.A
[ 10. 62.125]= Cp.B，Cp.C[ 10. 62.126]= null・・・[254.254.254]= Cp.Z

We now similarity components
down to Component A , B and C.

DBSoftware Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

12

Judge Condition -2Step2 : Components are judged by characteristic metrics
Component

22identifer

2325

Ttotal7576

・・・void・・・B4・・・Token
Composition
MetricsintA
3■D(A,B): Non-similarity between Component A and B
The sum of the difference of TCM

D(A,B)diff(A,B)
min(Ttotal（A）, Ttotal（B）)＜ threshold

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

13Pattern of Reuse
1. Reused as it is.
It can be extracted by judging similar components.

2. Reused by changing code.
It can be extracted not by judging similar components,
but by detecting inclusive relation.

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

14Pattern of Reuse
1. Reused as it is.
It can be extracted by judging similar components.

2. Reused by changing code.
It can be extracted not by judging similar components,
but by detecting inclusive relations.

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

15

Inclusive relation
In characteristic metrics method
One component contains another component completely.
However, If the difference of size is more than thethreshold.
In this case, these two components can’t be judged to besimilar.

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

16Inclusive relation method
In order to grasp reuse with code addition
By using the code clone information
between components, we analyze inclusive
relation
Use of a code clone detection tool ：｢CCFinder」*
It has a scalability which can bear practical analysis.
– Analysis against millions of lines in practical time.

*Toshihiro Kamiya, Shinji Kusumoto, and Katsuro Inoue, "CCFinder: A Multi-Linguistic Tokenbased Code Clone Detection System for Large Scale Source Code," IEEE Trans. Software
Engineering, vol. 28, no. 7, pp. 654-670, (2002-7).
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

17

The Inclusive Relations
in Software Components
About Component x:

Δ←threshold

Total Line of Codes of x ＝ LOC(x)The Number of Lines of x which is also contained incomponent y as a code clone ＝ Cy(x)x⊆y ⇔LOC(x)× Δ ≦ Cy(x)Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

18

The Extraction Method ofInclusive Relation -1Step 1: Code clone pair information iscalculated through analysis of CCFinder.
Clone pair informationcomponents

CCFinder・・・・・・・

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

19

The Extraction Method of
Inclusive Relation -2Step2: For each component X, check this formulax⊆y ⇔LOC(x)× Δ ≦ Cy(x)Component X

Component Y
Code Clone

overThreshold?
yesX⊆Y

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

20

The Extraction Method ofInclusive Relation -3Step３: By comparing metrics, this judges
whether the extracted pair is an inclusive
relation.
metric3void2

identifer

23

Ttotal75＜ 4＜ 2＜＜ 40＜ 102・・・int・・・

Cp.Y・・・

Cp.X■Cp.X ⊆ Cp.Y
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

21

Application Result
Characteristic metrics method
We show the cost scale figure

Inclusive relation method
We show some examples which are in inclusive
relation

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

22

Application Result -1■ calculation time of Characteristic Metrics Method
654秒

sec32
1001000

2000

3000
4000
Number ofComponents
部品数50006000※calculation time of characteristic string method = 24.3 sec (at 500 components)
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

23

Application Result -2■ Example of a extracted inclusive relation
PipedReader⊆void receive( )int read( )PipedInputStream
void receive( )Code Clone

int read( )void close()void close()void connect()void connect()

LOC: 131

int available( )LOC: 142

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

24

Application Result -2■other Examples of a extracted inclusive relation
SocketPermission
PropertyPermission⊆LOC:135

LOC:457

FilePermmission
LOC:249

Format
LOC:25⊆

NumberFormat
LOC:207

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

25Summary And Future Work
Summary
We have suggested similarity measurements
Characteristic metrics method
Inclusive relations method

Future Work
Evaluation of system performance
Adjustment of a threshold

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

26