[PL] Skeletal Program Enumeration for Rigorous Compiler Testing Qirun Zhang Chengnian Sun Zhendong Su (2016)

* 해당 글의 내용은 아래 논문을 요약한 것이며 자료들 또한 모두 아래 논문에서 가져온 것입니다.

Qirun Zhang, Chengnian Sun, and Zhendong Su. 2017. Skeletal program enumeration for rigorous compiler testing. SIGPLAN Not. 52, 6 (June 2017), 347–361. https://doi.org/10.1145/3140587.3062379

 

앞서 포스팅한 글에서 언급한 바와 같이, 컴파일러의 버그는 프로그램 생성에 있어 치명적이지만 알아차리지 못할 만한 오류를 생성시킬 수 있습니다. 이러한 버그를 최대한 줄이기 위하여 Program generation, Program mutation 등의 기법이 사용되고 있고, 현재 이 논문에서는 Skeletal Program Enumeration 을 통해 테스트 프로그램들을 생성하여 컴파일러를 검사하고자 합니다.

 

Skeletal Program Enumeration이란?

모든 프로그램 P는 V(변수 집합)의 원소들(=변수)이 들어갈 수 있는 구멍을 지닌 기본 Skeleton_P로 이루어져 있다고 이야기 할 수 있습니다. 아래 사진을 살펴보면 (a), (b), (c) 의 프로그램 모두 같은 skeleton을 지닌 프로그램이라고 할 수 있습니다. 

Figure 1

이와 같이 동일한 skeleton을 지닌 프로그램이라고 하더라도 변수를 어떻게 조합하여 배치할 것인가에 따라 수많은 테스트 프로그램들이 생성될 수 있습니다. 예로, k개의 변수를 n개의 자리에 (변수의 범위를 생각하지 않고) 배치한다고 하였을 때, 나올 수 있는 프로그램의 개수는 k^n개가 될 것입니다. 이와 같이 Skeletal Program Enumeration의 경우, 적은 코드 사이즈로도 충분히 컴파일러를 테스팅 할 수 있으며, 변수의 사용 패턴에 따라 컴파일러의 오류를 다양하게 발생시킬 수 있음과 동시에 다른 프로그래밍 언어에도 적용될 수 있다는 장점을 지니고 있습니다.

 

다만, 몇몇 변수 사용 패턴의 경우, α-equivalent 한 프로그램들이 생성되기도 합니다. 따라서 이러한 중복된 프로그램들을 걸러내어 non-α-equivalent한 프로그램들로만 이루어진 테스트 프로그램 집합을 만드는 것이 이 논문이 추구하고자 하는 방향성입니다.

 

 α-equivalent란?

 α-equivalent에 대해 알아보기 위해서는 먼저 skeleton이 어떻게 이루어져 있는지를 살펴보아야 합니다. 아래 사진을 먼저 참고해봅시다!

Figure 4 Figure 5

해당 사진에서는 WHILE language를 바탕으로 프로그램의 skeleton을 나타낸 것입니다. a는 상수를 담을 수 있는 변수공간, b는 bool 타입으로 평가될 수 있는 것을 담는 변수공간으로 이해하였습니다. 일단 해당 언어에서는 모든 변수가 global이라고 가정해봅시다. Figure 4의 (a)가 (b)로 변하는 과정을 Hole transformation이라고 부르며, 여기서 등장하는 □가 바로 변수를 집어넣을 수 있는 Holes에 해당됩니다. 아래 Figure 5에서도 마찬가지입니다. 따라서 Skeleton_P의 경우 변수들이 배치될 수 있는 수많은  □, holes 들이 생기게 되며 이러한 skeleton은 다음과 같은 벡터로 표현될 수 있습니다. >> (Skeleton_P = <  □_1,  □_2,  □_3 ...  □_n >)

 

이러한 holes 들에 변수를 채운 Figure 5의 (a), (c), (d) 와 같은 프로그램들도 다음과 같은 벡터로 표현될 수 있습니다.

 

Figure 5 (a) -> <a, b, a, a, a, b>

Figure 5 (c) -> <b, a, b, b, b, a> Figure 5 (d) -> <a, b, b, b, a, b> 

 

여기서 우리는 Figure 5의 (a)와 (c)가 같은 변수 패턴을 지니고 있음을 알 수 있습니다. 변수의 이름만 바뀐 것일뿐, 그 사용 패턴은 같기 때문에 이 두 프로그램, P와 P_1은  α-equivalent하다고 이야기 할 수 있습니다. (a를 b로, b를 a로 replace하면 같은 프로그램이 됩니다.) 따라서 이미 (a)가 생성이 되었다면, (c)를 테스트 프로그램으로 고려할 필요가 없다는 의미입니다. 두 프로그램이  α-equivalent 하기 위한필요 충분조건은 다음과 같습니다.

Definition 2

그리고 이러한  α-equivalence는 global 변수와 local 변수가 뒤섞인 skeleton에서도 적용됩니다. 

Figure 6

Figure 6의 경우 앞선 Figure 5와는 다르게 변수가 사용될 수 있는 범위가 이전보다 복잡해진 것을 알 수 있습니다. 만약 변수가 사용되는 모든 경우를 생각한다면 (= α-equivalence 를 고려하지 않는다면) 우리는 총 (2^5 * 4^5) 개의 테스트 프로그램과 마주할 수 있게 됩니다. 하지만 이들 사이에도  α-equivalent한 프로그램들이 존재하기 때문에 변수들의 scope information을 고려하여 Definition 2를 확장해야 합니다.

 

SPE Algorithim이제부터는 이러한 내용들을 바탕으로 SPE 알고리즘의 수도코드를 살펴볼 것입니다. 앞서 언급한 바와 같이 해당 논문에서는 효율적으로,  α-equivalent하지 않은 테스트 프로그램들을 생성하는 것을 주 목적으로 둡니다. 즉, 테스트 프로그램 집합 내에는 non- α-equivalent한 프로그램들만 남게 됩니다. 

 

non- α-equivalent 한 변수 사용 패턴을 생성하기 위해 저자들은 이 문제를 집합 분할 문제로 인지하였습니다. 즉, n개의 holes에 k개의 변수를 집어넣는 것은 n개로 이루어진 집합을 k개의 중복 없는 집합으로 나누는 문제와 같다는 의미입니다, 예로, Figure 5 에 등장한, 6개의 holes에 2개의 변수를 배치하였던 코드를 생각하여봅시다. 해당 문제의 경우 holes를 나타내는 H라는 집합은 {1,2,3,4,5,6} 총 6개의 원소로 이루어져 있습니다. 변수가 총 2개이기 때문에 6개의 원소를 2개의 집합으로 나누면 되는 것이고, 이에 따라 Figure 5 (c)를 나타내면 {{1,3,4,5}, {2,6}} 임을 알 수 있습니다. {1,3,4,5}는 a가 사용된 위치, {2,6}은 b가 사용된 위치입니다. 이런 식으로 순서를 매기지 않고 집합을 분할하는 것을 통해 α-equivalent 한 프로그램들을 걸러낼 수 있게 됩니다.

해당 논리를 바탕으로 하면 SPE Algorithm의 복잡도는 아래 사진과 같습니다.

SPE를 집합 분할 문제로 간주하고 풀게 되면 n개의 원소를 k개의 집합으로 나누었을 때의 해들이 모두 a unique set partition이 되어야 합니다. 이를 위해 각 변수들을 등장하는 순서대로 0부터 넘버링하여 프로그램의 변수 사용 패턴을 문자로 표현합니다. 이를 restricted growth string 이라고 합니다.

restricted growth string

예로 Figure 5 (a)의 변수 사용은 <a, b, a, a, a, b>로 나타낼 수 있고, 이를 restricted growth string으로 나타내게 되면 "010001"로 나타낼 수 있습니다. 이와 equivalent 한 프로그램 Figure 5 (c) <b, a, b, b, b, a> 또한 "010001"로 (a)와 같은 문자열을 갖게 됩니다.

 

앞서 다룬 대부분의 예시들에서는 등장하는 변수들을 모두 global 변수로 가정하였습니다. 하지만 실제 프로그램을 생성하는 과정에서 모든 변수가 global 변수인 경우는 드물겠지요! 그래서 Skeletal program enumeration 에서 해결해야 하는 가장 중요한 문제는 이 변수들의 범위를 어떻게 다룰 것인지 입니다. 그리고 각 변수들의 scope information을 고려하여 Skeleton_P를 채움과 동시에 non- α-equivalent한 프로그램들을 만드는 것은 제법 어렵고 연구되지 않은 분야중 하나입니다.

 

이를 위해 앞서 언급한 집합 분할 문제를 더 확장할 필요가 있습니다. n개의 holes를 가진 Skeleton_P, t개의 범위가 있다고 가정해봅시다. Skeleton_P에 속해있는 □_i, 즉 i번째 hole에는 global 혹은 local 변수가 들어갈 수 있습니다. □_(g,i)는 오직 global 변수들로만 채워질 수 있고, □_(l,i)은 l이라는 범위에 있는 local 변수들과 global 변수들이 모두 들어갈 수 있습니다. (즉, 코드의 내부로 들어갈 수록 들어갈 수 있는 변수의 개수가 더 많아지게 됩니다. 이는 local 범위 안에 선언되는 변수들이 많아지기 때문입니다.) 

 

윗 단락에 이어서, 각각의 l 범위에서 만들어지는 solution을 S_l이라고 해봅시다. 이때 final solution S는 S_g × S1 × ··· × St 로 표현할 수 있습니다. 하지만 이 경우, 단순히 S_l이 unique set partition이 되는 경우만을 고려하기는 어렵습니다. 예로, Skeleton_P가 다음과 같고 3번, 4번 holes는 scope l을 지닌다고 해봅시다.

 

<□_1, □_2, □_3, □_4, □_5>

 

그리고 이러한 skeleton을 바탕으로 한 두 프로그램 P1과 P2가 다음과 같은 variable usage pattern을 지닌다고 해봅시다. 

 

 

P1 <a, a, b, c, b> 

 

P2 <a, a, c, b, b> 

 

이 경우 P1과 P2는 3번과 4번 holes만 고려한다면 α-equivalent한 프로그램이 되어버립니다. 하지만 실제로 이 두 프로그램을 estricted growth string로 나타내게 된다면 이 두 프로그램은 non-α-equivalent한 것이 됩니다. ("00121", "00122") 따라서 global solution ( =unique set of test program) 을 얻기 위해서는 l에 위치하는 holes들의 일부를 미리 골라 globals 들로만 채워질 수 있게끔 설정하고 나머지 l에 있는 holes들을 local 변수들로만 채우게끔 해야 합니다.

 

다음은 unique한 solution set (for global)의 생성을 수행하는 알고리즘의 수도코드입니다.

각 코드에 대한 설명은 메모로 달아놓았으나 전체적인 알고리즘의 구조는 재귀의 형태를 띄고 있습니다. 각 scope으로 깊게 들어갈 수록 PartitionScope을 지속적으로 실행하여 sub_solution을 생성하게 됩니다. 이 과정에서 local holes 들 중 global 변수로 채울 holes의 개수를 1개부터 u개까지 미리 선택하여 모든 경우의 solution 들을 생성하게 됩니다. 또한, Partitions는 앞서 언급한 규칙들에 따라 n개의 원소들을 k개의 집합으로 나누는 기능을 수행하게 됩니다.

 

이러한 알고리즘을 바탕으로 GCC와 Clang을 테스트한 결과 많은 버그가 발견되었습니다. 다만, miscompilation의 경우 사람이 직접 출력 결과와 직접 계산한 결과값을 비교해야 하기에 해당 논문에서는 crash에 대해서만 버그 검토를 진행했다고 합니다. (정상 작동하는 프로그램의 결과값과 EMI variant의 결과값을 비교하는 program mutation이 지닌 장점이 여기서 드러나는 것 같다는 생각...이 듭니다.) 다음은 해당 알고리즘이 밝혀낸 버그의 일부입니다. 

 

Figure 11

Figure 12

느낀점

저번 논문에서는 EMI 를 활용한 Program mutation에 대해 알아봤는데, 이번 논문을 읽고 나니 더더욱 컴파일러 테스팅에는 한가지 기법만이 사용되는 것이 아니라는 생각이 들었다. 두가지 방법이 서로 수행할 수 없는 부분을 상호보충해주는... 그런 느낌... 컴파일러 버그를 검사하기 위해서 무엇을 해야하는지 처음에는 감이 잡히지 않았는데 현재 어떤 방법들이 사용되고 있는지를 통해 대략적인 연구 흐름을 파악할 수 있었던 것 같다. 개인적으로는 code snippet을 삽입하는 program mutation보다 SPE가 조금 더.. .수월하지 않겠나.. (물론 둘 다 어렵긴 하다 ^^...) 저번에 슬쩍 Csmith과 같은 프로그램이 python에도 있나 살펴본적이 있는데... 그 프로그램을 바탕으로 mutation/generation/enumeration 을 수행하면 되는게 아닌가 싶다... ㅎ 근데 알고리즘 만들 수 잇슬까? ㅎ