C 프로그램의 버퍼 오버런(buffer overrun) 오류를 찾아 주는 정적 분석기의 설계와 구현 = Design and Implementation of Static Program Analyzer Finding All Buffer Overrun Errors in C Programs

국문 초록 (Abstract)

이 논문에서는 정적 프로그램 분석(static program analysis)과 통계적 분석(statistical analysis)의 조합을 가지고 실제적인 C 프로그램을 검증한 경험을 보고한다. 정적 분석과 통계적 분석의 조합은 입력 프로그램에 제한을 두지 않는 정적 분석기에서 발생하는 불가피한 허위 경보를 줄이기 위한 것이다. 우리는 ANSI C 프로그램이 실행 중에 겪을 수 있는 모든 배열 참조 오류(buffer overrun)를 찾아주는 정적 프로그램 분석기 아이락(Airac, Array Index Range Analyzer for C)을 고안하고 구현하였다. 분석의 안전성(soundness)을 유지하면서 프로그램 분석 분야에서 오랫동안 축적된 기술들을 활용하여 분석 비용 절감 및 정확도 향상을 달성했다. 대상 프로그램에 제한을 두지 않는 안전한 분석은 정확도에 한계가 있으므로 불가피한 허위 경보가 존재할 수 있다. 이러한 허위 경보(예를 들어 530만 줄짜리 상용 C 프로그램에 대한 분석 결과 아이락은 970개의 배열 참조 오류 경보를 발생시켰으나 그 중 737개는 허위 경보였다.)에 대처하기 위해 우리는 통계적 사후 분석을 시도하였다. 통계적 사후 분석은 주어진 경보가 실제 오류를 가리킬 확률을 계산한다. 이렇게 계산된 확률은 두 가지 방법으로 사용된다. 1) 경보를 걸러내거나, 2) 실제 오류에 대한 경보일 가능성이 높은 것들을 우선적으로 사용자에게 보여준다. 우리는 리눅스 커널 프로그램과 알고리즘 교과서의 프로그램들을 대상으로 실험을 수행했다. 우리 실험에서 실제 오류를 놓칠 위험이 허위 경보의 위험의 3배라고 설정한 경우 74.83%의 허위 경보를 걸러낼 수 있었고, 참일 확률이 높은 경보부터 검증하는 경우 15.17%의 허위 경보만이 실제 오류 50%와 섞여 있었다.

다국어 초록 (Multilingual Abstract)

We present our experience of combining, in a realistic setting, a static analyzer with a statistical analysis. This combination is in order to reduce the inevitable false alarms from a domain-unaware static analyzer. Our analyzer named Airac(Array Index Range Analyzer for C) collects all the true buffer-overrun points in ANSI C programs. The soundness is maintained, and the analysis' cost-accuracy improvement is achieved by techniques that static analysis community has long accumulated. For still inevitable false alarms (e.g. Airac raised 970 buffer-overrun alarms in commercial C programs of 5.3 million lines and 737 among the 970 alarms were false), which are always apt for particular C programs, we use a statistical post analysis. The statistical analysis, given the analysis results (alarms), sifts out probable false alarms and prioritizes true alarms. It estimates the probability of each alarm being true. The probabilities are used in two ways: 1) only the alarms that have true-alarm probabilities higher than a threshold are reported to the user; 2) the alarms are sorted by the probability before reporting, so that the user can check highly probable errors first. In our experiments with Linux kernel sources, if we set the risk of missing true error is about 3 times greater than false alarming, 74.83% of false alarms could be filtered; only 15.17% of false alarms were mixed up until the user observes 50% of the true alarms.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 분석기 설계
• 3. 통계적 사후 분석
• 4. 관련 연구
• 5. 토의 및 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

• 1 "bugtraq"
• 2 Laurent Mauborgne, "Trace partitioning in abstract interpretation based static analyzers." Springer-Verlag 3444 : 5-20, 2005.
• 3 Patrick Cousot, "The astr´ee analyzer." 3444 : 21-30, 2005.
• 4 Patrick Cousot, "The astr´ee analyzer." 3444 : 21-30, 2005.
• 5 N. Metropolis, "The Monte Carlo method" 44 (44): 335-341, 1949
• 6 Richard Lippmann, "Testing static analysis tools using exploitable buffer overflows from open source code." ACM Press 97-106, 2004.
• 7 Patrick Cousot, "Systematic design of program analysis frameworks." 269-282, 1979.
• 8 James O. Berger., "Statistical Decision Theory and Bayesian Analysis, 2nd Edition" Springer 1985.
• 9 David Hovemeyer, "Finding bugs is easy." 39 (39): 92-106, 2004
• 10 Michael Rodeh, "Cssv : towards a realistic tool for statically detecting all buffer overflows" 155-167, 2003.
• 11 Patrick Cousot, "Comparing the galois connection and widening/narrowing approaches to abstract interpretation." Springer-Verlag 269-295, 1992.
• 12 "CERT/CC advisories"
• 13 Andrew Gelman, "Bayesian Data Analysis. Text in Statistical Science." Chapman & Hall/CRC 2004.
• 14 Yichen Xie, "Archer : path-sensitive analysis to detect memory access errors." ACM Press 327-336, 2003.
• 15 Patrick Cousot, "Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints" 238-252, 1977
• 16 Bruno Blanchet, "A static analyzer for large safety-critical software." 196-207, 2003