Pointer analysis is an important part for the source code analysis of C programs. Most of pointer analysis algorithms are developed as top-down analyses, where the analyses are performed from callers to callees. Since such a scheme disables the analysis to operate on incomplete programs, existing top-down pointer analyses are not readily applicable to the modular software development process where individual software components are separately developed and subsequently linked with other components. Bottom-up pointer analyses can address this problem by performing analyses from callees to callers. However, analyzing the behavior of a procedure without utilizing any information on callers makes the different pointer behaviors of a procedure for different calls difficult to be traced precisely.
In this thesis, we propose a bottom-up and flow- and context-sensitive pointer analysis algorithm based on a new bottom-up pointer analysis domain named the update history. The update history can not only abstract memory states of a procedure independently of the information on aliases between memory locations, and but also keep information on the order of side effects performed. Such characteristics of the update history not only enable pointer analyses to be formulated as bottom-up analyses, but also help bottom-up pointer analyzers to effectively identify killed side effects and relevant alias contexts, both of which are the main contributions of this thesis. Our bottom-up and flow- and context-sensitive pointer analysis is formulated as an inference algorithm of a type system for the update history. Then we formally prove the soundness of our pointer analysis algorithm, which has not been satisfactorily investigated for this kind of problem previously, using the well-developed type soundness machinery from the type system framework.
The experiments performed on a pilot implementation show that our approach is cost-effective in a sense that the precision was improved without sacrificing the performance significantly. A client analysis that detected either uninitialized value or null pointer dereference errors using our pointer analysis was able to identify a maximum of 37% more pointer dereferences as safe than the client analyses using other bottom-up approaches experimented.
C나 Java 프로그램과 같이 포인터에 관련된 수행이 있는 프로그램을 효과적으로 분석하기 위해서는 포인터 분석이 중요하다. 대부분의 포인터 분석 방법들은 호출자로부터 피호출자의 순서로 분석을 수행하는 하향방식 분석으로 제안되었다. 하지만 이러한 방식의 분석들은 전체 프로그램이 주어졌을 때에만 작동 할 수 있기 때문에, 각각의 소프트웨어 컴포넌트들이 따로 작성되어 차후 순차적으로 합쳐지는 방식으로 개발되는 모듈단위 개발 과정에서 활용될 수 없는 단점이 있다. 상향방식의 포인터 분석들은 프로그램을 피호출자로부터 호출자의 순서로 분석함으로써 이러한 문제점을 해결할 수 있다. 하지만, 일반적으로 호출자에 대한 정보 없이 피호출자를 분석해야 하는 상향방식의 포인터 분석들은 호출 문맥의 차이에 따른 피호출자의 실행의 차이를 정확히 추적하기 어려운 문제가 있다.
본 논문에서는 업데이트 기록이라 이름 지어진 새로운 상향방식의 포인터 분석 공간을 기반으로, 프로그램 흐름과 호출 문맥에 민감한 상향방식의 포인터 분석 알고리즘을 제안한다. 업데이트 기록은 함수의 호출 문맥에 독립적으로 메모리 상태를 요약할 수 있을 뿐만 아니라, 메모리 반응이 일어난 순서에 관한 정보를 유지할 수 있다. 업데이트 기록의 이러한 특성은 상향방식의 포인터 분석을 고안할 수 있게 해줄 뿐만 아니라, 분석의 정확도를 높이기 위해 효과적으로 활용될 수 있는 정보인 죽은 메모리 반응 또는 관련된 별칭 문맥을 알아내는 데에도 효과적으로 사용될 수 있다. 본 논문에서는 업데이트 기록을 이용하여 프로그램의 포인터 관련 수행을 요약해주는 타입시스템을 정형화 하고, 이에 대한 추론 알고리즘으로서 상향방식의 포인터 분석을 정형화 하였다. 그리고, 타입시스템 이론의 잘 정리된 증명 방법들을 이용하여, 기존의 연구에서는 충분히 다루지 못했던, 제안된 상향방식의 포인터 분석의 안전성에 대한 정형화된 증명을 제시하였다.
실험은 C 프로그램에 대한 포인터 분석을 제안된 방법과 기존의 대표적인 상향방식의 포인터 분석들을 OCaml언어로 구현하여 비교하였다. 실험 결과 제안된 방법이 기존의 방법들에 비해 성능을 많이 희생하지 않으면서도 정확도를 높일 수 있음을 확인하였다. 또한, 제안된 상향방식의 포인터 분석 결과를 사용하여 초기화 되지 않은 포인터나 빈 포인터 참조 에러들을 추적해본 결과, 기존의 방법들을 사용한 실험에 비하여, 최대 37% 더 많은 포인터 참조가 안전함을 보일 수 있었다.
