A code theft may make severe damages to the companies that have software as their major assets. To deal with code thefts, various methods have been developed such as software tamper proofing, code obfuscation, software watermarking, and software birthmarking. Software tamper proofing and code obfuscation are techniques to prevent or hinder illegal uses of program codes. Software watermarking and software birthmarking are techniques to confirm that software is illegally copied or contained in another programs. Software watermarking is different from software birthmarking in a sense that software watermarking embeds watermarks in software and extracts them to verify the originality of programs, while techniques of software birthmarking only utilize program codes themselves. Software birthmarking is considered as one of code plagiarism detection techniques. However, the term software birthmarking is used for detecting code theft in executable files, while the term code plagiarism detection is used for detecting code theft in source codes.
In this thesis, software birthmarking techniques for binary executables are proposed. Prior to this research, software birthmarking has been targeted to executable files that are composed of intermediate codes such as Java bytecodes, which are simpler to analyze than OS-dependant binary executables. However, these binary executables account for higher proportion in real world applications than intermediate code executables. Besides, most lawsuits on code theft are related to binary executables. For these reasons, most birthmarking techniques target binary executables for the practical usage.
The proposed birthmarks for binary executables are as follow:
- a static API birthmark for binary executables that utilizes call graphs and API function calls, and
- a dynamic API birthmark for binary executables that utilizes API function call traces at run-time.
API functions are utilized as birthmarks for two reasons. The first is that API functions are massively called in most programs because API functions must be called to use system resources such as memory, disk, and network. The second is that API function calls found in source codes are preserved in binary executables even after compilation.
In a static API birthmark for binary executables a program birthmark is defined as a set of function birthmarks. A function birthmark is a set of API calls that are invoked during the execution of programs. To compute function birthmarks, executable files are disassembled.
From the disassembled code, functions, function calls and API calls are identified. In addition, call graphs are constructed by analyzing function calls. With the call graphs and API calls, each function birthmark is computed by collecting API calls in itself and its calling functions. A program birthmark is a set of function birthmarks. To compare two program birthmarks, maximum weighted bipartite graph matching algorithms are applied. In the matching, programs are partitions, functions are nodes, edges are similarities between functions, and a maximum weighted bipartite matching is a set of function pairs that maximizes the sum of edge weights. A program similarity between two programs is the average of function similarities in the maximum weighted bipartite matching between two programs. To check library module theft, containments are computed that measures how much a library is contained in a suspicious program.
A dynamic API birthmark for binary executables is defined as the API call sequence during the execution of a program. To get API call sequences, an API hooking method is used. An API call sequence is considered as a string of API calls. To compare two birthmarks, the semi-global alignment algorithm is applied. It takes two strings as inputs and gives a similarity between two strings by normalizing the match value with the length of a short sequence.
A static API birthmarking system and a dynamic API birthmarking system for binary executables are implemented to evaluate the proposed birthmarks. Real world Windows applications in various categories are tested to evaluate the proposed birthmarks. Experimental results show that our birthmarks are effective in detecting code theft for Windows binaries.
코드 도용은 소스 코드를 주요 자산으로 하고 있는 기업들에게 많은 손해를 끼치고 있다. 코드 도용을 방지하기 위하여 소프트웨어 변조 방지 기술, 코드 난독화 기술, 소프트웨어 워터마킹 기술, 소프트웨어 버스마킹 기술과 같은 다양한 방법이 계발되어 왔다. 소프트웨어 변조 방지 기술과 코드 난독화 기술은 직접적으로 소스 코드가 도용되는 것 자체를 방지하기 위한 기술이다. 소프트웨어 워터마킹 기술과 소프트웨어 버스마킹 기술은 코드가 도용되었을 때 의심되는 코드를 기존의 소스 코드와 비교하여 도용 여부를 판별하는 기술이다. 소프트웨어 워터마킹과 소프트웨어 버스마킹은 프로그램에 저작권 정보를 포함하는가의 여부에 따라서 구별된다. 소프트웨어 워터마킹은 소스 코드 소유자가 워터마크라고 부르는 저작권 정보를 직접 프로그램에 포함시켜 프로그램 도용이 의심되는 경우 해당 프로그램에서 워터마크를 추출하여 도용을 판정한다. 소프트웨어 버스마킹은 특별한 정보 삽입 없이 코드 자체에 대한 분석을 통하여 코드의 고유한 특징이라고 여겨지는 버스마크를 추출하고 프로그램을 비교 분석하여 도용을 판정한다. 소프트웨어 버스마킹 기술은 일종의 소프트웨어 위조 탐지 기술이라고도 볼 수 있다. 두 용어는 적용 대상에 따라 달라진다. 소프트웨어 위조 탐지라는 용어는 주로 소스 코드에 대한 위조 탐지에 사용되며 소프트웨어 버스마킹이라는 용어는 실행 파일에 대한 도용 탐지에 사용된다.
본 논문에서는 특별히 바이너리 실행 파일에 대한 소프트웨어 버스마킹 기술을 제안하고 있다. 이전까지 소프트웨어 버스마킹 기술은 주로 자바 바이트코드와 같이 분석이 용이한 중간 코드로 구성된 실행 파일에 대해 적용되어 왔다. 그러나 많은 프로그램이 중간 코드보다는 네이티브 코드로 구성된 바이너리 실행 파일 형태로 되어 있다. 또한 실제 발생하고 있는 코드 도용 사례들은 대부분 바이너리 실행 파일에 대한 것이다. 따라서 우리가 제안하고 있는 바이너리 실행 파일에 대한 소프트웨어 버스마킹 기술은 실제 코드 도용의 사례에 사용될 수 있는 더 실용적인 기술이라고 볼 수 있다.
이 논문에서는 바이너리 실행 파일에 대한 두 가지 버스마크를 제시한다. 첫째, 바이너리 코드에서의 함수 호출 관계와 API 호출에 기반한 정적 API 버스마크. 둘째, 바이너리 코드에서의 API 호출 트레이스를 이용한 동적 API 버스마크이다. API 함수는 프로그램이 메모리와 디스크와 같은 시스템 자원을 이용하기 위하여 필수적으로 호출해야 한다. 따라서 API 함수 호출을 이용한 버스마크를 정의하게 되면 대부분의 프로그램에 적용 가능하기 때문이다. 또한 소스 코드에서 API 함수 호출은 사용한 경우에 반드시 바이너리 실행 파일에 나타나기 때문에 소스 코드의 특징을 가장 잘 반영한다고 볼 수 있다는 장점이 있다.
바이너리 코드를 위한 정적 API 버스마크는 프로그램을 함수의 집합으로 보고 각 함수의 버스마크의 집합을 프로그램의 버스마크로 정의한다. 함수의 버스마크는 각 함수가 실행될 때 호출할 수 있는 API 호출의 집합으로 보고 있다. 이것을 정적으로 분석하기 위하여 먼저 바이너리 실행 파일을 디스어셈블러를 이용하여 함수를 구분하고 어셈블리 코드를 얻는다. 함수 버스마크를 구하기 위해 먼저 각 함수에 대해 어셈블리 코드로부터 가능한 API 호출의 집합을 구하고, 함수에 대한 호출 그래프를 구한다. 함수 버스마크는 해당되는 함수와 그 함수를 실행할 때 호출될 수 있는 다른 함수들을 호출 그래프를 통해 분석하고 호출 가능한 API에 대한 집합을 구한다. 프로그램 버스마크는 이 과정을 통해 구한 함수 버스마크의 집합이다. 버스마크를 비교하기 위하여 우리는 가중 이분 그래프에서의 매칭 알고리즘을 이용한다. 매칭 알고리즘을 통해 두 프로그램의 유사도를 계산할 수 있다. 또한 바이너리 코드 비교에 있어 정확성을 높이기 위하여 잘 알려진 라이브러리를 제외하고 비교하는 방법에 대해 제시한다.
바이너리 코드를 위한 동적 API 버스마크는 프로그램을 직접 실행할 때 호출되는 API의 시퀀스로 정의한다. 프로그램을 실행할 때의 API 시퀀스를 얻기 위하여 후킹 라이브러리를 사용한다. 버스마크를 비교하기 위하여 우리는 준전체정렬 알고리즘을 이용한다. 준전체 정렬 알고리즘을 통해 두 프로그램의 유사도를 계산할 수 있다.
제안하고 있는 버스마크를 평가하기 위하여 바이너리 소프트웨어 버스마킹 시스템을 구현하였다. 그리고 실제로 사용되고 있는 마이크로소프트 윈도 응용프로그램들을 카테고리 별로 선정하여 비교하였다. 버스마크의 수준에 대하여 신뢰성과 강인성을 기준으로 평가하여 바이너리 실행 파일에서의 유용성을 보였고 두 버스마크를 비교하였다. 정적 버스마크는 프로그램을 실행하지 않고 비교하기 때문에 프로그램 전체의 내용을 비교할 수 있다는 장점이 있다. 그러나 디스어셈블리가 잘못된 경우에 정확성이 떨어질 수 있고, 정적 분석의 일반적인 문제인 오탐지가 나타날 수 있다는 단점이 있다. 동적 버스마크는 프로그램을 직접 실행하기 때문에 정확한 결과를 얻을 수 있다. 그러나 프로그램 입력에 따라서 실행하는 부분이 달라지기 때문에 입력에 따라 버스마크가 편차를 보인다는 단점이 있다.
