Kang SeoYeon

Kang SeoYeon

(in progress) Obfuscator 프로젝트

[난독화]Opaque predicates를 이용한 난독화

2 minute read

https://github.com/yonniii/miniC_obfuscation

난독화의 품질 (참고)

난독화의 품질을 평가하는 기준은 4가지가 있다.

  1. 효과(the potency): 프로그램이 얼마나 모호해지는지
  2. 복원력(the resilience): 자동 역난독화기가 얼마나 부수기(break) 어려워하는지
  3. 잠행(the stealth): 난독화한 코드가 기존의 프로그램에 얼마나 자연스럽게 섞이는지
  4. 비용(the cost): 난독화한 프로그램의 계산적 오버헤드가 얼마나 더해지는지

프로그램을 더 모호하게 하는게 무엇인지 알기 위해서 Software Complexity Metrics를 검토하자. McCabe 순환복잡도에 따르면, predicate의 수에 따라서 프로그램의 복잡도가 증가한다. 그리고 Harrison에 따르면, 프로그램의 복잡도는 조건문과 루프 구조의 중첩된 레벨에 비례한다. 다른 매트릭스에서는 아래의 4가지가 프로그램의 복잡도를 증가시키는 것을 알 수 있다.

  1. 데이터구조의 복잡도
  2. 변수가 사이에 블럭의 수? or 변수가 의존하는 블럭의 수?(the number of inter-basic block variable dependencies)
  3. formal 파라미터의 수
  4. 상속한 트리의 depth

위의 기준들을 만족하면 더욱 강력하게 난독화 할 수 있다.

[참고] Collberg, C., Thomborson, C., Low, D.: Manufacturing cheap, resilient, and stealthy opaque constructs. In: POPL ’98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Prin- ciples of programming languages, pp. 184–196. ACM, New York, NY, USA (1998).

Obfuscation based on opaque predicate

Opaque predicate란?

항상 참 또는 거짓이 되는 분기문 또는 분기문의 집합을 말한다. 이것은 prior condition에 영향을 받을 수 있다. opaque predicate는 3가지 유형으로 분류된다.

image

  1. Invariant Opaque predicates
    모든 입력에 true 또는 false 중에서 하나의 값만을 가지는 분기문이다. 잘 알려진 수학적 정리나 제곱 잉여(quadratic residues)로부터 유도되는 것들이 대부분이다. *단점: fuzzing 테스팅에서 런타임 중에 변경되지 않는 값이 관찰된다. image
  2. Contextual Opaque predicates
    전제 조건하에 항상 같은 값을 내는 분기문이다. prior condition만으로 분기문의 값을 구할 수 있다. image
  3. Dynamic Opaque predicates
    어떤 경우이던지 같은 output을 내는 분기문 집합이다. 입력에 따라서 실행할때마다 분기문이 T/F로 변할 수 있지만, output은 같다. correlated, adjacent 두 가지 성질을 갖는다.

참고한 논문에 따르면, invariant opaque predicate를 풀기위한 도구는 많지만, contextual 과 dynamic은 탐지하기 어렵다.

[참고] LOOP: Logic-Oriented Opaque Predicate Detection in Obfuscated Binary Code, Jiang Ming, Dongpeng Xu, Li Wang, and Dinghao Wu
The Pennsylvania State University

CCS’15, October 12-16, 2015, Denver, Colorado, USA

opaque predicates를 이용한 난독화 방법 구현

Dynamic Opaque predicates를 이용

void main() {
    int a = 3;
    int b = 5;
    int c = 0;
    sum(1,2);
    sum(2,3);
    sub(3,4);
    sub(4,5);
}

난독화 전

void main()
{
	int a = 3;
	int b = 5;
	int c = 0;
	int p,q;
	p = rand() % 2 //p와 q는 같은 값을 갖게 됨. 0또는 1의 값
	q = p % 2
	if(p){
		sum(1, 2);
		sum(2, 3);
	} else{ 
		sum(1, 2);
		sum(2, 3);
		sub(3, 4);
	}
	if(q){
		sub(3, 4);
		sub(4, 5);
	} else{ 
		sub(4, 5);
	}
}

난독화 후

실행할 분기를 결정하기 위해서 변수 p와 q를 선언하고, 랜덤으로 0또는 1 을 값으로 갖도록 한다.

그리고 값에 따라 나누어지지만 결국 같은 실행을 하도록 코드를 작성하였다.

Contextual Opaque predicates

void main(){
    int a=3;
    if(a>1){
        _print(222);
    }
}

난독화 전

void main()
{
	int a = 3;
    if (a > 1){
        if(a*a +(-1-(1)) +(-1*-(1)) > 0 )
        {
            _print(222);
        }
    }
}

난독화 후

위의 논문에서 예시로 든 코드를 직접 구현해보았다.

You may also enjoy