ICECCS 2017

Exploring Similar Code- From Code Clone Detection to Provenance Identification -Katsuro Inoue
Osaka University

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

My Background
FormalPh.D. for
Implementation& Optimizationof Functional
Programs

84’90

Empirical

SoftwareProcess
Modeling &Formalization

ProgramSlicing

Mining Soft.
Repositories,
Code Clone,
Code Search

’95

’00

’05

’10

Code
Provenance,
LicenseAnalysis’15 ’17

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

Welcome to ICECCS 2017
The 22nd International Conference on Engineering ofComplex Computer Systems (ICECCS 2017) will be held on
November 6-8, 2017, Fukuoka, Japan. Complex computer
systems are common in many sectors, such as manufacturing,
communications, defense, transportation, aerospace,hazardous environments, energy, and health care. Thesesystems are frequently distributed over heterogeneous
networks, and are driven by many diverse requirements on
performance, real-time behavior, fault tolerance, security,
adaptability, development time and cost, long life concerns,
and other areas. Such requirements frequently conflict, andtheir satisfaction therefore requires managing the trade-offamong them during system development and throughout theentire system life. The goal of this conference is to bring
together industrial, academic, and government experts, froma variety of user domains and software disciplines, todetermine how the disciplines' problems and solution ...
3

Welcome to ICECCS 2017
The 22nd International Conference on Engineering ofComplex Computer Systems (ICECCS 2017) will be held on
November 6-8, 2017, Fukuoka, Japan. Complex computer
systems are common in many sectors, such as manufacturing,
communications, defense, transportation, aerospace,hazardous environments, energy, and health care. Thesesystems are frequently distributed over heterogeneous
networks, and are driven by many diverse requirements on
performance, real-time behavior, fault tolerance, security,
adaptability, development time and cost, long life concerns,
and other areas. Such requirements frequently conflict, andtheir satisfaction therefore requires managing the trade-offamong them during system development and throughout the
Average:entire system life. The goalof this2.3%
conference is to bring
together industrial, academic,
and 6.8%
government experts, fromICECCS:a variety of user domains and software disciplines, todetermine how the disciplines' problems and solution ...
4

5

#include <stdlib.h>#include <stdio.h>#include <ctype.h>
int main() {int tot_chars = 0;/* total characters */int tot_lines = 0;/* total lines */int tot_words = 0;/* total words */int boolean;/* EOF == end of file */int n;
while ((n = getchar()) != EOF) {tot_chars++;
if (isspace(n) && !isspace(getchar())) {tot_words++;}
if (n == '¥n') {tot_lines++;}if (n == '-') {tot_words--;}}
printf("Lines, Words, Characters¥n");printf(" %3d %3d %3d¥n", tot_lines, tot_words, tot_chars);
return 0;}
6

Similarity of Code Snippets

7

Library C
Program A

∂

∂

∂
∂

System X∂

System Y

Program B

∂

∂

∂ ∂

System Z

8

Matters?

9Library C
Program A

∂

∂

∂
∂

System X∂

System Y

Program B

∂

∂

∂ ∂

System Z

10

Program A’’

Program A

Program A’11Yes, code similarity matters!
12

Our Code Clone Research13

Code Clone• A code fragment with an identical orsimilar code fragment• Created– Accidentally: small popular idiomse.g.,

if(fp=fopen(“file”,”r”)==NULL){– Intentionally: copy & paste practice
copy &
paste
copy & paste

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

14

15

Issue at Company X• Maintained code clones by hand
M-LOC system
∂

∂

∂

∂∂

∂

∂

Check

20 years
Hand-made clone list

∂

∂

∂

∂

∂

∂∂

?

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

16

No tools available in ‘99
17

18

Clone Detection Policies• Determine detection granularity– char / token / line / block /function / ...

• Cut off small clones (probably by nonintentional idioms)• Find all possible clone sets at thesame time• Use efficient and scalable algorithm

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

19Classification of Clones• Type 1: Exact copy, only differences inwhite space and comments• Type 2: Same as type 1, but also variable
renaming• Type 3: Same as type 2, but also deleting,adding, or changing few statements• Type 4: Semantically identical, but notnecessarily same syntax.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

20

Example of Clones (type 2)

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

21

A Clone Detection Process
Source files
static(( )) ))throws
throws{{ String
1.1.static
throwsRESyntaxException$$void$$foo((foo()
foofoo()staticvoid
throwsthrowsRESyntaxException
String aa {{static void
throws$$RESyntaxException{{RESyntaxException
$$ $$
new
]{{] {{$$ "123,400",$$ =$$String[[ [[]] Stringnew]] == a[]String$[]2.2. [[String"abc",
Stringa[]=new
new
String[]{{"123,400","123,400","abc","orange"orange100"100"};};, "orange 100" }} ;; org pat. apache. regexp
3.3. "abc"org.apache.regexp.RE==neworg.apache.regexp.RE("[0-9,]+");
org.apache.regexp.RE
pat
neworg.apache.regexp.RE("[0-9,]+");
. RE
new
org
.
apache.
regexp$$ pat$$ ==new
4.4. int
0;0;
intsumsum===new. RE) ; int$$ (( "[0-9,]+"$$== $$00"[0-9,]+"
intsum$$ sum$$ =5.5. for++i)
for(int(intii==0;0;i)i<<;a.length;a.length;++i)$$ i$$i ==int;; forfor (( int= 00$$ ;; i$$i <<6.6. a$ if.if(pat.match(a[i]))(pat.match(a[i]));++$$ ;; ++$$ ii)) ))if
length; ++++pat$ . length
if ifif(( (($$ pat
7.7. .. matchsum+=
Sample.parseNumber(pat.getParen(0));
sum+=Sample.parseNumber(pat.getParen(0));$$ (( (( $$ aa [[ [[ $$ ii ]] ]] )) )) )) )) $$sum
sum
8.8. +=
System.out.println("sum""++sum);
System.out.println("sum
sum);
(( 00
$$ .. $.$. parseNumber(( $$ .. $$ (( ((patparseNumber
pat$$ ..==getParen
getParen+= Sample
9.9.}})) )) ;; System$$ .. .$$. out.. .$$. println
Systemout
println"sum==""(( $$ (( "sum+static
static(( $$throws
String$$ void)))void;;;; goo(String}}}goo(String$$ $$goo} static
10.
[][]((a)a)
static void
void
goo
String10.static
throwsRESyntaxException
RESyntaxException{{+ sumstatic]exp
throwsthrows$$RE("[0-9,]+");{{ $$ $$ == {{ RE[[ exp
RESyntaxException
RE expexp ==] ))) ==
throws11.
new
11. a$$ RE
RE
newRESyntaxException
RE("[0-9,]+");$$ (( "[0-9,]+"$$ )) ;; )) $$;; $=sum$$ == 00"[0-9,]+"
RE
int sum
new
$int
=
12.
int
sum
==0;0;
12.newint
sum$$ i$$i ==
<
; for
int
for (( int= 0$$0 ;;; i$$i <<
13.
(int
ii==0;0;ii<<a.length;
13. ; forfor
(int
a.length;++i)++i)$$ ;; ++$$ ii )) ))if;++
length; ++++a$$ .. lengthexp
if ifif(( (($$ exp
14.
14. $ifif(exp.match(a[i]))(exp.match(a[i])).. matchsum$ (( (( $$ aa [[ [[ $$ ii ]] ]] )) )) )) )) $$sum
15.
sum
+=
parseNumber(exp.getParen(0));
15. += parseNumber
sum+=parseNumber(exp.getParen(0));$$ (( ( $$exp .. (. $$ exp
getParen()) 0)) )( )0 ) )$ . parseNumber(( . $$ getParen
16.
System.out.println("sum=sum);
16. ; System.out.println("sumsum);$$ .. $.$. out.. .$$. println(( $$ ((++ "sumSystem""""++++sumout$$ ===
println
"sum
sum
17.
17.}})) ;; }}Lexical
Lexicalanalysis
analysis
Lexicalanalysis
Token
Tokensequence
sequence
Tokensequence
Transformation
Transformation
Transformation
Transformed
Transformedtoken
tokensequence
sequence
Transformed
token
sequence
Match
Matchdetection
detectionMatchdetection
ClonesClonesonontransformed
transformedsequence
sequence
Clonesontransformed
sequence
Formatting
Formatting
Formatting
Clone pairs
22

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

Match Detection Algorithms
1 2 3 4 5 6 7x x y x y z %xyxyz% 1
xyz% 2

1
x
1 x *
2 x *
3 y
4 x *
5 y
6 z
7 %

2 3 4
x y x
*
*
*
*
*
*
*
*

5 6 7
y z %

y

x

xyz%

*

y

*

z%

3

4

z%
5
6

*

Matching Table

z%

*

%

7

1 2 3 4 5 6 7x x y x y z%

Suffix Tree

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

23

Initial Result• Initial prototype had been
implemented in a few weeks• Limited scalability– Refined & tuned– Bought powerful workstation and
expensive memory

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

24Clones between Unix Kernels
FreeBSDLinux

NetBSD

FreeBSDLinux

NetBSD

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

25

Let’s Submit to IEEE TSE !
CCFinder: a multilinguistic token-based code clone detection system for large scale source code, T Kamiya, S
Kusumoto, K Inoue, IEEE Transactions on Software Engineering, Vol.28, No.7, pp.654-670, 2002.

•Initial submission in July, 2000
•Major revision request in Jan., 2001
•Minor revision request in Aug., 2001
•Accepted in Sept., 2001
•Published in July, 2002

1,413 citations (2017, Nov. 3)
22nd highly-cited paper in SE

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

26Extending CCFinder• Prototype was extended, tuned, andrefined as a practical tool
• Target languages– Initially C– Adapted to C++, COBOL, Java, Lisp, Text

• Added GUI and result visualizer

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

27

Promoting Code Clone Technology• Collaboration with many companies– NTT, Fujitsu, Hitachi, Samsung,Microsoft Research, ...

• International Workshop on
Software Clones IWSC (’02~)• Code clone seminars (9 times, ’02~’07)

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

> 5,000 downloads

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

30

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

31

32

Papers Related to Code Clone
1800
1600
1400
1200
1000
800
600
400
200
0
~00

01~05

06~10

11~15

16~

33

Applying to New Fields
34

Compiler Construction Class
S1

S2

S3

S4

S5

S1
S2
S3
S4
S5

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

35Compiler Construction Class
S1

S2

S3

S4

S5

S1
S2
S3
S4
S5

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University36Law Suit of Lace-making Machines

A

B

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

37

Clones in near systems

38

System Evolution Analysis— BSD Unix Clustering —Similarity Measure ß Cover Ratio
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

39Chasing Scalability• CCFinder input limitation: A few M LOC due to thesuffix tree algorithm --- on core
• Code clone detection is embarrassingly parallel
problem --- divide and concur

Distributed CCFinder with 80 lab machines
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

40

FreeBSD Ports Collection / 136 Versions of Linux Kernel

FreeBSD Ports Collection(10.8GB, 400M LOC in C)

136 Ver. Linux Kernels(7.4GB, 260M LOC in C)

Livieri, S., Higo, Y., Matsushita, M., Inoue, K., “Very-Large Scale Code Clone Analysis and Visualization of Open Source Programs Using Distributed
CCFinder: D-CCFinder“, ICSE2007.
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

41

Searching for clone pairs

4234th International Conference on Software Engineering, pp.331-341, Zurich,
Switzerland, 2012-05.

Developer’s Concerns
Existing Project• Origin- Who?
- When?

Code Fragment

Reusable?

- License?
- Copyright?

New Project• Evolution- Maintenance?
Developer- Popularity?
- Newer version?
…

To ease concerns, a support system is needed
Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

44

Code History Tracking System?

Code Fragment
in Question
Copy Source

Proj. C

Descendants

License: X
Copyright: Y

Proj. B

Proj. F

ModifyProj. E
Proj. G

Proj. A
Ancestor

ModifyCopy

Proj. D
License: X /Copyright: Y

Proj. HTime

License: X’
Copyright Y’

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

45

System Overview
Output Results R

Input Query Q
Codeqc
Fragment
Code
Attributes(Optional)

Integrated CodeHistory Tracker
Ichi Tracker

attribute 1: ...
attribute 2: ...
...

SearchResults SR

SearchQuery SQ

Code
Fragment

Code
Clonesattribute 1: ...
attribute 2: ...
...

Code
Attributes

attribute 1: ...
attribute 2: ...
...

Code Search Engines
SPARS/R

GoogleCode
SearchKodersInternet
attribute 1: ...
attribute 2: ...
...

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

46

Evolution Pattern of Texture.java
1

4

7
56 8

9

25

jMonkeyEngine R3800

C

0.9

Cover Ratio

0.8

A
0.7
1

10

2
3

R3448
B

0.6

R4099 12 131415

16 17 19 20 21 22

23 24

26

18

0.5
11

0.4
2006/10/10

2007/04/28

2007/11/14

2008/06/01

2008/12/18

2009/07/06

2010/01/22

2010/08/10

1 Jmonkeyengine r3448(K)

2 Simplexe(G)

3 Simplexe(K)

4 Jmonkeyengine r3800(G)

5 The-project08(G)

6 Tank Combat Game(K)

7 wrathofthetaboos(G)

8 wrathofthetaboos(K)

9 Lasthaven(G)

10 Jme-cotk(G)

11 Ardor3D(G)

12 Jmonkeyengine r4099(G)

13 Fairytale-soulfire(G)

14 Jmonkeyengine r4490(G)

15 Jmonkeyengine r4490(S)

16 Xenogeddon(G)

17 Deathsquadrendezvous(G)

18 Partiendolapana(G)

19 Tholos(G)

20 Ardor3D(G)

21 Cosmic-engine(G)

22 Fregatclient3d(G)

23 Footballmanagerdesia(G)

24 Multiplicity(G)

25 Jmerefactoring(G)

26 Java3dfh(G)

2011/02/26

Last Modify Time
: File in New BSD License: Evolution of jMonkeyEngine Project: File in zib-libpng License: Cluster of Same or Similar FilesEvolution Pattern of kern_malloc
1

1

12 3

4

65
13

24

15

58

36

(G)
Kernel Source
Archive - CMU Mach
3.0
(K)

2

62

11

0.9

3

Lites 1.1.u3

4

Lites 1.1-950808

5 6

10

6

9
27

0.8
8

37-46

26
12

14
16

25
18

34
28-33

47
48

20-23

61

59

49
50

35

17

0.7

66

52 53

56
51

55

63

67

57

Mip-summer98

8

freeBSD/SPARC

ftp in Stockholm
9-12
University
freeBSD-cam2.1.5R

14-15 SonicOSX

54

0.6

7

13

60

64

16

Labyrinth
BSD(labyrinthos)

17

Oskit

18

Psumip

19

Mach

0.4
1993/01/31

Unofficial OSKit
23
sourceUnofficial OSKit
24-26
source(oskit)
ftp in Stockholm
27
University

1995/10/28

1998/07/24

2001/04/19

2004/01/14

Last modified time

2006/10/10

2009/07/06

(G)
(G)
(G)
(G)
(K)

(K)
(G)

(G)

20-22 Savannah

0.5

(G)

(G)
The Rio (RAM I/O)
Project(K)
ftp in The Universityof Edinburgh
(G)

5

7

Cover Ratio

Lites 1.0

19

(G)
(G)
(K)
(K)
(G)

28-33 Kame
34-36 SimOS
27-46 Kame
47

Netnice48

Kame49-50 Psumip
51

Netnice

52

Reflexprotocol

53

Netnice54

NetBSD v1.105

55

OpenBSD PV Xen

56

OpenBSD v1.73

57

Pmon

63

OpenBSD v1.74

64

Pmon

65

774

66

Chord-ns3

(G)
(K)
(G)
(G)
(G)
(G)
(G)
(G)
(G)
(K)
(G)

(K)

(G)
Proyecto A.T.L.D.
58-62 GNU/hurd(extremeli
nux)
(K)

67

(K)
(G)
(G)

(G)
Openbsd-loongsonvc(G)

Results by G(Google Code Search)and 2012/04/01
K(Koders): File in New BSD License: File in Original BSD LicenseCurrent and Future

OSS Dependency
Clone A∂

ImportPaste

Library P

System Y∂∂

Copy
Clone B∂∂

System Z

ExportOSS System X
Library Q

50babel-pres...

broccoli-a...

js-yamlmustachereact-dom
whencomatchdep
hapi
rewirerun-sequence
cookie-par...
karma-webp... merge
gulp-filter
xml2jsgulp-load-... url-loader
winstonpower-assert
grunt-jscs
babel-pres...
gulp-nsp
ape-report...
grunt-brow... karma-cove...
xtend grunt-rele...
grunt-bumpbabelify
hoek
babel-pres... sqlite3
clone
concat-str... update-not...
ember-cli-...
classnames faucet
event-stream jasmine-corebabel-pres...
babel-regi... delredis
source-map...
inherits pre-commit eslint-plu...
mysql
tmp
expectgulp-replacemimekarma-sour...
gulp-sass
ramda
path
gulp-clean
brfs
vows
gulp-coffee
styluschokidarkarma-chaimockery
gulp-minif...
babel-poly...
yosaybabel-plug...
extendeslint-con...
tap-spec
angular-mo...
uuid
grunt-eslint cheerio
coffeelint
gulp-istan...
through nodemailer
promisegulp-bumpmarkedrequire-dir
phantomjs aws-sdk
cli-colorcz-convent...
code assert
pg watch
README.md
null<%= name %>node-uuid
nan
watchify lab chai-as-pr...ws
grunt-shellgrunt-moch... ape-tmpl
qs
promptgrunt-cont...
hubot
karma-fire...
time-grunt
ember-reso...
vinyl-sour... codecov.io grunt-cont...
gulp-if
ape-tasking
jasmine-nodemocha-lcov...
npm
meow
body-parser
yeoman-ass...
css-loader
grunt-cont...
shelljs
nodemonejs
sinon-chaikarma-jasm... minimatch
gulp-rename
readable-s...
jshint-sty...
gulp-concat
proxyquirecozember-cli-...
ember-cli-...

colorsbabel-cli
eslint-plu...
grunt-cont...

graceful-fs

superagent

redux

gulp-jshint

underscore...

requirejs
grunt-karma

compression

grunt-cont...

karma-moch...

babel-loader

yargs

gulp-mocha
nodeunitmongodb grunt-cont...
gulp-watch
jqueryq

gulp-plumber

bunyanjest-cli

expect.js

autoprefixer

blanketresolvecommander

minimist

mocha

zuul

grunt-cont...
standard
karma-phan...
load-grunt...

ember-disa...
ember-cli-...

vinylbootstrap
http-proxygulp-sourc...

escodegengulp-eslint

gulp-uglify

karma-brow...

grunt-cont...

underscoresupertest
socket.io
benchmarkeverythingbabel-eslint
nock

grunt-cont...
ember-cli-...
react-redux
ember-disa...
esprimanode-sassnyc
webpack-de...
optimist
ava

example<%= appNam...

eslintistanbul

fs-extraobject-ass...
gulp-babel

ember-cli-...
react-nativersvp
mongoosejadeember-cli-...
ember-expo...
karma-chro...
semverless
momentxo
ember-databrowser-sync

babel
grunt-cont...
jsdom
inquirersocket.io-...

grunt

tape debug
karma-mocha
postcssconnect
ember-cli-...

async

grunt-cli
handlebars
temp

tap

yeoman-gen...

through2

jscs

react-router

coffee-scr...

shouldkarma

immutablesinonlodashuglify-js
bowerbrowserify

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

request51

Raula Gaikovina Kula, Daniel M. German, Ali Ouni, Takashi Ishio, Katsuro Inoue, Do developers update their librarydependencies? An empirical study on the impact of security advisories on library migration, EMSE accepted & FSE2017 J. 1st.

52

53

54

OSS Ecosystem
OSS Repository

OSS Repository

Project
DependProject

DependContribute

Developer

Use

User

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

55Summary

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

Finding similar code insoftw1are matters
57

Code clone analysis becamevery popular SE technology

58

Analyzing code similarity is key toknow OSS provenance and evolution

Exploring OSS universe
with code similarity analysis

Thank you
62