Lightweight Equivalence Checking of Code Transformation for Code Pointer Integrity

Abstract

코드 변환 시의 동등성이 만족되지 않을 경우 소프트웨어 오류를 야기할 수 있다. 기존의 정리 증명을 통한 코드 변환의 동등성 검사는 코드의 규모가 커질수록 기하급수적으로 높은 비용이 요구되기 때문에 실제 소프트웨어 개발 시에 적용하기 어렵다. 본 논문에서는 규칙 증명과 코드 검사의 분리를 통하여 실용적인 LLVM의 코드 변환의 동등성 검사 기법을 제안한다. 먼저 주어진 코드 변환 규칙의 동등성은 자동정리증명을 통하여 컴파일 전에 별도로 증명한다. 그리고 컴파일 과정에서 변환 전과 후의 코드에 대한 정적 분석을 수행하여 코드 변환 규칙이 생성된 코드에 올바르게 적용되었는지 검사한다. 이러한 코드 분석의 수행 시간은 코드의 규모에 선형으로 증가하기 때문에, 규모가 큰 코드에도 효과적으로 적용될 수 있다. 제안된 연구를 코드 포인터 무결성(code pointer integrity) 보안강화 코드변환에 적용하여 LLVM 기반 도구제작에 활용하였다.

Code transformation is widely used to improve the performance and security of programs, but serious software errors can occur in this process if the generated program is not equivalent to the original program. There are a number of approaches for translation validation that can be used to prove the equivalence of programs, but the high cost of proof checking restricts the applicability of these techniques for large programs. In this paper, we propose a practical approach for checking the correctness of LLVM code transformation. We first prove the correctness of the transformation rules using automated theorem proving before compilation. We then perform a simple code analysis method—as opposed to directly proving the program equivalence— to check whether the transformations rules are correctly applied to the generated code. As the complexity of the proposed code analysis is linear, our technique can be effectively applied to large programs, unlike previous techniques. To prove the effectiveness of the proposed approach, we present a case study on LLVM code transformation for a code pointer integrity instrumentation.