[PL] Finding Compiler Bugs via Live Code Mutation Sun, Chengnian & Le, Vu & Su, Zhendong. (2016)

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

Sun, Chengnian & Le, Vu & Su, Zhendong. (2016). Finding compiler bugs via live code mutation. 849-863. 10.1145/2983990.2984038. 

 

해당 논문은 C 코드를 GCC, LLVM과 같은 컴파일러를 통해 어셈블리 코드로 컴파일하는 과정에서 일어나는 버그와 이를 수정하기 위해 Live Code Mutation 기법을 적용하는 과정 및 결과를 주 내용으로 하고 있습니다. 

 

GCC, LLVM과 같은 컴파일러들도 결국 사람이 만든 것이기에 결코 완벽하다고 할 수 없습니다. 이 과정에서 컴파일 버그가 종종 나타나곤 하는데, 일반적으로 컴파일 버그는 crashes와 miscompilations로 분류됩니다. crashes의 경우 컴파일 과정에서 에러를 내며 컴파일 자체가 중단되지만 miscompilations는 컴파일 이후 실행까지 되기 때문에 에러를 잡아내기 더 어렵습니다. (주로 사용자가 기대하는 값과 다른 값을 출력하는 코드로 컴파일이 됩니다.) 

 

현재로서는 컴파일러 버그를 잡아내기 위해 formal verification, translation validation, 그리고 random testing 등의 기술들이 사용되고 있습니다. 해당 논문에서는 random testing(Csmith: random C Code generator)과 EMI을 통해 GCC와 LLVM의 컴파일 버그를 추적하였습니다.

 

Equivalence Modulo Inputs (EMI)란?

L이라는 프로그래밍 언어로 만들어진 프로그램 P와 Q, 그리고 inputs들로 이루어진 I 집합이 있다고 가정해봅시다. I 집합에 존재하는 모든 i들에 대해 P와 Q가 각각 같은 값을 출력하면 이 두 프로그램을 Equivalent modulo inputs이라고 할 수 있습니다. 이때 Q는 P의 EMI variants라고 이름 붙일 수 있습니다.

P and Q are equivalent modulo inputs iff

 

다시 본론으로 돌아와서...

현재 Orion과 Athena와 같은 컴파일러 버그 추적 툴들은 이 EMI를 활용하여 컴파일 버그를 추적합니다. Orion과 Athena는 유효한 프로그램 pg를 받고 pg의 EMI variants 인 pg'를 생성하는데, 이렇게 만들어진 pg'와 pg의 출력을 비교하여 두 출력값이 다른 경우들은 컴파일 버그 카테고리에 일차적으로 속할 수 있게 됩니다. (출력값이 달라도 해당 버그가 duplicates bug이거나 드물게 EMI variants 생성에서 생긴 문제에 의한 것이라면 우리가 찾고자 하는 컴파일 버그라고 할 수 없기 때문입니다.)

 

Orion과 Athena는 Dead-Code EMI mutation을 활용하여  EMI variants를 생성합니다. Dead-Code EMI mutation이란 프로그램이 수행될 때 실질적으로는 실행되지 않는 부분(=Dead Code)에 에러를 발생시키는 코드나 추가하거나, 기존 코드를 삭제하여 에러를 발생시키는 등의 작업을 수행하여 코드를 변형시키는 것을 의미합니다. 에러가 나는 코드일지라도 Dead Code 내부에 구현이 되어있어 실행되지 않기 때문에 프로그램은 정상적으로 종료되어야 하지만, 그렇지 않은 경우가 종종 발생하며 이를 컴파일 버그라고 볼 수 있습니다.

 

다만, 이러한 방식은 코드 변형이 Dead Code에만 한정되어 있다는 점, 컴파일러가 해당 부분을 Dead Code로 인지하고 삭제할 수 있다는 점에서 한계점을 지닙니다. 또한 결국 실행되지 않는 부분에서 발생하는 버그이기 때문에 실질적으로는 버그의 발생을 인지하기가 어렵습니다. 

 

따라서 이를 보완하기 위해 Live-Code EMI Mutation을 도입하게 됩니다.

 

Live-Code EMI Mutation을 도입하기 위해서 Profiling stage, Mutation stage를 거치게 됩니다. Profiling stage에서는 program point L에서 변수들의 값을 수집하며, Mutation stage에서는 해당 변수들의 값을 바탕으로 프로그램의 출력값과 상태를 변화시키지 않는 code snippet을 program point L 이전에 삽입하게 됩니다. 

 

다음은 이러한 기술을 활용하여 찾아낸 버그들의 예시입니다.

회색 부분이 code snippet

첫번째 코드의 경우 정상적으로 종료되어야 하나 segmentation fault를 출력하고, 두번째 코드도 마찬가지로 정상적으로 종료하는 대신 abort 됩니다. 두 코드 모두 live code의 영역에서 code snippet이 삽입됐기 때문에 Orion과 Athena와 같은 툴에서는 이러한 버그를 추출해낼 수 없습니다.

이제 EMI variants을 생성하는 알고리즘의 수도코드를 살펴봅시다. 

Algorithm 1: Hermes's process for testing compilers (Hermes는 저자들이 개발한 Live Code Mutation tool 입니다.)

P를 Seed Program, P'를 P의 EMI variants, O는 P를 컴파일 후 실행한 결과, O'는 P'를 컴파일 한 후 실행한 결과입니다. procedure Test에서는 EMI variant를 생성하고 각각의 값들을 비교하는 과정을 코드로 구현하였습니다. function EMI에서는 P'를 생성하여 return, function Mutate에서는 P'를 생성하기 위한 mutate 과정을 수행하고 있습니다. Mutate의 경우 env 변수를 생성하는데, 이는 mutate 이후에도 프로그램의 상태를 변화시키지 않기 위함입니다. profile 과 env의 semantics rule은 다음과 같습니다.

Loc은 Program points를, P(Z)는 values를 의미합니다.

즉, profile을 통해 Program points 별로 변수가 가지게 되는 값들을 알 수 있게 됩니다.

Algorithm1-Line 17을 살펴보면 SynCode(env) 구문이 존재합니다. SynCode()는 EMI snippet을 만들어내기 위한 함수로 일정한 확률로 세가지 종류의 snippet 중 하나를 선택하여 코드를 생성하는데, 그 세가지 종류는 아래와 같습니다.

 

1. Always False Conditional Block (FCB)

위의 예시처럼 항상 조건문의 조건이 False가 되어 실행되지 않는 code snippet을 Always False Conditional Block (FCB) 라고 합니다. 실행되지 않는 구문이기에 내부에 존재하는 코드들의 validity를 살펴볼 필요는 없습니다. 

2. Always True Guard (TG)

s를 Seed Program의 코드 일부라고 하고, p를 true라고 가정할 때 if (p) s 와 같이 항상 True가 되어 s를 실행시키는, 즉 Seed Program 을 변화시키지 않는 code snippet을 Always True Guard (TG)라고 합니다.

 

3. Always True Conditional Block (TCB)

세 종류의 code snippet 중 가장 복잡한 (?) 과정을 거쳐 생성되는 코드입니다. FCB와는 달리 항상 실행이 되는 구문이기 때문에 내부 코드의 validity를 검증해야 합니다. 우선 TCB의 기본 틀은 다음과 같습니다.

회색 부분은 앞으로 나올 알고리즘이 return하는 코드들에 의해 대체됩니다.

회색 부분 중 먼저 Predicate을 생성하는 알고리즘을 살펴봅시다!

Algorithm 2: Synthesize a predicate

depth는 code의 size를 의미하며, 일정한 확률로 SynNeg, SynCon, SynDis, SynAtom을 호출하게 됩니다. 각각 not, and, or 을 의미하며 SynAtom을 호출하는 경우에는 무작위로 한 변수를 상수와 비교하거나, 변수와 변수를 비교하는 predicate을 만들게 됩니다. 

Algorithm 3: Synthesize valid expressions

다음은 predicate에 이어 expressions를 생성하는 과정입니다. 다시 한번 강조하지만 TCB의 경우 실행이 되는 구문이기 때문에 valid한 expressions가 생성되어야 합니다. 유효한 expressions들을 생성하기 위해서는 env에서 랜덤으로 valid한 expressions 들을 원소로 갖는 worklist가 만들어져야 합니다. 이후 v에 해당 worklist에서 랜덤으로 한 개 (bop의 경우 2개)의 변수를 할당하고 uop_list 혹은 bop_list (Figure 5 참고) 를 바탕으로 유효한 expression을 만듭니다. undefined behavior가 발생하지 않는다면 worklist 에서 v 혹은 {u,v} 를 제거합니다. 이후 break문을 통해 반복문을 벗어나고 worklist의 원소가 1개가 될 때까지 while 문을 반복한 후 worklist에 있는 expression을 return 합니다. 다만 여기서 Unary Expressions의 경우 worklist가 줄어들지 않는 상황이 발생합니다. 따라서 해당 코드에서는 명시되지 않았지만 별도로 counter 변수를 선언하여 반복문의 제한을 두었습니다.

valid한 expressions를 생성하기 위해 line 8 과 line 17 에서 IsUndefined()를 활용하고 있습니다. Expression e의 validity를 검증하기 위해서는 e의 child expressions들의 값들을 추측할 수 있어야 합니다. 이를 Spex(env, e) 를 통해 수행하게 되는데 우선 아래 사진을 먼저 살펴봅시다.

env에 v가 존재한다면 바로 env에서 v를 가져오면 됩니다. 만약 e가 unary expressions인 경우, 각각의 child-expressions 에 uop를 적용하여 값을 구해주면 됩니다. binary expressions의 경우 각 항에 Spex를 각각 적용한 값의 cartesian product를 구해주면 됩니다. (이후 이 product를 가지고 bop 연산자를 적용시켜 validity를 검증하는 것 같습니다. 확실하진 않습니다😂)

 

이후 위에서 Undefined Behavior를 막기 위해 값들을 추측하는 것과 유사하게 Program Point에서의 env 를 추측하여 Code Insertion 이후 프로그램이 이전과 달라지지는 않았는지, 즉 Seed Program의 EMI variants가 제대로 만들어졌는지 검사를 진행하게 됩니다.

 

이러한 strategies 들을 가지고 GCC와 LLVM의 컴파일 버그를 추적한 결과 총 168개의 컴파일 버그 (duplicate, invalid 제외)를 발견했다고 합니다. 기존 Orion, Athena 보다 더 많은 버그를 단시간에 효율적으로 추적한 것으로 보입니다. 다음은 Hermes가 발견한 컴파일 버그의 일부입니다.

느낀점

이렇게 논문을 꼼꼼하게 읽어본 게 얼마만인지 ^^... 고등학교 때는 미디어 관련 논문들은 많이 읽어봤다만... 수식과 코드로 가득한 논문들은 처음이라 꽤나 애를 먹었다... 시간도 별로 나지 않았던 터라 짬 내서 읽었는데 그렇게 끊겨서 읽은 것치고는 이해도가 나쁘지 않아 뿌듯... ㅎㅎ 사실 다음에 읽을 논문이 더 어려워 보여서 두렵긴 하지만 노력하면 못 할 것이 뭔들 있겠니 라는 마음으로 ~  이러한 것들을 파이썬에 적용시켜야 할텐데 시간이 난다면 몇개 예시도 찾아보고 싶다... 허허