9. Program Analysis

SW Vulnerability 분석에 관한 포스팅이다. 일반적으로 프로그램은 크고 복잡하기 때문에 자동으로 검출하는 것이 목표이다. 검출하고자 하는 취약점은 Syntactic과 Semantic이다.

 

Syntactic	Semantic
buffer overflow integer overflow etc.	login vulnerabilities - memory leak - race condition

 

Bug를 찾기 위해서 분석하기도 하며, 다양한 program representation에서 수행된다. Static program analysis와 Dynamic program analysis가 있다.

 

Program representations

• Source code
• Binary code
• Intermediate representation (IR) code
• Structured representations

 

Original에 해당하는 것은 Source code와 Executable code이다. Original code는 머신이 분석하기에 어려운 코드이다. 인간 친화적이기 때문. 그래서 우리는 소스 코드를 structured representation으로 변경해줘야 한다.

 

Static program representation

다음의 형태가 있다.

• Call graph (CG)
• Points-to relations
• Control flow graph (CFG)
• Program dependence graph (PDG)

 

Call graph

Source code

function 단위로 procedure를 표현한다. Call graph를 생성하는 것은 어려운 일이다. Input에 의해 어떤 function을 호출할 지 결정되기 때문이다.

Call graph of source code

 

Points-to Relations

edge(a,b) : a points to b

프로그램 변수가 어떤 값을 가리키고 있는지 나타내는 그래프입니다. Aliases라는 개념이 사용됩니다. 두개의 expression이 하나의 메모리 공간을 point하고 있을 경우 둘의 관계를 aliase라고 합니다.

 

Program analysis의 정확도 측면에서 가장 큰 영향력을 보이는 그래프입니다. Pointers, Call-by-reference, Array indexing, C unions 등을 참고해 그래프를 생성합니다.

 

Control Flow Graph (CFG)

Basic Block(BB)를 이용해 코드를 분리하고 control flow를 나타낸다.

CFG example

BB는 분기가 일어나는 직전까지의 코드 블럭이다. Single entry와 Single exit point를 가지는 것이 특징이다.

 

Infeasible path 절대 실행이 안되는 path를 말한다.

Feasible paht 1번이라도 실행이 되는 path를 말한다.

 

Program Dependence Graph (PDG)

BB가 아닌 program statement나 instruction을 노드(코드 1줄)로 사용한다. Control dependece edge와 Data dependence edge가 있다.

 

Background: Dominator

DOM(6) = {1,3,6} / SDOM(6) = {1,3} / IDOM(6) = {3}

START → X → Y의 관계를 가지면 X는 Y의 dominator다.

Strictly dominator는 X != Y의 관계를 가지고 있다.

Immediate dominator는 dominator 중 바로 직전의 dominator를 말한다.

 

Background: Postdominator

PDOM(4) = {4,3,6} / SPDOM(4) = {3,6} / IPDOM(4) = {3}

Y → X → END의 관계를 가지고 있으면 X는 Y의 post-dominator이다.

Strictly, Immediate post-dominator가 존재한다.

 

Background: Back Edge

Back edge

Head가 tail을 dominate하는 구조이다. START → Head → Tail 구조이다. 종종 loop를 식별하는 데 사용되기도 한다.

 

PDG: Control Dependence

Example

주어진 CFG에서 control dependency는 어떻게 될까요?

Node	Dependece
entry, B1, exit	Entering code
B2	B1T
B3	B2T
B4	B1F
B5	B1F, B2F
B6	B1F, B2F

*CD(B2) = {B1T}로 작성할 수 있습니다.

 

이를 토대로 PDG:Control Dependence graph를 그리면 다음과 같습니다.

Control dependency graph

 

PDG: Data dependence

Example

마찬가지로 같은 CFG에서 Data dependence를 구해보겠습니다.

Data dependence

DD($x_{B3}$) = {B2}로 표현합니다.

 

일반적으로 Data dependece는 aliasing(여러 메모리 location이나 object를 참조하는 변수)때문에 파악하기 어려운 경우가 많습니다.

 

Dynamic program representation

다음의 방법이 가능합니다. 주로 Trace하는 방법입니다.

• Instruction trace
• Control flow trace
• Address and value trace
• Dynamic dependence trace

 

Instruction Trace

Example

실제로 instruction이 수행되는 과정을 trace해서 분석합니다. $x_i$에 대해서 $x$는 program point를 말하고 $i$는 몇 번째 실행하고 있는지를 보여줍니다.

 

Control Flow Trace

Example

BB 기준으로 trace합니다. 더 compact하게 표현하면 <T,T,F>도 가능합니다.

 

Dependence Graph

Example

Dynamic dependence graph를 trace합니다. Contro(black)l과 data(green) dependence가 있습니다.

 

Static v.s. Dynamic analysis

Static	Dynamic
부정확 Full coverage Better scalability	정확 Limited coverage Large trace and compute algorithm = slow & high space requirement
False error	no False error

Static의 부정확함을 커버하기 위해 infeasible path를 지우는 방식, 더 좋은 alias 분석, 포인터 분석 방법을 사용한다. Dynamic의 낮은 coverage를 커버하기 위해 test case를 자동으로 생성한다. Fuzzing, symbolic execution, model-based 등의 방법이 있다.

 

혹은 두 개를 적절히 섞어서 사용한다.

 

Buffer Overflow Detection & Prevention

Static analysis

Potential buffer overflow를 찾는 것이 목표이다. 기본적으로 str library function을 제외한 모든 것들은 무시한다. 그리고 len(a)는 program이 array에서 얼마나 멀리 있는지를, alloc(a)는 array가 얼마나 큰지 보여준다. 따라서 다음처럼 buffer overflow를 검출할 수 있다.

if len(a) > alloc(a) then buffer overflowed

 

Detecting during compilation

Prototype of detecting buffer overflow

하지만 다음의 한계로 인해 사용이 어려워진다.

• Double pointer
  탐지에 어려움이 있다.
• Function pointers & union types
  탐지가 불가능하다.
• C struct
  same 'type'은 aliased된다.
  Struct member는 unique memory address로 다뤄진다.

 

Taint Analysis

Taint를 확인해 Data flow를 tracking하는 방법으로 unknown attack에도 효과적이다. 주 목적은 자동으로 buffer overflow를 탐지하는 것이다. 알고리즘은 다음과 같다.

 

Taint algorithm

• 모든 input을 tainted로 mark한다.
• Tainted data가 어떻게 propagate하는지 모니터링한다.
• 위험하게 사용될 경우 attack으로 간주한다.

 

이렇게 하는 이유는, 공격자가 내부 값을 바꾸기 위해서는 input을 사용할 수 밖에 없다는 점을 공략하기 위해서이다. 변수인 input만 trace하면서 attack을 검출한다.

 

Binary Instrumentation

Instruction을 tainted memory에서 수행하는 방법이다.

Binary instrumentation

Pros	Cons
source code 필요 없음 안정적으로 overwrite attack 검출	Large run-time overhead Coverage

 

Fuzzing

Random input을 마구잡이로 test program에 넣어서 비정상적 행동을 이끌어 내면 공격 성공으로 간주하는 공격 방법이다.

Fuzzing

Error를 보고 프로그램을 파악한다. 관측할 수 있는 에러의 종류는 다음과 같다.

• Crash (ex. assert fail)
• Memory error
• Lock
• etc..

 

Mutation-based Fuzzing

Mutation-based fuzzing

잘 만든 seed input을 기준으로 랜덤하게 mutate해서 fuzzing을 수행한다.

Pros	Cons
쉽고 자동화됨 Input format에 대한 지식 없어도 괜찮음	seed input이 얼마나 좋은지에 성능이 결정됨

유한한 테스트 범위 내에서 종료되지만, seed input이 비효율적인 경우 오래걸릴 수 있다.

 

Generation-based Fuzzing

Generation-based fuzzing

문서 기반의 input format을 보고 anomaly를 넣을 수 있는 곳에 넣어서 input을 만들고 fuzzing을 수행한다.

Pros	Cons
Protocol에 대한 지식을 사용함으로 랜덤보다 성능이 좋아짐	구현하기 어려움

무한한 테스트 케이스가 수행되었음에도 에러가 없을 수 있다. 이 경우 수동적 분석을 시도해야 한다.

 

Code Coverage

Code 내 특정 범위의 내용이 얼마나 실행되었는지 수치로 나타내는 방법이다. Fuzzing에 유용하다. Fuzzing을 수행하면서 Coverage 수를 확인하고 모든 케이스에 대해서 fuzzing이 이루어지고 있는지 확인할 수 있기 때문이다.

 

Line coverage 얼마나 많은 line이 실행되었는가

Branch coverage 얼마나 많은 branch가 실행되었는가

Path coverage CFG에서 얼마나 많은 path가 실행되었는가

 

좋은 fuzzing을 수행하기 위해서는 골구로 충분히 많은 양의 실행횟수가 있어야 한다.

 

Coverage-Guided Gray-Box Fuzzing

Mutation-based fuzzing의 특별한 방법이다. 다음의 방법으로 사용된다.

 

• Instrumented program에 mutated input을 돌려서 coverage를 측정한다.
• Coverage가 증가한 mutant를 찾아서 사용한다.

 

Genetic algorithm과 유사한 방법이다.

 

American Fuzzy Lop

Seed based Fuzzing

주어진 input에 대한 code path를 모니터링해서 새로운 code path를 찾는 input을 mutate한다. 느리고 큰 input은 스킵할 수 있다는 장점이 있다.

 

Coverage-guided Fuzzing Challenge

몇 코드는 매우 적은 input에 대해서만 동작할 수 있다. 이 경우 coverage가 증가하기 위해 매우 많은 input을 넣어보는 참사가 발생할 수 있다. 휴리스틱하게 fuzzing하거나 symbolic execution을 수행한다.