컴파일러와 정적 분석기의 구조

컴파일러의 구성 요소

컴파일러는 소스 코드를 기계 코드로 변환하는 핵심 도구입니다. 이 과정은 여러 단계로 구성되며, 각 단계는 특정 역할을 담당합니다.

1. 어휘 분석기(Scanner)

정규 표현식을 활용하여 소스 코드를 토큰으로 변환합니다. 이 단계에서는 단어의 철자와 의미적正確성을 검증합니다.

2. 구문 분석기(Parser)

문맥 자유 문법을 기반으로 토큰을 추상 구문 트리(AST)로 파싱합니다. 문장의 문법적 구조를 검증하며, 문맥 비감지 특성을 사용하여 분석 속도를 최적화합니다.

3. 의미 분석기(Type Checker)

속성 문법을 활용하여 의미적合理성을 검증합니다. 타입 검사와 범위 확인 등의 작업을 수행합니다.

4. 변환기(Translator)

decorated AST를 중간 표현(IR)로 변환합니다. 이 단계에서 정적 분석이 이루어지며, 코드 최적화나 취약점 탐지 작업이 진행됩니다.

5. 코드 생성기(Code Generator)

IR을 최종 기계 코드로 변환합니다.

추상 구문 트리와 중간 표현의 비교

추상 구문 트리(AST)의 특성

• 고-level 표현으로 구문 구조에 근접
• 프로그래밍 언어에 종속
• 빠른 타입 검사에 적합
• 제어 흐름 정보가 직접적으로 표현되지 않음
• 인간이 읽기에는 적합하지만 분석에는 한계

중간 표현(IR)의 특성

• low-level 표현으로 기계 코드에 근접
• 언어 독립적
• 간결하고统一的 구조
• 제어 흐름 정보 포함
• 정적 분석의 기반이 됨

Three-Address Code (3AC)

삼주소码(3AC)는 각 명령어가 최대 세 개의 주소를 포함하는 코드 형식입니다. 오른쪽 구조에는 최대 하나의 연산자만 존재하며, 주소는 다음 세 가지 형태 중 하나입니다:

• 변수: a, b
• 상수: 3, 5
• 임시 변수: t1, t2 (컴파일러가 자동 생성)

변환 예시: t2 = a + b + 3

t1 = a + b
t2 = t1 + 3

3AC 명령어 형식

x = y bop z     // 이항 연산 (+, -, *, /)
x = uop y       // 단항 연산 (부정, 논리 NOT)
goto L          // 무조건 분기
if x rop y goto L  // 조건 분기 (<, >, ==, >=, <=)
if x goto L     // 조건 분기

실제 정적 분석 도구: Soot 프레임워크

Soot는 Java 바이트코드 분석 및 최적화를 위한 프레임워크입니다. Jimple은 Soot에서 제공하는 중간 표현으로, 복잡한 바이트코드 명령어를 삼주소码 형태로 단순화합니다.

원본 Java 코드:

package analysis.examples;

public class WhileLoopExample {
    public static void main(String[] args) {
        int[] data = new int[15];
        int counter = 0;
        while (data[counter] < 100) {
            counter = counter + 2;
        }
    }
}

변환된 Jimple 코드:

public static void main(java.lang.String[])
{
    int[] r0;
    int $counter, counter1;
    java.lang.String[] r1;
    r1 := @parameter0: java.lang.String[];
    r0 = newarray (int)[15];
    counter1 = 0;
 label1:
    $counter = r0[counter1];
    if $counter >= 100 goto label2;
    counter1 = counter1 + 2;
    goto label1;
 label2:
    return;
}

Jimple 기본 명령어:

invokespecial: 생성자, 슈퍼클래스 메서드, private 메서드 호출
invokevirtual: 인스턴스 메서드 호출 (가상 디스패치)
invokeinterface: 인터페이스 메서드 호출
invokestatic: 정적 메서드 호출

메서드 시그니처 형식: 클래스명_반환타입_메서드명(매개변수타입)

Static Single Assignment (SSA)

SSA의 정의

정적 단일 할당(SSA)은 각 변수에 정확히 한 번만 값을 할당하는IR形式입니다. 각 변수에는 단일 정의점이 존재하며, 동일한 변수에 여러 번 할당되지 않습니다.

Φ 함수 (phi-function)

SSA에서는 제어 흐름이 합류하는 지점에서 Φ 함수를 사용합니다. 이 함수는 여러 경로에서 온 값들을 선택합니다:

x2 = Φ(x0, x1)  // 제어 흐름 경로에 따라 x0 또는 x1을 선택

SSA의 장단점

장점:

• 제어 흐름 정보가 변수 이름에 암묵적으로 포함
• 정의-사용 관계가 명확하여 분석이 용이
• 최적화 알고리즘의 성능 향상

단점:

• 제어 흐름 분기가 많은 경우 과도한 변수 생성
• 기계 코드 변환 시 성능 저하 가능성

기본 블록 (Basic Blocks)

기본 블록의 정의

기본 블록은 다음 조건을 만족하는 가장 긴 연속적인 삼주소码 단위입니다:

• 블록의 첫 명령어만 진입점으로 사용 가능
• 블록의 마지막 명령어만 탈출점으로 사용 가능

기본 블록 구성 알고리즘

입력: 삼주소指令 시퀀스 P

출력: P의 기본 블록 목록

단계 1: 리더(Leader) 식별

• P의 첫 번째 명령어는 리더
• 조건부/무조건 분기의目标是 리더
• 조건부/무조건 분기 명령어의 다음 명령어는 리더

단계 2: 블록 구성

각 리더부터 다음 리더까지의 명령어 집합을 하나의 기본 블록으로 구성합니다.

제어 흐름 그래프 (CFG)

CFG의 역할

삼주소码는 최종적으로 제어 흐름 그래프(CFG)에서 분석됩니다. CFG는 정적 분석의 기반 구조이며, 노드는 개별 3AC 명령어 또는 기본 블록이 될 수 있습니다.

엣지 추가 규칙

• 두 기본 블록이 연속적으로 실행되고 분기가 없는 경우 엣지 추가
• 무조건 분기: 분기 소스 → 대상 블록
• 조건 분기: 조건 만족 시 소스 → 대상 블록

전체 CFG 구조

CFG에는 시작 노드(Entry)와 종료 노드(Exit)가 추가되어 초기화와 종료를 나타냅니다. 노드 A에서 노드 B로의 엣지가 존재하면, A는 B의 전임자(predecessor)이고 B는 A의 후임자(successor)입니다.

       [Entry]
          |
    +-----+-----+
    |           |
  [BB1]       [BB2]
    |           |
    +-----+-----+
          |
       [Exit]

이렇게 구성된 CFG를 기반으로 다양한 정적 분석 기법(데이터 흐름 분석, 제어 흐름 분석 등)을 적용할 수 있습니다.