ソフトウェアエンジニアリングシンポジウム 2013 Smith-Waterman 1,a) 1,b) 1,c) 1,d) 1,e) LCS Smith-Waterman Bellon Gapped Code Clone Detection Using The Smith-Waterman Algor

Size: px

Start display at page:

Download "ソフトウェアエンジニアリングシンポジウム 2013 Smith-Waterman 1,a) 1,b) 1,c) 1,d) 1,e) LCS Smith-Waterman Bellon Gapped Code Clone Detection Using The Smith-Waterman Algor"

ひでよりねごろ
4 years ago
Views:

1 Smith-Waterman,a),b),c),d),e) LCS Smith-Waterman Bellon Gapped Code Clone Detection Using The Smith-Waterman Algorithm Hiroaki MURAKAMI,a) Keisuke HOTTA,b) Yoshiki HIGO,c) Hiroshi IGAKI,d) Shinji KUSUMOTO,e) Abstract: A variety of techniques detecting code clones has been proposed before now. In order to detect gapped code clones, AST(Abstract Syntax Tree)-based technique, PDG(Program Dependence Graph)-based technique, metric-based technique and finger print technique using the LCS algorithm have been proposed. However, each of those techniques has limitations such as detection time is long or detection accuracy is not sufficient. This paper proposes a new method that detects gapped code clones using the Smith-Waterman algorithm in order to resolve those limitations. The authors developed the proposed method as a software tool, and confirmed that the proposed method could resolve the limitations by conducting a quantitative evaluation with Bellon s benchmark. Keywords: Code Clone, Program Analysis, String Algorithm. [] Graduate School of Information Science and Technology, Osaka University a) h-murakm@ist.osaka-u.ac.jp b) k-hotta@ist.osaka-u.ac.jp c) higo@ist.osaka-u.ac.jp d) igaki@ist.osaka-u.ac.jp e) kusumoto@ist.osaka-u.ac.jp [2] [3] 23 Information Processing Society of Japan

2 * *2 LCS AST PDG LCS AST PDG AST PDG AST PDG LCS Smith- Waterman [4] Smith-Waterman 2 AST PDG AST PDG LCS LCS Bellon [5] Bellon Bellon Bellon * Abstract Syntax Tree AST *2 Program Dependence Graph PDG Smith-Waterman F 2. Smith-Waterman Smith-Waterman [4] 2 Smith-Waterman TCGATAGCT ACGTACGCA 2 Smith- Waterman Smith-Waterman. : 2 a, a 2,, a N b, b 2,, b M (N + 2) (M + 2) 2. : A 2 3. : v i,j + s(a i, b j ), v i,j + gap, v i,j (2 i, 2 j) = max () v i,j + gap,. { match (ai = b j ), s(a i, b j ) = (2) mismatch (a i b j ). c i,j i j v i,j c i,j a i a, a 2,, a N i b j b, b 2,, b M j s(a i, b j ) a i b j match mismatch gap match mismatch gap (match, mismatch, gap) (, -, -) v i,j c i,j (4) v 7,6 (= 3) v 6,5 (= 2) s(v,6, v 7, )(= ) c 6,5 c 7,6 4. : C 23 Information Processing Society of Japan 2

3 T C G A T A G C T T C G A T A G C T 塩基配列 : T C G A T A G C T A C A C 4 G 2 4 G 2 塩基配列 2: A C G T A C G C A T 2 A C T 2 A C G G C C A 3 3 A 3 3 () (2) (3) T C G A T A G C T T C G A T A G C T A C A C 塩基配列 : T C G A T A G C T G 2 T 2 A C G 2 T 2 A C 類似部分配列塩基配列 2: A C G T A C G C A 8 G G C C A 3 3 A 3 3 (4) (5) Smith-Waterman Fig. An Example of the Smith-Waterman Algorithm. (6) 5. : CGATAGC CGTACGC CGATAGC CGTACGC 3. match mismatch gap match mismatch gap 5 : 2: 3: 4: 5: 2 : 2: ; { } 2 3: Smith-Waterman Information Processing Society of Japan 3

4 : if(isname){ 3: for(int i = ; i < token.length; i++){ 32: buf.append(token[i]);} 33: String result = buf.tostring(); 34: }else{ 35: for(int j = ; j < token.length; j++){ 36: buf.append(token[j]); 37: if(j % 2 == ){buf.append(",");}} 38: String result = buf.tostring(); 39: } 4: return result; 52: StringBuffer buf = new StringBuffer(); 53: for(int i = ; i < token.length; i++){ 54: buf.append(token[i]);} 55: buf.append(getcomma()); 56: String result = buf.tostring(); 57: System.out.println(result); if ( $ ) { for ( $ $ = $ ; $ < $. $ ; $ + + ) { $. $ ( $ [ $ ] ) ; } $ $ = $. $ ( ) ; } else { for ( $ $ = $ ; $ < $. $ ; $ + + ) { $. $ ( $ [ $ ] ) ; } if ( $ % $ = = $ ) { $. $ ( $ ) ; } } $ $ = $. $ ( ) ; } return $ ; $ $ = new $ ( ) ; for ( $ $ = $ ; $ < $. $ ; $ + + ) { $. $ ( $ [ $ ] ) ; } $. $ ( $() ) ; $ $ = $. $ ( ) ; $. $. $ ( $ ) ; if($) { for($$=$ ; $<$.$ ; $++) { $.$($[$]) ; } $$=$.$() ; } else { for($$=$ ; $<$.$ ; $++) { $.$($[$]) ; } if($%$==$) { $.$($) ; } } $$=$.$() ; } return$ ; $$=new$() ; for($$=$ ; $<$.$ ; $++) { $.$($[$]) ; } $.$($()) ; $$=$.$() ; $.$.$($) ; () (2) (3) (4) { (6) ; 2(5) ; 3(4) { 4(9) ; } 5(8) ; } 6() { (6) ; 2(5) ; 3(4) { 4(9) ; } 6(9) { 7(6) ; } } 5(8) ; } 8(2) ; 9(7) ; (6) ; 2(5) ; 3(4) { 4(9) ; } 95(8) ; 5(8) ; (8) ; (4) ハッシュ値列字句数列ハッシュ値列字句数列 (5) (6) ハッシュ値列類似部分ハッシュ値列ハッシュ値列 if ( j % 2 = = ) buf. append (, ) ギャップとなる字句 buf. append ( getcomma ()) : if(isname){ 3: for(int i = ; i < token.length; i++){ 32: buf.append(token[i]);} 33: String result = buf.tostring(); 34: }else{ 35: for(int j = ; j < token.length; j++){ 36: buf.append(token[j]); 37: if(j % 2 == ){buf.append(",");}} 38: String result = buf.tostring(); 39: } 4: return result; 52: StringBuffer buf = new StringBuffer(); 53: for(int i = ; i < token.length; i++){ 54: buf.append(token[i]);} 55: buf.append(getcomma()); 56: String result = buf.tostring(); 57: System.out.println(result); コードクローンコードクローンのペア関係ギャップとなるトークン (7) (8) (9) 2 Fig. 2 An Example of Detection Process Using the Proposed Method. 2 2 v i,j >. v i, = v,j. c i,j c k,l (k i, l j) S S = {c m,n k m i l n j}. (3) 23 Information Processing Society of Japan 4

5 Algorithm Input: (N + 2) (M + 2) Output: for i = N + 2 to do for j = M + 2 to do if v i,j > and v i, = v,j and (c i,j ) then c i,j end if end for end for Algorithm : 3 LCS *3 LCS 5: CDSW Smith-Waterman 3 (match, mismatch, gap) A B : F 2: 3: *3 Longest Common Subsequence 2 A B Smith- Waterman A B Bellon [6] 8 Bellon *4 8 CPU 2.27GHz Intel Xeon CPU 6.GB 4.3 : : Bellon ok [5] ok Definition 4. (ok ). f f 2 lines(f) f A A contain(f, f 2 ) = lines(f ) lines(f 2 ). (4) lines(f ) p p 2 ok p.f p p.f 2 Table Target Software Systems. netbeans Java 4,36 weltab C,46 ant Java 34,744 cook C 7,8 jdtcore Java 47,634 snns C 93,867 swing Java 24,37 postgresql C 2,686 *4 ( ) 23 Information Processing Society of Japan 5

6 73: final public void dstore_2() { 74: countlabels = ; 75: stackdepth -= 2; 76: if (maxlocals < 4) { 77: maxlocals = 4; } 78: try { 79: position++; 7: bcodestream[classfileoffset++] = OPC_dstore_2; 7: } catch (IndexOutOfBoundsException e) { 72: resizebytearray(opc_dstore_2); } } ギャップ行 86: final public void fcmpl() { 862: countlabels = ; 863: stackdepth--; 864: try { 865: position++; 866: bcodestream[classfileoffset++] = OPC_fcmpl; 867: } catch (IndexOutOfBoundsException e) { 868: resizebytearray(opc_fcmpl); } } クローンタイプギャップ行の集合 2 終了行終了行 2 ギャップ行の集合ファイル名開始行ファイル名 2 開始行 2 eclipse-jdtcore/src/internal/compiler/codegen/codestream.java eclipse-jdtcore/src/internal/compiler/codegen/codestream.java , 76, No. 577 Fig. 3 An Example of the Clone Reference the Authors Remade (Reference No. 577). ok(p, p 2 ) = min( max( contain(p.f, p 2.f ), contain(p 2.f, p.f )), max( contain(p.f 2, p 2.f 2 ), contain(p 2.f 2, p.f 2 ))). (5) Bellon ok.7 S cand S refs S cand S refs S Recall P recision F F -measure Recall = S S refs. (6) P recision = S S cand. (7) 2 Recall P recision F -measure = Recall + P recision. (8) 5. Smith-Waterman 3 (match, mismatch, gap) (9) () () Z match = {x Z x 4}. (9) mismatch = {y Z 4 y }. () gap = {z Z 4 z }. () : 2: 64 (= 4 4 4) CDSW F F (match, mismatch, gap) (match, mismatch, gap) (2, -2, -) F A B (match, mismatch, gap) (2, -2, -) 6. A A Bellon Bellon Web * F Bellon F 4 F F 3.8%.43% *5 references_with_gaps/ 23 Information Processing Society of Japan 6

Bellon's らの正解クローン clone references Our 著者らの正解クローン clone references.35.3.25.2.5..5 netbeans ant jdtcore swing weltab cook snns postgresql 4 F Fig. 4 F -measure of CDSW Using Both the Clone References.

7 Bellon's らの正解クローン clone references Our 著者らの正解クローン clone references netbeans ant jdtcore swing weltab cook snns postgresql 4 F Fig. 4 F -measure of CDSW Using Both the Clone References. F 7. B CloneDR CLAN CCFinder Dup Duploc Duplix NiCad DECKARD CDSW 5 Fig. 5 F F -measure of All the Clone Detectors. B CDSW CDSW 2 NiCad DECKARD Bellon NiCad 3 CDSW CDSW F 5 F 5 CDSW F CDSW ok ok 2 Table 2 Clone Detectors Used for Comparison. Baxter CloneDR Merlo CLAN Kamiya CCFinder Baker Dup Rieger Duploc Krinke Duplix Roy NiCad LCS Jiang DECKARD 6 DECKARD CDSW Fig. 6 Exection Time of DECKARD and CDSW..7 CDSW DECKARD 6 6 CDSW 3 DECKARD CDSW F CDSW 3 CDSW Bellon CDSW Bellon NiCad 23 Information Processing Society of Japan 7

8 Bellon Bellon NiCad Smith-Waterman LCS Smith-Waterman LCS Smith-Waterman mismatch gap LCS Smith-Waterman Smith-Waterman 2 2 a, a 2,, a n b, b 2,, b m Smith-Waterman O(mn) O(mn) LCS 9.2 Smith-Waterman [7] 2 2 Smith-Waterman [8]. Smith-Waterman CSDW 8 Smith-Waterman 3 (match, mismatch, gap) Bellon CSDW CSDW F 7 CDSW (S)( 25223) ( 2465) (A)( 24682) SEC: Software Reliability Enhancement Center 22 [] D Vol. 9-D, No. 6, pp (28). [2] Clone Detection Literature:. tairasr/clones/literature/. [3] Kim, M., Bergman, L., Lau, T. and Notkin, D.: An Ethnographic Study of Copy and Paste Programming Practices in OOPL, Proc. of the 24 International Symposium on Empirical Software Engineering, pp (24). [4] Smith, T. F. and Waterman, M. S.: Identification of common molecular subsequences, Journal of Molecular Biology, Vol. 47, No., pp (98). [5] Bellon, S., Koschke, R., Antniol, G., Krinke, J. and Merlo, E.: Comparison and evaluation of clone detection tools, IEEE Trans. on Software Engineering, Vol. 3, No., pp (27). [6] Detection of Software Clones:. bauhaus-stuttgart.de/clones/. [7] Smith-Waterman Vol. 2, No. 39, pp. 6 (22). [8] D Vol. 93-D, No. 9, pp (2). 23 Information Processing Society of Japan 8

1 Fig. 1 Extraction of motion,.,,, 4,,, 3., 1, 2. 2.,. CHLAC,. 2.1,. (256 ).,., CHLAC. CHLAC, HLAC. 2.3 (HLAC ) r,.,. HLAC. N. 2 HLAC Fig. 2

1 Fig. 1 Extraction of motion,.,,, 4,,, 3., 1, 2. 2.,. CHLAC,. 2.1,. (256 ).,., CHLAC. CHLAC, HLAC. 2.3 (HLAC ) r,.,. HLAC. N. 2 HLAC Fig. 2 CHLAC 1 2 3 3,. (CHLAC), 1).,.,, CHLAC,.,. Suspicious Behavior Detection based on CHLAC Method Hideaki Imanishi, 1 Toyohiro Hayashi, 2 Shuichi Enokida 3 and Toshiaki Ejima 3 We have proposed a method for