19-x-xxx

시스템 종속 그래프에 기반한

프로그램 자르개의 구현

(An implementation of Program Slicer

based on System Dependence Graph)

노상훈 ․ 신승철

동양대학교 컴퓨터학부

noulne@paran.com   shin@dyu.ac.kr

요  약

프로그램 자르기(Program Slicing)는 프로그램의 이해와 디버깅 등을 돕는 매우 유용한 도구로 알려져 있고 프로그램 분석에도 이를 도입하여 효과를 배가하는 시스템이 연구되어 왔다. 우리는 시스템 종속 그래프를 이용하는 프로그램 자르개를 구현하였는데 본 논문에서는 그래프의 적절한 표현방법과 잘라낸 정보(slice info)를 취급할 때 발생한 문제를 해결하는 방법을 설명한다. 또한 구현된 자르개가 소프트웨어 보안 문제의 하나인 정보흐름 보안성 검증에서 어떻게 응용될 수 있는지를 설명한다.

1. 서  론

System Dependence Graph 기반의 Program Slicer의 구현

프로그래밍언어논문지 제19권 제2호 (2005. 11)

프로그램 자르기(Program Slicing)는 M. Weiser에 의해 최초로 소개된 개념[1]이다. Susan Horwitz가 발표한 논문[2]에는 시스템 종속 그래프(SDG: System Dependence Graph)를 이용하여 구현하는 방법이 조금 더 상세하게 수록되어 있다. 프로그램 자르기는 소프트웨어 공학 측면에서 요구되는 프로그램 이해, 디버깅 등에 매우 유용하며 프로그램 분석 시스템에도 도입되고 있다.

우리는 [2]를 바탕으로 하여 C언어를 대상으로 하는 프로그램 자르개(Program Slicer)를 구현하였다. 본 논문은 프로그램 자르개를 구현하는 과정에서 나타나는 난제에 대한 해결 방법이나 보완 방법을 제시한다.  또한 구현된 프로그램 자르개를 프로그램 보안 문제에 어떻게 적용할 수 있는지 간단한 응용의 예를 통하여 보인다.

2. 프로그램 자르기

2.1. 프로그램 자르기

프로그램 자르기란 프로그램 상의 특정 기준점(criteria)과 관련된 문맥만을 추출하는 작업을 의미한다.

Criteria에 영향을 주는 문장만을 추출하는 것을 Backward slicing 이라고 하면, Criteria로부터 영향을 받는 문장만을 추출하는 것을 Forward slicing이라고 한다.

그림1)에서 진하게(bold) 표기된 것은, 마지막의 printf에 있는 출력변수 i 에서 후방향 자르기(Backward Slicing)를 한 것이다. 마지막 사용의 i 에 영향을 주는 문장들만이

그림1) Backward Slicing의 예

void main() {

int i = 1;

int sum = 0;

while (i<11) {

sum = sum + i;

i = i + 1;

}

printf("sum = %d\n", sum);

printf("i = %d\n", i);

}

추출되어 있다.

프로그램 자르기의 구현 방법은 여러 가지가 있을 수 있지만, 가장 효과적인 방법으로 널리 사용되는 것은 바로 뒷 절에서 SDG를 이용하는 방법이다. 이 방식의 핵심은 제어종속(Control Dependent)과 자료종속(Data Dependent)을 좇아서 관련된 문맥을 추출하는 것이다.

그림) System Dependence Graph

2.2. 시스템 종속 그래프

SDG는 프로시저내 프로그램(Intraprocedural Program)을 표현하고 있는 프로그램 종속 그래프(PDG: Program Dependence Graph)를 프로시저간 프로그램(Interprocedural Program)을 표현할 수 있도록 확장시킨 그래프이다.

SDG는 그림2)와 같이 도식으로 표현될 수 있다. 여기서 PDG는 각 문장 간의 제어 종속과 자료 종속을 포함하며, SDG 상에서 하나의 함수-혹은 프로시저를 표현한다.

비교적 근래에 발표된 Kumar의 Better slicing of programs with jumps and switches[3]에서는 Node M에서 N으로의 제어종속이 있음에 대해 다음과 같이 정의하고 있다.

“N이 M의 CFG 후행자(successors)를 후지배(postdominates)하되, 전부를 후지배하지는 않는다.”

다수의 함수로 이루어진 프로시저간 프로그램(Interprocedural Program)을 표현하기 위해서 추가적으로 표현되어야 할 것은 매개변수(parameter)와 함수 호출(function call)이다. [2]에서는 값-결과전달 호출(call-by-value-result)을 표현하기 위해 형식 입력 매개변수(formal in- parameter)와 형식 출력 매개변수(formal out- parameter)의 노드(node)를 추가하는 방법을 사용하였다.

다른 방식의 인수 전달을 사용하더라도 이 표기법을 사용하여 다룰 수 있다.

2.3. 심볼 속성간의 추이적 종속성

프로시저간 프로그램 자르기에서는 실제 자르기에 들어가기에 앞서 호출부(call-site)의 실매개변수(actual parameter)간의 추이적 종속성(transitive　dependence)을 먼저 계산하고 있다.  함수 호출이 추가됨으로 인해서 프로시저간 프로그램 자르기가 프로시저내 프로그램 자르기와 차이를 보이는 점 중의 하나이며, 비교적 복잡한 계산을 요하고 있다.

Thomas Reps의 Speeding up Slicing[4]에서는 이 계산을 단축시킬 수 있는 향상된 방법을 제시하고 있다.

3. 프로시져간 프로그램 자르기의 단계

프로시저간 프로그램 자르기의 단계는 크게 다음과 같다.

1. 입력된 AST로부터 SDG 구축

2. TDS(Transitive Dependences among a Symbol's attributes) 계산

3. SDG에 TDS정보 적용

4. 3의 SDG 정보를 이용해 프로시저간 프로그램 자르기

5. 4에서 추출된 노드정보를 기반으로 SDG 자르기

우리는 단계 1에서 구축하는 SDG는 syntax directed 방식[5]을 기반으로 구현하였는데 이것은 ocaml로 된 모듈로서 단계 2~5의 구현에 사용된다. 본 논문은 단계 2~5에 초점을 둔다.

4. 구현

4.1. Graph의 자료구조

시스템 종속 그래프를 이용하여 프로그램 자르기를 구현할 때 중요하게 고려해야 하는 사항은 어떻게 그래프를 다루는가이다.

OCaml에서는 추상구문트리(AST:Abtract Syntax Tree)를 다룰 때, 일반적으로 타입(type)의 안전성과 해석의 편의성 같은 측면을 위해 variant 타입을 이용해 부모 값(value)에 자식 값이 완벽하게 유착되는 방식으로 구현을 한다.

하지만, 프로그램 자르기처럼 노드간의 임의적인 이음선(edge) 연결과 제거 등의 그래프 조작을 하기에는 적합하지 않다. 부모와 자식의 관계를 약화시켜 그 연결을 손쉽게 조작할 수 있도록 하기 위해, 노드와 이음선을 분리시키는 구현을 사용하는 것이 좋다.

본 구현의 바탕이 되는 현재 구현되어 있는 SDG는 [5]에서 제시한 명령형 언어 바탕의 구현을 사용하였다. 이 구현에서는 제어흐름(Control Flow), 제어종속과 같은 다른 종류의  이음선을 근원노드(source node)에 후행자로써, 함께 기록하여 사용하고 있다.

위와 같이 구현할 경우 각 노드에서 동시에 여러 종류의 이음선을 다룰 때는 효율적이지만, 동일 노드하에서 새로운 종류의 이음선을 가지는 그래프를 구현하려고 하는 경우 문제가 된다. 또한 노드를 공유하며, 이음선의 연결만 달리하는 그래프를 여러 개 만들게 되는 경우 매우 비효율적이게 된다.

실제로 구현 시 TDS와 TDP 그리고 원본은 보존하며 별개로 잘라진 사본 그래프등 많은 그래프를 필요로 하게 된다.

때문에 본 논문에서 추가적으로 구축되는 그래프는 SDG의 노드만을 재활용하고 이음선은 독자적인 방법으로 다루게 하였다.

그래프의 구현에서 고려해야할 사항이 한 가지 더 있다.

SDG는 여러 프로시저로 이루어진 시스템을 하나의 거대한 그래프로 표현하고 있다. 하지만, 프로시저 내부의 개별적 계산에 SDG 전체 노드의 정보를 참여시키는 것은 연산의 비효율성을 낳는다.

구현된 SDG에서는 이 문제를 해결하기 위해 SDG를 PDG의 list로 된 자료구조 다루고 있다. 대부분의 연산은 PDG 내부에서 이루어지고, 프로시저간 이음선에 대한 연산은 개별적으로 처리하기 때문이다.

가장 직관적인 구현은 PDG가 독자적인 노드를 소유하여 관리하고,  이음선은 각 PDG 내부에서 부여되는 노드의 ID를 가지고 표현하는 것이다. 이런 구현은, 프로시저간 이음선에 사용할 노드를 표현하려면, PDG의 ID와 노드의 ID가 필요하다. 이 경우 이음선을 다루는 경우는 문제가 되지 않지만, 노드의 정보를 빈번하게 열람해야 하는 경우 단점으로 작용한다. 현재 TDS/TDP 와 같은 그래프에서는 이런 방법을 통해 구현되어 있다.

하지만 조금 더 생각해 보면 이 문제는 보완의 여지가 있다. 현재 그래프의 구현에서 문제시 되고 있는 점을 요약하면 다음과 같다.

■ SDG를 하나의 큰 그래프로 구현하면 연산이 비효율적이게 된다.

■ SDG를 PDG의 집합으로 표현하게 되면, 서로 다른 PDG에 속한 노드간의 이음선을 다루기가 번거롭다.

위의 두 가지 방법을 섞은 아래의 방법을 사용하면 더 나은 방법으로 처리할 수 있다.

■ 노드와 이음선은 별개로 취급한다.

■ 노드는 큰 그래프의 부속품으로 취급한다.

■ 부분그래프는 해당 그래프에 속하는 노드의 목록과, 이음선을 보유한다.

SDG 전체에서 사용되는 프로시저간 이음선은 SDG에 속하게 하고, 각 프로시저내 이음선은 PDG에 속하게 하는 구성을 생각할 수 있다. PDG는 제어흐름과 제어종속 데이터종속등 여러 개의 이음선 자료구조를 가지고 있다고 볼 수 있을 것이다.

노드와 이음선을 분리하게 되면, 노드를 상수로써 다룰 수 있게 되기 때문에, 이런 방식의 구현은 간단하게 할 수 있다.

이음선의 자료구조는 인접 리스트(adjacent list)로 할 수 있다. 본 구현에서는 Map이라는 OCaml에서 지원해주는 모듈을 사용하였다. Map은 key⟶data의 사상(mapping)을 균형트리(balanced tree)를 통해 다루어 주는 모듈이 제공되고 있다. 균형트리이기 때문에 검색과 추가/삭제도 효율적이고 순회 역시 선형시간으로 가능하기 때문에 프로그램 자르기의 구현에 효율적으로 사용할 수 있다.

NodeMap을 key로 Node 타입을 받을 수 있는 Map 모듈이라고 한다면, 이음선은 다음과 같이 구현 할 수 있다.

type 'a edge = 'a NodeMap.t NodeMap.t

즉, 'a type의 data를 갖는 sink node의 목록을 갖는 근원노드의 목록이라고 요약할 수 있다.

'a type의 data는 이음선에 붙는 보조정보를 위해 사용할 수 있다. 예를 들면 제어흐름, 제어종속과 같은 이음선은 true, false의 꼬리표(label) 정보가 필요한데, 이는 bool edge 타입의 자료구조로 표현할 수 있다.

4.2. TDS의 구현

TDS는 TDP(Transitive Dependences in a Production)를 이용하여 구할 수 있다. TDS(X)와 TDP(X)는 각각 한 함수 X에 대한 매개변수 노드들로만 이루어진 작은 그래프이다.

TDS(X)는 X의 형식 매개변수간의 추이적 종속을 표현하는 그래프이고, TDP(X)는 X와 X에 의해 호출되는 Y의 매개변수간의 추이적 종속관계를 표현하는 그래프이다.

TDS는 TDP를 이용하여 구현되기 때문에 TDP가 우선적으로 계산되어야 한다. TDP는 SDG로부터 계산되어지는데, 이 구현에서 TDP를 계산하기 위해 marking map과 worklist 알고리즘을 사용하였다.

착안점은 매개변수 A로부터 시작하여, 도달가능한 모든 곳 중에서 매개변수 B가 있다면, A에서 B로의 종속이 있다고 볼 수 있는 것이다.

그래서 근원노드가 될 수 있는 형식입력매개변수와 실출력매개변수(actual out-parameter)를 시작 노드로 하여 worklist는 각 시작 노드의 후행자로 초기화한다. 또한 매 노드에 대해서 marking map역시 초기화 한다. 각 노드의 방문(visit)에서 표시(mark)되어 있는지를 검사해 표시되어 있다면, 해당 노드의 방문을 중단하고, worklist의 다음 노드를 방문 한다.

만약 표시되어 있지 않다면 marking map에 이미 방문했다는 표시를 하고, 그 노드의 후행자를 다시 worklist에 넣는다. 만약 방문중인 노드가 매개변수라면 시작 노드로부터 현재 노드로 향하는 제어종속을 추가하고 계속한다.

제어종속의 추가시에는 매번 관련 노드의 추가를 시도한다. 추가할 노드가 이미 해당 TDP에 존재하면 추가 하지 않는다. 이렇게 되면, 최소한의 노드로만 구성된 TDP가 생성되게 된다.

TDP가 계산되고 나면, TDS는 [2]에 구현되어 있는 ConstructSubCGraphs를 사용하면 TDS를 계산할 수 있다. 계산된 TDS는 SDG에 적용되어져야 한다. 모든 호출부에 해당 함수에 대한 TDS로부터 실매개변수간의 종속관계를 복사한다.

4.3. Slicer의 구현

TDS 정보가 적용된 SDG에 [2]에   구현된 MarkVerticesOfSlices 와 MarkReachingVertices를 사용하면 후방향 자르기 된 노드 목록을 얻을 수 있다.

여기서 짚고 넘어갈 점은 이 계산을 통해 얻어진 노드는 애초의 “실행 가능한” 잘린 정도가 아니라는 점이다. 이 정보를 토대로 정말로 컴파일 가능한 코드를 만들어 내기 위해서는 약간의 정보 복원이 필요하다.

후방향 자르기 된 정보를 고려하자면, 기준점 이후에 나오는 모든 노드가 제외되게 된다. 반대로 전방향 자르기된 정보는 기준점 이전에 나오는 모든 노드가 제외되게 되는 것이다. 이는 심각한 문제를 초래하게 되는데, 전자의 경우는 return문이 소실될 수 있으며, 후자의 경우 형식매개변수는 물론 함수 호출의 실매개변수는 잘린정보에 포함된 체 함수호출 자체는 사라져 버리는 이상한 모양까지 나타나게 된다.

때문에 본 구현에서는 잘린정보를 기반으로 SDG를 잘라내기 전에 잘린정보를 복원하는 작업을 추가하였다. 가장 우선적으로는 시작노드와 종료노드는 무조건 포함시킨다. 그리고 s잘린정보에 포함된 매개변수노드의 선행자 역시 잘린정보에 복원한다.

이제 남은 것은 후방향 자르기에서 return 노드에 대한 처리이다. 현재의 구현은 PDG 내에서 가장 끝에 있는 return 노드를 복원 시키는 방식을 사용하고 있지만, 이 방법은 문제의 여지를 포함하고 있다. return 문으로 자료 흐름(Data Flow)가 있는 노드가 잘린정보에 포함되어 있지 않을 수 있다. 때문에 모조값(dummy value)를 return하는 새로운 코드를 추가해야하는 이 문제는 그래프 수준에서 다룰 문제는 아니다. 잘라진 SDG를 바탕으로 AST를 다시 자를 때, 새로운 코드를 끼워 넣는 방식을 사용하여야 한다.

코드화의 경우 문제가 되는 또 하나의 경우는 일부의 매개변수가 제거 되는 경우이다. 모든 호출부에서 제거되는 매개변수가 동일한 경우는 형식매개변수에서 제거하면 되기 때문에 문제가 되지 않지만, 그렇지 않은 경우 형식매개변수를 어느 한쪽으로 맞출 수 없기 때문에 불합리 하게 된다. 이 구현에서는 형식매개변수는 그대로 유지하고 대신 AST를 잘라낼 때 모든 호출부에서 그래프에 포함되지 않은 매개변수를 ‘__UNUSED0__’와 같은 모조변수(dummy variable)로 수정하였다. 이에 맞춰, 함수의 가장 앞부분에 사용되는 모조변수에 대한 선언을 추가한다. 모조변수는 타입별로 하나씩만 선언하면 되므로 타입종류⟶변수이름의 map을 이용하여 구현하면 된다.

위와 같이 적절한 노드의 복원이 이루어지 난 뒤에, SDG 자르기를 하는데, 이 때 처리해 주어야 하는 점은 이음선의 처리 문제이다. 이는 해당 노드의 모든 선행자를 모든 후행자에게로 연결하고 해당 노드로 이어지는 모든 선행자와 후행자를 제거함으로써 처리할 수 있다.

5. Slicer의 응용

자르개는 소프트웨어 검증에 사용될 수 있다. 그래서 간단한 예로, 특정 함수에 영향을 주는 모든 함수를 추출해 내는 Flower라는  프로그램을 구현해 보았다.

그림) Flower의 예제 프로그램

void main()

{

int i;

int secret, normal;

secret = getint();

normal = getint();

for(i=0; i<secret; i++)

{ normal++; }

secret = 0;

printf("%d", secret);	printf("%d", normal);

}

그림4) Functional Information Flow

Flower에서는 임의의 함수 호출을 선택하면 이 함수 호출에 영향을 주는 모든 함수를 함수정보흐름(Functional Information Flow)을 통해 보여준다. 그림3)의 마지막 printf에 영향을 주는 모든 함수를 추출하여 그래프로 보여주는 것이 그림4) 이다.

normal 변수의 초기값은 normal =getint()의 영향을 받으며, 또한 for문에서 condition으로 사용되는 secret변수에 normal변수가 제어종속이 있기 때문에 결과적으로 두 개의 getint() 함수는 모두 마지막의 printf에 영향을 주고 있다.

만약 기준점을 네트워크 송신 함수로 설정하고 암호 입력 함수가 함수정보흐름 상에 나타날 경우 그 사이에 암호화 함수가 존재하는지를 검사하여 프로그램의 정보흐름보안성을 검증할 수 있다.

참 고 문 헌

[1] M. Weiser. Program Slicing. IEEE Transactions on Software Engineering, vol. 10, no. 4, July 1984, pp. 352-357.

[2] Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems 12, 1 (January 1990), 26-60

[3] Kumar, S. and Horwitz, S., Better slicing of programs with jumps and switches. In Proc. of FASE 2002: Fundamental Approaches to Softw. Eng., (Grenoble, France, April 8-12, 2002).

[4] Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., Speeding up slicing. In SIGSOFT '94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19, 5 (December 1994), pp. 11-20

[5] M. J. Harrold and G. Rothermel. Syntax-directed construction of program dependence graphs. Technical Report OSU-CISRC-5/96-TR32, The Ohio State University, May 1996.

노 상 훈

2001년~2005년 동양대학교 컴퓨터공학부(학사)

관심분야 : 프로그래밍 언어, 프로그램 분석 및 검증.

신 승 철

1992 - 1996년 인하대 전자계산학과 (박사)

1999년 - 2000년 캔사스 주립대 연구원

1996년 - 현재 동양대 컴퓨터학부 부교수

관심분야 : 프로그래밍 언어, 소프트웨어 보안, 프로그램 분석 및 검증, 수리논리