% 기 - 코드는 빠르게 변하며 이를 제때 검증하려면 insensitive하지 않은 분석이 필요하다. % 승 - 다음의 flow-, context-, 등의 insensitive 분석이 있다. % 전 - 쓰이는 실예는 다음과 같이 있다. % 결 - 이러한 접근법으로 def-use graph program slicing을 어떻게 빠르게 할까

Abstract

코드는 빠르게 변하며, 이를 효과적으로 검증하기 위해서는 둔감 (insensitive) 분석이 필수적이다. 이 글에서는 흐름 둔감 분석의 정의와 사용례를 소개하고, 이를 다중 지향성 퍼징을 위한 정적 분석기의 정의-사용 그래프 생성 작업에 어떻게 적용할지 논한다.

본문

둔감한 (insensitive) 분석은 코드의 빠른 변화를 효과적으로 검증하는 데 필수적이며, 대표적으로 흐름 (flow) 둔감 분석이 있다. 이는 코드의 실행 순서를 고려하지 않고, 모든 라벨의 값을 동시에 계산하여 코드의 복잡한 흐름을 단순화한다. 흐름 둔감 분석은 여러 사례에서 사용된다. 예를 들어, GCC 컴파일러의 변수 초기화 경고 (Wmaybe-uninitialized)가 초기화되지 않은 변수를 탐지할 때, 그리고 정적 분석기 ’’ 스패로우’‘가 시공간적 듬성함 (sparsity)을 파악하기 위해 애벌 분석 (pre-analysis)을 수행할 때 등이다.

%% 한편, 맥락 둔감 분석은 함수 호출 시 호출자 문맥을 무시하고, 모든 호출을 동일한 맥락으로 분석해 속도를 높이지만, 성능 저하의 단점이 있다. 이를 보완하기 위해 $k$단계 제어 흐름 분석($k$-CFA)이 존재하며, 함수 호출의 깊이를 적절히 분석한다.%%

’’ 스패로우’‘의 애벌 분석의 산물인 데이터 정의-사용 그래프가 지향성 퍼징 도구에서 중요한 역할을 맡으며, 조금 다른 정확도를 요구받고 있다. 퍼징에 적합한 슬라이스는 오류가 예상되는 목표 지점에 정확한 정의-사용 관계를 제공해야 된다. 예로, 동적 할당 지점이 힙 버퍼 오버플로를 일으킬 수 있으므로 이를 정확히 추적해야 한다. 또한, 목표 지점의 데이터에 선택적 민감도(selective sensitivity)를 도입하는 것도 고려해볼 만하다. 현재, 이러한 접근의 필요성을 확인하기 위해 기존 슬라이스가 부적합했던 벤치마크를 찾는 중이다.

지향성 퍼징에 연관 없는 지점의 데이터 흐름 추적을 억제하기 위해 플래그 관련 변수값을 고려할 수도 있다. 퍼징의 커맨드라인에서 쓰지 않는 플래그는 관련 분기와 코드 상당수가 실행이 아예 안 되지만, 정적 분석기는 이를 인식하지 못한다. 따라서 직접 해당 코드를 제거한 후 분석하는 실험을 진행 중이다. 또한, 코드 제거를 자동화하기 위해 변수 값을 상수로 초기화하고 상수 전파 최적화를 적용한 정적 분석 실험도 구상 중이다.

추가로, ’’ 스패로우’‘가 왜 데이터 정의-사용 그래프를 추출하기 전에 구간 듬성 분석을 거치는지 등 그 구조를 공부하려 한다. 최근 동료가 내놓는 혁신적인 결과들로 분석기 수정이 퍼징 성능을 끌어올릴 수 있단 걸 알고 나선, 기존 분석기 무지랭이였던 나도 분발하고픈 열의가 생긴다.