Program analyzers with only bottom-up phases do not make use of the upper level modules to analyze procedures. They generate a summary for each procedure and make use of the summaries to handle actual procedure calls in other modules. Thus bottom-up analyzers can handle a module without the source codes of the called procedures, provided that their summaries are given.
Such program analyzers have several merits. Even if a module is modified, the module and only its upper level modules are needed to be analyzed again. In other words, we do not need to analyze its lower level modules again. We can also analyze a program which uses libraries whose source codes are not available, if we have the summaries of the library functions.
In this paper, we present a summary-generating bottom-up pointer analysis algorithm. For each function in the given program, our algorithm generates a summary which abstracts the side effects of the function without using any information on calling contexts of the function. Due to lack of information on the calling contexts, the algorithm has to introduce assumptions on the alias relations among the memory locations, which will be passed as formal parameters, to get more precise summaries. Summaries are represented using sequences of memory updates, which enables the algorithm to infer only useful assumptions.
We suggest several extensions to implement the algorithm for C language. Then we present the experiment results and discuss the characteristics of the benchmark programs and the effectiveness of the implementation.
이 논문에서 모듈이란 상호 재귀적인 함수들의 집합을 의미하며 모듈단위 분석이란 한 모듈을 분석 시에 다른 모듈의 소스코드가 필요하지 않는 프로그램 분석을 의미한다. 우리가 제안하는 모듈단위 포인터분석 알고리즘은 주어진 프로그램의 최하위 모듈부터 분석을 시작하여 점차 상위 모듈을 분석해 나간다. 이때 각 프로시저에 대한 요약본을 생성하며 분석 도중 프로시저 호출을 만나면 해당 프로시저의 소스코드 대신 이미 생성된 요약본을 이용한다. 또한 어떤 모듈을 분석 시에 모듈단위 분석을 위해 다른 모듈의 소스코드를 사용하지 않는다. 따라서 각 프로시저가 어떻게 호출되는지 알지 못하는 상태에서 분석이 진행된다. 하지만 우리의 알고리즘은 메모리 공간들이 같은 공간을 나타낼 수 있는 지에 여부에 대해 가정을 도입함으로써 더 정확한 요약본을 계산할 수 있다. 우리가 제안하는 포인터분석은 다음과 같은 장점들이 있다. 프로그램 시작점이 존재하지 않는 라이브러리나 혹은 상향식으로 개발되고 있는 프로그램의 분석이 가능하다. 그리고 어떤 모듈이 수정되더라도 그 모듈과 그것의 상위 모듈만 재분석될 필요가 있다. 즉 그것의 하위 모듈은 다시 분석할 필요가 없다. 또한 소스코드가 주어지지 않은 라이브러리를 사용하는 프로그램에 대해서도 라이브러리의 요약본이 주어진다면 분석할 수 있다.
