본 논문에서는 대학생들의 프로그래밍 과제물이나 프로그래밍 경진대회에 제출된 프로그램과 같이 동일한 기능을 요구받는 프로그램 소스 집합들에서 표절행위가 있었는지를 탐색하는 새로운 알고리즘을 제시하고 있다. 지금까지 보편적으로 사용되어 온 대표적인 알고리즘은 부분 스트링간의 완전 일치를 통한 Greedy-String-Tiling이나 두 스트링간의 지역정렬(local alignment)을 이용한 유사도 분석이 주된 방법론이었다. 본 논문에서는 해당 프로그램 소스의 집합에서 추출된 키워드들의 빈도수에 기반한 로그 확률값을 가중치로 하는 적응적(adaptive) 유사도 행렬을 만들어 이를 기반으로 주어진 프로그램의 유사구간을 탐색하는 새로운 방법을 소개한다. 우리는 10여개 이상의 프로그래밍 대회에서 제출된 실제 프로그램으로 본 방법론을 실험해 보았다. 실험결과 이 방법은 이전의 고정적 유사도 행렬(match이면 +1, mismatch이면 -1, gap이면 -2)에 의한 유사구간 탐색에 비하여 여러 장점이 있음을 알 수 있었으며, 제시한 적응적 유사도 행렬을 보다 다양한 표절탐색 목적으로 사용할 수 있음을 알 수 있었다.
본 논문에서는 대학생들의 프로그래밍 과제물이나 프로그래밍 경진대회에 제출된 프로그램과 같이 동일한 기능을 요구받는 프로그램 소스 집합들에서 표절행위가 있었는지를 탐색하는 새로운 알고리즘을 제시하고 있다. 지금까지 보편적으로 사용되어 온 대표적인 알고리즘은 부분 스트링간의 완전 일치를 통한 Greedy-String-Tiling이나 두 스트링간의 지역정렬(local alignment)을 이용한 유사도 분석이 주된 방법론이었다. 본 논문에서는 해당 프로그램 소스의 집합에서 추출된 키워드들의 빈도수에 기반한 로그 확률값을 가중치로 하는 적응적(adaptive) 유사도 행렬을 만들어 이를 기반으로 주어진 프로그램의 유사구간을 탐색하는 새로운 방법을 소개한다. 우리는 10여개 이상의 프로그래밍 대회에서 제출된 실제 프로그램으로 본 방법론을 실험해 보았다. 실험결과 이 방법은 이전의 고정적 유사도 행렬(match이면 +1, mismatch이면 -1, gap이면 -2)에 의한 유사구간 탐색에 비하여 여러 장점이 있음을 알 수 있었으며, 제시한 적응적 유사도 행렬을 보다 다양한 표절탐색 목적으로 사용할 수 있음을 알 수 있었다.
This paper suggests a new algorithm for detecting the plagiarism among a set of source codes, constrained to be functionally equivalent, such are submitted for a programming assignment or for a programming contest problem. The typical algorithms largely exploited up to now are based on Greedy-String...
This paper suggests a new algorithm for detecting the plagiarism among a set of source codes, constrained to be functionally equivalent, such are submitted for a programming assignment or for a programming contest problem. The typical algorithms largely exploited up to now are based on Greedy-String Tiling, which seeks for a perfect match of substrings, and analysis of similarity between strings based on the local alignment of the two strings. This paper introduces a new method for detecting the similar interval of the given programs based on an adaptive similarity matrix, each entry of which is the logarithm of the probabilities of the keywords based on the frequencies of them in the given set of programs. We experimented this method using a set of programs submitted for more than 10 real programming contests. According to the experimental results, we can find several advantages of this method compared to the previous one which uses fixed similarity matrix(+1 for match, -1 for mismatch, -2 for gap) and also can find that the adaptive similarity matrix can be used for detecting various plagiarism cases.
This paper suggests a new algorithm for detecting the plagiarism among a set of source codes, constrained to be functionally equivalent, such are submitted for a programming assignment or for a programming contest problem. The typical algorithms largely exploited up to now are based on Greedy-String Tiling, which seeks for a perfect match of substrings, and analysis of similarity between strings based on the local alignment of the two strings. This paper introduces a new method for detecting the similar interval of the given programs based on an adaptive similarity matrix, each entry of which is the logarithm of the probabilities of the keywords based on the frequencies of them in the given set of programs. We experimented this method using a set of programs submitted for more than 10 real programming contests. According to the experimental results, we can find several advantages of this method compared to the previous one which uses fixed similarity matrix(+1 for match, -1 for mismatch, -2 for gap) and also can find that the adaptive similarity matrix can be used for detecting various plagiarism cases.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
그러나 데이터 셋에 따라 분포가 달라지는 경우는 확인할 수 없었다. 다음 절에서는 ICPC 그룹 A에서 직접 표절로 검출된 코드에 대해서 집중적으로 살펴보고자 한다.
둘째, 매개변수를 확장하는 것에 대한 연구이다. 현재 적응적 유사도 산출 방법에서는, 자유도가 1인 조절변수 q=1 —를 이용해서 일치, 툴일치, 갭을 이용한 일치를 조정하고 있다.
특히 자료구조나 알고리즘의 표절은 해당 분야의 전문가(human expert)만이 할 수 있는 고도의 지능적 작업이므로 이를 컴퓨터 시스템이 기계적으로 측정하여 판단하는 것은 매우 어렵다. 따라서 본 논문에서는 두 프로그램의 유사도를 일단 구문수준에서 시작하여 좀 더 확장된 형태로 고려할 수 있는 연구에 집중하고자 한다.
본 논문에서는 두 키워드의 빈도 곱의 로그 값으로 유사도 점수를 정했는데, 어떤 신호값(signal)의 세기 (intensity)를 상대적으로 비교하기 위하여 그 값에 log 를 취한 값(log odd)을 취하는 것은 공학에서 혼히 이용하는 방법이다. 예를 들어 마이크로어레이 실험에서 각 스팟별 신호의 강도를 상대적으로 비교하는 것 역시 그 상대값의 비율에 로그를 취한 것을 사용한다.
특히 일반적으로 잘 사용하지 않는 특별한 방법을 사용하거나 구문 형태를 고쳐서 그 형식이 드러나지 않게 고치는 일에 많은 비용이 든다고 가정할 때, 각 키워드의 비율의 비중을 고려한 적응적 유사도 행렬에 의한 표절 탐색 방법은 이전의 단순한 일치/불일치로만 계산하는 기존의 방법에 비해서 상당히 효과적이다. 본 논문에서는 실제 표절 데이터를 대상으로 한 실험을 통해 이를 보였다.
여기서 제한된 환경에서의 프로그램들이란, 입력과 출력 형식, 동작되어야 하는 프로그램의 기능이 매우 엄격하게 정의된 프로그래 밍 과제물이라든지, 프로그래밍 경진대회에서 제출된 문제들에 대한 프로그램들을 말한다. 본 논문에서는 이러한 제한된 환경에서의 프로그램 집합에 대해서, 본 논문에서 제시하는 방법의 우수성을 보이고자 한다.
본 연구에는 위에서 제시한 여러 문제에도 불구하고 현재까지 개발된 기존의 표절 탐색보다는 진일보된 새로운 방법을 제시하고 그 방법이 보다 타당함을 다양한 데이터와 실험의 특성값을 비교함으로 보이고자 한다. 그리고 지금까지 수집된 몇 가지 표절 데이터를 이용하여 우리가 개발한 방법이 기존의 방법보다 더 우수함을 보인다.
본 연구에는 이러한 저작물 중에서 프로그래밍 소스의 표절관계를 탐색하기 위한 기초적인 자료를 조사하고 이를 바탕으로 어떻게 프로그램의 표절을 찾아낼 수 있는지에 대하여 논의하고자 한다. 일반적으로 프로그램의 표절은 어떤 프로그램 A와 프로그램 B 사이에 유사한 면이 있는지를 소스코드 수준에서 살펴보는 것이다.
관해 기술한다. 여기서는 ICPC 2005 프로그램 그룹 중에서도 가장 순서쌍 수가 많은 프로그램 그룹 1 에 대하여 유사도 분포를 조사하였다. 고정적 유사도 행렬을 채택하였을 경우와 적응적 유사도 행렬을 채택하였을 경우에 대해 유사도 분포를 조사하였는데, 적응적 유사도의 경우에는 a값을 0.
우리는 본 논문에서 제시한 적웅적 방법이 이 차이를 잘 극복해 주었다는 것을 지적하고자 한다. 즉 for 루프 조건을 바꾸는 구간이 다소 길긴 하지만 적응적 방법에서는 그 불일치(mismatch)값이 고정적인 불일치 값인 -1보다 작으므로 그 뒤의 매칭을 포함시킨 부분 정렬을 구성하였다.
따라서 이들 간의 비교는 하지 않았다. 우리는 이 중에서 9번, 10번, 63번 프로그램(각각 鸟, 戸】。, /%3으로 표기)을 선택해서 고정적 방법과 적응적 방법의 결과를 비교해 보고자 한다. 즉 그 유사도의 순위가 각 방법에서 서로 다르게 나타난 (鸟, 4。)쌍과 (孔, 孔3)쌍을 서로 비교해 보고자 한다.
돌린 결과 유사하다고 판정된 프로그램의 쌍은 모두 10개가 추출되었다. 우리는 이 프로그램을 각각 하나씩 검사하여 실제 표절이 이루어졌는지 살펴보았다. 그 중 완전히 복사한 프로그램 한 쌍을 찾아내서 이 팀은 이후에 불이익을 받게 하였다.
우리는 이 중에서 9번, 10번, 63번 프로그램(각각 鸟, 戸】。, /%3으로 표기)을 선택해서 고정적 방법과 적응적 방법의 결과를 비교해 보고자 한다. 즉 그 유사도의 순위가 각 방법에서 서로 다르게 나타난 (鸟, 4。)쌍과 (孔, 孔3)쌍을 서로 비교해 보고자 한다.
유사도의 분포 차이를 살펴본다. 특히 적응적 유사도에 대해서는 매개변수 a 값과 /3 값을 변경시킴으로써 어떻게 분포가 변화하는지 살펴본다. a 값을 늘리면 일 .
표 1에 수집된 테스트 데이터 프로그램 집합에 대하여 실제 표절 프로그램을 찾아내기 위해서 모든 데이터셋에 대해 검사해 보았다. 과거 발표된 연구 결과에서는 인위적인 표절을 수행한 프로그램에 대해 표절 검사를 수행하였다.
제안 방법
고정적 유사도 행렬 (fixed similarity matrix)을 채택하였을 경우와 적응적 유사도 행렬(adaptive similaiity matrix)을 채택하였을 경우에 대하여 지역정렬 알고리즘을 수행하였다. 각 경우에 유사도 점수 분포와 유사도가 높은 구간을 비교하여 살펴보았다. 우리는 리눅스가 탑재된 Intel Pentium PC에서 유사도 검출 프로그램을 수행하여 유사도를 산출하였다.
간단한 실험을 수행하였다. 고정적 유사도 행렬 (fixed similarity matrix)을 채택하였을 경우와 적응적 유사도 행렬(adaptive similaiity matrix)을 채택하였을 경우에 대하여 지역정렬 알고리즘을 수행하였다. 각 경우에 유사도 점수 분포와 유사도가 높은 구간을 비교하여 살펴보았다.
여기서는 ICPC 2005 프로그램 그룹 중에서도 가장 순서쌍 수가 많은 프로그램 그룹 1 에 대하여 유사도 분포를 조사하였다. 고정적 유사도 행렬을 채택하였을 경우와 적응적 유사도 행렬을 채택하였을 경우에 대해 유사도 분포를 조사하였는데, 적응적 유사도의 경우에는 a값을 0.4에서 0.7까지 변화시켜 가며 유사도 분포를 조사하였다. 유사도 분포를 표로 정리하면 표 2와 같다.
대해 검사해 보았다. 과거 발표된 연구 결과에서는 인위적인 표절을 수행한 프로그램에 대해 표절 검사를 수행하였다. 그러나 이러한 인위적인 표절은 실제 현장에서 행해지고 있는 표절과는 차이가 있다.
구체적인 유사구간은 각 토큰별 유사도 값에 따라서 결정되므로 유사도 행렬 값에 따라 달라질 수 있기 때문이다. 구체적인 프로그램에 대해서 유사도가 다르게 나타나는 구간을 살펴보기 위해 표절로 의심되는 코드에 대해서 유사구간을 비교해 보았다.
제안된 알고리즘은 적응적으로 유사도를 산출하므로 테스트 데이터 셋으로 사용될 프로그램 집합은 같은 목적으로 작성된 프로그램들로 구성되어야 한다. 그래서 이 논문에서는 과제 및 경시대회 문제에 대한 프로그램을 선정하였다.
이 값의 비율을 직접적으로 비교하면 약 5000배에 해당하므로 이 값을 그대로 쓰는 것은 거의 의미가 없다고 할 수 있다. 따라서 본 연구에서는 그 출현 빈도가 약 2배 차이가 날 때 실제 가중치는 1 정도 차이가 나는 것이 합리적이라 판단하여 1O&로 계산하기로 했다.
여기서는 ICPC 2005의 그룹 1에 대해서만 기술하였지만, 다른 데이터 셋에 대해서도 유사도 분포를 조사하였다. 그러나 데이터 셋에 따라 분포가 달라지는 경우는 확인할 수 없었다.
우리는 ICPC 그룹 A의 프로그램을 대상으로 고정적 방식과 적응적 방식으로 표절 여부를 비교해보았다. 표 3에는 각 유사도 행렬로 비교했을 때 나타난 유사 프로그램의 쌍이 순서대로 정렬되어 있다.
각 경우에 유사도 점수 분포와 유사도가 높은 구간을 비교하여 살펴보았다. 우리는 리눅스가 탑재된 Intel Pentium PC에서 유사도 검출 프로그램을 수행하여 유사도를 산출하였다. 유사도 검출 프로그램은 Java L5.
첫째, 키워드 빈도를 특성 변수로 이용하여 적응적으로 유사도를 산출하는 방법을 제안하였다. 이를 위해, 특정 목적으로 작성된 프로그램 그룹에 대하여 키워드 빈도를 산출하였고 이들 빈도의 로그를 취하여 적응적 유사도 행렬을 정의하였다. 결과로 얻어진 유사도 행렬을 바탕으로 세 가지 유사도 SIMgSIMgeSIMmm 를 정의하였다.
적응적 지역정렬 알고리즘의 효과를 실험해 보기 위해, 간단한 실험을 수행하였다. 고정적 유사도 행렬 (fixed similarity matrix)을 채택하였을 경우와 적응적 유사도 행렬(adaptive similaiity matrix)을 채택하였을 경우에 대하여 지역정렬 알고리즘을 수행하였다.
수 있다. 첫째, 키워드 빈도를 특성 변수로 이용하여 적응적으로 유사도를 산출하는 방법을 제안하였다. 이를 위해, 특정 목적으로 작성된 프로그램 그룹에 대하여 키워드 빈도를 산출하였고 이들 빈도의 로그를 취하여 적응적 유사도 행렬을 정의하였다.
대상 데이터
그리고 공공기관에서 일반적인 프로그램의 표절판정을 위한 도구로서 두 프로그램간의 유사한 코드끼리 상호 비교해주는 도구 exEYEs가 프로그램 심의조정위원회에서 개발되어 무료로 제공되고 있다. 공개 판을 받을 수 있는 사이트는 www.pdmc.or.kr 이다.
언어에 종속적이다. 이 논문에서 구현한 유사도 검출 프로그램은 C/C++ 언어를 대상으로 하고 있다. 현재 구현된 유사도 검출 프로그[램에서는 C/C++ 언어 키워드 중 81개의 키워드를 선정하여 프로그램 선형화 에이용하고 있다(r = 81).
테스트 데이터 프로그램으로는 부산대학교 2005년도 고급 컴퓨터 프로그래밍 교과에서 과제로 제출된 프로그램과 한국정보올림피아드 (KOI: Korea Olympiad in Informatics) 2004년도 및 2006년도 예선 문제, ACM 국제 대학생 프로그래밍 경진대회 (ICPC:Intemational Collegiate Programming Contest) 2004년도 및 2005년도 아시아 지역 예선 문제에 대한 출전자 제출 프로그램을 사용하였다. 테스트 데이터 셋을 정리하면 표 1과 같다.
성능/효과
ICPC 예선 대회가 끝난 후 본 연구자들이 개발한 초기 버전으로 돌린 결과 유사하다고 판정된 프로그램의 쌍은 모두 10개가 추출되었다. 우리는 이 프로그램을 각각 하나씩 검사하여 실제 표절이 이루어졌는지 살펴보았다.
이를 위해, 특정 목적으로 작성된 프로그램 그룹에 대하여 키워드 빈도를 산출하였고 이들 빈도의 로그를 취하여 적응적 유사도 행렬을 정의하였다. 결과로 얻어진 유사도 행렬을 바탕으로 세 가지 유사도 SIMgSIMgeSIMmm 를 정의하였다.
그리고 지금까지 수집된 몇 가지 표절 데이터를 이용하여 우리가 개발한 방법이 기존의 방법보다 더 우수함을 보인다. 본 논문에서는 특정 프로그램 집합으로 제한된 환경에서의 표절 검사에 초점을 맞추고 있다.
둘째, 이전의 고정적 유사도 행렬에 비하여 적응적 유사도 행렬을 이용하는 것이 표절 탐색에 더 효과적임을 실험을 통해 보였다. 특히 일반적으로 잘 사용하지 않는 특별한 방법을 사용하거나 구문 형태를 고쳐서 그 형식이 드러나지 않게 고치는 일에 많은 비용이 든다고 가정할 때, 각 키워드의 비율의 비중을 고려한 적응적 유사도 행렬에 의한 표절 탐색 방법은 이전의 단순한 일치/불일치로만 계산하는 기존의 방법에 비해서 상당히 효과적이다.
그러나 이러한 인위적인 표절은 실제 현장에서 행해지고 있는 표절과는 차이가 있다. 따라서 우리는 실제 프로그래밍 경진대회나 실제 과제 제출 프로그램을 대상으로 하여 표절을 검사하였으며, 그 결과 ICPC 프로그램 그룹에서 표절로 의심되는 프로그램을 찾을 수 있었다. 개인 정보 보호를 위해 이 프로그램 그룹을 ICPC 그룹 A 라고 지칭하겠다.
이 때문에 본 연구의 방법으로 표절을 탐색하는 것은 표절의 가능성이 있는 프로그램들의 집합을 1차 선별해주는 것이지 그 결과가 바로 표절된 결과임을 증명해주는 것이 아니다. 본 논문이 제시한 방법론의 주된 기여는, 수작업을 통한 표절가능 프로그램 쌍을 찾아내는 작업을 보다 빠르게 수행할 수 있도록, 잘못된 판별 (false-negativee false-positive) 의 수를 최소화하는 전처리 단계를 제공했다는 점이다.
실제로 log를 취한 값을 사용할 것인지 아닌지는 실험에 따라서 달라져야 하겠지만 본 유사도 검출의 경우에는 log를 취한 값을 사용하는 것이 바람직하다고 판단하였다. 왜냐하면 키워드 빈도의 차이가 크므로 키워드의 상대적인 비율을 그대로 매칭 가중치에 반영하는 것은 바람직하지 못하기 때문이다.
이상의 실험결과를 통해, 고정적 유사도 행렬을 이용할 경우와 적응적 유사도 행렬을 이용할 경우에 유사도 분포는 크게 다르지 않음을 알 수 있었다. 그러나 구체적으로 유사한 구간은 앞선 실험에서 확인할 수 없었는데, 여기서는 구체적인 유사구간의 차이를 살펴본다.
그 중 완전히 복사한 프로그램 한 쌍을 찾아내서 이 팀은 이후에 불이익을 받게 하였다. 조사 결과 시합 중 한 팀이 다른 지역의 팀에게 인터넷으로 해답 프로그램을 전송해 준 것으로 나타났다.
표 2에서 확인할 수 있는 바와 같이 고정적 유사도 행렬을 채택하였을 경우와 적응적 유사도 행렬을 채택하였을 경우에 유사도 절대값 松분포는 상당히 다른 형태로 나타났다. 그 이유는 翎以血가 유사도 절대 수치 값을 반환하기 때문이다.
후속연구
첫째, 적응직 유사도 행렬을 제어하는 두 매개변수 a와 를 조절하여 가장 최적의 값을 실제 표절 프로그램, 또는 인위적으로 만든 표절 프로그램을 이용하여 찾는 문제도 홍미로운 문제가 된다. 이 경우 프로그램들 간의 유사도 점수는 대략적으로 왼쪽으로 치우친 모양의 Poisson 분포를 따르는 것으로 예상되지만 실제 그 분포에 대한 연구는 추후 더 정교하게 진행되어야 할 것이다. 따라서 실제 테스트용으로 사용될 수 있는 표절 프로그램을 대량으로 수집하여 집중적으로 그 특성을 알아보는 작업이 필요하므로 표절 프로그램을 수집하는 것이 필요하다.
참고문헌 (14)
조동욱, 소정, 김진용, 최병갑, 김선영, 김지영, 프로그램 표절 감정 툴에 대한 비교 분석 및 개발 툴에 대한 방향제시, 제20회 한국정보처리학회 추계학술대회논문집, 10권, pp. 757,760, 2003
Brenda Cheang, Andy Kumia, Andrew Lim, and Wee-Chong Oon. On automated grading of programming assignments .n an academic institution. Computer and Education, 41:121-131, 2003
Janet Garter. Collaboration or plagiarism: What happens when students work together. In Proceeding of the 4th Annual SIGCSE/SIGCUE Conference on Innovation and Technology in Computer Science Eduwtion(ITICSE-99), volume 31 of SIGCSE Bulletin inroads, page 52-55, N.Y., June 27- July 1 1999. ACM Press
Paul Clough. Plagiarism in natural and programming languages: An overview of current tools and technologies. Technical report, University of Sheffield, Department of Computer Science, June 2000
R. James, C. McInnis, and M. Devlin. Plagiarism detection software: How effective is it?, 2002. Except from R. James, C. McInnis, and M. Devlin, ？Assessing Leaming in Australian Universities: Ideas, strategies and resources for quality in student assessment. Centre for the Study of Higher Education, Australian Universities Teaching Committee, Melbourne, ustralia, 2002 (http://www.cshe.unimelb.edu.au/assessingleaming/ docs/PlagSoft ware.pdf)
Thomas Schmidt and Jens Stoye. Quadratic time algorithms for finding common intervals in two and more sequences. In Proceedings of the 15th Annual Symposium on Combinatorial Pattem Matching(CPM 2004), volume 3109 of Lecture Notes in Computer Science, pages 347-358. Springer, 2004.
이효섭, 도경구, 프로그램 표절 검출 방법에 대한 조사, 한국정보과학회 한국컴퓨터종합학술대회 2005 논문집(B), 32권, pp, 916-917, 2005
Kristina L. Verco and Michael J. Wise. Software for detecting suspected plagiarism: Comparing structure and attribute-counting systems. In Proceedings of the 1st Australian Conference on Computer Science Education, pages 130-134, Sydney, Australia, July 1996
M. Joy and M. Luck. Plagiarism in programming assignments. IEEE Transactions of Education, 42(2):129-133, May 1999
Jeong-Woo Soon, Seong-Bae Park, and SeYoung Park. Program plagiarism detection using parse tree kernels. In Proceedings of the 9th Pacific Him International Conference on Artificial Intelligence (PHICAI 2006), volume 4099 of Lecture Notes in Computer Science, pages 1000-1004. Springer, August 2006
Lutz Prechelt, Guido Malpohl, and Michael Philippsen. Finding plagiarisms among a set of programs with JPlag. Journal of Universal Computer Science, 8(11):1016-1038, 2002
Xin Chen, Brent Francia, Ming Li, Brian McKinnon, and Amit Seker. Shared information and program plagiarism detection. IEEE Transactions on Information Theory, 50(7):1545-1551, 2004
※ AI-Helper는 부적절한 답변을 할 수 있습니다.