기본 개념 정리

조은선 교수님의 컴파일러 수업 마지막 PPT를 참고 했습니다.

CFA

프로그램의 가능한 수행 순서 == 브랜치가 있는가 없는가.

(out of scope)여기서 단순히 ‘n개의 갈림길이 있음’에 그치지 않고

• 이쪽 경로로 갈수 있는가(+ 각 경로에서 변수가 어떤값인가) => 심볼릭 익스큐션(그때 판단의 결과를 주는 엔진이 SMT solver.)
• 실제 값을 넣고 어느 방향으로 가는지 확인 => 프로파일링(동적)

우선은 ‘모든 경로 다 갈수있다’의 관점에서 서술함. 수업시간에 베이직 블록으로 나누고, CFG를 그리던 그것에 해당함.

기드라 이용 관점 -> 저기 out of scope에 도전하는 것 아니면 건들 것 없음. 기드라가 CFG를 이쁘게 그려준다.

DFA - reaching definition

프로그램 내에 각 data들이 생성/소멸 되는 정보 모으기.

? 왜 하는가
만약 ‘변수 x’ 가 위험하다는 결과가 도출되었다면?

1. 이 변수가 재선언 되었다면?
2. 이 변수가 값이 상수 등으로 재 초기화 되었다면?
3. 특정경로는 위험하고, 특정경로는 안 위험한데?.. 애매한데, 다 x다.

=> 이를 위해서 DFA를 한 것. 이 분석을 reaching definition 이라고 함. (즉 분기문을 안쓰고, 모든 변수를 재 선언 안한다면 쓸필요가 없겠지?)

SSA => assignment마다, 분기 끝마다 일회용 이름을 부여해버리며 get/kill 구하며 하는 reaching definition의 역할을 그대로 할 수 있음.

기드라 사용관점 -> 할 필요 없음. high p-code가 이미 SSA 형태.

DFA - taint analysis

오염이 source에서 sink까지 도달가능한가?
개념이 너무 간단하고, 구현의 문제여서, 직접 내가 겪었던 이슈로 심화 학습을 해보았다.

반복문과, 분기로 떡칠된 저 부분을 통과후 X는 안전할까? 위험할까?
위의 x가 분기문에 도달할수 있긴할까?

1. dangerous를 발견, use def 체인을 타고 오염분석 -> CBRANCH OP를 만남(분기 시작). 어떻게 하지?
2. 저 if문 부분의 베이직 블럭을 도달한다 할까, 도달 불가라할까..

이를 해결하기 위해 CFA를 분석정밀도로 나눈 것을 보자.

• flow insensitive => 순서,/경로 다무시. => X는 안전하기도하고 아니기도하고…
  ?그럼 이런 모호한걸 어디씀 => 타입결정.
• flow sensitive => 순서를 신경씀. 하지만 경로는 분기가 합쳐지는 곳에는 phi노드로 퉁침 -> 오염 전파는 보통 둘중 하나가 오염이면 오염으로 퉁침.
• Path-sensitive => 모든 가능한 경로를 독립적으로 추정.(DFS 느낌)

실전 코드는 정말 길이가 어마어마한만큼 3번을 선택하면 무조건 경로가 폭발한다.
=> 2번 방식을 선택후 별도의 방법을 적용하는게 합리적.

해결하려면 별도로 심볼릭 익스큐션, 프로파일링 같은 추가적인 대책이 없다면 오탐으로 남기는게 맞을듯?

반복문은?
기드라 high p-code(SSA) 상에서 루프는 헤더의 MULTIEQUAL(phi) + 백엣지로 나타난다. 아래 코드처럼 worklist + visited로 짜면 루프를 위한 별도 처리가 필요 없다.
왜인지는 클로드가 이론적으로 막 설명했는데, 굉장히 복잡해서 스킵.
직접 손으로 해보면 반복이 없어도 오염이 잘 전달된다.

기드라에서 오염분석 구현해보기.

MULTIEQUAL PcodeOP
==pcode 상의 Phi 노드
SSA form에서 제어 흐름이 합류하는 지점에 등장하는 연산이다.
예를 들어 if/else 분기 이후, 두 분기에서 각각 다른 값이 할당된 변수가 합류할 때, “어느 경로에서 왔든 이 변수다”를 표현하기 위해 사용된다.

언급했듯 하나라도 taint라면 taint 형태로 사용.

def-use 코드

// source: GetVariable 반환값 단일 Varnode
private void forwardTaint(Varnode source, HighFunction highFunc) {
    Set<Varnode> visited = new HashSet<>();// visited 셋 -> 이미 체크한 곳을 또 체크하지 않는가?
    Queue<Varnode> worklist = new LinkedList<>(); // 체크할 노드를 저장하는 queue

    worklist.add(source);//방문을 시작할 노드를 queue에 넣고
    visited.add(source);//방문 처리(재방문 방지)
    
    while (!worklist.isEmpty()) {//q가 빌때까지 = 더 방문할 노드가 없을때까지.
        Varnode curr = worklist.poll(); //큐앞에서 노드를 하나 빼서

        Iterator<PcodeOp> uses = curr.getDescendants();//이 노드가 사용되는 OP를 순회하는 이터레이터 반환
        if (uses == null) continue;

        while (uses.hasNext()) {//OP들 순회.
            PcodeOp op = uses.next();

            if (op.getOpcode() == PcodeOp.CALL ||
                op.getOpcode() == PcodeOp.CALLIND) {

                i_found_sink();//다른 함수로 이어지는 sink를 찾음. 필요한 처리를 하자.
                continue; 
            }

            Varnode output = op.getOutput();// op의 아웃풋
            if (output != null && visited.add(output)) { //null이거나 이미 방문한 varnode면 전파 끝. 
                worklist.add(output);//다음 방문리스트를 큐에 삽입.
            }
        }
    }
}

use-def 코드

// sink: memcpy size 인자 단일 Varnode
private void backwardTaint(Varnode sink, HighFunction highFunc) {
    Set<Varnode> visited = new HashSet<>();// visited 셋 -> 이미 체크한 곳을 또 체크하지 않는가?
    Queue<Varnode> worklist = new LinkedList<>();//방문 처리(재방문 방지)

    visited.add(sink);//방문을 시작할 노드를 queue에 넣고
    worklist.add(sink);//방문 처리(재방문 방지)

    while (!worklist.isEmpty()) {//더 방문할 노드가 없을때까지
        Varnode curr = worklist.poll();//하나 꺼내서

        PcodeOp def = curr.getDef(); // 이 varnode를 정의한 op

        if (def == null) {// def 없음 = 함수 파라미터 or 전역변수 등
            // 함수 경계에 도달한 것이므로 inter-procedural 필요 시 여기서 처리
            i_reached_boundary(curr);
            continue;
        }

        if (def.getOpcode() == PcodeOp.CALL ||
            def.getOpcode() == PcodeOp.CALLIND) {//싱크의 예시가 함수 호출인거지, 경우따라다름
            // 반환값이 어떤 함수 호출에서 왔음 → source 판별은 블랙박스
            i_found_source_candidate(def);
            continue;
            //소스 찾았으니 탐색 종료.
        }

        // 그 외 op의 모든 입력으로 역추적
        for (Varnode input : def.getInputs()) {
            if (!input.isConstant() && visited.add(input)) {//상수라서 추적 무의미 하거나, 방문했다면 스탑.
                worklist.add(input);
            }
        }
    }
}

들수 있는 의문점

• MULTIEQUAL Pcode OP 그렇게 강조하고 ‘그 외 op’와 같은 취급? -> worklist에는 오염된 Varnode만 들어온다. 오염된 Varnode가 MULTIEQUAL의 입력으로 사용되는 순간 계속 오염 전파됨. 그 외의 경로는 필요없음 (비오염이면? -> 애초에 도달 못함. 오염이면? -> UNION할건데 더볼필요가 없음, visited여서 continue.)
• 반복문 중간부터 오염분석을 시작하면? -> 백엣지 따라서 위에 방문안한 부분도 다 방문함.(visited가 아니므로) 사용 API들

등장하진 않았지만, 오염분석과 함께 쓰일 확률 높은 API들

API관련은, 다른 분들이 담당으로 더 잘설명해주실테니 간단하게 정리하고 패스~

그동안 시간에 쫒겨서 일단 어떻게든 하다가, 제대로 이해하니 참 좋다.

다시보니 서웅이가 학기초에 발표한 내용과 조금 겹치는것 같기도함. 남의 발표를 귀기울이자…

일부러 함수 간 전파는 뺐다. 함수간 전파까지 한번에 구현한후 오류가 터지면

1. 함수내에서 복잡도가 터짐
2. 함수밖에서 복잡도가 터짐
3. etc

죽음의 N지선다에 걸리게 될것이다. 겸손하게 차례차례 구현하자.

다음주에는 함수간 오염 전파에대해서 다뤄보고 싶다.