컴퓨터와 소프트웨어의 사용이 증가하면서, 프로그램 소스의 도용(표절)이 사회적인 문제로 부각되고 있다. 이런 문제를 해결하고자 프로그램의 문법 구조를 비교하여 표절을 찾아내는 방법론이 제안되었지만, 간단한 프로그램 수정에도 표절을 찾아내지 못하는 한계를 가지고 있다 이 연구에서는, 문법 구조적인 정보 뿐 아니라, 프로그램식 간의 수행시 의존 관계를 드러내는 그래프를 이용한 프로그램 표절 감지 시스템을 제안한다. 이 방법론은 문법 정보 뿐 아니라, 수행시 의존 관계까지 비교 대상에 을림으로써, 수행시 의콘 관계를 변화시키지 못하는 프로그램 수정에 대해서도 프로그램 표절을 판별할 수 있다. 또한, 이 연구에서는 표절 프로그램이란 무엇인가를 엄밀하게 정의하고 이 표절 프로그램의 정의와 연구에서 제안된 표:늰 감별 그래프와의 관계를 보였다. 즉, 두 프로그램이 표절이라는 것은 표절 감별 그래프가 일치한다는 긴과 필요 충분 관계가 있음을 증명하였다. 또한 제안된 표절 감별 방법론을 실제적인 프로그래밍 언어인 IML 에 대해서 구현하였다. 구현된 도구를 통해서 실제 표절된 프로그램들을 감별한 결과, 기존의 방법에서 찾기 어려운 프로그램 표절을 제안된 방법론이 다룰 수 있음을 확인하였다.
컴퓨터와 소프트웨어의 사용이 증가하면서, 프로그램 소스의 도용(표절)이 사회적인 문제로 부각되고 있다. 이런 문제를 해결하고자 프로그램의 문법 구조를 비교하여 표절을 찾아내는 방법론이 제안되었지만, 간단한 프로그램 수정에도 표절을 찾아내지 못하는 한계를 가지고 있다 이 연구에서는, 문법 구조적인 정보 뿐 아니라, 프로그램식 간의 수행시 의존 관계를 드러내는 그래프를 이용한 프로그램 표절 감지 시스템을 제안한다. 이 방법론은 문법 정보 뿐 아니라, 수행시 의존 관계까지 비교 대상에 을림으로써, 수행시 의콘 관계를 변화시키지 못하는 프로그램 수정에 대해서도 프로그램 표절을 판별할 수 있다. 또한, 이 연구에서는 표절 프로그램이란 무엇인가를 엄밀하게 정의하고 이 표절 프로그램의 정의와 연구에서 제안된 표:늰 감별 그래프와의 관계를 보였다. 즉, 두 프로그램이 표절이라는 것은 표절 감별 그래프가 일치한다는 긴과 필요 충분 관계가 있음을 증명하였다. 또한 제안된 표절 감별 방법론을 실제적인 프로그래밍 언어인 IML 에 대해서 구현하였다. 구현된 도구를 통해서 실제 표절된 프로그램들을 감별한 결과, 기존의 방법에서 찾기 어려운 프로그램 표절을 제안된 방법론이 다룰 수 있음을 확인하였다.
Stealing the source code of a program is a serious problem not only in a moral sense but also in a legal sense. However, it is not clear whether the code of a program is copied from another or not. There was a program similarity checker detecting code-copy by comparing the syntax trees of programs. ...
Stealing the source code of a program is a serious problem not only in a moral sense but also in a legal sense. However, it is not clear whether the code of a program is copied from another or not. There was a program similarity checker detecting code-copy by comparing the syntax trees of programs. However this method has a limitation that it cannot detect the code-copy attacks when the attacker modifies the syntax of the program on purpose. We propose a program similarity check by program control graph, which reveals not only syntax information but also control dependancy. Our method can detect the code-copy attacks that do not change control dependancy Moreover, we define what code-copy means and establish the connection between code-copy and similarity of program control graph: we prove that two programs are related by copy congruence if and only if the program control graphs of these programs are equivalent. We implemented our method on a functional programming language, nML. The experimental results show us that the suggested method can detect code similarity that is not detected by the existing method.
Stealing the source code of a program is a serious problem not only in a moral sense but also in a legal sense. However, it is not clear whether the code of a program is copied from another or not. There was a program similarity checker detecting code-copy by comparing the syntax trees of programs. However this method has a limitation that it cannot detect the code-copy attacks when the attacker modifies the syntax of the program on purpose. We propose a program similarity check by program control graph, which reveals not only syntax information but also control dependancy. Our method can detect the code-copy attacks that do not change control dependancy Moreover, we define what code-copy means and establish the connection between code-copy and similarity of program control graph: we prove that two programs are related by copy congruence if and only if the program control graphs of these programs are equivalent. We implemented our method on a functional programming language, nML. The experimental results show us that the suggested method can detect code similarity that is not detected by the existing method.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구는 기존의 연구들에서 벗어나지 못한 문법 구 조 기반의 비교를 벗어나서, 실제 프로그램 흐름 정보를 드러내는 새로운 구조를 제안한다. 연구에서 사용되는 흐름 정보는 프로그램 분석을 이용한 정확한 흐름 분석 이므로 [7]에서 人'용한 프로그램 흐름 예측과 매우 다르 다.
연구에서 제안하는 표절 감별 그래프를 이용하면 기존의 연구에서 감별하지 못하는 프로그램 표절을 감별해 낼 수 있다. 이 연구에서는 “프로그램 표절”를 명확히 정의하 고, “프로그램 표절”과 “표절 감별 그래프의 일치”에 대해서 이론적인 맥을 세우고자 한다.
이 연구에서는, 문법의 구조적인 정보 뿐 아니라, 프 로그램식 간의 수행시 의존 관계도 드러내는 그래프를 이용한 프로그램 표절 감지 시스템을 제안한다. 연구에서 제안하는 표절 감별 그래프를 이용하면 기존의 연구에서 감별하지 못하는 프로그램 표절을 감별해 낼 수 있다.
가설 설정
단, /'는 프로그램식 。'에 나타나는 변수들이고, 로 치환할 때 气 속의 묶인(bound) 변수들과 레 이블들은 새로운 변수들과 새로운 레이블로 바뀌어 있다고 가정한다. □
보조 정리 2. 质(P네 느 P, 단 R 는 F의 끼운 프 로그램이고, 厂T|[R(3네와 P, 에 나타나는 변수 이름은 전역 변수를 제외하고는 다르다고 가정한다.
일반적으로 임의의 표절 감별 그래프에 대해 연관된 프로그램이 항상 존재하지는 않는다. 우리는 안전성을 위해서 임의의 표절 감별 그래프를 고려하지 않고, 제한 된 형태의 표절 감별 그래프만을 가정한다. 제한된 형태의 표절 감별 그래프는 존재하는 프로그램으로부터 만 들어진 그래프이다.
De Bruijn 표기법을 포함하는 변형된 프로그램 문법 은 그림 2와 같다. 이 문법 구조는 두 가지 가정을 한 다: (1) 모든 프로그램식은 유일한 레이블을 가진다, (2) 모든 프로그램 변수는 서로 다르다.
제안 방법
우리는 제안된 방법론을 실제로 사용되는 프로그래밍 언어인 nMUlO]에 적용하여 구현하였다. 우선, 두 개의 프로그램이 앞서 정의된 표절 관계에 있음을 표절 감별 그래프를 이용한 방법으로 구현하였다. 구현된 프로그램을 이용하면 두 프로그램이 표절 관계에 있는지 없는지 손쉽게 알 수가 있다.
최근에 발표된 유전체 서열의 정렬 기법을 이용한 표 절 검사[7, 8]는 요즘 널리 연구되고 있는 유전자 염기 서열 비교 방법론을 표절 검사에 응용하였다. 이 방법은 프로그램의 키워드들을 아미노산에 매핑하여 염기 서열 들을 검사하는 방법으로 표절 검사를 수행한다. 또한, 프로그램 흐름을 예측해서 흐름 순서대로 키워드들을 배치하여서, 프로그램 순서를 바꾸거나 안 쓰이는 코드 를 삽입한 표절을 잘 검사할 수 있었다.
이 연구에서는 위의 프로그램 문법을 De Bruijn 표기 법[9]을 포함하는 문법 구조로 변형하여 사용한다. 변형 된 문법은 함수의 인자 대신 De Bruijn 표기법을 사용 한다.
이 연구에서는 프로그램 표절 감별을 위해서 프로그 램의 표절 감별 그래프를 제시하였다. 프로그램을 제시 된 그래프로 바꾸어 비교를 하면, 프로그램의 문법 정보 뿐 아니라, 바인딩 정보까지도 드러낼 수 있기 때문에, 문법 구조만을 비교하는 이전의 방법보다 훨씬 더 효과적으로 표절 프로그램을 찾아낼 수 있다.
이론/모형
따라서, 프로그램 표절 감별의 폭을 넓히기 위해서, 두 프 로그램의 일부가 표절 관계에 있는 경우를 포괄하는 비교 알고리즘이 표절 감별 검사 도구에 포함될 필요가 있다. 기존의 여러가지 구조적인 비교 알고리즘 중에 서, 우리는 CloneChecker의 알고리즘을 사용하여 프로 그램의 일부가 표절 관계인 경우를 고려하였다.
이 연구에서는 위의 프로그램 문법을 De Bruijn 표기 법[9]을 포함하는 문법 구조로 변형하여 사용한다. 변형 된 문법은 함수의 인자 대신 De Bruijn 표기법을 사용 한다. 변형된 문법 구조를 사용하는 데에는 두 가지 이 유가 있다.
우리는 제안된 방법론을 실제로 사용되는 프로그래밍 언어인 nMUlO]에 적용하여 구현하였다. 우선, 두 개의 프로그램이 앞서 정의된 표절 관계에 있음을 표절 감별 그래프를 이용한 방법으로 구현하였다.
성능/효과
기존의 문법 구조 기반 의 표절 감별 연구에서 찾아내지 못하는 프로그램 표절 을, 제안된 방법론은 찾아낼 수 있다. 결론적으로, 제안 된 방법론이 기존의 문법 구조 기반의 표절 감별 연구에서 다루지 못하는 흐름 구조를 이용한 표절의 시도를 확실하게 감별함으로써, 기존의 방법과 함께 다양한 표 절 시도를 막을 수 있는 보다 강력한 표절 감별 도구를 개발하였다는 데에 의의가 있다.
이 방법은 프로그램의 키워드들을 아미노산에 매핑하여 염기 서열 들을 검사하는 방법으로 표절 검사를 수행한다. 또한, 프로그램 흐름을 예측해서 흐름 순서대로 키워드들을 배치하여서, 프로그램 순서를 바꾸거나 안 쓰이는 코드 를 삽입한 표절을 잘 검사할 수 있었다. [8]에서는 서열 의 유사도를 가장 유사한 한 부분에 대해서만 계산하는 것이 아니라, 서열의 여러 부분에서도 재귀적으로 같은 방법을 적용시킴으로 기존의 방법을 개선하였다.
두 개념이 정확하게 일치한다는 것은 두 개념 사이에 완전(completeness)하고 안전 (soundness)한 관계가 있음을 말한다. 먼저, 두 프로그 램이 정의된 표절 관계에 있을 때, 각 프로그램의 표절 감별 그래프도 일치 관계에 있음을 의미하는 완전성을 보인다. 그리고 표절 감별 그래프가 일치하는 두 프로그 램은 서로 표절 관계에 있음을 의미하는 안전성을 보인다.
실험 데이타를 통해서, 구현된 검사 도구가 기존의 CloneChecker와 상호 보완적으로 프로그램 표절 검사 에 사용될 수 있음을 확인할 수 있다. 또 더 나아가서, 우리의 표절 감별 방법에 걸맞는 가중치 있는 부분 프로그램 비교 알고리즘올 고안한다면, 지금보다 높은 분 별력을 가진 표절 검사 도구가 될 수 있을 것이다.
이 연구에서는, 문법의 구조적인 정보 뿐 아니라, 프 로그램식 간의 수행시 의존 관계도 드러내는 그래프를 이용한 프로그램 표절 감지 시스템을 제안한다. 연구에서 제안하는 표절 감별 그래프를 이용하면 기존의 연구에서 감별하지 못하는 프로그램 표절을 감별해 낼 수 있다. 이 연구에서는 “프로그램 표절”를 명확히 정의하 고, “프로그램 표절”과 “표절 감별 그래프의 일치”에 대해서 이론적인 맥을 세우고자 한다.
논문의 7장에서 CloneChecker의 방 법과 그 방법론을 우리의 방법과 함께 사용한 실험결과를 보인다. 이 실험 결과는 우리의 방법론을 기존의 방법과 함께 사용하였을 때, 서로 상호 보완적인 효과를 가짐을 보이고 있다.
83)은 우리의 방법에서 가장 높은 유사도를 나타내었다. 저자가 그 프 로그램짝을 직접 눈으로 비교해 본 결과, 예상과 같이 let 등의 코드를 이용하여, CloneCheckere]- 감별하지 못할 정도의 작은 수정을 시도한 프로그램짝이었다.
하지만, 제안된 방법론도 역시 프로그램의 의미보다는 문법 구 조에 치우쳐 비교를 하므로, (5) 부분적인 수행 (예를 들어, 상수로 바꾸기) 에 관해서는 표절 시도를 찾아 낼 수 없는 단점이 있다. 제안된 방법의 가장 큰 장점 중 하나는 (1)에서 (4)의 일부를 포함하는 표절 시도를 한 꺼번에 여러 번 적용하여도 완벽하게 표절 감별을 할 수 있다는 것이다.
제안된 방법의 구현을 통해서, 기존의 nML 프로그램 표절 감별에 본 연구가 기존의 연구와 함께 효율적으로 사용될 수 있음으로 확인하였다. 기존의 문법 구조 기반 의 표절 감별 연구에서 찾아내지 못하는 프로그램 표절 을, 제안된 방법론은 찾아낼 수 있다.
우리는 또한 표절 프로그램이란 무엇인가를 엄밀하게 정의하고 이 표절 프로그램의 정의와 표절 감별 그래프와의 관계를 보였다. 즉, 두 프로그램이 표절이라는 것은 표절 감별 그래프가 일치한다는 것과 필요 충분 관계에 있음을 증 명하였다.
후속연구
실험 데이타를 통해서, 구현된 검사 도구가 기존의 CloneChecker와 상호 보완적으로 프로그램 표절 검사 에 사용될 수 있음을 확인할 수 있다. 또 더 나아가서, 우리의 표절 감별 방법에 걸맞는 가중치 있는 부분 프로그램 비교 알고리즘올 고안한다면, 지금보다 높은 분 별력을 가진 표절 검사 도구가 될 수 있을 것이다.
참고문헌 (10)
장성순, 서선애, 이광근, '프로그램 유사성 검증기', 한국정보과학회,가을 학술 회의, 제 28권,pp. 334-336, 2001년 10월
서선애, 한태숙, '흐름 그래프 형태를 이용한 프로그램 유사성 비교' 학술 논문, 한국과학기술원 전산학과 프로그래밍 언어 연구, 2004년 10월. http://ropas.kaist.ac.kr/-saseo/papers/kor_simil_long.pdf
Dick Grune, 'SIM: The software and text similarity tester SIM,' http://www.few.vu.nl/-dick/sim.html
M.J. Wise. 'YAP3: improved detection of similarities in computer programs and other texts,' SIGCSEB: SIGCSE Bulletin (ACM Special Interest Group on Computer Science Education),' volume 28, 1996
이평준, 전명재, 조환규, '재귀적 지역정렬을 이용한 프로그램 표절 탐색' 한국정보과학회 봄 학술 회의, 2004년 4월
N. De Bruijn, 'Lambda-calculus Notation with Nameless Manipulation,' A Toolfor Automatic Formula Manipulation, volume 34, pp. 381-392, 1972
이광근, 이욱세, 어현준, 김정택, 최용식, 류석영, 강현구, 서선애, 장성순, 김범식,'nML 컴파일러 시스템 (status report)'. 한국정보과학회 가을 학술 회의, 제 28권. pp. 340-342, 2001년 10월 http://ropas. kaist.ac.kr/n
※ AI-Helper는 부적절한 답변을 할 수 있습니다.