[논문]자바스크립트에 특화된 프로그램 종속성 그래프를 이용한 표절 탐지

김신형; 한태숙

자바스크립트에 특화된 프로그램 종속성 그래프를 이용한 표절 탐지
Plagiarism Detection Using Dependency Graph Analysis Specialized for JavaScript 원문보기

정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용, v.37 no.5, 2010년, pp.394 - 402

김신형 (한국과학기술원 전산학과) , 한태숙 (한국과학기술원 전산학과)

초록
AI-Helper

자바스크립트는 현재 웹 사이트, 웹 어플리케이션에서 가장 많이 사용되는 스크립트 언어 중 하나이다. 자바스크립트로 작성된 프로그램은 원본 프로그램 형태로 클라이언트에게 전송되므로 무단 복제, 도용에 쉽게 노출된다. 때문에 자바스크립트 프로그램의 도용을 탐지하기 위한 연구가 필요하다. 현재 일반적으로 프로그램 표절 탐지를 위해 사용되는 자동화 도구들의 경우 고수준의 표절 기법에 적절히 대응하지 못한다. 반면에 프로그램 종속성 그래프에 기반을 둔 기존 연구들의 경우 자바스크립트의 동적인 특징을 적절히 반영하지 못한다. 또한 지나친 일반화로 인해 일부 틀린 판정(false positive)을 보이며 대상 프로그램의 크기가 클 경우 탐지 속도에 문제를 보이고 있다. 본 논문에서는 자바스크립트에 특화된 프로그램 종속성 그래프(이하 JS PDG)와 이를 사용한 도용 탐지 기법을 제안하여 이러한 문제를 해결하고자 한다. 본 논문에서 제안하는 JS PDG는 세분화된 노드 타입을 가지고 있어 기존 PDG와 비교해 보다 정확한 그래프 간 비교를 할 수 있도록 하며 포함하고 있는 노드 타입에 따라 정의되는 JS PDG의 타입은 탐색 범위를 분할을 가능하게 해 전체 도용 탐지 속도가 개선 될 수 있도록 한다. 실험 결과 기존 PDG에서 나타나는 틀린 판정을 확인할 수 있었으며 PDG간 비교 횟수가 줄어들어 도용 탐지 속도가 개선됨을 확인할 수 있었다.

Abstract ▼ AI-Helper

JavaScript is one of the most popular languages to develope web sites and web applications. Since applicationss written in JavaScript are sent to clients as the original source code, they are easily exposed to plagiarists. Therefore, a method to detect plagiarized JavaScript programs is necessary. The conventional program dependency graph(PDG) based approaches are not suitable to analyze JavaScript programs because they do not reflect dynamic features of JavaScript. They also generate false positives in some cases and show inefficiency with large scale search space. We devise a JavaScript specific PDG(JS PDG) that captures dynamic features of JavaScript and propose a JavaScript plagiarism detection method for precise and fast detection. We evaluate the proposed plagiarism detection method with experiment. Our experiments show that our approach can detect false-positives generated by conventional PDG and can prune the plagiarism search space.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

JS PDG는 자바스크립트의 동적인 특징을 반영하여 에지(edge)을 구성하며 노드(node)의 타입 정보를 가지고 있어 보다 정확한 자바스크립트 프로그램의 의미를 나타낼 수 있다. 또한 각 JS PDG가 포함하고 있는 특수 노드를 이용하여 한정된 탐색 범위를 제공함으로써 전체적인 도용 탐지의 속도를 향상 시킬 수 있는 방법을 제시한다.
본 논문에서는 앞에서 발견된 문제점들을 해결하기 위해 자바스크립트에 특화된 프로그램 종속성 그래프(이하 JS PDG라 칭함)와 이를 이용한 도용 탐지 기법을 제안한다. JS PDG는 자바스크립트의 동적인 특징을 반영하여 에지(edge)을 구성하며 노드(node)의 타입 정보를 가지고 있어 보다 정확한 자바스크립트 프로그램의 의미를 나타낼 수 있다.
본 논문에서는 특수 노드의 타입 정보를 포함하고 있는 JS PDG와 이를 이용한 도용 탐지 기법을 제안했다. JS PDG에서 사용된 특수 노드들은 다른 객체, 값으로 대체 불가능한 특징을 가진 것들로 이들의 타입 정보를 이용해 보다 정확한 도용 탐지가 이루어질 수 있도록 추가적인 정보를 제공하는 역할을 한다.
본 실험에서는 4.1 과 4.2에서 언급한 JS PDG가 가지고 있는 특징 즉, 속도와 정확도 개선에 대한 검증을 하고자 하였다.
우리는 향후 본 논문에서 제안하는 JS PDG와 이를 활용한 자바스크립트 도용 탐지 기법을 바탕으로 웹 사이트, 웹 어플리케이션 간의 도용 여부를 합리적인 시간 안에 탐지할 수 있는 자동화 시스템을 구축하고자 한다.

가설 설정

현재 많이 사용되는 자바스크립트 라이브러리①brary) 중 3 개를 선택한 후 각 프로그램에 대해 2개의 버전 (version)을 대상 프로그램으로 선정하여 하위 버전을 원본 프로그램으로, 상위 버전을 도용이 의심되는 도용프로그램으로 가정했다. 일반적으로 상위 바전에서 하위 버전에서 사용하던 함수를 그대로 사용하거나 약간의 변경을 하되 본래의 기능 그대로 사용하는 경우가 많이 있기 때문에 그러한 함수 쌍을 원본과 도용이 의심되는 함수 쌍으로 찾고자 하는 것이다.

제안 방법

JS PDG에서의 각 노드는 기존 PDG에서 사용되는 노드를 바탕으로 보다 정확한 프로그램의 의미를 나타낼 수 있도록 특수 노드를 추가했다. 전체 노드 타입 (node type)은 표 2에 표시했다.
기존 PDG 분석을 자바스크립트에 적용한 사례가 없어 직접 구현했는데 spidermonkey4)를 사용하여 자바스크립트 프로그램의 추상화된 문법 트리를 생성한 후 강것으로부터 PDG를 생성하는 프로그램을 작성했다. 기존 PDG 분석 구현 시의 노드 타입은 표 2의 JS PDG에서 특수 노드를 제외한 일반 노드로 구성하였으며 JS PDG의 경우 3장 JS PDG의 구성상 특징에 설명한 바와 같이 기존 JS PDG와의 구별되는 특징을 반영하여 각각 구현하였다.
기존 PDG 분석을 자바스크립트에 적용한 사례가 없어 직접 구현했는데 spidermonkey4)를 사용하여 자바스크립트 프로그램의 추상화된 문법 트리를 생성한 후 강것으로부터 PDG를 생성하는 프로그램을 작성했다. 기존 PDG 분석 구현 시의 노드 타입은 표 2의 JS PDG에서 특수 노드를 제외한 일반 노드로 구성하였으며 JS PDG의 경우 3장 JS PDG의 구성상 특징에 설명한 바와 같이 기존 JS PDG와의 구별되는 특징을 반영하여 각각 구현하였다.
다음으로 원본 프로그램과 도용이 의심되는 프로그램으로 사용할 도용 프로그램을 선정하여 기존 PDG와 JS PDG를 사용하여 도용 탐지를 시행한 후 그 결과에 대해 살펴보았다. 구체적인 내용은 다음과 같다.
우수한 성능을 나타낸다고 알려져 있다. 따라서 우리는 JS PDG의 성능을 평가하기 위한 실험의 중점을 기존 PDG 분석과의 비교에 두었다.
동작은 다음과 같다. 먼저 원본 프로그램 P와 도용이 의심되는 프로그램 P'를 구성하는 함수들을 대상으로 함수 당 하나의 JS PDG를 생성하여 두 개의 JS PDG 집합을 구성한다. 이때 표 3에 명시된 특수 노드를 포함한 함수들의 JS PDG는 표 4에 나타난 바와 같이 분류된다.
먼저, 임의의 자바스크립트 프로그램으로부터 기존 PDG와 JS PDG를 추출해 낼 수 있는 시스템을 각각 구현했다. 기존 PDG 분석을 자바스크립트에 적용한 사례가 없어 직접 구현했는데 spidermonkey4)를 사용하여 자바스크립트 프로그램의 추상화된 문법 트리를 생성한 후 강것으로부터 PDG를 생성하는 프로그램을 작성했다.
본 논문에서 제안하는 자바스크립트 표절 탐지 기법은 기존 PDG를 기반으로 하는 시스템에서 노드 타입의 지나친 일반화로 인해 틀린 판정으로 도출되는 대상에 대해서도 분별할 수 있는 능력을 가지고 있다.
같은 작업을 하였다. 여러 가지 알고리즘(algo rithm) 을 선택하여 그래프 동형 확인을 할 수 있도록 지원하고 있는 C++ 라이브러리인 VFLib$을 사용하되 프로그램의 일부를 수정하여 원본 함수를 구성하는 PDG 전체 노드의 80%이상이 포함될 경우 서브 그래프 동형으로 판단하도록 하고 원본 프로그램의 각 함수에 대해 도용 프로그램의 모든 함수들에 대해 서브 그래프 동형 확인을 하도록 했다.
임의의 프로그램으로부터 기존 PDG와 JS PDG의 집합을 생성한 후 서브 그래프 동형을 확인하기 위해 다음과 같은 작업을 하였다. 여러 가지 알고리즘(algo rithm) 을 선택하여 그래프 동형 확인을 할 수 있도록 지원하고 있는 C++ 라이브러리인 VFLib$을 사용하되 프로그램의 일부를 수정하여 원본 함수를 구성하는 PDG 전체 노드의 80%이상이 포함될 경우 서브 그래프 동형으로 판단하도록 하고 원본 프로그램의 각 함수에 대해 도용 프로그램의 모든 함수들에 대해 서브 그래프 동형 확인을 하도록 했다.

대상 데이터

생성된 PDG 중 노드의 수가 1。개 이상이고 데이터 의존성 에지가 5개 이상인 함수들만을 실험 대상으로 선정 했다. 그 이유는 노드와 에지가 일정 수 이상 되면 서브 그래프 동형 확인 시 틀린 판정으로 동형이라고 판단하게 되는 경우가 적어지기 때문이다.
JS PDG에서 사용된 특수 노드들은 다른 객체, 값으로 대체 불가능한 특징을 가진 것들로 이들의 타입 정보를 이용해 보다 정확한 도용 탐지가 이루어질 수 있도록 추가적인 정보를 제공하는 역할을 한다. 실험 및 평가에서 살펴본 바와 같이 JS PDG 분석을 사용하여 기존 PDG 분석을 사용했을 경우의 틀린 판정 사례를 실제 사용되고 있는 자바스크립트 라이브러리 프로그램들로부터 찾아내었다.

성능/효과

같다. 전체 함수 대비 특수 함수의 비율이 하위, 상위 버전 각각 32.5%, 27%로 나타난 jqiiery의 비교 횟수는 JS PDG를 사용헀을 경우 기존 PDG를 사용했을 경우와 비교해 약 29%가 줄어든 것을 확인할 수 있다. 표 7의 비교 횟수 개선 비율에서 나타난 바와 같이 전체 함수대비 특수 함수의 비율이 높을수록 비교 횟수의 개선 비율 역시 높게 나타나는 것을 알 수 있다.
전체적인 과정을 설명하면’ 임의의 자바스크립트로부터 기존 PDG와 JS PDG를 추출할 수 있는 시스템을 각각 독립적으로 구현하고 기존 PDG나 JS PDG의 집합으로 부터 생성된 PDG들을 입력받아 서브 그래프 동형 확인을 할 수 있는 프로그램을 작성했다. 다음으로 원본 프로그램과 도용이 의심되는 프로그램으로 사용할 도용 프로그램을 선정하여 기존 PDG와 JS PDG를 사용하여 도용 탐지를 시행한 후 그 결과에 대해 살펴보았다.
예를 들어 mochikit의 경우 노드가 17개이고 에지가 5개인 작은 PDG가 노드가 64개이고 에지가 26개인 큰 PDG에 서브 그래프 동형으로 판단된 것이다. 즉, 기존 PDG를 사용했을 경우 나타날 수 있는 틀린 판정의 실질적인 예라고 할 수 있는데 JS PDG의경우 이들에 대해 도용이 아니라는 올바른 판정을 내린 것을 확인할 수 있었다.
jqeury의 경우 기존 PDG는 전체 40개의 함수에 대해 21개의 함수를 도용이 의심된다고 판단했으며 JS PDG는 19개의 함수를 도용이 의심된다고 판단했다. 직접 확인한 결과 JS PDG가 도용이 의심된다고 판단한 19개의 함수는 기존 PDG에 의해 모두 도용이라고 판단되었으나 기존 PDG가 도용이라고 판단한 추가적인 2개의 함수는 기존 PDG과 JS PDG가 서로 다른 판단을 하였다. 마찬가지로 prototype과 mochikit의 경우에도 각 1개의 함수에 대해 서로 다른 판단을 하였다.
직접 확인해 본 결과 대부분의 경우 도용으로 판단된 두 함수는 서로 다른 이름과 기능을 가지고 있었으나 노드와 에지의 수가 적은 JS PDG들이 비교적 복잡한 구조의 PDG들 즉, 많은 노드와 에지를 가지는 JS PDG 들에 우연히 서브 그래프 동형으로 판정받은 것을 확인할 수 있었다. 예를 들어 mochikit의 경우 노드가 17개이고 에지가 5개인 작은 PDG가 노드가 64개이고 에지가 26개인 큰 PDG에 서브 그래프 동형으로 판단된 것이다.
분할함으로써 속도 개선을 했다. 프로그램을 구성하는 전체 함수에 대비해 특수 함수로 분류되는 함수들의 비중이 높을수록 탐색 범위 분할은 효과적으로 이루어진다.

참고문헌 (18)

Paulson, L. D. et al., "Building rich web applications with Ajax," In Computer, vol.38. pp.14-17, 2005.
J. W. Michael, "YAP3: improved detection of similarities in computer program and other texts," SIGCSE Bulletin, vol.28, pp.130-134, 1996.
L. Prechelt, et al., "Finding plagiarisms among a set of programs with JPlag," J. of Universal Computer Science, vol.8, pp.1016-1038, 2002.
T. Kamiya, et al., "CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code," IEEE TSE, vol.28, no.7, pp.654-670, 2002.
S. Schleimer, et al., "Winnowing: local algorithms for document fingerprinting," In Proc. of ACM SIGMOD Int. Conf. on Mgmt. of Data, 2003.
S. Bellon, et al., "Comparison and Evaulation of Clone Detection Tools," IEEE Trans. on Software Engineering, vol.33, no.9, September 2007.
J. Krinke, "Identifying similar code with program dependence graphs," In Proc. WCRE'01. IEEE, 2001.
R. Komondoor and S. Horwitz, "Using Slicing to Identify Duplication in Source Code," In Proc. of the 8th Int. Sym. on Static Analysis, pp.40-56, 2001.
Liu, C. et al., "GPLAG: detection of software plagiarism by program dependence graph analysis," In Proc. of the 12th ACM SIGKDD Int. Conf. on Knowledge discovery and data mining, pp.872-881, 2006.
Dongseok Jang et al., "Points-to analysis for JavaScript," In Proc. of the 2009 ACM sym. on Applied Computing, pp.1930-1937.
I. Baxter et al., "Clone Detection Using Abstract Syntax Trees," In ICSM, pp.368-377, 1998.
R. Koschke et al., "Clone Detection Using Abstract Syntax Suffix Trees," In Proc. WCRE'06. IEEE, 2006.
Lanubile F. et al., "Finding Function Clones in Web Applications," In Software Maintenance and Reengineering, 2003. Proc. 7th European Conf., pp.379-386.
Jeanne Ferrante et al., "The Program Dependence Graph and its use in optimtization," In ACM Trans. on Programming Languages and Systems, vol.9, no.3, pp.319-349, July 1987.

상세보기
Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison- Wesley Longman Publishing Co., Inc., Boston, MA, 1986.
ECMAScript Language Specification Edition 3
J. R. Ullmann, "An algorithm for subgraph isomorphism," J. of the Association for Computing Machinery, vol.23, pp.31-42, 1976.

상세보기
Luigi P. Cordella et al., "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol.26, no.10, pp.1367-1372, Oct. 2004.

상세보기

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증